3
$\begingroup$

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?

$\endgroup$

2 Answers 2

3
$\begingroup$

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.

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

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

$\endgroup$

Your Answer

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

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