On the Complexity of Robust PCA and $\ell_1$-norm Low-Rank Matrix Approximation
Nicolas Gillis, Stephen A. Vavasis
The low-rank matrix approximation problem with respect to the component-wise $\ell_1$-norm ($\ell_1$-LRA), which is closely related to robust principal component analysis (PCA), has become a very popular tool in data mining and machine learning. Robust PCA aims at recovering a low-rank matrix that was perturbed with sparse noise, with applications for example in foreground-background video separation. Although $\ell_1$-LRA is strongly believed to be NP-hard, there is, to the best of our knowledge, no formal proof of this fact. In this paper, we prove that $\ell_1$-LRA is NP-hard, already in the rank-one case, using a reduction from MAX CUT. Our derivations draw interesting connections between $\ell_1$-LRA and several other well-known problems, namely, robust PCA, $\ell_0$-LRA, binary matrix factorization, a particular densest bipartite subgraph problem, the computation of the cut norm of $\{-1,+1\}$ matrices, and the discrete basis problem, which we all prove to be NP-hard.
An implementation is available here: https://sites.google.com/site/nicolasgillis/code. From the page:
This Matlab code implements an exact cyclic coordinate descent method for the component-wise ℓ1-norm matrix approximation problem: Given an m-by-n matrix M and a factorization rank r, find an m-by-r matrix U and an r-by-n matrix V such that ||M-UV||1 = sumi,j |M-UV|ij is minimized. By default, it initializes the algorithm with the optimal solution of the ℓ2-norm problem using the truncated singular value decomposition provided by Matlab.
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.
No comments:
Post a Comment