Alternating Minimization for Square Root Principal Component Pursuit

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. Although 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.

History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms–Continuous.

Funding: The research of X. Li was supported in part by the National Key R&D Program of China [Grant 2023YFA1009300] and the National Natural Science Foundation of China [Grants 12271107 and 12531014]. The research of Y. Zhang was supported by the National Key R&D Program of China [Grant 2023YFA1011100].

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2025.1105) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2025.1105). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.