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

Question

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?

[Paper reference: link]

Answer 1

While typically more useful, spectral norm low-rank approximation error is not always stronger than Frobenius norm error.

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.

If course this is quite an edge case. But this is why the linked paper uses the terminology 'intuitively stronger'. None of the three guarantees shown in that paper is strictly stronger than the others.

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