Robust Matrix Sensing in the Semi-Random Model
Authors: Xing Gao
Yu Cheng
Venue: NeurIPS 2023 poster (2023)
Keywords: Matrix sensing
Optimization
Low-rank matrix recovery
Semi-random
Adversarial input
Robustness
TL;DR: We apply a more robust framework known as the semi-random model to the popular machine learning problem of matrix sensing, and provide a descent-style algorithm that iteratively reweights the input to recover the ground-truth matrix.

Abstract: Low-rank matrix recovery is a fundamental problem in machine learning with numerous applications. In practice, the problem can be solved by convex optimization namely nuclear norm minimization, or by non-convex optimization as it is well-known that for low-rank matrix problems like matrix sensing and matrix completion, all local optima of the natural non-convex objectives are also globally optimal under certain ideal assumptions.

In this paper, we study new approaches for matrix sensing in a semi-random model where an adversary can add any number of arbitrary sensing matrices. More precisely, the problem is to recover a low-rank matrix $X^\star$ from linear measurements $b_i = \langle A_i, X^\star \rangle$, where an unknown subset of the sensing matrices satisfies the Restricted Isometry Property (RIP) and the rest of the $A_i$'s are chosen adversarially.

It is known that in the semi-random model, existing non-convex objectives can have bad local optima. To fix this, we present a descent-style algorithm that provably recovers the ground-truth matrix $X^\star$. For the closely-related problem of semi-random matrix completion, prior work [CG18] showed that all bad local optima can be eliminated by reweighting the input data. However, the analogous approach for matrix sensing requires reweighting a set of matrices to satisfy RIP, which is a condition that is NP-hard to check. Instead, we build on the framework proposed in [KLL$^+$23] for semi-random sparse linear regression, where the algorithm in each iteration reweights the input based on the current solution, and then takes a weighted gradient step that is guaranteed to work well locally. Our analysis crucially exploits the connection between sparsity in vector problems and low-rankness in matrix problems, which may have other applications in obtaining robust algorithms for sparse and low-rank problems.

Robust Matrix Sensing in the Semi-Random Model
Xing Gao University of Illinois at Chicago xgao53Quic.
Yu Cheng Brown University
ju_cheng@broom..dd
Abstract
Low-rank matrix recovery is fundamental problem in machine learning with numerous applications. In practice, the problem can be solved by convex opti- mization namely nuclear norm minimization, by non-convex optimization it is well-known that for low-rank matrix problems like matrix sensing and matrix completion, all local optima of the natural non-convex objectives are also globally optimal under certain ideal assumptions.
In this paper, we relax the assumptions and study new approaches for matrix sensing semi-random model where an adversary can add any number of arbitrary sensing matrices. More precisely, the problem is to recover low-rank matrix X from linear measurements = X",, where an unknown subset the sensing matrices satisfies the Restricted Isometry Property (RIP) and the rest of the A are chosen adversarially.
It is known that in the semi-random model, existing non-convex objectives can have bad local optima. To fix this, we present descent-style algorithm that provably recovers the ground-truth matrix X For the closely-related problem of semi- random matrix completion, prior work [CGT8] showed that all bad local optima can be eliminated by reweighting the input data. However, the analogous approach for matrix sensing requires reweighting a set of matrices to satisfy RIP, which a condition that is NP-hard to check. Instead, we build on the framework proposed [KLL 223 for semi-randon sparse linear regression, where the algorithm in each iteration reweights the input based on the current solution, and then takes weighted gradient step that is guaranteed to work well locally. Our analysis crucially exploits the connection between sparsity in vector problems and low- rankness in matrix problems, which may have other applications obtaining robust algorithms for sparse and low-rank problems.
Introduction
Low-rank matrix recovery is popular inverse problem with many applications in machine learning such as collaborative filtering, image compression, and robust principal component analysis (PCA) [RS05 FCRPOS CLMWII). In this paper, study one of the most basic low-rank matrix recovery problems namely matrix sensing [CRT06] RFPIO]. In the matrix sensing problem, we want to reconstruct low-rank ground-truth matrix X" Rd x from collection of sensing matrices {A:) and the corresponding linear measurements b. = (Ai, X).
For notational convenience, define sensing operator A|:] : di R² such that A[X] with b, (A,, X) for i 1...n The goal is to solve the following rank-constrained optimization problem:
| - bll2 subject to rank(X) <..
min X Xd
As optimizing over low-rank matrices are often computationally hard, one common approach is to replace the non-convex low-rank constraint with its convex-relaxation, which results the following
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

nuclear norm minimization problem [FPPO
min
|| subject to A[X] = bb
(I)
X K42
Another widely-used approach in practice is to consider the unconstrained non-convex factorized parametrization [RFPI0 GIZ17 BNS16::
UER4 (ER4" VER |AUV -
min
(2)
and solve with some form of gradient descent or alternating minimization.
Existing convex and non-convex approaches all rely on certain assumptions. A standard assumption in the literature that the sensing matrices satisfy the Restricted Isometry Property (RIP), which means that the sensing matrices approximately preserve the norm of a low-rank matrix. (Formally, + IIIII S + E X)² & L- |X||
given rank(X) S for some parameters r and L.)
In this paper, we relax the RIP condition on the sensing matrices and study a robust version of the problem, which is often referred to as the semi-random model. More specifically, an adversary "cor- rupts" the input data by providing any number of additional sensing matrices A, that are adversarially chosen, but the corresponding measurements b; = (A;,X* remain consistent with the ground truth matrix X Consequently, only a subtset of the sensing matrices satisfy the RIP condition and the rest of them are arbitrary. This is an intermediate scenario between the average case and the worst case, which arises more frequently in practice.
To the best of our knowledge, we are the first to study the matrix sensing problem in this semi-random model. Formally, we consider the following adversary: suppose that originally there was collection of RIP sensing matrices {A ("good" matrices), then the adversary augmented some arbitrary [A+)i=++1 ("bad" matrices) and then shuffled all the sensing matrices. The algorithm is then given the measurements based on the "good" and "bad" matrices together. The combined sensing matrices are no longer guaranteed to satisfy the RIP condition, but there exists subset (indicated by an X), S L || where w on the original "good" matrices and w = 0 on the "bad" matrices added by the adversary. In general, the subset may be replaced by convex combination and the indicator vector by simplex. Inspired we refer to this condition wRIP
indicator vector w²) that does, i.e.. + ||X S Σi_, W
by the adversary for semi-random vector regression in [KLI+ 23
(weighted RIP) and formally define it in Definition 2.2
Since the wRIP condition is a more general assumption than RIP, existing solutions that rely on RIP might fail under the semi-random model with wRIP condition. As stated in 22LL+ this type of perspective", but affects the
adversary does not break the problem from an "information-theoree problem computationally. In particular, existing non-convex approaches for matrix sensing (e.g.. 2 may get stuck at bad local minima as the RIP condition is necessary for proving landscape results regarding the non-convex objective (see, e.g., the counter- examples provided in [NSI6]. The convex relaxation approach (I) does continue to work in the semi-random model, because the augmented linear measurements are consistent with the ground-trum matrix X which simply provides additional optimization constraints. However, convex approaches are often less desirable in practice and can become computationally prohibitive when d1, d2 > 100 as pointed out in [RFP10]
1.1 Our Contributions
The limitations of existing algorithms motivate us to pose and study the problem of semi-random matrix sensing in this paper. We summarize our main contributions below:
Pose and study matrix sensing in the semi-random model. We introduce the more general wRIP condition on matrix sensing as a relaxation of the typical RIP assumption, and provide a solution that is more robust input contamination. Our work will serve as a starting point for the design of more efficient robust algorithms for matrix sensing, as well as other low-rank matrix problems, in the semi-random model.
Design an efficient robust algorithm for semi-random matrix sensing, Our algorithm is guaranteed to converge to a global optimum which improves on the existing non-convex solution [BNS16] that can get stuck in bad local optima in the semi-random model, while achieving comparable running time as existing convex solution [FPP00] informally stated in Theorem below. A formal statement can be found in Theorem 3.1

---

Adapt reweighting scheme for semi-random matrix sensing. In contrast to the non- non-convex approach that failed and the convex approach that avoided the challenge posed by the adversary altogether, we study new approach that directly targets the semi-random adversary instead. We develop an algorithm using an iterative reweighting approach inspired by [KLL-23]: in each iteration, the algorithm reweights the sensing matrices to combat the effect of the adversary and then takes a weighted gradient step that works well based on the current solution.
Exploit the connection between sparsity and low-rankness. Observing duality between sparse vectors and low-rank matrices, we draw a parallel between linear regression and matrix sensing problems. By exploring the structural similarities and differences between vector and matrix problems, we are able to extend and generalize the work of [KLL on semi-random sparse vector recovery to the higher dimensional problem of semi-random matrix sensing. We emphasize that even though the generalization from vector to matrix problems is natural, the analysis behind the intuition is often nontrivial and involves different mathematical tools.
We state a simplified version of our main algorithmic result assuming Gaussian design. The more general result is stated as Theorem 3.1 in Section 3
Theorem 1.1
Matrix Sensing), Suppose the ground- matrix X E Rd xd2 satisfies rank(X*) S and || S poly(d). Let ,A, be the sensing matrices and let b, = (A,, b X-) be the corresponding measurements. Suppose there exists a (hidden) set of (drr) sensing matrices with i..dd standard Gaussian entries, and the remaining sensing matrices are chosen adversarially, where === max(d1, d2).
There exists an algorithm that can outpul X E Rdiidda such that ||X 1 S e with high probability in time fouuu+trllooo1//// where w < 2.373 is the matrix multiplication exponent.
1.2 Overview of Our Techniques
Since there exists subset (or convex combination in general) of the sensing matrices that satisfy the RIP condition, a natural strategy is to reverse the effect from the adversary by reweighting the sensing matrices so that they satisfy the RIP condition. However, it is NP-hard to verify RIP condition on all low-rank inputs, so it is unclear how to preprocess and "fix" the input in the beginning and then apply existing solutions matrix sensing. Instead, we make a trade-off between the frequency of reweighting and the requirement on the weights by adopting an iterative reweighting approach: in each iteration, we only aim to find set of weights so that the weighted matrices satisfy some desirable properties (not necessarily RIP) with respect to the current estimate X (as opposed to all low-rank matrices).
Inspired by the workflow in 23 our semi-randon matrix sensing algorithm (Algorithm) I repeatedly calls halving algorithm to reduce the error of our estimate arbitrarily small. The halving algorithm (Algorithm 2 contracts the upper bound on || - X*I F. which is the error between our current estimate X and the ground truth X*, each time it run. Inside this algorithm a gradient descent style loop, where in each iteration we try to minimize weighted objective function, which is essentially the weighted fz-norm of A[X,] b (the distance X "measured" by the sensing matrices), where the weights are provided by an oracle implemented in Algorithm 3 The algorithm proceeds by taking a step opposite to the gradient direction, and the step then projected onto a nuclear-norm- norm- bounded ball which is necessary for the weight oracle to continue working in the next step. As we mentioned before, the weights from the oracle need to satisfy some nice properties with respect to the current iteration estimate X,. Ideally, the property should: firstly, ensure the gradient step makes enough progress towards X"; secondly, can be derived from the wRIP condition so that we know such requirement is feasible; and lastly, be easily verifiable as opposed to the NP-hard RIP condition.
With the first requirement in mind, we define the weight oracle as in Definition 2.5 should satisfy two properties, namely the progress and decomposition guarantees, and together they ensure the gradient step makes good enough progress toward X Intuitively speaking, the progress guarantee ensures the gradient step large in the direction parallel to the "actual" deviation X - X* (as opposed to only reducing the "measured" deviation A[X] b) and thus will make significant progress, while the decomposition guarantee ensures the gradient step has small contribution and
The oracle output
'hroougoout the paper, we write Ö(f(n) for ( polylog fn)) and similarly for (2()).
3

---

effect in other directions thus will not cancel the progress after the projection. While the progress guarantee is quantified as an inner product, we introduce a concept called nrom--dccomooiition" (Definition 2.4) to capture the decomposition guarantee, and we will provide more details later. For the second requirement, we can loosely relate the two oracle guarantees to the wRIP condition: the (large) progress guarantee makes use of the lower bound in wRIP condition Zi=1" We (A
X 2 I
- L. We introduce condition called dRIP (decomposable wRIP defined Definition 2.3 to formally capture this relation, and we will show that it follows from the wRIP condition thus we can achieve such an oracle. Lastly, we will show that the oracle properties can be easily verified, meeting our third requirement.
and the (small) decomposition guarantee makes use of the upper bound Σ W (A, P
A formal statement and road map that leads to our main result can be found in Section 3
1.3 Related Work
Matrix sensing (RIP): There are two main types of existing solutions. The convex-relavation formulation of the problem can be posed as a semidefinite program via the standard form primal- dual pair [RFPIO], where the primal problem has a (d1 + d2)² semidefinite constraint and n linear
constraints. State of the art SDP solver [JKI+ 20 requires running time of (Id22.5) where d max d2). The other approach uses non-convex formulation 2 reduce the size of the decision variable from d2 to dr, improving computational efficiency. It IS shown in [NSS66] that there are no spurious local minima given RIP sensing matrices and incoherent linear measurements in the non-convex approach, however, it is no longer applicable in the semi-random model.
Semi-random model: First introduced by [S95], I. the semi-random model has been studied for various graph problems [FK01 [W177 MSIO MMV12]. Previously the work of [[CG88 applied the semi-random model to the matrix completion problem, and recently KLL++3 studied sparse vector recovery in this model.
Semi-random matrix completion: Low-rank matrix problems such as matrix completion and matrix sensing have similar optimization landscapes [GJZ17]. thus development in often lends insight to another. Prior work [CGI8) on the closely-related problem of matrix completion under the semi- random model showed that all bad local optima can be eliminated by reweighting the input data via preprocessing step. It exploits the connection between the observation data matrix and the Laplacian matrix of a complete bipartite graph, and gives a reweighting algorithm to preprocess the data in black-box manner. However, the analogous approach for matrix sensing requires reweighting a set of matrices to satisfy RIP, which is condition that is NP-hard to check, thus is not practical in the matrix sensing problem.
Semi-random vector regression: In order to overcome the barrier of the reweighting or preprocessing approach mentioned earlier, we take inspiration from the work of [KLL++23 on sparse vector recovery under the semi-random model. One of their main contributions is the "short-flat decomposition" which is a property that can be efficiently verified for a given vector (locally), instead of verifying the RIP condition for all sparse vectors (globally). They provide projected gradient descent style algorithm, where the rows of the sensing matrix are reweighted differently in each iteration to ensure "short-flat decomposition" exists for the gradient. We draw parallel between the problem of sparse vector regression and low-rank matrix sensing, and extend their work on linear regression of sparse vectors the more generalized problem of sensing low-rank matrices.
2 Preliminaries
2.1 Notations
Throughout the paper, we denote the ground truth low-rank matrix as X*. We assume X e Rddixd, rank(X*) = r, and d1, d2 have the same order of magnitude. Let max(d1, de).
We write [n] for the set of integers (1,...,n, n). We use A for the nonnegative probability simplex in dimension n,, and R2 for the set of vectors with nonnegative coordinates in RR. For a vector æ, denote its e,, 82, and -noms as || ||,||| and |all respectively, and write the 7th coordinate in as F.. For matrix A, we use |||] ||Al and ||A|]| p for the nuclear, spectral (operator), and
4

---

rank(A') Frobenius norms of A respectively. For matrix A, we use A(a) = www.iinaak(AAaaaa..... 1l - F to denote the best rank-k approximation of A; or equivalently, given the SVD of Ei= o.u;o:" we have AQa) = - " where Ji,..., Fk are the top h singular values of A.
We write tr(A) for the trace of a square matrix A. For matrices B E Rdixds,
xd2, we write (A, B) for their entrywise inner product (A, B) = (A, B) = tr(A B) = EE, Bzr- A symmetric matrix A Rdxd is positive semidefinite (PSD) if and only if = U for some matrix U, and we write A < Bf A and B have the same dimension and B B-Airr positive semidefinite. We write exp (A) as the matrix exponential of A; if A is diagonalizable A = UDU then exp( U exp(D)U
2.2 Definitions
We formally define the matrix sensing operator and observation vector below. Definition 2.1 (Matrix Sensing Operator). Given a collection of sensing matrices A = [AA)]) C Rdixdd Xd2, we define the sensing operator A[-] IRd xd2 - IR" such that A|X] = b where b, = XA for E x22,
In other words, we have := E.= (Ai, X)e; where is the hhh standard basis vector in IR". Throughout the paper, we use either A or {A,).- 1 represent the sensing matrices.
To consistently recover a rank-r matrix in general, the number of measurements n should be at least (d1 + d2 r)r [CPI]] hence we assume n = (b(rr) where ! suppresses log factors. In most matrix sensing literature,
standard to impose the Restricted Isometry Property (RIP) condition on the sensing matrices. The RIP condition states that A[-1 is approximately an isometry on low-rank matrices, which means the fo-m of the observation vector close to the Frobenius norm of X*.
In this paper, we consider a semi-random model and relax the RIP condition as follows: we require that there exist weights {wi ) { (or w' E A so that the weighted sensing matrices { { A, ) satisfy the RIP condition. We call this relaxed assumption the wRIP (weighted RIP) condition.
We formally define RIP and wRIP conditions below.
Definition 2.2 (RIP and wRIP Conditions). We say collection of sensing matrices A= {A4 -= C Rd xd2 satisfies the RIP (Restricted Isometry Property) condition with parameters r, L, and p if the following conditions hold for all X E Edixds with rank(X) S
1. Boundedness: ||A,||2 S Pp
2. Isometry: 1 | 1 < | < L. 1111
Further, we say A= = {A+)= satisfies the wRIP (weighted RIP) condition with parameters r, L, P. if 3w E n such that the following conditions hold for all X gdxdd xd2 with rank(X) S r::
1. Boundedness: ||Asl|2 PP;
2. Isometry: 1. 1|X S E.= W (A,, X)2 < L. |X
Notice that wRIP is a relaxation of the RIP condition, because we can choose w = 1/n for in the standard RIP setting. More importantly. wRIP is strictly weaker. For example, wRIP allows (possibly majority) fraction of the sensing matrices to be chosen adversarially. We want to emphasize that the algorithm does not know w' one of the main challenges of cemi-random matrix sensing is that finding w" seems computationally hard, because it is NP-Hard to check the RIP condition.
For presenting our algorithm and analysis, we introduce variant of the wRIP condition called dRIP (decomposable-wRII)
Definition 2.3 (dRIP Condition). We say collection of sensing matrices A =A,,) C Rdd xd2 satisfies the dRIP (decomposable wRIP) condition if Eoe E A and constants L,, K,r, p 2 such
that for all V e Rd xd2 satisfying ||V|| E [2, 1], [[V],, S 2v/r:
1. Boundedness: ||A.1|2 S P:
2. Isometry: 1 < Σ w/ (A, 2)² <L:
5

---

3. Decomposability: B(L, KVF nomm-decomposition of G* = Σ1= (A V)A, - Di=1 w U;
Definition 2.4 (Norm Decomposition), We say a matrix G has a (CF, (CC,C)))ooone dom-edotmmeoooooiiitiinn ES and E s.t. G = S + E, and | Cr. El1, I C2.
The main difference with wRIP is that dRIP requires the additional "decomposition" property. Observe that G is the (weighted) gradient at the point V. At a high level, we would like to decompose the gradient into two matrices, with small Frobenius norm and the other with small operator norm. Our matrix norm- norm-decomoosition is inspired by the "short-flat-ded -ido-fflatddooooosittiin for vectors in K
In Section 4 we will explain the motivation behind the norm decomposition as well as how to efficiently verify such decompasition exists. We will also show that the dRIP condition is closely related to wRIP (by choosing parameters within a constant factor each other) in Appendix C
A crucial component in our algorithm is a weight oracle that produces nonnegative weight on each sensing matrix (the weights in general different in each iteration), such that the weighted gradient step moves the current solution closer to X The oracle should output weights that satisfy certain properties which we term progress and decomposition guarantees. The purpose of these two guarantees is further explained in the proof of Lemma 4.2 in Appendix A
Definition 2.5 (Weight Oracle). We say algorithm O is (Cprog Cr) if given as input matrices A [A.);= C RRdixda and an vector A[]] IR" where V E RBdixdd, ||V|l E 1 1], and Il. < 2v/rr, the algorithm O(A, u, returns a weight vector 1250 such that the following conditions hold with probability at least 1 6:
Progress guarantee: E wanf 2 Gprn
2. Decomposition guarantee: 3(Cr, GVF
norm-decompositiin of G EE= W;4; A,
Note that the progress guarantee is equivalent to (G, 2 Gprug
Finally we define numerical rank which we use in our analysis. Numerical rank serves as lower bound for the rank of a matrix based on its nuclear norm and Frobenius norm. That is, we always have Rank, (A) S rank(A).
Definition 2.6 (Numerical Rank). The numerical rank of A is Rank, (A)
||I [||]]
Semi-Random Matrix Sensing
In this section, we present our main algorithm (Algorithm [ for semi-random matrix sensing. Algorithm 1 with high probability recovers the ground-truth matrix X to arbitrary accuracy.
Algorithm 1: SemniKandoomMMatiiiSsiinnggiCoi
A,
1: Input: Rg 2 X p. b A[X""]
0,8 E (0,1);
2: Output: Xour s.t. |Xxu 11 Sc.
3: Xo f- 0, T' + log
Re 5, - 4, R
4: for 0 < t < T do
5:
X f- HalveError(XX X,, R, 0, A,,), R+
6: end for
7: Return Xou < Xx:
The performance guarantee and runtime of Algorithm are formally stated in the following theorem.
Theorem 3.1 (Matrix Sensing under wRIP). Suppose the ground-truth matrix X E Rdixd2 satisfies rank(X*) S r and |X* < Ra- Suppose the sensing matrices =A; E RRdiddyp satisfy
(r, L, p) -RIP (as in Definition 2.2 Let b A[X*] IR" be the corresponding measurements.

---

For any e, > 0, Algorithm 1 can output X E Rdixda such that ||X - -x I e with probability
at least 8. Algorithm 1 runs in time O(nd polylog (d) log (+ log [a )rp² L log la where
= max d1, d2) and w 2.373 is the matrix multiplication exponent.
Theorem 1.1 direct corollary of Theorem 3.1 under Gaussian design.
Proof of Theorem 1.7 When there are (ddr)) sensing matrices with i.i.d. standard Gaussian entries, the input sensing matrices satisfy (r, L, p)-wRIP for L = O(1) and Od) with probability least 1 poly[d] This follows from standard proof for RIP and the fact that we can ignore any
sensing matrices with ||A > d/2, We assume that the wRIP condition is satisfied.
By Theorem 3.1 when I. - 0(1), p O(d'/2), Rs poly(d) and d poly(dj Algorithm can
output solution X such that || - 1 S with high probability. The runtime of Algorithm can be simplified to r(nd""*rroo((///))r
We first provide road map for analysis for proving Theorem 3.1
Our main algorithm runs "halving" subroutine for log iterations reduce the error to c. Each call to this subroutine reduces the upper bound on the distance between the current solution and the ground truth X* by half. This halving subroutine runs in time Ond polylog (d) log ( log Ra )+p according Lemmas 4.2 and 4.3
Section 4
we present the halving algorithm (Algorithm 2 depends on a (9(11, O(1))-
oracle, and Lemma 4.1 shows that the oracle guarantees be easily verified. The algorithm's correctness and running time are analyzed in Lemma 4.2 and Lemma 4.3
In Section 5 we present the weight oracle required by the halving algorithm. We first show in Lemma 5.1 that the wRIP condition implies that the sensing matrices satisfy the dRIP condition tailored to the design of the oracle. Then present implementation of the oracle in Algorithm 3 based on the dRIP condition, and analyze its correctness and running time in Lemma 5.3 and
Lemma 5,4
Algorithm for Halving the Error
In this section, we present Algorithm 2 (HalveError). Algorithm 2 takes an estimate Xin with || - X S R and outputs Xour such that | X 11 S R This is the matrix version the
10--x*1aa HalRRaidusSparse [KLL+23] algorithm for vectors.
Algorithm 2: HalveErrorrX,, R, R,O,8,A,))
Input: Rank-r matrix X,, R.d || - 1 R, O is (1, 12T.) -oracle for A with failure probability 5 E (0, 1), linear measurements b 30= =[X]]
2: Output: Xou E Rd xd2 s.t. |Xout - =x < A w.p. 2 1 and rank rr.
3: X, Xin- X {X Rddixda || </ 22 1| 2 T=
4: for < <t<t do
5:
+ 1. (A[x) -b) b);
/* 21 Al - where (ue); 1/2 (A - +/
n
6:
w: O(A, un, +);
7:
G. El_ (w))a(u)::)
8:
O output satisfies the progress and decomposition guarantees on 4 then
9:
X + argmin (X, ;
else
11:
Return Xout + (X))
/* Rank-r approximation of X, +/
end if
13:
end for
Return Xout (XT)

---

A crucial requirement of the algorithm is takes a vector Ue
for A. In each iteration, the oracle i -|X which is the (normalized) "measured deviation" between current estimate X, and X and computes a weight vector wt. The algorithm then tries to minimize the weighted objective function by gradient descent:
X X
Objective: fe(X) 2 i=1
(W
.c.. fe(X)) -2-
Σ (w))((u))
R
X X ) i.c G. VxJ((X)xx,
Gradient: VxJ((X)
(w.)) (A,;
Σ (wi))
R
Ideally in the next iteration, would like to make a step from X, in the opposite direction of the gradient G2 with the goal of minimizing the deviation in the next iteration. However, we cannot take step exactly in the direction of GG, and our movement is constrained within a ball of (nuclear norm) radius /2r R. centered at Xin. namely the region X' {X ||X Xmnll. S v 22rR.. Nuclear norm is used as proxy to control the rank and Frobenius norm of X, simultancously throughout the algorithm: firstly, since ||Xiin X I R. makes sense that in each iteration || Xinl I R as well; secondly, while trying to minimize the difference between X, and X we also want to ensure the rank of X, relatively small, i.e. rank(X; S O(r). To tie things together, we use the following relationship between rank and numerical rank:
1X, Xin 1
rank(X, xmn) Rank, X
|x:
Xmll
Assuming rank(X.) 2 rank(X and || Xmllr R throughout, then rank(Xe) (x.) [x Xu. Roughly speaking, order for rank(X,)) I Or)), necessary that ||X, - Xmnll I O(vrR). ie. X2 is inside some nuclear norm ball X' of radius O(FFR) centered at X We set the radius of X be /2r that X E X, since | X I R, rank(X,.. X*) S 2r therefore ||X -xall= S R. Thus we confine our movement within this nuclear norm ball of radius V2rR centered at Xin throughout the algorithm, and take the rank-r approximation of the last X, to ensure rank (Xo))
2n"
upon the termination of the algorithm.
To analyze the algorithm, first we show how to check whether the weight oracle output satisfies the progress and decomposition guarantees. The progress condition Σ Li win? 2 1 is trivial to verify, and we check whether G is (Cr, decooppoosle using Lemma with details and proof deferred to Appendix A
Lemma 4.1 (Verify Norm Decomposition). Given a matrix G = USVT Ed Ei= dnnno and
C2 > 0, suppose 01 2 2 0k > C2 2 0k+1 2 ad, then for all | S Cz. we have ||G E 2 E
== (a, 2
The following lemmas analyze the algorithm's 's correctness and show that it terminates with the desired distance contraction, as well as its running time. The proof is deferred to Appendix [A]
Lemma 4.2 (Algorithm) 2 HalveError). Given a (1. 12I 12I?2)-raale -oracle for A with failure probability
ò E (0, 1), where A satisfies the dRIP Condition 2.3 and b A[X*), Algorithm 2 succeeds with probability at least 1- - 8.
Lemma 4.3 (Algorithm 2 Running Time), Algorithm 2 with failure probability 5 runs in time O(nd polylog (d) log LA).
The crucial part of Lemma 4.2 shows that if current estimate X, is sufficiently far from X*, i.c. ||X, - x 2 HR, then according to Lemma 5.3 with high probability the weight oracle produces an output satisfying the progress and decomposition guarantees, and each iteration of Algorithm 2 decreases the distance to X by a constant factor: |X - X < (1 3 Xx x=1 thus after sufficient number of iterations the distance to X" will be halved. On the other hand, if the weight oracle fails, with high probability the current estimate X, already sufficiently close X*. thus the algorithm can terminate early.
8

---

Oracle for Reweighting the Input
In this section, we present an algorithm (Algorithm that serves as the weight oracle required by the error-halving algorithm (Algorithm 2). Algorithm B is the matrix version of the StepOracle [KLL*23] algorithm for vectors. We first state that, given proper choices of parameters within a constant factor, the wRIP Condition 2.2 iimpiiss the dRIP Condition 2.3 which is a more suitable property for our oracle implementation. The proof is deferred to Appendix C
Lemma 5.1 (wRIP = dRIP). A satisfies wRIP Condition 2.2 with parameters L', then A satisfies the dRIP Condition 2.3 with parameters L, K, P such that L = G(L'), O(r'), and some constant K 2 1.
Now we are ready present an implementation of the weight oracle in Algorithm 3 based on the dRIP condition. This algorithm takes as inputs the dRIP sensing matrices A and vector u. If an applicable input to the oracle, with high probability the algorithm outputs weight vector w satisfying the progress and decomposition guarantees as in Definition 2.5
First we introduce some potential functions used in the algorithm.
Definition 5.2 (Potential Functions in Algorithm 3). For sensing matrices A {A, |A,) and input E I" to the oracle, we define the following potential functions on weight vector w E R":
Progress potential: + prog(w) Σi= w.u.
Decomposition potential: (w)) = S
(19log (F (FF(G=-s])) -S]) +
1wll
IOLF
where G Σi=1 A; and F(E) tr exp
BT
Overall potential: ((w) = @ (rog( CrDd)(w)
Note that F(E) = E exp
where oz (F) is the jth singular value of E, due to properties
of the exponential of a diagonalizable matrix.
The progress and decomposition potential functions control the progress and decomposition guar- antees respectively, and later we will show that the termination condition implied by the overall potential + 2 O. Consequently, by maximizing the overall potential each round, the algorithm tries make as much progress as possible while ensuring is decomposable.
Algorithm 3: O(A, 6,
1: Input: Sensing operator A satisfying dRIP Condition 2.3
R"
2: Output: w E R" such that the algorithm a (1, 12L oracle as in Definition 2.5 with probability 2 (1 - 6).
3: C' +- 108, μ 4- dCrlogd 17 log N' +- logz J. + 8Ln
4: for < k / N' do
5: wo <- 0;
6:
for 2 N do
7:
if T prog (w,) > then
8:
Return w we:
9:
else
10:
Sample i E [n] uniformly random;
8t argmax (w, + se;):
12:
W++1 -- we + 8
end if
14: end for
end for
16:
Return w + 0:
Lemma 5.3 (Correctness Algorithm 3) Suppose A satisfies dRIP Condition 2.3 and u an appli-
cable input to the weight oracle (that is, A[V] I2" for some V e dddixd satisfying ||V]]

---

[. 1] and ||VI, 2v/r), Then, Algorithm 3 is (1, 12L2)-oracle for A (as in Definition 2.5 with failure probability at most 8.
We prove this lemma in two steps: first we show in Lemma B.1 that the output is valid; then in Lemma B.2 we show that the oracle achieves the success probability. Our weight oracle inspired by the step oracle in [3] It is worth noting that Lemma B.3 key component used in the proof of Lemma B.2, is significantly different in the matrix case compared to the vector case. Lemma [.3 upper bounds the increase in dee each round, which is then used to provide lower bound for the increase in Φ Combining Lemma B.3 with our earlier remark that the algorithm terminates when
+ 0 gives the number of iterations needed terminate with high probability.
The running time of Algorithm is stated in the following lemma, and the proof is deferred to Appendix B
Lemma 5.4 (Algorithm 3 Running Time), Algorithm 3 with failure probability 5 runs in time O(nd polylog log (d) log 3rp²).
6 Conclusion and Future Work
In this paper, we pose and study the matrix sensing problem in natural semi-random model. We relax the standard RIP assumption on the input sensing matrices to a much weaker condition where an unknown subset of the sensing matrices satisfies RIP while the rest are arbitrary.
For this semi-random matrix sensing problem, existing non-convex objectives can have bad local optima. In this work, we employ an iterative reweighting approach using weight oracle to overcome the influence of the semi-random input. Our solution inspired by previous work on semi-random sparse vector recovery, where we exploit the structural similarities between linear regression on sparse vectors and matrix sensing on low-rank matrices.
Looking forward, we believe our approach can serve as a starting point for designing more efficient and robust algorithms for matrix sensing, well as for other low-rank matrix and sparse vector problems in the semi-random model.
Acknowledgement
We thank Rong Ge for helpful discussions. Xing Gao is supported in part by NSF awards ECCS- 221 1023 and SCF-2307106. Yu Cheng is supported in part by NSF Award CCF-2307106.
10

---

References
[BNS16] Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Global optimality of local search for low rank matrix recovery. Advances in Neural Information Processing Systems, 29, 2016.
[BS95] Avrim Blum and Joel Spencer. Coloring random and semi-random k-colorable graphs. Journal of Algorithms, 19(2):204-25) 2344, 1995.
[CG18] Yu Cheng and Rong Ge. Non-convex matrix completion against semi-random adver- sary. In Conference On Leurning Theory, pages 1362-1394, PMLR, 2018.
[CLMW11] Emmanuel Candès, Xiaodong Li, Yi Ma, and John Wright. Robust principal component analysis? Journal of the ACM (JACM), (8(3): 2011.
[CP11] Emmanuel J Candes and Yaniv Plan. Tight oracle inequalities for low-rank matrix recovery from minimal number of noisy random measurements. IEEE Transactions on Information Theory, 57(4):2342-2355) 2011.
[CRT06] Emmanuel J Candes, Justin K Romberg, and Terence Tao. Stable signal recovery from incomplete and inaccurate measurements. Communications on Pure and Applied Mathematics: A Journal Issued by the Courant Institute of Mathematical Sciences, 59(8):1207-1223, 2006.
[DDH07] Demmel, I. Dumitriu, and O. Holtz. Fast linear algebra is stable. Numerische Mathematik, 108(1):59-91, 2007.
[FCRPO8] Maryam Fazel, E Candes, Benjamin Recht, and P Parrilo. Compressed sensing and robust recovery of low rank matrices. In 2008 42nd Asilomar Conference on Signals, Systems and Computers, pages 1043-1047. IEEE, 2008.
[FK01] Uriel Feige and Joe Kilian. Heuristics for semirandom graph problems. Journal of Computer and System Sciences, 63(4))633-677, 2001.
[GJZ17] Rong Ge, Chi Jin, and Yi Zheng. No spurious local minima in nonconvex low rank problems: A unified geometric analysis. In International Conference on Machine Learning, pages 1233-1242. PMLR, 2017.
[J] Haotian Jiang, Tarun Kathuria, Yin Tat Lee, Swati Padmanabhan, and Zhao Song. A faster interior point method for semidefinite programming. In 2020 IEEE 61 annual symposium on foundations of computer science (FOCS), pages 910-91 918.918.111 IEEE, 2020.
[3]]+ Jonathan Kelner, Jerry Li, Allen X Liu, Aaron Sidford, and Kevin Tian. Semi-random sparse recovery in nearly-linear time. In The Thirty Sixth Annual Conference on Learning Theory, pages 23522398... PMLR, 2023.
[MMV12] Konstantin Makarychev, Yury Makarychev, and Aravindan Vijayaraghavan. Approx- imation algorithms for semi-random partitioning problems. In Proceedings of the forty-fourth annual ACM symposium Theory of computing, pages 367-384, 2012.
[MS10] Claire Mathieu and Warren Schudy. Correlation clustering with noisy input. In Proceed- ings of the twenty-first anmual ACM-SIAM symposium on Discrete Algorithms, pages 712-728. SIAM, 2010.
[PW17] Amelia Perry and Alexander S Wein. A semidefinite program for unbalanced multi- section in the stochastic block model. In 2017 International Conference on Sampling Theory and Applications (SampTA), pages 64-67. IEEE, 2017.
[RFP10] Benjamin Recht, Maryam Fazel, and Pablo A Parrilo. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM review 52(3):471-501 2010.
[RS05] Jasson DM Rennie and Nathan Srebro. Fast maximum margin matrix factorization for collaborative prediction. In Proceedings of the 22nd international conference on Machine learning, pages 713-719, 2005.

---

[Tho65] Colin J Thompson. Inequality with applications in statistical mechanics. Journal of Mathematical Physies, 6111):812-1113, 1965.
[Wil14] Virginia Vassilevska Williams. Multiplying matrices (n2. 373) time. preprint, 2014.
12

---

A Omitted Proofs from Section 4
To check whether G (CF, Ceccdooooeo using Lemma we first consider the following construction. Suppose the SVD of G is G = UEV Ei= 0,4;; Let = E Huu.y with
M4 max(o; C22 0) and let E = E (=j iaa' with A, min((s o.)). In other words, suppose
T1 2 20k > C2 2 0k+1... 2 dd- For i < k (i.e., o; > C2), let μı = d; C2 and X = C2;
for i k (i.e., 02 C2), let μ4 and X o. We have G S E with || C2, and
|| = -v E (a; - C2) Then by Lemma 4.1 G is (Cr, C2) -ooo-ddecoooooablle and only
if ||5||p S CF because:
.if || CC,, we have a valid (Cp, demm-oommmeeeeooosstttio for G;
if | Cp. valid (Cp, -orr-ddecoomooiiioon does not exist for G.
Lemma 4.1 (Verify Norm Decomposition). Given matrix G = UEV Σ 2i=1 druiy and
C2 > 0, suppose 0i 2 2 ok > C2 2 0h+l... 2 dd then for all |E|l2 S Cz we have
- E 2 Ei (o; C2)
Proof. Fix any E with ||ار| I C2. Observe that for all 1 S i S k, we have u. Gv; o; and -C2 S un! Ev; S C2. Consequently, for all S k, we have o; C2 and u. (G E)u; 2 C2 >
Let S = G - E. we have
|S |0 SV = E(UTSV)
d
Σ
(U SV) 2 Σ (U (UTSV'
1=1
[=1
k Σ
(w. So.)² > Σ (a: - (o)-02)²
Lemma 4.2 (Algorithm 2 HalveError). Given a (1. -oracle for A with failure probability 8 E 10, where A satisfies the dRIP Condition 2.3 and b = A[X*), Algorithm succeeds with probability least 8.
Proof. We will first show that the distance to X decreases by constant factor after each iteration:
[ - Xx < (1 (1- || |
Consider iteration t in Algorithm
2 X = argmin x xex IX - (X, -I Taking the gradi-
ent of ||XX (X,- nRR, I|? at X X(+1. we get 2[X,-1 -XX, -RRG))]. Since X* e X and Xt+1 is the local minimizer in X:
2(X141 (X, nRG,), X X²) SO.
Rearranging the terms gives
RG, X(+1 - X*) S -2(X++1 X1, X(+1 X*)
To simplify, let D = X,+1 X1, D. X, X', D2+1 X X*. Note that + Dr De1
2nR D.-1) S -2,D, = =(D (D- D141, DD+1) -D, - (De+1, De+1)
= (D,, - (D, - (D141, D++1),
- 2 Rn,,G D(+1) + (D, RG,,G D.) + RG D) (D,D) (3)
Inequality (3) provides lower bound on the distance contraction after each iteration. We break the right-hand side into two parts. The first term RG,, D2) corresponds to the magnitude of the step G2 in the direction D. X₁ XX, which is the progress made by this step. To lower bound it,
13

---

will use the progress guarantee of the (1, 1 -oracle. Recall in = A (A[X,] b) and consider
Vi === = (X; x* 7 Dr so that u, A[v]] Given that the oracle's 's output satisfies the progress guarantee, which states that Σx=1 (w)):(u)3 2 we have:
2rR Di) 2n (Gu, Vi) = Rn
(we) vi) 2n (wr))(u)?? 2 2n
(4)
The remaining term 2g R,, D) + D) might be negative and cancel some of our progress. A natural attempt is to try to bound it using G D) - (D. D) 2 -n R2 Gt). However, the wRIP condition of A does not provide any guarantee on || (In fact, we can derive that ||G]|2 S L from wRIP, but the best motivates the decomposition property in the dRIP Condition 2.3 and in the weight oracle. The idea is that even though we cannot directly bound || the term by decomposing G2 into Frobenius-ne pesenius-norm-bounee bounded matrix Eg, Specifically, we will use the decomposition guarantee of the (1, 1 which states that there exists norm-decomposition of G, St + Et where |S S 121² and || S C.F As our movement confined in X, D = X1+1 - X, is muclear-norm-bounder so the inner product (E,, D) can be bounded by generalized Holder's inequality. Recall 17 28814
hope for is ||G]| rank(G) -| where rank(G) S d.) This
in fact lower bound R(G D) +D, D) matrix St, and an operator-norm-
2n + (D,
= 2n E, D) + 2n) D) + (D,
2 2 || Eg 21 | - - R
2 2nR- 1
2/22 12 144L*
oUF
3
2 n
(5)
Putting inequalities 4 and 5 together:
|D - |D++1 1/= 2 Rn
2 1 2
D = ID < (1- ) -ID,
-1D
2
In the case that the algorithm terminates after T 6 iterations,
1x, 1 ---)"² 2) -1 1 s exp
177
RR S R²
2
16
- S ||ouut - XTIIa || X S 2| - X* r S 7 R.
The last inequality comes from Xour being the best rank-r approximation of Xx.
In the case that the algorithm terminates early at Line 11, we can assume with probability at least
1 T that the weight oracle would have succeeded given applicable input 4,, Then failure to satisfy the progress and decomposition guarantees means that u, is not an applicable input, which means V, does not satisfy the norm constraint in the weight oracle. ||V|l S 2/2r is guaranteed because X, E X, and | = I|, I' is decreasing in each round, so we must have ||Vill < 4. which means |X, X F 1 R. By the same argument as above, ||. X < R..
Finally, by union bound on the failure probability of the weight oracle, the algorithm succeeds with probability at least 1- 8.
Lemma 4.3 (Algorithm 2 Running Time), Algorithm 2 with failure probability 8 runs in time O(n polylog (d) log L4)
Proof. Algorithm 2 has for-loop that's repeated for T' - T times.
Inside the loop, line 5 and 7 takes linear time O(nd)). Computing wy using the oracle (line 6) runs in time Ond polylog (d) log rp²² according to Lemma 5.4 Line 8 through line 12 are all upper
14

---

bounded by time of SVD, which is on the same order of matrix multiplication O DDH07, with current best of (d2-373) [W114]. particular, verifying the oracle guarantees (line 8) can be solved as an eigenvalue problem. Finding X (line 9) is equivalent to projecting X(+1 == X+-nRG,-XX
/2r Rt
onto the unit nuclear norm ball. We first perform SVD on X1 then binary search for the largest truncation from its singular values to reach the nuclear norm sphere in time ((d d), and the entire projection step is dominated by SVD. Finally the output step consists of SVD and matrix multiplication.
The overall running time of the algorithm is dominated by the weight oracle, so the total running time O(nd polylog (d) log r
B Omitted proofs from Section 5
First we state a couple of lower bounds related to the decomposition potential function.
Claim B.1. 2² log[F(E)) 2 μ² log(d) and μ² Log[F(E)]} > |
Proof. For the first lower bound, exp
(E) # > for all j E [d] so F(E)
d
exp
(E)(E)
d.
(E)
|
For the second lower bound, F(E)=
Ej=1 exp
exp
exp
Lemma B.1 (Correctness of Algorithm B)
If Algorithm Algorithmmtermmnnneee Ieerminates from the inner loop, the output satisfies the progress and decomposition guarantees as defined in 2.5
Proof. We start with Wo 0, which means Prrug (wo) O, Pa (wo) log d, and ((wo) 0 - Cry² log d = 1.
At each round, since s; is chosen maximize (ww, + ste;), in particular if we choose st then ((w++1) ((w)). so P(w++1) 2 ((w,) which is non-decreasing. By definition & prug (w,) is also non-decreasing. and increases by at most each round, because
T p suss S 71 IIVII,)2 I 8nrp² S K logd S (w:) may not be monotone, but we have Fac (wx) 2 n²² lo
(w))
Suppose the algorithm terminates at round t during one of the inner loops, which means prog(wrr1) (wr-1) < 1 and 1 S Prog (wx) < 2.
Progress guarantee: + pprg( Ei= (we), 2 is satisfied upon termination.
Decomposition guarantee:
((wr) = & prog (wx) - CrDDa(we) 2 (wwo)= = =1,
(1² log - (S)) + ||welli (de(w)) S
$ Ppro (w)) + 1
3
min ||S|| STllerll
S
4CIr
Cr
Cr
min [|5]] L[llwlll
(121og log [F(Gu,- - -S1] - Cr
3
= #11|5 & L |uoll s.t. ||Gu, - $11 $
3
Cr
|wwllli <
3
and
-
|| S 12L
4C
Cr
So there exist guarantee.
||S|| 1 and ||]||, = ||G 8112 < y3 1 which satisfy the decomposition
VCr Byp
Notice that for any round /' (we) 1, we also have (sc(w) < Panny (w (w:) < Cr throughout the algorithm, which a fact we will use later Lemma B.3
C so
Lemma B.2 (Success probability of Algorithm B. Given satisfying dRIP Condition and applicable input u, Algorithm 3 terminates from the inner loop with probability at least 1 - 8.
15

---

Proof. We first show the probability that the algorithm terminates from the inner loop is at least 2
i... Pr[# prog (wr) 2 1 2 1 for some S N.
Notice that ((w;) a proy (w,) (r
= prog z Cr 2 Cr (wp)
1, therefore the algorithm starts with + ((w)) = -1 and will terminate once (ww) 2 0 Also notice that throughout the algorithm ((wr) because 4 Prog (w)) < 2 and Cr de (wrr)
(from proof of
Lemma
To prove by contradiction, assume that pr(g (w+) > 1] < < for all & N, i.e., Pr(continuel > for all rounds. We will lower bound the expected increase in (wrz) each round, and we will show that with sufficiently large N, (wr 2 contradicting ((w,, < 1 for all i N.
Recall that & (w,) = prog (wr))= - Cr (wr), the lower bound for increase in & Prog (wr) is provided by dRIP condition on A and applicable input The upper bound for expected increase in (we(w) is provided by Lemma B33
Given the algorithm continues at round t S N, consider choosing St mwo so that w' = we + twwes then the expected increase in least:
E ((((w++1)) ((w+))
continue]
EE t prog (w++1) $ pruy (w+) CrE (wr+1)) (wee)
2 10 4 prog! (w') ) 4 prog (wo)] - Cr (ww)) ) pdc(1c))
qon ur Cr Cr [B((uc(w'') Dac (wxe))))
2 Ln
Cr
2CLar
2
Given the algorithm stops after round [[ (w:)) stopp 0. Overall:
E(p(w++1) - (ww))) ([ (we+)) - 4 ((w))
continue] Pr[continue]
2Lm Pr[continuc]
By choosing a sufficiently large = SLm:
nN
NN
E [[ 2 (wo) + 2Ln Pr[continue] 2 -
4Lm 2
contradicting (w,) < 1. This means each inner loop of the algorithm will terminate with probability greater than 1. Finally, we boost the success probability to (1 (1-6) using the outer loop with N' logz } iterations.
Lemma B.3 provides a crucial bound used in the proof. Even though achieves similar result as
Lemma 13 KLL 23 on the potential functions defined for vectors, analyzing the potential function defined for matrices involves very different techniques.
Lemma B.3 (Potential Increase Upper Bound), Given w E R" s.t. (dc(w) I 3r by choosing a sufficiently large value for K, for w' w + nwiee ez we have:
Eig(n] Lac (w)))') < (w)) + LCr
The assumption (w) < 3 is justified in the proof of Lemma B.1
Proof. First we introduce some notation:
Denote Φop min Sp wl, (n² log [F(G.. S3] so that Duc(w) d + 40L Let
||ll
G Ei= w uA and by dRIP Condition 2.3 we know 3(L, nom--mmoomooooooooisiii of
G = S* + E*, where || 1r < L and
1 R.T.. Let G = Σ w.uiA and S =
16

---

orgmin&opppe (w) so that D (w)) 1²² log[F(G - S)]. and let E = G - S. Let G' = Ei=1 wfu:A..
Using these notation and Ei=1 i==1 wi = 1:
|
Pap(w") + 1100|1 + my!
E [de
IE
(op(w')
E ie[m]
iE|n]
[E(m]
LC
4C
|
IE (E[N]
o op (w')] +
+
4C
4CLar
|wll We need show (xe[n) (Pa((")) (w)) + zCLnr Pop(1o) JeLr
zeinr equivalently
E|g[n] Pop (w')) S (up(w) + 4CLnr
Consider S' = S+mp? S" We have || $ ||||| + ||5* 1F S [-||w||, - L- 1|
S' is a valid argument for @op(w") |in <T:1w// (1² log [F(G' - -5] therefore (up) S
2² IoG(F((' S-)]- Let E' G' - S G + u. S mw E + Z where 7 muu A, mpo S" Using these and the concavity of the log function, we have
[ig|n| (w')] S
2² log[F(G' -S']=
Σ 2 logg 2
1=1
[(F + 2001)
s n² log
It suffices to show
1² log
1
((E+Z(0))
< Pop(w)
7 LC
n² [og[F(()]]
7 4CL m
Expanding the left hand side:
1² log
F(E 2(0)
n
E E T Z6) + ET z(0) + ZIOT E
,² log
Trexp
n12
E E
Z Z + ET -00 + ( E
S ,² log
exp
exp
71
112
n
E E
n
Z Z + ET Z + 2((TE E
1² log
tr
exp
exp
112
11
112
E E.
n
(ZOT Z(0)
E 7 + ZOOTE) E
S 2 log
tr exp
cxp
122
n
12
( z + E ( Z E
= 2 log [F(E)] + 2 log
exp
n
The first inequality uses Golden Thommponn Inequality (stated as Lemma B.6). and the second inequality follows from Lemma B.4 Finally it suffices to show
Z
2
E. 7 + TOO E
11 log
exp
S
112
4CL nr
2
We will use the approximation exp(X) < 7 7 X X2 for symmetric with
|X], S The
argument in the exponential satisfies this condition justified in Claim B.2
We will also use
17

---

log (1 [1+x)
S vx 2 0.
Z 200)
+ E Z + Z E
n log
exp
112
N
Z 2
E 7 + Z E
S p²² log
cxp
71
112
7 z
E Z
Z E
(ZG) 2
E Z(7 + 2 E.)
S 11² log
+
+
1
14a
Z
Z
E'
Z(4)
+ Z0O
E
S log
||/|/2 +
+
m
1
71
112
2
n (Z() 2(0)
FT 2
2 E)
μCa
i=1
7 2(0)
ET 7(0) + 7 F
S 5221og
|1 +
+
112
122
1=1
2( Z0)
2(E Z (6)
- Z E)
+
44
1=1
1
1(0) z(0)
1
E 2 + -ZAT E
2
+ 2
112
7
112
2
(2()T 2(0
E Z
-O0 E)
2p
2/1
n
4.
2
1
Σ ( z(1)
7
+ 7
+
11
i=1
2 (T) 2(0
2 422
1
E z + ( E)²
+ 422
+
im1
mm1
These four terms bounded by Claims B.3 B.4 B.5 and B.6 respectively, notice that the second term dominates the first and the third, and the forth term dominates the second. So finally we have:
( 2 + 2(0 + ZOTE
2² log
exp
422
1=1
3
2672
VCK
K
nr
97I2 n
K nr
1
with choice of K 388CL3 O(13)
4CL
Lemma B.4. 1f0 & A. then tr(AB) S tr(()) ||B|]2
18

---

Proof. Since 0 x A, A= E, kyuuu with oj 20.
LonunjB _ B) = Σosu
tr(AB) tr
< Σ jj |BB||2
-r((A) |B||
Lemma B.5. (A+ B) ( (A+ B) $ 2A A and [(A+ B) B)]² $ 8(A 8)A
((BB)..
Proof.
2A T A 2B B- - 44
= (A B) (A-
> 0.
[A+ (A B)]² x (2.A A+ + 2B BB²²
< 2 A)]2 + 222 B)}²
x A)) + 8(B +BBBB))
The following claims were used in Lemma
B.3
Recall that A satisfies dRIP Condition 2.3 u
A[]] E R" for some E pdd xd2 satisfying |
E 11 1J, |VI]_ S 2/2r, 2 nw, (u:A;
S*). and (w) I 3 by assumption of Lemma
B.3
We have the following:
Cr
|| l12 S by boundedness property of dRIP Condition 2.3
|4,1 K4,, V < ||4 |V S p2v2r S LVTp assuming 2 S L.
||S*|| 1/ < | |r < | 112 KVr
by decomposition property of dRIP Condition 2.3
3 || op (wr) < (w)) < Cr
by Claim B.T
2 Claim B.2. 2 200 + T ((0) + g g
11
Proof.
1 z(0)
|| = u2 (u,A - ( - -55
s 2n1 2 (u A Aillz + 1|s S²112) (Lemma B.5)
< 2 (2 (T''p' +.²)
I 4 w/ L'TP'
E 2 + = E
$2 $2 E z
22 2(
2m
||4A, - 1-11,
s 2mw
||
([u4) ||lll2 + 11()112)
2
(LVrp² +L)
VCr
Lp²
8mw
VC
19

---

Putting them together:
Z Z (0) + E 7
+ 2 E
1 (1 2 + E z(1) + 2 E (1)2)
< 1
12
I logd - w?? L2rp' + s T,p ve
16VCL
1 K
I 1 with sufficiently large K
Claim B.3. || -
Z
1
S
4La n log
nr
Proof.
n
1
Σ
2
Z(07
Σ
"f w. St) -55
1=1
2
ru; 2 (u |4] Abll2 + 1|st (112))
S 2n Σ nue (w p2 + L2)
20 Krp log d
LLp² + 133
41,2 !
S
log d r
ト Z z(0)
1
Z z(1)
n
2
1
1=1
4L 2
n
S
K log d
nr
Claim B.4. ET E 2(0 + 7 B11, <
4
-.
JCK
Proof.
E. Z + 2 E
E
2
200
T
F.
1=1
1=1
2
E
T
7
72
2
n Σ
|6
71
2
||
IM
5 112
n
2
|| |1112 17 | 11
2
"
S
n
VCr
K
4
VCK nr
Claim B.5. 11 (Z (200 220021 50
2 KerpT
C
20

---

Proof.
Σ
z T 200
5 i=1
1 W
4 (u) [I 1.) + (|(5*T (Lemma B.5
1=1
x 81)
3 2 +2 uip
W/
+ 2
1=1
< 81)
1
Wi
ui
4
+ Σ wi
2 L2a
K3 p log"
iiml
mm1
88)
1
Σ
Wi p²
+ Σ
uz T.?
K3p3 pe log
1
(0' + -
S 8n
K3r2 log d
16L
22 p² log d
00
2 log
2
T 2(0
0o (x3rpp
CL
7
2²
log d
nr
Claim B.6. n²
11 (ET 7 + + E>
961
K
Proof.
T 2 + 2 (T) E)²
<
21
Σ
(E 2 + Z E)
2
12
i=1
1=1
1
4
F.T z z(1) F.
112 n
2
2 1
Σ
4 ||
Z
z
12 n
8
|
1
Σ
1 z
122
71
:=1
3
4L
1
(Claim)
B.3
n22
Cr
K log nr
96L2 "
K nr
Lemma B.6 (Golden-Thomppon Inequality (Tho65)). For two n x n Hermitian matrices A and B: tr (exp(A+ + B)) & tr (exp(A) exp(B))
Lemma 5.4 (Algorithm 3 Running Time). Algorithm with failure probability 5 runs in time O(nd" polylog (d) log }rp²)
Proof. Algorithm has a nested for loop that's repeated for N' N Onglogg log frp²) times. The major step in the loop is line 11: + argmax (ww; + set), which is equivalent to
argmin..ju.nn 2r (w+se))+++ + i sus. Recall that (w)(w) |s] S/ Note that n²² log (F(E) is convex in E.
min
(n²² (nolog log [F(G,, - S)]
where F(E)= = ir exp
ETE n²²
21

---

First we show that (op(w) is convex in w, i... given w1, W2 Pop (w) + w2)) S 2 (Pop(zr)) + 2op(w2)).
Let wy [w) + w2), and G. = Ex= (w,),,; A, for h 1,2.3. Suppose Si, S2 attain the minimum for 4 op (w1), @op(u)) respectively, i... Pop(wi) = log [F(G] - S1]] and & Lop(wz)
n² log [F(G2 S2]].
Let 53 - (S) + S2). Notice that G3 = [ + G2), so G3 - S - (Gi - Si G2 S2).
Since || S (1 [[ - 2 [[[]]il + ||w2ll2) = L ||w/y/1 S3 is a valid argument for
@ (op( therefore:
1 ( : log [F(G] - S1)] μ² log [F(G2 -aal)
Pop(ws) S n² log [F(G3 - Sa)l - 2
u up (w1) + @ap (sp(w))
Line 11 is equivalent to minimizing Cr over bounded interval [0, n), so the minimization needs to evaluate Pop(w + se;) for ((polylog(d) different values of 8. Evaluating Pop is also a minimization which can be solved by computing SVD on G. and evaluating F F(G... 5) in time (dd)) for polylog(d) various constructions of S. Overall finding the optimal value of takes time ((d polylog(d)), and the algorithm's 's total running time O(nd* polylog (d) log frp²).
se;) + 4T. - su,. which is convex in 8 for a fixed w.
C Omitted proofs: From wRIP to dRIP condition
Here we show that the dRIP Condition 2.3 is implied by the wRIP Condition 2.2 given proper choices of parameters within constant factor. Notice that in the wRIP condition, we have low-rank constraint on the input matrix, i... rank(X) S r, and dRIP we have norm constraint instead, i.e., || E [ 1), [IVI, < 2/2r. To make use of the wRIP condition of A, we will decompose V into low-rank matrices, so that wRIP condition applies to each of the low-rank matrices. Though the rank of V is arbitrary, we can still upper bound its numerical rank based on the norm constraint.
Finst we will introduce a low-rank decomposition, and an upper bound the sum of their Frobenius norms. This is the matrix version of the deciiioosidooooiiiiooonnnn in Lemma 15 for vectors in KLL * 23).
Lemma C.1 (Low-rank Decomposition). Given V Rd21x22
x22 with Ranka(V)
I v, and let I I
V= = be its SVD with o; in descending order. Decompose V into sum of rank-r matrices, ie., write V = Etzi y(i) where v(8) = Li=((-1)+1 ouuu, Then we have: Σk= | V
iilr
Proof. Note that (1) is the rank-r approximation of V. and ((0's are constructed using disjoint singular values and vectors in groups of size r, and are orthogonal to each other.
Denote o. (V()) as the 8th largest singular value of (())
vr or (v(t)) S vr. ||
v((+1)
S Vr..o 0o
(vlet.1)
r
Σ 1(0)
S vr 1-1
|r00
s Vr
vi0) ||. = r
VF
1|
2=
IIVI [
b |
Now we are ready to prove Lemma 5.1 which states that wRIP implies dRIP condition. The proof uses similar techniques as in the second part of Lemma 17 [LLL for vector recovery.
Lemma 5.1 (IRIP = dRIP). A satisfies wRIP Condition 2.2 with parameters r', T1, then A satisfies the dRIP Condition 2.3 with parameters T., K,r, p such that I. = (T.'), r A(r'), and some constant K3 > L.
22

---

Proof. Boundedness property is satisfied by assumption || S p iii
Isometry property:
Consider V Rdixda s.t. || E L 4.. IIII. - 2v2r. Need to show J. S Di=wo (A V32 5
L.
Let L. = 25L', K 2 1 and r == 12800 K² 1
" = Rankn - TVI I 128r. By Lemma C.I. decompose V into rank-r' matrices so that we
can apply the (r',L)) L/)-IIP property of A.
k
>
|10 1|- s -
S
1
|
S TO IVIle
1
10LK
10
t=
k
|V
2 || - ||/0|| V -
v
2 +IV F
v
9 2
10
2
2m
Let B, V A..
so that Ei= (A,, V32 = E (B,, v)2 = 12 (Be, Veeile.
Lower bound:
a Σ BB vlyee
k
Σ B, V)e.
Σ
B 1.
Σ
2
2
1=2
2
k
Σ (B,, V(
Σ
(B V(0)e
2-2
Σ
Bi v(Uj2
Σ BR V(0)2
||
Σ
V'- |
V
L
A=2
0.9
0.1
|V
VL
IIVII
VT
L
4.5
0.02 VT.
||
VT.
F
Taking the square: EL= w (Ai, v)2 N 448²
|| 2
1.48 T6L
2 +
Upper bound:
B, Via
(Bi, v())e
BB r(0)e
2
1=1
Σ Bi v(0)++ +
Σ
Bi V(0822
$ VI
|rul||
+ Σ
VD : |||
2
$ VT |I + 0.1VII
IIVII
L
VT.
||V| + 0.02
IIVI..
5
VT.
Taking the square: En U7
< 4.
1I 0.02
-IVI[ +
0.008 < 1 S..
Combining the lower bound and upper bound:
1 x D. wi (Ai, v)2 <L.
23

---

Decomposition property:
Let S (r)), the rank-r' approximation of G = Σ wA V2. Aj. Let E G S. Suffices to
show || S L and || I KVF We have
|| (8 (G,
Σ w (A V)A, Σ
(B. S) Σ (Be, ()
==1
BBs V)e,
Σ
(By: Sleg) S
Σ (Bs, v)e
Σ
(B S)e,
j=1
1=1
Σ (Bg, v)2.
Σ
(B,
Σ
u (A,, v)2. V)2.
Σ
w S),
1=1
i=1
1=1
L 5
VLL VL |S|||
||||
which implies ||||| F S v L, and consequently,
||S|/ 2
L
L
El2, = (G) S (G) or(() S
/
I
S
O
r'
5VP
400 fr K
24


Reviews:
[{"review_id": "m53w31QFV2", "reviewer": "Reviewer_ZDRS", "summary": "The paper introduces a new descent algorithm for low rank matrix recovery in the setting of the semirandom model (where a subset of the measurements satisfy the RIP). The algorithm is based on a research of the best reweighting of the measurements (in order to navigate the non convex landscape) and a minimization of the data fidelity term.  ", "questions": "see above ", "limitations": "NA", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "There is clearly some novelty in the paper. Although as indicated it applies the ideas from Kelner et al 2022. It is sound and well written. ", "weaknesses": "General comments\n\nIt is a good extension of the idea in Kelner et al 2022. The introduction of the algorithm could be improved though. The algorithm is clearly and neatly stated but a clear intuition on the main steps would be a clear addition to the paper. E.x. the relation between the weight oracle and lemma 4.2 is not completely clear. The weight oracle is key and some additional intuition on why it enables a contraction of the distance to the ground truth would be helpful (see detailed comments below). I..e as you indicate, it is hard to reverse the action of the adversary so what makes the algorithm efficient ? I.e. it seems to me you are leveraging the diversity of the measurements to escape local minimas. Why does the weighted objective enable you to escape the local mins introduced by the non RIP part of the matrix? your gradient is a simple LS gradient so the weights are really key. This is my main criticism with the paper. See my comments below on the progress and decomposition guarantees. If I understand well, the weight oracle gives you a sufficiently large “escape” direction. Yet this only does not imply convergence. convergence comes from key lemma 4.2 which if I understand well implies that the existence of such a sufficiently large escape direction will lead to a gradient step that will decrease the distance to the global solution. Unfortunately there is almost no intuition provided for this lemma. \n\nFinally, I think you could better summarize your contribution with one sentence or two of the form “The algorithm relies on a combined optimisation of the weight (in order to escape non convexity) and minimization of the cost function (in order to get closer to the true minimizer)”\nYou don’t have to explicitly use the above but some clear intuition on why the algorithm is working is definitely missing. In particular, you need to provide (some more) intuition on lemma 4.2.\n\n\nDetailed comments\n\npage 2\n - line 33-38, you should directly detail how you generate the non RIP matrices. Also, if your measurements are generated as the union of the RIP and non RIP matrices, then I don’t see why having additional non RIP measurements will be a problem. You just add redundant constraints. If you use a subset of the union then you should say it clearly\n- Is finding a submatrix that satisfies RIP is hard ? if so you should say it as well because otherwise, you could just retrieve the RIP part of the matrix and solve the problem from there.\n\npage 3\n- You should improve the statement of Theorem 1.1. recall the meaning of d, n and omega. Do you have convergence regardless of the number of adversarial measurements? this should also be clarified in the statement\n- Ok so as I indicated above, the first paragraph in section 1.2 (where you explain that it is NP hard to extract a RIP matrix) should appear earlier (or at last you should mention the hardness of the RIP submatrix detection problem in one sentence in the abstract or/and introduction)\n- lines 112 -122, you mention the “progress” and “decomposition” gaurantees. It would help to have a decomposition of the paragraph with two clear items providing a short explanation on each guarantee\n\npage 5\n- When you introduce the distinction between the RIP and dRIP conditions. It is not clear why reweighting the matrices will be useful. Perhaps you could add a sentence explaining why the reweighting is important/how it will affect recovery. \n- Generally speaking it is good to indicate that the isometry condition in the wRIP is a relaxation of the isometry condition in the RIP, it could be good to indicate that the wRIP can be understood as requiring that only a subset of the measurements satisfy the RIP\n\npage 6\n- The halveError subroutine in algorithm 1 should be introduced earlier. In fact I’m not sure Algorihtm 1 is essential here \n- I know you mention it on line 184 but the sample complexity is important for the matrix sensing and completion problem and they should appear in the statement of Theorem 3.1.\n- It is a detail byut the oracle which is named Oracle in Algorithm 3 is named O in Algorithm 2\n- When you introduce the Progress and decomposition guarantees which are key to the algorithm, you indicate that “the purpose of those” will be further discussed in section 4. Yet section 4 barely adds to the definition of the properties, merely indicating that success of the oracle corresponds to satisfaction of the progress guarantee which in turns leads to a reduction of the distance to the groundtruth . We would like more intuition on why the weights make such a difference in the recovery. \n- Generally speaking when you introduce the “progress” and “”decomposition” guarantees, those are equivalent to finding a weight so that there is a large gradient. \n\npage 8\n\n- lines 303 - 306 “which means with high probability the weight oracle produces output satisfying the progress and decomposition guarantees then each iteration decreases the distance” —> Why is that clear ?\n\n\ntypos:\n- page 3: lines 108-109, “Ideally, the property should” —> “Ideally the properties should be (1) … (2)…” \n- page 3 line 109 “ensure the weighted gradient step makes ” —> “ensure that the gradient step …” would be more clear\n- same page, line 109 again: “secondly, can …” —> “secondly ensure that those steps can …”\n- page 8, line 304 “the weight oracle produces output ..” —> “the weight oracle produces an output ..”\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful comments and positive feedback.\n\nRegarding how the non-RIP matrices are generated and why they may cause issues: The non-RIP matrices can be arbitrary. In fact, a computationally-unbounded adversary can generate (any number of) additional sensing matrices $A_i$ after examining the ground-truth matrix, the good (RIP) sensing matrices, and our algorithm. The only constraint is that the corresponding linear measurements $b_i = \\langle A_i, X^\\star \\rangle$ must be accurate where $X^\\top$ is the ground-truth matrix to be recovered. These additional sensing matrices indeed only add redundant constraints for convex approaches (e.g., nuclear norm minimization), but they pose a series risk for non-convex approaches, because they can destroy the *landscape* of many non-convex objectives. More specifically, all local optima are globally optimal with RIP, but now these extra sensing matrices may introduce bad local optima.\n\nRegarding the purpose of the progress and decomposition guarantees (the reviewer’s 4th comments for Page 6): In the proof of Lemma 4.2, we provided more intuition for the progress and decomposition conditions and their role in proving the correctness of Algorithm 2. We apologize for any confusion caused by directing readers to Section 4, as we moved the proof of Lemma 4.2 to Appendix A in this submission. We will fix this.\n\nOn the correctness of Lemma 4.2 (the reviewer’s comments for Page 8): This follows from Lemma 5.3. We will make this clear.\n\nWe appreciate the reviewer providing many detailed suggestions on how we could improve the presentation of our paper:\n\n- Define $d$, $n$, and $\\omega$ in Theorem 1.1, and highlight that the adversary can add any number of arbitrary sensing matrices.\n\n- Add an earlier statement on checking the RIP condition is NP-Hard.\n\n- Provide more intuition on the progress and decomposition guarantees and how they affect the recovery of the ground-truth matrix.\n\n- Emphasize that the wRIP condition is equivalent to requiring only a subset of the sensing matrices satisfying RIP.\n\n- Discuss the sample complexity (i.e., the number of random matrices needed to satisfy RIP with high probability) in or around Theorem 3.1.\n\n- Name the weight oracle consistently in Algorithms 2 and 3.\n\nWe will address all of them.\n\nWe thank the reviewer for pointing out the typos in our paper. We will fix them."}, {"review_id": "w9QTpHpSTD", "reviewer": "Reviewer_PQDV", "summary": "This paper studies the matrix sensing problem in the semi-random model, where a subset of the matrices satisfy an RIP property and the rest are adversarially chosen so as to make the RIP not hold. The algorithm iteratively updates weights on the sensing matrices throughout the iterations to search for the set on which the RIP holds. Through this updating, the approximation error geometrically decreases.", "questions": "- My main question is about how well the algorithm performs in practice. Can the authors give some experiments showing how well it actually runs?\n- What challenges arise in the analysis that did not happen in the case of sparse vectors? What I'm asking is how does the analysis differ from the past work [KLL+22] to make it sufficiently novel/non-incremental, and not just a translation to the matrix recovery setting? \n- The statement of algorithm 1 is not useful - there is only one step within the loop that calls another function, and everything else is just parameter initialization.\n- The work might read better if vectors and matrices are distinguished from parameters somehow (for example, by using bold symbols).\n- Can the authors give more intuition/explanation for the dRIP condition and how it is used? They mention that it would be explained more in Section 4 but I do not see it, other than it makes the oracle work.", "limitations": "- The work contains no experiments.\n- The computational complexity of the method is not able to adapt to the rank of the underlying matrix $X^*$.\n- The novelty of the theoretical methodology may be limited in how different it is from [KLL+ 22], but I have not checked that reference.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "- This work makes an important step towards provable methods when an RIP does not hold. It forms a natural and nontrivial extension of recent work on sparse recovery to the matrix sensing setting.\n- The work introduces novel weighted and relaxed RIP conditions, under which it is still possible to efficiently identify and recover low-rank matrices.", "weaknesses": "- Only the noiseless setting is studied.\n- The work is more expensive than nonconvex methods in the random model where the rank is known, which have complexity $O(ndr)$, whereas the proposed method has complexity $O(nd^{\\omega}r)$.\n- There are no experiments on data. Furthermore, it is unclear in what real/practical settings wRIP/dRIP might hold.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful comments and positive feedback.\n\nOn the challenges in the matrix case: While the generalization from vectors to matrices (by considering the singular values as a “vector”) may appear intuitive, such generalization should not be taken for granted. To illustrate, consider a simple equation $e^{a+b} = e^a e^b$, which continues to hold in the vector case $\\sum_i e^{a_i + b_i} = \\sum_i e^{a_i} e^{b_i}$, but its generalization to matrices is the well-known Golden–Thompson inequality $tr(e^{A+B}) \\le tr(e^A e^B)$ which requires a non-trivial proof. We refer the readers to Section 2 of [ALO16], which pointed out several wrong matrix inequalities that found their way into published papers when people tried to generalize proofs to the matrix case. Concretely in our paper, we ran into some difficulties in proving our Lemma 5.3 (in Appendix B), and its proof required techniques that are distinct from the vector case. On another note, the algorithm in [KLL+23] runs in nearly-linear time, but despite our best efforts, we were not able to obtain the same runtime due to several technical obstacles.\n\nRegarding experiments: We believe that our results are substantial even without experiments, and we hope that our theoretical results are judged based on their merits. Our main contribution is to pose and study the problem of semi-random matrix sensing, and to provide descent-style algorithms with good asymptotic runtimes. We did not include experiments because our focus is not to obtain the fastest possible algorithm for semi-random matrix sensing, and experiments sometimes divert readers' attention toward such metrics. That said, we acknowledge that experimental evaluation is important and a fruitful direction for future work.\n\nOn the remaining weaknesses and questions:\n\n- We chose to study the noiseless case because it is the most basic setting and our focus is the semi-random model (vs. the random setting with RIP). While our algorithm is simple, our analysis is already fairly involved, so we decided to leave the noisy setting to future work.\n\n- While it is true that our algorithm runs slower than the fastest non-robust matrix sensing algorithm (i.e., with RIP condition), our setting is inherently more challenging because we allow the adversary to add any number of arbitrary sensing matrices. Our goal is to initiate a line of research toward designing robust matrix sensing algorithms that are as efficient as their non-robust counterparts (or show that it is impossible to do so).\n\n- We believe Algorithm 1 helps improve the clarity of our paper. While Algorithm 1 appears trivial, it allows Algorithm 2 to focus on obtaining a matrix $X$ that is closer to the ground truth $X^\\star$ by a constant factor. The alternative would be to put all its technical details into Algorithm 2 (including the for loop, the number of iterations, the contracting radius, and the union bound in failure probability), which would introduce unnecessary complexity in Algorithm 2.\n\n- Throughout the paper, we tried to use lower-case letters for vectors and upper-case letters for matrices. We notice that there are exceptions to this rule (e.g., L being a scalar) and we will try our best to address this.\n\n- Regarding more explanation on the dRIP condition and the weight oracle: In the proof of Lemma 4.2, we provided more intuition for the progress and decomposition conditions and explained how these conditions are used to prove the correctness of Algorithm 2. We apologize for any confusion caused by directing readers to Section 4, as we moved the proof of Lemma 4.2 to Appendix A in this submission. We will fix this. More details about the dRIP condition can be found in Appendix B.\n\n[ALO16] Zeyuan Allen-Zhu, Yin Tat Lee, Lorenzo Orecchia. Using Optimization to Obtain a Width-Independent, Parallel, Simpler, and Faster Positive SDP Solver. SODA 2016.\n\n[KLL+23] Jonathan A. Kelner, Jerry Li, Allen Liu, Aaron Sidford, Kevin Tian. Semi-Random Sparse Recovery in Nearly-Linear Time. COLT 2023."}, {"review_id": "9d7gvkpEiu", "reviewer": "Reviewer_qNDU", "summary": "This paper study the matrix sensing problem (or low-rank matrix recovery) in the so-called semi-random model. The semi-random model stems from the fact that an unknown set of sensing matrices satisfy the Restricted Isometry Properties (RIP) while the remaining set are chosen adversarily. This model has the advantage to design methods that are robust to noise or adversarial examples. The authors design design a descent-style algorithm that iteratively reweights the input to recover the ground truth matrix. They extend a previous work that tackle the sparse vector recovery problem in the semi-random model, to matrix low-rank estimation problem.", "questions": "Q1- Some of the theoretical claims have not been proved in the paper : \n1- The authors claim that their work improves correctness and accuracy of existing non-convex relaxations [BNS16] \nCould the authors please provide a proof of the statement in the appendix? \n2- On the [BNS16] method, there are bad local minima when considering the semi-random model\nCould the authors please provide a proof of the statement in the appendix? \n\nQ2- The authors say that one of the drawback of convex solutions are their prohibitive time complexities. But their results show that they achieve comparable run-time as existing convex solutions. Could the authors please elaborate more on this?\n\nQ3- Could the authors please provide a small section of empirical evidence of their results, at least on synthetic data for a low-rank matrix recovery problem under adversary addition to their input, showing the gain of their method (time vs accuracy) over existing approaches?\n\nQ4- Combining the current analysis with the work [KL22+], to which extent the analysis of estimation of SPARSE and LOW-RANK matrix in the semi-random model doable? \n\nQ5- Could you please add the Limitations of the paper, as required in the guidelines?\n\nI would raise my score if the questions Q1-Q3 above are properly addressed.", "limitations": "The authors have not provided the limitations of their work in the manuscript. Could they please add the limitations in the rebuttal?", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The work tackles a very important theoretical problem in Machine learning that have direct implications on designing practical algorithm for robustness in the recovery of low-rank signals.\n- The paper generalize existing work [KL22+] from a theoretical standpoint.", "weaknesses": "- Lack of empirical evaluation of the main results on at least synthetic data\n- Some of the theoretical claims have not been proved in the paper : 1- The authors claim that their work improves correctness and accuracy of existing non-convex relaxations [BNS16] 2- On the [BNS16] method, there are bad local minima when considering the semi-random model\n- The authors say that one of the drawback of convex solutions are their prohibitive time complexities. But their results show that they achieve comparable run-time as existing convex solutions\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful comments and positive feedback.\n\nRegarding bad local optima in the semi-random model (Q1, Part 2): Section 5 of [BNS16] proved that bad local minima exist if the sensing matrices do not satisfy RIP. We mentioned this in Lines 74-77 of our paper. More precisely in our setting, a semi-random adversary can add an arbitrary number of sensing matrices (provided that the linear measurements are correct), so we can have 1% of the sensing matrices satisfying RIP and use the remaining 99% to implement the counter-examples in [BNS16]. We will discuss this in more detail, and we will include the counter-examples in the Appendix to be self-contained.\n\nOn comparison with existing non-convex approaches such as [BNS16] (Q1, Part 1): We intended to say that existing non-convex approaches can get stuck in bad local optima in the semi-random model, while our algorithm is guaranteed to converge to a global optimum. We agree with the reviewer that the phrase “improves the correctness and accuracy” should be made more precise. We will clarify this.\n\nRegarding our runtime being comparable to convex approaches (Q2): We focused on nonconvex approaches because they have many advantages in practice. For example, gradient descent is conceptually much simpler than state-of-the-art semidefinite program (SDP) solvers, and it can converge in much fewer iterations predicted by theory, while the runtime of cutting-plane and interior-point methods are often close to their theoretical bounds. More importantly, despite having comparable asymptotic runtime as existing convex approaches, we believe our work will serve as a starting point for the discovery of more practical and provably robust algorithms for semi-random matrix sensing.\n\nRegarding experiments (Q3): We believe that our results are substantial even without experiments, and we hope that our theoretical results are judged based on their merits. Our main contribution is to pose and study the problem of semi-random matrix sensing, and to provide descent-style algorithms with good asymptotic runtimes. We did not include experiments because our focus is not to obtain the fastest possible algorithm for semi-random matrix sensing, and experiments sometimes divert readers' attention toward such metrics. That said, we acknowledge that experimental evaluation is important and a fruitful direction for future work.\n\nOn recovering sparse and low-rank matrices (Q4): If the ground-truth matrix M is sparse, we can view M as a vector and use [KLL+23] to recover M in the semi-random model. Consequently, when M is sparse *and* low-rank, one can choose between our algorithm and [KLL+23]. The two algorithms have different sample complexities and running times, and the choice should be made depending on the rank and sparsity parameters. A potentially better approach is to integrate the two algorithms, e.g., by running weighted gradient descent and projecting onto the set of matrices with small nuclear norm (as in our paper) and small entrywise L1 norm (as in [KLL+23]), which is an intriguing direction for future work.\n\nOn a separate Limitations section (Q5): We would like to bring to the reviewer’s attention that a separate \"Limitations\" section is not mandatory according to this year’s CFP and Paper Checklist. We stated all assumptions very precisely (e.g., Theorem 3.1) and our algorithm will succeed under these assumptions.\n\n\n[BNS16] Srinadh Bhojanapalli, Behnam Neyshabur, Nathan Srebro. Global Optimality of Local Search for Low Rank Matrix Recovery. NeurIPS 2016.\n\n[KLL+23] Jonathan A. Kelner, Jerry Li, Allen Liu, Aaron Sidford, Kevin Tian. Semi-Random Sparse Recovery in Nearly-Linear Time. COLT 2023."}, {"review_id": "cTrSNTqq4W", "reviewer": "Reviewer_kSWp", "summary": "This paper studies the problem of low-rank matrix recovery for semi-random measurement matrices. This model allows for a mix of RIP matrices and arbitrarily chosen matrices. Using an iterative re-weighted approach, the authors demonstrate provable recovery using concepts from sparse recovery.", "questions": "Do the authors believe their results can apply to combinations of sparse and low-rank matrices? ", "limitations": "Future work is discussed.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper does a great job and connecting the sparse recovery framework to the setting studied. Although this indeed is not a new observation, it is discussed and explained well here. The paper is overall written well and the results are solid and robust. The theoretical guarantees are clearly stated and give precise recovery guarantees in this framework. ", "weaknesses": "The semi-random model is interesting mathematically but could be motivated better practically within the paper. The paper would be stronger if it included experimental results that supported the theory.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful comments and positive feedback.\n\nOn “combinations of sparse and low-rank matrices”: If we understand correctly, the reviewer is referring to the problem of sensing a matrix M in the semi-random model, in which the underlying matrix M can be decomposed as M = A + B where A is low-rank (and incoherent) and B is sparse. One possible approach is to maintain low-rank matrices A_t and B_t in each iteration, run alternating weighted gradient descent using the weight oracles proposed in [KLL+23] and in our paper, and show that A_t and B_t converge to the ground truth matrices. While we have not explored this setting on a technical level, this is an exciting avenue for future work and we thank the reviewer for pointing us in this direction.\n\n[KLL+23] Jonathan A. Kelner, Jerry Li, Allen Liu, Aaron Sidford, Kevin Tian. Semi-Random Sparse Recovery in Nearly-Linear Time. COLT 2023."}]

Author rebuttal:

Meta-review: This paper studies the matrix sensing problem with a semi-random measurement model, where a subset of the measurement matrices are norm-preserving (i.e., they satisfy the RIP condition), while the remaining measurement matrices are chosen adversarially. With the addition of adversarially chosen measurement matrices, the combined measurement operator may not satisfy RIP condition. This implies that the existing results on the benign landscape of matrix sensing do not apply to this setting. To address this challenge, the authors introduce a weighted gradient-based method that can guarantee convergence to the true low-rank solution in polynomial time. 

Four reviewers have reviewed the paper, and their overall assessment of the paper was positive. I agree with this assessment and believe the paper is a solid contribution with interesting results. Three reviewers also recommended that the authors should provide some experiments to showcase the empirical performance of their proposed algorithm. I agree with this comment, and encourage the authors to include (at least some preliminary) experiments in the final version of the paper.
Decision: Accept (poster)