Johnson-Lindenstrauss and the largest eigenvalue of a matrix

Question

Johnson-Lindenstrauss (JL) lemma shows that for any vector $u$ in $\mathbb{R}^d$, the vector $\frac{1}{\sqrt{k}}Ru$ satisfies $(1-\epsilon)\|u\|\leq \frac{1}{k}\|Ru\|^2\leq (1+\epsilon)\|u\|$ with probability $1-2e^{-k\epsilon^2/4}$, when $R$ is a $k\times d$ random matrix with each entry i.i.d. chosen as $\mathcal{N}(0,1)$ ($1\leq k \leq d$ is arbitrary at this point). See this note for example.

Let $A$ be a positive-semidefinite $d\times d$ matrix acting on $\mathbb{R}^d$ with largest eigenvalue $\lambda$. Let $A'= \frac{1}{k}RA R^{T}$ with the largest eigenvalue $\lambda'$. It is easy to argue from JL and union bound that the Frobenius norm satisfies $(1-\epsilon)\|A\|_2\leq \|A'\|_2\leq (1+\epsilon)\|A\|_2$ with probability $0.999$, when $k\geq \frac{6\log d}{\epsilon^2}$.

Question: Does

$(1-\epsilon)\lambda\leq \lambda' \leq (1+\epsilon)\lambda$

hold with high probability, for $k= \frac{O(\log d)}{\epsilon^2}$ or any $k$ that scales as $polylog(d)$ for a given constant $\epsilon$? In other words, does JL approximately preserve the largest eigenvalue of a matrix?

Answer 1

I had thought I used something like this in a previous paper, but on checking I only needed the vector-based version. I'm not quite sure how to get the upper bound, but I think you can get the lower bound by considering Rayleigh Quotients.

Lower bound: As $A'$ is still symmetric its maximal eigenvalue can be expressed as $$ \lambda' = \max_{v'}\frac{v'^T A' v'}{v'^Tv}. $$ Let $v$ denote the normalised maximal eigenvector of $A$ (s.t. $A\geq \lambda vv^T$), and let $v':=Rv$. Then, $$\begin{align} \lambda' &\geq \frac{v'^TA'v'}{v'^Tv}\\ &= \frac 1k \frac{v^T(R^TR)A(R^TR)v}{v^T(R^TR)v}\\ &\geq \frac 1k \frac{v^T(R^TR)(\lambda vv^T)(R^TR)v}{v^T(R^TR)v}\\ &=\lambda~\frac {v^T(R^TR)v}k\\ &\geq \lambda(1-\epsilon). \end{align}$$

I tried something similar for the upper bound, but the best I could get was $\lambda'\leq \lambda(1+\epsilon)\cdot d/k$, which doesn't seem right.

Answer 2

The answer to this question is no - thanks to Pravesh Kothari for the solution below and appreciate ideas from Clement Canonne and Christopher Chubb.

Consider two cases: 1) A is rank one, in which case $(1-\epsilon)\lambda < \lambda' < (1+\epsilon)\lambda$ holds. 2) $A= I$ (identity matrix), in which case $A' = \frac{1}{k} RR^T$. Looking at the way entries of R are chosen, the diagonal entries of A' are $\Omega(1)\cdot d/k$. Thus $\lambda=1$, whereas $\lambda' \geq \Omega(1)\cdot d/k$.