3
$\begingroup$

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<p$, 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?

$\endgroup$
2
  • $\begingroup$ 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). $\endgroup$
    – angryavian
    Apr 25, 2021 at 22:12
  • $\begingroup$ 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.. $\endgroup$
    – Hermi
    Apr 25, 2021 at 22:26

1 Answer 1

0
$\begingroup$

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

$\endgroup$
10
  • $\begingroup$ 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? $\endgroup$
    – Hermi
    Apr 26, 2021 at 16:43
  • $\begingroup$ @hermione-granger Sorry, $u_i$ are the columns of $U$ in the SVD $A=U\Sigma V^\top$. $\endgroup$
    – angryavian
    Apr 26, 2021 at 16:45
  • $\begingroup$ 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? $\endgroup$
    – Hermi
    Apr 26, 2021 at 16:56
  • $\begingroup$ @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$. $\endgroup$
    – angryavian
    Apr 26, 2021 at 17:02
  • $\begingroup$ 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? :) $\endgroup$
    – Hermi
    Apr 26, 2021 at 17:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .