Rubost PCA 优化
最近一直在看Robust PCA做背景建模的paper, 顺便总结了一下了Robust PCA.前面一篇博客介绍了PCA与Robust PCA区别,本篇博客总结Robust PCA 常见的优化方法,欢迎交流学习。在这里强烈推荐一篇博客Rachel Zhang的Robust PCA 学习笔记。
1.预备知识
2.问题描述
许多实际应用中已知的数据矩阵Ｄ往往是低秩或近似低秩的，但存在随机幅值任意大且分布稀疏的误差破坏了原有数据的低秩性，为了恢复矩阵Ｄ的低秩结构，可将矩阵Ｄ分解为两个矩阵之和，即Ｄ＝Ａ＋Ｅ，其中矩阵Ａ和Ｅ未知，但Ａ是低秩的，E是稀疏的。
当矩阵Ｅ的元素服从独立同分布的高斯分布时，可用经典的PCA来获得最优的矩阵Ａ，即转换为如下最优化问题：
当Ｅ为稀疏的大噪声矩阵时，同时引入折中因此，此问题可转化为如下优化问题：
上式中秩函数、0范数均非凸，变成了NP-hard问题，需要对其松弛，方可进行优化。由范数知识可知，核范数是秩函数的凸包，1范数是0范数的凸包，所以上述NP-hard问题松弛后可转化凸优化问题：
3.Rubost PCA优化
增广拉格郎日乘子法（Augmented Lagrang Multipliers）
交替方向法（Alternating Direction Methods）
ADM 是对ALM的改善，加快了收敛速度，又称为不精确拉格朗日乘子法。
迭代阈值法（Iterative Thresholding）
**加速近端梯度（Accelerated Proximal Gradient）
**
将优化问题式的等式约束松弛到目标函数中，得到如下的拉格朗日函数:
f(A,E)的Frechet梯度Lipschitz连续性推导
f(ｘ)二次逼近推导
4.Rubost PCA优化总结
IT算法的迭代形式简单且收敛，但收敛速度比较慢，且很难选取合适的步长；APG与IT算法类似，但它却大大降低了迭代次数；ALM比APG快很多，而且ALM可以达到较高的精度，需要较低的存储空间。不精确拉格朗日乘子法（IALM）改善了EALM，不需要求解精确解，速度较快。
参考
1. The Augmented Lagrange Multiplier Method for Exact Recovery of Corrupted Low-Rank Matrices
2. Fast Convex Optimization Algorithms for Exact Recovery of a Corrupted Low-Rank Matrix
3. A Singular Value Thresholding Algorithm for Matrix Completion
4. Sparse and Low-Rank Matrix Decomposition via Alternating Direction Methods
5. Robust Principal Component Analysis
6. http://blog.csdn.net/tiandijun/article/details/44917237