最近回过头来找到了RPCA的paper，也就是最经典的那个吧，尽管有错误。全文并没有仔细描述各种具体放入算法，只是从理论上上说了这个RPCA的问题以及介绍了2个用来解决这个问题的方法，其实重点只介绍了一个吧，就是那个proximal gradient approach吧，也只是使用了这个方法来做了个伪代码的算法介绍，对这个算法也没有具体说，不过给出了reference。感兴趣可以自己去看，反正我已经打印出来了，肯定要看的。
RPCA是解决这个问题的，D=A+E 其实A是low rank的E是sparse的。D是已知的，假设真实数据是A，E是噪声。并且A是low rank的。
也就是解决 在A和E这样的未知数下：min rank(A) + E的0范，s.t. D=A+E。
接着很自然的relaxing：rank转化成nuclear norm，0范转化成1范（因为rank和0范都是NP问题的）。
我一直对这个转化很感兴趣，因为毕竟不是搞数学的，作者在这个paper中说了很清楚的，我拿出来大概翻译下吧：
由A的核范 + lambda*E的1范很自然的会来代替rank(A) + lambda*E的0范，当max(A的2,2范,E的1,无穷范)小于等于1的时候。并且根据最近的研究成果表明，核范代替rank最小化，1范代替0范是有一定的条件的，但是这个条件比较broad。对于几乎所有的relaxing后的解大都可以代替真实解。
文中接着还说了，relaxing后的解并不真正等价于原来真实解，只是在一定概率下，命中率较高。
好了至此我也明白了，relaxing后的solution是在一定条件下才和真正解近似的。
补充下：只有lambda>0的情况下，以上讨论才成立。