Additivity of nuclear norm for projections

280 Views Asked by At

Let $A,B\in \mathbb R^{m\times K}$ with $B=U\Sigma V^T$. Let $r=\operatorname{rank} B$, $(u_1,\ldots,u_m)$ be the columns of $U$, and $S_1=\operatorname{span}(u_1,\ldots,u_r)$. Similarly let $(v_1,\ldots,v_K)$ be the columns of $V$, and $S_2=\operatorname{span}(v_1,\ldots,v_r)$.
Let $P_{S_1^\perp}$ and $P_{S_2^\perp}$ be the matrices of the orthogonal projections on $S_1^\perp$ and $S_2^\perp$. Define $P=P_{S_1^\perp}AP_{S_2^\perp}$. Prove that $\|B+P\|_* = \|B\|_* + \|P\|_*$

With $U=(U_1|U_2)$ and $V=(V_1|V_2)$, $P_{S_1^\perp} = U_2U_2^T$ and $P_{S_2^\perp} = V_2V_2^T$, thus $$B+P = U_1\Sigma_1V_1^T + U_2(U_2^TAV_2 + \Sigma_2)V_2^T$$ which looks like some kind of SVD, except that $U_2^TAV_2$ has no reason to be diagonal...