# Johnson-Lindenstrauss and the largest eigenvalue of a matrix

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?

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.

• Thanks! Your bound is basically saturated, as in the answer below. Feb 19, 2023 at 1:04

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$$.