Guarantees of a Preconditioned Subgradient Algorithm for Overparameterized Asymmetric Low-rank Matrix Recovery
Authors: Paris Giampouras
HanQin Cai
Rene Vidal
Venue: ICML 2025 poster (2025)
Keywords: Matrix factorisation
low-rank
matrix sensing
preconditioned subgradient
Primary area: optimization->nonconvex
TL;DR: Linear convergence rates of an overparameterized preconditioned subgradient algorithm for robust low-rank matrix estimation.

Abstract: In this paper, we focus on a matrix factorization-based approach for robust recovery of low-rank  asymmetric matrices from corrupted measurements. We propose an  Overparameterized Preconditioned Subgradient Algorithm (OPSA) and provide, for the first time in the literature, linear convergence rates independent of the rank of the sought asymmetric matrix in the presence of gross corruptions. Our work goes beyond existing results in preconditioned-type approaches addressing their current limitation, i.e., the lack of convergence guarantees in the case of asymmetric matrices of unknown rank. By applying our approach to (robust) matrix sensing, we highlight its merits when the measurement operator satisfies a mixed-norm restricted isometry property. Lastly, we present extensive numerical experiments that validate our theoretical results and demonstrate the effectiveness of our approach for different levels of overparameterization and corruption from outliers.

Guarantees of a Preconditioned Subgradient Algorithm for Overparameterized Asymmetric Low-rank Matrix Recovery
Paris Giampouras
HanQin Cai René Vidal
Abstract
Kümmerle & Verdun, 2021; Cai et al., 2023), and robust principal component analysis (Candès et al., 2011; Netra- palli et al., 2014; Giampouras et al., 2018; Cai et al., 2019; 2021b). can all be cast as low-rank matrix recovery prob- lems and then solved using minimization algorithms that seek a matrix X E Rmx= that is as close as possible the unknown low-rank matrix X, Rmxn.
In this paper, we focus on a matrix factorization- based approach to recover low-rank asymmer- ric matrices from corrupted measurements. We propose an Overparameterized Preconditioned Subgradient Algorithm (OPSA) and provide, for the first time in the literature, linear convergence rates independent of the rank of the sought asym- metric matrix in the presence of gross corrup- tions. Our work goes beyond existing results in preconditioned-type approaches addressing their current limitation, i.e.. the lack of convergence guarantees in the case of asymmetric matrices of unknown rank. By applying our approach to (robust) matrix sensing, we highlight its merits when the measurement operator satisfies a mixed- norm restricted isometry property. Lastly, we present extensive numerical experiments that val- idate our theoretical results and demonstrate the effectiveness of our approach for different levels of overparameterizztion and outlier corruptions.
A major challenge in low-rank matrix recovery concerns the computational complexity and memory requirements of the proposed algorithms when the size of the unknown matrix significantly increases. To address this, matrix factorization- based approaches have been proposed, (Chi et al., 2019; Park et al., 2016), which, given 2 rank (X.). use matri- ces L E Rm and R Raxr such that X LR... These approaches enable the development of iterative algorithms with significantly reduced computational complexity and memory storage requirements. However, they lead to non- convex formulations of the optimization problems, which pose their own challenges the derivation of theoretical guarantees and fast rates of convergence.
Alternating gradient- maased algorithms have been standard approach for solving matrix factorization- based problems. A well-known issue with these approaches lies in the depen- dence of their rate of convergence on the condition number of the unknown matrix X..nTong et al., 202 This makes convergence too slow in problems where the sought matrix is ill-conditioned. Several works, (Park al., 2016; Zhang et al., 2023), address this issue by moving beyond vanilla gradient updates and resorting preconditioned approaches. In (Tong et al., 2021a), preconditioned gradient algorithms have been proposed that consist of updates in the following form:
1. Introduction
Low-rank matrix recovery has been ubiquitous problem showing up in numerous applications in the fields of sig- nal/image processing, machine learning, and data science (Recht et al., 2010; Chen et al., 2013; Davenport & Romberg, 2016; Cai et al., 202 la; Smith et al., 2024; Wang et al., 2024). For instance, problems such as matrix sensing (Jain al., 2013; Wei al., 2016; Park et al., 2017; Li et al., 2020), matrix completion (Candes & Recht, 2008; Nic al., 2012:
= -
(R. R.)
Department of Computer Science, University of Warwick, Coventry, England, UK 'Department Statistics and Data Sci- ence and Department of Computer Science, University of Central Florida, Orlando, FL, USA "Center for Innovation in Data Engi- neering and Science (IDEAS). Departments of ESE and Radiology. University of Pennsylvania, Philadelphia, PA, USA. Correspon- dence to: René Vidal <vidalr@@ seas. weas.upenn.edu>.
preconditioner
(1)
R R R4 V
(L, L,
preconditioner
Preconditioned-based approaches, e.g. (Chi et al., 2019; Cai et al., 2021c; Zhang et al., 2023; 2024; Cai et al., 2024), lead to linear rates of convergence that do not depend on the condition number of X.. Recently, these approaches have been extended to the robust rank matrix recovery
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Guarantees of Overparamcterized Preconditioned Subgradient Algorithm
framework, aiming address more challenging scenarios that account for the presence of grossly corrupted data. In these settings, (Tong et al., 2021b) reported similar rates of convergence, which are however negatively influenced as the level of corruption increases.
1.1. Main Contributions
In this work, we advance beyond previous work by focusing robust low-rank matrix recovery with non-smooth ob- jective function, addressing the unique challenges of recov- ering asymmetric matrices with unknown rank (see Table I and comparison with SOTA). Our preconditioners naturally arise by adopting Srass--ewtoo--ypee updates in an implic- itly regularized objective function. Our main contributions are summarized as follows:
A fundamental assumption made in the above-mentioned approaches is that the rank r of the sought matrix X. is known. Clearly, in the case that r is underestimated, the algorithm will only be able to find low-rank approximation of the ground truth matrix. To address this shortcoming, in (Ma & Fattahi, 2021), the authors overparameterized the rank as d 2 r = rank(X.). and established a linear rate of convergence for robust low-rank matrix recovery for symmetric matrices using vanilla subgradient algorithm. Further works, build on this observation aiming to establish convergence to the ground truth matrix X, under weaker conditions, (Ding et al., 2021; Xiong et al., 2023), or to explore the intriguing implicit regularization phenomena in this setting, (Soltanolkotabi et al., 2023).
We propose a novel algorithm, coined Overparameter- ized Preconditioned Subgradient Algorithm (OPSA), that minimizes a robust { loss function. To account for overparameterization caused by rank overestimation, we propose a novel distance metric and assume that the matrix factors are initialized sufficiently close to the ground truth (which can be easily attained by spectral initialization). In Theorem 5.4, we show that OPSA converges linearly to the low-rank ground truth matrix X, using an adaptive Polyak's 's step size. Note that our main result holds for general non-smooth loss functions under certain conditions such as the restricted rank-d sharpness condition and restricted Lipschitz continuity. Moreover, our results extend the preconditioned sub- gradient method (Tong et al., 2021b) from the exact known rank setting to the overparameterized regime.
Note that due to non-invertibility issues as the iterates L,, R2 converge to L., R.,, the overparameterized scenario cannot be directly adopted as such in the previously pro- posed preconditionedd-aat
methods that rely updates given in (1). To address this issue, recent works, (Zhang et al., 2023; Xu et al., 2023), proposed an overparameterized preconditioned algorithm focusing on symmetric matrices and assuming smooth loss functions, with updates in the form:
For theoretical results, we focus on robust matrix sensing and show that linear convergence holds for OPSA both in the noiseless case and in the presence of gross coruptiion/outtiers when the measurement ma- trices satisfy a mixed-norm restricted isometry property (RIP). In this setting, we unveil how the iteration com- plexity is affected by overparameterization. Moreover, our results showcase that the tolerance of measure- ment matrices in outliers is another important factor for sharpness around X., which is a necessary condi- tion for exact convergence.
1++1 L. + (2)
and showed linear convergence at a rate independent of the condition number of X, and the overparameterization of the true rank. Focusing again on smooth problems, in (Cheng & Zhao, 2024), the authors proposed an extension of these works the case of asymmetric matrices coming up with an alternating algorithm with regularized preconditioners leading to updates:
In the experimental section, we empirically show- case the favorable performance of the proposed OPSA against the statc-of-the-art under different levels of overparameterization d, for the problem of robust ma- trix sensing with Gaussian measurements. We also demonstrate that OPSA constantly enjoys linear conver- gence with varying condition numbers k, parameters X, and outlier densities even when the rank is heav- ily overestimated. The experiments provided further confirm our theoretical findings.
L = L. VV (R] R + + Re11 R. (L ) (I, L, + +.T)
(3)
In this work, we depart from previous works by focusing on robust low-rank matrix recovery in the presence of outliers and propose an overparameterized preconditioned based algorithm in the unknown rank regime. Our work aims to address the following question (Q):
1.2. Notation
Q: Can we establish linear rates of convergence to the ground truth X., in the case of non-smooth minimization problems in the overparameterized regime with unknown rank, and for asymmetric matrices X.?
The transpose of a vector or matrix is denoted as (.)T. The Euclidean vector norm is denoted as || 1|2- The Frobenius and operator matrix norms are denoted as || ||r and || -lopp
2

---

Guarantees of Overparameterized Preconditioned Subgradient Algorithm
Table Comparison of theoretical convergence properties of SOTA algorithms for low-rank matrix estimation. Columns indicate if algorithms handle asymmetric matrices, outliers, unknown rank, and if convergence is independent of x(X.), the condition number of x. The proposed OPSA method addresses all these challenges. Asymmetric Outliers
Algorithm
Unknown Rank
No dependency x²( x((x))
VANILLA GD (Stöger & Soltanolkotabi, 2021)
SCALEDGD (Tong et al., 2021a)
AXK
X
PRECGD (Zhang et al., 2023)
x
/
SCALEDGD(A) (Xiong et al., 2023)
X
/
SCALEDSM (Tong al., 2021b)
X
OPSA (Proposed)
respectively. We also denote as (X) the singular values of matrix X -assuming a decreasing order as i increases- and x(X) ) its condition number. We denote the trace of matrix as tr(-), ), the trace of the inner product between two matrices A, B as (A, B) tr(A B), and the n- dimensional Euclidean space as Rmxn G(d) denotes the set of invertible matrices in Igdx
matrices, which suggests an implicit regularization behav- ior. In (Ding et al., 2021), improved results are obtained, again for the symmetric case, by relaxing the conditions imposed on measurement matrices. In (Zhang et al., 2023), with the aim to reduce the negative effect of overparame- terization and ill-conditioning, the authors focused on sym- metric matrices and generalized the preconditioned based approach in the overparameterized setting using updates in the form of (2). Similar to our work, the authors in (Cheng & Zhao, 2024) recently, proposed an overparameterized pre- conditioned approach for asymmetric matrix factorization establishing linear convergence with update in the form of (3). However, unlike our work, they focused on smooth losses, which pose less challenges, and enabled them to use a Polyak-Lojasiewice Lojasiewicz (PL)-type condition for deriving the convergence rate.
2. Related Work
In this section, provide some interesting insights into the connection of our approach with prior research works.
Preconditioned gradient and subgradient methods for low-rank matrix recovery. Preconditioned-base methods have attracted significant interest over the last few years since they allow for establishing rates of convergence that do not depend on the condition number of X.. (Tong al., 2021a; Zhang, 2021; Zhang al., 2023). For thorough review of these methods, we refer the reader to (Chi et al., 2019). Preconditioned methods have been extended to non- smooth problems such as robust low-rank matrix recovery with ( loss. However, they focus on either the known- rank asymmetric regime or assume an unknown-rank with sought symmetric matrix X. Relaxing the symmetric as- sumption on X the more challenging asymmetric one in unknown-rank regimes is the main contribution of our work. Recently, these approaches have been shown to of- fer significant improvements in the low-rank adaptation (LoRA) ) for parameter-efficient fine-tuning foundation mod- els, (Zhang& & Pilanci, 2024). Even though this problem out of the scope of the current paper, extending current approaches, which rely fixed rank, the overparam- eterized preconditioning framework is promising future research direction.
3. Problem Formulation
We focus on the low-rank matrix estimation problem, as- suming that the true rank r is unknown. We denote the ground truth matrix as X., and assume a singular value decomposition
X, = U.E.V.
(4)
where U, xxd contains d 2 left singular vectors, E, E Rddd is diagonal matrix consisting of d singular values of X, presented in non-ascending order. Since rank(X: X.) and d 2 we have o; (X.) 0 for i + L....,d. d.
The low-rank matrix estimation problem w.r.t. the space of X E Raxn defined as
min X X (a)k(X)gd
L(X),
(5)
Overparameterized (robust) low-rank matrix recovery. Recently, several works have focused on robust low-rank matrix recovery in the unknown rank regime. In (Ma & Fattahi, 2021), the authors focus on robust matrix sens- ing and report the convergence of vanilla subgradient algorithm in the overparameterized setting for symmetric
where L(X) is general loss function that is convex w.r.t. X and possibly non-smooth in order to allow the use of robust loss functions such as the & norm.
Here, we solve a problem equivalent to problem (5), defined
3

---

Guarantees of Overparameterized Preconditioned Subgradient Algorithm
over matrix factors L E Rmxd and R E Baxdd
where 7/ is the step size and O (R, and dRL(L, R, denote subgradients of the objective function L R,
min L R
C(LR
(6)
w.r.t L and R. respectively.
Note that the RHS of the above optimization problem corre- sponds to upper bounds of the original objective and leads to quasi-Newton-type updates, (Giampouras et al., 2020). We use Polyak's type step size, and get similar form to the one in (Tong et al., 2021b), i.c.
3.1. Matrix Sensing
Next, we focus on the matrix sensing problem i.e., we as- sume that we have access to observations y = (1i) of a low-rank matrix X, E mRxx, given as
V/2 A (X.) 8/3 isisp:
C(L,R ) C(L,R.)
7/1
(11)
71
where A; is the measurement operator,
where
- (A. P
A (x.)
7t |S R2 R + AT)
A, RRXX" is the i-th measurement matrix, and 's corre- spond to arbitrary and sparse corruptions.
+ +ss L, [L, L \r) 1/
with S, denoting a subgradient of the objective ((X)), i.e.
The observation model above can be written in a more com- pact form as
S. E 0x (X)).
y = A (X.) s.
(8)
The proposed algorithm is given Algorithm 1.
Our goal is to find X. given y and the measurement en- semble A() = (-))-)-- We formulate the problem
Algorithm 1 Overparameterizee Preconditioned Subgradi- ent Algorithm (OPSA)
as
Input: Data (y E RR in the matrix sensing case), d: overestimated rank, ry: stepsize. Initialize Lo and Rg, set 1 0.
min X
A
(9)
where we have used the & norm as the loss term I(-), also known as the residual sum of absolute errors, which is known be robust the presence of arbitrary sparse cor- ruptions (Candès et al., 2011).
3: while Stop Condition do
4: L = L. - S.R. (R₃ Rs + AI) R4+1 = Rr n. S, L, (L, L, + x1)
1-1+1
Recall that we assume we do not know the true rank of the unknown matrix X., and we also solve the problem in the space of matrix factors L E IR xd and R E Rnxd whose product equals X i.e., X = LRT with d being an overestimate of r. We thus formulate matrix sensing as
end while
8: Output: x= L.R.
Remark 4.1. In practice, if R., is unknown, e.g., due to noise or additional regularization terms, Polyak's 's type step size may be hard to apply. To address that, one can use geometrically decaying step size schedule to match the expected linear convergence. Such step size schedule was introduced in (Goffin, 1977) and has been widely used in the literature subgradient methods.
min Le Re ReRoxd
Iy A (LRT) Ih--
(10)
4. Overparameterized Preconditioned Subgradient Algorithm
To minimize the objective function given in (6), we quasi-Newton type updates. Hence, use local upper-bounds of the objective function, which lead to preconditioned-type updates for the matrix factors L and R, ie.,
5. Convergence Analysis
In this section, we present the convergence analysis of the proposed Overaparametrized Preconditioned Subgradient Algorithm (OPSA).
(Le,,, R441) = min C(L.RR) (...( ). -- L.)
5.1. Landscape Assumptions
La
(R,CLL, ( -R.))
In the following, we provide the assumptions used in our theoretical results.
(I(L- L.) (R. R - XDI
2m
Assumption 5.1 (Restricted Lipschitz Continuity). A func- tion 2(-) R m + R. is rank-d restricted I.-Lipschitz
+I R.) (L, L. + x

---

Guarantees of Overparameterized Preconditioned Subgradient Algorithm
continuous for some quantity L > 0f
with the Polyak's 's step-size defined in (11), we have
[(X)) - 2(22) S L|| - -X2lFF (12)
0.12
$
10
X +| op
dist Ft, -
x2
20 X
holds for any X1, X2 E mm such that X1 X2 has rank at most 2d.
I., - -x+l1= S (1
0.12
1.5 x 10 | |X 11p
Assumption 5.2 (Restricted Sharpness), A function L()): Rmxn + R is rank-d restricted u-sharp w.r.t. X, for some
20 X
1 Of
Proof. The rate can be derived from its general form (see (16)) by setting À _xx. x = c X olop- 20. The detailed proof is deferred to supplementary material.
((X) - [(X.) 2 u|| X
1I
(13)
holds for any X RRxx with rank at most d.
Remark 5.5. Our derived rate of convergence requires a good initialization that will satisfy condition (15). In prac- tice, this condition can be satisfied by using truncated spectral method in (Zhang al., 2016). It should be also noted that, even though the rate is independent of the condition number of X., the initialization condition is nega- tively affected as this condition number increases, requiring initializations closer to X..
5.2. Main Results
L. R.
Let F. =
E: R(m+t)xxd where L. = U,E. R. =
L
V,E, and F
E pimtt)xdd
R
In our results, propose modified version of the distance metric introduced in (Tong et al., 2021b), defined as
Technical innovation. It should be noted that the deriva- tion of the convergence rate in the overpararameterized and asymmetric case that we focus on, requires a novel defini- tion of the distance metric given in (23). Namely, previous convergence metrics dealing with the imbalance issue that shows up in the asymmetric low-rank matrix estimation problems, cannot be applied in the overparameterizeed set- ting due to overparameterizztion and non-invertibility of E. In order to prove the contraction of this convergence metric we derive novel and non-trivial perturbation- bounds of matrix norms, which pose their own challenges and move beyond existing approaches that address either the known-rank or unknown-rank and symmetric matrices regime (see Table I).
dist? d F.) = inf QEG(d)
ILQ L,)(E, + 12
+ ||(RQQ ST - (E, + &
Matrix Q is known as the alignment matrix and has long been used in similar distance metrics, (Tong et al., 2021
Lemma 5.3. The proposed distance metric is upper bound of the distance |LR - X.Ylr. Namely, assuming that dist F, F.) S Xe, it holds
|RR -X,1I= S (1+5) (2dist(F,FF. F.).
(14)
Note also that the derived rate of convergence is valid in the overparameterizee rank setting where d 2 and the value of À should be positive i.e., x > O. The positive value of X is required so that the matrix Σ. + A/ that is used in the convergence metric is always invertible. When d = r the rate of OPSA can take the same form as the one of the scaled subgradient method of (Tong et al., 2021b), that is derived in the known rank regime. Namely, when d then Σ, is invertible and À could be O. To make the theorem applicable for d = r, we could replace the À parameter appearing in (15), with X' = A + (X.))) .) In that case, when > r, we have X' = x since (x(X.) = O. But when d = r, X' = o, (X.) (since À = 0).and the initialization condition and rate of convergence (see supplementary material) boils down to a similar form, up to some constants, the one in (Tong et al., 2021b).
Proof: The proof is deferred to supplementary material.
We next provide our main result, which relies on the assump- tion that the Lipschitz continuity and restricted sharpness condition are satisfied and ensure exact convergence.
Theorem 5.4 (Convergence of OPSA). Let L(X)
mm + R be convex w.r. X, and assume that it satisfies
the rank-d restricted L-Lipschitz continuity assumption and the d restricted p-sharpness condition, defined above. Let also X= = 1 and without loss of generality or (X.) 1.
Let 6 10 20
and
11
10-1
X,
Fist
(15)
X
20
Remark 5.6. As is shown in Theorem 5.4, the rate is in- dependent of the condition number of X,. The linear rate provided in Theorem 5.4 a simplified form of the general
where x= L, Then for the Overparameterized Precondi- tioned Subgradient Algorithm (OPSA) given in Algorithm 1,
5

---

Guarantees of Overparamcterized Preconditioned Subgradient Algorithm
expression:
x x10
(( =1
1
V2 -1
12-1 1
|AA())
(1
1+2A 22- (1- VelVE+ v
2x
1 2X
+2 1- Velve+ + v2X4) ))
vā(vē+ v2xt) v
2xv2
100
200
300
400
500
(16)
Trials
Note that this general form holds for any value of À 2 O, and its detailed derivation can be found in the supplementary material (Theorem A.3.1).
Figure I. Values of IA(X) for Gaussian map A : 500x 500
|X
R5000 where rank( X) = 10. Each point represents one result 500 random trials. Bluc and red dash lines the lower and upper uniform bounds, respectively.
Remark 5.7. The level of overparameterization influences the rate of convergence through Specifically, depends on the landscape properties of the objective as expressed by the Lipschitcz constant and the restricted sharpness increases with (L 1 4) making the rate of convergence slower. This effect of the overestimated rank d on the rate of convergence is demonstrated in the numerical experiments section (see Figure 2).
5.3.2. ROBUST MATRIX SENSING
constant μs. Generally speaking, X
Here we consider the presence of outliers. We thus first define the S-outlier type bound condition. The S-outlier bound property has been used in the robust low-rank matrix recovery problem in prior works, e.g., (Tong et al., 2021b), It actually encodes a property of that allows restricted sharp- ness condition to be satisfied in matrix sensing problems in the presence of outliers. A detailed derivation of this condition, as a natural generalization of RIP can be found in (Charisopoulos et al., 2021).
5.3. Iteration Complexity for Matrix Sensing
In this section, we analyze the iteration complexity, i.e., the number of iterates T required to reach RT X. 1| < namely (-accuracy. This study will focus on the matrix sensing problem.
Definition 5.11 (S-outlier Type Bound). The linear map A(.) satisfies the rank-2d S-outlier type bound w.r.t. set with a constant 8 if for all matrices X e mxx of rank most 2d we have
5.3.1. NOISELESS MATRIX SENSING
Herein, focus the noiseless case without the presence of outliers, where it holds that y = A (X.).
8 S 1.As (x) 11 IIAs (x) 111,
(18)
Definition 5.8 (Mixed-norm RIP). Let 2d >> 0 denote the rank of and A(-) a linear map. We define the dza- Sza- as the lower and upper uniform bounds, respectively, of the quantity
where As (A: (X)s
(X)(E) and As (X)
X for all matrices X of rank at most 2d.
Proposition 5.12 (Matrix Sensing with Outliers). Let A (.) the rank-2d mixed-norm RIP with (5%a- 8ta) and the S- outlier bound property defined above with 8 Then L(X) satisfies the rank-d restricted I-Lippsciizz continuity and p-sharpness with
IX FF
The mixed-nome norm RIP is empirically verified for the Gaussian linear map in Figure
Proposition 5.9 (Lipschitz Continuity and Restricted Sharp- ness-No Outliers). A(-) satisfies the mixed-norm property with constants ozd oz then L(X)- lyy - A (X) || satis-
fies the rank-d restricted L-Lipschitz continuity and rank-d restricted sharpness with constants,
L 8zd and / = 5".
(19)
Proof: The Lipschitz constant can be derived following similar steps as in the noiseless case. For the restricted sharpness constant μ we use Proposition 2 of (Tong et al., 2021b).
L =ō and
f 8 Ezd
(17)
Proof: Similar to Proposition (Tong et al., 2021b).
Corollary 5.10 (Iteration Complexity Outliers). Using the same setting as in Theorem 5.4, we use the Lipschitz con-
Corollary 5.13 (Iteration Complexity with Oudiers), Under the same setting as in Theorem 5.4, and by using the Lipschitz constant and restricted sharpness constant of Propositions 5.12, we get iteration complexity for matrix sensing, in the presence of outliers, is O
stant and restricted sharpness constant of Proposition 5.9, we get iteration complexity for noiseless matrix sensing is
o ((
2
1og(t))
6
log(
6

---

Guarantees of Overparameteriize Preconditioned Subgradient Algorithm
5, = 20
5, 20
100
10
OPSA 1.0r
ScaledSM 1.0r
OPSA = 1.4r
ScaledSM 1.4r
OPSA d = 1.8r
ScaledSM d = 1.8r
Relative arror
2
OPSA 2.2r
Relative emro
10
ScaledSM d = 2.2r
OPSA 2.6r
ScaledSM d 2.67
10"4
10*
1
10
500
1000
1500
2000
500
1000
1500
2000
lteration count
Iteration count
Figure Performance comparison between OPSA (top) and ScaledSM (bottom) with different overparameteriiztion where P, X, outlier 100, 5, 20, 2, 10%.
10, 20
10, 20
100
10
OPSA 1.0r
ScaledSM 1.0r
OPSA 1.4r
SealedSM d 1,rr
OPSA 1.8r
SealedSM d 1.8r
Relative error
2
OPSA 2.2r
Relative error
1
ScaledSM d 2.2r
OPSA 2.6r
ScaledSM 2.6r
10
10
10
10
500
1000
1500
2000
1000
1500
2000
lteration count
Iteration count
Figure 3. Performance comparison between OPSA (top) and ScaledSM (bottom) with diffcrent overparamettrizztion where
T, A, outlier 100, 10, 20, 2, 10%.
It should be noted that Corollary 5.13 implies that in the presence of outliers, the iteration complexity increases at an amount depending on the properties of the measurement matrices (through )²))
iterations assuming that it is initialized appropriately (see statement of Theorem 5.4).
6. Numerical Experiments
Remark 5.14. Assuming measurement operator Ax(X) (A,, X), where A; has Gaussian i.i.d. entries (0,, 1). we can invoke the results of (Charisopoulos et al., 2021; Tong et al., 2021b), which show that A(-) satisfies the mixed-RIP and and S-outlier bound conditions with
In this section, we verify the empirical performance the proposed overparameterized Preconditioned Subgradient Algorithm (OPSA), i.e., Algorithm 1.
Experimental setup. The ground truth X, is generated as product of two x random matrices, and then the condition number is adjusted to be k by altering the singular values of X.. The observations of matrix sensing are obtained as described in (8), that
5z > 1,
8 2d
S
8u 1 2p..
where pa E [0, 1) is the fraction of outliers, as long as
ス (m n)d
(1 2p.) log
y; A, (X.)+8)
1 1 P.
2p.
where the sensing operator A((X.) = ( X.) and A, is Gaussian random matrix. The corruption vec- tor s E R contains randomly positioned outliers whose values are drawn uniformly at random from the interval Through this section,
Hence, under the same setting as in Theorem 5.4 OPSA converges linearly to e-accuracy in
o
log 1 è 11 (1-2p.)2
1
[- [xx)ll
7

---

Guarantees of Overparameterized Preconditioned Subgradient Algorithm
5, = 10
r= 10, 20
100
10
OPSA 6 20
OPSA 20
OPSA K = 40
OPSA = 40
-OPSA & 60
OPSA = 60
Relative error
1
OPSA & 80
Relative error
10
OPSA 80
OPSA 100
OPSA 100
10
10:10
15
10
0
500
1000
1500
2000
2500
0
500
1000
1500
2000
2500
Iteration count
Iteration count
Figure OPSA performance with different condition numbers N, where n, A, outlier 100, 2, 10%.
Top: r, = 5, 10. Bottom:
d 10, 20.
5, d= 10
10,d 20
10
109
OPSA 10
OPSA 10
OPSA À = 10
OPSA À = 10-1
OPSA À 1
OPSA À
Relative error
10.5
OPSA 2
Relative error
10
OPSA À
OPSA 10
OPSA
10
10-10
10
10115
2000
4000
6000
8000
10000
12000
2000
4000
6000
8000
10000
12000
Iteration count
Iteration count
Figure 5. OPSA performance with different X, where n, K, outlier = 100, 20, 10%. Top: r, d = 5, 10. Bottom: r, = 10, 20.
m = Snr measurements are used in all tests. The code of ScaledSM is obtained from the authors' website. For the sake of fairness, Polyak's stepsizes are used for all tested algorithms, thus S requires extra parameter tun- ing. For OPSA, À is the only parameter to be tuned, and experiment in this section shows that À can be easily tuned in wide favorable range. All the tests are conducted with Matlab 2024a on a mobile workstation equipped with an Intel 19- 1295HXX CPU and 64GB of RAM. The Matlab implementation for the proposed OPSA is available online https::////// //ggggttbbb/ com//
slower convergence. However, OPSA constantly achieves linear convergence while ScaledSM fails to converge when major overparameterization happens.
Performance with different condition numbers k. In this experiment, we test the convergence performance of OPSA with different condition numbers of X.. The results with conditional numbers up to 100 are reported in Figure 4. One can observe that the convergence behavior and final accu- racy OPSA are not distinctly affected by larger condition numbers, even when the rank heavily overestimated. This observation matches ure 7, conduct additional experiments for OPSA with extremely large condition numbers up to 10, 000. The results are consistence with Figure 4. Even with 1, 000 or x = 10, 000. OPSA still delivers stable convergence and achieves the same final accuracy.
www./o///ccceeeeeeeeoeeeeeeee/ee cae cawsarcai/OPSS. SA.
main theoretical result. In Fig-
Performance with different overparameterizationss d. We compare the convergence performance of OPSA against ScaledSM (Tong et al., 2021b), the state-of-the-art subgra- dient method for robust matrix sensing, with different levels of overparameterization d. The convergence evaluated with respect to the relative error |,, X-||// X. l| The comparison results with true rank r 5 and 10 reported in Figures 2 and 3, respectively. For both algo- rithms, one can see that more overparameterizztion leads to
|
Performance with different parameters X. Notice that is the only parameter to be tuned in OPSA. In Figure 5, we test the convergence performance of OPSA with different A. One can observe that a mild À value (e.g., 0.1, 1, 2) helps
8

---

Guarantees of Overparamcterized Preconditioned Subgradient Algorithm
5,
10
r= 10, 20
10
10
OPSA 1% outliers
OPSA 1% outliers
OPSA 5% outliers
OPSA 5% outliers
OPSA 10% outliers
OPSA 10% outliers
Relative error
1
OPSA 15% outliers
Relative error
10
OPSA 15% outliers
10
10-10
10
15
10:15
500
1000
1500
2000
500
1000
1500
2000
Iteration count
Iteration count
Figure 6. OPSA performance with different outlier densities, where A 100, 20, 2. Top: d 5, 10. Bottom: r, 10, 20.
r 5, = 10
10, d
100
100
OPSSA 100
OPSA 100
OPSA 1000
OPSA 1000
OPSA & 10000
OPSA x 10000
Relative error
10.5
Relative emror
10
10
10 10
10 15
10
500
1000
1500
2000
500
1000
1500
Iteration count
Iteration count
Figure 7. OPSA performance with different large condition numbers K, where n, A, outlier = 100, 2, 10%. Left: r, 7, = 5, 10. Right: r, d 10, 20.
OPSA maintain steep linear convergence when the rank is heavily overestimated. However, if the À parameter is set too large (e.g.. 10) or too tiny (e.g.. 10- OPSA converges much slower, although still at a linear rate. Overall, OPSA's performance is favorable with a wide range of À values, and thus the parameter tuning is easy for the proposed OPSA.
7. Conclusions
In this paper, we proposed an overparameterized Precondi- tioned Subgradient Algorithm (OPSA) for robust low-rank matrix recovery. Our work goes beyond existing SOTA works by addressing the challenging scenario of robust low- rank matrix recovery in the case of asymmetric matrices of unknown rank using a preconditioned-yype approach. Under certain landscape assumptions i.e., Lipschitz continuity and restricted sharpness conditions, we a) established a linear rate of convergence that independent of the condition number of the unknown matrix, and b) derived the iteration complexity matrix sensing, in the noiseless setting and in the presence of outliers. Numerical results corroborate our theoretical findings for different levels of overparameteriza- tion of the rank, and outliers, and the independence of the rate of convergence on the condition number of the sought matrix.
Performance with difffernnt outlier densities. In Figure 6, OPSA is tested against different outlier densities. OPSA successfully recovers X, and maintains linear convergence in all tests. Note that more iterations are needed, and slightly worse final accuracy can be achieved when more outliers are present. This is as expected since more outliers lead to harder recovery problems.
More numerical results. Additional numerical experiments on partially observed video background subtraction tasks, have been conducte and reported in the supplementary ma- terial.

---

Guarantees of Overparameterized Preconditioned Subgradient Algorithm
Acknowledgements
Cai, H., Kundu, C., Liu, J., and Yin, W. Deeply learned robust matrix completion for large-scale low-rank data recovery. arXiv preprint
H.Q. Cai acknowledges partial support from the National Science Foundation (NSF) through grant DMS- 234-4234449 R. Vidal acknowledges partial support of NSF grants 2212457 and 2031985, and Simons Foundation grant 814201.
2025.
Candes, E. J. and Recht, B. Exact low-rank matrix com- pletion via convex optimization. In 2008 46th Annual Allerton Conference on Communication, Control, and Computing, pp. 806-812. IEEE, 2008
Impact Statement
Candès, E. J., Li, X., Ma, Y., and Wright, J. Robust principal component analysis? Journal of the ACM (JACM), 58(3): 1-37, 2011.
Low-rank matrix recovery has been broadly applied as one of the fundamental techniques data mining and machine learning research. Hence, through its applications, the pro- posed preconditioned subgradient algorithm has potential broader impacts that data mining and machine learning have, as well as their limitations.
Charisopoulos, V., Chen, Y., Davis, D., Díaz, M., Ding, I.., and Drusvyatskiy, D. Low-rank matrix recovery with composite optimization: good conditioning and rapid con- vergence. Foundations of Computational Mathematics, 2 21(6):1505-1593, 2021.
References
Bhatia, R. Matrix analysis, volume 169. Springer Science & Business Media, 2013.
Chen, Y., Jalali, A., Sanghavi, S., and Caramanis, C. Low- rank matrix recovery from errors and erasures. IEEE Transactions on Information Theory, 59(7):4324 4337, 2013.
Birman, M. S., Koplienko, I.. S., and Solomyak, M. Z.. Esti- mates of the spectrum of a difference of fractional powers of selfadjoint operators. Izvestiya Vysshikh Uchebnykh Zavedenti. Matematika, (3):3-10, 1975.
Cheng, C. and Zhao, Z. Accelerating gradient descent for over-parameterized asymmetric low-rank matrix sensing via preconditioning. In IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 7705-7709, 2024.
Cai, H., Cai, J.-F, and Wei, K. Accelerated alternating pro- jections for robust principal component analysis. Journal of Machine Learning Research, 20(1):685-717, 2019.
Chi, Y., Lu, Y. M., and Chen, Nonconvex optimization meets low-rank matrix factorization: An overview. IEEE Transactions Signal Processing, 67(20):5239-557 2019. doi: 10.1 109/TSP.2019.2937725
Cai, H., Cai, J.-F., Wang, T., and Yin, G. Accelerated structured alternating projections for robust spectrally sparse signal recovery. IEEE Transactions on Signal Processing, 69:809-822 821, 2021a.
Davenport, M. A. and Romberg. J. An overview of low- rank matrix recovery from incomplete observations. IEFE Journal of Selected Topics in Signal Processing, 10(4): 608-622, 2016.
Cai, H., Hamm, K., Huang. L., Li, J., and Wang, T. Rapid robust principal component analysis: CUR accelerated inexact low rank estimation. IEEE Signal Processing Letters, 28:1 1216-00,-0000000010001101 2021b.
Ding, L., Jiang, L., Chen, Y., Qu, Q. and Zhu, Z. Rank over- specified robust matrix recovery: Subgradient method and exact recovery. Advances Neural Information Process- ing Systems, 34:26767-26778 2021.
Cai, H., Liu, J., and Yin, W. Learned robust PCA: A scalable deep unfolding approach for high-dimensional outlier detection. In Advances in Neural Information Processing Systems, volume 34, pp. 16977-16989, 2021c.
Giampouras, P., Vidal, R., Rontogiannis, A., and Haeffele, A novel variational form of the schatten-p quasi-norm. Advances in Neural Information Processing Systems, 33: 21453-21466 2020.
Cai, H., Huang, L., Li, P., and Needell, D. Matrix comple- tion with cross-concentrated sampling: Bridging uniform sampling and CUR sampling. IEEE Transactions on Pattern Analysis and Machine Intelligence, 4508):10100- 10113, 2023.
Giampouras, P. V., Rontogiannis, A. A., and Koutroumbas, K. D. Robust pea via alternating iteratively reweighted low-rank matrix factorization. In 2018 25th IEEE In- ternational Conference on Image Processing (ICIP), pp. 3383-3387, 2018. doi: 10. 10.1099/C1P2000888551112
Cai, H., Huang, L., Lu, X., and You, J. Accelcrating ill-conditioned Hankel matrix recovery via structured Newton-like descent. arXiv preprint arXiv:2406.07409 2024.
Goffin, J.L.. On convergence rates of subgradient optimiza- tion methods. Mathematical programming, 13:329-344 -44,, 1977.
10

---

Guarantees of Overparameterized Preconditioned Subgradient Algorithm
Jain, P., Netrapalli, P., and Sanghavi, S. Low-rank matrix completion using alternating minimization. In Proceed- ings of the the forty-fifth annual ACM symposium Theory 2013.
Tong, T., Ma, C., and Chi, Y. Accelerating ill-conditioned low-rank matrix estimation via scaled gradient descent. Journal of Machine Learning Research, 22(150):1-63. 2021a.
of computing, pp.
Kümmerle, C. and Verdun, C. M. A scalable second or- der method for ill-conditioned matrix completion from few samples. In International Conference on Machine Learning, Pp. 5872-5883. PMLR, 2021.
Tong, T., Ma, C., and Chi, Y. Low-rank matrix recovery with scaled subgradient methods: Fast and robust convergence without the condition number. IEEE Transactions on Signal Processing, 69:2396- 2021b.
Li, X., Zhu, Z.,, Man-Cho So, A., and Vidal, R. Noncon- vex robust low-rank matrix recovery. SIAM Journal Optimization, 30(1):660-686, 2020.
Tu, S., Boczar, R., Simchowitz, M., Soltanolkotabi, M., and Recht, B. Low-rank solutions of linear matrix equa- tions via procrustes flow. In International Conference on Machine Learning, pp. 964-973. PMLR, 2016.
Ma, J. and Fattahi, S. Implicit regularization of sub-gradient method in robust matrix recovery: Don't be afraid of outliers. arXiv preprint arXiv:2102.02990 95, 2021.
Wang, X., Zhou, T., Zhu, J., Liu, J., Yuan, K., Yao, T. Yin, W., Jin, R., and Cai, H. S Attention: Improving long se- quence attention with smoothed skeleton sketching. IEEE Journal of Selected Topics in Signal Processing, 18(6): 985-996, 2024.
Netrapalli, P., UN, N., Sanghavi, S., Anandkumar, A., and Jain, P. Non-convex robust pea. Advances in neural information processing systems, 27, 2014.
Nie, F.. Huang, H., and Ding, C. Low-rank matrix recovery via efficient schatten p-norm minimization. In Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 26, pp. 655-661, 2012.
Wei, K., Cai, J.-F, Chan, T. F., and Leung, S. Guarantees of riemannian optimization for low rank matrix recovery. SIAM Journal on Matrix Analysis and Applications, 37 (3)1118-- 2016
Park, D., Kyrillidis, A., Bhojanapalli, S., Caramanis, C.,, and Sanghavi, S. Provable montiro factorization for a class of norm-constrained matrix problems. arXiv preprint wxXiv:6666001314 2016.
Xiong, N., Ding, L., and Du, S. S. How over- parameterization slows down gradient descent in matrix sensing: The curses of symmetry and initialization. arXiv preprint arxiv:2310.01700 2023.
Park, D., Kyrillidis, A., Caramanis, C., and Sanghavi, S. Non-square matrix sensing without spurious local minima via the burer-monteiro approach. In Artificial Intellignnce and Statistics, pp. 65-74, PMLR, 2017.
Xu, X., Shen, Y., Chi, Y., and Ma, C. The power of precon- ditioning in overparameterized low-rank matrix sensing. In International Conference on Machine Learning, pp. 3861 1 136644, PMLR, 2023.
Recht, B., Fazel, M., and Parrilo, P. A. Guaranteed minimum- rank solutions of linear matrix equations via nuclear norm minimization. SIAM review 52(3):471-50, 2010.
Zhang, F. and Pilanci, M. Riemannian preconditioned loRA for fine-tuning foundation models. In Forty-firsi Interna- tional Conference on Machine Learning, 2024.
Zhang, G., Fattahi, S., and Zhang, R. Y. Preconditioned gradient descent for overparameterized nonconvex burer- monteiro factorization with global optimality certification. Journal of Machine Learning Research, 24(163):1-55. 2023.
Smith, C., Cai, H., and Tasissa, A. Riemannian optimization for non-convex euclidean distance geometry with global recovery guarantees. arXiv preprint arXiv:2410.06376, 2024.
Soltanolkotabi, M., Stöger, D.. and Xie, C. Implicit bal- ancing and regularization: Generalization and conver- gence guarantees for overparameterized asymmetric ma- trix sensing. In The Thirty Sixth Annual Conference on Learning Theory, pp. 5140-5142, PMLR, 2023.
Zhang, H., Chi, Y., and Liang, Y. Provable non-convex phase retrieval with outliers: Median truncatedwirtinger flow. In International conference machine learning, pp. 1022-1031. PMLR, 2016.
Stöger, D. and Soltanolkotabi, M. Small random initializa- tion is akin to spectral learning: Optimization and gen- eralization guarantees for overparameterized low-rank matrix reconstruction. Advances in Neural Information Processing Systems, 34:23831 -238443, 2021.
Zhang. J., Zhang, R. Y., and Chiu, H.-M. Fast and accu- rate estimation of low-rank matrices from noisy measure- ments via preconditioned non-convex gradient descent. International Conference on Artificial Intelligence and Statistics, pp. 3772-3780. PMLR, 2024.

---

Guarantees of Overparameterized Preconditioned Subgradient Algorithm
Zhang, R. Y. Sharp global guarantees for nonconvex low- rank matrix recovery in the overparameterized regime. arXiv preprint arXiv:2104. 10790 2021.
12

---

Supplementary Materials for Guarantees of a Preconditioned Subgradient Algorithm for Overparameterized Asymmetric Low-rank Matrix Recovery
A.1. Problem Formulation
We focus on the following low-rank matrix estimation problem
min L(Y, xX)
min L.R.R.' =X
C(Y. LR").
(20)
We assume preconditioned alternating gradient descent algorithm consisting of the following steps:
L++1 = L, - (o R R + XI)
(21)
R = R, (s L (L L + AI) -1
(22)
with S. E 3xl(x,XX,,)) X,).
L, R.
Let X, be the ground truth matrix, F.
(m+))xd where d 2 rank(X.). L, U.E. R. V.E." and
F
R (m++)xx We define the following convergence metric,
R
dist(F,
inf QEG(d)
[ILQQ L.)(E. + +
+ IIQ@IITTTTT R.)(E, + 1
(23)
V
In our analysis we focus on the Polyak's type step size, defined as follows,
C(L,R R.) T/ S. R AI) 2 + ||S L. -1
(24)
Algorithm 1 Overparameterizzd Preconditioned Subgradient Algorithm (OPSA)
I: Input: R", d: overestimated rank, λ > 0: regularization parameter, stepsize.
2: Initialize Lo and Ro, set ( O.
3: while ! .topp Condition do
4: L++1 = L, S, R2 (R. R2 + XI)
5: R441 = Rí ST L, [L, L, X
6:
1=1-1
7: end while
8: Output: X L,R.
13

---

Guarantees of Overparameterized Preconditioned Subgradient Algorithm
A.2. Auxiliary Lemmata
Lemma A.2.1 (Theorem holds,
(Birman et al., 1975); Theorem X.I.1, (Bhatia, 2013)), Let A, B positive definite matrices.
|| - B lop I || - B opp
(25)
Lemma A.2.2. Ler |X Xollop S (X,), then holds |x- X.IIo 2
(v2-1)o,(X.)
dist(F. F.).
(,(x.)+22
Proof: Let us denote Q, as the optimal alignment matrix for (ist(F, F.). We will have,
dist? FF, = ||QQ. - L.)(E. +1) A + IRQQ, T R.)(2 (E, + x1)
=tr((Z, xr) -.)
(.).((((. (LQ+ (., + \))
+tr((E, + +N)= - -R,) (RQ," - R,, + +X1)²}
=tr((LQ. - (LQ. - -I)(E, +XT) + (RQ -..) TRQ, RR,(EE, + AI)}
IILLQ. L.) || I|QQ.'" R. E (I( - L.)Il + (RQ,1 R.)))
By using the definition of the distance and Lemma 11 in (Tong al., 2021a), and Lemma 5.14 in (Tu al., 2016), we have
2A (v2
(F, I
X X.
X - X.
(26)
V2
(X.)
Hence, we have
2A
ox(X.) + 2A
dist dist (F
1| -X
X -xx111.
(27)
V2 12-1-
(V2 - 100-)), (X.)
(V2 - 1)o, (X.)
which leads us inequality
(V2- (X.) (x.) + 2x
| -X-XX1112 1.
dist (F, F.).
(28)
Lemma A.2.3. The proposed distance metric given in (23), is an upper bound of the distance assuming that dist (F, F.) S Xe, it holds
LR - -X, Namely,
LR XxIlr S (1+ - (2 F.).
(29)
Proof: We use the following distance metric,
dist(F, V QEG(d)
inf IILQQ L.)(E. + A + |[RQQT R.)(E, + 11
(30)
and we assume that dist Fr, F.)= S Ae.
By using the following known norm incqualities
|BB| 2 F (B) 2 ||A]ooo,,()) (B),
(31)
can get which implies
[[L I,)(E, + AT) 1 113, + [| R.) + AT) 1)1 1 X2 S X26
(32)
max L,, -TT Iopss || R.)(E, + -1) Sc.
(33)
14

---

Guarantees of Overparameterizee Preconditioned Subgradient Algorithm
Next, we show the relation between
R X.Ila and (F; F.).
|R, x, 10-11==1:0 = |RR x. || = | + L. R + RLF
< R. || + 1 || mll = R | + |
+11 A A1)+ (3, + $ A A (,. + +1) $ (E, + AI) AAIEE
1
(2, E + 21) / ||11 + A
(E. M + A1) /|1 マ I (E, + |Ir|An E )1)- llop
+ 1 L ( - =11) lopl|AR (.. + xr) ||e
1 + マタヒ max A (D. (I.+ + x1) ;) llap: | (E, + A1) lop) (IA (E. (
(1+2) 2dist F.) S (1+ - Vēλe.
where he have used the initialization condition, the fact that
max(|AAR E. + A1) x) lop. 114 (E. + +XD [lopp c
(34)
and the inequality
| (E, + A1) ||5 IAR + * l|5
(35)
< v2v AL (E, 21) || + DR (E. AI) 1|3.
This finishes the proof.
Lemma A.2.4. Let us assume dist(F, (F,F FF) S eλ, where x= |x. [x,lloz 10o
Let or (X.) = 1 and denote A (R. R
X
A1)1/2 - -RR R. + 22) ALL = (L L + 21)1/2 - (L. + 21) then it holds
|| (Σ, + +X) AuLllop S velvE+ v2xt), || (E)+ A op S VelVe+ v2xi).
(36)
Proof: We have
|I(E, A, = - + -
-(LE, L. + (E) ( llpp-
(37)
Let us denote A (L L + XE) + A1) and B= LL.L. +I))EE + +X)- -! From Lemma A.2.1, we have that
||A - llop S ||| A A-B||
Hence,
+1) (1)) -1) +
1lop
<I([L+>\) + +N), +X) - (I
= (L L L- L.) (E, + '1
+ =I1(5"L-
- (L- L.)) (L (.) (E. + +AI) 00
L.)
=I| =
[Σ, ( ( -133
= - (L) L. (L.L.. (L- - L.) L.) [. + XT) - 1|
<
II[( LL)
(L- (L-L.) L.))
(L- - L.) L..) |1 | ( - -
< 1
( [1L + /2 I, 1 - )
1
1
(Ate+ v2 x 1
/2vell X, = Vo(V-+
=
+
15

---

Guarantees of Overparameterized Preconditioned Subgradient Algorithm
From the last inequality, get that,
- A I Velve+ V2A4). E. AT)
(38)
The proof for the term t/| (E. + AI)
Ax op can be derived following similar steps.
Lemma A.2.5. Let L E lRmxd R E Raad and denote A = (R R + XT) - (R. R. + AT) A =
(L L - (I, L. + 12) Assume that max Then holds,
(.. Ilop. |l - R.)(E, - -I) pllppp Sc
I| (R - ( + XI)
1
lap - VElVE+ 22
(39)
([ - (E. (E.+ 17)
1lpp -
1 Velve+ v2Ad)
Proof: We have (R' R R+ A1) (E, (0.+ + - (R
(
Hence,
|| [R - "
(E,+ (
(40)
od (I+ (E, + +X) R
By Weyl's inequality, get
od (E, + (E.++AI) X1) (R (R)++
(E, + \T R.. R. + an)
||E, + +A) - Rl
(41)
2 0d
1 |(E, A R op.
From Lemma A.2.4, have
[[E, + AI) Ax S Ve(VE+ V2X+).
(42)
Hence, we conclude the proof. The proof for (E, + AI Rlopp can be similarly derived.
A.3. Proof of convergence of OPSA
Theorem A.3.1 (Convergence of Overparameterizee Preconditioned Subgradient Algorithm). Let L(X) BRmxn + R be convex w.r. X, and assume that it satisfies the rank-d restricted T.-Lipschitz continuity assumption and the rank-d restricted y-sharpness condition, defined above. Assume also that
dist Fo. F.) de
(43)
and let I.X.llor, (x,)) and x L. Then for the Overparameterizeed Preconditioned Subgradient algorithm given Algorithmm with the Polyak's 's stepsize defined (24), we have,
1/2
1opp
dist F.) S p(x,e,))
(44)
where plx, e, A) is given by
1
V2-1 1
/2 -
V 11+22 21
122--
1
=1
2
2x²
1 21
(1-
VelVe= v2xt))²
VelVE + v2tt) 2
-2
(45)
volVe+ v((Vev22x))
v2xi)
16

---

Guarantees of Overparamcterized Preconditioned Subgradient Algorithm
Proof: We denote L L1Q;; R= R,QU", ,AL L AR R -R, and S = -.
We focus on the contraction of dist F.).
dist? (F++1, S [[ Q: L.)(E. + + + Qi - (..) + +1)
(46)
Let L = L, R= - R and S = S, and first bound the term [1 LL)((E - x as follows,
[[ - L.) 1 - L.) (E. A1) 13
= =IAr (E, + A1) 2n (E, +1) R+ RT)
+ R X1) [, + x1) ||
= | E + X1) # 1/ 2n (S R. R
+ 2 A
1
25, (1) R AI) R R, 2
AALA
O₂
+ (R | R
x1) )
(E, + >1> 1B.
O₂
We focus on bounding the term [02],
(S E. + (R -) R RRT- ARR 2 A
$ || ( +X) ||E
(R
-1 ( + XI) (EE
R. (E, + + 1lop
+ 2 = (E, + +X)= - llop)
1
(47)
where we have used the inequalities ||AB| S || B F and ||A Bllop S || lop + BBlp..
For the first term of (47) we have
= (E (E, 1lop
- (R
(E, ( x1 (
-R. (E, + x 1lop
= [|R(RTR+M] ((RR - (R.
-R. R, + 21) x1) +) (E. +1) (R, + -1 (E, +1,++
- RR (E. + 1lpp
=I|R -RR(RRRR+) R+ (( (R. R. + AT) -) (E. +1)+
R. (E, + AT) 1lap
(E. <I x+) - $100 | R+ (R, R, (R. + 21) x)) + +1)
+ [ R+ - -R. (R. R. + x1) - 11.p.
We now focus on bounding the term ||( ( R R + +
R. + 21) ))) x Let A R -R.
17

---

Guarantees of Overparameterized Preconditioned Subgradient Algorithm
and B R, R. AI. We have
[IA : - B
+ 1lo |(A : - BB B (E, + 21)² 1lop
= =I(BB - - B+ (A (2. + x) 1lop
= =I(B) - -B A B (4 (E, + 2r) 1lop
= =I(I - B A +) (Σ, + 1lop
SIB- $ (B* - At) 11ool (E. + 1lop
VE(VE+ )
(48)
1 velve+ )
where the last inequality follows by using Lemmata A.2.4 and A.2.5.
Next, we bound the term | R R R X1) -R.
R. (R. R. + + : Ilop. We have
[R R + M1) R. R.
R. + +1) - 1lpp
= II(R - R.) RR' T R + AT)
+ R. ( R + 11) - - (R, R. + + +)) 1lop
< [R R.) R R + 2I) -
1lop + RR (R - - R. + +AI) #) 1lop
1lpp+ + |R, (R - -
-R. R. +11) +) 1lop
< IR - R.llopll RR R R+)
Velve+
V2tt) VV(xt)
Set 1- VClV + v2X1)'
(49)
where we have used the inequality | R. llop S ε. Note that this result holds, since we assumed dist(F, F.) S Ae, hence we can show the following,
II(L - L.) + xX
X1) A1)
+ (1
(50)
+ +I[R (ARR-R,), (E, + A1) (E, + ( + + < X26
+ +IILL ([(L-L.)] (() + A1) )(, + +1) + (2, + x1) + + 1) + )X)}))
X262
max (I|L- LLLLoo,lopp || R- R. mlpp) < Vdc
(51)
Combining the above bounds we get
[R R + (1) - 2 R. (E. + - 1lop
cc+2 2 VelVe+ + +V2X!)
(52)
VelVe+ V2X²)
We now focus on bounding Og,
|SR R R R XT) (,, + * 122
< SR (R
1 x (R
R + XI 3 (.. +
Ose
Oas
< |SS (R R R - $12 (1 V2Ntt+)
(53)
18

---

Guarantees of Overparamcterized Preconditioned Subgradient Algorithm
Using the derived inequalities above we have
|1(x++Qq LL) + 1 AT) - AL
1 + (2A
2
3
velve+ + v2XL)
+ 21LiIA1 (E, +XJ² |F
EE+2
2
1-
--Vilve+ v2x+))
1
+1² (1 V[-V )2X+))²
|SR(R R
Following the same steps for bounding the term (Ri+1Q. (E,
+ 11
we have
dist dist"(Fi+1, (F(11
< 1 E, + +X)² $ +| (E, + 11: -2) xx.)
Velve+ + v2At)
(IAL(E) + +\1)* $ ||. + | (Z, + +X) lIF)
+ 17L
E + 2
1 velve+ + v2x:)
+ =1
1
R (IST
L( L L+ A1) + +112
(1 - VclCe )2
3 I dist (F. 2m (É(LART) ((X)) + +27LV2
2 +E+2 2 Velve+ + v2X!)
dist (Fe, F.)
Velve+ + v22x1)
1 + 1 (1- VE-VE(v V2
[S
S L(L L + +1) -
Convergence with Polyak's 's stepsize, We use Polyak's 's stepsize defined as
(., )- - ((X.)
Th ||S(R XT) $ 12 + 1|ST LISTI(LTLL + 2
(54)
Due to convexity of L(X), Lemma A.2.2, and the assumption o, (X.) = 1, we also have,
(S, X x.) 2 - 2(x.)2 X,I 2 m (V2-1) dist F.).
2
We thus get
dist? (ist2(FF+1,,)) S dist? (ist (T).F.))1.
- (2 (1--))1- VelVe+ v2X+)3²
(1-
3 cC2
velvé+ v2Ai) /2xt)
+ +2
dist( dist(F), F.)
1- Ve(E(( v2xi)
((1( (1-Vilei+ velVe+ v2X1))²
1
[22 -2 1 V
< dist? dist? (Fr, F.)
(1
/1+2x 2X
2/2 L 3
+2 Ve(Vé+ v((v+v2XX) v2X1)
)
dist [F, F.).
1 2
1- Ve(ee v2X+)
Using (Tong et al., 2021b, Lemma A.2.2 and Lemma 4), we can lower bound the step size as
V2- 1
1/ 2 /
dist F, F.).
21
1+ 2X
19

---

Guarantees of Overparameterized Preconditioned Subgradient Algorithm
We define x and then get
dist dist² F.)
1
V2 12-1 1
V2 -
1
2x²
1 1+ 21
V 1 21
2
(1- Velve+ v2 ))3
3
VelvE+ + v2x1)
2xv2
dist (Fr;
2
Velve+ v2x²)
We define p(x, C, A) the contraction rate given by,
1
v2
12 -
1 (1- Velve= v2Xt))²
p(x,e,A)=11 1
[ 21
2
2x
1+ 21
3
VēlvE+ + v2tt)
2xv2
+2 2
2
--v[(vE++ ((((V+)22x)
This finishes the proof.
A.3.1. Proof of Theorem 5.4
Theorem 5.4 Let L(X) R + R be convex w.El X, and assume that it satisfies the rank-d restricted T--Lipschitz continuity assumption and the rank-d restricted u-sharpness condition, defined above. Assume also that |lo
À = cl| Xxlopp C 20, and without loss of generality of (X.) Set
10 which implies.
x1
dist Fo, F.) Ac=== 10-4
X op
(55)
X
where x L. Then for the Overparumeterized Preconditioned Subgradient Algorithm (OPSA) given in Algorithm 1, with the Polyak's step-size defined in (24), we have,
"
0.12
$
10
X,
1
F.,
x²
CX
|L, XxI1r < (1
0.12 x2
1.5
10-1
X
op
CX
Proof: By using the general expression for the rate p(x, A) provided in Theorem A.3.1 and for À = 1, and
10-4
||x.
We have,
(1 - p(x, x))x² 2 0.12,
(56)
which leads to the contraction rate showing up in the statement of the Theorem. By applying Lemma A.2.3, show the second inequality.
20

---

Guarantees of Overparameterized Preconditioned Subgradient Algorithm
A.4. More Numerical Experiments
A.4.1. Partially Observed Video Background Subtraction
Video background subtraction with partial observation is one standard benchmark for robust matrix completion. Note that the RIP condition of matrix completion is only defined with the tangent space projection and the incoherence condition. Nevertheless, following the setup as in (Cai et al., 2025), we apply OPSA the partially observed video background subtraction task two real video datasets, namely shoppingmall and restaurant' The visual results reported in Figures 8 and 9, compared against the fully observed RPCA results. Although the rank is overestimated and the observation is partially accessible, OPSA achieves crisp visual results.
Figure Video background subtraction on shoppingmall video. Each row corresponds a frame the video. The first column the original frames. The next two columns are the "groundtruth" foreground and background provided by AccAltProj (Cai et al., 2019), non-convex RPCA algorithm, with rank and full observation. The last two columns are the foreground and background outputted by the proposed OPSA with 5x overestimated rank d 10 and 30% observation.
'The datasets were originally provided by http://percepte wtt.:ii....r...aaaee. http://prrppp.iiiiii..aaaaaeee. htt.staaeee..s////ddddeee//// html; however, it is longer available. The datasets now available at /ctps://hqcat http://tttgg..../////aaas wttpsssteeeeeeettttntttteete respectively.
mat and
21

---

Guarantees of Overparameterized Preconditioned Subgradient Algorithm
Figure 9. Video background subtraction on restaurant video. Each row corresponds to frame in the video. The first column is for the original frames. The next two columns are the "groundtruth" foreground and background provided by AccAltProj (Cai et al., 2019), non-convex RPCA algorithm, with rank and full observation. The last two columns are the foreground and background outputted by the proposed OPSA with 5x overestimated rank d 10 and 30% observation.
22


Reviews:
[{"review_id": "U4BhcZ0szU", "reviewer": "Reviewer_oy8C", "summary": "This paper studies the problem of recovering a low-rank matrix from noisy linear measurements of the matrix (i.e. inner products with the vectorization of the matrix). This paper studies the problem at a particular level of generality:\n- We have adversarial noisy measurements of an ill-conditioned asymmetric matrix and want to recover it by solving a minimizing over all low-rank matrices with respect to a non-smooth loss function.\n\nIf we remove any of these requirements (noisy, ill-conditioned, asymmetric, non-smooth loss), then this problem has been solved by prior work.\n\nThey show that a generalization of prior algorithms succeed in recovering low-rank matrices in this setting with an algorithm that converges exponentially quickly (i.e. has an iteration complexity that's logarithmic in the desired precision).\n\nPaper is mostly theory with some lightweight experiments.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for taking the time to carefully review our paper and for providing such valuable comments and constructive feedback. Below, we present our detailed, point-by-point responses to each of the reviewer’s comments and concerns.\n\n> Claims & Evidence\n\nThank you for your positive words and for finding our theoretical results to be solid. Our  contributions are mainly theoretical, and hence, the experimental part  focused on corroborating the theoretical results. However, the proposed algorithm can also offer significant benefits in addressing real-world problems! Please see further details below on additional experiments conducted on real data.\n\n> Methods & Evaluation Criteria\n\nTo address reviewers’ concerns, we provide additional results on video background subtraction, which is a classic application for robust matrix completion.  We test with two well-known video datasets and compare the performance of the proposed OPSA to a state-of-the-art robust PCA method, which requires exact rank and full observation. The visual results can be found [here](https://ibb.co/5XVfRNQf) and [here](https://ibb.co/hJsTH8qm), showing that OPSA is competitive against the exact-rank robust PCA algorithm, despite that the former is given a rough overestimate of the rank and 30% of the observations.\n\n> Theoretical Claims\n\nThank you for your positive evaluation of our theoretical claims! In fact, Theorem 5.4 shows a linear rate of convergence that is ***independent of the condition number***. However, the **initialisation condition does indeed depend on the condition number (as also noted in Remark 5.6)**. We will further emphasize this point in the revised version of our paper!\n\n> Relation To Broader Scientific Literature\n\nAgain, we would like to thank the reviewer for recognising the novelty of our theoretical contributions.  Our work essentially addresses an open problem in the low-rank matrix factorization literature. As the reviewer recognizes,  theoretical challenges led to non-trivial technical contributions. Our experimental section was designed to corroborate the theoretical results, e.g., showing a linear rate of convergence in the rank overparameterized regime, etc. We understand that this might have caused a misunderstanding as to the practicality of the proposed algorithms. We hope that the additional real-world experiments we provided (please see details above) addressed the reviewer's concerns.\n\n> Other Comments/Suggestions\n\nIn the revised paper, we have fixed typos and provided clarification based on comments/suggestions! Below, we analytically respond to some of the key points raised here:\n\n6 -$\\bar{\\lambda}$ is an auxiliary variable used for the sake of deriving a simple form for the rate of convergence.  $\\bar{\\lambda}$ shows up in the expression we use for $\\lambda$ i.e., $\\lambda =\\frac{\\|X_\\ast\\|_{op}}{c \\bar{\\lambda}}$. This definition of $\\lambda$ ameliorates the derivation of the rate of convergence given in Theorem 5.4.\n\n8 - The reason for normalizing this way is to provide some useful insights into the rate of convergence. As also mentioned above, the rate of convergence does not depend on the condition number, however, the initialization condition does depend on it. \n\n9 - This is $c\\cdot \\chi$, we will add $\\cdot$ to make it clear.\n\n11 - This is the general expression for the rate for any $\\lambda$ for the RHS of $\\mathrm{dist}(\\mathbf{F},\\mathbf{F}_\\ast)$.\n\n> Questions For Authors: - Handling of not knowing the true rank a priori.\n\nIn practical settings a safe overestimate of true rank but not too large $d$  would work! Of course, this initial guess is problem-dependent and requires prior domain knowledge. Note also that OPSA is not too sensitive to the selection of $d$ (please see Fig. 2), allowing for a range $d < 2r$ without paying a significant price, when it comes to the speed of convergence.\n\n> What interesting loss functions fit Assumps 5.1 & 5.2...\n\nConvex losses combined with linear maps that satisfy RIP (e.g., our objective for the matrix sensing problem) would satisfy Assumptions 5.1 and 5.2 for restricted rank but not for non-rank-restricted versions. The reason for that is that RIP properties would normally hold for low-rank $X$.\n\n> What's going on with (15)?... \n\nThis is just an assumption! We have revised the statement to make this clear.\n\n> What does Def 5.11 really try to encode?...\n\nThe S-outlier bound property has been used in the robust low-rank matrix recovery problem in prior works, e.g., (Tong et al, 2021a). It actually encodes a property of $\\mathcal{A}$ that allows restricted sharpness condition to be satisfied in matrix sensing problems in the presence of outliers. We would like to refer the reviewer to a detailed derivation of this condition, as a natural generalization of RIP can be found in [Char21].\n\n [Char21] Charisopoulos, et al. \"Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence.\" Found. of Comput. Math., 2021.", "claims_and_evidence": "The core claims of the paper are convincing at a glance. I have no particular issues with the claims in the paper, but I also didn't invest the time to dig into their theorems.\n\nThe paper seems to argue a simple generalization of prior techniques to get a slightly more general result that previously possible using a very believable algorithm that just sorta seems like the right generalization of prior works.\n\nThe empirics are nice, but not sufficient to make me feel comfortable recommending this algorithm to practitioners. Paper is mostly theory, but that feels mostly solid. Some mild gaps in what they discuss, but nothing severe.\n\nIn short, I'm comfy accepting the paper.", "methods_and_evaluation_criteria": "The paper has an empiric section, but it's somewhat lacking.\n\nThey propose this simple method for low-rank matrix recovery, but only apply it to the simplest toy case where our underlying ground truth matrix is the product of \"two $n \\times r$ random matrices\" [Line 381, left], we make iid Gaussian measurements of our matrix, and the noise is randomly positioned with uniform at random (admittedly very large) values.\n\nThis is a very nice starting point for analyzing an algorithm, the sorta sanity check you want that this method actually works as theorized, but doesn't show that this method works at all for anything more realistic. I would really have wanted to see a real-world matrix that's operated upon. Perhaps a matrix completion or a robust PCA application, as they point out as potential applications in the first paragraph of their introduction [Lines 42-48, left]?\n\nFurther, the authors only use one algorithm as a benchmark, despite the fact that they cite many prior works as algorithms that try to solve low-rank matrix recover (see e.g. table 1 on page 3).\n\nThe empirics are good enough to make me believe that the proposed algorithms has the potential to work, but is not enough to make me believe that the algorithm actually works well.\n\nI'll note that I'm by no means an expert in the space of low-rank matrix recovery, so I'm not sure what the best benchmarks are, but something involving real world matrices should be possible. **I would love to hear if other reviewers have other benchmarks in mind.** Plus, given that they already have some experiments running, conceptually shouldn't be so hard to get running on other real-world matrices.", "theoretical_claims": "I didn't check the details of the proofs at any stage. I just followed the vague intuitions throughout the paper.\n\nNothing here seems like a really bold surprising claim. Their main theoretical result (theorem 5.4) is a pretty reasonable-looking claim, saying that if we start from a good initialization point then their iterative method converges to an extremely good solution. They also say, perhaps a bit too vaguely, that a prior work gives an easy method to produce a good-enough starting point.\n\nI have some minor peeves with the way the paper writes some parts of it's theory (such as sorta obfuscating the fact that theorem 5.4 has a mild dependence on conditioning, which is totally cool and fine, but obfuscated). I exhaust my little peeves in my list of typos and recommended edits. I don't really have concerns about the theoretical correctness broadly though.", "experimental_designs_or_analyses": "N/A (basically, this is the same as \"Methods and Evaluation Criteria\" imo)", "relation_to_broader_scientific_literature": "This is maybe my sticking point for this paper.\n\nThe results seem essentially correct. The experiments seem fine. The improvement over the prior work is that this paper proposes a way to satisfy 4 directions of generality as the same time in low-rank matrix recovery:\n1. (Bounded) Adversarial noise\n2. Asymmetric matrix\n3. Ill-conditioned matrix\n4. Non-smooth loss function\n\nThe proposed algorithm is intuitively very natural following from how the authors describe the prior work. I don't want to undersell the fact that it does require novelty, but isn't like a wild idea or anything either. It's more like figuring out the right way to generalize the prior ideas.\n\nThis makes me think about that annoying word \"marginal\". This work is proposing an algorithm that's theoretically capable in a very general setting, but hasn't been empirically demonstrated to work amazingly on real-world data (it's all very synthetic data). So I can't sell the importance of the paper on it's empirical prowess, it's instead got to mostly rely on its theoretical prowess instead. The generality is nice, but just how big of a deal is it? Not sure, and I think that at the end of the day it does cross the line to being significant enough. But it is a bit of a toss-up to me.", "essential_references_not_discussed": "None in particular.", "other_strengths_and_weaknesses": "The writing in the paper is really nice. Like I'm super enjoying the fact that, as I read the paper, I'll wonder \"oh, but does this require us to know the value of the loss function at the true optima\" and the paper will have a remark saying something like \"in practice, we don't know this value of the loss function at the true optima, so we use XYZ in practice instead and that works great\", and I greatly enjoy this. This pre-empting of the natural questions, and having good answers to these questions, made this paper particularly fun to read.\n\nI will say they dropped the ball a little bit in section 5.4, where they almost entirely lack this flavor text.", "other_comments_or_suggestions": "This is a list of typos and recommended edits. Ignore whatever you want to ignore.\n\n1. [Eqn 5] This general optimization problem is fine, but should it optimize over rank(X) \\leq something?\n2. [Line 172, left] Idk if the language of A as a measurement matrix is standard. If so, ignore more. But if not, then maybe call it a linear map from R^{m by n} to R? Or call it a matrix, but apply A to vec(X*)? Or specify that A_i(X*) = <A_i, X*> via the trace inner product?\n3. [Line 193, right] Remark 4.1 is great, glad it's included!\n4. [Line 258, left] Naively substituting terms in, we're assuming that $\\lambda = \\frac1{20}$.\n5. [Eqn 15] I think this is supposed to be an assumption on the initial iterate F0, not an implication from the definition of $\\varepsilon$? Needs to be rewritten here to clarify this.\n6. [Thm 5.4] What is bar lambda? I see that lambda is the regularization inside the preconditioner, but idk what bar lambda is.\n7. [Thm 5.4] Add a line which says something like \"In particular, $t = O(\\chi^2 \\log(c_\\chi \\sqrt{\\|\\|X_*\\|\\|}))$ iterations sufficed to have ||L_t R_t' - X_*||_F \\leq \\eta dist(F0, F*)\", or whatever the a good final guarantee is.\n8. [Thm 5.4] Why assume WLOG that the r^th singular value is 1? Instead, just write the condition number of X instead of the operator norm. It feels more honest imo, unless there's another reason to normalize this way in the body of the paper.\n9. [Thm 5.4] What is C_\\chi?\n10. [Line 253, right] Is \"liner rate\" a typo?\n11. [Line 255, right] What rate in 5.4 is this? Is this the expresson on the RHS of dist(Ft, F*)? Of ||Lt Rt' - X*||?\n12. [Line 280, left] Wonderful! Chi grows with d! Can we make this more rigorous with a specific example?\n13. [Defintion 5.8] So here, ||X||_F is the L2 norm of vec(X). And A(x) is a vector whos entries are inner products with vec(X). So, ||A(X)||_1 = ||B*vec(X)||_1 for some matrix B that depends on A. Then, we see this mixed-norm RIP property is the exact same as the 2->1 norm of the matrix B [See e.g. \"Estimating the matrix p → q norm\" by Guth et al]. Not sure this is interesting or superbly relevant, but it's an interesting connection to a term in classical numerical linear algebra.\n14. [Fig 1] I think this! Very simple and nice visual! Write out what the blue and red values actually are maybe? Just a ballpark is fine! Or their ratio, for the sake of Prop 5.9!\n15. [Fig 2] Also very nice! Simple clean story about OPSA being slower with overparameterization, but much less vulnerable than ScaledSM!\n16. [Corols 5.10, 5.13] You've overloaded the meaning of $\\varepsilon$ between here and Thm 5.4. I suggest you change $\\varepsilon$ in Thm 5.4 to like $\\Delta$ or $\\eta$ or just something else. Also, you need to acknoledge the (logarithmic) dependence on the quality of the starting iterate via like C_\\chi and \\kappa.\n17. [Section 5.4] Add some words before sending me straight into a definition. For instance, tell me a bit bout the model of noise you use, and if it's inspired by any prior work's formulation. Also, tell me what Definition 5.11 is really trying to encode.\n18. [Figures 2 and 3] These figures seem to have basically the same information, just slightly different input parameters. Replace one of these.", "questions_for_authors": "What's the recommended way to handle not knowing the true rank r a priori? Doubling? There a goodness of fit metric to concern outselves with?\n\nWhat interesting loss functions fit assumptions 5.1 and 5.2, but not the non-rank-restricted versions of these loss functions? I.e. how helpful is it to assume that X1, X2, X are rank <= d?\n\nWhat's going on with Eqn 15? Is this supposed to be a theorem proved about F0, or an assumption on the quality of our first iterate?\n\nRemark 5.6 points out that the condition number does matter for the initial iterate's assumption. This should be acknowledged sooner.\n\nWhat does Defn 5.11 really try to encode? This is a weird expression to read in Equation 17. We compare the L1 to L2 norm as done in Defn 5.8, but there's this splitting of A across S and the complement of S, but the norm is outside of the minus sign. It's all a bit odd at a glance.\n\nLines 370-373 point out that Corol 5.13 shows the rate of convergence depends on properties of the measurement matrix. Why is this mentioned here? Wasn't this also the case in Corol 5.10?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "EQVcY8BLCQ", "reviewer": "Reviewer_Uzmr", "summary": "The paper presents a preconditioned subgradient method for robust low-rank matrix sensing using a Burer-Monteiro factorization, focusing on the case where the rank $r$ of the ground truth signal is not known. The preconditioner used is a straightforward modification of the preconditioner proposed by [Xu et al.](https://arxiv.org/abs/2302.01186) tailored to the asymmetric case. The authors show that the resulting subgradient method, when initialized near the solution set, converges to a global minimizer at a geometric rate independent of the condition number of the unknown signal and present favorable numerical results on synthetic problems.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's time in thoroughly evaluating our paper and for providing insightful comments and feedback. Below, we provide point-by-point responses addressing each of the reviewer’s comments and concerns.\n\n> Claims And Evidence\n\nWe are glad that the reviewer has found our main claim well-supported both theoretically and experimentally!\n\n >> In Remark 5.6,  ...\n\nThank you for this question. Please note that in the statement of Theorem 5.4 we say that $\\sigma_r(X_*)=1$, hence the condition number $\\kappa(X_\\ast)$ is equal to the spectral norm of $X_\\ast$  i.e., $\\kappa(X_\\ast) = \\frac{\\sigma_1(X_\\ast)}{\\sigma_r(X_\\ast)} = \\sigma_1(X_\\ast) = ||X_\\ast||_{op}$. \n\n>> The sentence in Line 434 ... \n\nThank you for bringing up this point! Indeed, the wording in the paper “***OPSA may get stuck at some local minimum\"***  is not accurate and we have revised it. You are right to say that a large $\\lambda$ will relax the initialization condition, but slow down convergence. We verified this claim in the additional experiments we conducted, which are included in the revised paper. As observed in the updated figures, which can be found [here](https://ibb.co/G32nRDnY) and [here](https://ibb.co/KJhrpYS), OPSA still converges linearly for a higher value of $\\lambda=10$ but now much slower than in the case of lower values of $\\lambda$, requiring $\\approx$ 10000 iterations to converge.\n\n>Methods And Evaluation Criteria\n\nTo strengthen the experimental section, we provide additional experiments on robust matrix completion on real datasets, which can be found [here](https://ibb.co/5XVfRNQf) and [here](https://ibb.co/hJsTH8qm). The results showcase the merits of our approach in this real-world application and have been included in the revised version of our paper. Please see also our [responses](https://openreview.net/forum?id=GaCo82yC7z&noteId=2UnKEoGVze) to Reviewer oy8C.\n\n> Theoretical Claims\n\nThank you for your time to review our proofs and for finding them reasonable. In the revised version of the paper, we have fixed the listed typos and some others!\n\n> Relation To Broader Scientific Literature\n\nFollowing your suggestion, we have added Cheng&Zhao’s [C&Z] to Table 1. Indeed C&Z's approach addresses the asymmetric and overparameterized setting, however, they focus on smooth losses, unlike our work which addresses non-smooth loss functions. We should also note that C&Z reports linear convergence in function values unlike our work, which relies on a distance metric based on updates of matrix factors. \n\n>> In Table 1, the ScaledGD() method appears misattributed ...\n\n We have fixed that in the revised manuscript.\n\n> Essential References Not Discussed\n\nThat’s correct! We have added the references for these two papers to the revised manuscript.\n\n> Other Strengths And Weaknesses\n\n>>Strengths\n\nThank you for your positive evaluation of our work!\n\n>> Weaknesses\n\n>> Given the discussion under ...\n\nNote that  Tong et al. 2021 does not address the overparameterized rank setting. Our contribution generalizes their approach to include this setting, leading to non-trivial technical insights. Please refer to our [response](https://openreview.net/forum?id=GaCo82yC7z&noteId=2UnKEoGVze) to reviewer oy8C and the next comment for further details.\n\n>> I disagree with the claim ...\n\nThank you for bringing up this point! It is true that  ***the norm induced by the preconditioner evaluated at the optimal solution*** is exactly what we need to use as the distance metric. However, please note that Tong2021 uses non-regularized preconditioners, hence, our distance is a generalization of that one. Moreover, to the best of our knowledge, C&Z shows linear convergence in function values and it is not clear in the paper that the same distance metric as ours is being used at all. Note also that the distance is not the main contribution of the paper, but rather the key point for the technical innovation. In particular, demonstrating linear convergence and contraction for this distance metric is far from a trivial extension of prior work (e.g., Tong, 2021). The bounds and matrix inequalities established in earlier studies cannot be directly applied to this more general, perturbed version of the distance metric.\n\n>> (Relatively minor weakness)\n\nWe have fixed all these issues in the revised manuscript!\n\n> Other Comments Or Suggestions\n>> Sample Complexity Discussion\n\nAssuming a measurement operator with Gaussian i.i.d. $\\mathcal{N}(0,1)$ for the matrix sensing problem we can invoke the result of Tong et al 2021, which gives the following sample complexity bound for the mixed-RIP and $\\mathcal{S}$-outlier bound conditions to hold w.h.p. $p \\gtrsim \\frac{(m+n)d}{(1-2p_s)^2}\\mathrm{log}( \\frac{1}{1-2p_s})$, where $p_s$ is the outlier's ratio. A short discussion on this has been added to the revised paper.", "claims_and_evidence": "The main claim in the paper -- namely, geometric convergence independent of the condition number -- is supported both theoretically and experimentally. I have a few issues and questions related to other claims made in various places in the submission:\n\n- In Remark 5.6, the authors state that \"the initialization condition is negatively affected as this condition number increases\" (ostensibly referring to the condition number of $X_{\\star}$). However the initialization condition only depends on the spectral norm of $X_{\\star}$, which can be kept constant as the condition number increases. Is there a typo in the statement Theorem 5.4? Please clarify.\n\n- The sentence in Line 434 (left column) reads: \"if the $\\lambda$ parameter is set too large, OPSA may get stuck at some local minimum\". I suspect this interpretation of the numerical evidence is wrong -- in particular, Theorem 5.4 imposes an initial condition of $\\mathrm{dist}(F_0, F^{\\star}) \\leq \\lambda \\epsilon$, which is *milder* as $\\lambda$ increases. My understanding, based on Theorem 5.4, is that larger $\\lambda$ simply push the contraction factor $\\rho(\\chi, \\delta, \\epsilon)$ closer to 1 leading to very slow convergence rather than stagnation. Please clarify this point as well.", "methods_and_evaluation_criteria": "The method is evaluated on synthetic problem instances, which is standard in the literature on matrix sensing. Experiments on non-synthetic benchmarks, especially regarding the tuning of the preconditioner's $\\lambda$ parameter, could strengthen the paper but are not necessary.", "theoretical_claims": "I am familiar with the literature on (overparameterized) matrix sensing and the proof outline makes sense to me. However, I only checked the proofs at a high level. I believe the theoretical claims contain some typos, which I will list under the \"Other comments or suggestions\" portion of the review.", "experimental_designs_or_analyses": "No issues with experimental designs or analyses.", "relation_to_broader_scientific_literature": "The authors have done an adequate job positioning the paper within the broader literature on matrix sensing. However:\n\n- The proposed algorithm is essentially the same as the one in [Cheng & Zhao](https://ieeexplore.ieee.org/document/10446187). In particular, both algorithms treat the loss function as the composition of a well-conditioned \"outer\" loss with a poorly-conditioned \"inner mapping\", and apply the exact same preconditioner to the subdifferential/gradient of the \"outer\" loss. This work is cited in the paper but omitted from Table 1, while it covers the asymmetric case with unknown rank and the resulting convergence rate is independent of $\\kappa(X_{\\star})$.\n\n- In Table 1, the ScaledGD($\\lambda$) method appears misattributed to (Xiong et al. 2023), when (to my knowledge) it was proposed in the work of (Xu et al., 2023).", "essential_references_not_discussed": "Most essential references are already discussed. The idea of RIP under \"$\\mathcal{I}$-outlier bounds\", which appears without attribution, can be attributed to [this paper](https://link.springer.com/article/10.1007/s10208-020-09490-9) as well as [this earlier work](https://arxiv.org/abs/1705.02356).", "other_strengths_and_weaknesses": "Strengths:\n\n- The problem and algorithm are clearly motivated.\n- The numerical experiments cover a variety of regimes (albeit all being synthetic).\n\nWeaknesses:\n\n- Given the discussion under \"Relation To Broader Scientific Literature\", the main contribution of this paper is to cover the $\\ell_1$ loss with outliers given an asymmetric Burer-Monteiro factorization. With appropriate book-keeping (e.g.,, defining the correct distance measure -- see also my next comment below), the \"restricted regularity\" framework followed by the authors is well-tread by analyses (Tong et al., 2021).\n- I disagree with the claim (under \"Technical Innovation\") that the distance metric in (22) is novel. It is already known from the work of (Tong et al. 2021) and (Cheng & Zhao, 2024) that the distance must be measured in the norm induced by the preconditioner (and that, for that purpose, it suffices to use the norm induced by the preconditioner evaluated at the optimal solution - this leads precisely to the norm used in (22)). It is possible that I am missing something here, and I welcome any clarification.\n- (Relatively minor weakness): The paper appears to have been written (or revised) somewhat hastily. There are several typos, unused notation (e.g., the Kronecker product symbol) and passages that can be polished. For example, nothing about the \"low-rank matrix estimation problem\" defined in Eq. (5) suggests that the solution should be low-rank!", "other_comments_or_suggestions": "- Please take care to remove unused notation (e.g., $\\otimes$ and $\\mathrm{vec}$).\n- Please introduce necessary notation as needed. For example $\\Delta_{L}$ and $\\Delta_{R}$ in the appendix are used before they are defined.\n- Possible typos in (2) and (3): it should be $L_t^{\\mathsf{T}} L_t$ instead of $L_t L_t^{\\mathsf{T}}$. Similarly for $R_t$. Moreover, you should be taking the gradient of some loss function which is missing. \n- Possible typo in Corollary 5.10: should the iteration complexity depend on $\\delta_{2d}^+$ rather than $\\delta_{2r}^+$?\n- Possible typo in Proposition 5.12 / Corollary 5.13: should $L$ be $\\delta_{2d}^+$ instead of $\\delta_{2r}^+$?\n- A discussion of the sample complexity of your method, especially in the presence of outliers, would be useful.\n- More broadly: can the dependence be improved from $\\delta_{2d}^+$ to $\\delta_{d+r}^{+}$?", "questions_for_authors": "N/A", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "f17BqRT39w", "reviewer": "Reviewer_oXqM", "summary": "In \"Guarantees of a Preconditioned Subgradient Algorithm for Overaparametrized Asymmetric Low-rank Matrix Recovery\" the authors provide a novel method to solve robust asymmetric and overparametrized matrix sensing problems without the rate scaling with the condition number of the solution matrix. The authors provide numerical and theoretical evidence of the algorithm's performance.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for taking the time to review our paper and the valuable feedback! Next, we provide point-by-point responses to all reviewer’s comments and concerns.\n\n> Other Strengths and Weaknesses\n\n>> No bounds for RIP constants (and consequently restricted smoothness and sharpness) are provided for the Gaussian case. \n\nAssuming a measurement operator with Gaussian i.i.d. $\\frac{1}{p}\\mathcal{N}(0,1)$ for the matrix sensing problem, we can invoke the result of Tong et al 2021, which gives the following bounds for the RIP constants:\n- $\\delta^{-}_{2d} \\gtrsim 1$\n- $\\delta^{+}_{2d} \\lesssim 1$\n- $\\delta_0 \\gtrsim 1 - 2p_s$\n\nas long as  the sample complexity satisfies  $p \\gtrsim \\frac{(m+n)d}{(1-2p_s)^2}\\mathrm{log}( \\frac{1}{1-2p_s})$, where $p_s$ is the outlier's ratio. A short discussion on this has been added to the revised paper.\n\n>> Requires spectral initialization (but this is standard in the robust case)\n\nIndeed! Our work, similarly to other SOTA robust matrix sensing works, e.g. Tong et al 2021, requires spectral initialization. For future work, random initialization is one of the tasks we will try to tackle for robust matrix sensing.\n\n>>  Rate dependence on the restricted condition number of the loss, which may be dimension dependent.\n\nYou are right. The rate of convergence depends on $\\chi$ which is the condition number of the loss. Unfortunately, to the best of our knowledge, this dependence of $\\chi$ is something that all current SOTA works in this area share. We will work on removing this dependence in future works.\n\n>>  Sensitivity to hyperparameter lambda which requires a lot of knowledge to be tuned appropriately.\n\nAs shown in the experimental section, the performance of our algorithms is quite robust to a wide selection of $\\lambda$. For details, we refer the reviewer to Figure 5. Note, however, that a massive $\\lambda$ value may slow down the convergence, as it matches our theory (Please see also our [response](https://openreview.net/forum?id=GaCo82yC7z&noteId=hMHh5h5Ohj) to Reviewer Uzmr on this).\n\n\n> Questions For Authors:\n\n>> Q1) The authors introduced the mixed norm RIP. Can the authors compare their notion of RIP to those existing in the literature? Other notions of RIP have been introduced in the robust setting.\n\nThank you for this question. The mixed-RIP norm has been actually used in prior works e.g. Tong et al 2021. We refer the reviewer to our [response](https://openreview.net/forum?id=GaCo82yC7z&noteId=2UnKEoGVze) to Reviewer oy8C, and [Char21], which shows the analytical derivation of this mixed-RIP condition.  \n\n>> Q2) Is it possible to establish guarantees for the RIP for Gaussian matrices? As is, it is tested empirically. It would be good to know whether the proposed notion of RIP scales with increased d. The provided simulations only provide results for fixed rank 10, while the restricted smoothness and sharpness must hold for matrices of rank d. \n\nWe would like to refer the reviewer to our previous response above on this topic. Indeed, the sample complexity bound now scales linearly with $d$ instead of $r$. Please also note that in the synthetic experiments, the true rank $r$ was always overestimated with $d\\geq r$. Our reported results show linear convergence in the overaparameterized rank regime, validating our theory.", "claims_and_evidence": "Main claim: The proposed algorithm converges linearly when applied to robust and overparametrized matrix sensing problems. Further, the convergence rate is independent of the ground truth matrix condition number. \n\nThe authors establish that the claim is true in theorem 5.4 and provide numerical evidence that even with overparametrization, the convergence rate does not degrade as abruptly as that of existing schemes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I did not check the correctness of the proofs.", "experimental_designs_or_analyses": "Yes, I do not think the experimental design has issues.", "relation_to_broader_scientific_literature": "The authors suitably position their work in the literature.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Weaknesses:\n1) No bounds for RIP constants (and consequently restricted smoothness and sharpness) are provided for the Gaussian case.\n2) Requires spectral initialization (but this is standard in the robust case)\n3) Rate dependence on the restricted condition number of the loss, which may be dimension dependent.\n4) sensitivity to hyperparameter lambda which requires a lot of knowledge to be tuned appropriately.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "Q1) The authors introduced the mixed norm RIP. Can the authors compare their notion of RIP to those existing in the literature? Other notions of RIP have been introduced in the robust setting.\nQ2) Is it possible to establish guarantees for the RIP for Gaussian matrices? As is, it is tested empirically. It would be good to know whether the proposed notion of RIP scales with increased d. The provided simulations only provide results for fixed rank 10, while the restricted smoothness and sharpness must hold for matrices of rank d.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cFehXdD2d6", "reviewer": "Reviewer_SuTj", "summary": "This paper establishes theoretical guarantees for the preconditioned subgradient algorithm in the context of overparameterized low-rank matrix recovery (LRMR), with a particular focus on the non-smooth case. It is rigorously proven that the proposed preconditioned subgradient method achieves linear convergence to the true solution. The paper is well-written, with clear and coherent exposition, and presents compelling results that contribute meaningfully to the field.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their effort to review our paper and for the constructive feedback! We address all reviewers' comments/concerns below.\n\n> Summary: The paper is well-written, with clear and coherent exposition, and presents compelling results that contribute meaningfully to the field.\n\nWe would like to thank the reviewer for recognizing the significance of our contribution and the positive evaluation of our work!\n\n> Claims And Evidence\n>> The authors assert that  ....\n\nFollowing the reviewers’ suggestion we have accordingly updated Figure 4.  The updated Figures can be found [here](https://ibb.co/WpH1yZvq) and [here](https://ibb.co/YBcJSmd4), and show linear convergence to ground truth up to the order of $10^{-13}$ (not exactly zero relative error due to numerical limits and roundoff errors). \n\n\n>> Furthermore, the results in Figure 4 indicate ....\n\nWe have carried out additional experiments considering higher values of condition numbers (i.e., $\\kappa=1000, 10000$). The new empirical results can be found [here](https://ibb.co/rKJhrFn3) and [here](https://ibb.co/svZ9Qnv0), and show that our proposed algorithm still converges linearly even for significantly larger condition numbers and more challenging scenarios. \n\n>Theoretical Claims\n\nWe believe there is a misunderstanding here. As noted in Remark 5.16, the initialization condition does depend on the condition number of $\\kappa(X_\\ast)= || X_\\ast ||_{op}$. \n\nHowever, the **rate of convergence** provided in Theorem 5.4 is\n $1 - \\frac{0.12}{\\chi^2}$  and it is **independent of $\\kappa(X_\\ast)$**. We have further emphasized this distinction in the revised version of our paper.\n\n> Experimental Designs Or Analyses\n\n>> Regarding the experimental results in Figure 5...\n\nPlease see our response above and the updated figures provided in the anonymous links therein.\n\n>> Additionally, the authors state ...\n\nThank you for this comment! Indeed, the statement we made was incorrect and we have accordingly revised it. An extremely large $\\lambda$ will significantly slow down convergence but not lead to local minima if the initialization condition given in Theorem 5.4 is satisfied.\nWe verified this claim in the additional experiments we conducted and have included them in the revised paper. In the updated figures, which can be found [here](https://ibb.co/G32nRDnY) and [here](https://ibb.co/KJhrpYS), we observe that OPSA  converges linearly for a higher value of $\\lambda$ but now much slower, requiring $\\approx 10000$ iterations to converge.\n\n> Other Strengths And Weaknesses\n\n>> The authors claim that the distance metric introduced in Eq. (22) is novel.  \n\nWe would like to point out that the distance metric itself is a key ingredient that led to the technical contributions needed for proving Theorem 5.4. Specifically, this new distance metric renders the previous proof techniques used in Tong et al., 2021a, not applicable in this overparameterized rank setting that we address in this paper. We would like to refer the reviewer to our detailed responses above on a similar concern raised by Reviewers Uzmr and oy8C. \n\n>> The setting of the parameter $\\lambda$ ...\n\nAs reported in our numerical results (see Figure 5), OPSA is emperically robust to a wide selection of $\\lambda$, showcasing good performance and similar iteration complexity for a range of values from $10^{-4}$ to $2$. Theoretically speaking, from our existing theoretical results, we can easily derive a lower bound for $\\lambda$, i.e., $\\lambda \\geq c$ with $c$ being some universal positive constant. On the other hand, an extremely large $\\lambda$ will empirically and theoretically slow down the convergence, as we have discussed above, also see the updated figures ( [here](https://ibb.co/G32nRDnY) and [here](https://ibb.co/KJhrpYS)) and Theorem 5.4. By setting a desired convergence rate, an upper bound of $\\lambda$ can also be computed, which resembles the bound in Xu et al, 2023. That said, to choose a mild $\\lambda$ that works with OPSA is not difficult in many cases. We have added a short discussion on this in the revised version of the paper. \n\n>> In the References ...\n\nThank you for pointing this out! We have fixed this issue in the revised version of our paper.", "claims_and_evidence": "The authors assert that the convergence rate of the proposed preconditioned subgradient method is independent of the condition number of the target matrix, as stated in Theorem 5.4. However, the experimental results presented in Figure 4 are insufficient to fully validate this claim. Specifically, the relative error in Figure 4 reaches magnitudes as small as 1e-6, which is still too large to conclusively demonstrate the entire convergence process. To strengthen their argument, the authors are encouraged to provide additional experimental evidence showing the relative error at a much finer precision, such as $10^{-14}$, to ensure the robustness of their convergence analysis.\n\nFurthermore, the results in Figure 4 indicate differences in convergence rates across varying condition numbers $\\kappa$, where $\\kappa$ is set to relatively small values (20, 40, 60, 80, 100). To more rigorously test the independence of the convergence rate from the condition number, the authors should consider conducting experiments with significantly larger values of $\\kappa$, such as $10^3$, $10^4$, and beyond. This would provide a more comprehensive evaluation of the method's performance under a wider range of conditions and strengthen the empirical support for their theoretical claims.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "The authors claim that the convergence rate of OPSA is independent of the condition number of the target matrix $X_*$. However, in Theorem 5.4, they assume that $\\sigma_r(X_*)=1$, which implies that ${\\kappa} (X_*)={||X||}$ (the operator norm of matrix $X_*$). This assumption suggests that the convergence results are inherently tied to $||X_*||$, creating an apparent contradiction with the claim of condition number independence. Specifically, if the convergence rate depends on $||X_*||$, it indirectly depends on the condition number $\\kappa(X_*) $, given the assumption $\\sigma_r(X_*)=1$. This discrepancy warrants further clarification from the authors to reconcile the theoretical claims with the assumptions made in the analysis.", "experimental_designs_or_analyses": "Regarding the experimental results in Figure 5, similar to Figure 4, the relative error is only shown up to a precision of 1e-6. To strengthen their argument, the authors are encouraged to provide additional experimental evidence demonstrating the relative error at a much finer precision, such as $10^{-14}$. This would offer more robust support for the claimed convergence properties of the algorithm.\n\nAdditionally, the authors state in line 435 that with a large value of $\\lambda$, OPSA may become trapped in a local minimum. However, this conclusion lacks theoretical solidity. Specifically, for this non-convex optimization problem, if local minima exist, it remains unclear how a gradient/subgradient-based algorithm like OPSA can escape these local minima and converge to the global solution. As observed in Figure 4, the results for $\\lambda=10$ show that OPSA has not yet converged, even after the presented number of iterations. To provide a more comprehensive understanding, the authors should extend the iteration count to at least $10^4$ and present the corresponding results. This would help clarify whether OPSA can eventually escape local minima and achieve global convergence under varying conditions.", "relation_to_broader_scientific_literature": "The key contributions are closely related to the broder scientific literature.", "essential_references_not_discussed": "Not available", "other_strengths_and_weaknesses": "1. The authors claim that the distance metric introduced in Eq. (22) is novel. However, to the best of my knowledge, this appears to be only an incremental improvement over the distance metric proposed by Tong et al., 2021a. While the modification may offer certain advantages, it does not constitute a fundamentally new contribution.\n\n2. The setting of the parameter $\\lambda$ is crucial to the effectiveness of the proposed method. In similar works, such as Zhang et al., 2023a and Xu et al., 2023, the authors provide thorough discussions on the selection and impact of $\\lambda$. In contrast, this paper lacks sufficient theoretical or empirical discussion on the choice of $\\lambda$, offering only marginal experimental insights. A more detailed analysis of how $\\lambda$ influences the algorithm's performance, along with a broader range of experiments, would significantly strengthen the work.\n\n3. In the References section, the entries for Zhang et al., 2023a and Zhang et al., 2023b appear to be identical, which seems to be an error. The authors should carefully review and correct this duplication to ensure the accuracy and integrity of the references.", "other_comments_or_suggestions": "Not available", "questions_for_authors": "Please refer to the above comments.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposes an Overparameterized Preconditioned Subgradient Algorithm (OPSA) for recovering low-rank asymmetric matrices under gross corruption, with theoretical guarantees of linear convergence independent of the matrix’s rank and condition number. The paper makes meaningful theoretical contributions and extends existing techniques to a more general, previously unresolved setting: overparameterized, asymmetric, ill-conditioned, and robust matrix sensing with non-smooth loss. 

The primary theoretical result (Theorem 5.4) establishes linear convergence for OPSA with a convergence rate that is independent of the condition number. Reviewers Uzmr and oXqM recognized this as a substantial and nontrivial advance, especially in the overparameterized asymmetric setting. On the other hand, Reviewers uniformly noted that the original empirical section was too limited, relying solely on synthetic data and offering limited comparative analysis. The authors partially addressed this by adding experiments on real datasets (robust matrix completion) and analyzing convergence behavior under larger condition numbers and lower relative error tolerances. However, Reviewer oy8C still sees room for a more systematic comparison (e.g., error vs. time plots) to further validate OPSA’s practical performance.

Based on the reviews and the authors' thorough rebuttal, I recommend acceptance, as the contribution is theoretically solid and the paper has been improved substantially through the rebuttal process.
Decision: Accept (poster)