# Alternating minimization for square root principal component pursuit

arXiv: https://arxiv.org/abs/2501.00471 · HTML: https://mlsanity.com/paper/2501.00471/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 44 references that are in the map.
- First posted on arXiv 31 Dec 2024.

## Builds on (most cited first, 14 of 14)

- [Distributionally Robust Logistic Regression](https://mlsanity.com/paper/1509.09259/) (2015)
- [Bridging Convex and Nonconvex Optimization in Robust PCA: Noise, Outliers, and Missing Data](https://mlsanity.com/paper/2001.05484/) (2020)
- [Optimal parameter selection for the alternating direction method of multipliers (ADMM): quadratic problems](https://mlsanity.com/paper/1306.2454/) (2013)
- [ADMM Penalty Parameter Selection by Residual Balancing](https://mlsanity.com/paper/1704.06209/) (2017)
- [Matrix Completion with Noisy Entries and Outliers](https://mlsanity.com/paper/1503.00214/) (2015)
- [Model Consistency of Partly Smooth Regularizers](https://mlsanity.com/paper/1405.1004/) (2014)
- [Accelerated first-order primal-dual proximal methods for linearly constrained composite convex programming](https://mlsanity.com/paper/1606.09155/) (2016)
- [Efficient GPU implementation of randomized SVD and its applications](https://mlsanity.com/paper/2110.03423/) (2021)
- [Accelerating nuclear-norm regularized low-rank matrix optimization through Burer-Monteiro decomposition](https://mlsanity.com/paper/2204.14067/) (2022)
- [On Regularized Square-root Regression Problems: Distributionally Robust Interpretation and Fast Computations](https://mlsanity.com/paper/2109.03632/) (2021)
- [Orthogonal Invariance and Identifiability](https://mlsanity.com/paper/1304.1198/) (2013)
- [Faster Lagrangian-Based Methods in Convex Optimization](https://mlsanity.com/paper/2010.14314/) (2020)
- [Self-adaptive ADMM for semi-strongly convex problems](https://mlsanity.com/paper/2310.00376/) (2023)
- [Square Root Principal Component Pursuit: Tuning-Free Noisy Robust Matrix Recovery](https://mlsanity.com/paper/2106.09211/) (2021)

## Abstract (arXiv)

Recently, the square root principal component pursuit (SRPCP) model has garnered significant research interest. It is shown in the literature that the SRPCP model guarantees robust matrix recovery with a universal, constant penalty parameter. While its statistical advantages are well-documented, the computational aspects from an optimization perspective remain largely unexplored. In this paper, we focus on developing efficient optimization algorithms for solving the SRPCP problem. Specifically, we propose a tuning-free alternating minimization (AltMin) algorithm, where each iteration involves subproblems enjoying closed-form optimal solutions. Additionally, we introduce techniques based on the variational formulation of the nuclear norm and Burer-Monteiro decomposition to further accelerate the AltMin method. Extensive numerical experiments confirm the efficiency and robustness of our algorithms.