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

DOI10.1090/S0894-0347-09-00650-XMaRDI QIDQ3584355zbMATH OpenWikidataFDO

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

Publication date 27 August 2010

Published in Journal of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0903.2323

zbMATH Keywords

convex bodieslog-concave measuressample covariance matricesisotropic measures

Mathematics Subject Classification ID

Random matrices (probabilistic aspects) (60B20) Inequalities; stochastic orderings (60E15) Convexity and finite-dimensional Banach spaces (including special norms, zonoids, etc.) (aspects of convex geometry) (52A21) Probabilistic methods in Banach space theory (46B09)

Abstract: Let $K$ be an isotropic convex body in $R^n$. Given $eps>0$, how many independent points $X_i$ uniformly distributed on $K$ are needed for the empirical covariance matrix to approximate the identity up to $eps$ with overwhelming probability? Our paper answers this question posed by Kannan, Lovasz and Simonovits. More precisely, let $Xin{R}^n$ 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 $eps>0$, there exists $C(eps)>0$, such that if $NsimC(eps)n$ and $(X_i{)}_{ileN}$ are i.i.d. copies of $X$, then $Big|frac1Nsu{m}_{i=1}^N{X}_{i}otimes{X}_i-IdBig|leepsilon,$ with probability larger than $1-exp(-csqrtn)$.

Recommendations

• Sharp bounds on the rate of convergence of the empirical covariance matrix
• Covariance estimation for distributions with \({2+\varepsilon}\) moments
• Estimating the covariance of random matrices
• Estimation of deviation for random covariance matrices
• How close is the sample covariance matrix to the actual covariance matrix?

Cites work

• scientific article; zbMATH DE number 49190 (Why is no real title available?)
• scientific article; zbMATH DE number 1302647 (Why is no real title available?)
• scientific article; zbMATH DE number 4113273 (Why is no real title available?)
• scientific article; zbMATH DE number 236540 (Why is no real title available?)
• Concentration around the mean for maxima of empirical processes
• Concentration of mass on convex bodies
• Concentration property on probability spaces.
• Convex set functions in \(d\)-space
• Limit of the smallest eigenvalue of a large dimensional sample covariance matrix
• Local operator theory, random matrices and Banach spaces.
• New concentration inequalities in product spaces
• On Talagrand's deviation inequalities for product measures
• On singular values of matrices with independent rows
• On the limiting empirical measure of eigenvalues of the sum of rank one matrices with log-concave distribution
• On weakly bounded empirical processes
• RANDOM POINTS IN ISOTROPIC UNCONDITIONAL CONVEX BODIES
• Random vectors in the isotropic position
• Random walks and anO*(n5) volume algorithm for convex bodies
• Reconstruction and subgaussian operators in asymptotic geometric analysis
• Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling
• Sampling convex bodies: a random matrix approach
• The Brunn-Minkowski inequality in Gauss space
• The concentration of measure phenomenon
• Weak convergence and empirical processes. With applications to statistics
• \(L_{p}\)-moments of random vectors via majorizing measures

Cited in

(74)

• On the approximation accuracy of Gaussian variational inference
• An efficiency upper bound for inverse covariance estimation
• Dimension-free bounds for sums of independent matrices and simple tensors via the variational principle
• Phase transitions for support recovery under local differential privacy
• Side effects of learning from low-dimensional data embedded in a Euclidean space
• Random polytopes generated by contoured distributions
• A practical algorithm for volume estimation based on billiard trajectories and simulated annealing
• Pairwise sparse + low-rank models for variables of mixed type
• Dimension-free bounds for sums of dependent matrices and operators with heavy-tailed distributions
• Asymptotic geometric analysis: achievements and perspective
• Optimal modeling of nonlinear systems: method of variable injections
• Covariance estimation under missing observations and \(L_4 - L_2\) moment equivalence
• Minimizing convex functions with rational minimizers
• Fast random vector transforms in terms of pseudo-inverse within the Wiener filtering paradigm
• Restricted isometry property for random matrices with heavy-tailed columns
• On a multi-integral norm defined by weighted sums of log-concave random vectors
• Empirical approximation of the Gaussian distribution in \(\mathbb{R}^d\)
• Covariance estimation for distributions with \({2+\varepsilon}\) moments
• Non-asymptotic results for singular values of Gaussian matrix products
• Worst-case convergence analysis of inexact gradient and Newton methods through semidefinite programming performance estimation
• On the isotropic constant of random polytopes
• Asymptotic shape of a random polytope in a convex body
• Random embeddings with an almost Gaussian distortion
• Random matrices, geometric functional analysis and algorithms. Abstracts from the workshop held May 1--7, 2011.
• Coverings of random ellipsoids, and invertibility of matrices with i.i.d. heavy-tailed entries
• Sharp bounds on the rate of convergence of the empirical covariance matrix
• Limiting spectral distribution for a type of sample covariance matrices
• The lower tail of random quadratic forms with applications to ordinary least squares
• Gaussian and robust Kronecker product covariance estimation: existence and uniqueness
• Marcinkiewicz-type discretization of \(L^p\)-norms under the Nikolskii-type inequality assumption
• The smallest singular value of a shifted $d$-regular random square matrix
• Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling
• On the interval of fluctuation of the singular values of random matrices
• Beyond covariance: SICE and kernel based visual feature representation
• Quantitative Version of a Silverstein’s Result
• Rank-one multi-reference factor analysis
• On the convergence of the extremal eigenvalues of empirical covariance matrices with dependence
• On the geometry of polytopes generated by heavy-tailed random vectors
• Quermaßintegrals and asymptotic shape of random polytopes in an isotropic convex body
• An isomorphic Dvoretzky-Milman theorem using general random ensembles
• Non-asymptotic properties of spectral decomposition of large Gram-type matrices and applications
• On generic chaining and the smallest singular value of random matrices with heavy tails
• Spectral norm of products of random and deterministic matrices
• Bayesian inference for spectral projectors of the covariance matrix
• Geometry of log-concave ensembles of random matrices and approximate reconstruction
• Exact minimax risk for linear least squares, and the lower tail of sample covariance matrices
• Approximating the covariance ellipsoid
• Concentration phenomena in high dimensional geometry
• Convergence of the largest eigenvalue of normalized sample covariance matrices when \(p\) and \(n\) both tend to infinity with their ratio converging to zero
• Sampling convex bodies: a random matrix approach
• Estimating the covariance of random matrices
• Asymptotic shape of the convex hull of isotropic log-concave random vectors
• Row products of random matrices
• An upper bound on the smallest singular value of a square random matrix
• Approximating the moments of marginals of high-dimensional distributions
• Sampling discretization and related problems
• Condition number of a square matrix with i.i.d. columns drawn from a convex body
• Empirical processes with a bounded \(\psi_1\) diameter
• Small-ball probabilities for the volume of random convex sets
• The smallest singular value of random rectangular matrices with no moment assumptions on entries
• Random tensor theory: Extending random matrix theory to mixtures of random product states
• How close is the sample covariance matrix to the actual covariance matrix?
• On Monte-Carlo methods in convex stochastic optimization
• The limit of the smallest singular value of random matrices with i.i.d. entries
• On higher order isotropy conditions and lower bounds for sparse quadratic forms
• Folded concave penalized sparse linear regression: sparsity, statistical performance, and algorithmic theory for local solutions
• Covariance estimation under one-bit quantization
• Log-concavity and strong log-concavity: a review
• Variable metric random pursuit
• Phase retrieval: stability and recovery guarantees
• Almost sure convergence of the largest and smallest eigenvalues of high-dimensional sample correlation matrices
• High-dimensional nonparametric density estimation via symmetry and shape constraints
• A practical volume algorithm
• Estimating covariance and precision matrices along subspaces

This page was built for publication: Quantitative estimates of the convergence of the empirical covariance matrix in log-concave ensembles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3584355)