优化问题：
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∥F2rank(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=INmin{Y∈RN×Lmin∥CY−X∥F2}=argCTC=INmin{Y∈RN×LminTr(YTY−2YTCTX+XTX)}{C
=argminCTC=INTr([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)σiuiviT=i=1∑NσiuiviT
