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。以下为实例代码。

M = [ 2 3 3.2 4;4 2 1 2;3 4 7 8];
n = 2;
[u, s, v] = svd(M);
s(3,3) = 0;
nM = u*s*v' ;
rank(nM);
sum(  ((M - nM).^2)(:) )

M = [ 2 3 3.2 4;4 2 1 2;3 4 7 8];

n = 2;

[u, s, v] = svd(M);

s(3,3) = 0;

nM = u*s*v' ;

rank(nM);

sum( ((M - nM).^2)(:) )

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

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

参考资料：