# Singular Value Decomposition Theorem: Corollary

In a linear algebra and analysis course [it's a hybrid course between the two], we recently had the SVD (singular value decomposition) theorem, and the prof. told us (due to lack of time without proof):

Corollary 2.39: Let $$A = U\Sigma V^{T}$$ be the singular value decomposition of $$A\in \mathbb R^{m\times n}$$, where the singular values $$\sigma_1 \geq \dots \geq \sigma_p \geq 0$$, where $$p = \min\left\{ m, n\right\}$$. Further, for $$k, define

$$A_{k} = U\Sigma_{k}V^{T},$$

where $$\Sigma_{k} = \begin{pmatrix} \sigma_1 \qquad\qquad\qquad 0 \\ \qquad \ddots \qquad \\ \quad\quad\quad\sigma_{k} \\ 0 \qquad\qquad\qquad 0 \end{pmatrix} \in \mathbb R^{m\times n},$$

with $$k < p$$. It holds that: $$A_k = \arg\min_{\text{rank}\left( B \right) = k}\left|\left| A - B\right|\right|_{2} = \arg\min_{\text{rank}\left( B\right) = k}\left|\left| A - B\right|\right|_{F}.$$

Upon question on a hint of the proof the lecturer said that one might want to use the following relations: $$\text{Tr}\left( AB^{T} \right) \leq \sum_{j=1}^{p} \sigma_{j}\gamma_{j},$$ where $$\gamma_{1} \geq \dots \geq \gamma_{p} \geq 0$$ denote the singular values of $$B\in\mathbb R^{m\times n}$$. I also proved the following two relations:

$$\left|\left| A - A_{k} \right|\right|_{2} = \sigma_{k+1}, \qquad \left|\left| A - A_{k} \right|\right|_{F} = \left( \sum_{j = k+1}^{p} \sigma_{j}^{2} \right)^{1/2} \qquad$$

IDEA: I tried several things, one of them being: $$\left|\left| A - B\right|\right|_{2} \leq \left|\left| A - A_{k} \right|\right|_{2} + \left|\left| B - A_{k} \right|\right|_{2} = \sigma_{k+1} + \left|\left| B - A_{k} \right|\right|_{2}$$

But then, I am not sure how to continue. We already know from the Corollary that $$A_k = U\Sigma_k V^{T}$$ [by definition], and $$B = \tilde{U}\tilde{\Sigma}\tilde{V^{T}}$$ [by the SVD Theorem], i.e. $$\left|\left| B - A_{k} \right|\right|_{2} = \left|\left| \tilde{U}\tilde{\Sigma}\tilde{V^{T}} - U\Sigma_k V^{T}\right|\right|_{2}$$.

Could anybody help out, please, on how to continue?

• In the statement of the corollary, shouldn't the two argmins have different values? The first should be $\sigma_{k+1}$ (as you showed) and the second should be as is. And your $\|A-A_k\|_F$ ought to match the quantity in the corollary (you have $\sigma_j$ instead of $\sigma_j^2$ inside the some for some reason). Apr 25, 2021 at 22:12
• Thanks for the careful reading, you're right! Please feel free to add a quick answer or a short comment, I'm really curious why this corollary holds.. Apr 25, 2021 at 22:26

Operator norm:

You've shown $$\|A-A_k\|_2 = \sigma_{k+1}$$, so it remains to show that $$\|A-B\|_2 \ge \sigma_{k+1}$$ for any rank $$k$$ matrix $$B$$.

• Suppose $$B$$ has rank $$k$$. The nullspace of $$B$$ has dimension $$n-k$$.
• Let $$v_1, \ldots, v_{k+1}$$ be the top singular vectors of $$A$$ (i.e. $$Av_i = \sigma_i u_i$$). The span of these vectors has dimension $$k+1$$.
• Since the above two subspaces have dimensions $$n-k$$ and $$k+1$$ summing to more than $$n$$, its intersection is nonempty. Let $$z$$ be a unit vector in both these subspaces.
• Show that $$\|A-B\|_2^2 \ge \|(A-B)z\|_2^2 = \|Az\|_2^2 \ge \sigma_{k+1}^2.$$ (The first inequality is due to the definition of the operator norm. The second equality is due to $$z \in \ker B$$. The third inequality can be shown by writing $$z$$ as a linear combination of $$v_1, \ldots, v_{k+1}$$ and noting that these vectors map to $$\sigma_i u_i$$ for $$i \ge k+1$$.)

Frobenius norm:

You've shown $$\|A-A_k\|_F^2 = \sum_{j=k+1}^p \sigma_j^2$$ (note that you still have a typo), so it remains to show that $$\|A-B\|_F^2 \ge \sum_{j=k+1}^p \sigma_j^2$$ for any rank $$k$$ matrix $$B$$.

For a matrix $$M$$ I will use $$\sigma_i(M)$$ to denote the $$i$$th singular value of $$M$$, and let $$M_k$$ denote the result of keeping only the top $$k$$ singular values (just as you have defined $$A_k$$).

Using the result $$\|M - M_k\| = \sigma_{k+1}$$ that you proved, \begin{align} \sigma_i(A-B) &= \|(A-B) - (A-B)_{i-1}\|_2 \\ &= \|A - (B + (A-B)_{i-1})\|_2 \\ &\ge \|A - A_{k+i-1}\|_2 \\ &= \sigma_{k+i}(A). \end{align} The inequality is due to $$\text{rank}(B + (A-B)_{i-1}) \le \text{rank}(B) + \text{rank}((A-B)_{i-1}) = k+i-1$$, combined with the above result that $$A_{k+i-1}$$ is the best rank $$k+i-1$$ approximation of $$A$$ in the operator norm.

Using the fact that the squared Frobenius norm is the sum of squares of its singular values, we have $$\|A-B\|_F^2 = \sum_{i=1}^{\min(m,n)} (\sigma_i(A-B))^2 \ge\sum_{j=k+1}^p (\sigma_j(A))^2.$$

• I would have two immediate follow-up questions on this: (i) What are the $u_{i}$? (ii) Why does $Av_{i} = \sigma_{i} u_{i}$ hold? Apr 26, 2021 at 16:43
• @hermione-granger Sorry, $u_i$ are the columns of $U$ in the SVD $A=U\Sigma V^\top$. Apr 26, 2021 at 16:45
• No problem! But could you please explain then why $Av_{i} = U\Sigma V^{T} v_{i} \overset{!}{=} \sigma_{i}u_{i}$ hold? For example, we don't even know how to evaluate $V^{T}v_{i}$, do we? Apr 26, 2021 at 16:56
• @hermione-granger $v_i$ is the $i$th column of $V$, so $V^\top v_i$ is the $i$th standard basis vector (all zeros except for a $1$ in the $i$th component) because the columns of $V$ are orthonormal. This is an important characterization of the right- and left-singular vectors and singular values of $A$. Apr 26, 2021 at 17:02
• Okay, just to make sure: You mean that in general, the singular values of $A$ are just the columns of $V^{T}$ with our chosen notation? We probably had that, then, but I couldn't find it in my notes, probably overlooked it.. Could you please send a link for a proof or so? :) Apr 26, 2021 at 17:34