How to show that the low rank SVD preserves the $2$-norm?

1.1k Views Asked by At

Say we have a nonnegative $n \times m$ matrix $\mathbf{A}$, and we compute a $k$-rank SVD (singular value decomposition) so that $\mathbf{A} = \mathbf{U}\mathbf{\Sigma}\mathbf{V}^\top$. Then, $\mathbf{U}$ is $n \times k$, $\mathbf{\Sigma}$ is $k \times k$ and $\mathbf{V}^\top$ is $k \times m$.

We can then write the $k$-dimensional projection of $\mathbf{A}$ as $\mathbf{A}_{proj} = \mathbf{U}\mathbf{\Sigma}$.

How can we show that the $2$-norm of the $i$th row vector in $\mathbf{A}_{proj}$ is bounded by the $2$-norm of the corresponding $i$th row vector in $\mathbf{A}$? That is, can we show the following?

$$\|\mathbf{A}_{{proj}_i}\|_2 \leq \|\mathbf{A}_i\|_2$$

I am able to see these results empirically, but am unsure how to go about proving it. Thanks in advance for any help!

2

There are 2 best solutions below

0
On

I wanted to chime in with a thought on my own question -- maybe someone can help (bolster, or tear down) my line of reasoning.

We know that the $l_2$ norm is preserved for the full rank decomposition: i.e. when $k = rank(\mathbf{A})$, as $\mathbf{A}_{proj}$ will necessarily have the same row norm as $\mathbf{A}$ since $\mathbf{V^T}$ is orthonormal and multiplication by an orthornormal matrix preserves $l_2$ norm.

I am now seeing that the $(k+1)$-rank decomposition's row norms will be strictly greater than or equal to the $k$-rank decomposition's row norms, since the $k$-rank $\mathbf{A}_{proj}$ will be the first $k$ columns of the ($k+1$)-rank $\mathbf{A}_{proj}$. Any nonzero projection in the $i$th row of the $(k+1)^{th}$ column vector in $\mathbf{U}\mathbf{\Sigma}$ will result in a strict increase in that row's $l_2$ norm. A zero projection in that row will result in no change in the row's $l_2$ norm.

I think this is sufficient to show that $||\mathbf{A}_{{proj}_i}||_2 \leq ||\mathbf{A}_i||_2$.

0
On

Let $w_i$ be the $i$th row of $A_{proj}$ and let $z_i$ be the $i$th row of $A$. Then $z_i = w_iV^T$. Now use $V^TV = I$ to compute $$ \|w_i\|^2 = w_iV^TVw_i^T = z_i^Tz_i = \|z_i\|^2 \, . $$