Alternating minimization for square root principal component pursuit
Shengxiang Deng, Xudong Li, Yangjing Zhang · 2025
Read Alternating minimization for square root principal component pursuit by Shengxiang Deng, Xudong Li, Yangjing Zhang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-00471.txt.
Introduction
Shengxiang Deng, Xudong Li, and Yangjing Zhang design fast solvers for a robust data-cleaning model, in work the head dates to 2024. The catalog lists 2025, but the head's year governs. The model, square root principal component pursuit, splits a data matrix into a clean low-rank part and a sparse corruption part. It provably recovers the clean part with one fixed penalty setting.
Its statistical strengths were known, but how to compute it well was not. The team proposes an alternating minimization method that needs no tuning: each step splits the problem into pieces with exact closed-form answers. Two further tricks, from a variational view of the nuclear norm and a factorized decomposition, speed it more. Tests confirmed the solvers are fast and stable. The work serves data scientists who clean video, images, and sensor feeds.
Catalog record
| CREATOR | Shengxiang Deng, Xudong Li, Yangjing Zhang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 87 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2501-00471
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Alternating minimization for square root principal component pursuit Shengxiang Deng, Xudong Li, Yangjing Zhang Abstract 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. KEYWORDS: Square root optimization, principal component pursuit, alternating minimization, low rank and sparse optimization 1 Introduction Low-dimensional models are ubiquitous in modern high-dimensional data analysis. Various algorithmic and theoretical advances in retrieving low-dimensional information such as sparsity, and low-rankness from massive high-dimensional datasets are made in recent years. These developments have undoubtedly revolutionized the practice of data science and signal processing, and found applications in many areas, such as image processing, bioinformatics, and machine learning. In this paper, we focus on recovering a low-rank matrix from corrupted observations. Specifically, we study the following observation model: D=L_{0}+S_{0}+Z_{0}, (1.1) where D\in\mathbb{R}^{n_{1}\times n_{2}} , without loss of generality, n_{1}\geq n_{2} , is a given observation matrix, L_{0} is an unknown low-rank matrix, S_{0} contains sparse corruptions, and Z_{0} is some dense noise. We aim to accurately and effectively estimate L_{0} and S_{0} . This model has been extensively studied in the literature, see [ 8 , 9 ] . In the seminar work of [ 8 ] , model ( 1.1 ) was studies under the noiseless setting, i.e., Z_{0} was assumed to be absent in model ( 1.1 ). Let \|X\|_{*} and \|X\|_{1}=\sum_{ij}|X_{ij}| denote the nuclear norm and the \ell_{1} -norm of the matrix X , respectively. [ 8 ] showed that under some assumptions on L_{0} and S_{0} to avoid the identifiability issues, it is possible to exactly recover (L_{0},S_{0}) by solving the following convex principal component pursuit problem: \min\left\{\|L\|_{*}+\lambda\|S\|_{1}\mid L+S=D\right\}, (1.2) where \lambda=1/\sqrt{n_{1}} is the universal regularization parameter, and is obviously independent of the rank of L_{0} and the sparsity of S_{0} . Later, [ 42 ] studied the more practical noisy setting where Z_{0} in model ( 1.1 ) is not vacuous. Assuming similar separation and incoherence conditions as in [ 8 ] and upper boundedness of the Frobenius norm of Z_{0} , i.e., \|Z_{0}\|_{F}\leq\delta for some known \delta>0 , they established recovery results for the optimal solution pair to the following stabilized generalization of ( 1.2 ): \min\left\{\|L\|_{*}+\lambda\|S\|_{1}\mid\|L+S-D\|_{F}\leq\delta\right\} (1.3) with \lambda=1/\sqrt{n_{1}} . Instead of solving ( 1.3 ) directly, [ 42 ] proposed in the simulation study to solve the following reformulation \min_{L,S}\,\|L\|_{*}+\lambda\|S\|_{1}+\frac{\rho}{2}\|L+S-D\|_{F}^{2}, (1.4) where \lambda=1/\sqrt{n_{1}} , \rho>0 is heuristically chosen based on the prior knowledge of Z_{0} . It is not difficult to observe that problems ( 1.3 ) and ( 1.4 ) are equivalent in the sense that there exists a correspondence between \rho>0 and \delta>0 such that the optimal solution sets of ( 1.3 ) and ( 1.4 ) are the same. Comparing to ( 1.3 ), problem ( 1.4 ) is considered to be more approachable from the optimization algorithmic aspect. Indeed, problem ( 1.4 ) can be readily solved via various first-order algorithms, such as the famous accelerated proximal gradient method [ 24 ] . Theoretical recovery results based on model ( 1.4 ) (or similar ones) are further investigated and strengthened by [ 21 , 36 , 12 ] . A main criticism of models ( 1.3 ) and ( 1.4 ) is that their constructions rely on the prior knowledge of the noise level to determine the parameter \rho . However, this information is usually not available ahead of time. Thus, in practice, to obtain meaningful estimators, the computationally expensive step of tuning these parameters is unavoidable. To overcome this difficulty, [ 41 ] proposed a new framework termed square root principal component pursuit. They showed that under standard identifiability assumptions as in [ 8 , 42 ] , any optimal solution pair to \min_{L,S}\,\,\|L\|_{*}+\frac{1}{\sqrt{n_{1}}}\|S\|_{1}+\sqrt{\frac{n_{2}}{2}}\|L+S-D\|_{F} (1.5) recovers (L_{0},S_{0}) with a recovery error of order {\cal O}(\sqrt{n_{1}n_{2}}\|Z_{0}\|_{F}) . We note that different from the squared penalty term in ( 1.4 ), the square root penalty term is used in ( 1.5 ), which makes the universal choice of \rho=\sqrt{n_{2}/2} possible. Thus, ( 1.5 ) is a tuning-free model for recovering (L_{0},S_{0}) . Similar ideas of using square-root loss to obtain tuning-free methods for various high-dimensional regression applications can be found in [ 2 , 30 , 29 , 40 ] . In [ 41 ] , slack variables (L_{1},S_{1},Z) were further introduced to equivalently reformulate model ( 1.5 ) into \begin{array}[]{cl}\min&\|L_{1}\|_{*}+\frac{1}{\sqrt{n_{1}}}\|S_{1}\|_{1}+\sqrt{\frac{n_{2}}{2}}\|Z\|_{F}\\[8.53581pt] \mbox{s.t.}&L+S+Z=D,\,L-L_{1}=0,\,S-S_{1}=0.\end{array} (1.6) Then, the two-block alternating direction method of multipliers (ADMM) by [ 19 , 16 ] was used to solve the above reformulated model. While the main focus of [ 41 ] is on the statistical recoverability of model ( 1.5 ), emphasizing the square-root loss and the universal choice of \rho , the practical efficiency, as well as theoretical convergence properties, of the used ADMM algorithm were not fully addressed. In this paper, we propose to further examine the model \min_{L,\,S}\,\,\|L\|_{*}+\lambda\|S\|_{1}+\mu\|L+S-D\|_{F} (1.7) with an emphasis from the optimization perspective. First, we reinterpret problem ( 1.7 ) as a distributionally robust optimization (DRO) problem, which aims to find solutions that minimize the worst-case squared loss over some specially designed uncertainty set. As a compliment to the current literature, this new interpretation deepens our understandings of model ( 1.7 ), and allows us to tune the parameter \mu to obtain meaningful estimators even without the widely used separation and incoherence assumptions. In fact, the relationships between regularized square-root loss problems and robust optimization have been observed widely in the literature; see, e.g., [ 15 , 38 , 37 , 28 , 3 ] . Secondly, we propose to solve problem ( 1.7 ) directly by the Alternating Minimization (AltMin) method [ 32 , 1 ] . The AltMin method or its general form, namely the block coordinate descent method (see, e.g., [ 32 ] ), is a fundamental and popular method for solving optimization problems of multiple blocks of decision variables. At each iteration, the objective function is minimized with respect to one of the blocks while the remaining is fixed. Specifically, the AltMin method for solving ( 1.7 ) minimizes the two variables S and L in turn and takes the following updating rule at the i -th iteration: \left\{\begin{aligned} &S^{i+1}\in\arg\min_{S}\,\,\{\lambda\|S\|_{1}+\mu\|L^{i}+S-D\|_{F}\},\\[2.0pt] &L^{i+1}\in\arg\min_{L}\,\,\{\|L\|_{*}+\mu\|L+S^{i+1}-D\|_{F}\}.\end{aligned}\right. (1.8) The two involved subproblems in ( 1.8 ) are shown to have closed-form optimal solutions (see Sections 3.1 and 3.2 ). This nice observation not only makes the AltMin method particularly suitable and easy to implement for solving ( 1.7 ), but it may also be of independent interest. Compared to the ADMM method, the above AltMin algorithm has much simpler updating rules and is tuning-free. We also conducted a comprehensive analysis on the convergence properties