How Close is the Sample Covariance Matrix to?the?Actual Covariance Matrix?

Given a probability distribution in ? ⁿ with general (nonwhite) covariance, a classical estimator of the covariance matrix is the sample covariance matrix obtained from a sample of N independent points. What is the optimal sample size N=N(n) that guarantees estimation with a fixed accuracy in the operator norm? Suppose that the distribution is supported in a centered Euclidean ball of radius $O(\sqrt{n})$ . We conjecture that the optimal sample size is N=O(n) for all distributions with finite fourth moment, and we prove this up to an iterated logarithmic factor. This problem is motivated by the optimal theorem of Rudelson (J. Funct. Anal. 164:60?C72, 1999), which states that N=O(nlog?n) for distributions with finite second moment, and a recent result of Adamczak et al. (J. Am. Math. Soc. 234:535?C561, 2010), which guarantees that N=O(n) for subexponential distributions.     

Projections onto the set of Hankel matrices

The paper is devoted to lower estimates of the norms of the projections onto the set of Hankel matrices of order n. Let B_n be the set of operators in ² such that t_jk =0 for k+j>N and let Hank_N be the subspace in B_N consisting of those operators T for which t_jk =c_j+k (the Hankel matrices). The numbers _N are defined as the infimum of the norms of the projections of B_N onto Hank_N. The fundamental result of the paper asserts that.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 126, pp. 109–116, 1983.The author is grateful to V. V. Peller for stimulating discussions.     

Spectral norm of products of random and deterministic matrices

We study the spectral norm of matrices W that can be factored as W?=?BA, where A is a random matrix with independent mean zero entries and B is a fixed matrix. Under the (4?+???)th moment assumption on the entries of A, we show that the spectral norm of such an m × n matrix W is bounded by ${\sqrt{m} + \sqrt{n}}$ , which is sharp. In other words, in regard to the spectral norm, products of random and deterministic matrices behave similarly to random matrices with independent entries. This result along with the previous work of Rudelson and the author implies that the smallest singular value of a random m × n matrix with i.i.d. mean zero entries and bounded (4?+???)th moment is bounded below by ${\sqrt{m} - \sqrt{n-1}}$ with high probability.     

Eigenvector distribution of Wigner matrices

We consider N × N Hermitian or symmetric random matrices with independent entries. The distribution of the (i, j)-th matrix element is given by a probability measure ν _ij whose first two moments coincide with those of the corresponding Gaussian ensemble. We prove that the joint probability distribution of the components of eigenvectors associated with eigenvalues close to the spectral edge agrees with that of the corresponding Gaussian ensemble. For eigenvectors associated with bulk eigenvalues, the same conclusion holds provided the first four moments of the distribution ν _ij coincide with those of the corresponding Gaussian ensemble. More generally, we prove that the joint eigenvector–eigenvalue distributions near the spectral edge of two generalized Wigner ensembles agree, provided that the first two moments of the entries match and that one of the ensembles satisfies a level repulsion estimate. If in addition the first four moments match then this result holds also in the bulk.     

Generalized Hankel matrices of Markov parameters and their applications to control problems

The concept of Hankel matrices of Markov parameters associated with two polynomials is generalized for matrices. The generalized Hankel matrices of Markov parameters are then used to develop methods for testing the relative primeness of two matrices A and B, for determining stability and inertia of a matrix, and for constructing a class of matrices C such that A + C has a desired spectrum. Neither the method of construction of the generalized Hankel matrices nor the methods developed using these matrices require explicit computation of the characteristic polynomial of A (or of B).     

On conditions for permutability of Toeplitz and Hankel matrices

The problem of describing pairs of commuting matrices (T, H), where T and H are a Toeplitz and a Hankel matrix, respectively, is examined. Several families of such pairs are indicated.     

Relatively prime polynomials and nonsingular Hankel matrices over finite fields

The probability for two monic polynomials of a positive degree n with coefficients in the finite field Fq to be relatively prime turns out to be identical with the probability for an n×n Hankel matrix over Fq to be nonsingular. Motivated by this, we give an explicit map from pairs of coprime polynomials to nonsingular Hankel matrices that explains this connection. A basic tool used here is the classical notion of Bezoutian of two polynomials. Moreover, we give simpler and direct proofs of the general formulae for the number of m-tuples of relatively prime polynomials over Fq of given degrees and for the number of n×n Hankel matrices over Fq of a given rank.     

A note on the perturbation of positive matrices by normal and unitary matrices

In a recent paper, Neumann and Sze considered for an n × n nonnegative matrix A, the minimization and maximization of ρ(A + S), the spectral radius of (A + S), as S ranges over all the doubly stochastic matrices. They showed that both extremal values are always attained at an n × n permutation matrix. As a permutation matrix is a particular case of a normal matrix whose spectral radius is 1, we consider here, for positive matrices A such that (A + N) is a nonnegative matrix, for all normal matrices N whose spectral radius is 1, the minimization and maximization problems of ρ(A + N) as N ranges over all such matrices. We show that the extremal values always occur at an n × n real unitary matrix. We compare our results with a less recent work of Han, Neumann, and Tastsomeros in which the maximum value of ρ(A + X) over all n × n real matrices X of Frobenius norm was sought.     

Local laws for non-Hermitian random matrices

The product of m ∈ N independent random square matrices whose elements are independent identically distributed random variables with zero mean and unit variance is considered. It is known that, as the size of the matrices increases to infinity, the empirical spectral measure of the normalized eigenvalues of the product converges with probability 1 to the distribution of the mth power of the random variable uniformly distributed on the unit disk of the complex plane. In particular, in the case of m = 1, the circular law holds. The purpose of this paper is to prove the validity of the local circular law (as well as its generalization to the case of any fixed m) in the case where the distribution of the matrix elements has finite absolute moment of order 4 + δ,δ > 0,. Recent results of Bourgade, Yau, and Yin, of Tao and Vu, and of Nemish are generalized.     

Unitary similarity to a normal matrix

We give several criteria of unitary similarity of a normal matrix A and any matrix B in terms of the Frobenius and spectral norms, characteristic polynomials, and traces of matrices.     

Linear systems and determinantal random point fields

In random matrix theory, determinantal random point fields describe the distribution of eigenvalues of self-adjoint matrices from the generalized unitary ensemble. This paper considers symmetric Hamiltonian systems and determines the properties of kernels and associated determinantal random point fields that arise from them; this extends work of Tracy and Widom. The inverse spectral problem for self-adjoint Hankel operators gives sufficient conditions for a self-adjoint operator to be the Hankel operator on L²(0,∞) from a linear system in continuous time; thus this paper expresses certain kernels as squares of Hankel operators. For suitable linear systems (−A,B,C) with one-dimensional input and output spaces, there exists a Hankel operator Γ with kernel ?(x)(s+t)=Ce−(2x+s+t)AB such that gx(z)=det(I+(z−1)ΓΓ†) is the generating function of a determinantal random point field on (0,∞). The inverse scattering transform for the Zakharov-Shabat system involves a Gelfand-Levitan integral equation such that the trace of the diagonal of the solution gives . When A?0 is a finite matrix and B=C†, there exists a determinantal random point field such that the largest point has a generalised logistic distribution.     

Gauss inequalities on ordered linear spaces

Markov inequalities on ordered linear spaces are tightened through the α-unimodality of the corresponding measures. Modality indices are studied for various induced measures, including the singular values of a random matrix and the periodogram of a time series. These tools support a detailed study of linear inference and the ordering of random matrices, to include fixed and random designs and probability bounds on their comparative efficiencies. Other applications include probability bounds on quadratic forms and of order statistics on Rⁿ, on periodograms in the analysis of time series, and on run-length distributions in multivariate statistical process control. Connections to other topics in applied probability and statistics are noted.     

On the reduction of the normal Hankel problem to two particular cases

The normal Hankel problem (NHP) is to describe complex matrices that are normal and Hankel at the same time. The available results related to the NHP can be combined into two groups. On the one hand, there are several known classes of normal Hankel matrices. On the other hand, the matrix classes that may contain normal Hankel matrices not belonging to the known classes were shown to admit a parametrization by real 2 × 2 matrices with determinant 1. We solve the NHP for the cases where the characteristic matrix W of the given class has: (a) complex conjugate eigenvalues; (b) distinct real eigenvalues. To obtain a complete solution of the NHP, it remains to analyze two situations: (1) W is the Jordan block of order two for the eigenvalue 1; (2) W is the Jordan block of order two for ?1.     

The norm of polynomials in large random and deterministic matrices

Let ${{\bf X}_N =(X_1^{(N)}, \ldots, X_p^{(N)})}$ be a family of N × N independent, normalized random matrices from the Gaussian Unitary Ensemble. We state sufficient conditions on matrices ${{\bf Y}_N =(Y_1^{(N)}, \ldots, Y_q^{(N)})}$ , possibly random but independent of X _N , for which the operator norm of ${P({\bf X}_N, {\bf Y}_N, {\bf Y}_N^*)}$ converges almost surely for all polynomials P. Limits are described by operator norms of objects from free probability theory. Taking advantage of the choice of the matrices Y _N and of the polynomials P, we get for a large class of matrices the ??no eigenvalues outside a neighborhood of the limiting spectrum?? phenomena. We give examples of diagonal matrices Y _N for which the convergence holds. Convergence of the operator norm is shown to hold for block matrices, even with rectangular Gaussian blocks, a situation including non-white Wishart matrices and some matrices encountered in MIMO systems.     

Smallest singular value of random matrices with independent columns

We study the smallest singular value of a square random matrix with i.i.d. columns drawn from an isotropic symmetric log-concave distribution. We prove a deviation inequality in terms of the isotropic constant of the distribution. To cite this article: R. Adamczak et al., C. R. Acad. Sci. Paris, Ser. I 346 (2008).     

Contractions with rank one defect operators and truncated CMV matrices

The main issue we address in the present paper are the new models for completely nonunitary contractions with rank one defect operators acting on some Hilbert space of dimension N?∞. These models complement nicely the well-known models of Livšic and Sz.-Nagy-Foias. We show that each such operator acting on some finite-dimensional (respectively, separable infinite-dimensional Hilbert space) is unitarily equivalent to some finite (respectively semi-infinite) truncated CMV matrix obtained from the “full” CMV matrix by deleting the first row and the first column, and acting in CN (respectively ?²(N)). This result can be viewed as a nonunitary version of the famous characterization of unitary operators with a simple spectrum due to Cantero, Moral and Velázquez, as well as an analog for contraction operators of the result from [Yu. Arlinski?, E. Tsekanovski?, Non-self-adjoint Jacobi matrices with a rank-one imaginary part, J. Funct. Anal. 241 (2006) 383-438] concerning dissipative non-self-adjoint operators with a rank one imaginary part. It is shown that another functional model for contractions with rank one defect operators takes the form of the compression f(ζ)→PK(ζf(ζ)) on the Hilbert space L²(T,dμ) with a probability measure μ onto the subspace K=L²(T,dμ)?C. The relationship between characteristic functions of sub-matrices of the truncated CMV matrix with rank one defect operators and the corresponding Schur iterates is established. We develop direct and inverse spectral analysis for finite and semi-infinite truncated CMV matrices. In particular, we study the problem of reconstruction of such matrices from their spectrum or the mixed spectral data involving Schur parameters. It is pointed out that if the mixed spectral data contains zero eigenvalue, then no solution, unique solution or infinitely many solutions may occur in the inverse problem for truncated CMV matrices. The uniqueness theorem for recovered truncated CMV matrix from the given mixed spectral data is established. In this part the paper is closely related to the results of Hochstadt and Gesztesy-Simon obtained for finite self-adjoint Jacobi matrices.     

The Limiting Spectral Measure for Ensembles of Symmetric Block Circulant Matrices

Given an ensemble of N×N random matrices, a natural question to ask is whether or not the empirical spectral measures of typical matrices converge to a limiting spectral measure as N→∞. While this has been proved for many thin patterned ensembles sitting inside all real symmetric matrices, frequently there is no nice closed form expression for the limiting measure. Further, current theorems provide few pictures of transitions between ensembles. We consider the ensemble of symmetric m-block circulant matrices with entries i.i.d.r.v. These matrices have toroidal diagonals periodic of period m. We view m as a “dial” we can “turn” from the thin ensemble of symmetric circulant matrices, whose limiting eigenvalue density is a Gaussian, to all real symmetric matrices, whose limiting eigenvalue density is a semi-circle. The limiting eigenvalue densities f _m show a visually stunning convergence to the semi-circle as m→∞, which we prove. In contrast to most studies of patterned matrix ensembles, our paper gives explicit closed form expressions for the densities. We prove that f _m is the product of a Gaussian and a certain even polynomial of degree 2m?2; the formula is the same as that for the m×m Gaussian Unitary Ensemble (GUE). The proof is by derivation of the moments from the eigenvalue trace formula. The new feature, which allows us to obtain closed form expressions, is converting the central combinatorial problem in the moment calculation into an equivalent counting problem in algebraic topology. We end with a generalization of the m-block circulant pattern, dropping the assumption that the m random variables be distinct. We prove that the limiting spectral distribution exists and is determined by the pattern of the independent elements within an m-period, depending not only on the frequency at which each element appears, but also on the way the elements are arranged.     

On limit theorem for the eigenvalues of product of two random matrices

The existence of limiting spectral distribution (LSD) of the product of two random matrices is proved. One of the random matrices is a sample covariance matrix and the other is an arbitrary Hermitian matrix. Specially, the density function of LSD of S_nW_n is established, where S_n is a sample covariance matrix and W_n is Wigner matrix.     

On single and double Soules matrices

Until now the concept of a Soules basis matrix of sign patternN consisted of an orthogonal matrix R∈R^n,n, generated in a certain way from a positive n-vector, which has the property that for any diagonal matrix Λ = diag(λ₁, … , λ_n), with λ₁ ? ? ? λ_n ? 0, the symmetric matrix A = RΛR^T has nonnegative entries only. In the present paper we introduce the notion of a pair of double Soules basis matrices of sign patternN which is a pair of matrices (P, Q), each in R^n,n, which are not necessarily orthogonal and which are generated in a certain way from two positive vectors, but such that PQ^T = I and such that for any of the aforementioned diagonal matrices Λ, the matrix A = PΛQ^T (also) has nonnegative entries only. We investigate the interesting properties which such matrices A have.As a preamble to the above investigation we show that the iterates, , generated in the course of the QR-algorithm when it is applied to A = RΛR^T, where R is a Soules basis matrix of sign pattern N, are again symmetric matrices generated by the Soules basis matrices R_k of sign pattern N which are themselves modified as the algorithm progresses.Our work here extends earlier works by Soules and Elsner et al.