2

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!

Rodrigo de Azevedo
  • 1
svdummy
  • 21
  • If I don't recall this wrong $\bf U$ and $\bf V$ are defined to be unitary. Could maybe help. – mathreadler Sep 29 '16 at 19:40
  • you answered yourself 6 minutes after posting the question? anyway, here's a link you may find useful: http://math.stackexchange.com/questions/759032/proof-of-eckart-young-mirsky-theorem – tibL Oct 03 '16 at 11:49

2 Answers2

1

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

Hans Engler
  • 15,439
0

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

svdummy
  • 3