Optimal tuning-free convex relaxation for noisy matrix completion

This paper is concerned with noisy matrix completion--the problem of recovering a low-rank matrix from partial and noisy entries. Under uniform sampling and incoherence assumptions, we prove that a tuning-free square-root matrix completion estimator (square-root MC) achieves optimal statistical performance for solving the noisy matrix completion problem. Similar to the square-root Lasso estimator in high-dimensional linear regression, square-root MC does not rely on the knowledge of the size of the noise. While solving square-root MC is a convex program, our statistical analysis of square-root MC hinges on its intimate connections to a nonconvex rank-constrained estimator.


Introduction
Low-rank matrix completion [CR09,KMO10] aims to reconstruct a low-rank data matrix from its partially observed entries. This problem finds numerous applications in collaborative filtering [RS05], causal inference [ABD + 21], sensor network localization [BLWY06], etc.
In this paper, we focus on the noisy matrix completion problem, in which the revealed entries are further corrupted by random noise. Mathematically, let L ∈ R n×n be a rank-r matrix of interest, and E ∈ R n×n denote the noise matrix. We observe a subset of entries where Ω ⊆ {1, 2, . . . , n} × {1, 2, . . . , n} represents the index set of the observations. The goal of noisy matrix completion is to recover the underlying low-rank matrix L given the observation M = [M ij ].
Arguably, one of the most natural approaches to solving noisy matrix completion is the following nuclear norm regularized least-squares estimator [CP10, CCF + 20]: where L * denotes the nuclear norm (i.e., sum of singular values) of the matrix L, and λ > 0 is a tuning parameter. Here, the least-squares loss (i,j)∈Ω (L ij − M ij ) 2 measures the fidelity of the estimate L to the observation M , while the nuclear norm penalty λ L * encounrages the low-rank property of the solution.
In a recent work [CCF + 20], it has been shown that with properly chosen regularization parameter λ, the nuclear norm regularized least-squares estimator (2) achieves optimal statistical performance in terms of estimating the low-rank matrix L . However, this optimal choice depends on the noise size, which is often unknown in practice. This begs the question: Can we develop an estimator for noisy matrix completion that does not rely on the unknown noise size (a.k.a., tuning-free), and at the same time achieves optimal statistical performance?
Motivated by the success of the square-root Lasso estimator [BCW11] for sparse recovery problems, we consider in this paper the following square-root matrix completion estimator (dubbed square-root MC): A notable difference from the vanilla least-squares estimator (2) is that square-root MC (3) aims at minimizing the regularized 2 error instead of the regularized squared 2 error.
Our contributions. The main result of this paper (cf. Theorem 1) shows that square-root MC (3) with a noise-size-oblivious choice λ 1/ √ n (e.g., λ = 32/ √ n) achieves the optimal error guarantees for recovering the low-rank matrix L over a wide range of noise sizes. Such guarantees are on par with those established for the vanilla least-squares estimator (2) with a choice of λ depending the noise size [CCF + 20]. Clearly, the tuning-free property and statistical optimality of square-root MC together answer our motivating question in the affirmative.
To put our contributions into context, we would like to immediately point out two relevant pieces of prior work, while deferring other related ones to Section 4. First and foremost, a variant of the square-root MC estimator has been proposed and studied by Klopp [Klo14], in which an extra element-wise max norm constraint is added to the problem (3). In the same paper, it was shown that square-root MC achieves optimal statistical performance when the size of the noise is sufficiently large compared to the entries of the low-rank matrix. However, when the noise size is relatively small, the upper bound proved therein fails to uncover the optimal performance of the square-root MC estimator. In particular, it falls short of uncovering the exact recovery property when there is no noise, i.e., when E = 0. More recently, Zhang et al. [ZYW21] focuses on a closely related noisy robust PCA problem [CLMW11,CFMY21] and studies a similar tuning-free estimator. Their results, however, even in the full observation setting (i.e., Ω = {1, 2, . . . , n} × {1, 2, . . . , n}), has a poor dependence on the problem dimension n, which is far from optimality. Detailed comparisons between our results and those in the papers [Klo14,ZYW21] can be found in Section 2.
Notation. For a vector v, we use v 2 to denote its Euclidean norm. For a matrix M , we use M , M F , and M ∞ to denote its spectral norm, Frobenius norm, and the elementwise ∞ norm. In addition, M 2,∞ denotes the largest 2 norm of the rows. We also use σ j (M ) to denote the j-th largest singular value of M . Additionally, the standard notation f (n) = O (g(n)) or f (n) g(n) means that there exists a constant c > 0 such that |f (n)| ≤ c|g(n)|, f (n) g(n) means that there exists a constant c > 0 such that |f (n)| ≥ c |g(n)|. Also, f (n) g(n) means that there exists some large enough constant c > 0 such that |f (n)| ≥ c |g(n)|. Similarly, f (n) g(n) means that there exists some sufficiently small constant c > 0 such that |f (n)| ≤ c |g(n)|.

Main results
We start with introducing the model assumptions for noisy matrix completion. The first assumption is on the observation pattern.
Assumption 1. Each index (i, j) belongs to the set Ω independently with probability p.
The next assumption is concerned with the noise matrix.
In the end, we turn to the assumptions on the groundtruth matrix L . Let σ min , σ max be the smallest and largest singular values of L , respectively, and let κ := σ max /σ min be its condition number. We require the matrix L to be µ-incoherent defined in the following way.
Assumption 3. The rank-r matrix L with SVD L = U Σ V is µ-incoherent in the sense that Now we are in position to state our main results regarding the square-root MC estimator, with the proof deferred to Section 3.
Theorem 1. Suppose that Assumptions 1-3 hold. In addition, assume that the sample size and the noise level satisfy n 2 p ≥ C sample κ 4 µ 2 r 2 n log 3 n, and σ σ min n p ≤ C noise κ 4 µr log n for some sufficient large (resp. small) constant C sample > 0 (resp. C noise > 0). Set λ = C λ / √ n for the square-root MC estimator (3), where C λ is some large constant (e.g., 32). With probability at least 1 − O(n −3 ), any solution L cvx to the square-root MC problem (3) obeys Here C F , C ∞ , C op > 0 are three universal constants.
Several remarks on Theorem 1 are in order.
Minimax-optimal F estimation error. When the condition number κ is of a constant order, the square-root MC estimator enjoys minimax-optimal F estimation error [NW12,CCF + 20]. In contrast, the upper bound in the paper [Klo14] reads L cvx − L F max {σ, L ∞ } n log n/p, which is only statistically optimal when σ L ∞ . In addition, translating the bound in the paper [ZYW21] from robust PCA to the matrix completion setting, one obtains L cvx − L F σn 2 , which has a much worse (and hence sub-optimal) dependence on the problem dimension n.
Tuning-free property. More importantly, the optimal performance of square-root MC is achieved in a completely tuning-free fashion. The regularization parameter λ can be set to be 32/ √ n, that does not depend on the noise variance σ 2 , the observation probability p, nor the true rank r of the matrix L . This is in stark contrast to the vanilla nuclear norm regularized least-squares estimator (2) in which λ is set to be on the order of σ √ np (cf. [CCF + 20]).
Entrywise error guarantees. Also, our main results provide upper bounds on the entrywise estimation error (cf. bound (4b)). Compared to the F estimation error (4a), it can be seen that the square-root MC estimator is uniformly good in the sense that there is no spiky entry estimate with large estimation error.
To corroborate our main results, we perform numerical experiments on noisy matrix completion with simulated data. We fix the rank r to be 5 throughout the experiment. For each problem dimension n, we generate two n × r random orthonormal matrices as X and Y and take L := X Y as the rank-r n × n groundtruth matrix. The entrywise noise is taken to be Gaussian with variance σ 2 . For all the experiments, we set λ = 4/ √ n in square-root MC, and report the average results over 20 Monte-Carlo simulations. Figure 1 reports the relative error of the square-root MC estimator in Frobenius, spectral, and infinity norms. More specifically, Figure 1(a) fixes n = 500, p = 0.5, and varies σ; Figure 1(b) fixes σ = 10 −4 , p = 0.5, and varies n; Figure 1(c) fixes σ = 10 −4 , n = 2000, and varies p. Overall, the plots showcase a linear relationship between the performance and the noise size σ, the problem dimension √ n, and the observation probability p. This is consistent with the O(σ n/p) scaling proved in Theorem 1.

Outline of the proof
In this section, we provide the key steps for proving our main result, i.e., Theorem 1. The proof follows the general strategy of bridging convex and nonconvex solutions, first appeared in the paper [CCF + 20], with several important modifications to handle the non-smooth F norm (as opposed to the smooth squared F norm).
A central object in our analysis is the following nonconvex optimization problem which is closely related to the original convex square-root MC formulation (3). To see this, first, for any rank-r matrix Z, one has Z * = inf X,Y ∈R n×r :XY =Z 1 2 Second and more importantly, we have that for any matrix Z = XY , It turns out that the (approximate) solution to the nonconvex optimization problem (5) serves as an extremely tight approximation to the square-root MC estimator, which facilitates the statistical analysis of the latter. In sum, our proof involves two main steps: 1. We first show-via an explicit construction-that an approximate stationary point L ncvx of the nonconvex problem (5) exists and is also close to the groundtruth matrix L .
2. We then establish that such an approximate stationary point L ncvx is extremely close to the solution L cvx to the convex problem (3).
Combining the two key steps via triangle inequality finishes the proof.
Step 1: Nonconvex optimization. The nonconvex optimization problem (5) has two groups of decision variables, i.e., (X, Y ) and θ. Also note that given a fixed pair (X, Y ), the optimal choice of θ is simply given by θ = P Ω (XY − M ) F . Therefore it is natural to consider an alternating minimization method to construct an approximate stationary point of the nonconvex program (5); see Algorithm 1. Given a current iterate (X t , Y t , θ t ), the algorithm first runs one step of gradient descent on (X, Y ) while fixing θ t . It then Algorithm 1 Gradient descent on the nonconvex formulation of square root matrix completion , and total number of iterations t 0 = n 18 . Gradient updates: for t = 0, 1, . . . , t 0 − 1 do In the end, Algorithm 1 returns the point L ncvx with the smallest gradient among the iterates as an approximate stationary point.
The following lemma ensures that L ncvx is an approximate stationary point of the nonconvex problem and more importantly is close to the groundtruth matrix L . The proof is deferred to Section 3.1.
where C F , C ∞ , C op are three universal positive constants.
Step 2: Bridging convex and nonconvex solutions. It remains to show that L ncvx is extremely close to the convex solution L cvx , which is provided in the following lemma.
Lemma 2. Instate the assumptions of Theorem 1. With probability exceeding 1 − O(n −3 ), one has See Section 3.2 for the proof of this lemma.
We remark in passing that the polynomial factor n −5 in Lemma 2 is arbitrarily chosen, and the exponent 5 can be replaced with any large constant. The essence is that the difference between L ncvx and L cvx is orderwise much smaller compared to the estimation error of L ncvx itself. Such proximity between L ncvx and L cvx is verified empirically in Figure 2. Now we are ready to combine the previous two steps and finish the proof of Theorem 1. Proof of Theorem 1. Combine Lemmas 1-2 with the triangle inequality to arrive at where the last relation uses the facts that λ 1/ √ n and that p 1/ √ n. Redefine 4C F to be C F to complete the proof of the bound (4a). The other two bounds on the operator norm and the ∞ norm follow from similar arguments. We omit here for brevity.

Proof of Lemma 1
Since Algorithm 1 operates in the space of low-rank factors, we start with establishing guarantees for the stacked low-rank factor F t := X t Y t ∈ R 2n×r , and then translate the guarantees to the matrix space L t = X t Y t . Special care is needed as the decomposition L = XY is not unique in (X, Y ), and hence we need to account for the rotational ambiguity in (X, Y ). To this end, for each t ≥ 0, we define the optimal rotation matrix to be Introducing leave-one-out sequences.
In order to control the 2,∞ error of F t (and hence ∞ error of L t ), we construct 2n leave-one-out auxiliary sequences {F serves as a good approximation to the original sequence {F t } t≥0 , while at the same time is more amenable to statistical analysis.
To formally construct such leave-one-out sequences, we first define 2n auxiliary loss functions. For each 1 ≤ l ≤ n, define Algorithm 2 Gradient descent generating the leave-one-out sequences , and total number of iterations t 0 = n 18 . Gradient updates: for t = 0, 1, · · · , t 0 − 1 do Similarly, for each n + 1 ≤ l ≤ 2n, we define With these notations in place, Algorithm 2 details the way we construct the leave-one-out sequences. Similar constructions have been deployed in the papers [CCF + 20] and [CFMY21]. However, it is worth pointing out that the sequence {θ t } is produced according to the original sequence, instead of the leave-oneout sequence. This change is tailored to the analysis of the square-root MC estimator as it aligns better with the original loss function f , while allowing us to reuse several keys results in the paper [CCF + 20].
Properties of the iterates. As planned, we aim to show that the leave-one-out iterates {F (l) t } 1≤l≤2n,t≥0 stay extremely close to the original iterates {F t } t≥0 , and that {F t } t≥0 is close to the groundtruth factor F . Such properties are collected in the following lemma.
Lemma 3. With probability at least 1 − O(n −3 ), the following statements hold for all iterations 0 ≤ t ≤ t 0 : for some positive constants C F , C op , C 3 , C 4 , C ∞ . Here H Furthermore the output (X t , Y t ) has small gradient: See Section A for the proof of this lemma.
Now we are ready to prove Lemma 1 based on the results presented in Lemma 3.
Proof of Lemma 1. By the triangle inequality, one has Use relation (10b) to obtain The first inequality uses X t ≤ 2 X , which is a direct consequence of (10b) and the last line uses Here step (i) uses the fact X F X ≤ κ L F , whereas in step (ii) we use F 2,∞ F 2,∞ ≤ κ 3 µr L ∞ .

Proof of Lemma 2
Before embarking on the main proof, we state a few useful properties of the noise matrix E and the nonconvex solution L ncvx . These properties allow us to establish the proximity between the approximate stationary point L ncvx and the convex solution L cvx . The first property is concerned with the size of the regularization parameter, which appeared as Lemma 3 in the paper [CCF + 20].
Lemma 4. Suppose that n 2 p ≥ Cn log 2 n for some sufficiently large constant C > 0. Take λ = C λ / √ n for some constant C λ . Then with probability at least 1 − O(n −10 ), one has The next property is on the injectivity of P Ω in the tangent space T at L ncvx . More precisely, letting U ΣV be the SVD of L ncvx , we define the tangent space T at L ncvx as Proof. This is an easy consequence of Lemma 4 in the paper [CCF + 20] and the relation (10e).
Last but not least, the lemma collects several interesting properties of the nonconvex solution L ncvx , as well as its low-rank factors X ncvx , Y ncvx . Lemma 6. The approximate stationary point L ncvx satisfies See Section A.4 for the proof of this lemma.
For notational simplicity, we define In other words, g(X, Y ) is the minimal value of f (X, Y , θ) when (X, Y ) is fixed. Now we are ready to present the key lemma of this section, which relates the difference between L ncvx and L cvx to the size of the gradient ∇g(X ncvx , Y ncvx ). The proof is deferred to Section B.
Lemma 7. Suppose that (X ncvx , Y ncvx ) has small gradient in the sense that Then on the event that Lemmas 4-6 hold, any minimizer L cvx of the convex program (3) satisfies Remark 1. Observe that if ∇g(X ncvx , Y ncvx ) F = 0, i.e., if L ncvx is an exact stationary point of the nonconvex square-root MC problem, L ncvx is also a solution to the convex problem (3).
With the help of Lemma 7, we can prove Lemma 2 now.
Proof of Lemma 2. First, Lemma 3 tells us that the nonconve solution (X t , Y t ) satisfies the bound (15) on the size of the gradient. This together with Lemmas 4 to 6 allows us to invoke Lemma 7 to obtain where the last inequality uses the gradient upper bound (15), L F ≥ L ≥ σ max = κσ min , and the fact that the sample size assumption n 2 p ≥ C sample κ 4 µ 2 r 2 n log 3 n implies np 1 and κ n.

Prior art
Matrix completion. Convex relaxation has been extensively studied for the matrix completion problem both in the noiseless setting [CR09, CT10, Gro11, Rec11, Che15], and the noisy case [CP10, NW12, KLT11, Klo14, CCF + 20]. In the noiseless setting, convex relaxation achieves exact recovery as soon as the number of observed entries n 2 p exceeds nr log 2 n-roughly the degrees of freedom of a rank-r matrix, which is information theoretically optimal. When it comes to the noisy setting, Candès and Plan [CP10] focuses on arbitrary noise (e.g., noise could be deterministic and adversarial), and proves that convex relaxation is stable w.r.t. the noise size. The theoretical guarantees for convex relaxation are strengthened by Chen et al. [CCF + 20] in the stochastic noise case, which is the same setting we study in the current paper. Such a discrepancy between stochastic and deterministic noise for convex relaxation is also documented in [KS21]. Pioneered by the work [KMO10,KMO09], nonconvex optimization has gained a lot of attentions during the past decade for solving matrix completion owing to its computational efficiency. Efficient computational and statistical guarantees have been provided for manifold optimization [KMO10,KMO09] Tuning-free methods. A variety of tuning-free methods have been proposed to tackle high-dimensional linear regression. The seminal work [BCW11] proposes the square-root Lasso estimator which does not rely on knowing the size of the noise and is also statistically optimal. [SZ12] proposes an equivalent method named scaled sparse linear regression, which originates from the concomitant scale estimation [Hub11,Owe07]. [LM15] proposes TREX, a method similar to square-root Lasso and is completely parameter-free. [WPB + 20] borrows ideas from non-parametric statistics and proposes Rank Lasso, whose optimal choice of tuning parameter can be simulated easily in the case with unknown variance of the noise. See [WW19] for a survey on the selection of tuning-parameters for high-dimensional regression and [GHV12] for a survey on regression with unknown variance of noise.
Bridging convex and nonconvex optimization. The connections between convex and nonconvex optimization has been extensively used in a recent line of work. Chen et al. [CCF + 20] uses this to prove the optimality of the vanilla least-squares estimator for noisy matrix completion; Later, the papers [CFMY21, CFWY21, WF22] extend the technique to the robust PCA problem, the blind deconvolution problem, and matrix completion with heavy-tailed noise.
Leave-one-out analysis. Leave-one-out analysis is powerful in decoupling statistical dependence and obtain element-wise performance guarantees. It has been successfully applied to high-dimensional re-

Discussions
Focusing on the noisy matrix completion problem, this paper shows that a tuning-free estimator-square-root MC achieves optimal statistical performance. This opens up several interesting avenues for future research. Below, we list a few of them.
• Extensions to robust PCA. While our work focuses on matrix completion, a natural extension is to further consider partial observations with outliers, i.e., robust PCA. As mentioned, Zhang et al. [ZYW21] has studied this problem (with full observation) and provides an error guarantee of order O(σn 2 ), which is sub-optimal in its dependency on the problem dimension. By contrast, a vanilla least-squares estimator with noise-size-dependent choice of λ has been shown to be optimal [CFMY21]. It remains to be seen whether one can devise an optimal tuning-free method for robust PCA with noise and missing data.
• Inference for square-root MC estimator. The current paper discusses solely the estimation performance of the tuning-free estimator. As statistical inference for matrix completion is equally important, one wishes to develop inferential procedures around the square-root MC estimator as that has been done in the paper [CFMY19] for the vanilla least-squares estimator.
• Robustness to non-uniform design. In high-dimensional linear regression, optimal tuning-free methods have been developed to be adaptive to both the unknown noise size and the design matrix. In the matrix completion setting, the design is governed by the sampling pattern, which is assumed to be uniform in the current paper. It is of great interest to develop robust and tuning-free approaches for noisy matrix completion with non-uniform sampling that improved over the max-norm constrained estimator in [Klo14].

A Proof of Lemma 3
We prove Lemma 3 via induction. Since all the algorithms start from the groundtruth, it is trivial to see that the hypotheses (10) hold for t = 0. We also record two important properties of the iterates at t = 0, namely, and where C B > 0 is a universal constant. Note that at t = 0, we have θ 0 = P Ω (E) F , which concentrates sharply around np 1/2 σ under the noise assumption and uniform sampling. Now suppose the hypotheses (10), (16), and (17) hold for the t-the iterates. We aim to show that the same set of hypotheses continue to hold for the (t + 1)-th iterates. Sections A.1 and A.2 are devoted to this induction step. In addition, we prove the last claim (11) in Section A.3. In Section A.4 we prove Lemma 6 which is a consequence of (10) and (16).
We make a key observation that the t-th iterations of Algorithm 1 and 2 are exactly the same as the t-th iterations of Algorithm 1 (vanilla gradient descent) and 2 (construction of the leave-one-out sequence) in the paper [CCF + 20] with the parametersλ t andη t . Moreover, given the induction hypothesis (16) one has 1 2 n √ pσ ≤ θ t−1 ≤ 2n √ pσ. Combine this with our choice of λ = C λ n −1/2 to see that which are consistent with the choice of λ and η in [CCF + 20]. These allow us to invoke Lemmas 10-15 in [CCF + 20] to prove that claims (10) and (17) hold for the (t + 1)-th iterates.

A.2 Induction on hypotheses (16)
In this section, we aim to show that the claim (16) holds for the (t + 1)-th iterates.
Observe that Similar to the proof of Lemma 1, using the incoherence assumption Then As the sample size satisfies n 2 p κ 4 µ 2 r 2 n log 3 n, we have P Ω X t+1 Y t+1 − L F n √ pσ. As mentioned before, P Ω (E) F sharply concentrates around np 1/2 σ. Therefore by the triangle inequality, we have for large enough n.

A.3 Proof of bound (11)
Suppose for the moment that holds for all t ≥ 1. Then a telescoping argument would yield the conclusion that Expanding the left hand side, we see that it is upper bounded by where the last line uses the nonnegativity of norms and the invariance of Frobenius norm under rotation. In view of the properties (10) and the noise size assumption σ σmin n p 1, we have Then, where the last line uses the fact that σrκ n p . These combined with the fact that P Ω (E) F n √ pσ implies , as t 0 = n 18 , η σ/( √ pκ 3 σ max ), and To simplify the expression we use κ n and r √ n which are consequences of the sample size assumption n 2 ≥ n 2 p κ 4 µ 2 r 2 n log n.
Then h(X, Y ) matches the form of the objective function in Lemma 16 of the paper [CCF + 20]. Then Lemma 16 therein tells us that where we recallη t = η/θ t . Rewriting the bound in terms of f yields In addition, by the optimality of θ t+1 , one has Combining equations (20) and (21) completes the proof.

A.4 Proof of Lemma 6
By Lemma 3, we know that X ncvx satisfies where the last relation arises from the noise level assumption σ σmin n p 1/ κ 4 µr log n. Therefore we can apply Weyl's inequality to obtain for large enough n. These hold similarly for the singular values of Y ncvx . On the other hand, the relations (14c) come directly from (16), and (14d) follows from Lemma 4 in [CCF + 20].

B Proof of Lemma 7
To simplify the notation, we denote θ := P Ω (L ncvx −M ) F , and ∆ := L cvx −L ncvx throughout this section. In view of Lemma 6, we know that θ = 0, and hence θ −1 is well defined.
Recall that U ΣV is the SVD for L ncvx , and T is the tangent space at L ncvx . The following lemma is useful in controlling the size of ∆.
Lemma 8. Under the notations and assumptions of Lemma 7, we have where R is a residual matrix such that See Section B.1 for the proof.
We decompose the proof into three steps. In Step 1, we show that the difference matrix ∆ mainly lies in the tangent space T . In Step 2, the previous fact is leveraged to show an upper bound on P Ω (∆). In the last step (Step 3), we connect the previous steps with the injectivity property (cf. Lemma 5) to reach the desired conclusion.
Step 1: showing that ∆ lies primarily in the tangent space T . By the optimality of L cvx , we have Use the convexity of · F and · * and the decomposition L ncvx = U ΣV to see that holds for any W 0 ∈ T ⊥ with W 0 ≤ 1. Apply Lemma 8 to further obtain In particular, one can choose W 0 ∈ T ⊥ such that P T ⊥ (∆) * = W 0 , ∆ , which yields the inequality Here the last line arises from Holder's inequality. Again, by Lemma 8, we have the bounds P T (R) F ≤ 70κσ −1/2 min ∇g(X, Y ) F and P T ⊥ (R) < 1/2, which allow us to further arrive at

This further implies
As an immediate consequence, under the assumed upper bound (15) for ∇g(X, Y ) F , we have 140κσ Step 2: bounding P Ω (∆) 2 F . We start with presenting an identity involving P Ω (∆) 2 F : Lemma 8 and Equation (23) tell us that By convexity of · * , this further simplifies to for any W ∈ T ⊥ with W ≤ 1. Combine Equation (26) and (27) to reach We prove in the end of this section that the two terms α 1 and α 2 obey which yields the upper bound on P Ω (∆) 2 F in terms of P T (∆) F : Step 3: final calculations. Using the decomposition P Ω (∆) = P Ω P T (∆) + P Ω P T ⊥ (∆), we obtain

Together with Lemma 5 and Equation 24, we have
where the last line uses (15). As a result, we arrive at the sandwhich formula Then similar to the case of P Ω (L cvx − M ) F − P Ω (L ncvx − M ) F ≤ 0, Combining the two cases yields (28a).

B.1 Proof of Lemma 8
The proof relies on the following representation of the low-rank factors X, Y of the nonconvex solution L ncvx .
Lemma 9. Under the assumptions and notations of Lemma 7, there exists an invertible matrix Q ∈ R r×r such that X = U Σ 1/2 Q, Y = V Σ 1/2 Q − , Q ≤ 2 and where U Q Σ Q V Q is the SVD of Q.
See Section B.2 for the proof.
Denote the partial gradients of g(X, Y ) as B 1 , B 2 , i.e., B 1 := ∇ X g(X, Y ) = 1 θ P Ω (XY − M )Y + λX; (31) where we recall θ = P Ω (XY −M ) F . By definition, we know that max { B 1 F , B 2 F } ≤ ∇g(X, Y ) F . Let R be the matrix that is defined by equation (22). We now control its component in T and T ⊥ separately.
By the definition of the projection operator P T , we have For the term RV , we use the definitions of B 1 and R to see that which together with the representations in Lemma 9 implies RV = U Σ 1/2 (QQ − I r )Σ −1/2 − B 1 Q Σ −1/2 .
In view of the relation (30), we have