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

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注