2013-KDD-Robust principal component analysis via capped norms

Sun2013RobustPC.md

2013 - KDD - Robust principal component analysis via capped norms

Abstract

• such convex formulation is based on a strong assumption which may not hold in real-world applications, and the approximation error in these convex relaxations often can- not be neglected.
  • 算是本文的 Motivation 吧，但是究竟原来的 convex relaxation 怎么在 real-world 里不 hold 了，也没有交代清楚
  • 总的来说，作者就是觉得大家都在用 convex relaxation 求解，他要用 non-convex 的来求解

Problem Formulation

Capped norms

• 因为 $\sum_{i=1}^{p}\min(1, \frac{\sigma_i(X)}{\theta_1}) = \frac{1}{\theta_1}\sum_{i=1}^{p}\min(\theta_1, \sigma_i(X))$ ，可以看出 capped，盖帽，其实这个词用的非常形象，就是说大的，给你盖住，大于 $\theta_1$ 的奇异值，都变成 $\theta_1$
• 同理，第二个式子也是一样，大于 $\theta_2$ 的变成 $\theta_2$
• 从截图公式里的第二行可以看出，capped norm 是介于 rank 和 nuclear norm 之间的存在
• 如果所有奇异值都比 $\theta_1$ 大，所有元素都比 $\theta_2$ 大，那么上面截图里的不等号就要变等号了
• 也就是说， $\theta_1,\theta_2$ 越小，capped norm 就越逼近 rank 和 0 范数

Proposed non-convex formulation

• Difference of Convex (DC) programming treats a non-convex function as the difference of two convex functions, and then iteratively solves it on the basis of the combination of the first convex part and the linear approximation of the second convex part.
  • trace norm and the $\ell_1$-norm of matrices are convex
  • the summation of maximum is also convex
  • 把公式（5）当成这两部分的差

A Fast Alternating Algorithm

公式（5）等价于下面的式子（就是分子分母同乘以 $\theta_1,\theta_2$，因为 $\sum_{i=1}^{p}\min(1, \frac{\sigma_i(X)}{\theta_1}) = \frac{1}{\theta_1}\sum_{i=1}^{p}\min(\theta_1, \sigma_i(X))$ ）

@inproceedings{Sun2013RobustPC,
  title={Robust principal component analysis via capped norms},
  author={Qian Sun and Shuo Xiang and Jieping Ye},
  booktitle={KDD},
  year={2013}
}