低秩矩阵近似求解

优化问题：

Z ^ = arg ⁡ min ⁡ ∥ Z − X ∥ F 2  s.t.  rank ⁡ ( Z ) ⩽ N , Z ∈ R M × L \begin{aligned} \widehat{\mathbf{Z}}=\arg \min &\|\mathbf{Z}-\mathbf{X}\|_{\mathrm{F}}^{2} \\ \text { s.t. } & \operatorname{rank}(\mathbf{Z}) \leqslant N, \mathbf{Z} \in \mathbb{R}^{M \times L} \end{aligned} Z =argmin s.t. ​∥Z−X∥F2​rank(Z)⩽N,Z∈RM×L​

该限制条件可以改写为: Z = C Y ∈ R M × L , C T C = I N , C ∈ R M × N , Y ∈ R N × L \mathbf{Z}=\mathbf{C Y} \in \mathbb{R}^{M \times L}, \mathbf{C}^{\mathrm{T}} \mathbf{C}=\mathbf{I}_{N}, \mathbf{C} \in \mathbb{R}^{M \times N}, \mathbf{Y} \in \mathbb{R}^{N \times L} Z=CY∈RM×L,CTC=IN​,C∈RM×N,Y∈RN×L

因此，优化问题等价为： ( C ^ , Y ^ ) = arg ⁡ min ⁡ C T C = I N { min ⁡ Y ∈ R N × L ∥ C Y − X ∥ F 2 } = arg ⁡ min ⁡ C T C = I N { min ⁡ Y ∈ R N × L Tr ⁡ ( Y T Y − 2 Y T C T X + X T X ) } ⇒ { C ^ = arg ⁡ min ⁡ C T C = I N Tr ⁡ ( [ I M − C C T ] X X T ) Y ^ = C ^ T X \begin{aligned} (\widehat{\mathbf{C}}, \widehat{\mathbf{Y}}) &=\arg \min _{\mathbf{C}^{\mathrm{T}} \mathbf{C}=\mathbf{I}_{N}}\left\{\min _{\mathbf{Y} \in \mathbb{R}^{N \times L}}\|\mathbf{C Y}-\mathbf{X}\|_{\mathrm{F}}^{2}\right\} \\ &=\arg \min _{\mathbf{C}^{\mathrm{T}} \mathbf{C}=\mathbf{I}_{N}}\left\{\min _{\mathbf{Y} \in \mathbb{R}^{N \times L}} \operatorname{Tr}\left(\mathbf{Y}^{\mathrm{T}} \mathbf{Y}-2 \mathbf{Y}^{\mathrm{T}} \mathbf{C}^{\mathrm{T}} \mathbf{X}+\mathbf{X}^{\mathrm{T}} \mathbf{X}\right)\right\} \\ \Rightarrow &\left\{\begin{array}{l} \widehat{\mathbf{C}}=\arg \min _{\mathbf{C}^{\mathrm{T}} \mathbf{C}=\mathbf{I}_{N}} \operatorname{Tr}\left(\left[\mathbf{I}_{M}-\mathbf{C C}^{\mathrm{T}}\right] \mathbf{X} \mathbf{X}^{\mathrm{T}}\right) \\ \widehat{\mathbf{Y}}=\widehat{\mathbf{C}}^{\mathrm{T}} \mathbf{X} \end{array}\right. \end{aligned} (C ,Y )⇒​=argCTC=IN​min​{Y∈RN×Lmin​∥CY−X∥F2​}=argCTC=IN​min​{Y∈RN×Lmin​Tr(YTY−2YTCTX+XTX)}{C =argminCTC=IN​​Tr([IM​−CCT]XXT)Y =C TX​​ 注意到： Tr ⁡ ( [ I M − C C T ] X X T ) = T r ( X X T ) − t r ( C T X X T C ) \operatorname{Tr}\left(\left[\mathbf{I}_{M}-\mathbf{C C}^{\mathrm{T}}\right] \mathbf{X} \mathbf{X}^{\mathrm{T}}\right)=\mathrm{Tr}(\mathbf{XX}^T)-\mathrm{tr}(\mathbf{C^TXX^TC}) Tr([IM​−CCT]XXT)=Tr(XXT)−tr(CTXXTC) 因此，当且仅当 C T \mathbf{C}^T CT为 X X T \mathbf{XX}^T XXT的最大N列向量时，取到最值。因此： Z ^ = C ^ Y ^ = C ^ C ^ T X = C ^ C ^ T ∑ i = 1 rank ⁡ ( X ) σ i u i v i T = ∑ i = 1 N σ i u i v i T \widehat{\mathbf{Z}}=\widehat{\mathbf{C}} \widehat{\mathbf{Y}}=\widehat{\mathbf{C}} \widehat{\mathbf{C}}^{\mathrm{T}} \mathbf{X}=\widehat{\mathbf{C}} \widehat{\mathbf{C}}^{\mathrm{T}} \sum_{i=1}^{\operatorname{rank}(\mathbf{X})} \sigma_{i} \mathbf{u}_{i} \mathbf{v}_{i}^{\mathrm{T}}=\sum_{i=1}^{N} \sigma_{i} \mathbf{u}_{i} \mathbf{v}_{i}^{\mathrm{T}} Z =C Y =C C TX=C C Ti=1∑rank(X)​σi​ui​viT​=i=1∑N​σi​ui​viT​