<p>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.</p>
<p><strong>Lower bound:</strong>
As <span class="math-container">$A'$</span> is still symmetric its maximal eigenvalue can be expressed as
<span class="math-container">$$ \lambda' = \max_{v'}\frac{v'^T A' v'}{v'^Tv}. $$</span>
Let <span class="math-container">$v$</span> denote the normalised maximal eigenvector of <span class="math-container">$A$</span> (s.t. <span class="math-container">$A\geq \lambda vv^T$</span>), and let <span class="math-container">$v':=Rv$</span>. Then,
<span class="math-container">$$\begin{align}
\lambda'
&amp;\geq \frac{v'^TA'v'}{v'^Tv}\\
&amp;= \frac 1k \frac{v^T(R^TR)A(R^TR)v}{v^T(R^TR)v}\\
&amp;\geq \frac 1k \frac{v^T(R^TR)(\lambda vv^T)(R^TR)v}{v^T(R^TR)v}\\
&amp;=\lambda~\frac {v^T(R^TR)v}k\\
&amp;\geq \lambda(1-\epsilon). 
\end{align}$$</span></p>
<p>I tried something similar for the upper bound, but the best I could get was <span class="math-container">$\lambda'\leq \lambda(1+\epsilon)\cdot d/k$</span>, which doesn't seem right.</p>

CC BY-SA 4.0
2023-02-19T01:04:26.937Z
Thanks! Your bound is basically saturated, as in the answer below.
anurag anshu
CC BY-SA 4.0
2023-02-18T23:10:43.747Z
2023-02-18T23:10:43.747Z
Christopher T. Chubb
<p>The answer to this question is no - thanks to Pravesh Kothari for the solution below and appreciate ideas from Clement Canonne and Christopher Chubb.</p>
<p>Consider two cases: 1) A is rank one, in which case <span class="math-container">$(1-\epsilon)\lambda &lt; \lambda' &lt; (1+\epsilon)\lambda$</span> holds. 2) <span class="math-container">$A= I$</span> (identity matrix), in which case <span class="math-container">$A' = \frac{1}{k} RR^T$</span>. Looking at the way entries of R are chosen, the diagonal entries of A' are <span class="math-container">$\Omega(1)\cdot d/k$</span>. Thus <span class="math-container">$\lambda=1$</span>, whereas <span class="math-container">$\lambda' \geq \Omega(1)\cdot d/k$</span>.</p>

CC BY-SA 4.0
2023-02-19T01:03:44.540Z
2023-02-19T01:03:44.540Z
anurag anshu
<p>Johnson-Lindenstrauss (JL) lemma shows that for any vector <span class="math-container">$u$</span> in <span class="math-container">$\mathbb{R}^d$</span>, the vector <span class="math-container">$\frac{1}{\sqrt{k}}Ru$</span> satisfies <span class="math-container">$(1-\epsilon)\|u\|\leq \frac{1}{k}\|Ru\|^2\leq (1+\epsilon)\|u\|$</span> with probability <span class="math-container">$1-2e^{-k\epsilon^2/4}$</span>, when <span class="math-container">$R$</span> is a <span class="math-container">$k\times d$</span> random matrix with each entry i.i.d. chosen as <span class="math-container">$\mathcal{N}(0,1)$</span> (<span class="math-container">$1\leq k \leq d$</span> is arbitrary at this point). See <a href="http://cs-www.cs.yale.edu/homes/el327/papers/RandomProjectionsSeminar.pdf" rel="nofollow noreferrer">this note</a> for example.</p>
<p>Let <span class="math-container">$A$</span> be a positive-semidefinite <span class="math-container">$d\times d$</span> matrix acting on <span class="math-container">$\mathbb{R}^d$</span> with largest eigenvalue <span class="math-container">$\lambda$</span>. Let <span class="math-container">$A'= \frac{1}{k}RA R^{T}$</span> with the largest eigenvalue <span class="math-container">$\lambda'$</span>. It is easy to argue from JL and union bound that the Frobenius norm satisfies <span class="math-container">$(1-\epsilon)\|A\|_2\leq \|A'\|_2\leq (1+\epsilon)\|A\|_2$</span> with probability <span class="math-container">$0.999$</span>, when <span class="math-container">$k\geq \frac{6\log d}{\epsilon^2}$</span>.</p>
<p><strong>Question:</strong> Does</p>
<p><span class="math-container">$(1-\epsilon)\lambda\leq \lambda' \leq (1+\epsilon)\lambda$</span></p>
<p>hold with high probability, for <span class="math-container">$k= \frac{O(\log d)}{\epsilon^2}$</span> or any <span class="math-container">$k$</span> that scales as <span class="math-container">$polylog(d)$</span> for a given constant <span class="math-container">$\epsilon$</span>? In other words, does JL approximately preserve the largest eigenvalue of a matrix?</p>

<linear-algebra><matrices>
Johnson-Lindenstrauss and the largest eigenvalue of a matrix
anurag anshu
# Johnson-Lindenstrauss and the largest eigenvalue of a matrix

(Asked by: username_0 on 2023-02-18)

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](http://cs-www.cs.yale.edu/homes/el327/papers/RandomProjectionsSeminar.pdf) 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?

**Tags:** linear-algebra, matrices

---

## 2 answers

### Answer by username_1 on 2023-02-18. Score: 3

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.

> **Comments:**
> **username_0**: Thanks! Your bound is basically saturated, as in the answer below.  

---

### Answer by username_0 on 2023-02-19. Score: 3

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


---

