Concentration inequality for minimal eigenvalue of sample covariance

Question

I was reading an article of matrix completion and met the following lemma The concentration inequality for $\sigma_{\max}$ part is a standard result. However, I didn't find any results like the $\sigma_{\min}$ part. The most similar expression was found in Theorem 6.1 of Wainwright's book as follows \begin{equation} P\left[\frac{\sigma_{\min}(X)}{\sqrt{n}}\leq\sigma_{\min}(\sqrt{\Sigma})(1-\delta)-\sqrt{\frac{\operatorname{tr}(\Sigma)}{n}}\right]\leq \exp\{-n\delta^2/2\} \end{equation} but it cannot be directly relaxed to the form like \begin{equation} \sigma_{\min}\left(\frac{1}{n}X^TX\right)\geq c\sigma_{\min}(\Sigma) \end{equation} Since it involves a trace term. Moreover, the author refer its proof from another paper. But seems there are no explicit statement in it.

So my question is, how to prove that result? And can we obtain similar result for subgaussian random vectors?

Answer 1

A variant of this result has been proved in https://arxiv.org/pdf/1106.2775.pdf (under a regularity assumption that is weaker than sub-Gaussian).

Answer 2

The usual lower bound (e.g., Theorem II.13 in Davidson and Szarek ("Banach space theory and local operator theory") says that if $A\in R^{n\times d}$ has iid $N(0,1)$ entries then $$ P(\sigma_{\min}(A^TA)^{1/2} \ge \sqrt n - \sqrt d - t) \ge 1- e^{-t^2/2}. $$

You may assume $\sigma_{\min}(\Sigma)>0$ (that is, $\Sigma$ invertible), otherwise there is nothing prove. Now let $A=X\Sigma^{-1/2}$ so that $A$ has iid $N(0,1)$ entries as above. Then $$\sigma_{\min}(X^TX)=\sigma_{\min}(\Sigma^{1/2}A^TA\Sigma^{1/2}) \ge \sigma_{\min}(\Sigma) \sigma_{\min}(A^TA). $$ This is because, if the vector $u$ with $\|u\|=1$ is such that $\|Au\|^2=\sigma_{\min}(A^TA)$, then $\|Au\|^2=\|X\Sigma^{-1/2}u\|^2\le\sigma_{\min}(X^TX)\|\Sigma^{-1/2}u\|^2$ and $\|\Sigma^{-1/2}u\|^2\le \|\Sigma^{-1}\|_{operator}=\sigma_{\min}(\Sigma)^{-1}$.

Applying the concentration inequality for $\sigma_{\min}(A^TA)$ gives the desired bound.