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

DOI10.1090/S0894-0347-09-00650-XzbMATH Open1206.60006arXiv0903.2323WikidataQ105583999 ScholiaQ105583999MaRDI QIDQ3584355FDOQ3584355

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)

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)$.

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

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?

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)

Cites Work

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

Cited In (74)

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

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)