Matrix concentration inequality for unbounded (sub-exponential) matrices

Question

Let $a_1, \cdots, a_n\in\mathbb{R}^k$ be independent random vectors sampled from $N(0,\Sigma)$. We aim to establish a high probability bound on the eigenvalues $\lambda_{\min}(\sum_{i=1}^n a_ia_i^T)$ and $\lambda_{\max}(\sum_{i=1}^n a_ia_i^T)$. What are the best concentration inequalities to use?

Matrix Chernoff bound gives the bound for bounded random matrices. Is the best way here to derive a truncated variant of Matrix Chernoff bound?

Update: I find the Matrix Bernstein inequality for subexponential matrices (Theorem 6.2). Applying Remark 3.10, we can obtain a bound for the smallest eigenvalue.

Answer 1

First assume $\Sigma = \operatorname{Id}$. Write $A=((a_j)_{i})_{i \leq k, j \leq n}$, then $L_1 := AA^T$ is said to be a real Wishart matrix or $1$-Laguerre matrix. In this case some extremely sharp concentration bounds for $\lambda_{\min}(L_1)$ and $\lambda_{\max}(L_1)$ have been found by Ledoux and Rider in [Small deviations for beta ensembles, Electron. J. Probab. 15 (2010)]. See specifically Theorems 2 and 12 therein.

For general Sigma, we first may write $A = \Sigma^{\frac{1}{2}} X$, where $X$ is a $(k \times n)$-matrix of iid standard normal entries. The above bounds are applicable to $L_1 = XX^T$ and the sub-multiplicativity of the spectral norm yields \begin{align*} & \lambda_{\max}(AA^T) = ||\Sigma^{\frac{1}{2}} XX^T \Sigma^{\frac{1}{2}}|| \leq ||\Sigma^{\frac{1}{2}}||^2 \, ||X||^2 = \lambda_{\max}(\Sigma) \, \lambda_{\max}(XX^T) \end{align*} as well as \begin{align*} & \frac{1}{\lambda_{\min}(AA^T)} = ||(\Sigma^{\frac{1}{2}} XX^T \Sigma^{\frac{1}{2}})^{-1}|| = ||(\Sigma^{-\frac{1}{2}} (XX^T)^{-1} \Sigma^{-\frac{1}{2}}||\\ & \hspace{0.5cm} \leq ||\Sigma^{-\frac{1}{2}}||^2 \, ||(XX^T)^{-1}||^2 = \frac{1}{\lambda_{\min}(\Sigma)} \, \frac{1}{\lambda_{\min}(XX^T)}\\ & \Rightarrow \ \lambda_{\min}(AA^T) \geq \lambda_{\min}(\Sigma) \, \lambda_{\min}(XX^T) \ . \end{align*} We can thus use the bounds on the tail probabilities of $\lambda_{\max}(XX^T)$ to get less sharp, but still useful bounds on $\lambda_{\max}(AA^T)$. The Usefulness of the lower bound on $\lambda_{\min}(AA^T)$ depends on what you want to use it for.