# Why spectral norm low-rank approximation error is stronger than frobenius norm?

Suppose a rank $k$ matrix $Z$ with orthonormal columns $z_1,..., z_k$ satisfies Frobenius Norm Error: $$\|A − ZZ^TA_k\|_F ≤ (1 + \epsilon)\|A − A_k\|_F -- (1)$$ It is said that Frobenius norm error is often hopelessly insufficient, especially for data analysis and learning applications. When A has a “heavy-tail” of singular values, which is common for noisy data, $\|A − A_k\|^2_F = \sum_{i>k}{ \sigma_i^2}$ can be huge, potentially much larger than A’s top singular value. This renders (1) meaningless since $Z$ does not need to align with any large singular vectors to obtain good multiplicative error.

So, couple of papers suggested targeting spectral norm low-rank approximation error, Spectral Norm Error: $$\|A − ZZ^T A_k\|_2 \le (1 + \epsilon)\|A − A_k\|_2-- (2)$$ which is intuitively stronger. When looking for a rank $k$ approximation, $A$’s top k singular vectors are often considered data and the remaining tail is considered noise. A spectral norm guarantee roughly ensures that $ZZ^T A$ recovers $A$ up to this noise threshold.

Is spectral norm low-rank approximation error always stronger than frobenius norm? Is there any proof to its claim?

Consider setting $A$ to be a $k+1 \times k+1$ identity matrix. Then $\|A-A_k\|_2 = \|A-A_k\|_F = 1$. Even setting $Z = 0$, would give $\|A-ZZ^T A\|_2 = \|A\|_2 = 1 = \|A-A_k\|_2$. But it would give $\|A-ZZ^TA\|_F = \|A\|_F = \sqrt{k+1} = \sqrt{k+1} \|A-A_k\|_F$. So $Z$ here gives an optimal spectral norm low-rank approximation, but a quite bad Frobenius norm one.
Note that $Z = 0$ is not technically orthonormal, but the counterexample still holds if we pad $A$ with $k$ all zero rows and set $Z$ to be any $2k+1 \times k$ orthonormal span with entries only in its last $k$ rows.
One way to see why Frobenius norm error is typically weak is to imagine a rank-$k$ matrix $M \in \mathbb{R}^{n \times n}$, with all singular values equal to $1$. If we then add a rank-$n$ noise matrix $N \in \mathbb{R}^{n \times n}$ with all singular values equal to $1/\sqrt{n}$ and set $A = M + N$, we have by triangle inequality $\| A\|_F \le \|N \|_F + \| M\|_F \le \sqrt{n} + \sqrt{k}$. We have additionally have $\| A - A_k \|_F \ge \| N - N_k \|_F - \| M \|_F \ge \sqrt{n-k} - \sqrt{k} \ge \sqrt{n}-2\sqrt{k}$. So if we set $Z = 0$, we have $\| A - ZZ^T \|_F = \|A\|_F \le \frac{\sqrt{n} + \sqrt{k}}{\sqrt{n}-2\sqrt{k}} \| A - A_k \|_F \approx \| A - A_k \|_F$ when $n >> k$ as is typically the case. So here the Frobenius norm metric is not very informative -- even $Z = 0$ gives near optimal Frobenius norm error!
At the same time, we have $\|A \|_2 \ge \| M \|_2 - \| N \|_2 \ge 1- 1/\sqrt{n}$ and $\|A -A_k \|_2 \le \| M-M_k \|_2 + \|N\|_2 \le 1/\sqrt{n}$. So $A$ has a very good spectral norm low-rank approximation, which corresponds to identifying the underlying rank-$k$ matrix $M$.