Alternating Minimization for Square Root Principal Component Pursuit

References

• Beck A (2015) On the convergence of alternating minimization for convex programming with applications to iteratively reweighted least squares and decomposition schemes. SIAM J. Optim. 25(1):185–209.Crossref, Google Scholar
• Belloni A, Chernozhukov V, Wang L (2011) Square-root Lasso: Pivotal recovery of sparse signals via conic programming. Biometrika 98(4):791–806.Crossref, Google Scholar
• Boyd S, Parikh N, Chu E, Peleato B, Eckstein J (2011) Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations Trends Machine Learn. 3(1):1–122.Crossref, Google Scholar
• Burer S, Monteiro RDC (2003) A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Math. Programming 95(2):329–357.Crossref, Google Scholar
• Burer S, Monteiro RDC (2005) Local minima and convergence in low-rank semidefinite programming. Math. Programming 103(3):427–444.Crossref, Google Scholar
• Candès EJ, Li X, Ma Y, Wright J (2011) Robust principal component analysis? J. ACM 58(3):1–37.Crossref, Google Scholar
• Chandrasekaran V, Sanghavi S, Parrilo PA, Willsky AS (2011) Rank-sparsity incoherence for matrix decomposition. SIAM J. Optim. 21(2):572–596.Crossref, Google Scholar
• Chen C, Chen Q, Do MN, Koltun V (2019) Seeing motion in the dark. Proc. IEEE/CVF Internat. Conf. Comput. Vision (IEEE Computer Society, Washington, DC), 3185–3194.Google Scholar
• Chen Y, Fan J, Ma C, Yan Y (2021) Bridging convex and nonconvex optimization in robust PCA: Noise, outliers, and missing data. Ann. Statist. 49(5):2948–2971.Crossref, Google Scholar
• Chen C, He B, Ye Y, Yuan X (2016) The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent. Math. Programming 155(1):57–79.Crossref, Google Scholar
• Chen Y, Gui X, Zeng J, Zhao XL, He W (2024) Combining low-rank and deep plug-and-play priors for snapshot compressive imaging. IEEE Trans. Neural Network Learn. Systems 35(11):16396–16408.Crossref, Google Scholar
• Daniilidis A, Drusvyatskiy D, Lewis AS (2014) Orthogonal invariance and identifiability. SIAM J. Matrix Anal. Appl. (Singapore) 35(2):580–598.Crossref, Google Scholar
• Deng S, Li X, Zhang Y (2025) Alternating minimization for square root principal component pursuit. https://doi.org/10.1287/ijoc.2025.1105.cd, https://github.com/INFORMSJoC/2025.1105.Google Scholar
• Gabay D, Mercier B (1976) A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Computers Math. Appl. 2(1):17–40.Crossref, Google Scholar
• Ghadimi E, Teixeira A, Shames I, Johansson M (2014) Optimal parameter selection for the alternating direction method of multipliers (ADMM): Quadratic problems. IEEE Trans. Automated Control 60(3):644–658.Crossref, Google Scholar
• Glowinski R, Marroco A (1975) Sur l’approximation, par éléments finis d’ordre un, et la résolution, par pénalisation-dualité d’une classe de problèmes de dirichlet non linéaires. Rev. Française D’Automatique, Inform. Rech. Opér. Anal. Numérique 9(R2):41–76.Google Scholar
• Hu EJ, Shen Y, Wallis P, Allen-Zhu Z, Li Y, Wang S, Wang L, et al. (2021) LoRA: Low-rank adaptation of large language models. Preprint, submitted June 17, https://doi.org/10.48550/arXiv.2106.09685.Google Scholar
• Klopp O, Lounici K, Tsybakov AB (2017) Robust matrix completion. Probability Theory Related Fields 169(1):523–564.Crossref, Google Scholar
• Lee C, Liang L, Tang T, Toh KC (2024) Accelerating nuclear-norm regulari5zed low-rank matrix optimization through Burer-Monteiro decomposition. J. Machine Learn. Res. 25(379):1–52.Google Scholar
• Lewis AS (2002) Active sets, nonsmoothness, and sensitivity. SIAM J. Optim. 13(3):702–725.Crossref, Google Scholar
• Modi A, Chen J, Krishnamurthy A, Jiang N, Agarwal A (2024) Model-free representation learning and exploration in low-rank MDPs. J. Machine Learn. Res. 25(6):1–76.Google Scholar
• Nesterov Y (1983) A method for solving the convex programming problem with convergence rate O(1/k2). Proc. USSR Acad. Sci. 269(3):543–547. Google Scholar
• Nesterov Y (2013) Gradient methods for minimizing composite functions. Math. Programming 140(1):125–161.Crossref, Google Scholar
• Peng J, Sun W, Li HC, Li W, Meng X, Ge C, Du Q (2021) Low-rank and sparse representation for hyperspectral image processing: A review. IEEE Geosci. Remote Sensing Magazine 10(1):10–43.Crossref, Google Scholar
• Recht B, Fazel M, Parrilo PA (2010) Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Rev. 52(3):471–501.Crossref, Google Scholar
• Rennie JD, Srebro N (2005) Fast maximum margin matrix factorization for collaborative prediction. Raedt L, Wrobel S, eds. Proc. 22nd Internat. Conf. Machine Learn. (ACM, New York), 713–719.Google Scholar
• Sabach S, Teboulle M (2022) Faster Lagrangian-based methods in convex optimization. SIAM J. Optim. 32(1):204–227.Crossref, Google Scholar
• Singh DP, Joshi I, Choudhary J (2018) Survey of GPU based sorting algorithms. Internat. J. Parallel Programming 46(6):1017–1034.Crossref, Google Scholar
• Struski L, Morkisz P, Spurek P, Bernabeu SR, Trzciński T (2024) Efficient GPU implementation of randomized SVD and its applications. Expert Systems Appl. 248:123462.Crossref, Google Scholar
• Stucky B, Van De Geer S (2017) Sharp oracle inequalities for square root regularization. J. Machine Learn. Res. 18(67):1–29.Google Scholar
• Sun T, Zhang CH (2012) Scaled sparse linear regression. Biometrika 99(4):879–898.Crossref, Google Scholar
• Tang T, Toh KC (2024) Self-adaptive ADMM for semi-strongly convex problems. Math. Programming Comput. 16(1):113–150.Crossref, Google Scholar
• Tseng P (2001) Convergence of a block coordinate descent method for nondifferentiable minimization. J. Optim. Theory Appl. 109(3):475–494.Crossref, Google Scholar
• Vaiter S, Peyré G, Fadili J (2018) Model consistency of partly smooth regularizers. IEEE Trans. Inform. Theory 64(3):1725–1737.Crossref, Google Scholar
• Wang J, Wang LP, Yuan SS, Li F, Liu JX, Shang JL (2023) NLRRC: A novel clustering method of jointing non-negative LRR and random walk graph regularized NMF for single-cell type identification. IEEE J. Biomedical Health Inform. 27(10):5199–5209.Crossref, Google Scholar
• Wohlberg B (2017) ADMM penalty parameter selection by residual balancing. Preprint, submitted April 20, 2017, https://arxiv.org/abs/1704.06209.Google Scholar
• Wong RK, Lee TC (2017) Matrix completion with noisy entries and outliers. J. Machine Learn. Res. 18(1):5404–5428.Google Scholar
• Xu Y (2017) Accelerated first-order primal-dual proximal methods for linearly constrained composite convex programming. SIAM J. Optim. 27(3):1459–1484.Crossref, Google Scholar
• Yang Y, Ma C (2023) Optimal tuning-free convex relaxation for noisy matrix completion. IEEE Trans. Inform. Theory 69(10):6571–6585.Crossref, Google Scholar
• Zhang J, Yan J, Wright J (2021) Square root principal component pursuit: Tuning-free noisy robust matrix recovery. Adv. Neural Inform Processing Systems 34:29464–29475.Google Scholar
• Zhou Z, Li X, Wright J, Candés E, Ma Y (2010) Stable principal component pursuit. Proc. IEEE Internat. Sympos. Information Theory (IEEE, Piscataway, NJ), 1518–1522.Google Scholar