Robust Principal Component Analysis

Definition

PCA doesn’t work well when there are noises in the input data. The goal of Robust PCA is to find a matrix decomposition to a low rank matrix and a sparse matrix.

The optimization problem of Robust PCA is set up as $\underset{L,S}{\mathrm{argmin}}\mathrm{rank}(L)+\lambda ||S|{|}_0\text{s.t.}X=L+S$ where $L$ is a low-rank matrix, $S$ is a sparse matrix, and $||\cdot |{|}_0$ is the number of non-zero elements in the matrix.

However, the optimization problem is infeasible because it is neither continuous nor convex. So, we solve the relaxed problem $\underset{L,S}{\mathrm{argmin}}||L|{|}_{\ast }+\lambda ||S|{|}_1\text{s.t.}X=L+S$ where $||\cdot |{|}_{\ast }$ is the Nuclear Norm of the matrix, and $||\cdot |{|}_1$ is the matrix L1 norm.

Applications

• Video Surveillance
• Face Recognition
• Latent Semantic Indexing
• Collaborative Filtering (Matrix Completion)