I'm trying to understand the low rank approximation matrices using SVD and Frobenius norm, and one line I keep encountering and cannot understand is the following :
$$\operatorname{Tr}((A-M)^*(A-M)) = \sum_1^n (v_j^*(A-M)^*(A-M)v_j) = \sum_{k+1}^{\operatorname{rank}(A)} s^2$$
where $\bigl\{v_j\bigr\}$ is the orthonormal basis of V of the classic $A=USV^*$ decomposition.
M is also presented by a SVD decomposition but it is truncated at some rank $k< \operatorname{rank}(A)$.
I understand that the trace is invariant under change of basis (which is what I am assuming is happening here).
I also understand that such a change is good to get rid of the V terms in the SVD decomposition of the outcome.
But when I expand $A-M$ and it is basically a summation conjugate multiplied by another summation conjugate between $v_j^*$ and $v_j$, I don't understand how to make the leap.
A little clarification : the * is for the conjugate
Best Answer
$\DeclareMathOperator{\tr}{tr}$ First note that $\tr(A^*B) =\langle A, B\rangle_F$, i.e. the trace of $A^*B$ is equal to the Frobenius inner product of the two matrices. Now let $A=U S V^*$ and $M = US_kV^*$ where $S$ is the diagonal matrix containing the singular values $\sigma_i$ and $S_k$ is the same with $\sigma_i$ replaced by $0$ for $i>k$. The important fact to remember now is that the $2$-norm (and $F$ norm) is invariant w.r.t. Orthogonal tranformations, i.e.
$$ \|A-M\|_F^2 = \|USV^* - US_k V^*\|_F^2 = \|U(S-S_k)V^*\|_F^2 = \|S-S_k\|_F^2 = \smash{\sum_{i=k+1}^n \sigma_i^2}$$
This can also be seen via the cyclic property of the trace:
$$\begin{aligned} \tr((A-M)^*(A-M) &= \tr\bigl( (USV^* - US_k V^*)^*(USV^* - US_k V^*)\bigr) \\ &=\tr\bigl( (U(S - S_k) V^*)^*(U(S-S_k) V^*)\bigr) \\ &=\tr\bigl( V (S-S_k) U^*U(S-S_k)V^*\bigr) \\ &=\tr\bigl( (S-S_k)^2V^*V\bigr) = \tr\bigl((S-S_k)^2\bigr) = \smash{\sum_{i=k+1}^n} \sigma_i^2\\ \end{aligned}$$