Eckart-Young-Mirsky定理及其泛函版本简证
Published:
最佳低秩逼近的结果依赖于Eckart-Young-Mirsky定理，但大多数证明都略显繁琐，本文从优化的角度给出简要证明，并且推广到无限维的泛函版本。
Matrix Form
考虑Eckart-Young-Mirsky定理的矩阵形式, 定理告诉我们该问题的解由对矩阵$A$的奇异值分解给出，
\(\begin{align} &\min_Q \Vert A - AQQ^T \Vert_F^2 \\ &\text{s.t. } Q^T Q = I_k \end{align}\) 首先对优化目标进行化简，
\[\begin{align} \min_Q tr(A - A QQ^T)^T(A-AQQ^T) &=\min_Q tr(A^TA - A^TAQQ^T +AQQ^TQQ^TA^T) \\ &= \min_Q tr(A^TA) - tr(A^TAQQ^T) \\ &= \max_Q tr(A^TAQQ^T) \end{align}\]使用Lagrange乘子法求解，根据正交性约束，定义上三角阵$C$为Lagrange乘子，
\[\begin{align} L &= \frac{1}{2}[tr(A^TAQQ^T) - tr(C^T(Q^TQ-I))] \\ \frac{dL}{dQ} &= A^TAQ - QC^T = O \end{align}\]巧妙的是，根据正交性，Lagrange乘子矩阵$C$不仅为上三角阵，还为对角阵，
\[\begin{align} A^TAQ &= QC^T \\ Q^TA^TAQ &=Q^TQC^T \\ Q^TA^TAQ &= C^T \\ Q^TA^TAQ &= \Lambda \end{align}\]最后一个等号成立是因为等式左端为对阵矩阵。
更一般的形式是，对于任何$r$个正交基组成的矩阵$B$，最小化$A,B$之间的F范数误差的结果仍然由上式给出，
\[\begin{align} &\min \Vert A - Z Q \Vert_F^2 \\ &\text{s.t. } Q^TQ = I_k \end{align}\]由于对于正交基$Q$的组合系数$Z$没有限制，对其求导可以求出该系数，
\[\begin{align} L &= \Vert A - Z Q \Vert_F^2 = tr((ZQ-A)^T(ZQ-A))\\ \frac{dL}{dZ} &= Q^T(ZQ-A) =O \\ Z &= A Q^T \end{align}\]上式是显然的，因为组合系数显然应该为内积给出的投影系数 $Z=AQ^T$ ,才使得重构误差达到最小，因此实际上为等价问题。
\[\begin{align} &\min \Vert X - ZQ^T \Vert_F^2 =\min \Vert X - AQQ^T \Vert_F^2 = \sum_{i=k+1}^n \sigma_k(X)\\ &\text{s.t. } Q^T Q = I_k \end{align}\]基于优化的方法虽然较为简洁，但还需说明目标函数在在该点的凸性，该部分可能较为繁琐，此处暂略。
基于更高等视野的证明方法，可以利用 特征值不等式 中的Hoffman–Wielandt不等式。
Functional Form
推广到泛函中的结论， \(\begin{align} &\min_\phi \int (X(t) - \sum_{j=1}^r [\int X(t) \phi_j(t)dt] \phi_j(t) )^2dt\\ &\text{s.t. } \phi_j(t),j=1...r \text{ are r orthogonal basis} \end{align}\)
依葫芦画瓢，对目标函数进行化简，
\[\begin{align} &\min_\phi \int (X(t) - \sum_{j=1}^r \int [X(t) \phi_j(t)dt] \phi_j(t) )^2dt \\ =& \min_\phi \int X(t)^2 dt - 2 \int X(s) \sum_{j=1}^r [\int X(t) \phi_j(t)dt] \phi_j(s) ds + \int (\sum_{j=1}^r [\int X(t) \phi_j(t)dt] \phi_j(t) )^2 dt\\ =& \min_\phi \int X(t)^2 dt - \int X(s) \sum_{j=1}^r [\int X(t) \phi_j(t)dt] \phi_j(s) ds \\ =& \max_\phi \int X(s) \sum_{j=1}^r [\int X(t) \phi_j(t)dt] \phi_j(s) ds \end{align}\]定义Lagrange乘子$\lambda_i,\mu_{ik}$, 且根据对称性有，$\mu_{ik}=0(i\ge k)$,
\[\begin{align} L &= \frac{1}{2} \int X(t) \sum_{j=1}^r [\int X(s) \phi_j(t)dt] \phi_j(s) ds - \sum_j \lambda_j(\int \phi_j^2(s) ds-1) -\sum_{jk} \mu_{jk} \int \phi_j(s) \phi_k(s) ds \\ \frac{dL}{d \phi_j} &= \int X(s) X(t) \phi_j(t) dt - \lambda_j \phi_j(s)- \mu_{jk} \phi_k(s) = 0\\ \end{align}\]根据Kernel的定义，并且再次依葫芦画瓢，
\[\begin{align} \int \sigma(s,t) \phi_j(t) dt &= \lambda_j \phi_j(s) + \mu_{jk} \phi_k(s) \\ \int \phi_k(s) \sigma(s,t) \phi_j(t) dt ds &= \mu_{jk} \end{align}\]利用神奇的对称性，可以得到，$\mu_{jk} = 0$, 因此得到最终的方程，
\[\int \sigma(s,t) \phi_j(t) dt = \lambda_j \phi_j(s)\]类似地，在系数任意的前提下，也是一个等价问题，
\[\begin{align} &\min_\phi \int (X(t) - \sum_{j=1}^r S_j \phi_j(t) )^2dt\\ &\text{s.t. } \phi_j(t),j=1...r \text{ are r orthogonal basis} \end{align}\]经过类似地求导运算，可以得到每个正交基前面的系数$S_j$满足，
\[\begin{align} S_j = \int \phi_j(t) X(t) dt \end{align}\]由于观测通常有$n$个函数样本，对其取样本期望，核函数$\sigma(s,t)$用样本方差定义，可以得到最终的形式，
\[\begin{align} &\min E \int (X(t) - \sum_{j=1}^r S_j \psi_j(t))^2 dt = \sum_{j=r+1}^{\infty} d_j\\ &\text{s.t. } \psi_j(t),j=1...r \text{ are r orthogonal basis} \\ &\text{With } \sigma(s,t) = \sum_{j=1}^{\infty} d_j \phi_j(s) \phi_i(s) \end{align}\]