On the Complexity of Robust PCA and ℓ₁-Norm Low-Rank Matrix Approximation

References

• Alon N, Naor A (2006) Approximating the cut-norm via Grothendieck’s inequality. SIAM J. Comput. 35(4):787–803.Crossref, Google Scholar
• Ames B, Vavasis S (2011) Nuclear norm minimization for the planted clique and biclique problems. Math. Programming 129(1):69–89.Crossref, Google Scholar
• Asahiro Y, Hassin R, Iwama K (2002) Complexity of finding dense subgraphs. Discrete Appl. Math. 121(1):15–26.Crossref, Google Scholar
• Brooks J, Dulá J (2013) The L1-norm best-fit hyperplane problem. Appl. Math. Lett. 26(1):51–55.Crossref, Google Scholar
• Brooks J, Dulá J, Boone E (2013) A pure L1-norm principal component analysis. Computational Statist. Data Anal. 61:83–98.Crossref, Google Scholar
• Brown T, Spencer J (1971) Minimization of ± 1 matrices under line shifts. Colloquium Mathematicae, Vol. 23 (Institute of Mathematics Polish Academy of Sciences), 165–171.Crossref, Google Scholar
• Candès E, Li X, Ma Y, Wright J (2011) Robust principal component analysis? J. ACM 58(3):Article 11.Crossref, Google Scholar
• Chandrasekaran V, Sanghavi S, Parrilo P, Willsky A (2011) Rank-sparsity incoherence for matrix decomposition. SIAM J. Optim. 21(2):572–596.Crossref, Google Scholar
• Chi E, Kolda T (2012) On tensors, sparsity, and nonnegative factorizations. SIAM J. Matrix Anal. Appl. 33(4):1272–1299.Crossref, Google Scholar
• Clarkson K, Woodruff D (2015) Input sparsity and hardness for robust subspace approximation. 56th Annual IEEE Sympos. Foundations Comput. Sci. (FOCS 2015).Google Scholar
• Doan X, Vavasis S (2013) Finding approximately rank-one submatrices with the nuclear norm and ℓ1-norm. SIAM J. Optim. 23(4):2502–2540.Crossref, Google Scholar
• Eriksson A, Van Den Hengel A (2010) Efficient computation of robust low-rank matrix approximations in the presence of missing data using the l1 norm. IEEE Conf. Comput. Vision and Pattern Recognition (CVPR ’10), 771–778.Google Scholar
• Fiorini S, Kaibel V, Pashkovich K, Theis D (2013) Combinatorial bounds on nonnegative rank and extended formulations. Discrete Math. 313(1):67–83.Crossref, Google Scholar
• Frieze A, Kannan R (1999) Quick approximation to matrices and applications. Combinatorica 19(2):175–220.Crossref, Google Scholar
• Gabriel K, Zamir S (1979) Lower rank approximation of matrices by least squares with any choice of weights. Technometrics 21(4):489–498.Crossref, Google Scholar
• Gillis N, Glineur F (2010) Using underapproximations for sparse nonnegative matrix factorization. Pattern Recognition 43(4):1676–1687.Crossref, Google Scholar
• Gillis N, Glineur F (2011) Low-rank matrix approximation with weights or missing data is NP-hard. SIAM J. Matrix Anal. Appl. 32(4):1149–1165.Crossref, Google Scholar
• Gillis N, Vavasis S (2015) On the Complexity of Robust PCA and ℓ1-norm Low-Rank Matrix Approximation. arXiv:1509.09236.Google Scholar
• Golub G, Van Loan C (1996) Matrix Computation, 3rd ed. (The Johns Hopkins University Press, Baltimore).Google Scholar
• Guruswami V, Raghavendra P, Saket R, Wu Y (2012) Bypassing UGC from some optimal geometric inapproximability results. Proc. Twenty-Third Annual ACM-SIAM Sympos. Discrete Algorithms (SODA 2012), 699–717.Google Scholar
• Kannan R, Vinay V (1999) Analyzing the structure of large graphs. Manuscript, http://www.cs.yale.edu/homes/kannan/Papers/webgraph.pdf.Google Scholar
• Ke Q, Kanade T (2003) Robust subspace computation using L1 norm. Technical Report CMU-CS-03-172, Carnegie Mellon University, http://www.cs.cmu.edu/afs/.cs.cmu.edu/Web/People/ke/publications/CMU-CS-03-172.pdf.Google Scholar
• Ke Q, Kanade T (2005) Robust l1 norm factorization in the presence of outliers and missing data by alternative convex programming. IEEE Comput. Society Conf. Comput. Vision and Pattern Recognition, CVPR ’05 (IEEE Computer Society, Washington, DC), 739–746.Google Scholar
• Khot S (2006) Ruling out PTAS for graph min-bisection, dense k-subgraph, and bipartite clique. SIAM J. Comput. 36(4):1025–1071.Crossref, Google Scholar
• Khuller S, Saha B (2009) On finding dense subgraphs. Albers S, Marchetti-Spaccamela A, Matias Y, Nikoletseas S, Thomas W, eds. Proc. 36th Internat. Colloquium Automata, Languages and Programming, ICALP ’09, Lecture Notes in Computer Science, Vol. 5555 (Springer, Berlin), 597–608.Crossref, Google Scholar
• Koren Y, Bell R, Volinsky C (2009) Matrix factorization techniques for recommender systems. IEEE Comput. 42(8):30–37.Crossref, Google Scholar
• Kwak N (2008) Principal component analysis based on L1-norm maximization. IEEE Trans. Pattern Anal. Machine Intelligence 30(9):1672–1680.Crossref, Google Scholar
• Markovsky I, Usevich K (2013) Structured low-rank approximation with missing data. SIAM J. Matrix Anal. Appl. 34(2):814–830.Crossref, Google Scholar
• Miettinen P, Mielikainen T, Gionis A, Das G, Mannila H (2008) The discrete basis problem. IEEE Trans. Knowledge and Data Engrg. 20(10):1348–1362.Crossref, Google Scholar
• Mirisaee S, Gaussier E, Termier A (2015) Improved local search for binary matrix factorization. AAAI Conf. Artificial Intelligence, 1198–1204.Google Scholar
• Netrapalli P, Niranjan U, Sanghavi S, Anandkumar A (2014) Non-convex robust PCA. Adv. Neural Inform. Processing Systems (NIPS), 2080–2088.Google Scholar
• Poljak S, Rohn J (1993) Checking robust nonsingularity is NP-hard. Math. Control, Signals and Systems 6(1):1–9.Crossref, Google Scholar
• Qiu C, Vaswani N, Lois B, Hogben L (2014) Recursive robust PCA or recursive sparse recovery in large but structured noise. IEEE Trans. Inform. Theory 60(8):5007–5039.Crossref, Google Scholar
• Rohn J (2000) Computing the norm ||A||∞, 1 is NP-hard. Linear and Multilinear Algebra 47(3):195–204.Google Scholar
• Shen BH, Ji S, Ye J (2009) Mining discrete patterns via binary matrix factorization. Elder JF IV, Fogelman-Soulié F, Flach PA, Javeed Zaki M, eds. Proc. 15th ACM SIGKDD Internat. Conf. Knowledge Discovery and Data Mining, KDD ’09 (ACM, New York), 757–766.Google Scholar
• Shum H, Ikeuchi K, Reddy R (1995) Principal component analysis with missing data and its application to polyhedral object modeling. IEEE Trans. Pattern Anal. Machine Intelligence 17(9):854–867.Crossref, Google Scholar
• Song Z, Woodruff D, Zhong P (2017) Low rank approximation with entrywise ℓ1-norm error. Hatami H, McKenzie P, King V, eds. Proc. 49th Annual ACM SIGACT Sympos. Theory Comput., STOC ’17 (ACM, New York), 688–701.Google Scholar
• Usevich K, Markovsky I (2014) Optimization on a Grassmann manifold with application to system identification. Automatica 50(6):1656–1662.Crossref, Google Scholar
• Woodruff D (2014) Sketching as a tool for numerical linear algebra. Foundations and Trends® Theoret. Comput. Sci. 10(1–2):1–157.Crossref, Google Scholar
• Wright J, Ganesh A, Rao S, Peng Y, Ma Y (2009) Robust principal component analysis: Exact recovery of corrupted low-rank matrices via convex optimization. Adv. Neural Inform. Processing Systems (NIPS), 2080–2088.Google Scholar
• Xu H, Caramanis C, Sanghavi S (2012) Robust PCA via outlier pursuit. IEEE Trans. Inform. Theory 58(5):3047–3064.Crossref, Google Scholar
• Zhang ZY, Li T, Ding C, Ren XW, Zhang XS (2010) Binary matrix factorization for analyzing gene expression data. Data Min. Knowl. Disc. 20(1):28–52.Crossref, Google Scholar
• Zheng Y, Liu G, Sugimoto S, Yan S, Okutomi M (2012) Practical low-rank matrix approximation under robust L1-norm. IEEE Conf. Comput. Vision and Pattern Recognition, CVPR ’12 (IEEE Computer Society, Washington, DC), 1410–1417.Google Scholar