Let $k$ and $d$ be positive integers such that $d/k:=\lambda > 1$. Let $W$ be $k \times d$ random matrix with rows $w_1,\ldots,w_k \in \mathbb R^d$ drawn iid from $N(0,(1/d)I_d)$, and define the $k \times k$ matrix $C(W)$ by setting $C(W)_{i,j} := 2(w_i^\top w_j)^2 + \|w_i\|^2\|w_j\|^2$.

Question. Is there a high-probability good lower-bound for the smallest eigenvalue of $C(W)$ ?

N.B. I'm familiar with standard RMT.


1 Answer 1


We have $$ C(W) = 2 A \circ A + v v^\top$$ where $v$ is the vector with entries $\|w_i\|^2$, $A$ is the Wishart matrix with entries $w_i^\top w_j$, and $\circ$ is the Hadamard product. From the Schur product theorem (and the fact that adding a positive semi-definite matrix to a self-adjoint matrix only serves to increase the least eigenvalue $\lambda_1$) we conclude that $$ \lambda_1(C(W)) \geq 2 \lambda_1(A)^2.$$ Combining this with the Marchenko-Pastur law one gets an almost sure lower bound of $2 (1 - 1/\sqrt{\lambda})^4 - o(1)$ (if I have not made a sign error). However, the application of the Schur product theorem may be inefficient and one could hope to improve this lower bound slightly.

Note from the Weyl inequalities that $$ 2\lambda_1(A \circ A) \leq \lambda_1(C(W)) \leq 2 \lambda_2(A \circ A) $$ so the problem really boils down to understanding the spectral behavior of the Hadamard square $A \circ A$ of a Wishart matrix $A$.

  • $\begingroup$ Great. Thanks for the detailed answer. $\endgroup$
    – dohmatob
    Jan 30, 2021 at 23:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.