Quantitative estimates of the convergence of the empirical covariance matrix in log-concave ensembles

By Radosław Adamczak, Alexander E. Litvak, Alain Pajor, Nicole Tomczak-Jaegermann. 2009

238 citations recorded by the source corpus.

Let K be an isotropic convex body in Rn. Given e > 0, how many independent points Xi uniformly distributed on K are neededfor the empirical covariance matrix to approximate the identity up to e with overwhelming probability? Our paper answers this question from [12]. More precisely, let X ∈ Rn be a centered random vector with a log-concave distribution and with the identity as covariance matrix. An example of such a vector X is a random point in an isotropic convex body. We show that for any e > 0, there existsC(e) > 0, suﰁch that if N ∼ C(e)n and (Xi)i≤N are i.i.d. copies of ﱞﱞ1 N ﱞﱞ X, then ﱞN i=1 Xi ⊗ Xi − Idﱞ ≤ e, with probability larger than 1 − exp(−c√n).

Subfields: Applied Mathematics, Geometry and Topology, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/7a2dabf307af5f23eb97dfaab00601af9a49b2dc

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Geometry and Topology

In Statistics and Probability

Citations in the corpus

How Close is the Sample Covariance Matrix to the Actual Covariance Matrix? (2010, background): “The truncation argument described in [1] in the beginning of proof of Proposition 4.”
Sample covariance matrices of heavy-tailed distributions (2016, background): “The contents of this section is to a large extent based on arguments from papers [1, 20, 10].”
Securing Distributed Gradient Descent in High Dimensional Statistical Learning (2018, unknown): “Note that standard routine to bounding the spectral norm of the sample covariance matrix is available, see [10, Theorem 5.44] and [1, Corollary 3.8] for example.”
Introduction to the non-asymptotic analysis of random matrices (2010, background): “Still, the sample size N = O(n) suffices to estimate the covariance matrix in this case [2].”
Log-Concavity and Strong Log-Concavity: a review (2014, methodology): “By analogy with the Wishart Ensemble, the Log-concave Ensemble is defined in Adamczak et al. (2010) to be the set of squared n×n matrices equipped with the distribution of AA∗, where A is a n × N matrix with i.i.d. columns that have an isotropic log-concave distribution.”
Algorithmic Regularization in Over-parameterized Matrix Sensing and Neural Networks with Quadratic Activations (2017, unknown): “…f u,v : R d → R as f u,v ( x ) = u, x v, x 1 x i ,u 2 ≤ R 2 1 x i ,v 2 ≤ R 2 . h i h i Thus by the symmetrization technique and the contraction principle(e.g., see Corollary 4.7 in [1]), we have: We have that f u,v ( x ) ≤ R 4 . where { ε i } mi =1 is a set of i.i.d. Rademacher random variables.”
Spectral norm of products of random and deterministic matrices (2008, background): “Under the assumptions of Theorem 4.1, one has for every t > 0: P ( ‖BA‖ > (C(ε) + t) √ Mn ) ≤ 4e−t2/4.”
On the Marchenko-Pastur and Circular Laws for some Classes of Random Matrices with Dependent Entries (2011, methodology): “To control the latter we will use a recent result from [3] specialized to square matrices (we would like to remark in passing that for the purpose of proving the circular law, a weaker estimate following e.”
Exact minimax risk for linear least squares, and the lower tail of sample covariance matrices (2019, background): “A series of work obtained control on these quantities under weaker assumptions [1, 50, 63, 69].”
Sharp bounds on the rate of convergence of the empirical covariance matrix (2010, methodology): “La propriété ii) résulte d’un résultat de Paouris [7] (voir [1], Lemma 3.1”
The smallest singular value of random rectangular matrices with no moment assumptions on entries (2014, background): “Simonovits, the authors of [1] treated log-concave random vectors.”
On Singular Values of Random Matrices (2015, background): “[1] Let A ba an N × n matrix whose rows Ai are independent sub-gaussian isotropic random vectors in Rn.”
Non-asymptotic theory of random matrices: extreme singular values (2010, background): “These include random symmetric matrices which were the subject of the recent survey by Ledoux [48] and random matrices with independent columns, see in particular [1, 94].”
Empirical Processes with a Bounded Ψ1 Diameter (2010, methodology): “that the indexing set is the entire sphere and that the measure is isotropic, logconcave (in particular, that Q1(μ) ∼ 1 and that the Euclidean norm of a random point concentrates around √ n). Hence, the method of [ ALPT1 ] cannot be extended”
Restricted Isometry Property of Matrices with Independent Columns and Neighborly Polytopes by Random Sampling (2009, methodology): “Assume thus that Z1, . . . , Zn are independent mean zero random variables with ‖Zi‖ψr ≤ 1.”