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 bodiesisotropic measureslog-concave measuressample covariance matrices

Mathematics Subject Classification ID

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

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

• \(L_{p}\)-moments of random vectors via majorizing measures
• 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
• 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?)
• 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 singular values of matrices with independent rows
• On Talagrand's deviation inequalities for product measures
• 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

Cited in

(90)

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

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)