Large deviation for the empirical eigenvalue density of truncated Haar unitary matrices

Let U_m be an m×m Haar unitary matrix and U_[m,n] be its n×n truncation. In this paper the large deviation is proven for the empirical eigenvalue density of U_[m,n] as m/n→λ and n→∞. The rate function and the limit distribution are given explicitly. U_[m,n] is the random matrix model of quq, where u is a Haar unitary in a finite von Neumann algebra, q is a certain projection and they are free. The limit distribution coincides with the Brown measure of the operator quq.     

On the Diaconis-Shahshahani Method in Random Matrix Theory

If Γ is a random variable with values in a compact matrix group K, then the traces Tr(Γ^j) (j ∊ N) are real or complex valued random variables. As a crucial step in their approach to random matrix eigenvalues, Diaconis and Shahshahani computed the joint moments of any fixed number of these traces if Γ is distributed according to Haar measure and if K is one of U_n, O_n or Sp_n, where n is large enough. In the orthogonal and symplectic cases, their proof is based on work of Ram on the characters of Brauer algebras. The present paper contains an alternative proof of these moment formulae. It invokes classical invariant theory (specifically, the tensor forms of the First Fundamental Theorems in the sense of Weyl) to reduce the computation of matrix integrals to a counting problem, which can be solved by elementary means.     

Maxima of entries of Haar distributed matrices

Let _n=(_ij) be an n×n random matrix such that its distribution is the normalized Haar measure on the orthogonal group O(n). Let also W_n:=max_1i,jn|_ij|. We obtain the limiting distribution and a strong limit theorem on W_n. A tool has been developed to prove these results. It says that up to n/( log n)² columns of _n can be approximated simultaneously by those of some Y_n=(y_ij) in which y_ij are independent standard normals. Similar results are derived also for the unitary group U(n), the special orthogonal group SO(n), and the special unitary group SU(n).Mathematics Subject Classification (2000):15A52, 60B10, 60B15, 60F10     

Improving the Data Augmentation Algorithm in the Two-Block Setup

The data augmentation (DA) approach to approximate sampling from an intractable probability density f_X is based on the construction of a joint density, f_{X, Y}, whose conditional densities, f_X|Y and f_Y|X, can be straightforwardly sampled. However, many applications of the DA algorithm do not fall in this “single-block” setup. In these applications, X is partitioned into two components, X = (U, V), in such a way that it is easy to sample from f_Y|X, f_{U|V, Y}, and f_{V|U, Y}. We refer to this alternative version of DA, which is effectively a three-variable Gibbs sampler, as “two-block” DA. We develop two methods to improve the performance of the DA algorithm in the two-block setup. These methods are motivated by the Haar PX-DA algorithm, which has been developed in previous literature to improve the performance of the single-block DA algorithm. The Haar PX-DA algorithm, which adds a computationally inexpensive extra step in each iteration of the DA algorithm while preserving the stationary density, has been shown to be optimal among similar techniques. However, as we illustrate, the Haar PX-DA algorithm does not lead to the required stationary density f_X in the two-block setup. Our methods incorporate suitable generalizations and modifications to this approach, and work in the two-block setup. A theoretical comparison of our methods to the two-block DA algorithm, a much harder task than the single-block setup due to nonreversibility and structural complexities, is provided. We successfully apply our methods to applications of the two-block DA algorithm in Bayesian robit regression and Bayesian quantile regression. Supplementary materials for this article are available online.     

Codimension-one minimal projections onto Haar subspaces

Let H_n be an n-dimensional Haar subspace of and let H_n−1 be a Haar subspace of H_n of dimension n−1. In this note we show (Theorem 6) that if the norm of a minimal projection from H_n onto H_n−1 is greater than 1, then this projection is an interpolating projection. This is a surprising result in comparison with Cheney and Morris (J. Reine Angew. Math. 270 (1974) 61 (see also (Lecture Notes in Mathematics, Vol. 1449, Springer, Berlin, Heilderberg, New York, 1990, Corollary III.2.12, p. 104) which shows that there is no interpolating minimal projection from C[a,b] onto the space of polynomials of degree n, (n2). Moreover, this minimal projection is unique (Theorem 9). In particular, Theorem 6 holds for polynomial spaces, generalizing a result of Prophet [(J. Approx. Theory 85 (1996) 27), Theorem 2.1].     

Universal optimality of digital nets and lattice designs

This article considers universal optimality of digital nets and lattice designs in a regression model. Based on the equivalence theorem for matrix means and majorization theory,the necessary and sufficient conditions for lattice designs being φp-and universally optimal in trigonometric function and Chebyshev polynomial regression models are obtained. It is shown that digital nets are universally optimal for both complete and incomplete Walsh function regression models under some specified conditions,and are...     

On simultaneous reduction of families of matrices to triangular or diagonal form by unitary congruences

Let {A_i }and {B_i } be two given families of n-by-n matrices. We give conditions under which there is a unitary U such that every matrix UA_iU ¹ is upper triangular. We give conditions, weaker than the classical conditions of commutativity of the whole family, under which there is a unitary U such that every matrix UA_jU ^? is upper triangular. We also give conditions under which there is one single unitary U such that every UA_iU ¹ and every UB_jU ^? is upper triangular. We give necessary and sufficient conditions for simultaneous unitary reduction to diagonal form in this way when all the A_j's are complex symmetric and all theB_j 's are Hermitian.     

Eigenvalue distributions of random unitary matrices

 Let U be an n × n random matrix chosen from Haar measure on the unitary group. For a fixed arc of the unit circle, let X be the number of eigenvalues of M which lie in the specified arc. We study this random variable as the dimension n grows, using the connection between Toeplitz matrices and random unitary matrices, and show that (X -E [X])/(\Var (X))^1/2 is asymptotically normally distributed. In addition, we show that for several fixed arcs I ₁ , ..., I _m , the corresponding random variables are jointly normal in the large n limit. Received: 15 November 2000 / Revised version: 27 September 2001 / Published online: 17 May 2002     

Asymptotics for the Euclidean TSP with power weighted edges

Summary LetU ₁,...,U_n denote i.i.d. random variables with the uniform distribution on [0, 1]², and letT ²T²(U₁,...,U_n) denote the shortest tour throughU ₁,...,U_n with square-weighted edges. By drawing on the quasi-additive structure ofT ² and the boundary rooted dual process, it is shown that lim _n E T ²(U ₁,...,U_n)= for some finite constant .This work was supported in part by NSF Grant DMS-9200656, Swiss National Foundation Grant 21-298333.90, and the US Army Research Office through the Mathematical Sciences Institute of Cornell University, whose assistance is gratefully acknowledged     

Stochastic aspects of easy quantum groups

We consider several orthogonal quantum groups satisfying the ??easiness?? assumption axiomatized in our previous paper. For each of them we discuss the computation of the asymptotic law of Tr(u ^k ) with respect to the Haar measure, u being the fundamental representation. For the classical groups O _n , S _n we recover in this way some well-known results of Diaconis and Shahshahani.     

Rate of convergence to the semi-circle law for the Deformed Gaussian Unitary Ensemble

It is shown that the Kolmogorov distance between the expected spectral distribution function of an n × n matrix from the Deformed Gaussian Ensemble and the distribution function of the semi-circle law is of order O(n ^−2/3+v ). Research supported by the DFG-Forschergruppe FOR 399/1. Partially supported by INTAS grant N 03-51-5018, by RFBF grant N 02-01-00233, by RFBR-DFG grant N 04-01-04000, by RF grant of the leading scientific schools NSh-4222.2006.1.     

Rational points on the unit sphere

It is known that the unit sphere, centered at the origin in ℝ ⁿ , has a dense set of points with rational coordinates. We give an elementary proof of this fact that includes explicit bounds on the complexity of the coordinates: for every point ν on the unit sphere in ℝ ⁿ , and every ν > 0; there is a point r = (r ₁; r ₂;…;r _n) such that:

Numerical inversion of laplace transform via wavelet in partial differential equations

This article presents a rational Haar wavelet operational method for solving the inverse Laplace transform problem and improves inherent errors from irrational Haar wavelet. The approach is thus straightforward, rather simple and suitable for computer programming. We define that P is the operational matrix for integration of the orthogonal Haar wavelet. Simultaneously, simplify the formulae of listing table (Chen et al., Journal of The Franklin Institute 303 (1977), 267–284) to a minimum expression and obtain the optimal operation speed. The local property of Haar wavelet is fully applied to shorten the calculation process in the task. The operational method presented in this article owns the advantages of simpler computation as well as broad application. We still can obtain satisfying solution even under large matrix. Moreover, we do not have numerically unstable problems. © 2013 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 30: 536–549, 2014     

Growth of connected locally compact groups

The asymptotic behavior of the Haar measure of Uⁿ = U · U ··· U, where U is a compact neighborhood of the identity in a separable, connected locally compact group, is considered. It is shown that for a given group G, the measure of Uⁿ grows at most polynomially for all U ? G, or at least exponentially for all U ? G. The groups having polynomial growth are characterized in terms of uniformly discrete free subsemigroups and in terms of the eigenvalues of elements occurring in the adjoint group of an approximating Lie group.     

Error estimates in S P for cubature formulas exact for haar polynomials in the two-dimensional case

On the spaces S _p , an upper estimate is found for the norm of the error functional δ _N (f) of cubature formulas possessing the Haar d-property in the two-dimensional case. An asymptotic relation is proved for $ \left\| {\delta _N (f)} \right\|_{S_p^* } On the spaces S _p , an upper estimate is found for the norm of the error functional δ _N (f) of cubature formulas possessing the Haar d-property in the two-dimensional case. An asymptotic relation is proved for with the number of nodes N ∼ 2 ^d , where d → ∞. For N ∼ 2 ^d with d → ∞, it is shown that the norm of δ _N for the formulas under study has the best convergence rate, which is equal to N ^−1/p . Original Russian Text ? K.A. Kirillov, M.V. Noskov, 2009, published in Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki, 2009, Vol. 49, No. 1, pp. 3–13.     

High quality preconditioning of a general symmetric positive definite matrix based on its UTU + UTR + RTU-decomposition

A new matrix decomposition of the form A = U^TU + U^TR + R^TU is proposed and investigated, where U is an upper triangular matrix (an approximation to the exact Cholesky factor U₀), and R is a strictly upper triangular error matrix (with small elements and the fill-in limited by that of U₀). For an arbitrary symmetric positive matrix A such a decomposition always exists and can be efficiently constructed; however it is not unique, and is determined by the choice of an involved truncation rule. An analysis of both spectral and K-condition numbers is given for the preconditioned matrix M = U^−T AU⁻¹ and a comparison is made with the RIC preconditioning proposed by Ajiz and Jennings. A concept of approximation order of an incomplete factorization is introduced and it is shown that RIC is the first order method, whereas the proposed method is of second order. The idea underlying the proposed method is also applicable to the analysis of CGNE-type methods for general non-singular matrices and approximate LU factorizations of non-symmetric positive definite matrices. Practical use of the preconditioning techniques developed is discussed and illustrated by an extensive set of numerical examples. Copyright © 1999 John Wiley & Sons, Ltd.     

The Entries of Haar-Invariant Matrices from the Classical Compact Groups

Let Γ _n =(γ _ij ) _n×n be a random matrix with the Haar probability measure on the orthogonal group O(n), the unitary group U(n), or the symplectic group Sp(n). Given 1≤m<n, a probability inequality for a distance between (γ _ij ) _n×m and some mn independent F-valued normal random variables is obtained, where F=ℝ, ℂ, or ℍ (the set of real quaternions). The result is universal for the three cases. In particular, the inequality for Sp(n) is new.     

On One Class of Matrix Topological *-Algebras

We study a matrix algebra M _n(U), where U is a commutative topological nuclear entire (bounded, analytic) *-algebra. We prove that M _n(U) is also a topological nuclear entire (bounded, analytic) *-algebra.