RGNMR: A Gauss-Newton method for robust matrix completion with theoretical guarantees
Eilon Vaknin Laufer, Boaz Nadler · 2025
Read RGNMR: A Gauss-Newton method for robust matrix completion with theoretical guarantees by Eilon Vaknin Laufer, Boaz Nadler (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-2505-12919.txt.
Introduction
Vaknin Laufer and Nadler propose in 2025 a method to rebuild a simple structured matrix when some known entries are corrupted. Filling a partly seen matrix is a core data task, and bad entries make it harder. Past methods need many seen entries, break when rank is overstated, or fail on poorly scaled matrices.
Their method factors the matrix and refines the fit with a Gauss-Newton step, while dropping entries that look like outliers. Proofs show exact recovery under set conditions, with bounds that beat past factor based results. Simulations show gains over rivals, above all with few seen entries or wrong rank guesses.
Catalog record
| CREATOR | Eilon Vaknin Laufer, Boaz Nadler |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 129 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-12919
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
RGNMR: A Gauss-Newton method for robust matrix completion with theoretical guarantees Eilon Vaknin Laufer, Boaz Nadler Abstract Recovering a low rank matrix from a subset of its entries, some of which may be corrupted, is known as the robust matrix completion (RMC) problem. Existing RMC methods have several limitations: they require a relatively large number of observed entries; they may fail under overparametrization, when their assumed rank is higher than the correct one; and many of them fail to recover even mildly ill-conditioned matrices. In this paper we propose a novel RMC method, denoted RGNMR , which overcomes these limitations. RGNMR is a simple factorization-based iterative algorithm, which combines a Gauss–Newton linearization with removal of entries suspected to be outliers. On the theoretical front, we prove that under suitable assumptions, RGNMR is guaranteed exact recovery of the underlying low rank matrix. Our theoretical results improve upon the best currently known for factorization-based methods. On the empirical front, we show via several simulations the advantages of RGNMR over existing RMC methods, and in particular its ability to handle a small number of observed entries, overparameterization of the rank and ill-conditioned matrices. In addition, we propose a novel scheme for estimating the number of corrupted entries. This scheme may be used by other RMC methods that require as input the number of corrupted entries. 1 Introduction Figure 1 : Performance of RMC methods as a function of the number of observed entries measured by the oversampling ratio \frac{|\Omega|}{r\cdot(n_{1}+n_{2}-r)} where r\cdot(n_{1}+n_{2}-r) is the number of degrees of freedom of a rank r matrix. (left) Median rel-RMSE ; (right) Failure probability ( \pm 1.96 SE). The underlying matrix L^{*} has a condition number \kappa=2 . The corruption fraction is \alpha=5\% . Figure 2 : Performance of RMC methods under overparameterization with input rank of 5+i for i\in[0,5] . (left) Median rel-RMSE ; (right) Failure probability ( \pm 1.96 SE). The matrix L^{*} has a condition number \kappa=2 and the oversampling ratio is \frac{|\Omega|}{r\cdot(n_{1}+n_{2}-r)}=12 .The corruption fraction is \alpha=5\% Figure 3 : Performance of RMC methods as a function of the condition number. (left) Median rel-RMSE ; (right) Failure probability ( \pm 1.96 SE). The oversampling ratio is \frac{|\Omega|}{r\cdot(n_{1}+n_{2}-r)}=12 . The corruption fraction is \alpha=5\% . Low-rank matrices play a fundamental role in multiple scientific disciplines. As reviewed in Davenport and Romberg, (2016) , in various applications, there is a need to recover a low rank matrix from only a subset of its entries. Examples include recommendation systems ( Bennett et al.,, 2007 ) , various problems in computer vision ( Kennedy et al.,, 2016 ; Tulyakov et al.,, 2016 ; Miao and Kou,, 2021 ) , in sensor networks ( Wu et al.,, 2025 ) and in single-cell data analysis ( Lejun et al.,, 2025 ) . A key challenge in these and other applications is that some of the observed entries may be arbitrarily corrupted outliers. In this work, we consider the robust matrix completion (RMC) problem, of recovering a low rank matrix from a subset of its entries, out of which a few are outliers. Formally, let X\in\mathbb{R}^{n_{1}\times n_{2}} be a matrix with a decomposition X=L^{*}+S^{*} , where L^{*} is a rank r matrix and S^{*} is a sparse corruption matrix whose few non-zero entries are arbitrary. The RMC problem is to recover L^{*} from the subset \{X_{i,j}\,|\,(i,j)\in\Omega\} , where \Omega\subset[n_{1}]\times[n_{2}] denotes the subset of observed entries in X . Related work. Over the past decade, the RMC problem was studied from both mathematical, computational and statistical perspectives. On the computational front, several RMC algorithms have been proposed. In general, to solve the RMC problem the following optimization issues need to be addressed: (i) either promote a low rank solution or strictly enforce it; and (ii) suppress the potentially detrimental effect of the outliers, whose locations are a-priori unknown. Regarding the first issue, one approach is to incorporate into the optimization objective a low-rank promoting penalty such as the nuclear norm ( Candès et al.,, 2011 ; Nie et al.,, 2012 ; Klopp et al.,, 2017 ; Wong and Lee,, 2017 ; Chen et al.,, 2021 ) . Under suitable assumptions on the matrices L^{*} , S^{*} and on the set \Omega , these methods enjoy strong theoretical guarantees. However, these schemes are in general computationally slow, and do not scale well to large matrices. A different approach is to strictly enforce a rank r solution. This can be done by optimization over the manifold of rank r matrices ( Yan et al.,, 2013 ; Cambier and Absil,, 2016 ) , or by projecting matrices onto it. Several works factorize the target matrix as L=UV^{\top} , and optimize over the two factor matrices U\in\mathbb{R}^{n_{1}\times r} and V\in\mathbb{R}^{n_{2}\times r} ( Yi et al.,, 2016 ; Lin et al.,, 2017 ; Zeng and So,, 2017 ; Huang et al.,, 2021 ; Wang et al.,, 2023 ) . The resulting problem involves only (n_{1}+n_{2})r variables instead of the n_{1}\times n_{2} entries in L . Factorization based methods are thus in general more scalable and able to handle larger matrices. Regarding the second issue, some works attenuate the effect of the outliers either by estimating the locations of the corrupted entries and removing them, or by estimating their values S_{ij} for (i,j)\in\Omega ( Yan et al.,, 2013 ; Cherapanamjeri et al.,, 2017 ; Huang et al.,, 2021 ; Chen et al.,, 2021 ; Wang and Wei,, 2024 ) . Other works mitigate the influence of outliers by using a robust norm on the difference X-L in the objective function ( Nie et al.,, 2012 ; Cambier and Absil,, 2016 ; Lin et al.,, 2017 ; Zhao et al.,, 2016 ; Zeng and So,, 2017 ; Wang et al.,, 2023 ) . Limitations of existing RMC methods. Despite extensive research on the RMC problem, current algorithms have various limitations: (i) Several RMC methods fail to recover the low rank matrix unless the number of observed entries is quite large; (ii) Some methods require as input the (often unknown) rank r of the target matrix and fail when overparameterized even by just a single additional dimension (an input rank of r+1 ); (iii) Various methods fail to recover a matrix with a moderate condition number, as low as 5. We illustrate these issues in Figures 1 , 2 and 3 . These figures show recovery results of various RMC algorithms for a matrix L^{*} of size 3200\times 400 , rank r=5 , at a corruption rate of \alpha=5\% (see Section 4 for further details). As in Zeng and So, (2017) ; Tong et al., (2021) and Huang et al., (2021) , the quality of a recovered matrix \hat{L} is measured by the relative error \texttt{rel-RMSE}=\tfrac{\|\hat{L}-L^{*}\|_{F}}{\|L^{*}\|_{F}} , and is considered a failure if \texttt{rel-RMSE}>10^{-3} . For each simulation setting we ran 100 independent realizations. As shown in these figures, RMC methods such as AOP ( Yan et al.,, 2013 ) , RMC ( Cambier and Absil,, 2016 ) , RPCA-GD ( Yi et al.,, 2016 ) , RRMC ( Cherapanamjeri et al.,, 2017 ) , HUB ( Ruppel et al.,, 2020 ) and HOAT ( Wang et al.,, 2023 ) require a large number of observed entries and fail