Constructing confidence sets for the matrix completion
problem

arXiv:1704.02760v1 [math.ST] 10 Apr 2017

April 11, 2017
Alexandra Carpentier, Universität Potsdam1
Olga Klopp, University Paris Nanterre2
Matthias Löffler, University of Cambridge3
Abstract
In the present note we consider the problem of constructing honest and adaptive confidence sets for the matrix completion problem. For the Bernoulli model with known variance
of the noise we provide a realizable method for constructing confidence sets that adapt to
the unknown rank of the true matrix.

Keywords: low rank recovery, confidence sets, adaptivity, matrix completion.

1

Introduction

In recent years, there has been a considerable interest in statistical inference for high-dimensional
matrices. One particular problem is matrix completion where one observes only a small number
n ≪ m1 m2 of the entries of a high-dimensional m1 × m2 matrix M0 of unknown rank r; it aims
at inferring the missing entries. The problem of matrix completion comes up in many areas
including collaborative filtering, multi-class learning in data analysis, system identification in
control, global positioning from partial distance information and computer vision, to mention
some of them. For instance, in computer vision, this problem arises as many pixels may be
missing in digital images. In collaborative filtering, one wants to make automatic predictions
about the preferences of a user by collecting information from many users. So, we have a data
matrix where rows are users and columns are items. For each user, we have a partial list of his
preferences. We would like to predict the missing ones in order to be able to recommend items
that he may be interested in.
In general, recovery of a matrix from a small number of observed entries is impossible, but,
if the unknown matrix has low rank, then accurate and even exact recovery is possible. In the
noiseless setting, [6, 4, 3] established the following remarkable result: assuming that it satisfies a
low coherence condition, M0 can be recovered exactly by constrained nuclear norm minimization
with high probability from only n & r(m1 ∨ m2 ) log2 (m1 ∨ m2 ) entries observed uniformly at
random.
1 Institut

für Mathematik, carpentier@maths.uni-potsdam.de
kloppolga@math.cnrs.fr
3 Statistical Laboratory, Centre for Mathematical Sciences, m.loffler@statslab.cam.ac.uk
2 MODAL’X,

1

What makes low-rank matrices special is that they depend on a number of free parameters
that is much smaller than the total number of entries. Taking the singular value decomposition
of a matrix A ∈ Rm1 ×m2 of rank r, it is easy to see that A depends upon (m1 + m2 )r − r2
free parameters. This number of free parameters gives us a lower bound for the number of
observations needed to complete the matrix.
A situation, common in applications, corresponds to the noisy setting in which the few available entries are corrupted by noise. Noisy matrix completion has been extensively studied recently
(e.g., [12, 15, 2, 8]). Here we observe a relatively small number of entries of a data matrix
Y = M0 + E
where M0 = (Mij ) ∈ Rm1 ×m2 is the unknown matrix of interest and E = (εij ) ∈ Rm1 ×m2 is
a matrix of random errors. It is an important issue in applications to be able to say from the
observations how well the recovery procedure has worked or, in the sequential sampling setting, to
be able to give data-driven stopping rules that guarantee the recovery of the matrix M0 at a given
precision. This fundamental statistical question was recently studied in [7] where two statistical
models for matrix completion are considered: the trace regression model and the Bernoulli model
(for details see Section 1.1). In particular, in [7], the authors show that in the case of unknown
noise variance, the information-theoretic structure of these two models is fundamentally different.
In the trace regression model, even if only an upper bound for the variance of the noise is known,
a honest and rank adaptive Frobenius-confidence set whose diameter scales with the minimax
optimal estimation rate exists. In the Bernoulli model however, such sets do not exist.
Another major difference is that, in the case of known variance of the noise, [7] provides a
realizable method for constructing confidence sets for the trace regression model whereas for the
Bernoulli model only the existence of adaptive and honest confidence sets is demonstrated. The
proof uses the duality between the problem of testing the rank of a matrix and the existence of
honest and adaptive confidence sets. In particular, the construction in [7] is based on infimum test
statistics which can not be computed in polynomial time for the matrix completion problem. The
present note aims to close this gap and provides a realizable method for constructing confidence
sets for the Bernoulli model.

1.1

Notation, assumptions and some basic results

We assume that each entry of Y is observed independently of the other entries with probability
p = n/(m1 m2 ). More precisely, if n ≤ m1 m2 is given and Bij are i.i.d. Bernoulli random variables
of parameter p independent of the εij ’s, we observe
Yij = Bij (Mij + εij ) , 1 ≤ i ≤ m1 , 1 ≤ j ≤ m2 .

(1)

This model for the matrix completion problem is usually called the Bernoulli model. Another
model often considered in the matrix completion literature is the trace regression model (e.g.,
[12, 15, 2, 10]). Let k0 = rank(M0 ).
In many of the most cited applications of the matrix completion problem, such as recommendation systems or the problem of global positioning from the local distances, the noise is
bounded but not necessarily identically distributed. This is the assumption which we adopt
in the present paper. More precisely, we assume that the noise variables are independent, homoscedastic, bounded and centered:
Assumption 1. For any (ij) ∈ [m1 ] × [m2 ] we assume that E(εij ) = 0, E(ε2ij ) = σ 2 and that
there exists a positive constant U > 0 such that
max |εij | ≤ U.
ij

2

Let m = min(m1 , m2 ), d = m1 + m2 . For any l ∈ N we set [l] = {1, . . . , l}. For any integer
0 ≤ k ≤ m and any a > 0, we define the parameter space of rank k matrices with entries bounded
by a in absolute value as

A(k, a) = M ∈ Rm1 ×m2 : rank(M ) ≤ k, kM k∞ ≤ a .

For constants β ∈ (0, 1) and c = c(σ, a) > 0 we have that
inf

sup

c M0 ∈A(k,a)
M

PM0 ,σ

c − M0 k22
kd
kM
>c
m1 m2
n

!

(2)

≥β

c is an estimator of M0 (see, e.g., [11]). It has been also shown in [11] that an iterative
where M
c satisfies with PM0 ,σ -probability at least 1 − 8/d
soft thresholding estimator M
c − M0 k2
kM
(a + σ)2 kd
F
≤C
m1 m2
n

ck∞ ≤ 2a
and kM0 − M

(3)

for a constant C > 0. These lower and upper bounds imply r
that for the Frobenius loss the
(σ + a)2 k0 dm1 m2
minimax risk for recovering a matrix M0 ∈ A(k0 , a) is of order
.
n
For k ∈ [m] we set
(σ + a)2 dk
rk = C
,
n
where C is the numerical constant in (3).
T
Let A, B be matrices in Rm1 ×m2 . We define the matrix scalar
Pproduct as hA, Bi = tr(A B).
The trace norm of a matrix A = (aij ) is defined as P
kAk∗ := P σj (A), the operator norm as
kAk := σ1 (A) and the Frobenius norm as kAk22 := i σi2 = i,j a2ij where (σj (A))j are the
singular values of A ordered decreasingly. kAk∞ = max|aij | denotes the largest absolute value
i,j

of any entry of A.
In what follows, we use symbols C, c for a generic positive constant, which is independent of
n, m1 , m2 , and may take different values at different places. We denote by a ∨ b = max(a, b).
We use the following definition of honest and adaptive confidence sets:
Definition 1. Let α, α′ > 0 be given. A set Cn = Cn ((Yij , Bij ), α) ⊂ A(m, a) is a honest
confidence set at level α for the model A(m, a) if
lim inf
n

inf

M∈A(m,a)

PnM (M ∈ Cn ) ≥ 1 − α.

Furthermore, we say that Cn is adaptive for the sub-model A(k, a) at level α′ if there exists a
constant C = C(α, α′ ) > 0 such that
sup
M∈A(k,a)

PnM (kCn k2 > Crk ) ≤ α′

while still retaining
sup
M∈A(m,a)

PnM (kCn k2 > Crm ) ≤ α′ .

3

2

A non-asymptotic confidence set for matrix completion
problem

c be an estimator of M0 based on the observations (Yij , Bij ) from the Bernoulli model (1)
Let M
ck∞ ≤ a. Assume that for some β > 0 M
c satisfies the following risk bound:
such that kM
!
2
c − M0 k2
(σ
+
a)
k
d
kM
0
2
≥ 1 − β.
(4)
≤C
sup
P
m1 m2
n
M0 ∈A(k0 ,a)
We can take, for example, the thresholding, estimator considered in [11] which attains (4) with
ck the projection of M
c
β = 8/d. Our construction is based on Lepski’s method. We denote by M
on the set A(k, a) of matrices of rank k with sup-norm bounded by a:
ck ∈ arg min kM
c − Ak2 .
M
A∈A(k,a)

Set

c− M
ck k2 ≤ rk }
S = {k : kM
2

and

k ∗ = min{k ∈ S}.

f=M
ck∗ to center our confidence set and the residual sum of squares statistic r̂n :
We will use M
r̂n =

Given α > 0, let
z̄ =

1X
fij )2 − σ 2 .
(Yij − Bij M
n ij

p
fk22 + z(U C ∗ )2 dk ∗
kM − M
256

and ξα,U = 2U 2

(5)

p
4U 2 log(α−1 )
√
log(α−1 ) +
.
3 n

Here z is a sufficiently large numerical constant to be chosen later on and C ∗ ≥ 2 is an universal
constant in Corollary 3.12 [1]. We define the confidence set as follows:
(
)

2
∗
fk22
a
zdk
+
z̄
ξ
kM
−
M
α,U
.
(6)
≤ 128 r̂n +
+ √
Cn = M ∈ Rm1 ×m2 :
m1 m2
n
n
c attains the risk bound (4) with probability
Theorem 1. Let α > 0, d > 16 and suppose that M
at least 1 − β. Let Cn be given by (6). Assume that kM0 k∞ ≤ a and that Assumption 1 is
satisfied. Then, for every n ≥ m log(d), we have
PM0 (M0 ∈ Cn ) ≥ 1 − α − exp(−cd).

(7)

Moreover, with probability at least 1 − β − exp(−cd)
kCn k22
(σ + a)2 dk0
≤C
.
m1 m2
n

(8)

Theorem 1 implies that Cn is an honest and adaptive confidence set:
c attains the risk bound (4) with probability
Corollary 1. Let α > 0, d > 16 and suppose that M
at least 1 − β. Let Cn be given by (6). Assume that Assumption 1 is satisfied. Then, for
n ≥ m log(d), Cn is a α + exp(−cd) honest confidence set for the model A(m, a) and adapts to
every sub-model A(k, a), 1 ≤ k ≤ m, at level β + exp(−cd).
4

Proof of Theorem 1. We consider the following sets


256(a ∨ U )2 zd
2
m1 ×m2
and rank(A) ≤ k
: kAk∞ ≤ a, kM0 − Ak2 ≥
C(k, a) = A ∈ R
p
and write
C = ∪m
k=1 C(k, a).

(9)

256(a ∨ U )2 zd
we have that M0 ∈ Cn . So, we only need to consider
p
2
2
2
f ∈ C. We introduce the
f ≥ 256(a ∨ U ) zd . In this case we have that M
the case M0 − M
p
2
observation operator X defined as follows,
When

f
M0 − M

2

≤

X : Rm1 ×m2 → Rm1 ×m2

with

X (A) = (Bij aij )ij .

and set kAk2L2 (Π) = EkX (A)k22 = pkAk22 . We can decompose
f − M0 )k22 + 2n−1 hX (E), M0 − M
fi + n−1 kX (E)k22 − σ 2 .
r̂n = n−1 kX (M

/ Cn ) by the sum of the following probabilities:
Then we can bound the probability PM0 (M0 ∈
!
f − M0 k2
kM
L2 (Π)
2
2
∗
f − M0 )k + za dk ,
I := PM0
> kX (M
2
128


fi > z̄ ,
II := PM0 −2hX (E), M0 − M

√
III := PM0 −kX (E)k22 + nσ 2 > nξα,U .

By Lemma 1, the first probability is bounded by 8 exp (−4d) for z ≥ (27C ∗ )2 . For the second
term we use Lemma 7 which implies that II ≤ exp(−cd) for z ≥ 6240. Finally, for the third
term, Bernstein’s inequality implies



t2
2
2
P −kX (E)k2 + nσ > t ≤ exp − 2 2 2 2 .
2σ nU + 3 U t
p
Taking t = 2U 2 n log(α−1 ) + 43 U 2 log(α−1 ) we get that III ≤ α by definition of ξα,U . This
completes the proof of (7).
To prove (8), using Lemma 1 and Lemma 7, we can bound the square Frobenius norm
diameter of our confidence set Cn defined in (6) as follows:

f − M0 k22 
kCn k22
ξα,U
kM
.
.
+ rk∗ + √
m1 m2
m1 m2
n

This bound holds on an event of probability at least 1 − exp(−cd). Now we restrict to the event
c attains the risk bound in (4) which happens with probability at least 1 − β. On this
where M
c−M
ck0 k2 ≤ rk0 . So, k0 ∈ S and k ∗ ≤ k0 . Now, the triangle
event, M0 ∈ A(k0 , a) implies kM
2
∗
inequality and rk ≤ rk0 imply that on the intersection of those two events we have that
f − M0 k22 . m1 m2 (rk0 + rk∗ ) . m1 m2 rk0 .
kM

This, together with the definition of ξα,U and the condition n ≤ m1 m2 , completes the proof of
(8).
5

A

Technical Lemmas

Lemma 1. With probability larger then 1 − 8 exp (−4d) we have that
kX (M0 − A)k2 − kM0 − AkL2 (Π) − 87 kM0 − AkL2 (Π)
p
≤ 27 C ∗
a rank(A)d

sup
A∈C

where C ∗ is an universal numerical constant and C is defined in (9).
Proof. We have that

kX (M0 − A)k2 − kM0 − AkL2 (Π) − 78 kM0 − AkL2 (Π)
p
≥ 27 C ∗
P sup
a rank(A)d
A∈C
≤

k0
X

k=1

sup

P

A∈C(k,a)

|

kX (M0 − A)k2 − kM0 − AkL2 (Π)
{z
I

!

!
√
7
− kM0 − AkL2 (Π) ≥ 27 C ∗ a kd . (10)
8
}

In order to upper bound I, we use a standard peeling argument. Let α = 7/6 and ν 2 =
For l ∈ N set


Sl = A ∈ C(k, a) : αl ν ≤ kA − M0 k2 ≤ αl+1 ν .

Then
I≤
≤

470a2 zd
.
p



∞
X
√
√
7
P sup kX (M0 − A)k2 − kM0 − AkL2 (Π) ≥ 27 C ∗ a kd + αl a 470zd
8
A∈Sl
l=1

∞
X
l=1

sup

P
|

A∈C(k,a,αl+1 ν)

kX (M0 − A)k2 − kM0 − AkL2 (Π)
{z
II

!
√
√
7
≥ 27 C ∗ a kd + αl a 470zd
8
}

where C(k, a, T ) = {A ∈ C(k, a) : kM0 − Ak2 ≤ T }. The following Lemma gives an upper bound
on II:
Lemma 2. Consider the following set of matrices
C(k, a, T ) = {A ∈ C(k, a) : kM0 − Ak2 ≤ T }
and set
ZT =

sup
A∈C(k,a,T )

Then, we have that

kX (M0 − A)k2 − kM0 − AkL2 (Π) .



√
2
2
3√
P ZT ≥
pT + 27 C ∗ a kd ≤ 4e−c1 p T /a
4

with c1 ≥ (512)−1 .

Lemma 2 implies that II ≤ 8 exp(−c1 p α2l ν 2 /a2 ) and we obtain
I≤8

∞
X
l=1

exp(−c1 p α2l+2 ν 2 /a2 ) ≤ 8
6

∞
X
l=1

exp −2c1 p ν 2 log(α) l/a2



where we used ex ≥ x. We finally compute for ν 2 = 188a2 zdp−1

8 exp −2c1 p ν 2 log(α)/a2
≤ 16 exp (−376 c1 zd log(7/6)) ≤ exp(−5d)
I≤
1 − exp (−2c1 p ν 2 log(α)/a2 )
where we take z ≥ (27C ∗ )2 . Using (10) and d ≥ log(m) we get the statement of Lemma 1.

Proof of Lemma 2. This proof is close to the proof of Theorem 1 in [15]. We start by applying
N (δ)
the discretization argument. Let {G1δ , . . . Gδ } be a δ−covering of C(k, a, T ) given by Lemma
3. Then, for any A ∈ C(k, a, T ) there exists some index i ∈ {1, . . . , N (δ)} and a matrix ∆ with
k∆k2 ≤ δ such that A = Giδ + ∆. Using the triangle inequality we have
X (M0 − Giδ )

kM0 − AkL2 (Π) − kX (M0 − A)k2 ≤

2

− kM0 − Giδ kL2 (Π) + kX ∆k2 +

Lemma 3 implies that ∆ ∈ Dδ (2k, 2a, 2T ) where
Dδ (k, a, T ) = {A ∈ Rm1 ×m2 : kAk∞ ≤ a, kAk2 ≤ δ

and kAk∗ ≤

√
pδ.

√
kT }.

Then,
ZT ≤

max

i=1,...,N (δ)

X (M0 − Giδ )

2

− kM0 − Giδ kL2 (Π) +

sup
∆∈Dδ (2k,2a,2T )

kX ∆k2 +

√
pδ.

Now we take δ = T /8 and use Lemma 6 and Lemma 5 to get
√
√
√
√
√
√
√
ZT ≤ pδ + 8 C ∗ a kd + 19a C ∗ 2kd + pT /2 + pδ ≤ 27 C ∗ a kd + 6 pT /8.


pT 2
.
with probability at least 1 − 8 exp − 512a
2
N (δ)

Lemma 3. Let δ = T /8. There exists a set of matrices {G1δ , . . . Gδ
and such that
N (δ)

1
(i) For any A ∈ C(k, a, T ) there exists a GA
δ ∈ {Gδ , . . . Gδ

kA − GA
δ k2 ≤ δ

} with Nδ ≤


18T 2(d+1)k
δ

} satisfying

(A − GA
δ ) ∈ Dδ (2k, 2a, 2T ).

and

(ii) Moreover, kGjδ − M0 k∞ ≤ 2a and kGjδ − M0 k2 ≤ 2T for any j = 1, . . . , Nδ .
Proof. We use the following result (see Lemma 3.1 in [5] and Lemma A.2 in [17]):
Lemma 4. Let S(k, T ) = {A ∈ Rm1 ×m2 : rank(A) ≤ k
an ǫ−net S̄(k, T ) for the Frobenius norm obeying

and

kAk2 ≤ T }. Then, there exists

S̄(k, T ) ≤ (9T /ǫ)(m1 +m2 +1)k .
Let SM0 (k, T ) = {A ∈ Rm1 ×m2 : rank(A) ≤ k and kA − M0 k2 ≤ T } and take a X0 ∈
C(k, a, T ). We have that SM0 (k, T )−X0 ⊂ S(2k, 2T ). Let S̄(2k, 2T ) be an δ−net given by Lemma
A
4. Then, for any A ∈ SM0 (k, T ) there exists a ḠA
δ ∈ S̄(2k, 2T ) such that kA−X0 − Ḡδ k2 ≤ δ. Let
j
j
Gδ = Π(Ḡδ ) + X0 for j = 1, . . . , S̄(2k, 2T ) where Π is the projection operator under Frobenius
√
norm into the set D(2k, 2a, 2T ) = {A ∈ Rm1 ×m2 : kAk∞ ≤ 2a, and kAk∗ ≤ 2 2kT }. Note
7

that as D(2k, 2a, 2T ) is convex and closed, Π is non-expansive in Frobenius norm. For any
A ∈ C(k, a, T ) ⊂ SM0 (k, T ), we have that A − X0 ∈ D(2k, 2a, 2T ) which implies
A
A
kA − X0 − Π(ḠA
δ )k2 = kΠ(A − X0 − Ḡδ )k2 ≤ kA − Ḡδ − X0 )k2 ≤ δ

and we have that (A−Π(ḠA
δ )−X0 ) ∈ Dδ (2k, 2a, 2T ) which completes the proof of (i) of Lemma 3.
To prove (ii), note that by the definition of Π we have that kGjδ −M0 k∞ = kΠ(Ḡjδ )+X0 −M0 k∞ =
kΠ(Ḡjδ + X0 − M0 )k∞ ≤ 2a and kGjδ − M0 k2 ≤ 2T .
Lemma 
5. Let δ =T /8 and assume that n ≥ m log(m). We have that with probability at least
pT 2
1 − 4 exp −
512a2
√
√
sup
kX ∆k2 ≤ 19a C ∗ 2kd + pT /2.
∆∈Dδ (2k,2a,2T )

Proof. Let XT =

sup
∆∈Dδ (2k,2a,2T )

kX ∆k2 . We use the following Talagrand’s concentration inequal-

ity :
Theorem 2. Suppose that f : [−1, 1]N → R is a convex Lipschitz function with Lipschitz
constant L. Let Ξ1 , . . . ΞN be independent random variables taking value in [−1, 1]. Let Z : =
f (Ξ1 , . . . , Ξn ). Then for any t ≥ 0,
2

P (|Z − E(Z)| ≥ 16L + t) ≤ 4e−t
For a proof see [16] and [8]. Let f (x11 , . . . , xm1 m2 ) : =

/2L2

.

sup
∆∈Dδ (2k,2a,2T )

qP

(i,j)

x2ij ∆2ij . It is easy

to see that f (x11 , . . . , xm1 m2 ) is a Lipschitz function with Lipschitz constant L = 2a. Indeed,
|f (x11 , . . . , xm1 m2 ) − f (z11 , . . . , zm1 m2 )|
sX
x2ij ∆2ij −
=
sup
∆∈Dδ (2k,2a,2T )

≤

(i,j)

sup
∆∈Dδ (2k,2a,2T )

sX

(i,j)

sup
∆∈Dδ (2k,2a,2T )

sX

2 ∆2
zij
ij

(i,j)

(xij − zij )2 ∆2ij ≤ 2akx − zk2

where x = (x11 , . . . , xm1 m2 ) and z = (z11 , . . . , zm1 m2 ). Now, Theorem 2 implies


t2
P (XT ≥ E(XT ) + 32a + t) ≤ 4 exp − 2 .
8a

(11)

Next, we bound the expectation E(XT ). Applying Jensen’s inequality, a symmetrization argument and the Ledoux-Talagrand contraction inequality (see, e.g., [13]) we get




X
X

2
(E(XT )) ≤ E 
Bij ∆2ij  ≤ E 
sup
Bij ∆2ij − E Bij ∆2ij  + pδ 2
sup
∆∈Dδ (2k,2a,2T )



≤ 2E

sup

∆∈Dδ (2k,2a,2T )

= 8a E

(i,j)

X

(i,j)

sup
∆∈Dδ (2k,2a,2T )

∆∈Dδ (2k,2a,2T )





ǫij Bij ∆2ij  + pδ 2 ≤ 8a E 
|hΣR , ∆i|

!

(i,j)

sup
∆∈Dδ (2k,2a,2T )

X

(i,j)

√
+ pδ 2 ≤ 16 a 2k T E (kΣR k) + pδ 2
8



ǫij Bij ∆ij  + pδ 2

P
where {ǫij } is i.i.d. Rademacher sequence, ΣR = (i,j) Bij ǫij Xij with Xij = ei (m1 )eTj (m2 ) and
ek (l) are the canonical basis vectors in Rl . Lemma 4 in [11] and n ≥ m log(m) imply that
p
E kΣR k ≤ C ∗ pd
(12)
√
√
√
where C ∗ ≥ 2 is an universal numerical constant. Using (12), x + y ≤ x + y, 2xy ≤ x2 + y 2
and δ = T /8 we compute

1/2 √
p
√
√
E(XT ) ≤ 4 a C ∗ 2kpd T
+ pδ ≤ 16a C ∗ 2kd + 3 pT /8.

Taking in (11) t =

√
pT /8 we get the statement of Lemma 5.
N (δ)

Lemma 6. Let δ = T /8, d > 16 and (G1δ , . . . , Gδ
Lemma 3. We have that
max

k=1,...,N (δ)

X (M0 − Gkδ )

2

) be the collection of matrices given by

− kM0 − Gkδ kL2 (Π) ≤

√

√
pδ + 8 C ∗ a kd



pδ 2
with probability at least 1 − 4 exp − 8a
.
2

Proof. For any fixed A ∈ Rm1 ×m2 satisfying kAk∞ ≤ 2a we have that
sX
X
kX Ak2 =
(uij Bij Aij ) .
Bij A2ij = sup
kuk2 =1 ij

ij

Then we can apply Theorem 2 with f (x11 , . . . , xm1 m2 ) : = sup
kuk2 =1

P

ij

(uij xij ) to get



t2
P (|kX Ak2 − EkX Ak2 | > t + 32a) ≤ 4 exp − 2 .
(13)
8a
P
On the other hand let Z = sup
ij (uij Bij Aij ). Applying Corollary 4.8 from [14] we get that

Var Z =

kAk2L2 (Π)

−

kuk2 =1
2
(EkX Ak2 ) ≤

162 a2 which together with (13) implies




t2
(14)
P kX Ak2 − kAkL2 (Π) > t + 48a ≤ 4 exp − 2 .
8a
√
√
Now Lemma 6 follows from Lemma 3, (14) with t = pδ + 5C ∗ a kd and the union bound.
Lemma 7. We have that
sup
A∈C

|hX (E), A − M0 i| −

1
256 kM0

d rank(A)

− Ak2L2 (Π)

with probability larger then 1 − exp(−cd) with c ≥ 0, 003

9

≤ 6240(U C ∗ )2 .

Proof. Following the lines of the proof of Lemma 1 with α =
we get
P

sup

|hX (E), A − M0 i| −

1
256 kM0

d rank(A)

A∈C

− Ak2L2 (Π)

p
252(a ∨ U )2 zd
65/64 and ν 2 =
p
∗ 2

≥ 6240(U C )

∞
k0 X
X

!

pα2l ν 2
P
sup
|hX (E), A − M0 i| ≥ 6240(U C ) dk +
≤
256
A∈C(k,a,αl+1 ν)
k=1 l=1


k0 X
∞
X
c2 pα2l+2 ν 2
≤4
≤ exp (−cd)
exp −
(a ∨ U )2
∗ 2

!

k=1 l=1

where we use the following lemma:

Lemma 8. Consider the following set of matrices
C(k, a, T ) = {A ∈ C(k, a) : kM0 − Ak2 ≤ T }
and set

We have that

eT =
Z

sup
A∈C(k,a,T )

|hX (E), A − M0 i| .




eT ≥ 6240(C ∗ U )2 dk + pT 2 /260 ≤ 4 exp −pT 2 /c2 (a ∨ U )2
P Z

with c2 ≤ 12(1560)2

Proof of Lemma 8. Fix a X0 ∈ C(k, a, T ). For any A ∈ C(k, a, T ), we set ∆ = A − X0 and we
have that rank(∆) ≤ 2k and k∆k2 ≤ 2T . Then using |hX (E), A − M0 i| ≤ |hX (E), X0 − M0 i| +
|hX (E), ∆i| we get

where

eT ≤ |hX (E), X0 − M0 i| +
Z

sup
∆∈T (2k,2a,2T )

|hX (E), ∆i|

T (2k, 2a, 2T ) = {A ∈ Rm1 ×m2 : kAk∞ ≤ 2a, kAk2 ≤ 2T

and rank(A) ≤ 2k}.

Bernstein’s inequality and kX0 − M0 k2 ≤ T imply that


t2
P {|hX (E), X0 − M0 i| > t} ≤ 2 exp − 2 2 4
.
2σ pT + 3 U at
Taking t = pT 2 /520 we get


P |hX (E), X0 − M0 i| > pT 2 /520 ≤ 2 exp −

pT 2
c2 (a ∨ U )2



.


On the other hand, Lemma 9 implies that with probability at least 1 − 2 exp −
sup
∆∈T (2k,2a,2T )

|hX (E), ∆i| ≤ 6240(C ∗ U )2 kd + pT 2 /520

which together with (15) implies the statement of Lemma 8.
10

(15)
pT 2
c3 (a ∨ U )2




Lemma 9. Assume that n ≥ m log(m). We have that with probability at least 1−2 exp −
sup
∆∈T (2k,2a,2T )

pT 2
(a ∨ U )2

|hX (E), ∆i| ≤ 6240(C ∗ U )2 kd + pT 2 /520

where c3 is a numerical constant.
eT =
Proof. Let X
eT ):
pectation E(X

sup
∆∈T (2k,2a,2T )



eT ) ≤ E 
E(X

|hX (E), ∆i| =

sup
∆∈T (2k,2a,2T )

√
≤ 2 2k T E (kΣk)

X

(i,j)

sup
∆∈T (2k,2a,2T )

hX (E), ∆i. First we bound the ex-



εij Bij ∆ij  = E

sup
∆∈T (2k,2a,2T )

|hΣ, ∆i|

!

P
where Σ = (i,j) Bij εij Xij with Xij = ei (m1 )eTj (m2 ) and ek (l) are the canonical basis vectors
in Rl . Using n ≥ m log(m) Lemma 4 in [11] and Corollary 3.3 in [1] imply that
p
E kΣk ≤ C ∗ U pd.
(16)
where C ∗ ≥ 2 is an universal numerical constant. Using (16) we get
p
eT ) ≤ 2C ∗ U 2kpd T ≤ 3120(C ∗ U )2 kd + pT 2 /1560.
E(X

(17)

Now we use Theorem 3.3.16 in [9] (see also Theorem 8.1 in [7]) to obtain


eT ≥ E(X
eT ) + t ≤ exp −
P X

≤ exp −

t2
eT ) + 4σ 2 pT 2 + 9U at
4U aE(X

!

t2
√
8aU 2 C ∗ 2kpdT + 4σ 2 pT 2 + 9U at



(18)

√
Taking in (18) t = pT 2 /1560 + 2U C ∗ 2kpdT , together with (17) we get the statement of Lemma
9.

Acknowledgements
The work of A. Carpentier is supported by the DFGs Emmy Noether grant MuSyAD (CA 1488/11). The work of O. Klopp was conducted as part of the project Labex MME-DII (ANR11-LBX0023-01). The work of M. Löffler was supported by the UK Engineering and Physical Sciences
Research Council (EPSRC) grant EP/L016516/1 for the University of Cambridge Centre for
Doctoral Training, the Cambridge Centre for Analysis, and the European Research Council
(ERC) grant No. 647812.

References
[1] Afonso S. Bandeira and Ramon van Handel. Sharp nonasymptotic bounds on the norm of
random matrices with independent entries. Ann. Probab., 44(4):2479–2506, 2016.
11



[2] T. Tony Cai and Wen-Xin Zhou. Matrix completion via max-norm constrained optimization.
Electron. J. Stat., 10(1):1493–1525, 2016.
[3] E. J. Candès and Y Plan. Matrix completion with noise. Proceedings of IEEE, 98(6):925–936,
2009.
[4] E.J. Candès and B. Recht. Exact matrix completion via convex optimization. Fondations
of Computational Mathematics, 9(6):717–772, 2009.
[5] Emmanuel J. Candès and Yaniv Plan. Tight oracle bounds for low-rank matrix recovery
from a minimal number of random measurements. CoRR, abs/1001.0339, 2010.
[6] Emmanuel J. Candès and Terence Tao. The power of convex relaxation: near-optimal matrix
completion. IEEE Trans. Inform. Theory, 56(5):2053–2080, 2010.
[7] A. Carpentier, O. Klopp, M. Löffler, and R. Nickl. Adaptive confidence sets for matrix
completion. to appear in Bernoulli, 2017.
[8] Sourav Chatterjee. Matrix estimation by universal singular value thresholding. Ann. Statist.,
43(1):177–214, 2015.
[9] E. Giné and R. Nickl. Mathematical Foundations of Infinite-Dimensional Statistical Models.
Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press,
2015.
[10] Olga Klopp. Noisy low-rank matrix completion with general sampling distribution.
Bernoulli, 20(1):282–303, 2014.
[11] Olga Klopp. Matrix completion by singular value thresholding: sharp bounds. Electron. J.
Stat., 9(2):2348–2369, 2015.
[12] V. Koltchinskii, K. Lounici, and A. B. Tsybakov. Nuclear-norm penalization and optimal
rates for noisy low-rank matrix completion. Ann. Statist., 39(5):2302–2329, 2011.
[13] Vladimir Koltchinskii. Oracle inequalities in empirical risk minimization and sparse recovery problems, volume 2033 of Lecture Notes in Mathematics. Springer, Heidelberg, 2011.
Lectures from the 38th Probability Summer School held in Saint-Flour, 2008, École d’Été
de Probabilités de Saint-Flour. [Saint-Flour Probability Summer School].
[14] M. Ledoux. The concentration of measure phenomenon, volume 89 of Mathematical Surveys
and Monographs. American Mathematical Society, Providence, RI, 2001.
[15] S. Negahban and M. J. Wainwright. Restricted strong convexity and weighted matrix completion: Optimal bounds with noise. Journal of Machine Learning Research, 13:1665–1697,
2012.
[16] Michel Talagrand. A new look at independence. Ann. Probab., 24(1):1–34, 1996.
[17] Yu-Xiang Wang and Huan Xu. Stability of matrix factorization for collaborative filtering.
In Proceedings of the 29th International Conference on Machine Learning, ICML 2012,
Edinburgh, Scotland, UK, June 26 - July 1, 2012, 2012.

12

