Eckart–Young theorem (低维矩阵近似)

       Eckart–Young theorem讲的是有一个矩阵M,找到另一个rank为r(小于M的rank)的矩阵N,使得\sum\limits_i\sum\limits_j (M_{i,j}-N_{i,j})^2 最小。其实是Frobenius norm

      解法是对M进行SVD后得M=U\sum V^*,取前r个最大的特征值和对应的特征向量,即:N = U\sum_r V^*。为何这样做之后|| M -N ||_F最小,可以见课堂笔记。主要是使用了Lagrange Multiplier。以下为实例代码。

      使用Octave计算后,可得如下结果示意图,可见,误差很小。代码见github。图中绿色为结果,蓝色为原始点。

EckartYoung

       后来作业里有一个要求,1_n^T*N = 0,即满足N列均值为0。条件强了很多,所以结果就不好了。图中绿色为结果,蓝色为原始点。

hw

 

参考资料:

  1. SVD
  2. Moreau Envelopes