1
$\begingroup$

I've been reading about SVDs and have a couple questions. First, let $A\in \mathbb{R}^{n\times d}$ be a matrix with SVD $U\Sigma V^T$. Let $\sigma_i$ denote the $i$'th singular value, with corresponding right singular vector $v_i$. Is there a simple proof, using elementary linear algebra, for why the left singular vectors, $Av_i$'s, are orthogonal. Secondly, is it true that $A_k=\sum_{i=1}^kAv_iv_i^T$ is always of rank $k$, where $k\le \text{rank}(A)$?

$\endgroup$
  • $\begingroup$ Here is an animation of a low rank approximation: [Low rank approximation using the singular value decomposition][1] [1]: youtube.com/watch?v=pAiVb7gWUrM $\endgroup$ – dantopa Mar 8 '17 at 19:01
1
$\begingroup$

left singular vectors is by definition a unit vector $v_i$ such that : $$ Av_i=s_i w_i \qquad A^tw_i=s_i v_i $$ then : $$ AA^tw_i=s_i A v_i= s_i^2 w_i $$ so $s_i^2$ are the eigenvalues of the hermitian matrix $AA^t$ with corresponding eigenvectors $w_i$ so $w_i$ will be orthonormal, in fact it suffices to show that $w_i$ are orthogonal, let $s_i\neq s_j$ : $$ s_i^2\langle w_i , w_j \rangle =\langle s_i^2 w_i , w_j \rangle = \langle AA^tw_i , w_j \rangle=\langle w_i , AA^tw_j \rangle=\langle w_i ,s_j^2 ww_j \rangle=s_j^2\langle w_i , w_j \rangle $$ so $\langle w_i , w_j\rangle =0$ this implies that $$ \langle Av_i , Av_j\rangle=\langle s_i w_i , s_jw_j\rangle=s_i s_j\langle w_i , w_j\rangle=0 $$ for the second question of rank we will use some simple fact about rank, which you can see them here : $$ rank(Ab)\leq \min(rank(A),rank(B))\\ rank(A+B)\leq rank(A)+rank(B) $$ so we know that the matrix $v_iv_i^t$ is of rank one (because $(v_iv_i^t)x=\langle v_i , x \rangle v_i$ forall $x$) and then for all $i$ the matrix $Av_i v_i^t$ is of rank one (if we assume surly that $A\neq 0$), so $$ rank(A_k)=rank(\sum_{i=1}^k A v_i v_i^t ) \leq \sum_{i=1}^k rank(A v_i v_i^t)=k $$ to verify the equality we can use this question (because the answer of the question remain true for $n\times d$ matrix) and to see that $$ Ran(Av_iv_i^t)=\mathbb{R}(Av_i)\\ Ran((Av_iv_i^t)^t)=Ran(v_iv_i^t A^t )=\mathbb{R} v_i $$ (because $Ran(v_i v_i^t)=\mathbb{R} v_i $)

so for $i\neq j$ : $$ Ran(Av_iv_i^t)\cap Ran(Av_jv_j^t)= \mathbb{R}(Av_i) \cap \mathbb{R}(Av_j)=\{0\} \;\textrm{Orthogonality from the first question }\\ Ran((Av_iv_i^t)^t)\cap Ran((Av_jv_j^t)^t)=\mathbb{R} v_i \cap \mathbb{R} v_j =\{0\} \; \textrm{Orthogonality with the same argument } $$ so $Rank(A_k)=k$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.