1–72

The Leave-one-out Approach for Matrix Completion:
Primal and Dual Analysis

arXiv:1803.07554v1 [stat.ML] 20 Mar 2018

Lijun Ding
Yudong Chen

ld446@cornell.edu
yudong.chen@cornell.edu
School of Operations Research and Information Engineering, Cornell University

Abstract
In this paper, we introduce a powerful technique, Leave-One-Out, to the analysis of lowrank matrix completion problems. Using this technique, we develop a general approach for
obtaining fine-grained, entry-wise bounds on iterative stochastic procedures. We demonstrate the power of this approach in analyzing two of the most important algorithms for
matrix completion: the non-convex approach based on Singular Value Projection (SVP),
and the convex relaxation approach based on nuclear norm minimization (NNM). In particular, we prove for the first time that the original form of SVP, without re-sampling or
sample splitting, converges linearly in the infinity norm. We further apply our leave-one-out
approach to an iterative procedure that arises in the analysis of the dual solutions of NNM.
Our results show that NNM recovers the true d-by-d rank-r matrix with O(µ2 r3 d log d) observed entries, which has optimal dependence on the dimension and is independent of the
condition number of the matrix. To the best of our knowledge, this is the first sample complexity result for a tractable matrix completion algorithm that satisfies these two properties
simultaneously.

1. Introduction
In this paper, we introduce a new technique that is based on Leave-One-Out to the study of
low-rank matrix completion problems. Matrix completion concerns recovering a low rank
matrix from partial observation of a subset of its entries. To study the sample complexity
and algorithmic behaviors of these problems, one often needs to analyze a recursive procedure in the presence of dependency across iterations and entries of the iterates. Such
dependency creates significant difficulties in both the design and analysis of algorithms,
often leading to sub-optimal bounds as well as complicated and unrealistic algorithms that
are not used in practice.
Using the Leave-One-Out approach, we are able to isolate the effect of such dependency,
and establish entry-wise control on the iterates of the recursive procedures. We apply this
approach to the analysis of two archetypal algorithms for matrix completion—the convex
relaxation method based on Nuclear Norm Minimization (NNM, Candès and Recht 2009),
and the non-convex approach based on Singular Value Projection (SVP, Jain et al. 2010)—
in two distinct ways. For NNM, we apply this technique to an iterative procedure that arises
in the analysis, particularly for constructing a dual solution that certifies the optimality of
the desired primal solution. For SVP, we employ this technique directly in studying the
primal solution path of the algorithm.

c

L. Ding & Y. Chen.

Leave-one-out Approach for Matrix Completion

1.1. Our contributions
Concretely, we consider the problem of recovering a low rank matrix M ∗ ∈ Rd1 ×d2 with
rank r < min{d1 , d2 } given a subset of its entries Mij∗ for (i, j) ∈ Ω. The set of observed
indices Ω ⊂ [d1 ] × [d2 ] is assumed to be generated from the standard Bernoulli model; that
is, each entry of M ∗ is observed with probability p, independently of all others. Under this
setting, we summarize our main results and contributions below.
1.1.1. Nuclear norm minimization
NNM is a convex relaxation approach to matrix completion that replaces the non-convex
rank function with the convex nuclear norm. To show that NNM recovers the underlying
matrix M ∗ exactly, it suffices to prove that M ∗ satisfies the first-order optimality conditions
by constructing a so-called dual certificate. The best existing sample complexity results
are obtained using a celebrated argument called the Golfing Scheme, which builds the
dual certificate via an iterate procedure (Gross et al., 2009; Gross, 2011). An essential
ingredient of the Golfing Scheme is to split the observations into independent subsets that
are used in different iterations. Doing so allows ones to circumvent the dependency across
iterations even when a uniform bound does not hold. While this argument has proved to be
fruitful (Recht, 2011; Candès et al., 2011; Chen, 2015), it is also well-recognized that sample
splitting is inherently artificial, and leads to fundamentally sub-optimal sample complexity
results.
Using Leave-One-Out, we are able to completely avoid sample splitting in the Golfing
Scheme and obtain new sample complexity bounds. In particular, we show in Theorem 1
that NNM recovers M ∗ with high probability given a number of Cµ2 r 3 d log d observed
entries, where C > 0 is an absolute constant and µ is the incoherence parameter of M ∗ (see
Definition 2). To the best of our knowledge, this is the first sample complexity result for
a tractable algorithm that enjoys the following two properties simultaneously: (a) it has
absolutely no dependence on the condition number of M ∗ , and (b) it has optimal dependence
on the matrix dimension d, without any superfluous log d factors. While the improvement
of our bound over existing ones may appear quantitatively small, we believe that it paves
the way to finally matching the lower bound of Ω(µrd log d) (Candès and Tao, 2010).
1.1.2. Singular Value Projection
SVP solves a non-convex rank-constrained least squares formulation of matrix completion
by projected gradient descent. Analyzing SVP is more challenging than that of NNM, as
the projection step of the SVP iterations involve an implicit and highly nonlinear mapping,
one that is given by the Singular Value Decomposition (SVD). A major roadblock of the
analysis involves showing that the (difference of) iterates remain incoherent/non-spiky—
which roughly means they are entrywise well-bounded—in the presence of dependent data.
In the presence of this difficulty, previously work has again commonly made use of
the sample splitting trick; that is, using a fresh set of independent observations in each
iteration (Jain et al., 2013; Hardt and Wootters, 2014; Jain and Netrapalli, 2015). Unlike
in NNM where sampling splitting is done only in the analysis, using this trick for SVP
requires changing the actual algorithmic procedure. Doing so has several major drawbacks:
(a) sample splitting is a wasteful way of using the data, and moreover leads to sample
2

Leave-one-out Approach for Matrix Completion

complexity bounds that scale (unnecessarily) with the desired accuracy of the algorithm
output; (b) the trick is artificial, and results in a complicated algorithm that is rarely used
in practice—a gap between theory and practice; (c) as observed by Hardt and Wootters
(2014); Sun and Luo (2016), naive sample splitting (i.e., partitioning Ω into disjoint subsets)
actually does not ensure the required independence; rigorously addressing this technical
subtlety leads to even more complicated algorithms that are sensitive to the generative
model of Ω and hardly practical.
Using the Leave-One-Out technique, we are able to study the original form of SVP,
without any sample splitting. In particular, we show that the iterates remain well-bounded
entrywise, even when the procedure itself does not have any explicit regularization mechanism for ensuring such a property—hence establishing a form of implicit regularization for
SVP. In fact, we establish an even stronger conclusion that the iterates converge linearly in
entrywise norm to the desired solution; see Theorem 2.
1.1.3. Perspectives
To put the results above in perspective, we note that NNM, and more broadly convex relaxation methods, remain one of the most important and versatile approaches to matrix
completion and other high-dimensional problems. Similarly, SVP plays a unique role, both
conceptually and algorithmically, in a growing line of recent work on non-convex optimization based approaches for matrix completion. In particular, SVP is recognized as a natural
and simple algorithm, and does not require a two-step procedure of “initialization + local
refinement”, which are common in other non-convex algorithms. In fact, other algorithms
often rely on (one or a few steps of) SVP for initialization; examples include alternate
minimization (Jain et al., 2013), projected gradient descent (Chen and Wainwright, 2015)
and gradient descent with regularized objective (Sun and Luo, 2016; Zheng and Lafferty,
2016). Moreover, SVP involves one of the most well-understood non-convex problems and
most well-studied numerical procedures—computing the best low-rank approximation of a
matrix using SVD. Many other algorithms for matrix completion can often be viewed as
approximate or noisy versions of SVP. More importantly, both NNM and SVP have proven
themselves as prototypes for designing more sophisticated algorithms tailored to additional
problem structures (e.g., clustering, ranking and matching/alignment problems). Hence,
an in-depth understanding of these two fundamental algorithms—which is the goal of this
paper—paves the way for designing and analyzing algorithms for more challenging settings.
In this sense, while we apply Leave-One-Out to NNM and SVP specifically, we believe
this technique is useful more broadly in studying other iterative procedures—convex or nonconvex—for matrix completion and related statistical problems with complex probabilistic
structures. When preparing this manuscript, we became aware of the concurrent work of
Ma et al. (2017), who use a related technique to analyze gradient descent procedures for
non-convex formulations of matrix completion and phase retrieval problems.
1.2. Related work and comparison
The Leave-One-Out technique, broadly defined, is a classical idea in studying statistical
problems with complicated probabilistic structures. It has been used to analyze highdimensional problems with random designs such as robust M-estimation (El Karoui et al.,
3

Leave-one-out Approach for Matrix Completion

2013) and linear regression with de-biased Lasso estimators (Javanmard and Montanari,
2015). More recently, the work of Zhong and Boumal (2017) applies this technique to
analyze the generalized power method (GPM) for the phase synchronization problem, and
the work of Abbe et al. (2017) uses it to study one-shot spectral algorithms for stochastic
block models, matrix completion and Z2 -synchronization. This technique has also been used
in Chen et al. (2017) to study spectral and gradient descent methods for computing the
maximum likelihood estimators with convex objectives in ranking problems with pairwise
comparisons. As mentioned, the contemporary work of Ma et al. (2017) applies it to study
the convergence behaviors of gradient descent for non-convex formulations.
Compared to these recent results, our use of the Leave-One-Out technique is different
in three major aspects:
1. The work of Ma et al. (2017) and Zhong and Boumal (2017) study the gradient descent and GPM procedures. Both procedures involve relatively simple iterations with
explicit and mostly linear operations. In contrast, the SVP iterations, which involve
computing singular values and vectors, are far more complicated. In particular, the
SVD of a matrix is a highly nonlinear function that is defined variationally and implicitly. This makes our problem significantly harder, and our analysis requires quite
delicate use of matrix perturbation and concentration bounds.
2. The work of Abbe et al. (2017) and Chen et al. (2017) study “one-shot” spectral methods, which only involve a single SVD operation. In contrast, SVP is an iterative procedure with multiple sequential SVD operations. As will become clear in our analysis,
even studying the second iteration of SVP involves a very different analysis than those
for one-shot algorithms. To further track the propagation of errors and dependency
across potentially an infinite number of iterations, we need to make use of careful
induction and probabilistic arguments.
3. For analyzing NNM, the Leave-One-Out technique is used in a very different context.
In particular, instead of studying an actually algorithmic procedure, here we use leaveone-out to study an iterative procedure that arises in the dual analysis of a convex
program.
The exact low-rank matrix completion problem is studied in the seminar work of Candès and Recht
(2009), who initialized the use of the nuclear norm minimization approach. Follow-up
work on NNM includes Candès and Tao (2010); Gross (2011); Recht (2011). The state-ofart sample complexity bound for NNM in exact matrix completion, established in Chen
(2015), takes the form O(µrd log2 d)—note the log2 d factor due to the use of sample
splitting in the Golfing Scheme. The work of Balcan et al. (2018) also establishes competing sample complexity result for a related convex optimization approach, along with
complementary results for an exponential-time algorithm. The SVP algorithm is first
proposed in Jain et al. (2010), although no rigorous guarantees are provided for matrix
completion. The follow-up work of Jain and Netrapalli (2015) establishes rigorous sample
complexity bounds via splitting the samples. Many other iterative algorithms have been
proposed and studied for matrix completion along with sample complexity bounds; a partial list includes Keshavan et al. (2010); Hardt and Wootters (2014); Sun and Luo (2016);
Chen and Wainwright (2015); Zheng and Lafferty (2016). A remarkable recent result shows
4

Leave-one-out Approach for Matrix Completion

that a nonconvex regularized formulation of matrix completion in fact has no spurious local
minima (Ge et al., 2016). Most of these iterative algorithms require a number of observations that depend on the condition number of the underlying matrix. We provide a detailed
quantitative comparison of these results after presenting our main theorems.
Organization In Section 2, we present our main results on the sample complexity for
NNM and the linear entrywise convergence of SVP. In Section 3 we discuss the main intuitions of our Leave-One-Out based technique, and provide a general recipe of using this
technique. Following this recipe, we prove our sample complexity bounds for NNM in Section 4. The paper is concluded with a discussion in Section 5. The proof for SVP is deferred
to the appendix.
Notation For an integer d > 0, we write [d] := {1, 2, . . . , d}. We use the standard bigO/Ω notations that hide universal constants, with a & b meaning a = Ω(b). Denote by
S d×d the set of symmetric matrices in Rd×d , ei the i-th standard basis vector in appropriate
dimension, and 1 the all-one vector. For a matrix A, let Ai· be its i-th row and A·j its j-th
column. The Frobenius norm, operator norm and nuclear norm of a matrix are denoted by
||| · |||F , ||| · |||op and ||| · |||nuc . We also use the notations kAk∞ := maxi,j |Aij | for the entrywise ℓ∞
norm, and kAk2,∞ := maxi kAi· k2 for the maximum row ℓ2 norm. For two matrices A, B
with compatible dimensions, we write A ⊗ B = AB T . The best rank-k approximation of A
in Frobenius norm is [A]r , and its i-th largest singular value is σi (A) (or simply σi if it is
clear in the context). We denote by I the identity operator on matrices. The operator norm
of a linear map A on matrices is |||A|||op := maxZ:|||Z|||F=1 |||A(Z)|||F . By with high probability
(w.h.p.), we mean with probability at least 1 − c1 (d1 + d2 )−c2 for some universal constants
c1 , c2 > 0, where d1 and d2 are the dimensions of the low-rank matrix M ∗ to be recovered.

2. Problem setup and main theorems
In this section, we formally set up the matrix completion problem, and state our main
results on nuclear norm minimization and Singular Value Projection.
2.1. Nuclear norm minimization
To present our results on NNM, we consider the following standard Bernoulli sampling
model for the matrix completion problem.
Definition 1 Suppose that M ∗ ∈ Rd1 ×d2 has rank r and p ∈ (0, 1]. Under the model
MC(M ∗ , p), we are given the partially observed matrix ΠΩ (M ∗ ), where the sampling operator
ΠΩ : Rd1 ×d2 → Rd1 ×d2 is given by [ΠΩ (A)]ij = Aij δij for each (i, j), and the observation
indicators {δij }i∈[d1 ],j∈[d2] are independent Bernoulli variables with distribution P(δij = 1) =
p = 1 − P(δij = 0). We denote by Ω := {(i, j) | δij = 1} the set of indices of the observed
entries.
The NNM approach involves solving the following convex program:
minimizeX∈Rd1 ×d2 |||X|||nuc

subject to ΠΩ (X) = ΠΩ (M ∗ ).
5

(1)

Leave-one-out Approach for Matrix Completion

Work
Chen (2015)
Keshavan et al. (2010)
Sun and Luo (2016)
Zheng and Lafferty (2016)
Balcan et al. (2018)
This paper
Lower bound in Candès and Tao (2010)

Sample Complexity pd2
2
O(µrd
 log d) 2 4 
2
O rdκ max µ log d, µ rκ 
O rdκ2 max µ log d, µ2 r 6 κ4
O(κ2 µr 2 d max{µ, log d})
O(κ2 µrd log d log2κ d)
O(µ2 r 3 d log d)
Ω(µrd log d)

Table 1: Comparison of sample complexity results for tractable algorithms for exact matrix
completion under the setting with d1 = d2 = d.
Our goal is to characterize when the NNM program (1) recovers the underlying low-rank
matrix M ∗ as the unique optimal solution. In order to quantify the difficulty of recovering
M ∗ , we consider the following standard measure of the incoherence of a matrix.
Definition 2 A matrix M ∈ Rd1 ×d2 with rank-r SVD M = U ΣV T is µ-incoherent if
r
r
µr
µr
and kV k2,∞ ≤
.
kU k2,∞ ≤
d1
d2
The incoherence condition will be imposed on M ∗ to avoid pathological situations where
most of the entries of M ∗ are equal to zero. In such situations, it is well-known that it is
impossible to complete M ∗ unless all of its entries are observed (Candès and Recht, 2009).
Also denote by κ := σ1 (M ∗ )/σr (M ∗ ) the condition number of M ∗ .
With the set-up above, we state our sample complexity result for NNM.
1 ,d2 })
Theorem 1 Under the model MC(M ∗ , p), if M ∗ is µ-incoherent and p & µ2 r 3 log(max{d
min{d1 ,d2 } ,
then with high probability M ∗ is the unique minimizer of the NNM program (1).

We prove this theorem in Section 4. In the setting with d1 = d2 = d, the theorem
shows that NNM recovers M ∗ with high probability provided that the expected number of
observed entries satisfies pd2 & µ2 r 3 d log d. Note that the sample complexity bound has only
one logarithmic term log d, and is independent of the condition number κ of M ∗ . A lower
bound on the sample complexity of matrix completion is established by Candès and Tao
(2010), who show that pd & µr log d is necessary for any algorithm to uniquely recover M ∗
with probability at least 3/4. Our bound hence has the correct dependence on d and κ, and
is sub-optimal in terms of the incoherence parameter µ and the rank r.
In Table 1 we compare our bound with the state-of-art sample complexity results for
polynomial-time algorithms (we omit other existing results that are strictly dominated by
the bounds presented here). The work of Chen (2015), which builds on earlier results on
NNM, establishes a bound that scales sub-optimally with log2 d, which is a fundamental
consequence of having to split Ω into log d subsets in the Golfing Scheme. The other previous
results in the table all have non-trivial dependence on the condition number κ. While it is
6

Leave-one-out Approach for Matrix Completion

common to see dependency of the time complexity on κ, the appearance of κ in the sample
complexity seems unnecessary. To the best of our knowledge, our result is the only one on
tractable algorithms that achieves optimal dependence on both the condition number and
the dimension; in particular, our result is not dominated by any existing results.
Before we proceed, we would like to note that the very recent work in Balcan et al.
(2018) obtains a sample complexity bound that matches the lower bound; their bound,
however, is achieved by an inefficient algorithm that has running time exponential in d.
2.2. Singular Value Projection
We now turn to the analysis of the SVP algorithm. For simplicity, we will work with the
setting where the true matrix M ∗ is symmetric and positive semidefinite. Our results can
be extended to the general asymmetric case either via a direct analysis, or by using an
appropriate form of the standard dilation argument (see, e.g., Zheng and Lafferty 2016),
though the proofs will become more tedious.
The symmetric matrix completion problem is defined as follows.
Definition 3 Suppose that M ∗ ∈ S d×d is symmetric positive semidefinite with rank r,
and p ∈ (0, 1]. Under the model SMC(M ∗ , p), we are given the partially observed matrix
ΠΩ (M ∗ ), where the sampling operator ΠΩ : Rd×d → Rd×d is given by [ΠΩ (A)]ij = Aij δij for
each (i, j), and the observation indicators {δij }j≤i∈[d] are independent Bernoulli variables
with distribution P(δij = 1) = p = 1 − P(δij = 0) and δji = δij . We denote by Ω := {(i, j) |
δij = 1} the set of indices of the observed entries.
To motivate the SVP algorithm, we consider a natural optimization formulation for
the above SMC(M ∗ , p) model, which involves solving the following rank-constrained leastsquares problem:
minimizeX∈S d×d

1
|||ΠΩ (X) − ΠΩ (M ∗ )|||2F
2

subject to rank (X) ≤ r.

(2)

SVP can be viewed as the projected gradient descent method applied to the above problem (2). In particular, let Pr be the projection operator onto the set of matrices with rank
at most r; that is, Pr (A) is the best rank-r approximation of A ∈ S d×d in Frobenius norm.
Then the SVP iteration with a step size ηt is given by


(3)
M 0 = 0;
M t+1 = Pr M t − ηt ΠΩ (M t ) − ΠΩ (M ∗ ) , t = 0, 1, 2, . . .

We will later fix a constant step size ηt = p1 . The rationale behind this choice is that if Ω
were independent of the quantity M t , then the expectation of M t − p1 (ΠΩ (M t ) − ΠΩ (M ∗ ))
would be exactly M ∗ . As is standard, we assume that p is known.1
The SVP algorithm is first proposed by Jain et al. (2010). They observe empirically
that the objective value |||ΠΩ (M t ) − ΠΩ (M ∗ )|||2F of the SVP iterate converges quickly to
zero. Based on this observation, they conjecture that the SVP iterate M t is guaranteed to
converge to M ∗ (Jain et al., 2010, Conjecture 4.3). We reproduce below their conjecture,
rephrased under our symmetric setting:
1. In practice p can be estimated accurately by the empirical observation frequency

7

|Ω|
.
d2

Leave-one-out Approach for Matrix Completion

′ > 0 depending on r and µ,
Conjecture 1 (Jain et al., 2010) For some constants Cr,µ , Cr,µ
d
the following holds with high probability under the model SMC(M ∗ , p) with p ≥ Cr,µ d log
d .
1
t
SVP with some fixed step size ηt = O( p ) outputs a matrix M of rank at most r such that
′ log 1 iterations; moreover, M t converges to M ∗ .
|||ΠΩ (M t ) − ΠΩ (M ∗ )|||2F ≤ ǫ after Cµ,r
ǫ

Jain et al provide theoretical evidences supporting this conjecture, though no complete
proof is given. The conjecture remains open since the proposal of SVP.
Using the Leave-One-Out technique, we are able to essentially establish the conjecture.
In fact, we prove a stronger result showing that the SVP iterate converges linearly to M ∗
entrywise in ℓ∞ norm.
Theorem 2 Under the model SMC(M ∗ , p), if M ∗ is µ-incoherent and p &
with high probability the SVP iterates in equation (3) satisfy the bound
t

∗

kM − M k∞

 t
1
≤
σ1 (M ∗ ),
2

for all t = 1, 2, 3, . . .

κ6 µ4 r 6 log d
,
d

then

(4)

We prove Theorem 2 in Appendix C. The theorem establishes, for the first time, the convergence of the original form of SVP where the same set of observed entries Ω is used in all
iterations, without any resampling or sampling splitting.
2.2.1. Warm-up: the equal eigenvalue case
The proof of Theorem 2 turns out to be quite long and technical. To provide intuitions, we
shall first prove the result in a simpler version of the SMC(M ∗ , p) model, where we assume
in addition that the non-zero singular values of M ∗ are known and all equal to 1. We call
this the SNM(M ∗ , p) model. This simpler case captures most of the essential elements and
difficulties of the full analysis.
Knowing the singular values, we only need to compute an estimate F t ∈ Rd×r of the
singular vectors of M ∗ . We therefore consider the following simplified SVP procedure:



1
t
t
∗
0
t+1
t
t
F = 0;
F
= SVDr F ⊗ F − ΠΩ (F ⊗ F ) − ΠΩ (M ) , t = 0, 1, 2, . . . (5)
p

Here SVDr is the operator such that for each A ∈ S d×d , SVDr (A) is the d-by-r matrix whose
columns are the eigenvectors associated with the r largest eigenvalues of A. We have the
following guarantee for this simplified SVP procedure. The proof is given in Appendix B.

Theorem 3 Under the model SNM(M ∗ , p), if M ∗ is µ-incoherent with all non-zero eigen4 6
values equal to 1 and p & µ r dlog d , then with high probability the SVP iterates in equation (5)
satisfy the bound
 t
1
t
t
∗
kF ⊗ F − M k∞ ≤
, for all t = 1, 2, 3, . . .
(6)
2

8

Leave-one-out Approach for Matrix Completion

Challenges in the analysis: Standard approaches for analyzing SVP often aim to prove
that F t ⊗ F t converges to M ∗ in Frobenius norm. To do this, one may try to show that the
operator ΠΩ satisfies a form of Restricted Isometry Property (RIP), so that ΠΩ (F t ⊗F t −M ∗ )
preserves the Frobenius norm of the error matrix F t ⊗F t −M ∗ (Jain et al., 2010). However,
RIP cannot hold uniformly for all low-rank matrices. Even when one restricts to incoherent
iterates F t ⊗ F t , the error matrix itself may not be incoherent but rather is the difference of
two incoherent matrices. A more severe challenge arises in showing that the error matrix will
retain the property needed for RIP to hold throughout the iterations—SVP has no explicit
mechanism to ensure such properties. We instead employ a different argument, based on
Leave-One-Out, that directly controls the quantity kF t − F ∗ k2,∞ . This allows us to show
that every row of factorized difference F t − F ∗ , and hence every entry of the error matrix
F t ⊗ F t − M ∗ as well, converge to zero linearly and simultaneously. A byproduct of our
analysis is that F t ⊗ F t remains incoherent throughout the iterations, although incoherence
and RIP are no longer needed explicitly in our convergence proof.

3. Intuitions and recipe of our Leave-One-Out-based approach
In this section, we describe the high-level intuitions of our Leave-One-Out-based approach
for studying a stochastic iterative procedure. We then provide a general recipe of employing
this approach in the analysis of concrete algorithms including NNM and SVP.
3.1. Intuitions of Leave-One-Out
Consider an iterative procedure as follows: Starting from a given θ 0 ∈ RN , one performs
the iterations
(7)
θ t+1 = F(θ t ; δ), t = 0, 1, . . . ,
where δ = (δ1 , . . . , δN ) ∈ RN represents the random data. (In a more general situation,
each δi can be a vector.) The map F is a possibly nonlinear and implicit transformation,
and let us assume that θ ∗ = 0 is a fixed point of F. Our goal is to understand the behaviors
of individual coordinates θit , i ∈ [N ] of the iterates. If F is a contraction in ℓ2 norm in the
sense that
kF(θ; δ) − F(θ̄; δ)k2 ≤ αkθ − θ̄k2 ,

uniformly for all θ, θ̄

for some α < 1 with high probability, then it is easy to show that the ℓ2 distance of iterate
to the fixed point kθ t k2 decreases geometrically to zero.
In some situations, however, one is interested in controlling the entrywise behaviors
of θ t , e.g., bounding its ℓ∞ norm kθ t k∞ . Using the worst-case inequality kθ t k∞ ≤ kθ t k2 ,
together with the above ℓ2 distance bound, is often far too loose. Worse yet, there are cases
where the ℓ2 contraction may not hold uniformly for all θ and θ̄; instead, only a restricted
version of it holds:
kF(θ; δ) − F(θ̄; δ)k2 ≤ αkθ̄ − θ̄k2 ,

∀θ, θ̄ : kθk∞ , kθ̄k∞ ≤ b

(8)

for some small number b. In this case, establishing convergence of θ t again requires one to
first control the ℓ∞ norm of θ t . We see these two types of difficulties in the analysis of SVP
9

Leave-one-out Approach for Matrix Completion

and nuclear minimization for matrix completion problems.
To overcome these challenges, we need to make use of the more fine-grained structures
of F and θ t . For illustration, we assume that iteration (7) is separable w.r.t. the data δ,
in the sense that
θit+1 = Fi (θ t ; δi ).
(9)
That is, the i-th coordinate of the iterate has explicit dependence only on the i-th coordinate
of the data δ. However, θit+1 also depends on all the coordinates of θ t , which in turn depends
on the entire date vector δ. Consequently, θ t+1 still depends implicitly on the entire random
vector δ.
On the other hand, the mapping F(θ; δ) is often not too sensitive to individual coordinates of θ. In this case, we expect that the randomness of δ propagates slowly across
the coordinates of θ, so the correlation between θit+1 and {δj , j 6= i} is weak (though they
are not completely independent). To formalize the above insensitivity property quantitatively, we assume that F satisfies, in addition to the restricted ℓ2 -contraction bound (8),
the following ℓ∞ Lipschitz condition
kF(θ; δ) − F(θ̄; δ)k∞ ≤ βkθ − θ̄k2 .

(10)

The value of β is often small, sometimes β ≪ α, since we are comparing l∞ norm with l2
norm. However, one should not expect that β < √1N ; otherwise we would have l∞ contraction, which is rare for the problems we consider.
To exploit the above properties (8)–(10), we employ a leave-one-out argument, which
allows us to isolate the effect of the dependency across coordinates. For each i, let δ(−i) =
(δ1 , . . . , δi−1 , 0, δi+1 , . . . , δN ) be the vector obtained from the original data vector δ by zeroing out the i-th coordinate. Consider the fictitious iteration (which is used only in the
analysis)
(11)
θ t+1,i = F(θ t ; δ(−i) ).
By construction, θ t+1,i is independent of δi . Then we have
|θit+1 | = |F(θ t ; δi )|

= |F(θ t ; δi ) − F(θ t,i ; δi ) + F(θ t,i ; δi )|

≤ kF(θ t ; δ) − F(θ t,i ; δ)k∞ + |F(θ t,i ; δi )|
| {z }
{z
}
|

≤ βkθ

t

(12)

Lipschitz term
discrepancy term
t,i
t,i
− θ k2 + |F(θ ; δi )|,

where the last line is due to the Lipschitz assumption (10), which bounds the “Lipschitz term” that measures the variation of F applied to two different iterates θ t and θ t,i .
The“discrepancy term” |F(θ t,i ; δi )| captures the effect of zeroing out the i-th coordinate of
the data δ. This term involves two independent quantities θ t,i and δi , which is often easy
to handle. To proceed, we need to bound the term βkθ t − θ t,i k2 , that is, showing that θ t,i
and θ t are proximal to each other. This is true intuitively, as θ t,i and θ t are computed from

10

Leave-one-out Approach for Matrix Completion

two sets of data that differ at only one coordinate. More precisely, we have the bound
kθ t+1 − θ t+1,i k2 = kF(θ t ; δ) − F(θ t,i ; δ(−i) )k2

≤ kF(θ t ; δ) − F(θ t,i ; δ)k2 + kF(θ t,i ; δ) − F(θ t,i ; δ(−i) )k2
(a)

= kF(θ t ; δ) − F(θ t,i ; δ)k2 + Fi (θ t,i ; δ) − Fi (θ t,i ; δ(−i) )
{z
} |
|
{z
}
l2 -contraction term

(13)

discrepancy term

(b)

≤ αkθ t − θ t,i k2 + |Fi (θ t,i ; δi ) − Fi (θ t,i ; 0)|;

here step (a) is due to the separability assumption (9), and step (b) can be established using
the ℓ2 -contraction bound (8) under the induction hypothesis kθ t k∞ ≤ b. The second term
in line (b) above again involves independent quantities and is easy to bound. In this case,
the bound above combined with an induction argument establishes a (often contracting)
upper bound on kθ t − θ t,i k2 , so θ t and θ t,i are close (often become closer) to each other
throughout the iterations.
To sum up, by using the above leave-one-out argument, we reduce the harder problem
of controlling the individual coordinates of θ t to two easier problems:
1. Controlling a quantity of the form Fi (θ; δi ) when θ and δi are independent;
2. Controlling a quantity of the form F(θ; δ) − F(θ̄; δ) in various norms, for which we
can make use of the restricted ℓ2 -contraction and Lipschitz properties of F. The
latter properties can often be established even when ℓ2 - or ℓ∞ -contraction fails to
hold uniformly.
3.2. Using the leave-one-out argument in our proofs
The analysis of NNM and SVP for matrix completion involves stochastic iteration procedures of the form (7) given in the last sub-section. Here the data δ consists of the observation indicators δij = 1{(i, j) ∈ Ω} = 1{Mij∗ is observed} given in Definitions 1 and 3.
For NNM, the dual certificate is constructed
using a procedure with F : Rd×d → Rd×d

given by F(·; δ) = PT − 1p PT ΠΩ (·), where PT is a linear operator to be defined later.
The (simplified)
in (5) corresponds
to an F : Rd×r → Rd×r given by


 SVP1 iteration
1
∗
F(·; δ) = SVDr I − p ΠΩ (· ⊗ ·) + p ΠΩ (M ) .
Dealing with these problems is of course more complicated than the example given in the
last sub-section. In particular, the separability and Lipschitz properties (8)–(10) may not
hold exactly as stated, or may be non-trivial to recognize and establish. Moreover, the high
probability bounds obtained from exploiting independence only hold for a finite number
of iterations due to the use of union bounds. Consequently, proving the desired results
requires additional steps that are sometimes quite technical. Nevertheless, the intuitions
remain valid. Below we summarize our strategy of using the leave-one-out technique for
our problems:
1. Introduce the leave-one-out sequence to the analysis as in equation (11) by appropriately defining the coordinate system and recognizing which coordinate of δ should
11

Leave-one-out Approach for Matrix Completion

be zeroed out. This can be done using a calculation similar to equation (12), which
exposes which δi can be left out to induce independence in the term F(θ t,i ; δi ).
2. Establish appropriate versions of the ℓ2 -contraction condition (8) and the ℓ∞ /ℓ2 Lipschitz condition (10). Use them to bound the Lipschitz, discrepancy and contraction terms in equations (12) and (13).
3. Perform induction steps on t based on the bounds (12) and (13).
4. To control an infinite number of iterations, we use the fact that the iterate θ t is already
close to 0 after finitely many iterations. In this case, we may exploit local properties
near 0 to establish uniform/deterministic bounds. It may also suffice to use a crude
bound kθ t k∞ ≤ kθ t k2 , as the right hand side is already sufficiently small.

4. Proof of Theorem 1
In this section, we apply our leave-one-out based technique to prove the sample complexity
bound in Theorem 1 for NNM. We assume that d = d1 = d2 for simplicity; the proof of the
general case follows exactly the same lines.
4.1. Preliminaries
Let the singular value decomposition of M ∗ be M ∗ = U ΣV T . We define the projections
PT (Z) : = U U T Z +ZV V T −U U T ZV V T and PT ⊥ (Z) : = Z −PT (Z) for a matrix Z ∈ Rd×d .
Introduce the shorthand RΩ : = 1p ΠΩ , which can be explicitly expressed as [RΩ (Z)]ij =
1
p δij Zij . We also define the operator HΩ : = I − RΩ and the linear subspace T : = {PT (Z) |
Z ∈ Rd×d }.
We make use of a standard result that provides sufficient conditions for the optimality
of M ∗ to the NNM formulation.
Proposition 1 (Chen, 2015, Proposition 2) Suppose that p ≥ d1 . The matrix M ∗ is the
unique optimal solution to the NNM problem (1) if the following conditions hold:
1. |||PT RΩ PT − PT |||op ≤ 21 .
2. There exists a dual certificate Y ∈ Rd×d that satisfies ΠΩ (Y ) = Y and
(a) |||PT ⊥ (Y )|||op ≤ 21 ,

(b) |||PT (Y ) − U V T |||F ≤

1
4d .

The first condition in Proposition 1 can be verified using the following well-known result
from the matrix completion literature.
Lemma 1 (Candès and Recht, 2009, Theorem 4.1; Chen et al., 2013, Lemma 11) If p &
µr log d
, then with high probability
d
1
|||PT RΩ PT − PT |||op ≤ .
4

12

Leave-one-out Approach for Matrix Completion

To prove Theorem 1 and establish optimality of M ∗ , it remains to construct the dual
certificate Y that satisfies the second set of conditions in Proposition 1. This is usually done
using the Golfing scheme developed in Candès et al. (2011); Gross (2011), where Ω is split
into log d independent subsets and Y is constructed iteratively using a different subset in
each iteration. Doing so induces independence across iterations and makes certain entrywise
bounds easier to establish; it however leads to sub-optimal sample complexity bounds. We
instead consider a procedure that uses the same Ω in all iterations. Let us first describe
our dual certificate construction procedure, and discuss why we need to establish entrywise
bounds.
Constructing the dual certificate:
U V T and

We consider an iterative procedure where W 0 : =

W t : = PT HΩ (W t−1 ) = [PT HΩ ]t (U V T ),

t = 1, 2, . . .

(14)

We claim that with t0 : = 2 log2 d + 2, the matrix
Y :=

t0
X
t=1

RΩ PT (W t−1 )

(15)

is the desired dual certificate. Indeed, with high probability Y satisfies the conditions 2(a)
and 2(b) in Proposition 1, as shown below:
Verifying the dual certificate:

For condition 2(b), Lemma 1 ensures that w.h.p.

1
|||W t |||F ≤ |||PT HΩ PT |||op |||W t−1 |||F ≤ |||W t−1 |||F
2

for all t = 1, 2, . . .

Applying the above inequality recursively with t = t0 , t0 − 1, . . . , 1 gives the desired bound:
 t0
1 √
1
1
|||U V T |||F ≤ 2 r ≤
.
|||PT (Y ) − U V T |||F = |||W t0 |||F ≤
2
4d
4d
For condition 2(a), let us assume for the moment that W t satisfies the ℓ∞ norm bound
t

kW k∞

 t
 t
1
1
1 µr
t−1
T
≤ kW k∞ ≤
,
kU V k∞ =
2
2
2
d

for all 1 ≤ t ≤ t0 .

(16)

Now, since each W t has rank at most 3r, Lemma 15 in Appendix D ensures that w.h.p.
s
√
d log d
(17)
kW t k∞ .
|||HΩ (W t )|||op ≤ 6c r
p
Combining with the assumed ℓ∞ bound (16) gives
t

|||HΩ (W )|||op

 t+2
1
≤
2

13

for all t ≤ t0 ,

(18)

Leave-one-out Approach for Matrix Completion

where we use the assumption that p &
in (15) that
t0
(a) X

|||PT ⊥ (Y )|||op ≤

t=1

r 3 µ2 log d
.
d

|||PT ⊥ (RΩ PT − PT )(W

t−1

It then follows from the definition of Y

)|||op ≤

t0
X
t=1

|||HΩ PT (W

t−1

t0  t+1
(b) X
1

)|||op ≤

t=1

2

≤

where step (a) holds because PT ⊥ PT (W t−1 ) = 0, and step (b) is due to PT (W t−1 ) = W t−1
and the inequality (18). Therefore, Y satisfies the condition 2(a) in Proposition 1 w.h.p.
To complete the proof of Theorem 1, it remains to establish the entrywise ℓ∞ bound (16)
for the iterative procedure (14). This step has been the bottleneck in the analysis of previous
work using Golfing Scheme. In the rest of this section, we establish inequality (16) by using
our leave-one-out based technique.
4.2. Proving inequality (16) by leave-one-out
The iterative procedure (14) can be written abstractly as W 0 = U V T , W t = F(W t−1 ),
where F = PT HΩ . Note that this is a special case of the general iterative procedure (7)
described in Section 3. We now analyze this procedure following the strategy outlined in
Section 3.2.
Introduce the leave-one-out sequence: Since we need to bound the matrix entrywise
(−w)
: Rd×d → Rd×d
norm, for each index w = (w1 , w2 ) ∈ [d] × [d] we define the operator HΩ
by
(


(1 − 1p δij )Zij , i 6= w1 and j 6= w2 ,
(−w)
=
HΩ Z
0,
i = w1 or j = w2 .
ij
(w)

(−w)

Also define HΩ : = HΩ − HΩ

W 0,w = U V T ;

. For each w, we introduce the leave-one-out sequence
(−w)

W t,w = (PT HΩ

)(W t−1,w ), t = 1, 2, . . .

These iterates have the property that W t,w is independent of {δw1 j }j∈[d] and {δiw2 }i∈[d] ,
namely, the randomness of Ω in the w1 -th row and w2 -th column. If we define F (−w) :=
(−w)
to match the notations in Section 3, then W 0,w = U V T and W t,w = F (−w) (W t−1,w ).
PT HΩ
Verify the Lipschitz condition and bound the discrepancy terms: We now state
a few lemmas useful in subsequent analysis; their proofs are deferred to Appendix A. In the
language of Section 3, these lemmas are used to establish the ℓ∞ /ℓ2 -Lipschitz condition (10)
and to bound discrepancy terms in (12) and (13). Note the ℓ2 contraction condition is
already established in Lemma 1 as F = PT HΩ is linear and all iterates belongs to T .
We first introduce a lemma corresponding to the ℓ∞ /ℓ2 -Lipschitz condition in (10).
Lemma 2 If p & µr log d/d, we have w.h.p.
r
1 µr
|||Z|||F , ∀Z ∈ T .
kPT HΩ (Z)k∞ ≤
2
d

14

1
,
2

Leave-one-out Approach for Matrix Completion

(To see the correspondence, note that all iterates W t , W t,w are in T and F = PT HΩ
is linear; therefore the Lipschitz condition kF(Z1 ) − F(Z
q 2 )k∞ ≤ β|||Z1 − Z2 |||F in (10) is
1
equivalent to kF(Z)k∞ ≤ β|||Z|||F , ∀Z ∈ T , where β = 2 µr
d .)

The next lemma bounds on the discrepancy term [F(W t,w )]w1 ,w2 = |[PT HΩ (W t,w )]w1 ,w2
in equation (12).
Lemma 3 If p &

r 3 µ2 log d
,
d

for each t we have w.h.p.

[PT HΩ (W t,w )]w1 ,w2 ≤

1
kW t,w k∞ ,
4

for all w ∈ [d] × [d].
(w)

Our last lemma bounds the discrepancy term |||(F−F (−w) )(W t,w )|||F = |||PT HΩ (W t,w )|||F
in equation (13).
Lemma 4 Suppose that p & µr log d/d. There exists a numerical constant c > 1 such that
for each t, we have w.h.p.
s
µr log d
(w)
t,w
kW t,w k∞ , for all w ∈ [d] × [d].
|||PT HΩ (W )|||F ≤ c
p
Induction on t: Equipped with the lemmas above, we are ready to prove the desired
inequality (16) by induction on t. Our induction hypothesis is
 t−1
1
t−1
kW 0 k∞ ,
(19)
kW k∞ ≤
2
 t−1
1
t−1,w
kW
k∞ ≤
kW 0 k∞ , ∀ w ∈ [d] × [d],
(20)
2
s
 
µr log d 1 t−2
t−1
t−1,w
kW 0 k∞ .
(21)
|||W
−W
|||F ≤ 2c
p
2
The constant c here is given in Lemma 4. The base case t = 1 is satisfied since W 0,w = W 0
for all w ∈ [d] × [d] by construction. Assuming that the inequalities (19)–(21) holds for t − 1,
we prove below that they also hold for t.
For inequality (19), we have w.h.p. for each w ∈ [d] × [d],
|Wwt | = |[PT HΩ (W t−1 )]w |

= | [PT HΩ (W t−1,w )]w +[PT HΩ (W t−1 − W t−1,w )]w |
{z
} |
{z
}
|
Discrepancy term

(a)

1
1
kW t−1,w k∞ +
4
2

ℓ2 contraction term

r

µr
|||W t−1 − W t−1,w |||F
d
s
 
(b) 1
µ2 r 2 log d 1 t−2
kW 0 k∞
≤ kW t−1,w k∞ + 2c
4
pd
2
 
(c) 1
1 1 t−2
t−1,w
≤ kW
k∞ +
kW 0 k∞
4
8 2
 
(d) 1 t
kW 0 k∞ ,
≤
2
≤

15

(22)

Leave-one-out Approach for Matrix Completion

where step (a) holds due to Lemma 2 and 3, step (b) uses the induction hypothesis (21),
step (c) holds because p & µ2 r 2 log d/d, and step (d) uses the induction hypothesis (20).
For inequality (20), we have w.h.p. for each v ∈ [d] × [d]
|Wvt,w | = |[PT HΩ (W t−1,v )]v + [PT HΩ (W t−1,w − W t−1,v )]v |

≤ |PT HΩ (W t−1,v )]v | + |PT HΩ (W t−1,v − W t−1 )]v | + |PT HΩ (W t−1,w − W t−1 )]v |
 t
1
≤
kW 0 k∞ ,
2

where the last step follows from a similar argument as in the inequalities (22).
Finally, for the proximity inequality (21), we have w.h.p.
(−w)

|||W t − W t,w |||F = |||PT HΩ (W t−1 ) − PT HΩ

(W t−1,w )|||F
(−w) 

≤ |||PT HΩ (W t−1 − W t−1,w )|||F + |||PT HΩ − HΩ
|
{z
} |
{z
Lipschitz term

(W t−1,w )|||F
}

discrepancy term

s

(a)

1
µr log d
|||W t−1 − W t−1,w |||F + c
kW t−1,w k∞
4
p
s
s
 
 
(b) 1
µr log d 1 t−2
µr log d 1 t−1
0
≤ × 2c
kW k∞ + c
kW 0 k∞
4
p
2
p
2
s
 
µr log d 1 t−1
kW 0 k∞ ,
≤ 2c
p
2
≤

where in step (a) we use Lemma 1 for the Lipschitz term and Lemma 4 for the discrepancy
term, and in step (b) we use the induction hypotheses (19) and (20). This completes the
induction step.
We perform the induction up to t = t0 = 2 log2 d + 2, which establishes our claimed
inequality (16) and completes the proof of Theorem 1.

5. Discussion
In this paper, we introduce a new Leave-One-Out based technique to analyze iterative procedures. This technique allows us to control entrywise norm and shows previous sample
splitting procedure is not necessary. We provide a simple recipe to employ this technique
and demonstrate its power in the context of matrix completion by (i) proving new sample
complexity of nuclear norm minimization with optimal dependence on dimension and condition number, and (ii) proving the conjecture in Jain et al. (2010) that the original form
of SVP converges linearly to the underlying matrix M ∗ .
In view of the success of our techniques in analyzing SVP and nuclear norm minimization
for matrix completion, we expect that this Leave-One-Out based approach can be applied
more broadly to study the fine-grained other iterative procedures that arise in statistical
learning and decision problems. Examples include proximal, stochastic gradient and alternating minimization methods for convex or nonconvex formulations, as well as stochastic
approximation type procedures for sequential learning and decision-making problems.
16

Leave-one-out Approach for Matrix Completion

Acknowledgments
L. Ding and Y. Chen were partially supported by the National Science Foundation CRII
award 1657420 and grant 1704828. Y. Chen would like to thank Yuxin Chen for inspiring
discussions.

References
Emmanuel Abbe, Jianqing Fan, Kaizheng Wang, and Yiqiao Zhong. Entrywise eigenvector
analysis of random matrices with low expected rank. arXiv preprint arXiv:1709.09565,
2017.
Maria-Florina Balcan, Yingyu Liang, David P Woodruff, and Hongyang Zhang. Matrix
completion and related problems via strong duality. In LIPIcs-Leibniz International Proceedings in Informatics, volume 94. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik,
2018.
Emmanuel J Candès and Benjamin Recht. Exact matrix completion via convex optimization. Foundations of Computational mathematics, 9(6):717, 2009.
Emmanuel J Candès and Terence Tao. The power of convex relaxation: Near-optimal
matrix completion. IEEE Transactions on Information Theory, 56(5):2053–2080, 2010.
Emmanuel J Candès, Xiaodong Li, Yi Ma, and John Wright. Robust principal component
analysis? Journal of the ACM (JACM), 58(3):11, 2011.
Yudong Chen. Incoherence-optimal matrix completion. IEEE Transactions on Information
Theory, 61(5):2909–2923, 2015.
Yudong Chen and Martin J Wainwright. Fast low-rank estimation by projected gradient
descent: General statistical and algorithmic guarantees. arXiv preprint arXiv:1509.03025,
2015.
Yudong Chen, Ali Jalali, Sujay Sanghavi, and Constantine Caramanis. Low-rank matrix
recovery from errors and erasures. IEEE Transactions on Information Theory, 59(7):
4324–4337, 2013.
Yuxin Chen, Jianqing Fan, Cong Ma, and Kaizheng Wang. Spectral method and regularized
mle are both optimal for top-k ranking. arXiv preprint arXiv:1707.09971, 2017.
Chandler Davis and William Morton Kahan. The rotation of eigenvectors by a perturbation.
iii. SIAM Journal on Numerical Analysis, 7(1):1–46, 1970.
Noureddine El Karoui, Derek Bean, Peter J Bickel, Chinghway Lim, and Bin Yu. On
robust regression with high-dimensional predictors. Proceedings of the National Academy
of Sciences, 110(36):14557–14562, 2013.
Jianqing Fan, Dong Wang, Kaizheng Wang, and Ziwei Zhu. Distributed estimation of
principal eigenspaces. arXiv preprint arXiv:1702.06488, 2017.

17

Leave-one-out Approach for Matrix Completion

Rong Ge, Jason D Lee, and Tengyu Ma. Matrix completion has no spurious local minimum.
In Advances in Neural Information Processing Systems, pages 2973–2981, 2016.
Rong Ge, Chi Jin, and Yi Zheng. No spurious local minima in nonconvex low rank problems:
A unified geometric analysis. arXiv preprint arXiv:1704.00708, 2017.
David Gross. Recovering low-rank matrices from few coefficients in any basis. IEEE Transactions on Information Theory, 57(3):1548–1566, 2011.
David Gross, Yi-Kai Liu, Steven T. Flammia, Stephen Becker, and Jens Eisert. Quantum
state tomography via compressed sensing. CoRR, abs/0909.3304, 2009.
Moritz Hardt and Mary Wootters. Fast matrix completion without the condition number.
In Conference on Learning Theory, pages 638–678, 2014.
Prateek Jain and Praneeth Netrapalli. Fast exact matrix completion with finite samples.
In Conference on Learning Theory, pages 1007–1034, 2015.
Prateek Jain, Raghu Meka, and Inderjit S Dhillon. Guaranteed rank minimization via
singular value projection. In Advances in Neural Information Processing Systems, pages
937–945, 2010.
Prateek Jain, Praneeth Netrapalli, and Sujay Sanghavi. Low-rank matrix completion using
alternating minimization. In Proceedings of the forty-fifth annual ACM symposium on
Theory of computing, pages 665–674. ACM, 2013.
Adel Javanmard and Andrea Montanari. De-biasing the lasso: Optimal sample size for
gaussian designs. arXiv preprint arXiv:1508.02757, 2015.
Raghunandan H Keshavan, Andrea Montanari, and Sewoong Oh. Matrix completion from
a few entries. IEEE Transactions on Information Theory, 56(6):2980–2998, 2010.
Ren-Cang Li. Relative perturbation theory: II. eigenspace and singular subspace variations.
SIAM Journal on Matrix Analysis and Applications, 20(2):471–492, 1998.
Cong Ma, Kaizheng Wang, Yuejie Chi, and Yuxin Chen. Implicit regularization in nonconvex statistical estimation: Gradient descent converges linearly for phase retrieval, matrix
completion and blind deconvolution. arXiv preprint arXiv:1711.10467, 2017.
Benjamin Recht. A simpler approach to matrix completion. Journal of Machine Learning
Research, 12(Dec):3413–3430, 2011.
Ruoyu Sun and Zhi-Quan Luo. Guaranteed matrix completion via non-convex factorization.
IEEE Transactions on Information Theory, 62(11):6535–6579, 2016.
Joel A Tropp. User-friendly tail bounds for sums of random matrices. Foundations of
computational mathematics, 12(4):389–434, 2012.
Vincent Q Vu, Jing Lei, et al. Minimax sparse principal subspace estimation in high dimensions. The Annals of Statistics, 41(6):2905–2947, 2013.
18

Leave-one-out Approach for Matrix Completion

Qinqing Zheng and John Lafferty. Convergence analysis for rectangular matrix completion using burer-monteiro factorization and gradient descent.
arXiv preprint
arXiv:1605.07051, 2016.
Yiqiao Zhong and Nicolas Boumal. Near-optimal bounds for phase synchronization. arXiv
preprint arXiv:1703.06605, 2017.

Appendix A. Proofs of Lemmas in Section 4
In this section, we prove the lemmas that are used in the proof of Theorem 1 in Section 4.
A.1. Proof of Lemma 2
Proof
For each fixed (i, j) ∈ [d] × [d], we have
eTi [PT HΩ (Z)]ej = hPT HΩ (Z), ei eTj i
(a)

= hPT HΩ PT (Z), ei eTj i

= hZ, PT HΩ PT (ei eTj )i

≤ |||Z|||F |||PT HΩ PT (ei eTj )|||F

(b)

1
|||Z|||F |||PT (ei eTj )|||F
4r
1 µr
≤
|||Z|||F ,
2
d
≤

where equality (a) is due to Z ∈ T , inequality (b) holds because |||PT HΩ PT |||op ≤
lemma 1, and the last inequality can be proved using the explicit form of PT .

1
2

by

A.2. Proof of Lemma 3
Proof
We first note that
[PT HΩ (W t,w )]w1 ,w2

= eTw1 PT HΩ (W t,w )ew2

= eTw1 [U U T HΩ (W t,w )]ew2 + eTw1 [HΩ (W t,w )V V T ]ew2 − eTw1 [U U T HΩ (W t,w )V V T ]ew2 ,
{z
} |
{z
} |
{z
}
|
T1

T2

T3

19

(23)

Leave-one-out Approach for Matrix Completion

where the last equality is due to the explicit expression of PT . We start with bounding the
term T3 . We have
eTw1 [U U T HΩ (W t,w )V V T ]ew2 = hHΩ (W t,w ), U U T ew1 eTw2 V V T i

≤ |||HΩ (W t,w )|||op |||U U T ew1 eTw2 V V T |||nuc
= |||HΩ (W t,w )|||op |||U U T ew1 eTw2 V V T |||F
(a)

= |||HΩ (W t,w )|||op |||U T ew1 eTw2 V |||nuc

(b)

= |||HΩ (W t,w )|||op kU T ew1 k2 kV T ew2 k2
s
√
d log d
µr
≤ 6c r
kW t,w k∞
p
d
1
kW t,w k∞ ,
≤
12
where equalities (a) and (b) hold because U U T ew1 eTw2 V V T is rank 1 and the last inequality
2 3
is due to p & µ r dlog d .
For the term T1 , since W t,w is independent of δkw2 , we have
eTw1 [U U T HΩ (W t,w )]ew2 = h[U U T ]w1 · , [HΩ (W t,w )]·w2 i


X
1
t,w
T
=
[U U ]w1 k 1 − δkw2 Wkw
2
p
1≤k≤d,k6=w1
s
(a)
C log d
CkU U T k∞ kW t,w k∞ log d
≤
k[U U T ]w1 · k2 kW t,w k∞ +
p
p
s
(b)
C log d µr
µr C log d
kW t,w k∞ +
kW t,w k∞
≤
p
d
d pd
(c)

≤

1
kW t,w k∞
12

with probability at least 1 − dC/2 . Inequality (a) holds because W t,w is independent of
δkw2 and Bernstein inequality. Inequality (b) follows from the fact that kU U T k∞ ≤ µr
d
d
and inequality (c) is due to p & rµ log
.
If
we
take
C
=
12
and
note
there
are
only
d
×
d
d
rµ log d
many pair of (w1 , w2 ), we see that as long as p & d , the bound holds uniformly for all
w ∈ [d] × [d].
The term T2 can be bounded similarly as T1 . This proves the lemma.

A.3. Proof of Lemma 4
Proof

20

Leave-one-out Approach for Matrix Completion

We have
(w)

(w)

(w)

(w)

|||PT HΩ (W t,w )|||F = |||U U T HΩ (W t,w ) + HΩ (W t,w )V V T − U U T HΩ (W t,w )V V T |||F
(w)

(w)

(w)

(w)

(w)

≤ |||U U T HΩ (W t,w )|||F + |||HΩ (W t,w )V V T |||F + |||U U T HΩ (W t,w )V V T |||F
(w)

≤ |||U U T HΩ (W t,w )|||F + |||HΩ (W t,w )V V T |||F | + |||U U T HΩ (W t,w )|||F
(w)

(w)

= 2|||U T HΩ (W t,w )|||F + |||HΩ (W t,w )U |||F .

We only need to analyze the first term; the second term is similar. Since only w1 -row and
(w)
w2 -column of HΩ (W t,w ) are nonzero,

 ((w))
(w)
(w)
|||U T HΩ (W t,w )|||F ≤ kU T HΩ (W t,w ) ·w2 k2 + |||U T ew1 eTw1 HΩ (W t,w )|||F .
{z
}
|
{z
} |
T2

T1

Consider T1 . We have

T1 =

sX
l≤r

 (w)

2
(U·l )T HΩ (W t,w ) ·w2 .

For each summand, we have with probability 1 − d−C/2

 (w)

 (w)
U·l HΩ (W t,w ) ·w2 = hU·l , HΩ (W t,w ) ·w2 i
X
δkw2
t,w
=
Ukl (1 −
)Wkw
2
p
k≤d
s
(a)
log d
C log d
≤ C
kU·l k2 kW t,w k∞ +
kW t,w k∞ kU·l k∞
p
p
s
s
r s
(b)
C log d
µr
log
d
log d
kW t,w k∞ +
kW t,w k∞
≤
p
d
p
p
s
log d
≤c
kW t,w k∞ .
p
Inequality (a) holds because of the independence between W t,w2 and δkw2 . Inequality (b) is
due to p & µr log d/d. It follows that for a large c and C, we have w.h.p. for all w ∈ [d] × [d],
s
r log d
kW t,w k∞
T1 ≤ c
p
if p & µr log d/d.
For T2 , we have
T2 =

sX
l≤r

(w)

k(U·l )T ew1 eTw1 HΩ (W t,w )k22 .

21

Leave-one-out Approach for Matrix Completion

For each summand, we have
(w)

(w)

k(U·l )T ew1 eTw1 HΩ (W t,w )k2 = |Uw1 l |k[HΩ (W t,w )]w1 · k2


1
≤ |Uw1 l | kW t,w k2 + k[ΠΩ (W t,w )]w1 · k2
p


(a)
√
1p
t,w
t,w
dkW k∞ +
2pdk[ΠΩ (W )]w1 · k∞
≤ |Uw1 l |
p
s
d
≤ 3|Uw1 l |
kW t,w k∞ ,
p
P

where we use that w.h.p.

k δkw1

≤ 2pd, ∀w1 ∈ [d] in (a). It follows that
s
sX
d
kW t,w k∞
T2 ≤ 3
|Uw1 l |2
p
l≤r
s
d
kW t,w k∞
= 3kUw1 · k2
p
r
µr
≤3
kW t,w k∞ .
p

Combining the pieces, we get
s

(w)

|||U T HΩ (W t,w )|||F ≤ T1 + T2 ≤ c

µr log d
kW t,w k∞ .
p

Appendix B. Proof of Theorem 3
We prove Theorem 3 in this section.
B.1. Setup and Proof outline
We want to recover M ∗ = F ∗ ⊗ F ∗ which is an unknown rank r matrix with eigenvectors
F ∗ ∈ Rd×r and all one eigenvalues. The fact that M ∗ is µ-incoherent with all eigenvalues 1
implies that
(
r
kM ∗ k∞ ≤ µr
µr
d , q
∗
kF k2,∞ ≤
=⇒
µr
∗ k ≤
d
maxi kMi−
2
d .

Recall the operator ΠΩ : Rd×d → Rd×d is defined as [ΠΩ (A)]ij = Aij δij for all i, j ∈
[d], A ∈ Rd×d . We define HΩ : = I − p1 ΠΩ . The SVP iteration in (5) can be rewritten as
F 0 = 0;



F t+1 = SVDr M ∗ + HΩ F t ⊗ F t − M ∗ .
22

Leave-one-out Approach for Matrix Completion

Proof Outline

Our proof is split into three stages:

1. We first prove that the first iteration gives us a good entrywise bound, i.e.,
 1 r
1
1
µr
1
∗
min
kF − F k2,∞ ≤ 2 2
∗
∗
∗
F ⊗F =M
64 µr 2
d

(24)

4 6

in Subsection B.2 as long as p & µ r dlog d . The additional factor 6421µr2 of the RHS
of inequality (24) is due to a technicality in inequalities (65) and (66) as we will see
later. The first step utilizes our Leave-One-Out based technique in Section 3.
2. We will then prove that as long as p &
t

min

F ∗ ⊗F ∗ =M ∗

µ4 r 6 log d
d

∗

kF − F k2,∞

 t r
1
1
µr
≤ 2 2
64 µr 2
d

(25)

for all 2 ≤ t ≤ t0 : = 5 log2 d + 12 in Subsections B.3, B.4 and B.5 by following our
Leave-One-Out based technique in Section 3. Inequalities (24) and (25) together with
Lemma 9 implies the following inequality
 
r 1 t
t
t
∗
.
(26)
kF ⊗ F − M k∞ ≤
d 2
3. Finally, since after t0 = 5 log2 d + 12 number of iteration, M t = F t ⊗ F t is extremely
close to M ∗ and hence incoherent, we use Proposition 2, a form of RIP condition, to
deduce linear convergence of |||M t − M ∗ |||F , i.e.,
 t0  t−t0
1
1
|||F t ⊗ F t − M ∗ |||F ≤
(27)
2
2
for all t > t0 w.h.p. in Subsection B.6 if p &

µ4 r 6 log d
.
d

Inequalities (26) and (27) then imply that
t

t

∗

kF ⊗ F − M k∞
for all t ≥ 1 w.h.p. as long as p &
.

µ4 r 6 log d
d

 t
1
≤
2

(28)

and we are done.

Introduce leave-one-out sequence Since we want to control entrywise norm, for each
m ∈ [d], we consider the following fictitious iteration: with F 0,m = 0 and


(m)
F t+1,m = SVDr M ∗ + HΩ F t,m ⊗ F t,m − M ∗ ,
(m)

where HΩ is the operator derived from HΩ but with the m-th row and m-column fully
observed; that is,
(


(1 − 1p δij )Zij , i 6= m, j 6= m,
(m)
.
=
HΩ Z
0,
i = m or j = m
ij
23

Leave-one-out Approach for Matrix Completion

These iterates have the property that F t,m is independent of the m-th row of Ω, i.e.,
independent of δij for i or j equals m.

(m)
Let the error matrices be E t = E t,0 : = HΩ F t ⊗ F t − M ∗ and E t,m : = HΩ F t,m ⊗

(0)
F t,m − M ∗ . Also let F t,0 = F t , HΩ = HΩ . We denote the reconstructed matrices from
F t,i to be M t,i = F t,i ⊗ F t,i for all t, i. For every i, m ∈ {0} ∪ [d], we denote ∆t,m =
F t,m − (F ∗ )t,m where (F ∗ )t,m = arg minF ∗ (F ∗ )T =M ∗ kF t,m − F ∗ k2,∞ and D t,m,i = F t,m −
F t,i,m,∗ where F t,i,m,∗ = F t,i Ot,i,m for O t,i,m = arg minOOT =I,O∈Rr×r |||F t,m − F t,i O|||F . We
denote D t,m = D t,0,m . The quantity ∆t,m measures the difference of F t,m to F ∗ and
D t,m,i measure the differences between the leave-one-out sequences. For each t, we denote
∆t,∞ = arg max∆t,m k∆t,m k2,∞ and D t,∞ = arg maxDt,i,m |||D t,i,m |||F .
We will use c, C to denote generic numerical constants in the following. They may differ
from line to line.
B.2. Step 0: Induction hypothesis and base case t = 1
We will follow our proof outline in Section B.1. Since the SVDr is really implicit, it is not
easy to direct verify the Lipschitz and contraction conditions and bounds on discrepancy
term in inequalities (12) and (13) in Section 3. Instead, we start with the definition of
eigenvalue and eigenvectors and see how to continue this step.
To prove inequality (25) for all 1 ≤ t ≤ t0 , we use induction on t ≤ t0 = 5 log2 d + 12.
The induction hypothesis is that for all i, j ∈ {0, . . . , d}
r
 t r
1
µr
µr
1
t,i
t,i
∗ t,i
=⇒ kF k2,∞ ≤ 2
,
(ℓ2,∞ error bound) kF − F O k2,∞ ≤ 2 2
64 µr 2
d
d
 t r
1
1
µr
t,i
t,j i,j,t
(proximity) |||F − F Q |||F ≤ 2 2
64 µr 2
d
for some Ot,i ∈ Rr×r , Qi,j,t ∈ Rr×r with O t,i ⊗ Ot,i = I and Qi,j,t ⊗ Qi,j,t = I. The above
two inequality are surely equivalent to
r
 t r
1
1
µr
µr
t,i
t,∞
=⇒ kF k2,∞ ≤ 2
,
(ℓ2,∞ error bound) k∆ k2,∞ ≤ 2 2
64 µr 2
d
d
 t r
1
1
µr
t,∞
(proximity) |||D |||F ≤ 2 2
.
64 µr 2
d
B.2.1. Preliminary calculation of the base case t = 1
Let us fix an index i ∈ {0, . . . , d} and an index m ∈ [d].
Let Λ0,i be the diagonal matrix with top r eigenvalue of M ∗ + E 0,i . The definition of
1,i
F gives
(M ∗ + E 0,i )F 1,i = F 1,i Λ0,i .

24

Leave-one-out Approach for Matrix Completion

Now focusing on the m-th row and letting O ∈ Rr×r , OO T = I to be chosen later, we
have
1,i
∗
Fm·
− Fm·
O

=eTm (M ∗ + E 0,i )F 1,i (Λ0,i )−1 − eTm F ∗ O

=eTm F ∗ (F ∗ )T F 1,i (Λ0,i )−1 + eTm E 0,i F 1,i (Λ0,i )−1 − eTm F ∗ O


=eTm F ∗ (F ∗ )T F 1,i (Λ0,i )−1 − O + eTm E 0,i F 1,i (Λ0,i )−1




= eTm F ∗ (F ∗ )T F 1,i − O + eTm F ∗ (F ∗ )T F 1,i (Λ0,i )−1 − I + eTm E 0,i F 1,i (Λ0,i )−1 .
{z
}
{z
} |
{z
} |
|
T1

T2

T3

A bound of |||E 0,i |||op :
|||E 0,i |||op

The error E 0,i is bounded by
s
 1
(a)

d log d µr (b) 1
1
1
(i)
∗
= |||HΩ M |||op ≤ 2c
,
≤
2
2
p
d
16 64 µr 2

where inequality (a) is due to Lemma 14 and inequality (b) is due to p &

(29)

µ4 r 6 log d
.
d

The first term T1 : Let the singular value decomposition of (F ∗ )T F 0,i ∈ Rr×r to be
U cos ΘV T , where cos Θ = diag(cos θ1 , . . . , cos θr ) ∈ Rr×r . The matrix Θ = diag(θ1 , . . . , θr )
is the principal angles matrix between F ∗ and F 1,i . By Davis-Kahan, Lemma 17, we have
||| sin Θ|||op ≤

|||E 0,i |||op
.
1 − |||E 0,i |||op

(30)

Then we can take O = U V T which is independent of m and OO T = I to get


keTm F ∗ (F ∗ )T F 1,i − O k2 ≤ kF ∗ k2,∞ |||(F ∗ )T F 1,i − O ||op
r
µr
=
|||U cos ΘV T − U V T |||op
d
r
µr
=
||| cos Θ − I|||op
d
r
(a)
µr
||| sin Θ|||2op
≤
d
r
(b)
|||E 0,i |||2op
µr
≤
d (1 − |||E 0,i |||op )2
 1 2

1
1
1
r
642 µr 2 16 2
(c)
µr
≤

 1 2
d
1
1
1 − 6421µr2 16
2
r  1
1
µr 1
1
.
≤
100 642 µr 2
d 2
Here step (a) is due to maxi (1 − cos θi ) ≤ maxi (1 − cos2 θi ) = maxi sin2 θi . We use the
bound of ||| sin Θ|||op shown in inequality (30) in step (b) and the bound of |||E 0,i |||op in step
(c).
25

Leave-one-out Approach for Matrix Completion

The second term T2 :

Weyl’s inequality gives
0,i

|||Λ

0,i

− I|||op ≤ |||E |||op

 1
1
1
1
≤
.
2
2
16 64 µr 2

The second term T2 can be bounded as follows


keTm F ∗ (F ∗ )T F 1,i (Λ0,i )−1 − I k2


≤keTm F ∗ (F ∗ )T F 1,i k2 ||| (Λ0,i )−1 − I |||op


≤keTm F ∗ k2 |||(F ∗ )T F 1,i |||op ||| (Λ0,i )−1 − I |||op
r  1
1 1
µr 1
.
≤
2
2
8 64 µr
d 2
The third term T3 :
follows

Using the bound on |||E 0,i |||op , we could bound the third term as

keTm E 0,i F 1,i (Λ0,i )−1 k2 ≤ keTm E 0,i F 1,i k2 |||(Λ0,i )−1 |||op
1
≤ keTm E 0,i F 1,i k2
 1 .
1
1
1 − 642 µr2 16 12
Putting together: Combining all the bounds, we see that by choosing O = U V T where
U, V are the left and right singular vectors of (F ∗ )T F 0,i , we have
1,i
∗
− Fm·
Ok2
kFm·
r  1
µr 1
1 1
+ keTm E 0,i F 1,i k2
≤
2
2
4 64 µr
d 2

1
1−

1
1
642 µr 2 16

 1 .

(31)

1
2

B.2.2. Bounding the term keTm E 0,i F 1,i k2

We next show how to bound keTm E 0,i F 1,i k2 and finishqthe induction on ℓ2,∞ error bound
for the base case. The goal is to have an additional c µr
d term with some small constant

c < 1. Note that if i = m, then eTm E 0,i is zero and we are done. So in the following, we
assume i 6= m.
Let Q ∈ Rr×r and QQT = I where the exact value is left to be determined later. We
have
eTm E 0,i F 1,i
=eTm E 0,i F 1,m Q + eTm E 0,i (F 1,i − F 1,m Q)
(i)

= eTm HΩ (−M ∗ )F 1,m Q + eTm E 0,i (F 1,i − F 1,m Q) .
{z
}
{z
} |
|

(32)

T2

T1

Verify Lipschitz condition and bound discrepancy term of inequality (12) We
note that T1 is similar to the discrepancy term in inequality (12) in Section 3 and T2 is
similar to the Lipschitz term there. This step is like the inequality (12) there.
26

Leave-one-out Approach for Matrix Completion

The first term T1 :

For T1 , we bound it as follows
(i)

kT1 k2 = keTm HΩ (−M ∗ )F 1,m k2
 X

d
√
1
1,m
∗
(1 − δmk )(−Mmk
≤ r max
)Fkj
.
j≤r
p

(33)

k=1

Since F 1,m is independent of δmk for all k, using Lemma 10 with F = F 0,m = 0, and C = 12,
we have for any j ≤ r with probability 1 − d−6 ,
d
X
1
1,m
∗
(1 − δmk )(−Mmk
)Fkj
|
p
i=1
s
 C log d 1,m
C log d 1,m
kF k2,∞ kF ∗ k2,∞ |||F ∗ |||op +
kF k2,∞ kF ∗ k2,∞ kF ∗ k2,∞ ) .
≤
p
p
{z
}
|
{z
} |

|

R2

R1

Later, we will see that we need this inequality holds for all pair of i, m ∈ {0} ∪ [d] simultaneously. Since each happens with 1 − d−6 , by union bound, we still have w.h.p., the above
inequality holds for all combination of i, m, j.
The first term R1 can be bounded as follows
s
(a)
C log d
(k∆1,m k2,∞ + kF ∗ k2,∞ )(k∆0,m k2,∞ )
R1 ≤
p
s
r
C log d
µr
1,m
(k∆ k2,∞ +
)(k∆0,m k2,∞ )
≤
p
d
s
s
C log(d)µr 0,m
C log(d) 0,m
=
k∆ k2,∞ +
k∆ k2,∞ k∆1,m k2,∞
pd
p
s
(b)
1
1
C log(d)µr 1,m
√
≤
k∆0,m k2,∞ +
k∆ k2,∞
2
2
16 × 2 r 64 µr
pd
(c)

≤

1
1
1
√
k∆0,m k2,∞ + √ k∆1,m k2,∞ .
16 × 2 r 642 µr 2
16 r

Inequality (a) is due to triangular inequality applied to the term kF 1,m k2,∞ and that k·k2,∞
is invariant under right multiplication
of unitary matrix. Inequality (b) holds because
q
k∆0,m k2,∞ = kF ∗ k2,∞ ≤

µr
d

and p &

log(d)µ4 r 6
.
d

27

We have inequality (c) because p &

Leave-one-out Approach for Matrix Completion

log(d)µ4 r 6
.
d

The second term R2 can be bounded as follows
r

C log d
µr 0,m
1,m
∗
(k∆ k2,∞ + kF k2,∞ )
k∆ k2,∞
R2 ≤
p
d
r
r
µr
C log d µr
(k∆1,m k2,∞ +
)k∆0,m k2,∞
≤
p
d
d
r
C log d µr 0,m
3Cµr log d 0,m
=
k∆ k2,∞ k∆1,m k2,∞ +
k∆ k2,∞
p
d
dp
(b)
1
1
1
√
≤ √ k∆1,m k2,∞ +
k∆0,m k2,∞ .
16 r
16 × 2 r 642 µr 2
(a)

Inequality (a) is due to triangular inequality applied to the term kF 1,m k2,∞ and that k·k2,∞
is invariant under right multiplication of unitary matrix. Inequality (b) is due to p &
log(d)µ4 r 6
.
d
Putting the two together, we have the following bound of T1
kT1 k2 ≤

√

 X

d
1
1,m
0,m
∗
(1 − δmk )(Mmk
)Fkj
− Mmk
j≤r
p

r max

k=1

(34)

1
1
1
k∆0,m k2,∞ .
≤ k∆1,m k2,∞ +
2
8
8 × 2 64 µr 2
The T2 term:

We choose Q so that F 1,i − F 1,m Q = D 1,i,m . We have
(i)

kT2 k2 = keTm E 0,i (F 1,i − F 1,m Q)k2 = keT HΩ (M ∗ )D 1,i,m k2
(a)

(i)

≤ |||HΩ (M ∗ )|||op |||D 1,i,m |||F
s
(b)
d log d
≤ 2c
kM ∗ k∞ |||D 1,i,m |||F
p
s
d log d µr 1,i,m
|||D
|||F
≤ 2c
p
d

(c)

≤

1 1,i,m
|||D
|||F ,
8

where (a) is due to Cauchy-Schwaz, (b) is due to Lemma 14, and (c) is due to p &
To proceed, we analyze D 1,i,m separately.
The term D 1,i,m

(35)

µ4 r 6 log d
.
d

Recall that


(i)
F 1,i = SVDr M ∗ + HΩ (−M ∗ ) ,



(m)
F 1,m = SVDr M ∗ + HΩ (−M ∗ ) .
(i)

Due to Weyl’s inequality, M ∗ +HΩ (−M ∗ ) has eigen gap between r-th and r+1-th eigenvalue
at least δ = 1 − 2|||E 0,i |||op .
28

Leave-one-out Approach for Matrix Completion

(i)

(i)

(m)

Let W = (HΩ − HΩ )(M ∗ ) which is the perturbation matrix between M ∗ + HΩ (−M ∗ )
(m)
1
and M ∗ + HΩ (−M ∗ ). We have |||W |||op ≤ |||E 0,i |||op + |||E 0,m |||op ≤ 16
from the analysis of
1
0,i
0,i
|||E |||op in equation (29) and so δ = 1 − 2|||E |||op ≥ 1 − 16 .
By Davis-Kahan, Lemma 17, we have
√
√
2|||W F 1,m |||F
2|||W F 1,m |||F
1,i,m
≤
≤ 2|||W F 1,m |||F .
(36)
|||D
|||F ≤
δ − |||W |||op
7/8
Bound the discrepancy term of inequality (13) We now perform a step corresponds
to inequality (13). There is no ℓ2 contraction term here since all F t,0 = 0.
(0)

(m)

The case i = 0 First consider the case i = 0. Under this scenario, we have HΩ − HΩ
being supported only on the m-th row and column. Thus
v
uX X
X X


δmk
δmk
u
1,m
∗ F 1,m 2 +
∗ F 1,m 2
(1 −
)Mmk
)Mmk
(1 −
|||W F |||F = t
mj
kj
p
p
j≤r k≤d

j≤r k≤d,k6=m

v
uX
u
1,m 2
= t (Fmj
)
j≤r

v
uX
u
1,m 2
≤ t (Fmj
)
j≤r

X

((1 −

k≤d,k6=m

X X

δmk
δmk
∗ )2 +
∗ F 1,m 2
)Mkm
)Mmk
(1 −
kj
p
p
j≤r k≤d

v
uX X
X

δmk
δmk
∗ )2 + u
∗ F 1,m 2
t
)Mkm
)Mmk
(1 −
((1 −
kj
p
p
j≤r k≤d

k≤d,k6=m

v
u X
X
√
δmk
δmk
u
1,m
∗
∗ )2 + r max
)Mmk
)Mmk
Fkj
≤ kF 1,m k2,∞ t
((1 −
(1 −
j≤r
p
p
k≤d,k6=m

k≤d

(a)

≤ (k∆1,m k2,∞ + kF ∗ k2,∞ )kHΩ (M ∗ )em k2 +
r

X
√
δmk
1,m
∗
Fkj
)Mmk
r max
(1 −
j≤r
p
k≤d

X
√
δmk
µr
1,m
∗
≤ (k∆1,m k2,∞ +
(1 −
Fkj
)|||HΩ (M ∗ )|||op + r max
)Mmk
j≤r
d
p
k≤d
s
r
X
(c)
√
µr
d log d µr
δmk
1,m
∗
(1 −
≤ (k∆1,m k2,∞ +
)(2c
) + r max
)Mmk
Fkj
j≤r
d
p
d
p
k≤d
r
 1
1 1
1
µr
1
k∆1,m k2,∞ +
.
≤
2
2
32
32 2 64 µr
d
(b)

1,m and step (b) holds because
Here step (a)
q is due to triangular inequality applied to ∆
∗
kF ∗ k2,∞ ≤ µr
d . In step (c), we bound |||HΩ (M )|||op using Lemma 14. The second term of
inequality (c) can be bounded as T1 in Subsection B.2.2 using Lemma 10 and is less than
 1 q
log(d)µ4 r 6
µr
1
1
1
1,m
k2,∞ + 32 642 µr2 21
.
64 k∆
d using p &
d

29

Leave-one-out Approach for Matrix Completion

Combining the above with the bound of D 1,0,m in inequality (36), we have for any
m ∈ [d],
 1 r
µr
1
1
1
1
1,0,m
1,m
|||D
|||F ≤ k∆ k2,∞ +
.
(37)
2
2
16
16 64 µr 2
d
The case i 6= 0 Let Q1 , Q2 be matrices Qi ∈ Rr×r and Qi QTi = I for i = 1, 2. We
determine the choice of Q1 , Q2 later. Then we have
(a)

|||D 1,i,m |||F ≤ |||F 1,i − F 1,m Q1 |||F

≤ |||F 1,i − F 1,0 Q2 |||F + |||F 1,0 Q2 − F 1,m Q1 |||F

(b)

≤ |||D 1,0,i |||F + |||D 1,0,m |||F

(38)

 1 r
1
1 1
µr
1 1,∞
.
≤ k∆ k2,∞ +
2
2
8
8 64 µr 2
d

(c)

Here inequality (a) is due to the optimality in defining D 1,i,m . Inequality (b) is that we
first choose Q2 to be the Q⋆2 which minimizes |||F 1,i − F 1,0 Q2 |||F and then we choose Q1 so
that |||F 1,0 Q⋆2 − F 1,m Q1 |||F is minimized as well. For the optimal Q1 , the quantity |||F 1,0 Q⋆2 −
F 1,m Q1 |||F is the same as |||D 1,0,m |||F due to unitary invariance of Frobenius norm. Inequality
(c) is what we just proved for D 1,0,m .
B.2.3. Complete the proof of the induction hypothesis for the base case
Combing inequality (31), and bounds on T1 , T2 , i.e., inequalities (32),(35) and (38), we have
(a)

1,i
∗
k∆1,i
m· k2 ≤ kFm· − Fm· Ok2
 1 r
(b) 1
1
1
1
µr
≤
+ keTm E 0,i F 1,i k2
1
2
2
4 64 µr 2
d
1 − 16
r

 1
(c) 1
1
1 1,m
1
µr 8
+
×
k∆ k2,∞
≤
4 642 µr 2 2
d
7
8

 1 r 
1
1
1
1
1
µr
1
0,m
1,∞
k∆ k2,∞ + k∆ k2,∞ +
+
8 × 2 642 µr 2
64
64 642 µr 2 2
d
r



1
(d) 1
µr 8
1
1
1
≤
+ × k∆1,∞ k2,∞
4 642 µr 2 2
d
7
8
r
 1 r 
1
1
1
1
1
µr
µr
1
1,∞
+ k∆ k2,∞ +
+
8 × 2 642 µr 2
d
64
64 642 µr 2 2
d
 1 r
1
µr 1 1,∞
1 1
+ k∆ k2,∞ .
≤
2 642 µr 2 2
d
6

(39)

Here inequality (a) is due to the optimality of ∆1,i , and (b) is due to inequality (31).
Inequality (c)qis due to the bound on T1 and T2 . We use the fact that when t = 0,
k∆0,∞ k2,∞ ≤

µr
d

in inequality (d).

30

Leave-one-out Approach for Matrix Completion

Since the above holds for all i, m, taking maximum of the LHS gives
 1 r
 1 r
µr 1 1,∞
µr
1 1
1
1
3 1
1,∞
1,∞
k∆ k2,∞ ≤
+ k∆ k2,∞ ⇐⇒ k∆ k2,∞ ≤
.
2
2
2
2
2 64 µr 2
d
6
5 64 µr 2
d
This shows that the ℓ2,∞ error bound induction hypothesis is true for the first iteration.
For the proximity, using the bound of |||D 1,i,m |||F in inequality (38) and what we just prove,
we have
 1 r
µr
1 1,∞
1
1 1
1,i,m
|||D
|||F ≤ k∆ k2,∞ +
2
2
8
8 64 µr 2
d
 1 r
1
µr
1 1
.
≤
2
2
4 64 µr 2
d
Taking maximum over i and m of the LHS shows that
 1 r
 1 r
µr
µr
1 1
1
1
1
1,∞
|||D |||F ≤
≤ 2 2
.
2
2
4 64 µr 2
d
64 µr 2
d
This completes the base case t = 1.
B.3. Step 1: Preliminary analysis of the induction step of ℓ2,∞ error bound
Now suppose the induction hypothesis is true for the t-th iteration (t ≥ 1). We prove that
they are also true for the t + 1-th iteration.
Let us fix an index i ∈ {0, . . . , d} and an index m ∈ [d].
Let Λt,i be the diagonal matrix with top r eigenvalue of M ∗ + E t,i . The definition of
t+1,i
F
gives
(M ∗ + E t,i )F t+1,i = F t+1,i Λt,i .
Now focusing on the m-th row and letting O ∈ Rr×r , OO T = I to be chosen later, we
have
t+1,i
∗
Fm·
− Fm·
O

=eTm (M ∗ + E t,i )F t+1,i (Λt,i )−1 − eTm F ∗ O

=eTm F ∗ (F ∗ )T F t+1,i (Λt,i )−1 + eTm E t,i F t+1,i (Λt,i )−1 − eTm F ∗ O


=eTm F ∗ (F ∗ )T F t+1,i (Λt,i )−1 − O + eTm E t,i F t+1,i (Λt,i )−1




= eTm F ∗ (F ∗ )T F t+1,i − O + eTm F ∗ (F ∗ )T F t+1,i (Λt,i )−1 − I + eTm E t,i F t+1,i (Λt,i )−1 .
{z
}
{z
} |
{z
} |
|
T1

T2

T3

Bounding |||E t,i |||op : We let F ∗ = arg minF F T =M ∗ kF t,i − F k2,∞ only in this paragraph to
save some notation. The ℓ2,∞ error bound induction hypothesis implies that kF t,i k2,∞ ≤

31

Leave-one-out Approach for Matrix Completion

q
t,i is
2 µr
d . The error E


(i)
|||E t,i |||op = |||HΩ F t,i ⊗ F t,i − M ∗ |||op



(i)
(i)
= |||HΩ F t,i ⊗ F t,i − F ∗ ⊗ F t,i + HΩ F ∗ ⊗ F t,i − F ∗ ⊗ F ∗ |||op


(i)
(i)
≤ |||HΩ (F t,i − F ∗ ) ⊗ F t,i |||op + |||HΩ F ∗ ⊗ (F t,i − F ∗ ) |||op
s
(a)
d log d
max{kF·j∗ k∞ , kF·jt,i k∞ } max k(F t,i − F ∗ )·j k∞
≤ 4cr
p j∈[r]
j∈[r]
s
(b)
d log d
max{kF ∗ k2,∞ , kF t,i k2,∞ }kF t,i − F ∗ k2,∞
≤ 4cr
p
s
r
 t r
(c)
1
d log d
µr 1
µr
2
≤ 4cr
2
2
p
d 64 µr 2
d
s


64µ2 c2 r 4 log d 1 t 1
=
pd
2 642 µr 2
 t+1
1
1
1
.
≤
2
2
16 64 µr 2

(40)

Here inequality (a) is due to Lemma 15 and inequality (b) is due to the relation between
the k · k∞ and k · k2,∞ . Inequality (c) is due to the induction hypothesis of ℓ2,∞ error bound.
2 4
The choice of p & µ r dlog d is used in the last inequality.
By following the same argument in bounding T1 , T2 , T3 as in Subsection B.2.1, we see
that by choosing O = U V T where U, V are the left and right singular vectors of (F ∗ )T F t,i ,
we have
t+1,i
∗
kFm·
− Fm·
Ok2
r  t+1
1
µr 1
1 1
(41)
+ keTm E t,i F t+1,i k2
≤
 t+1 .
2
2
4 64 µr
d 2
1
1
1
1 − 642 µr2 16 2
t+1,i k and finish the induction on ℓ
We next show how to bound keTm E t,i F
2
2,∞ error
q

bound. The goal is to have an additional c

µr
d

term with some small constant c < 1. Note

that if i = m, then eTm E t,i is zero and we are done. So in the following, we assume i 6= m.

32

Leave-one-out Approach for Matrix Completion

B.4. Step 2: Bounding keTm E t,i F t+1,i k2 and complete the induction on ℓ2,∞ error
bound
Let Q ∈ Rr×r and QQT = I where the exact value is left to be determined later. We have
eTm E t,i F t+1,i
=eTm E t,i F t+1,m Q + eTm E t,i (F t+1,i − F t+1,m Q)
(i)

=eTm HΩ (M t,i − M ∗ )F t+1,m Q + eTm E t,i (F t+1,i − F t+1,m Q)
(i)

(i)

= eTm HΩ (M t,m − M ∗ )F t+1,m Q + eTm HΩ (M t,i − M t,m )F t+1,m Q + eTm E t,i (F t+1,i − F t+1,m Q) .
{z
}
|
{z
} |
{z
} |
T1

T2

T3

(42)

Verify Lipschitz condition and bound discrepancy term of inequality (12) The
first term T1 is similar to the discrepancy term in inequality (12) in Section 3 and the the
other two terms T2 , T3 are similar to the Lipschitz term there.
The first term T1 :

For T1 , we bound it as follows
(i)

kT1 k2 = keTm HΩ (M t,m − M ∗ )F t+1,m k2

 X
d
√
1
t+1,m
t,m
∗
.
≤ r max
(1 − δmk )(Mmk − Mmk )Fkj
j≤r
p

(43)

k=1

Since F t+1,m is independent of δmk for all k, using Lemma 10 with C = 12 and ||| · |||F ≥
||| · |||op , we have for any j ≤ r with probability 1 − d−6 ,
d
X
1
t,m
t+1,m
∗
(1 − δmk )(Mmk
|
− Mmk
)Fkj
|
p
i=1
s

C log d t+1,m
≤
kF
k2,∞ kF t,m k2,∞ |||F t,m − F ∗ |||F + kF t,m − F ∗ k2,∞ |||F ∗ |||F
p
|
{z
}
R1


C log d t+1,m
kF
k2,∞ kF ∗ k2,∞ kF t,m − F ∗ k2,∞ + kF k2,∞ kF t,m − F ∗ k2,∞ .
+
p
|
{z
}
R2

33

Leave-one-out Approach for Matrix Completion

The first term R1 can be bounded as follows:
s
r
(a)
√
C log d
µr t,m
t+1,m
∗
(k∆
k2,∞ + kF k2,∞ )(2
|||∆ |||F + k∆t,m k2,∞ r)
R1 ≤
p
d
s
r
(b)
√
C log d
µr √
t+1,m
≤
(k∆
k2,∞ +
)(2 µrk∆t,m k2,∞ + k∆t,m k2,∞ r)
p
d
s
r
C log d
µr √
(k∆t+1,m k2,∞ +
)(3 µr)k∆t,m k2,∞ )
≤
p
d
s
s
2
2
9C log(d)µ r
9C log(d)µr t,m
=
k∆t,m k2,∞ +
k∆ k2,∞ k∆t+1,m k2,∞
pd
p
s
 
(c)
1
9C log(d)µ2 r 2 1 t 1
t,m
√ k∆ k2,∞ +
≤
k∆t+1,m k2,∞
16 × 2 r
pd
2 642 µr 2
(d)

≤

1
1
√ k∆t,m k2,∞ + √ k∆t+1,m k2,∞ .
16 × 2 r
16 r

Here (a) is due to triangular inequality applied to the term kF t+1,m k2,∞ , the invariance of
k · k2,∞ under right multiplication of unitary
and the first induction hypothesis on
√ matrix,
t,m
t,m
t,m
F . Inequality (b) is due to |||∆ |||F ≤ dk∆ k2,∞ and µ ≥ 1. We use ℓ2,∞ error bound
2 r3
of ∆t,m in inequality (c). By p & log(d)µ
, we have (c) and (d). The second term R2 can
d
be bounded as follows
r
r
(a) C log d

µr t,m
µr t,m
t+1,m
∗
(k∆
k2,∞ + kF k2,∞ )
k∆ k2,∞ + 2
k∆ k2,∞
R2 ≤
p
d
d
r
r
3C log d µr
µr
(k∆t+1,m k2,∞ +
)k∆t,m k2,∞
≤
p
d
d
r
3C log d µr t,m
3Cµr log d t,m
=
k∆ k2,∞ k∆t+1,m k2,∞ +
k∆ k2,∞
p
d
dp
(b)
1
1
√ k∆t,m k2,∞ .
≤ √ k∆t+1,m k2,∞ +
16 r
16 × 2 r
Here step (a) is due to triangular inequality applied to the term kF t+1,m k2,∞
q , invariance

of k · k2,∞ under right multiplication of unitary matrix, and kF t,m k2,∞ ≤ 2 µr
d using the
induction hypothesis of ℓ2,∞ error bound. Inequality (b) is due to the induction hypothesis
2
.
of ℓ2,∞ error bound and p & log(d)µr
d
Putting the two and the bound of T1 in (43) together, we have w.h.p. for all i, m,
kT1 k2 ≤

√

r max
j≤r

 X
d
k=1

1
t,m
t+1,m
∗
− Mmk
)Fkj
(1 − δmk )(Mmk
p

1
1
≤ k∆t+1,m k2,∞ +
k∆t,m k2,∞ .
8
8×2
34



(44)

Leave-one-out Approach for Matrix Completion

The T2 term The term T2 can be bounded by
(i)

kT2 k2 =keTm HΩ (M t,i − M t,m )F t+1,m Qk2
(i)

=keTm HΩ (D t,i,m ⊗ F t,m + F t,i ⊗ D t,i,m )F t+1,m Qk2
(i)

(i)

≤ keTm HΩ (D t,i,m ⊗ F t,m )F t+1,m Qk2 + keTm HΩ (F t,i ⊗ D t,i,m )F t+1,m Qk2 .
|
{z
} |
{z
}
R1

The R1 term

R2

We use triangle inequality and get
(i)

R1 = keTm HΩ (D t,i,m ⊗ F t,m )F t+1,m Qk2
(i)

(i)

≤ keTm HΩ (D t,i,m ⊗ F t,m )F ∗ k2 + keTm HΩ (D t,i,m ⊗ F t,m )∆t+1,m k2 .

(45)

The first term can be bounded as follows
(i)

keTm H (D t,i,m ⊗ F t,m )F ∗ k2
v Ω
2
uX X X
u
δ
mk
t,i,m
t,m
∗
Dmj Fkj (1 −
)Fkl
=t
p
j≤r
l≤r k≤d
v
2
uX X
X t,m
u
δ
mk
t,i,m
∗
)Fkl
=t
Dmj
Fkj (1 −
p
k≤d
l≤r j≤r
v
2 
 X X
u 
(a)uX X
δ
mk
t,i,m
t,m
∗
2
)Fkl
≤t
(Dmj )
Fkj (1 −
p
j≤r k≤d
l≤r j≤r
v
 X X X
 
u X
u
δmk ∗ 2
t,i,m 2
t,m
t
(Dmj )
Fkj (1 −
)Fkl
=
p
j≤r
l≤r j≤r k≤d
v

uX X X
u
δmk ∗ 2
t,m
t,i,m t
=kDm· k2
)Fkl
Fkj (1 −
p
l≤r j≤r

≤kD t,i,m k2,∞ r max
l,j≤r

(46)

k≤d

X
k≤d

t,m
Fkj
(1 −

δmk ∗
)Fkl .
p

We use Cauchy-Schwarz in (a). Now using Lemma 8, we have
s
X t,m
log d ∗
C log d ∗
δmk ∗
)Fkl ≤ C
kF k2,∞ +
kF k2,∞ kF t,m k2,∞
Fkj (1 −
p
p
p
k≤d
s
log d ∗
C log d ∗
≤ C
kF k2,∞ +
kF k2,∞ kF t,m k2,∞
p
p
s
µr log d 2C(log d)µr
+
≤ C
pd
pd
35

(47)

Leave-one-out Approach for Matrix Completion

C

with probability at least 1 − d 2 . By setting C = 12, we see the above holds w.h.p. for
all i, m.
Combing inequalities (46) and (47), we have
(i)

keTm HΩ (D t,i,m ⊗ F t,m )F ∗ k2
X t,m
δmk ∗
Fkj (1 −
≤kD t,i,m k2,∞ r max
)Fkl
l,j≤r
p
k≤d
s

µr log d 2C(log d)µr
t,i,m
C
≤kD
k2,∞ r
+
pd
pd
s

 t r

(a)
µr log d 2C(log d)µr
1
1
µr
C
r
+
≤ 2 2
64 µr 2
d
pd
pd
r


t+1
(b) 1
1
1
µr
,
≤
32 642 µr 2 2
d

(48)

where inequality (a) holds because our proximity induction hypothesis and inequality (b)
2 4
holds because p & µ r dlog d .
Similarly as inequality (46), the second term of the RHS of inequality (45) can be
bounded as follows
(i)

keTm HΩ (D t,i,m ⊗ F t,m )∆t+1,m k2
X t,m
δmk t+1,m
)∆kl
Fkj (1 −
≤kD t,i,m k2,∞ r max
l,j≤r
p
k≤d
 t+1 r
(a) 1
1
1
1
µr
≤
+ k∆t+1,m k2,∞ ,
2
2
32 64 µr 2
d
32

(49)

where (a) is due to the proximity induction hypothesis.
Thus, combining inequalities (48) and (49), we have w.h.p. for all i, m
(i)

R1 = keTm HΩ (D t,i,m ⊗ F t,m )F t+1,m Qk2
 t+1 r
µr
1
1
1
1
≤
+ k∆t+1,m k2,∞ .
2
2
16 64 µr 2
d
32
The R2 term

(50)

Using triangle inequality, we get
(i)

R2 = keTm HΩ (F t,i ⊗ D t,i,m )F t+1,m Qk2
(i)

(i)

≤ keTm HΩ (F t,i ⊗ D t,i,m )F ∗ k2 + keTm HΩ (F t,i ⊗ D t,i,m )∆t+1,m k2 .

36

(51)

Leave-one-out Approach for Matrix Completion

Using the same argument in inequality (46), for the first term we have
(i)

keTm HΩ (F t,i ⊗ D t,i,m )F ∗ k2
X t,i,m
δmk ∗
Dkj (1 −
≤kF t,i k2,∞ r max
)Fkl
l,j≤r
p
k≤d

t,i,m
k2
≤kF k2,∞ r max keTm HΩ (1 ⊗ F·l∗ )D·j
t,i

l,j≤r

t,i,m 
(52)
k2
≤kF k2,∞ r max kem k2 |||HΩ (1 ⊗ F·l∗ )|||op kD·j
l,j≤r
s
r
r
 t r
(a)
1
µr
d log d µr 1
µr
≤2
r
2
2
d
p
d 64 µr 2
d
r


t+1
(b) 1
1
1
µr
≤
.
2
2
32 64 µr 2
d
q
µr
∗
We use Lemma 14 and kF ∗ k2,∞ ≤
d in step (a) to bound |||HΩ (1 ⊗ F·l )|||op . We also
t,i

t,i,m
apply the proximity induction hypothesis on D t,i,m to bound kD·j
k2 . The step (b) is due
2 4

to p & µ r dlog d .
Similar as above, for the second term we have
(i)

keTm HΩ (F t,i ⊗ D t,i,m )∆t+1,m k2

t,i,m
≤kF t,i k2,∞ r max keTm HΩ (1 ⊗ ∆t+1,m
)D·j
k2
·l
l,j≤r

≤

(53)

1
k∆t+1,m k2,∞ .
32

Putting the bound of R1 in inequality (50) and the bound of R2 above together, we
have the following bound for T2 ,
(i)

(i)

kT2 k2 ≤ keTm HΩ (D t,i,m ⊗ F t,m )F t+1,m Qk2 + keTm HΩ (F t,i ⊗ D t,i,m )F t+1,m Qk2
 t+1 r
1
1
3
1
µr
t+1,m
≤ k∆
k2,∞ +
.
16
32 642 µr 2 2
d

(54)

The T3 term Now we bound the third term T3 in inequality (42). We have
kT3 k2 = keTm E t,i (F t+1,i − F t+1,m Q)k2
(i)

= keTm HΩ (M t,i − M ∗ )(F t+1,i − F t+1,m Q)k2
=

(i)
keTm HΩ (M t,i

− M ∗ )∆t+1,i k2 +

(i)
keTm HΩ (M t,i

(55)
− M ∗ )∆t+1,m k2 ,

where the last line is due to a proper choice of Q and k · k2 is unitary invariant.
Using Bernstein inequality for Bernoulli random variables δij , we have that if p &
with probability at least 1 − d−2 , uniformly for all j,
X
δij ≤ 2pd.
j

37

log d
d ,

Leave-one-out Approach for Matrix Completion

Now for the first term in inequality (55), we have
v

uX  X
u
δmj t+1,i 2
(i)
t,i
∗
t+1,i
T
t,i
∗
t
(M − M )ml (1 −
k2 =
kem HΩ (M − M )∆
)∆jl
p
l≤r

j≤d

sX
(a)
t,i
∗ k k∆t+1,i k + kM t,i − M ∗ k k∆t+1,i k d)2
≤
(2dkMm·
− Mm·
∞
∞
m·
∞
m· ∞
l≤r

√
t,i
∗
− Mm·
k∞ k∆t+1,i k∞
≤ 3 rdkMm·

√
≤ 3 rd(kF ∗ k2,∞ kF t,i − F ∗ k2,∞ + kF t,i k2,∞ kF t,i − F ∗ k2,∞ )k∆t+1,i k2,∞
r
 t r
(c) √
1
µr 1
µr t+1,i
≤ 3 rd × 3
k∆
k2,∞
2
2
d 64 µr 2
d
 
9 1 t t+1,i
≤ 2
k∆
k2,∞
64 2
1
≤
k∆t+1,i k2,∞ .
32
(56)
Inequality (a) is due to triangle inequality and the fact that with probability 1 − d−2 , for
each row, we observe no more than 2pd nonzeros when p & logd d . Inequality (b) is due to
Lemma 9. Inequality
(c) holds because our ℓ2,∞ error bound induction hypothesis implies
q
(b)

kF t,i k2,∞ ≤ 2 µr
d .
Similarly, we have for the second term of inequality (55),

1
k∆t+1,m k2,∞ .
32
Combining inequality (55),(56) and (57), we have with a proper choice of Q,
(i)

keTm HΩ (M t,i − M ∗ )∆t+1,m k2 ≤

(57)

1
(58)
k∆t+1,∞ k2,∞ .
16
Completing the ℓ2,∞ error bound induction hypothesis: Now, combining inequalities (41)-(42), bounds of T1 , T2 , T3 in inequalities (44), (54), and (58), we have
keTm E t,i (F t+1,i − F t+1,m Q)k2 ≤

keTm (F t+1,i − F ∗ O)k2
 t+1 r

1
µr 100 1 t+1,m
1 1
+
k∆
k2,∞
≤
4 642 µr 2 2
d
99 8

 t+1 r
 t+1 r
µr
µr
1 1
1
1
1
1
3
1
t+1,m
t+1,∞
+
+ k∆
k2,∞ +
+ k∆
k2,∞
8 642 µr 2 2
d
16
32 642 µr 2 2
d
16
 t+1 r
1
µr 25 t+1,∞
1 1
+ k∆
k2,∞ ,
≤
2
2
2 64 µr 2
d
99
(59)
∗
T
t,i
where O depends only on (F ) F . Taking maximum over i, m of LHS and rearranging
the terms gives the inequality for the ℓ2,∞ error bound induction hypothesis:
 t+1 r
µr
1
1
t+1,∞
.
k∆
k2,∞ ≤ 2 2
64 µr 2
d
38

Leave-one-out Approach for Matrix Completion

B.5. Step 3: Proving proximity property
We begin by recalling that


(i)
F t+1,i = SVDr M ∗ + HΩ (M t,i − M ∗ ) ,



(m)
F t+1,m = SVDr M ∗ + HΩ (M t,m − M ∗ ) .

Verify ℓ2 contraction condition and bound discrepancy term in inequality (13):
Let
(m)
(i)
(i)
W = (HΩ − HΩ )(M t,m − M ∗ ) +
H (M t,i − M t,m )
,
|
|Ω
{z
}
{z
}
discrepancy error W (a)

ℓ2 contraction term for SVP operator W (b)
(i)

(m)

which is the perturbation matrix between M ∗ +HΩ (M t,i −M ∗ ) and M ∗ +HΩ (M t,m −M ∗ ).
The terms W (a) , W (b) are similar to discrepancy term and ℓ2 contraction term respectively
in inequality (13) in Section 3.
(i)
By Weyl’s inequality, M ∗ + HΩ (M t,i − M ∗ ) has eigengap between r-th and r + 1-th
1
t,i
eigenvalue at least δ = 1 − 2|||E |||op . We have |||W |||op ≤ |||E t,i |||op + |||E t,m |||op ≤ 16
following
1
0,i
t,i
the analysis of |||E |||op in inequality (40) and so δ = 1 − 2|||E |||op ≥ 1 − 16 .
By Davis-Kahan’s sin Θ theorem (Lemma 17), we have
√
2|||W F t+1,m |||F
t+1,i,m
|||D
|||F ≤
δ − |||W |||op
√
(60)
2|||W F t+1,m |||F
≤
7/8
≤ 2(|||W (a) F t+1,m |||F + |||W (b) F t+1,m |||F ).
To proceed, we first consider the case i = 0.

39

Leave-one-out Approach for Matrix Completion

B.5.1. The W (a) term
Note that W (a) is only supported on the m-th row and column. We can bound W (a) as
follows
|||W (a) F t+1,m |||F
v
uX X
u
=t

j≤r k≤d,k6=m

(1 −

v
uX
u
t+1,m 2
)
= t (Fmj
j≤r

v
uX
u
t+1,m 2
)
≤ t (Fmj
j≤r

X X


δmk
δmk
t,m
t,m
∗ )F t+1,m 2 +
∗ )F t+1,m 2
(1 −
)(Mmk
− Mmk
)(Mmk
− Mmk
mj
kj
p
p

X

j≤r k≤d

((1 −

k≤d,k6=m

X X

δmk
δmk
t,m
t,m
∗ ))2 +
∗ )F t+1,m 2
(1 −
)(Mmk
− Mkm
)(Mmk
− Mmk
kj
p
p
j≤r k≤d

v
uX X
X

δmk
δmk
u
t,m
t,m
∗
∗ )F t+1,m 2
2
((1 −
)(Mmk − Mmk )) + t
)(Mmk
− Mmk
(1 −
kj
p
p
j≤r k≤d

k≤d,k6=m

v
u X
X
√
δmk
δmk
u
t,m
t,m
t+1,m
t+1,m
∗
∗ ))2 + r max
≤ kF
k2,∞ t
)(Mmk
− Mmk
)(Mmk
− Mmk
)Fkj
((1 −
(1 −
j≤r
p
p
k≤d,k6=m

k≤d

X
√
δmk
t,m
t+1,m
∗
≤ (k∆t+1,m k2,∞ + kF ∗ k2,∞ )kHΩ (M t,m − M ∗ )em k2 + r max
(1 −
)(Mmk
− Mmk
)Fkj
j≤r
p
k≤d
r
X
√
µr
δmk
t+1,m
t,m
∗
(1 −
)Fkj
)|||HΩ (M t,m − M ∗ )|||op + r max
)(Mmk
− Mmk
≤ (k∆t+1,m k2,∞ +
j≤r
d
p
k≤d
s
r
r 
r



(a)
1 t µr
1
µr
d log d µr
t+1,m
) 4cr
2
≤ (k∆
k2,∞ +
d
p
d 642 µr 2 2
d
X
√
δmk
t+1,m
t,m
∗
+ r max
(1 −
)Fkj
)(Mmk
− Mmk
.
j≤r
p
k≤d
 t+1 r
1
1
µr
1
.
≤
16 642 µr 2 2
d
(61)
t,m
t,m
∗
We use the bound of |||E |||op = |||HΩ (M
− M )|||op in inequality (40) in step (a) and
the second term of (a) can be bounded as T1 in inequality (44). The last inequality holds
4 6
because our ℓ2,∞ error bound induction hypothesis for the t + 1 case and p & µ r dlog d .
B.5.2. The W (b) term
We have
|||W (b) F t+1,m |||F = |||HΩ (M t − M t,m )F t+1,m |||F

= |||HΩ (F t ⊗ D t,m + D t,m ⊗ F t,m )F t+1,m |||F

≤ |||HΩ (F t ⊗ D t,m )F t+1,m |||F + |||HΩ (D t,m ⊗ F t,m )F t+1,m |||F .
Here F t,m is understood as the one closest to F t in Frobenius norm.
For the first term of RHS of inequality (62), we have
40

(62)

Leave-one-out Approach for Matrix Completion

v
u X 
u
|||HΩ (F t ⊗ D t,m )F t+1,m |||F ≤ t

X

j≤d,l1 ≤r

l2 ≤r,k≤d

v
uX
u
√
≤ r max t
l1 ≤r

=

√

≤r
≤r

r max |||

3
2
3
2

(a)

j≤d

l1 ≤r

X

l2 ≤r

t,m t+1,m
Fjlt 2 Dkl
Fkl1 (1 −
2

X

l2 ≤r,k≤d


δjk 2
)
p

t+1,m
Fjlt 2 Dkl2 Fkl
(1 −
1


δjk 2
)
p

HΩ (F·lt2 ⊗ F·lt+1,m
)D·lt,m
|||F
1
2

max |||HΩ (F·lt2 ⊗ F·lt+1,m
)D·lt,m
|||F
1
2

l1 ,l2 ≤r

max

l1 ,l2 ≤r

|||HΩ (F·lt2

⊗

(63)

F·lt+1,m
)|||op |||D·lt,m
|||F
1
2

s

d log d t
kF k2,∞ kF t+1,m k2,∞ |||D t,m |||F
p
s
 t r
(b) 3
1
d log d µr 1
µr
2
≤ r 8c
2
2
p
d 64 µr 2
d
 t+1 r
1
1
µr
1
.
≤
16 642 µr 2 2
d
≤r

3
2

max 2c

l1 ,l2 ≤r

Here inequality (a) is due to Lemma 15. Inequality (b) is due to ℓ2,∞ error bound induction
hypothesis for the t + 1 case which we just proved and the proximity induction hypothesis.
2 5
The last inequality is due to p & µ r dlog d .
For the second term of the RHS of inequality of (62), we split it into three terms as
follows
|||HΩ (D t,m ⊗ F t,m )F t+1,m |||F

≤|||HΩ (D t,m ⊗ F t,m )∆t+1,m |||F + |||HΩ (D t,m ⊗ F t,m )F ∗ |||F
≤|||HΩ (D

t,m

⊗F

t,m

)∆

t+1,m

|||F + |||HΩ (D

t,m

⊗∆

t,m

∗

)F |||F + |||HΩ (D

(64)
t,m

∗

∗

⊗ F )F |||F ,

where first and second inequality is due to triangle inequality and the fact ||| · |||F is unitary
invariant.

41

Leave-one-out Approach for Matrix Completion

The first term of the RHS of inequality (64) can be bounded as follows
|||HΩ (D t,m ⊗ F t,m )∆t+1,m |||F
v

u X  X
u
δjk 2
t,m t+1,m
t
t
=
)
Fkl2 Djl2 ∆kl1 (1 −
p
j≤d,l1 ≤r l2 ≤r,k≤d
v
2
u X X
X
u
t,m
t ∆t+1,m (1 − δjk )
=t
Djl
F
kl2 kl1
2
p
j≤d,l1 ≤r l2 ≤r
k≤d
v
u X X
X X
u
t,m 2
t ∆t+1,m (1 − δjk ))2 )
≤t
(
(Djl
)
)(
(
Fkl
kl1
2
2
p
j≤d,l1 ≤r l2 ≤r

l2 ≤r k≤d

v
X X
(a)u
uX X
t,m 2
t ∆t+1,m (1 − δjk ))2 )
≤t
(
(Djl
)
)(max
(
(
Fkl
kl1
2
2
j≤d
p
l1 ≤r j≤d,l2 ≤r

≤|||D t,m |||F

√

(65)

l2 ≤r k≤d

v
u X X
u
t ∆t+1,m (1 − δjk ))2 )
r max t(
(
Fkl
kl1
2
l2 ≤r,j≤d
p
l2 ≤r k≤d

δjk
)
p
k≤d
r
 t r
 t+1 r
(b)
1
1
µr
µr 1
µr
1
r × 3d
≤ 2 2
2
2
64 µr 2
d
d 64 µr 2
d
 t+1 r
1
1
µr
1
.
≤
2
2
64 64 µr 2
d
≤|||D t,m |||F r

max

l2 ,l1 ≤r,j≤d

X

t
Fkl
∆t+1,m
(1 −
kl1
2

We use Cauchy-Schwarz in step (a). Inequality (b) is due to the fact that with probability
1 − d−2 , for each row, we observe no more than 2pd nonzeros when p ≥ 10 logd d . Similarly,
we can bound the second RHS term of inequality (64) as follows
|||HΩ (D t,0,m ⊗ ∆t,m )F ∗ |||F
X
δjk
∗
≤|||D t,m |||F r max
Fkl
∆t,m
kl1 (1 − p )
2
l2 ,l1 ≤r,j≤d
k≤d

|||F r × 3dkF k2,∞ k∆t,m k2,∞
r
 t r
 t r
µr
µr 1
µr
1
1
1
≤ 2 2
r × 3d
2
2
64 µr 2
d
d 64 µr 2
d
 t+1 r
1
1
µr
1
.
≤
2
2
64 64 µr 2
d
≤|||D

t,m

∗

42

(66)

Leave-one-out Approach for Matrix Completion

For the third RHS term of inequality (64), we use Lemma 11 to find that
1
|||D t,m |||F
96
 t r
1
1
1
µr
≤
96 642 µr 2 2
d
 t+1 r
1
1
µr
1
.
≤
48 642 µr 2 2
d

|||HΩ (D t,m ⊗ F ∗ )F ∗ |||F ≤

Combining the bounds in (62), (63), (64),(65),(66) and (67), we have
 t+1 r
1 1
1
µr
(b) t+1,m
|||W F
|||F ≤
.
2
2
8 64 µr 2
d

(67)

(68)

B.5.3. Completing proximity induction hypothesis
Combining the inequalities (60), (61) and (68), we conclude that for i = 0 and each m ∈ [d]
|||D t+1,0,m |||F ≤ 2(|||W (a) F t+1,m |||F + |||W (b) F t+1,m |||F )
 t+1 r
µr
1 1
1
≤
.
2
2
2 64 µr 2
d

(69)

For general i, using the same argument in inequality (38), we have
|||D t+1,i,m |||F ≤ |||D t+1,0,i |||F + |||D t+1,0,m |||F
 t+1 r
1
1
µr
≤ 2 2
.
64 µr 2
d

(70)

This completes the induction for t ≤ t0 .
B.6. Step 3: Bounds on infinite number of iterations
The previous steps corresponds to the first three steps of our recipe in Section 3. Here we
complete the last step of our recipe.
We have proved that for each t ≤ t0 = 5 log2 d + 12, w.h.p.
r
 t r
µr
µr
1
1
t,∞
t,i
(ℓ2,∞ error bound) k∆ k2,∞ ≤ 2 2
=⇒ kF k2,∞ ≤ 2
64 µr 2
d
d
 t r
1
µr
1
.
(proximity) |||D t,i,j |||F ≤ 2 2
64 µr 2
d
Thus the above holds uniformly for all t ≤ t0 . The previous argument also works for each
t ≥ t0 = 5 log2 d + 12. But since there are infinite number of t ≥ t0 , the probability for
the above to hold for all t using union bound won’t work. We now turn to prove linear
convergence of |||M t − M ∗ |||F .

43

Leave-one-out Approach for Matrix Completion

Control the iterates for infinite iterations We prove that with high probability, for
all t ≥ t0 , we have
1
|||F t+1 ⊗ F t+1 − F ∗ ⊗ F ∗ |||F ≤ |||F t ⊗ F t − F ∗ ⊗ F ∗ |||F
2

(71)

which implies the following linear convergence result
|||F t+1 ⊗ F t+1 − F ∗ ⊗ F ∗ |||F ≤

1
|||F t0 ⊗ F t0 − F ∗ ⊗ F ∗ |||F .
2t−t0

Since t0 = 5 log2 d + 12, we have
|||M t0 − M ∗ |||F ≤ dkM t0 − M ∗ k∞ ≤

1 1 µr
642 d2 d

and kM t0 k∞ ≤ 2 µr
d .
Suppose that the base case t = t0 for inequality (71) is verified and it is true for the t-th
iteration. We have
|||M t − M ∗ |||F ≤ |||M t0 − M ∗ |||F ,
using the induction hypothesis. This implies that
kM t k∞ ≤ kM ∗ k∞ + kM t − M ∗ k∞ ≤ kM ∗ k∞ + |||M t − M ∗ |||F ≤ 2
kD̃ t k∞ ≤ |||D̃ t |||F ≤ |||D̃ t0 |||F ≤

µr
,
d

1 1 µr
,
642 d2 d

(72)
(73)

4 6

where D̃ t : = M t − M ∗ . By previous analysis of |||E t |||op , we know that if p & µ r dlog d , then
1
|||E t |||op ≤ 16
and so the first r eigenvalue of M ∗ + E t is positive and there is an eigengap of
∗
t
M + E with magnitude at least 81 between the r-th eigenvalue and (r + 1)-th eigenvalue.
Under the definition of F t+1 and [M ∗ + E t ]r , we have
|||M t+1 − (M ∗ + E t )|||2F =|||M t+1 − [M ∗ + E t ]r |||2F + |||[M ∗ + E t ]r − (M ∗ + E t )|||2F ≤ |||E t |||2F ,
(74)
where the inequality is due to Mirsky’s inequality and what we just proved for eigenvalues
of M ∗ + E t . This also gives
|||M t+1 − M ∗ |||F ≤ |||M t+1 − (M ∗ + E t )|||F + |||E t |||F = 2|||E t |||F ≤ 2 ×

1
,
642

(75)

where the last inequality uses the inequality (73), the fact that kD̃ t k∞ ≤ |||D̃ t |||F , |||E t |||F ≤
√
d|||E t |||op and Lemma 15. The above then gives
kM t+1 k∞ ≤ kM t+1 − M ∗ k∞ + kM ∗ k∞ ≤ |||M t+1 − M ∗ |||F +

µr
µr
≤2 .
d
d

(76)

Thanks to the inequalities (72),(73), (75) and (76), the premise of Proposition 2 is
satisfied for M + = M t+1 , M = M t . By expanding the square of the LHS of inequality (74),

44

Leave-one-out Approach for Matrix Completion

we have

|||D̃ t+1 |||2F ≤ −2hD̃ t+1 , E t i

1
≤ −2hD̃ t+1 , (I − ΠΩ )(D̃ t )i
p
1
≤ −2hD̃ t+1 , (I − ΠΩ )(D̃ t )i
p
1
≤ 2| hΠΩ D̃ t+1 , ΠΩ D̃ t i − hD̃ t+1 , D̃ t i|
p
1
≤ 2 × |||D̃ t+1 |||F |||D̃ t |||F ,
4
where the last line is due to Proposition 2. The last inequality implies that

(77)

1
1
|||D̃ t+1 |||2F ≤ |||D̃ t |||F |||D̃ t+1 |||F =⇒ |||D̃ t+1 |||F ≤ |||D̃ t |||F .
2
2
The above arguments also works for the case t = t0 since the premise of Proposition 2 is
also satisfied due to the choice of t0 . We see the base case is also verified and the proof is
completed.

Appendix C. Proof of Theorem 2
In this section, we establish the convergence of the original form of SVP. We emphasize that
in our setting, the true low-rank matrix M ∗  0 may have unequal eigenvalues. Let σ1 be
the largest eigenvalue of M ∗ and σr be the smallest nonzero one. Recall that the condition
number of M ∗ is κ = σσr1 .
(m)

Recall that we choose the step size to be p1 , HΩ = I − 1p ΠΩ , and HΩ
derived from HΩ but with the m-th row and m-column observed; that is,
(


(1 − p1 δij )Zij , i 6= m, j 6= m,
(m)
=
HΩ Z
0,
i = m or j = m.
ij

is the operator

Using these notations, SVP algorithm in this case can be written compactly as
M 0 = 0,

M t+1 = Pr (M ∗ + HΩ (M t − M ∗ )).

(78)

We write the eigenvalue decomposition of M t as M t = (F t Λt )⊗F t . For analysis purpose,
for each m ∈ [d], we consider the following fictitious iteration: with F 0,m = 0, Λ0,m = 0 and


(m)
F t+1,m Λt+1,m ⊗ F t+1,m = Pr M ∗ + HΩ F t,m Λt,m ⊗ F t,m − M ∗ .

Here F t,m ∈ Rd×r has orthonormal columns and Λt,m ∈ Rr×r is diagonal. Also be reminded
that these iterates have the property that F t,m is independent of the m-th row of Ω, i.e.,
independent of δij for i or j equal to m.


(m)
Let E t = E t,0 : = HΩ F t Λt,m ⊗ F t − M ∗ and E t,m : = HΩ F t,m Λt,m ⊗ F t,m − M ∗ .
(0)

Also let F t,0 = F t , HΩ = HΩ . We use the shorthand M t,i := F t,i Λt,i ⊗ F t,i for all t, i.
Unlike the case that the nonzero eigenvalues of M ∗ are the same, we will construct
the rotation matrix O directly and do induction based on the explicit rotation matrix.
45

Leave-one-out Approach for Matrix Completion

For each m ∈ {0} ∪ [d], let H t,m = (F ∗ )T F t,m and its singular value decomposition be
Ū Σ̄V̄ T . We denote Gt,m = Ū V̄ T . It is known that Gt,m is the minimizer of the problem
minOOT =I,O∈Rr×r |||F t,m − F ∗ O|||F (Ge et al., 2017, Lemma 6). Similarly, we define H t,i,m =
(F t,m )T F t,i and Gt,i,m for each pair of F t,i and F t,m . We let H t = H t,0 , Gt = Gt,0 .
In the subsequent analysis, for each i, m ∈ {0}∪[d], we let ∆t,m := F t,m −F ∗ Gt,m , D t,i,m =
t,i
F − F t,m Gt,i,m and S t,i,m := Λt,m Gt,i,m − Gt,i,m Λt,i . For each t, we denote ∆t,∞ :=
arg max∆t,m k∆t,m k2,∞ , D t,∞ := arg maxDt,i,m |||D t,i,m |||F , E t,∞ := arg maxE t,i |||E t,i |||op and
S t,0,∞ := arg maxm∈[d] |||S t,0,m |||F .
To handle the unequal eigenvalues, we use techniques similar to the ones in Fan et al.
(2017); Abbe et al. (2017). In particular, the follow lemma is useful in the subsequent
analysis.
Lemma 5 (Abbe et al., 2017, Lemma 3) Let W = M ∗ + E, E ∈ S d×d and F ∈ Rd×r be the
matrix with the top r eigenvector of W as its columns. Define the matrix H = (F ∗ )T F and
let its singular value decomposition be H = U ΣV T . Let G = U V T . We have
1
2
≤
|||H|||op ≤ 1, |||H − G|||op

Furthermore, if γ =

|||E|||op
σr

|||EF ∗ |||op
, |||Λ∗ H − HΛ∗ |||op ≤ 2|||E|||op .
σr − |||E|||op

< 21 , then
|||H −1 |||op ≤

(1 − γ)2
.
1 − 2γ

As a simple consequence of the above lemma, we have the following bounds.
Lemma 6 Under the setting of Lemma 5 and assume that |||E|||op < 12 σr , we have


1
∗
∗
|||Λ G − GΛ |||op ≤ 2 + 2σ1
|||E|||op ,
σr − |||E|||op


1
∗
∗
|||Λ H − GΛ |||op ≤ 2 + σ1
|||E|||op ,
σr − |||E|||op


1
|||Λ∗ G − HΛ∗ |||op ≤ 2 + σ1
|||E|||op .
σr − |||E|||op
Proof We prove only the first inequality, the other two are similar. We have
(a)

|||Λ∗ G − GΛ∗ |||op ≤ |||Λ∗ G − Λ∗ H|||op + |||HΛ∗ − GΛ∗ |||op + |||HΛ∗ − Λ∗ H|||op
(b)

≤ |||Λ∗ |||op |||G − H|||op + |||H − G|||op |||Λ∗ |||op + |||HΛ∗ − Λ∗ H|||op


(c)
1
|||E|||op ,
≤ 2 + 2σ1
σr − |||E|||op
where we use triangle inequality in step (a), the sub-multiplicative property of ||| · |||op in step
(b), and Lemma 5 and the inequality |||E|||op < 21 σr in step (c).
As we shall see later, the following Lemma is important in proving proximity. Recall
that λi (A) denotes the r-th largest eigenvalue of a symmetric matrix A.
46

Leave-one-out Approach for Matrix Completion

Lemma 7 Let A be a symmetric matrices in S d×d and first r eigenvalues are positive
and the smallest positive eigenvalue has magnitude larger than other negative ones. Let
the eigenvalue decomposition of A be A = F1 Λ1 F1T + F2 Λ2 F2T and Λ1 be the eigenvalue
matrix corresponding to the top r eigenvalues of A. Let Ã = A + E, E ∈ S d×d and the
top r eigenvectors of Ã be F associated with its top r eigenvalue matrix Λ. If |||E|||op <
1
2 (λr (A) − |λr+1 (A)|), then
|||Λ1 G − GΛ|||F ≤


2λ1 (A) + |||E|||op
+ 1 |||EF |||F ,
λr (A) − |||E|||op

where G = U V T and U V T is from the singular value decomposition of H = F1T F = U ΣV T .
Proof Using the definition of F , we have
ÃF = F Λ
=⇒ (A + E)F = F Λ
=⇒ F1 Λ1 F1T F + F2 Λ2 F2T F + EF = F Λ
=⇒ Λ1 F1T F + F1T EF = F1T F Λ
=⇒ Λ1 H − HΛ = −F1T EF

=⇒ |||Λ1 H − HΛ|||F = |||F1T EF |||F .
Consequently, using the definition of H, G and the Davis-Kahan sin Θ Theorem (Lemma 17),
we have
|||Λ1 G − GΛ|||F ≤ |||Λ1 G − Λ1 H|||F + |||HΛ − GΛ|||F + |||ΛH − HΛ|||F

≤ (λ1 (A))|||G − H|||F + (λ1 (A) + |||E|||op )|||G − H|||F + |||F1T EF |||F

(a)

≤ (2λ1 (A) + |||E|||op )||| sin Θ|||F + |||F1T EF |||F

2λ1 (A) + |||E|||op
≤
+ 1 |||EF |||F ;
λr (A) − |||E|||op

here third line (a) is due to the fact that |||H − G|||F = |||I − cos Θ|||F ≤ |||(sin Θ)(sin Θ)|||F ≤
||| sin Θ|||F , where Θ is the principle angles between F and F1 .
We are now ready to give the proof of Theorem 2. The high-level strategy is the same
as the proof of case for equal eigenvalue case (Theorem 3) in Appendix B. We shall first
6 4 6
prove that as long as p & κ µ rd log d , there holds the infinity norm bound
 
r 1 t
t
∗
kM − M k∞ ≤
σ1
(79)
d 2
for all 1 ≤ t ≤ t0 = 5 log2 d + 12 w.h.p.; this is done using an induction argument in
6 4 6
Subsections C.1–C.4. We then show in Subsection C.5 that if p & κ µ rd log d , then there
holds the Frobenius norm bound
 t0  t−t0
1
1
t
∗
σ1
(80)
|||M − M |||F ≤
2
2
47

Leave-one-out Approach for Matrix Completion

for all t > t0 w.h.p.
The above two bounds imply that
t

∗

kM − M k∞
for all t ≥ 1 w.h.p. as long as p &
Theorem 2.

 t
1
≤
σ1
2

κ6 µ4 r 6 log d
,
d

(81)

which establishes the desired result in

C.1. Step 0: Induction hypothesis and base case t = 1
Our induction hypothesis for 1 ≤ t ≤ t0 = 5 log2 d + 12 is
(l2,∞ error bound)
(proximity)
(Operator norm bound)
(Non-commutativity bound)

r
 t r
1
µr
µr
1
t,i
=⇒ kF k2,∞ ≤ 2
,
k∆ k2,∞ ≤ 16
2
2 κµr 2
d
d
 t r
1
1
µr
t,∞
|||D |||F ≤ 16
,
2
2 κµr 2
d
 t
1
1
t−1,∞
|||E
|||op ≤ 16
σr =⇒ |||Λt−1,i |||op ≤ 2σ1 ,
2
2 κµr 2
 t r
µr
1
1
t,0,∞
|||S
|||F ≤ σ1 16
.
2
2 κµr 2
d
t,∞

Note that unlike the equal eigenvalue case, we need to keep track of the norm of E t,i
and the non-commutativity term Λt,m Gt,i,m − Gt,i,m Λt,i . This is mainly due to the extra
technicality of handling the term Λ∗ Gt,i − Gt,i Λ∗ which is 0 when Λ∗ = I. Using a similar
argument as inequalities (93) and (94) in Subsection C.2, we see that the above bounds
imply the inequality (79).
To establish the base case t = 1, let us first fix an index i ∈ {0} ∪ [d] and an index
m ∈ [d].
Operator norm bound of E 0,i :

The error E 0,i is bounded by


(i)
|||E 0,i |||op = |||HΩ M ∗ |||op
s
(a)
d log d µr
≤ 2c
σ1
p
d
 1
(b) 1
1
1
σr
≤
Cκ 216 κµr 2 2

(82)

for a large constant C > 0. Here step (a) is due to Lemma 14. The step (b) is due to
6 4 6
p & κ µ rd log d . This proves the operator norm bound.

48

Leave-one-out Approach for Matrix Completion

Now focusing on the m-th row, we have
1,i
∗
Fm·
− Fm·
G1,i =eTm (M ∗ + E 0,i )F 1,i (Λ1,i )−1 − eTm F ∗ G1,i

=eTm (F ∗ Λ∗ ⊗ F ∗ )F 1,i (Λ1,i )−1 + eTm E 0,i F 1,i (Λ1,i )−1 − eTm F ∗ G1,i


=eTm F ∗ Λ∗ (F ∗ )T F 1,i (Λ1,i )−1 − (Λ∗ )−1 G1,i + eTm E 0,i F 1,i (Λ1,i )−1


= eTm F ∗ Λ∗ (F ∗ )T F 1,i (Λ∗ )−1 − (Λ∗ )−1 G1,i
{z
}
|
+

T1

T ∗ ∗
∗ T 1,i
em F Λ (F ) F (Λ1,i )−1

|

{z
T2


− (Λ∗ )−1 + eTm E 0,i F 1,i (Λ1,i )−1 .
{z
}
} |
T3

We can bound T1 , T2 , T3 by following almost the same arguments as bounding T1 , T2 , T3
in Section B.2.1 and using Lemma 6 for the T1 here. The conclusion is
1,i
∗
kFm·
− Fm·
G1,i k2
r  1
µr 1
1
1
C+1
≤
+ keTm E 0,i F 1,i k2
16
2
C 2 κµr
d 2
Cσr

(83)

for a large constant C > 0.
C.1.1. Bounding the term keTm E 0,i F 1,i k2

We next bound the term keTm E 0,i F 1,i k2 , which is the key to proving the ℓ2,∞ norm bound
in the induction hypothesis for the base case. Note that if i = m, then eTm E 0,i is zero and
we are done. So in the following, we assume i 6= m.
Let Q ∈ Rr×r be a matrix satisfying QQT = I, whose exact value is to be determined
later. We have
eTm E 0,i F 1,i
=eTm E 0,i F 1,m Q + eTm E 0,i (F 1,i − F 1,m Q)
(i)

= eTm HΩ (−M ∗ )F 1,m Q + eTm E 0,i (F 1,i − F 1,m Q) .
{z
}
{z
} |
|
T2

T1

The first term T1 :

(84)

For T1 , we bound it as follows
(i)

kT1 k2 = keTm HΩ (−M ∗ )F 1,m k2

 X
d
√
1
1,m
∗
.
≤ r max
(1 − δmk )(−Mmk )Fkj
j≤r
p
k=1

49

(85)

Leave-one-out Approach for Matrix Completion

Since F 1,m is independent of δmk for all k, using Bernstein, Lemma 8, and C = 12, we have
for any j ≤ r with probability 1 − d−6 ,
d
X
1
1,m
∗
(1 − δmk )(−Mmk
)Fkj
|
p
i=1
s
C log d 1,m
C log d 1,m
∗
≤
kF k2,∞ kMm·
k2 +
kF k2,∞ kM ∗ k∞ .
p
p
{z
}
{z
} |
|

|

R2

R1

We need this inequality to hold for all i, m ∈ {0} ∪ [d] simultaneously. Indeed, since each
event happens with 1 − d−6 , by union bound we know that the above inequality holds for
all combination of i, m, j w.h.p.
The first term R1 can be bounded as follows:
s
r
(a)
C log d
µr
1,m
∗
R1 ≤
(k∆ k2,∞ + kF k2,∞ )σ1
p
d
s
r
r
(b)
C log d
µr
µr
(k∆1,m k2,∞ +
)σ1
≤
p
d
d
s
s
r
C log(d)µr
µr
Cµ log(d)r 1,m
σ1
+
k∆ k2,∞ σ1
=
pd
d
dp
r


(c)
1
1
µr
1
1,m
√
+ √ k∆ k2,∞ .
≤ σr
d
16 × 2 r 216 κµr 2
16 r
Here step (a) is due to triangular inequality applied to the term kF 1,m k2,∞ and that k · k2,∞
is invariant under
matrix and that M ∗ is µ-incoherent. We
q right multiplication of unitary
4
κ log(d)µ4 r 6
use kF ∗ k2,∞ ≤ µr
, we have inequality (c).
d in step (b). Due to p &
d
The second term R2 can be bounded as follows
(a)

µr
C log d
(k∆1,m k2,∞ + kF ∗ k2,∞ ) σ1
p
d
r
µr
C log d µr
σ1 (k∆1,m k2,∞ +
)
≤
p
d
d
r
C log d µr
Cµr log d µr
1,m
=
σ1 k∆ k2,∞ +
σ1 ,
p
d
dp
d
1
1
1
√ 16
k∆0,m k2,∞ σr .
≤ σr √ k∆1,m k2,∞ +
16 r
16 × 2 r 2 κµr 2

R2 ≤

Here step (a) is due to triangular inequality applied to the term kF 1,m k2,∞ and that k · k2,∞
is invariant under right multiplication of unitary matrix and that M ∗ is µ-incoherent. The
2 4 6
last inequality is due to p & log(d)κd µ r .

50

Leave-one-out Approach for Matrix Completion

Combining the two bounds above and the bound of T1 in inequality (85), we obtain that
√
T1
k k2 ≤ r max
j≤r
σr

 X

d
1
1,m
∗
(1 − δmk )(−Mmk )Fkj
p
k=1

(86)

1
1
1
k∆0,m k2,∞ .
≤ k∆1,m k2,∞ +
16
8
8 × 2 2 κµr 2

The T2 term: We choose Q so that F 1,i − F 1,m Q = D 1,i,m . We bound the term T2 as
follows
(i)
kT2 k2 = keTm E 0,i (F 1,i − F 1,m Q)k2 = keT HΩ (M ∗ )D 1,i,m k2
(a)

(i)

≤ |||HΩ (M ∗ )|||op |||D 1,i,m |||F
s
(b)
d log d
kM ∗ k∞ |||D 1,i,m |||F
≤ 2c
p
s
(87)
d log d µr 1,i,m
|||D
|||F σ1
(c)2c
p
d
s
4c2 log(d)µ2 r 2
=
σ1 |||D 1,i,m |||F
dp
σr
≤ |||D 1,i,m |||F .
8
Here step (a) is due to Cauchy-Schwarz, step (b) is due to Lemma 14, and step (c) is due
2 4 7
to that M ∗ is µ-incoherent. The last step is due to p & κ µ rd log d .
To proceed, we further upper-bound D 1,i,m .
The term D 1,i,m

Recall that


(i)
F 1,i = Pr M ∗ + HΩ (−M ∗ ) ,



(m)
F 1,m = Pr M ∗ + HΩ (−M ∗ ) .
(i)

Due to Weyl’s inequality, M ∗ +HΩ (−M ∗ ) has eigengap between r-th and r+1-th eigenvalue
at least δ = σr − 2|||E 0,i |||op .
(i)
(m)
(i)
Let W = (HΩ − HΩ )(M ∗ ) which is the perturbation matrix between M ∗ + HΩ (−M ∗ )
(m)
1
and M ∗ + HΩ (−M ∗ ). We have |||W |||op ≤ |||E 0,i |||op + |||E 0,m |||op ≤ 16
σr from the analysis of
15
0,i
0,i
|||E |||op in equation (82) and thus δ = σr − 2|||E |||op ≥ 16 σr .
By the Davis-Kahan Theorem (Lemma 17), we have
√
√
2|||W F 1,m |||F
2|||W F 1,m |||F
2
1,i,m
|||D
|||F ≤
≤
≤ |||W F 1,m |||F .
(88)
δ − |||W |||op
7/8σr
σr

51

Leave-one-out Approach for Matrix Completion

(m)

(0)

The case i = 0 First consider the case i = 0. Under this scenario, we have HΩ − HΩ
being supported only on the m-th row and column. Thus
v
uX X
X X


δmk
δmk
u
∗ F 1,m 2 +
∗ F 1,m 2
)Mmk
)Mmk
(1 −
|||W F 1,m |||F = t
(1 −
mj
kj
p
p
j≤r k≤d

j≤r k≤d,k6=m

v
uX
u
1,m 2
= t (Fmj
)
j≤r

v
uX
u
1,m 2
≤ t (Fmj
)
j≤r

X

((1 −

k≤d,k6=m

X X

δmk
δmk
∗ )2 +
∗ F 1,m 2
)Mkm
)Mmk
(1 −
kj
p
p
j≤r k≤d

v
uX X
X

δmk
δmk
∗ )2 + u
∗ F 1,m 2
t
(1 −
((1 −
)Mkm
)Mmk
kj
p
p
j≤r k≤d

k≤d,k6=m

v
u X
X
√
δmk
δmk
u
1,m
∗
∗ )2 + r max
(1 −
Fkj
)Mmk
)Mmk
≤ kF 1,m k2,∞ t
((1 −
j≤r
p
p
k≤d

k≤d,k6=m

(a)

≤ (k∆1,m k2,∞ + kF ∗ k2,∞ )kHΩ (M ∗ )em k2 +
r

√

r max
j≤r

X
δmk
1,m
∗
(1 −
Fkj
)Mmk
p
k≤d

X
√
δmk
µr
1,m
∗
(1 −
)|||HΩ (M ∗ )|||op + r max
)Mmk
Fkj
j≤r
d
p
k≤d
s
r
X
(c)
√
µr
d log d µrσ1
δmk
1,m
∗
(1 −
≤ (k∆1,m k2,∞ +
Fkj
)(2c
) + r max
)Mmk
j≤r
d
p
d
p
k≤d
r 
 1

(d)
1
1 1
µr
1
k∆1,m k2,∞ +
.
≤ σr
16
2
32
32 2 2 κµr
d
q
Here step (a) is due to triangular inequality on ∆1,m and we use kF ∗ k2,∞ ≤ µr
d in step
∗
(b). The term |||HΩ (M )|||op of inequality (c) can be bounded using Lemma 14. The second
term of inequality (c) can be bounded as T1 in Subsection C.1.1; in particular, this term
 1 q
log(d)µ4 r 6 κ4
µr
1
1
1
1
is at most 64
k∆1,m k2,∞ + 32
, which establishes step
d when p &
d
216 κµr 2 2
(b)

≤ (k∆1,m k2,∞ +

(d).
Combining the above with inequality (88), we have for any m ∈ [d],
|||D

The case i 6= 0

1,0,m

 1 r
1
1
1
µr
1
1,m
k∆ k2,∞ +
.
|||F ≤
16
2
16
16 2 κµr 2
d

(89)

Similar to inequality (38), we have
|||D 1,i,m |||F ≤ |||D 1,0,i |||F + |||D 1,0,m |||F

 1 r
1 1,∞
1
1
1
µr
≤ k∆ k2,∞ +
.
16
2
8
8 2 κµr 2
d

52

(90)

Leave-one-out Approach for Matrix Completion

C.1.2. Complete the proof of the induction hypothesis for base case
Combing inequalities (83)–(84) and bounds of T1 , T2 , D 1,i,m (i.e., inequalities (86), (87) and
(90)), we have
1,i
∗
kFm·
− Fm·
G0,i k2
 1 r
(a) 1
1
1
16
µr
+ keTm E 0,i F 1,i k2
≤ 16
2
4 2 κµr 2
d
15σr

 1 r
(b) 1
µr 8
1
1
1
≤ 16
+ × k∆1,m k2,∞
2
4 2 κµr 2
d
7
8
r
 1 r 
1
1
1
1
1
µr
µr
1
1,∞
+ k∆ k2,∞ +
+
16
2
16
2
8 × 2 2 κµr
d
64
64 2 κµr 2
d
 1 r
µr 1 1,∞
1
1
1
≤ 16
+ k∆ k2,∞ ,
2
2 2 κµr 2
d
6

(91)

where step (a) is due to inequality (83) and step (b) is due to the bounds of T1 and T2 .
Since the above holds for all i, m, taking maximum of the LHS gives
 1 r
 1 r
1
1
1
1
1
3
µr 1 1,∞
µr
1,∞
1,∞
k∆ k2,∞ ≤
+ k∆ k2,∞ =⇒ k∆ k2,∞ ≤
.
16
2
16
2
2 2 κµr 2
d 6
5 2 κµr 2
d
We have therefore proved that the ℓ2,∞ error bound in the induction hypothesis is true for
the first iteration.
For the proximity condition in the induction hypothesis, using inequality (90) and what
we just proved, we have
 1 r
1 1,∞
1
1
1
µr
1,i,m
|||D
|||F ≤ k∆ k2,∞ +
8
8 216 κµr 2 2
d
 1 r
1
1
1
µr
≤
.
4 216 κµr 2 2
d
Taking maximum over i and m of the LHS shows that
 1 r
 1 r
1
1
1
1
1
µr
µr
1,∞
≤ 16
,
|||D |||F ≤
16
2
2
4 2 κµr 2
d
2 κµr 2
d
thereby proving the proximity condition.
Finally, using Lemma 7, we have
|||S

1,0,m

|||F = |||S

1,m,0

|||F ≤ 4κ|||W F

1,m

 1 r
1
1
µr
σ1
.
|||F ≤
16
2
2 2 κµr 2
d

Taking maximum over m gives the base case of the Non-commutativity bound in the induction hypothesis.
Recall that the operator norm bound in the induction hypothesis has been proved in
equation (82). We have therefore completed the proof of the base case t = 1.
53

Leave-one-out Approach for Matrix Completion

C.2. Step 1: Preliminary analysis of the induction step of ℓ2,∞ error bound
Now suppose the induction hypothesis is true for the t-th iteration (t ≥ 1) and we prove
that they are also true for the (t + 1)-th iteration.
Let us fix an index i ∈ {0, . . . , d} and an index m ∈ [d].
t,i
Operator norm
q bound of E : The ℓ2,∞ error bound induction hypothesis implies that
t,i is
kF t,i k2,∞ ≤ 2 µr
d . The error E


(i)
|||E t,i |||op = |||HΩ F t,i Λt,i ⊗ F t,i − M ∗ |||op
(i)

= |||HΩ F t,i Λt,i (F t,i )T − F ∗ Gt,i Λt,i (F t,i )T
{z
}
|
∗

t,i

t,i

t,i T

∗

R1
t,i

+ F G Λ (F ) − F G Λt,i (F ∗ Gt,i )T
|
{z
}
R2
t,i T

(92)

+ F ∗ Gt,i Λt,i (F ∗ G ) − F ∗ Gt,i Λ∗ (F ∗ Gt,i )T
{z
}
|
R3


+ F G Λ (F G ) − F ∗ Λ∗ (F ∗ )T |||op .
{z
}
|
∗

t,i

∗

∗

t,i T
R4

Each Ri can be bounded as follows
t,i

t,i

t,i

∗

t,i

t,i

t,i

t,i

kR1 k∞ ≤ k∆ k2,∞ kF Λ k2,∞ ≤ k∆ k2,∞ kF k2,∞ |||Λ |||op
t,i

t,i

kR2 k∞ ≤ k∆ k2,∞ kF G Λ k2,∞

 t
1
1 µr
≤ 4σ1 16
,
2
2 κµr 2
d

 t
1 µr
1
,
≤ 4σ1 16
2
2 κµr 2
d

kR3 k∞ ≤ kF ∗ Gt,i (Λt,i − Λ∗ )k2,∞ kF ∗ Gt,i k2,∞

≤ kF ∗ Gt,i k2,∞ |||(Λt,i − Λ∗ )|||op kF ∗ k2,∞
 t
1
1 µr
≤ 4σ1 16
,
2
2 κµr 2
d

where we use Wely’s in the term |||(Λt,i −Λ∗ )|||op ≤ |||E t−1,i |||op ≤

1
216 κµr 2

hypothesis on operator norm bound) and

 t
1
2

(93)
σr (our induction

kR4 k∞ ≤ kF ∗ k2,∞ kF ∗ (Gt,i Λ∗ (Gt,i )T − Λ∗ )k2,∞

≤ kF ∗ k2,∞ kF ∗ k2,∞ |||Gt,i Λ∗ (Gt,i )T − Λ∗ |||op

= kF ∗ k2,∞ kF ∗ k2,∞ |||Gt,i Λ∗ − Λ∗ Gt,i |||op
 t
1
1 µr
≤ (3κ + 2)σ1 16
,
2
2 κµr 2
d

54

(94)

Leave-one-out Approach for Matrix Completion

where we use Lemma 6 in the last inequality. We can now bound |||E t,i |||op further using
Lemma 15,
 t s
√
1
1 µr d log d
|||E t,i |||op ≤ rc(3 × 4 + (3κ + 2))σ1 16
2
2 κµr 2
d
p
(95)
 t+1
1
1
σr
≤
Cκ 216 κµr 2 2
2 2

for a large constant C > 0 where the last line is due to p & κ6 µ r dlog d . This proves the
induction hypothesis on |||E t,i |||op .
Recall that Λt,i is the diagonal matrix with top r eigenvalue of M ∗ + E t,i . The definition
of F t+1,i gives
(M ∗ + E t,i )F t+1,i = F t+1,i Λt,i .
Focusing on the m-th row, we have
t+1,i
∗
Fm·
− Fm·
Gt,i =eTm (M ∗ + E t,i )F t+1,i (Λt,i )−1 − eTm F ∗ Gt,i

=eTm (F ∗ Λ∗ ⊗ F ∗ )F t+1,i (Λt,i )−1 + eTm E t,i F t+1,i (Λt,i )−1 − eTm F ∗ Gt,i


=eTm F ∗ Λ∗ (F ∗ )T F t+1,i (Λt,i )−1 − (Λ∗ )−1 Gt,i + eTm E t,i F t+1,i (Λt,i )−1


= eTm F ∗ Λ∗ (F ∗ )T F t+1,i (Λ∗ )−1 − (Λ∗ )−1 Gt,i
{z
}
|
+

T1
 t,i −1
T ∗ ∗
∗ T t+1,i
em F Λ (F ) F
(Λ )

|

{z
T2


− (Λ∗ )−1 + eTm E t,i F t+1,i (Λt,i )−1 .
{z
}
} |
T3

We can bound T1 , T2 , T3 by following almost the same argument in bounding T1 , T2 , T3 in
Subsection B.2.1 and using Lemma 6 for the T1 , term here. The conclusion is
t+1,i
∗
kFm·
− Fm·
Gt,i k2
r  t+1
µr 1
1
C +1
1
≤
+ keTm E t,i F t+1,i k2
16
2
C 2 κµr
d 2
Cσr

(96)

for a large constant C > 0.
t+1,i k and finish the induction on ℓ
We next show how to bound keTm E t,i F
2
2,∞ error
q

bound. The goal is to have an additional c
that if i = m, then

eTm E t,i

µr
d

term with some small constant c < 1. Note

is zero and we are done. So in the following, we assume i 6= m.

55

Leave-one-out Approach for Matrix Completion

C.3. Step 2: Bounding keTm E t,i F t+1,i k2 and complete the induction on ℓ2,∞ error
bound
Let Q ∈ Rr×r and QQT = I where the exact value is left to be determined later. We have
eTm E t,i F t+1,i
=eTm E t,i F t+1,m Q + eTm E t,i (F t+1,i − F t+1,m Q)
(i)

=eTm HΩ (M t,i − M ∗ )F t+1,m Q + eTm E t,i (F t+1,i − F t+1,m Q)
(i)

(i)

= eTm HΩ (M t,m − M ∗ )F t+1,m Q + eTm HΩ (M t,i − M t,m )F t+1,m Q + eTm E t,i (F t+1,i − F t+1,m Q) .
{z
}
{z
} |
{z
} |
|
T1

T3

T2

(97)

The first term T1 :

For T1 , we bound it as follows
(i)

kT1 k2 = keTm HΩ (M t,m − M ∗ )F t+1,m k2

 X
d
√
1
t+1,m
t,m
∗
≤ r max
.
(1 − δmk )(Mmk − Mmk )Fkj
j≤r
p

(98)

k=1

Since F t+1,m is independence of δmk for all k, using Bernstein, Lemma 8, and C = 12,
we have for any j ≤ r with probability 1 − d−6 ,
d
X
1
t,m
t+1,m
∗
(1 − δmk )(Mmk
− Mmk
)Fkj
|
p
i=1
s
 C log d t+1,m

C log d t+1,m
t,m
∗
kF
k2,∞ kMm·
kF
k2,∞ kM t,m − M ∗ k∞ .
− Mm·
k2 +
≤
p
p
{z
}
{z
} |
|

|

R2

R1

Now decompose M t,i − M ∗ into four terms as what we did in (92) and bound each term
separately in terms of k · k∞ and k · k2 , we have
r
r
µr t,m
µr t−1,i
t,m
t,m
∗
|||∆ |||F + 6κ
|||E
|||op σ1 ,
kMm· − Mm· k2 ≤ 2σ1 k∆ k2,∞ + 2σ1
d
d
r
r
µr
µr
µr t,m
t,m
∗
kMm·
− Mm·
k∞ ≤ 4σ1 k∆t,m k2,∞
+ 2σ1
k∆ k2,∞ + 6κ |||E t−1,i |||op σ1 .
d
d
d
Similar to how we bound R1 , R2 in bounding T1 in Section B.4 and using induction hypothesis on ∆t,i , |||E t−1,i |||op , we have
R1
1
1
√ k∆t,m k2,∞ + √ k∆t+1,m k2,∞ ,
≤
σr
16 × 2 r
16 r
R2
1
1
√ k∆t,m k2,∞
≤ √ k∆t+1,m k2,∞ +
σr
16 r
16 × 2 r
as p &

log(d)κ6 µ4 r 6
.
d

56

Leave-one-out Approach for Matrix Completion

Putting the pieces together, we can bound T1 as follows
k

√
T1
k2 ≤ r max
j≤r
σr

 X
d
k=1

1
t,m
t+1,m
∗
− Mmk
)Fkj
(1 − δmk )(Mmk
p



(99)

1
1
≤ k∆t+1,m k2,∞ +
k∆t,m k2,∞ .
8
8×2
The T2 term We first decompose M t,i − M t,m into three terms. We have
M t,m − M t,i = F t,m Λt,m ⊗ F t,m − F t,i Λt,i ⊗ F t,i

= F t,m Λt,m ⊗ F t,m − F t,i Gt,m,i Λt,m ⊗ F t,m

+ F t,i Gt,m,i Λt,m ⊗ F t,m − F t,i Λt,i Gt,m,i ⊗ F t,m
t,i

t,i

t,m,i

+F Λ G
=D

t,m,i

t,m

Λ

⊗F

t,m

⊗F

t,m

t,i

t,i

−F Λ

t,i

− F (S

t,m,i

⊗F

(100)

t,i

) ⊗ F t,m + F t,i Λt,i Gt,m,i ⊗ D t,m,i .

We may decompose T2 into the following three terms
(i)

kT2 k2 =keTm HΩ (M t,i − M t,m )F t+1,m Qk2
(i)

(i)

≤ keTm HΩ (D t,m,i Λt,m ⊗ F t,m )F t+1,m Qk2 + keTm HΩ (F t,i (S t,m,i ) ⊗ F t,m )F t+1,m Qk2
|
{z
} |
{z
}
R1

+

R2

(i)
keTm HΩ (F t,i Λt,i Gt,m,i

|

{z

R3

Using |||S t,m,i |||

op

≤

8κ(|||E t,i |||

op

⊗ D t,m,i )F t+1,m Qk2 .
}

+|||E t,m |||

op

) by Lemma 7, we have

|||S t,m,i |||

op

≤

1
8σ1 216 κµr
2

 t q
1
2

By a similar argument as bounding R1 in term T2 in Subsection B.4, we have w.h.p. uniformly for all i, m,
 t+1 r
R1 + R2
1
1
1
1
µr
+ k∆t+1,m k2,∞
≤
16
2
σr
16 2 κµr 2
d
32
6 4 6

given p & κ µ rd log d .
Using a similar argument as bounding R2 in the term T2 in Subsection B.4, we have
w.h.p. uniformly for all i, m,
 t+1 r
1
1
1
1
µr
R3
+ k∆t+1,m k2,∞
≤
16
2
σr
32 2 κµr 2
d
32
6 4 6

given p & κ µ rd log d .
Putting bounds of R1 , R2 , R3 above together, we have the following bound for T2 ,
 t+1 r
1
µr
3
1
1
kT2 k2
t+1,m
k2,∞ +
.
(101)
≤ k∆
16
2
σr
16
32 2 κµr 2
d
57

µr
d .

Leave-one-out Approach for Matrix Completion

The T3 term Now we bound the third term T3 in inequality (97). We have
kT3 k2 = keTm E t,i (F t+1,i − F t+1,m Q)k2
(i)

= keTm HΩ (M t,i − M ∗ )(F t+1,i − F t+1,m Q)k2

(102)

(i)

(i)

≤ keTm HΩ (M t,i − M ∗ )∆t+1,i k2 + keTm HΩ (M t,i − M ∗ )∆t+1,m k2
where the last line is due to proper choice of Q and k · k2 is unitary invariant.
Now for the first term of the RHS of inequality (102), we have
(i)

keTm HΩ (M t,i − M ∗ )∆t+1,i k2
v

uX X
u
δmj t+1,i 2
t,i
∗
t
=
)∆jl
(M − M )ml (1 −
p
l≤r

j≤d

(103)

s
(a) X
t,i
∗ k k∆t+1,i k + dkM t,i − M ∗ k k∆t+1,i k )2
≤
− Mm·
(2dkMm·
m·
∞
∞
∞
m· ∞
l≤r

√
t,i
∗
≤ 3 rdkMm·
− Mm·
k∞ k∆t+1,i k∞ .

Here we use the fact that if p &

log d
d ,

w.h.p., uniformly for all j,
X
δij ≤ 2pd
j

in step (a).
t,i
∗ k can be bounded by decomposing it into four terms as bounding
The term kMm·
−Mm·
∞
t,i
|||E |||op in Subsection C.1. The conclusion there using inequalities (93) and (94) is
 t
1
1 µr
t,i
∗
kMm·
− Mm·
k∞ ≤ 16σ1 16
.
2 κµr 2 2
d
(i)

Now we can continue the chain in inequality (103) in bounding the term keTm HΩ (M t,i −
M ∗ )∆t+1,i k2 and have
1 T (i)
ke H (M t,i − M ∗ )∆t+1,i k2
σr m Ω
 t
√
1 µr t+1,i
1
k∆
k2,∞
≤3 rd × 16 2 2
64 µr 2
d
1
≤ k∆t+1,i k2,∞ .
32

(104)

Similarly, we have for the second term of RHS of inequality (102) in bounding T3 ,
(i)

keTm HΩ (M t,i − M ∗ )∆t+1,m k2 ≤

1
k∆t+1,m k2,∞ .
32

(105)

Combining inequality (102),(103) and (105), we have with proper choice of Q = Gt,i,m ,
kT3 k2 = keTm E t,i (F t+1,i − F t+1,m Q)k2 ≤
58

1
k∆t+1,∞ k2,∞ .
16

(106)

Leave-one-out Approach for Matrix Completion

Completing ℓ2,∞ error bound induction hypothesis: Now, combining inequalities
(96)-(97), and bounds of T1 , T2 , T3 , (i.e., inequalities (99),(101) and (106)), we have
k∆t+1,i
m· k2

 t+1 r

1
1
µr 100 1 t+1,m
1
+
k∆
k2,∞
≤ 16
4 2 κµr 2 2
d
99 8

 t+1 r
 t+1 r
1
1
1
1
1
1
3
1
µr
µr
t+1,m
t+1,∞
+
+ k∆
k2,∞ +
+ k∆
k2,∞
8 216 κµr 2 2
d
16
32 216 κµr 2 2
d
16
 t+1 r
1
1
µr 25 t+1,∞
1
+ k∆
k2,∞ .
≤ 16
2
2 2 κµr 2
d
99
(107)
Taking maximum over i, m of LHS and rearranging the terms gives the inequality for the
ℓ2,∞ error bound,
 t+1 r
1
1
µr
t+1,∞
k∆
k2,∞ ≤ 16
.
2
2 κµr 2
d
C.4. Step 3: Proving proximity and Non-commutativity bound
Recall that



(i)
F t+1,i Λt+1,i ⊗ F t+1,i = Pr M ∗ + HΩ (M t,i − M ∗ ) ,


(m)
F t+1,m Λt+1,m ⊗ F t+1,m = Pr M ∗ + HΩ (M t,m − M ∗ ) .
(i)

By Weyl’s, M ∗ + HΩ (M t,i − M ∗ ) has eigen gap between r-th and r + 1-th eigenvalue at
least δ = σr − 2|||E t,i |||op .
Let
(i)

(i)

(m)

W = (HΩ − HΩ )(M t,m − M ∗ ) +
{z
}
|
discrepancy error W (a)

HΩ (M t,i − M t,m )
|
{z
}

.

ℓ2 contraction term of SVP operator W (b)
(i)

(m)

which is the perturbation matrix between M ∗ +HΩ (M t,i −M ∗ ) and M ∗ +HΩ (M t,m −M ∗ ).
We have |||W |||op ≤ |||E t,i |||op + |||E t,m |||op ≤ σ16r following the analysis of |||E t,i |||op in inequality
(95) and so δ = σr − 2|||E 0,i |||op ≥ σr − σ16r .
By Davis-Kahan, we have
√
2|||W F t+1,m |||F
t+1,i,m
|||D
|||F ≤
σr − |||W |||op
√
2|||W F t+1,m |||F
(108)
≤
7/8σr
2
≤ (|||W (a) F t+1,m |||F + |||W (b) F t+1,m |||F ).
σr
We first consider the case i = 0.

59

Leave-one-out Approach for Matrix Completion

C.4.1. The W (a) term
Similar to bounding W (a) in Section B.5, we have
1
|||W (a) F t+1,m |||F
σr


X
√
1
δmk
t+1,m
t,m
∗
t+1,m
∗
t,m
∗
≤
(1 −
)(Mmk − Mmk )Fkj
(k∆
k2,∞ + kF k2,∞ )kHΩ (M
− M )em k2 + r max
j≤r
σr
p
k≤d
r


X
(a) 1
√
µr
δmk
t+1,m
t,m
∗
t+1,m
≤
(1 −
)Fkj
)|||HΩ (M t,m − M ∗ )|||op + r max
)(Mmk
− Mmk
|
(k∆
k2,∞ +
j≤r
σr
d
p
k≤d
r


 t+1 
σr
1
1
1
µr
t+1,m
)
(k∆
k2,∞ +
≤
16
2
σr
d
Cκ 2 κµr 2

σr t+1,m
σr
t,m
+ k∆
k2,∞ + k∆ k2,∞ |
C
C
 t+1 r
1
1
µr
1
,
≤
32 216 κµr 2 2
d
(109)
t,m
∗
t,m
where |||HΩ (M − M )|||op = |||E |||op in line (a) can be bounded using inequality (95) and
the second term of line (a) can be bounded as T1 in inequality (99). The last inequality is
4 6 6
due to the first induction hypothesis and p & µ r κd log d .
C.4.2. The W (b) term
We have
|||W (b) F t+1,m |||F = |||HΩ (M t − M t,m )F t+1,m |||F

≤ |||HΩ (D t,m,0 Λt,m ⊗ F t,m )F t+1,m |||F + |||HΩ (F t (S t,m,0 ) ⊗ F t,m )F t+1,m |||F
{z
} |
{z
}
|
t

t

R1
t,m,i

+ |||HΩ (F Λ G
|

⊗D
{z

R2

t,m,0

)F

R3

t+1,m

|||F .
}

Here F t,m is understood as the one closest to F t in Frobenius norm.
The term R2 and R3 can be bounded as inequality (63). Specifically, we have

60

(110)

Leave-one-out Approach for Matrix Completion

R2 = |||HΩ (F t (S t,m,0 ) ⊗ F t,m )F t+1,m |||F
s
3
d log d t
≤ r 2 max 2c
kF k2,∞ kF t+1,m k2,∞ |||F t,m (S t,m,0 )T |||F
l1 ,l2 ≤r
p
s
3
d log d t
≤ r 2 max 2c
kF k2,∞ kF t+1,m k2,∞ |||F t,m |||op |||S t,m,0 |||F
l1 ,l2 ≤r
p
s
 t r
(a) 3
d log d µr
µr
1
1
≤ r 2 8cσ1
16
2
p
d 2 κµr 2
d
 t+1 r
1
1
µr
σr
,
≤
16
2
64 2 κµr 2
d

(111)

where (a) is due to our ℓ2,∞ error bound induction hypothesis for the t case and the t + 1
2 2 5
case and the last inequality is due to p & κ µ rd log d . We also have
R3 = |||HΩ (F t Λt Gt,m,0 ⊗ D t,m,0 )F t+1,m |||F
s
3
d log d t t,i t,m,0
kF Λ G
k2,∞ kF t+1,m k2,∞ |||D t,m,0 |||F
≤ r 2 max 2c
l1 ,l2 ≤r
p
s
 t r
(a) 3
1
1
d log d µr
µr
≤ r 2 8cσ1
16
2
p
d 2 κµr 2
d
 t+1 r
σr
1
1
µr
≤
.
16
2
64 2 κµr 2
d

(112)

where (a) is due to our ℓ2,∞ error bound induction hypothesis for the t case and the t + 1
2 2 5
case and the last is due to p & κ µ rd log d .
For the R1 term, we can follow inequalities (64), (65), (66) and (67) and have
 t+1 r
σr
1
1
µr
t,m,0 t,m
t,m
t+1,m
(113)
R1 = |||HΩ (D
Λ ⊗ F )F
|||F ≤
.
16
2
64 2 κµr 2
d
d
We need p & κ2 µr log
in proving an inequality similar to (67) using Lemma 11.
d
Combing inequalities (110), (111),(112) and (113), we have
 t+1 r
σr
1
1
µr
(b) t+1,m
|||W F
|||F ≤
.
16
2
16 2 κµr 2
d

(114)

C.4.3. Completing proximity and non-commutativity induction hypothesis
Using inequality (108), (109) and (114), we have for i = 0, and any m ∈ [d]
2
(|||W (a) F t+1,m |||F + |||W (b) F t+1,m |||F )
σr
 t+1 r
1
µr
1
1
.
≤
16
2
2 2 κµr 2
d

|||D t+1,0,m |||F ≤

61

(115)

Leave-one-out Approach for Matrix Completion

A similar argument as inequality (38) gives
|||D

t+1,i,m

 t+1 r
µr
1
1
|||F ≤ 16
.
2
2 κµr 2
d

Taking maximum over i, m gives the proximity.
Finally, using Lemma 7, we have
|||S

t,0,m

|||F = |||S

t,m,0

|||F ≤ 4κ|||W F

t+1,m

 t+1 r
1
1
µr
σ1
.
|||F ≤
16
2
2 2 κµr 2
d

Taking maximum over m gives the non-commutativity bound induction hypothesis.
Recall we prove the operator norm bound in equation (95). We have therefore completed
the induction for t ≤ t0 = 5 log2 d + 12.
C.5. Step 3: Bounds on infinite number of iterations
We have proved that for each t ≤ t0 = 5 log2 d + 12, with high probability
r
 t r
1
1
µr
µr
t,∞
t,i
(ℓ2,∞ error bound) k∆ k2,∞ ≤ 16
=⇒ kF k2,∞ ≤ 2
2
2 κµr 2
d
d
 t
1
1
(Operator norm bound) |||E t−1,∞ |||op ≤ 16
σr ,
2
2 κµr 2
and so the above holds uniformly for all t ≤ 5 log2 d + 12. The previous argument also
works for each t ≥ t0 = 5 log2 d + 12. But since there are infinite number of t ≥ t0 , the
probability for the above to hold for all t using union bound won’t work. We now turn to
prove inequality (80).
We prove that with high probability, for all t ≥ t0 , we have
1
|||M t+1 − M ∗ |||F ≤ |||M t − M ∗ |||F
2

(116)

which implies the following linear convergence result
|||M t − M ∗ |||F ≤

1
2t−t0

|||M t0 − M ∗ |||F .

Since t0 = 5 log2 d + 12, using an argument similar to inequality (93), we have
|||M t0 − M ∗ |||F ≤ dkM t0 − M ∗ k∞ ≤ (3 × 4 + (3κ + 2))σ1

1
216 κµr 2

1 µr
2d5 d

and kM t0 k∞ ≤ 2 µr
d σ1 .
Suppose the base case t = t0 for inequality (116) is verified and it is true for the t-th
iteration. We have
|||M t − M ∗ |||F ≤ |||M t0 − M ∗ |||F ,
using the induction hypothesis, i.e., inequality (116).

62

Leave-one-out Approach for Matrix Completion

This implies that
kM t k∞ ≤ kM ∗ k∞ + kM t − M ∗ k∞ ≤ kM ∗ k∞ + |||M t − M ∗ |||F ≤ 2
kD̃ t k∞ ≤ |||D̃ t |||F ≤ |||D̃ t0 |||F ≤

µr
σ1 ,
d

1 σ1 µr
,
642 d2 d

(117)
(118)
6 4 6

where D̃ t : = M t − M ∗ . By previous analysis of |||E t |||op , we know that if p & κ µ rd log d ,
1
σr and so the first r eigenvalue of M ∗ + E t is positive and there is an
then |||E t |||op ≤ 16
eigengap of M ∗ + E t with magnitude at least 81 σr between the r-th eigenvalue and r + 1-th
eigenvalue.
Under the definition of M t+1 , we have
|||M t+1 − (M ∗ + E t )|||2F ≤|||E t |||2F .

(119)

This also gives
|||M t+1 − M ∗ |||F ≤ |||M t+1 − (M ∗ + E t )|||F + |||E t |||F = 2|||E t |||F ≤ 2 ×

1 σ1
,
642 κ2

(120)

where the last inequality is due to inequality (118), the fact that kD̃ t k∞ ≤ |||D̃ t |||F , |||E t |||F ≤
√
6 4 6
d|||E t |||op and Lemma 15 with p & κ µ rd log d . The above then gives
kM t+1 k∞ ≤ kM t+1 − M ∗ k∞ + kM ∗ k∞ ≤ |||M t+1 − M ∗ |||F +

µr
µr
≤ 2 σ1 .
d
d

(121)

Due to inequalities (117), (118), (120) and (121), the premise of Proposition 2 is satisfied
for M + = M t+1 , M = M t . By expanding the square of the LHS of inequality (119), we
have
|||D̃ t+1 |||2F ≤ −2hD̃ t+1 , E t i
1
≤ −2hD̃ t+1 , (I − ΠΩ )(D̃ t )i
p
1
≤ −2hD̃ t+1 , (I − ΠΩ )(D̃ t )i
p
1
≤ 2| hΠΩ D̃ t+1 , ΠΩ D̃ t i − hD̃ t+1 , D̃ t i|
p
1
≤ 2 × |||D̃ t+1 |||F |||D̃ t |||F ,
4
where the last line is due to Proposition 2. The last inequality implies that
1
1
|||D̃ t+1 |||2F ≤ |||D̃ t |||F |||D̃ t+1 |||F =⇒ |||D̃ t+1 |||F ≤ |||D̃ t |||F .
2
2
The above arguments also works for the case t = t0 since the premises of Proposition 2 is
also satisfied due to the choice of t0 . We see the base case is also verified and the proof is
completed.

63

Leave-one-out Approach for Matrix Completion

Appendix D. Auxiliary lemmas
In this section, we state several auxiliary technical results that are used in the proofs of our
main theorem.
Lemma 8 (Bernstein) Let X1 , . . . , Xn be n independent random variable with |Xi | ≤ B
with mean 0, we have
n
X




−t2
P
Xi | ≥ t) ≤ 2 exp
P(|
.
2 ni=1 E(Xi2 ) + 23 Bt
i=1

Lemma 9 Let F ∈ Rd×r and M = F F T . We have

kM − M ∗ k∞ ≤ kF ∗ k2,∞ kF − F ∗ k2,∞ + kF k2,∞ kF − F ∗ k2,∞
and for any m ≤ d,
∗
kMm· − Mm·
k2 ≤ kF k2,∞ |||F − F ∗ |||op + kF − F ∗ k2,∞ |||F ∗ |||op .

Proof Direct computation yields
kM − M ∗ k∞ = kF ⊗ F − F ⊗ F ∗ + F ⊗ F ∗ − F ∗ ⊗ F ∗ k∞
(a)

≤ kF ⊗ (F − F ∗ )k∞ + k(F − F ∗ ) ⊗ F ∗ k∞

(b)

≤ kF ∗ k2,∞ kF − F ∗ k2,∞ + kF k2,∞ kF − F ∗ k2,∞ ,

where inequality (a) is due to the property of norm and inequality (b) is due to CauchySchwarz. Similarly, we have
∗
kMm· − Mm·
k2 ≤ kFm· ⊗ (F − F ∗ )k2 + k(F − F ∗ )m· ⊗ F ∗ k2

≤ kF k2,∞ |||F − F ∗ |||op + kF − F ∗ k2,∞ |||F ∗ |||op .

Lemma 10 In the setting of SMC(M ∗ , δ), for fixed F, F ′ ∈ Rd×r , M = F F T and any
m, k, j, we have


1
kF ′ k2,∞
′
∗
∗
∗
∗
|(1 − δmk )(Mmk − Mmk )Fkj | ≤
kF k2,∞ kF − F k2,∞ + kF k2,∞ kF − F k2,∞
p
p
(122)
and

2 
 X
d
1
′
∗
E
(1 − δmk )(Mm,k − Mmk )Fkj
p
k=1

2
1 ′ 2
∗
∗
∗
≤ kF k2,∞ kF k2,∞ |||F − F |||op + (kF − F k2,∞ |||F |||op .
p
64

(123)

Leave-one-out Approach for Matrix Completion

Consequently, using Bernstein, Lemma 8, we have for any m, j and C > 0
|

d
X
i=1

1
′
∗
(1 − δmk )(Mmk − Mmk
|
)Fkj
p

s


C log d ′
kF k2,∞ kF k2,∞ |||F − F ∗ |||op + kF − F ∗ k2,∞ |||F ∗ |||op
p

C log d ′
+
kF k2,∞ kF ∗ k2,∞ kF − F ∗ k2,∞ + kF k2,∞ kF − F ∗ k2,∞ ,
p
≤

(124)

with probability at least 1 − d−C/2 .
Proof We have

1
1
′
∗
|(1 − δmk )(Mmk − Mmk
| ≤ kM − M ∗ k∞ kF·j′ k∞
)Fkj
p
p
and then we use Lemma 9 and kF·j′ k∞ ≤ kF ′ k2,∞ to deduce the first claimed inequality
(122).
For the second claimed inequality (123), we have
 X
2 
d
1
′
∗
E
(1 − δmk )(Mmk − Mmk )Fkj
p
k=1

2
d
X
1
′
∗
E (1 − δmk )(Mmk − Mmk )Fkj
=
p
≤

k=1
d
X

1
p

k=1

∗
′
(Mmk − Mmk
)Fkj

2

1
∗ 2
≤ kF·j′ k2∞ kMm· − Mm·
k2 .
p

Using Lemma 9 and kF·j′ k∞ ≤ kF ′ k2,∞ , we prove the claim.
The last one is a simple consequence
of Bernstein inequality by setting Xi =

 (1 −
′
kF k2,∞
1
′
∗
kF ∗ k2,∞ kF − F ∗ k2,∞ + kF k2,∞ kF − F ∗ k2,∞ . The
p δmk )(Mmk − Mmk )Fkj , B =
p

result follows.

Lemma 11 In the setting of SMC(M ∗ , p), for each ǫ ∈ (0, 1), if p &
probability at least 1 − 2d−3 , we have
|||HΩ (W ⊗ F ∗ )F ∗ |||F ≤ ǫ|||W |||F
where W ∈ Rd×r and F ∗ is orthonormal.

65

µr log d
,
ǫ2 d

then with

Leave-one-out Approach for Matrix Completion

Proof We have
|||HΩ (W ⊗ F ∗ )F ∗ |||F =

sup
|||u|||F =1,u∈Rd×r

=

sup
|||u|||F =1,u∈Rd×r

=
=

hHΩ (W ⊗ F ∗ )F ∗ , ui
hHΩ (W ⊗ F ∗ ), u ⊗ F ∗ i

1
h(I − ΠΩ )(W ⊗ F ∗ ), u ⊗ F ∗ i
p
|||u|||F =1,u∈Rd×r
sup

1
hW ⊗ F ∗ , u ⊗ F ∗ i − hΠΩ (W ⊗ F ∗ ), ΠΩ (u ⊗ F ∗ )i
p
|||u|||F =1,u∈Rd×r
sup

(a)

≤ǫ

sup
|||u|||F

=1,u∈Rd×r

|||F ∗ |||2op |||W |||F |||u|||F

(b)

= ǫ|||W |||F .

We use Lemma 18 in the step (a) and use the fact that
in equality (b).

|||F ∗ |||

op

= 1 since

F∗

(125)
is orthonormal

Lemma 12 (Ge et al., 2017, Lemma 6) Given matrices F, F ∗ ∈ Rd×r , let M = F ⊗ F and
M + = F + ⊗ F + . Also let ∆ = F − F + O⋆ where O = arg minO∈Rr×r ,O⊗O=I |||F − F + O|||F .
We have
|||∆ ⊗ ∆|||2F ≤ 2|||M − M + |||2F
and
σr (M + )|||∆|||2F ≤

1
√
|||M − M + |||2F .
2( 2 − 1)

For the next proposition, recall the definition of the condition number κ =
the true low-rank matrix M ∗ .

σ1 (M ∗ )
σr (M ∗ )

of

2 2 6

Proposition 2 In the setting of SMC(M ∗ , p), if p & µ r κd log d , then with probability at
least 1 − 4d−2 , the following holds simultaneously for all rank-r matrices M, M + ∈ S d×d
1
1
1
1
∗
∗
∗
+
∗
∗
with kM k∞ ≤ 2 µr
d σ1 (M ), |||M − M |||F ≤ 642 × κ2 σ1 (M ), |||M − M |||F ≤ 642 × κ2 σ1 (M )
µr
∗
+
and kM k∞ ≤ 2 d σ1 (M ),
1
1
hW + , W i − hΠΩ (W + ), ΠΩ (W )i ≤ |||W + |||F |||W |||F
p
4
where W + = M + − M ∗ , W = M − M ∗ .
Proof Let M = F ⊗ F and M + = F + ⊗ F + where F, F + ∈ Rn×r . Also let Q, Q+ ∈ Rr×r
so that Q = inf Q∈Rr×r ,QQT |||F Q − F ∗ |||F , Q+ = inf Q∈Rr×r ,QQT |||F + Q − F ∗ |||F . We denote
∆ = F Q − F ∗ and ∆+ = F + Q − F ∗ . Using Lemma 12, we have
r
r
1
1
1
3
σr (M ∗ )
σr (M ∗ )
+
+
|||W
|||
≤
3
×
,
|||∆
|||
≤
3
.
|||∆|||F ≤ √ |||W |||F ≤ 3 × 2
√
F
F
σr
64
κ2
σr
642
κ2
(126)
66

Leave-one-out Approach for Matrix Completion

The difference W can be expressed as
W = F ∗ ⊗ ∆ + ∆ ⊗ F ∗ + ∆ ⊗ ∆,
with a similar expression for W + . With these expressions, we decompose the inner product
of interest as
1
hW + , W i − hΠΩ (W + ), ΠΩ (W )i
p
1
= hF ∗ ⊗ ∆ + ∆ ⊗ F ∗ , F ∗ ⊗ ∆+ + ∆+ ⊗ F ∗ i − hΠΩ (F ∗ ⊗ ∆ + ∆ ⊗ F ∗ ), ΠΩ (F ∗ ⊗ ∆+ + ∆+ ⊗ F ∗ )i
p
{z
}
|
T1

1
+ hF ∗ ⊗ ∆ + ∆ ⊗ F ∗ , ∆+ ⊗ ∆+ i − hΠΩ (F ∗ ⊗ ∆ + ∆ ⊗ F ∗ ), ΠΩ (∆+ ⊗ ∆+ )i
p
|
{z
}
T2

1
+ hF ∗ ⊗ ∆+ + ∆+ ⊗ F ∗ , ∆ ⊗ ∆i − hΠΩ (F ∗ ⊗ ∆+ + ∆+ ⊗ F ∗ ), ΠΩ (∆ ⊗ ∆)i
p
{z
}
|
T3

1
+ h∆+ ⊗ ∆+ , ∆ ⊗ ∆i − hΠΩ (∆+ ⊗ ∆+ ), ΠΩ (∆ ⊗ ∆)i .
p
{z
}
|
T4

For T1 , we use Lemma 18 and choose ǫ ≤
we have
|T1 | ≤

1
κ,

(127)
which ensures with probability 1 − 2d−3 ,

1
1
|||F ∗ ⊗ ∆|||F |||F ∗ ⊗ ∆+ |||F ≤ 4ǫσ1 (M ∗ )|||∆|||F |||∆+ |||F ≤ |||W + |||F |||W |||F .
24
8

To bound T2 to T4 , we recall the premise of the proposition that max{{kF
⊗F k∞ , kF + ⊗
q
∗

∗
F + k∞ } ≤ 2 µr
max{kF k2,∞ , kF + k2,∞ } ≤ 2µrσ1d(M ) . It follows
d σ1 (M ). This implies that
q
q
∗
∗
that k∆k2,∞ ≤ kF k2,∞ + kF ∗ k2,∞ ≤ 2 2µrσ1d(M ) and similarly k∆+ k2,∞ ≤ 2 2µrσ1d(M ) .
These bounds allows us to use Lemma 19. We have with probability at least 1−2d−3 −2d−4 ,

1
1
|T2 | ≤ ||| √ ΠΩ (F ∗ ⊗ ∆ + ∆ ⊗ F ∗ )|||F ||| √ ΠΩ (∆+ ⊗ ∆+ )|||F + |||F ∗ ⊗ ∆ + ∆ ⊗ F ∗ |||F |||∆+ ⊗ ∆+ |||F
p
p
(a)
p
≤ 4|||F ∗ ⊗ ∆|||F (1 + ǫ)|||∆+ |||4F + ǫσ1 (M ∗ )|||∆+ |||2F + 2|||F ∗ ⊗ ∆|||F |||∆+ |||2F
p
p
p
≤ 4 σ1 (M ∗ )|||∆|||F (2 (1 + ǫ)|||∆+ |||2F + 2 ǫσ1 (M ∗ )|||∆+ |||F ) + 2|||∆|||F |||∆+ |||2F
r
√
1+ǫ
1
≤ (24
× 2 + 4 ǫ)σ1 (M ∗ )|||∆|||F |||∆+ |||F
2
κ
64
1
+
≤ |||W |||F |||W |||F .
24
(128)
We use Lemma 18 for the term ||| √1p ΠΩ (F ∗ ⊗∆+∆⊗F ∗ )|||F and Lemma 19 for ||| √1p ΠΩ (∆+ ⊗

∆+ )|||F in step (a). The last one needs that ǫ is much smaller than
67

1
.
κ2

This requirement

Leave-one-out Approach for Matrix Completion

2 2

4

d)κ
in Lemma 19. A similar argument shows that |T3 | ≤
on ǫ then requires p & µ r (log
d
1
+
−3 + d−4 ).
24 |||W |||F |||W |||F with probability at least 1 − 2(d
For T4 , using Lemma 18 again, we have

1
1
|T4 | ≤ ||| √ ΠΩ (∆ ⊗ ∆)|||F ||| √ ΠΩ (∆+ ⊗ ∆+ )|||F + |||∆|||2F |||∆+ |||2F
p
p
p
p
≤ (1 + ǫ)|||∆|||4F + ǫσ1 (M ∗ )|||∆|||2F (1 + ǫ)|||∆+ |||4F + ǫσ1 (M ∗ )|||∆+ |||2F + |||∆|||2F |||∆+ |||2F
p
p
p
p
≤ (2 (1 + ǫ)|||∆|||2F + 2 ǫσ1 (M ∗ )|||∆|||F )(2 (1 + ǫ)|||∆+ |||2F + 2 ǫσ1 (M ∗ )|||∆+ |||F ) + |||∆|||2F |||∆+ |||2F
1
≤ |||W + |||F |||W |||F .
24
(129)
The last line is due to that ǫ is much smaller than κ12 and max{|||∆+ |||F , |||∆|||F } ≤ 3 ×
q
σr (M ∗ )
1
.
642
κ2
Combing pieces and inequality (127), we have
1
|hW + , W i − hΠΩ (W + ), ΠΩ (W )i| ≤ |T1 | + |T2 | + |T3 | + |T4 |
p


1
1
1
1
≤
+
+
+
|||W + |||F |||W |||F
8 24 24 24
1
= |||W |||F |||W + |||F .
4
This completes the proof of Proposition 2.
Lemma 13 (Matrix Bernstein) (Tropp, 2012) Consider a finite sequence {Zk } of independent, random n1 × n2 matrices that satisfy
EZ
Pk = 0Tand |||Zk |||op ≤ D
P the assumption
2
T
almost surly. Let σ be the maximum of ||| k E[Zk Zk ]|||op and ||| k EZk Zk |||op . Then for
all t ≥ 0 we have


 X

t2
.
P |||
Zk |||op ≥ t ≤ (n1 + n2 ) exp − 2 2
2σ + 3 Dt
k
Lemma 14 In the setting of SMC(M ∗ , p) or MC(M ∗ , p), for each fixed matrix Z ∈ Rd×d ,
if p ≥ logd d , there is a numerical constant c > 1 such that w.h.p.
s

(i)

|||HΩ (Z)|||op ≤ |||HΩ (Z)|||op ≤ 2c

d log d
kZk∞ .
p

Proof We prove the case of SM C(M ∗ , p). The case of M C(M ∗ , p) is proved in Candès et al.
(2011, Lemma 3.1) and Chen et al. (2013, Lemma 12) already. Since the i-th column and
(i)
(i)
i-row of HΩ (Z) is zero, we have |||HΩ (Z)|||op ≤ |||HΩ (Z)|||op . We shall use Lemma 13 to

68

Leave-one-out Approach for Matrix Completion

bound the operator norm of HΩ (Z). Since
1
HΩ (Z) = (I − ΠΩ )(Z)
p
1X
=Z−
Zij δij ei eTj
p
i,j

(a)

=

d
X
X
1
1
(1 − δij )Zii ei eTi
(1 − δij )(Zij ei eTj + Zji ej eTi ) +
p
p
i=1

i>j

=

X

Ξij +

d
X

Ξii

i=1

i>j

where Ξij := (1 − p1 δij )(Zij ei eTj + Zji ej eTi ) and Ξii := 1 − p1 δij )Zii ei eTi . We use the fact that
δij = δji for symmetric matrix completion in step (a).
Now, observe that E(Ξij ) = 0, |||Ξij |||op ≤ p2 kZk∞ , E(Ξii ) = 0, |||Ξii |||op ≤ 1p kZk∞ and
|||E

X
i>j

Ξij ΞTij

+

d
X
i=1

Ξii ΞTii



d

|||op

X
X
1
2
2
Zii2 ei eTi |||op
= ( − 1)|||
Zij
ei eTi + Zji
ej eTj +
p
i=1

i>j

d
X

1
= ( − 1)||| diag(
p
d
≤ ( )kZk2∞ .
p

2
Z1i
,...,

i=1

j
X

2
Zjk

k=1

+

d
X

k=j+1

2
Zkj
,...,

d
X

2
Zdi
)|||op

i=1

It follows from Lemma 13 that
|||HΩ (Z)|||op ≤ c

log d
+
p

1

with probability at least 1 − d− 8 c+1 . Since p ≥

d log d
p

log d
d ,

s

|||HΩ (Z)|||op ≤ 2c

s

!

kZk∞

we know

d log d
kZk∞
p

1

with probability at least 1 − d− 8 c+1 . Taking c large enough, e.g., c = 16, yields the lemma.

Lemma 15 In the setting of SMC(M ∗ , p) or MC(M ∗ , p), if p ≥ logd d , then there is a
numerical constant c > 1 such that w.h.p.
s
d log d
kuk∞ kvk∞ , ∀u, v ∈ Rd ,
|||HΩ (u ⊗ v)|||op ≤ 2c
p
69

Leave-one-out Approach for Matrix Completion

and

s

|||HΩ (U ⊗ V )|||op ≤ 2rc
Moreover, if p ≥

log d
d ,

|||HΩ (A)|||op ≤ 2c

(i)
|||HΩ (A)|||op

∀U, V ∈ Rd×r .

then w.h.p.
s

and

d log d
kU k2,∞ kV k2,∞ ,
p

s

≤ 2c

rd log d
kAk∞ ,
p

rd log d
kAk∞ ,
p

∀A ∈ Rd×d : rank(A) = r,

∀A ∈ Rd×d : rank(A) = r, ∀i ∈ [d].

Proof We shall prove the third inequality in the statement of the lemma, which is restated
below:
s
rd log d
kAk∞ , ∀A ∈ Rd×d : rank(A) = r.
|||HΩ (A)|||op ≤ 2
p
The other three inequalities in the lemma are simple consequence of the above inequality.
In particular, the first inequality can be obtained by setting r = 1 and note ku ⊗ vk∞ ≤
√
kuk∞ kvk∞ . The second one is due to r ≤ r and kU ⊗ V k∞ ≤ kU k2,∞ kV k2,∞ . The
(i)
(i)
last inequality is due to |||HΩ (A)|||op ≤ |||HΩ (A)|||op by recalling that HΩ sets i-th row and
i-column of HΩ (A) to be 0.
Since rank(A) = r, we can decompose it to A = U ⊗ V where U, V ∈ Rd×r . We denote
(1)
(r)
(1)
(r)
ui = (ui , . . . , ui ) and vj = (vj , . . . , vj ) to be the i-th row and j-th row of U and V
respectively. We make use of the expression
|||HΩ (U ⊗ V )|||op =

sup

hHΩ (U ⊗ V ), a ⊗ bi.

kak2 =kbk2 =1

Recall HΩ = I − p1 ΠΩ , 1 is the all one vector and observe that
1
hHΩ (U ⊗ V ), a ⊗ bi = hU ⊗ V, a ⊗ bi − hΠΩ (U ⊗ V ), a ⊗ bi
p
X
1 X
hui , vj iai bj
=
hui , vj iai bj −
p
ij

i,j∈Ω

1
= h1 ⊗ 1, (U ⊗ V ) ◦ (a ⊗ b)i − hΠΩ (1 ⊗ 1), (U ⊗ V ) ◦ (a ⊗ b)i
p
= hHΩ (1 ⊗ 1), (U ⊗ V ) ◦ (a ⊗ b)i,

where ◦ denotes the Hadamard product. It follows that
|||HΩ (U ⊗ V )|||op =

sup

hHΩ (U ⊗ V ), a ⊗ bi

kak2 =kbk2 =1

≤ |||HΩ (1 ⊗ 1)|||op

sup
kak2 =kbk2 =1

70

|||(U ⊗ V ) ◦ (a ⊗ b)|||nuc .

Leave-one-out Approach for Matrix Completion

Lemma 14 applied to the fixed matrix Z = 1 ⊗ 1 guarantees that w.h.p.
s
d log d
|||HΩ (1 ⊗ 1)|||op ≤ 2c
.
p
Since the matrix (U ⊗V )◦(a⊗b) has rank at most r as [(U ⊗V )◦(a⊗b)]ij = hai ui , bj vj i,
we have
√
|||(U ⊗ V ) ◦ (a ⊗ b)|||nuc ≤ r|||(U ⊗ V ) ◦ (a ⊗ b)|||F
s
√ X
= r
(ai bj )2 (hui , vj i)2
ij

s
√ X
≤ r
(ai bj )2 max |hui , vj i|
=

√

ij

ij

r · 1 · kU ⊗ V k∞ .

Combining this and the bound of |||HΩ (1 ⊗ 1)|||op , we establish the third inequality in the
lemma statement.
Lemma 16 (Vu et al., 2013, Proposition 2.2) If the matrices V1 , V2 ∈ Rd×r have orthonormal columns, then
1
inf
|||V1 − V2 Q|||2F ≤ ||| sin(V1 , V2 )|||2F ≤
inf
|||V1 − V2 Q|||2F ,
2 Q∈Rr×r ,QQT =I
Q∈Rr×r ,QQT =I
where (V1 , V2 ) is the principal angle between V1 , V2 .
Lemma 17 (Davis-Kahan sinΘ Theorem) (Davis and Kahan, 1970; Li, 1998) Suppose
that A, W ∈ Rd×d are symmetric matrices, and Ã = A + W . Let δ = λr (A) − λr+1 (A) be
the gap between the top r-th eigenvalue and the (r + 1)-th eigenvalue of A, and U, Ũ be the
r leading orthonormal eigenvectors of A and Ã respectively. If δ > |||W |||op , then for any
unitary invariant norm ||| · |||
||| sin(U, Ũ )||| ≤

|||W U |||
.
δ − |||W |||op

Furthermore, using Lemma 16, there is a matrix O ∈ Rr×r satisfying OO T = I such that
√
2|||W U |||F
.
|||U − Ũ O|||F ≤
δ − |||W |||op
Lemma 18 (Chen and Wainwright, 2015, Lemma 4) In the setting of SMC(M ∗ , p), if p &
µr log d
, then with probability at least 1 − 2d−3 , the following holds: for all H, G ∈ Rd×r ,
ǫ2 d
|p−1 hΠΩ (F ∗ ⊗ H), ΠΩ (G ⊗ F ∗ )i − hF ∗ ⊗ H, G ⊗ F ∗ i| ≤ ǫ|||F ∗ |||2op |||H|||F |||G|||F ,

|p−1 hΠΩ (F ∗ ⊗ G), ΠΩ (F ∗ ⊗ H)i − hF ∗ ⊗ H, F ∗ ⊗ Gi| ≤ ǫ|||F ∗ |||2op |||H|||F |||G|||F .

71

Leave-one-out Approach for Matrix Completion

Lemma 19 (Chen and Wainwright, 2015, Lemma 5) In the setting of SMC(M ∗ , p), for
2 2
each ǫ ∈ (0, 1), if p & ǫ12 ( µ dr + logd d ), then the following event occurs with probability at
q
least 1 − 2d−4 : for all H ∈ Rd×r with kHk2,∞ ≤ 6 µr
d ,
p−1 |||ΠΩ (H ⊗ H)|||2F ≤ (1 + ǫ)|||H|||4F + ǫ|||H|||2F .

72

