RPCA via ALM Method

Robust PCA

Principal Component Analysis(PCA)는 복잡한 다차원의 행렬을 낮은 차원의 데이터로 변환하는 방법이다. 원 데이터의 정보를 잘 보존한 채로 낮은 차원의 데이터로 변환해 연산도 줄고 noise도 제거가 되는 효과가 있어 데이터 전처리에 다양하게 쓰이는 기법이다.

하지만 만약 원 데이터가 noise에 영향을 많이 받아 알아보기 힘든 "grossly corrupted" 된 데이터에서는 사용하기 어렵다.

이를 해결하기 위해서 나타난 방법 중 하나가 Robust PCA (RPCA) [1] 기법이다. 정의는 다음과 같다.

Given $D=A+E$, where $A$ and $E$ are unknown, but $A$ is known to be low rank and $E$ is known to be sparse, recover $A$ from $D$

Noise가 낀 원본 데이터 $D$에서 노이즈가 제거된 $A$를 찾는 방법이다. 이 때, $A$가 low-rank 이고 $E$가 sparse 해야 한다는 가정이 있어야 한다.

여기서 noise와 관련된 행렬 $E$가 sparse 해야 한다는데, 어떻게 원본 데이터가 "grossly corrupted" 될 수 있는지 의문이었다. 내가 이해한 바로는 $E$는 sparse 하지만 그 magnitude, 정도는 arbitrary할 수 있어 sparse한 $E$로도 원본 데이터가 충분히 영향을 많이 받을 수 있다는 것으로 이해하였다.

수식으로는 다음과 같다

$||\cdot||_0$는 L0 norm이다.

이 때, 위 식은 NP-Hard 문제가 합쳐진 것으로 nonconvex-problem이 된다. 따라서 위 수식을 다음과 같이 relax할 수 있다.

$||\cdot||_*$는 nuclear norm, $||\cdot||_1$는 L1 norm이다.
즉 $A+E=D$가 constraint가 되는 convex optimization 문제가 된다.

Augmented Lagrangian Multiplier Method

RPCA를 풀 수 있는 다양한 방법들이 있는데, 그 중 Augmented Lagrangian Multiplier [2]를 이용한 방법을 소개한다.

RPCA via Iterative Thresholding

[7] [24] 에 의하면 optimal 한 $(\hat{𝐴},\hat{E} )$ 는 singular value decomposition (SVD)을 이용해서 유도할 수 있다.

여기서

여기서 $x \in \mathbb{R}, \;\;\varepsilon>0\;$이다.

Augmented Lagrangian Multiplier (ALM)

행렬 (혹은 데이터) $X$에 대하여

이 때, augmented Lagrangian Function을 다음과 같이 나타낸다.

여기서 $\begin{Vmatrix}\cdot\end{Vmatrix}_F$ 는 Frobenius norm, $\left\langle A^TB \right\rangle=tr(A^TB)$으로 $A^TB$의 주대각선의 성분들의 합을 나타낸다.

위 식에서 optimal $X$를 찾기 위해서는 $\argmin_{X} L(X,Y,\mu)$ 을 구하면 된다.

같은 방식으로 RPCA에 ALM을 적용하면 다음과 같다.

그러면 Lagrangian function은 다음과 같이 된다.

마찬가지로 optimal한 $(A,E)$를 얻기 위해서는 $\argmin_{X} L(A,E,Y,\mu)$ 을 구하면 된다.

Reference
[1] J. Wright, A. Ganesh, S. Rao, and Y. Ma, “Robust principal component analysis: Exact recovery of corrupted low-rank matrices,” Adv. Neural Inf.
Process. Syst., vol. 87, no. 4, pp. 2080–2088, 2009
[2] Z. Lin, M. Chen, and Y. Ma, “The augmented Lagrange multiplier method for exact recovery of corrupted low-rank matrices,” unpublished paper, 2010. [Online]. Available: https://arxiv.org/abs/1009.5055v1
[3] Cai, J., Cand`es, E., Shen, Z.: A singular value thresholding algorithm for matrix completion. preprint, code available at http://svt.caltech.edu/code.html (2008)
[4] Yin, W., Hale, E., Zhang, Y.: Fixed-point continuation for ℓ1-minimization: methodology
and convergence. preprint (2008)