Concentration inequalities and moment bounds for sample covariance operators

By Vladimir Koltchinskii, Karim Lounici. 2014

316 citations recorded by the source corpus.

Let $X,X_1,\dots, X_n,\dots$ be i.i.d. centered Gaussian random variables in a separable Banach space $E$ with covariance operator $\Sigma:$ $$ \Sigma:E^{\ast}\mapsto E,\ \ \Sigma u = {\mathbb E}\langle X,u\rangle, u\in E^{\ast}. $$ The sample covariance operator $\hat \Sigma:E^{\ast}\mapsto E$ is defined as $$ \hat \Sigma u := n^{-1}\sum_{j=1}^n \langle X_j,u\rangle X_j, u\in E^{\ast}. $$ The goal of the paper is to obtain concentration inequalities and expectation bounds for the operator norm $\|\hat \Sigma-\Sigma\|$ of the deviation of the sample covariance operator from the true covariance operator. In particular, it is shown that $$ {\mathbb E}\|\hat \Sigma-\Sigma\|\asymp \|\Sigma\|\biggl(\sqrt{\frac{{\bf r}(\Sigma)}{n}}\bigvee \frac{{\bf r}(\Sigma)}{n}\biggr), $$ where $$ {\bf r}(\Sigma):=\frac{\Bigl({\mathbb E}\|X\|\Bigr)^2}{\|\Sigma\|}. $$ Moreover, under the assumption that ${\bf r}(\Sigma)\lesssim n,$ it is proved that, for all $t\geq 1,$ with probability at least $1-e^{-t}$ \begin{align*} \Bigl|\|\hat\Sigma - \Sigma\|-{\mathbb E}\|\hat\Sigma - \Sigma\|\Bigr| \lesssim \|\Sigma\|\biggl(\sqrt{\frac{t}{n}}\bigvee \frac{t}{n}\biggr). \end{align*}

Subfields: Applied Mathematics, Mathematical Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/3771aeebe191b3338da23a24fa2d280146a55cb3

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 Mathematical Physics

In Statistics and Probability

Citations in the corpus

Nonasymptotic upper bounds for the reconstruction error of PCA (2016, methodology): “In view of high-dimensional applications, empirical spectral pro- jectors (such as P̂6d) are often studied when the distance to the population spectral projectors is measured in operator or Hilbert-Schmidt norm, see e.g. Zwald and Blanchard [32], Nadler [25], Mas and Ruymgaart [23], and Koltchinskii”
Robust covariance estimation under $L_{4}-L_{2}$ norm equivalence (2018, background): “This is important in view of the recent results on covariance estimation in Banach spaces [2].”
Normal approximation and concentration of spectral projectors of sample covariance (2015, background): “In [14], it was proved that, in the Gaussian case, moment bounds and concentration inequalities for the operator norm ‖̂ − ‖∞ are completely characterized by the operator norm ‖ ‖∞ and the effective rank r( ).”
Exact minimax risk for linear least squares, and the lower tail of sample covariance matrices (2019, background): “It is well-known [74] that sub-Gaussian tail bounds on both the smallest and largest eigenvalues can be obtained under sub-Gaussian assumptions on covariates (see also [38] for operator norm concentration under general population covariance).”
Time-uniform, nonparametric, nonasymptotic confidence sequences (2018, methodology): “We now consider the nonasymptotic sequential estimation of a covariance matrix based on bounded vector observations (Rudelson, 1999; Vershynin, 2012; Gittens and Tropp, 2011; Tropp, 2015; Koltchinskii and Lounici, 2017).”
Structured Random Matrices (2016, methodology): “ by the present model. While the latter assumption is limiting, it allows us to obtain a complete understandingof the structural parameters that control the expected deviation EkZ −Σk in this setting [10]. Theorem 5.1 (Koltchinskii-Lounici).In the setting of this section EkZ − Σk ≍ kΣk r r(Σ) n + r(”
Uniform Hanson-Wright type concentration inequalities for unbounded entries via the entropy method (2018, methodology): “For the sake of brevity, we work with the finite-dimensional case, while as in Koltchinskii and Lounici (2017) our results will not depend explicitly on the dimension n. Recall, that a centered random vector X ∈ Rn is subgaussian if for all u ∈ Rn it holds ‖〈X,u〉‖ψ2 .”
Asymptotics and Concentration Bounds for Bilinear Forms of Spectral Projectors of Sample Covariance (2014, background): “The following theorems (see Koltchinskii and Lounici [18]) could be viewed as an extension of bound (2.”
On the spectral norm of Gaussian random matrices (2015, background): “It is evident already in the diagonal case that such bounds are dimension-free only in an ad hoc sense that fails to capture the fundamental structure of the problem (see, however, [4] for a different setting where the intrinsic dimension plays a fundamental role.”
Uniform, nonparametric, non-asymptotic confidence sequences (2018, methodology): “Here we consider a more practical problem: non-asymptotic sequential estimation of a covariance matrix based on bounded vector observations (Rudelson, 1999; Vershynin, 2012; Gittens and Tropp, 2011; Tropp, 2015; Koltchinskii and Lounici, 2017).”
Sub-Gaussian estimators of the mean of a random matrix with heavy-tailed entries (2016, background): “ rank dened as r() = tr() k k [48]; clearly, it always true that r() d. The quantity p r() k khas been shown to control the expected error of the sample covariance estimator in the Gaussian setting [29]. Under the additional assumption that the kurtosis of the linear forms hZ;vi;v6= 0 , is uniformly”
Time-uniform Chernoff bounds via nonnegative supermartingales (2018, background): “See also Vershynin (2012), Gittens and Tropp (2011), Tropp (2015), and Koltchinskii and Lounici (2017) for more recent treatments; this particular example is drawn from Wainwright (2017).”
A note on the Hanson-Wright inequality for random vectors with dependencies (2014, methodology): “4, we do not present the general setting and motivation for this type of results, referring the Reader to the original paper [15].”
Matrix concentration inequalities and free probability (2021, background): “The latter restriction is not optimal: it was shown in [23] that when X has i.”
Benign overfitting in linear regression (2019, background): “H Rank facts The quantity r0(Σ) is an important complexity parameter for covariance estimation problems, where it has been called the ‘effective rank’ [36, 27].”