Restricted strong convexity and weighted matrix completion: Optimal bounds with noise

Introduction

Matrix completion problems correspond to reconstructing matrices, either exactly or approximately, based on observing a subset of their entries . In the simplest formulation of matrix completion, the observations are assumed to be uncorrupted, whereas a more general formulation (as considered in this paper) allows for noisiness in these observations. Matrix recovery based on only partial information is an ill-posed problem, and accurate estimates are possible only if the matrix satisfies additional structural constraints, with examples including bandedness, positive semidefiniteness, Euclidean distance measurements, Toeplitz, and low-rank structure (see the survey paper and references therein for more background).

The focus of this paper is low-rank matrix completion based on noisy observations. This problem is motivated by a variety of applications where an underlying matrix is likely to have low-rank, or near low-rank structure. The archetypal example is the Netflix challenge, a version of the collaborative filtering problem, in which the unknown matrix is indexed by individuals and movies, and each observed entry of the matrix corresponds to the rating assigned to the associated movie by the given individual. Since the typical person only watches a tiny number of movies (compared to the total Netflix database), it is only a sparse subset of matrix entries that are observed. In this context, one goal of collaborative filtering is to use the observed entries to make recommendations to a person regarding movies that they have not yet seen. We refer the reader to Srebro’s thesis (and references therein) for further discussion and motivation for collaborative filtering and related problems.

In this paper, we analyze a method for approximate low-rank matrix recovery using an $M$-estimator that is a combination of a data term, and a weighted nuclear norm as a regularizer. The nuclear norm is the sum of the singular values of a matrix , and has been studied in a body of past work, both on matrix completion and more general problems of low-rank matrix estimation (e.g., ). A parallel line of work has studied computationally efficient algorithms for solving problems with nuclear norm constraints (e.g, ). Here we limit our detailed discussion to those papers that study various aspects of the matrix completion problem. Motivated by various problems in collaborative filtering, Srebro and colleagues studied various aspects nuclear norm regularization; among various other contributions, Srebro et al. established generalization error bounds under certain conditions. Candes and Recht studied the exact reconstruction of a low-rank matrix given perfect (noiseless) observations of a subset of entries, and provided sufficient conditions for exact recovery via nuclear norm relaxation. These results were then refined in follow-up work , with the simplest approach to date being provided by Recht . In a parallel line of work, Keshavan et al. have studied a method based on thresholding and singular value decomposition, and established various results on its behavior, both for noiseless and noisy matrix completion. Among other results, Rohde and Tsybakov establish prediction error bounds for matrix completion, a different metric than the matrix recovery problem of interest here. In recent work, Salakhutdinov and Srebro provided various motivations for the use of weighted nuclear norms, in particular showing that the standard nuclear norm relaxation can behave very poorly when the sampling is non-uniform. The analysis of this paper applies to both uniform and non-uniform sampling, as well as a form of reweighted nuclear norm as suggested by these authors, one which includes the ordinary nuclear norm as a special case. We provide a more detailed comparison between our results and some aspects of past work in Section 3.4.

As has been noted before , a significant theoretical challenge is that conditions that have proven very useful for sparse linear regression—among them the restricted isometry property—are not satisfied for the matrix completion problem. For this reason, it is natural to seek an alternative and less restrictive property that might be satisfied in the matrix completion setting. In recent work, Negahban et al. have isolated a weaker condition known as restricted strong convexity (RSC), and proven that certain statistical models satisfy RSC with high probability when the associated regularizer satisfies a decomposability condition. When an $M$-estimator satisfies the RSC condition, it is relatively straightforward to derive non-asymptotic error bounds on parameter estimates . The class of decomposable regularizers includes the nuclear norm as particular case, and the RSC/decomposability approach has been exploited to derive bounds for various matrix estimation problems, among them multi-task learning, autoregressive system identification, and compressed sensing .

The remainder of this paper is organized as follows. We begin in Section 2 with background and a precise formulation of the problem. Section 3 is devoted to a statement of our main results, and discussion of some of their consequences. In Sections 4 and Section 5, we prove our main results, with more technical aspects of the arguments deferred to appendices. We conclude with a discussion in Section 6.

Background and problem formulation

In this section, we introduce background on low-rank matrix completion problem, and also provide a precise statement of the problem studied in this paper.

Here the quantities $\frac{\nu}{\sqrt{{d_{r}}{d_{c}}}}\widetilde{\xi}_{i}$ correspond to additive observation noises with variance appropriately scaled according to the matrix dimensions. In defining the observation model, one can either allow the Frobenius norm of $\Theta^{*}$ to grow with the dimension, as in done in other work , or rescale the noise as we have done here. This choice is consistent with our assumption that $\Theta^{*}$ has constant Frobenius norm regardless of its rank or dimensions. With this scaling, each observation in the model (1) has a constant signal-to-noise ratio regardless of matrix dimensions.

We assume that each row and column is sampled with positive probability, in particular that there is some constant $1\leq L<\infty$ such that $R_{a}\geq 1/L$ and $C_{b}\geq 1/L$ for all rows and columns. However, apart from the constraints $\sum_{a=1}^{d_{r}}R_{aa}={d_{r}}$ and $\sum_{b=1}^{d_{c}}C_{bb}={d_{c}}$, we do not require that the row and column weights remain bounded as ${d_{r}}$ and ${d_{c}}$ tend to infinity.

2 The observation operator and restricted strong convexity

We now describe an alternative formulation of the observation model (1) that, while statistically equivalent to the original, turns out to be more natural for analysis. For each $i=1,2,\ldots,n$, define the matrix

where $\varepsilon_{i}\in\{-1,+1\}$ is a random sign, and consider the observation model

where $\langle\!\langle{A},\;{B}\rangle\!\rangle:=\sum_{j,k}A_{jk}B_{jk}$ is the trace inner product, and $\xi_{i}$ is an additive noise from the same distribution as the original model. The model (3) is can be obtained from the original model (1) by rescaling all terms by the factor $\sqrt{{d_{r}}{d_{c}}}$, and introducing the random signs $\varepsilon_{i}$. The rescaling has no statistical effect, and nor do the random signs, since the noise is symmetric (so that $\xi_{i}=\varepsilon_{i}\widetilde{\xi}_{i}$ has the same distribution as $\widetilde{\xi}_{i}$). Thus, the observation model (3) is statistically equivalent to the original one (1).

where we have defined the weighted Frobenius norm $|\!|\!|\cdot|\!|\!|_{{{\omega(F)}}}$ in terms of the row $R$ and column $C$ weights. As a consequence, the signal-to-noise ratio in the observation model (3) is given by the ratio $\operatorname{SNR}=\frac{|\!|\!|\Theta^{*}|\!|\!|^{2}_{\omega(F)}}{\nu^{2}}$.

As shown by Negahban et al. , a key ingredient in establishing error bounds for the observation model (3) is obtaining lower bounds on the restricted curvature of the sampling operator—in particular, to establish the existence of a constant $c>0$, which may be arbitrarily small as long as it is positive, such that

3 Controlling the spikiness and rank

In order to provide a tractable measure of how close $\Theta$ is to a low-rank matrix, we define (for any non-zero matrix) the ratio

with equality holding if all the non-zero singular values of $\sqrt{R}\Theta\sqrt{C}$ are identical.

Main results and their consequences

We now turn to the statement of our main results, and discussion of their consequences. Section 3.1 is devoted to a result showing that a suitable form of restricted strong convexity holds for the random sampling operator ${\mathfrak{X}_{n}}$, as long as we restrict it to matrices $\Delta$ for which $\beta_{\operatorname{ra}}(\Delta)$ and $\alpha_{\operatorname{sp}}(\Delta)$ are not “overly large”. In Section 3.2, we develop the consequences of the RSC condition for noisy matrix completion, and in Section 3.3, we prove that our error bounds are minimax-optimal up to logarithmic factors. In Section 3.4, we provide a detailed comparison of our results with past work.

Introducing the convenient shorthand $d=\frac{1}{2}({d_{r}}+{d_{c}})$, let us define the constraint set

where $c_{0}$ is a universal constant. Note that as the sample size $n$ increases, this set allows for matrices with larger values of the spikiness and/or rank measures, $\alpha_{\operatorname{sp}}(\Delta)$ and $\beta_{\operatorname{ra}}(\Delta)$ respectively.

There are universal constants $(c_{0},c_{1},c_{2},c_{3})$ such that as long as $n>c_{3}\,d\log d$, we have

with probability greater than $1-c_{1}\exp(-c_{2}d\log d)$.

Roughly speaking, this bound guarantees that the observation operator captures a substantial component of any matrix $\Delta\in\mathfrak{C}(n;c_{0})$ that is not overly spiky. More precisely, as long as $\frac{128\alpha_{\operatorname{sp}}(\Delta)}{\sqrt{n}}\leq\frac{1}{2}$, the bound (9) implies that

Since the Hessian matrix of this function is given by ${\mathfrak{X}_{n}}^{*}{\mathfrak{X}_{n}}/n$, the bound (10) implies that the quadratic loss is strongly convex in a restricted set of directions $\Delta$.

As discussed previously, the worst-case value of the “spikiness” measure is $\alpha_{\operatorname{sp}}(\Delta)=\sqrt{{d_{r}}{d_{c}}}$, achieved for a matrix that is zero everywhere except a single position. In this most degenerate of cases, the combination of the constraints $\frac{\alpha_{\operatorname{sp}}(\Delta)}{\sqrt{n}}<1$ and the membership condition $\Delta\in\mathfrak{C}(n;c_{0})$ imply that even for a rank one matrix (so that $\beta_{\operatorname{ra}}(\Delta)=1$), we need sample size $n\gg d^{2}$ for Theorem 1 to provide a non-trivial result, as is to be expected.

2 Consequences for noisy matrix completion

We now turn to some consequences of Theorem 1 for matrix completion in the noisy setting. In particular, assume that we are given $n$ i.i.d. samples from the model (3), and let $\widehat{\Theta}$ be some estimate of the unknown matrix $\Theta^{*}$. Our strategy is to exploit the lower bound (9) in application to the error matrix $\widehat{\Theta}-\Theta^{*}$, and accordingly, we need to ensure that it has relatively low-rank and spikiness. Based on this intuition, it is natural to consider the estimator

Past work on matrix completion has focused on the case of exactly low-rank matrices. Here we consider the more general setting of approximately low-rank matrices, including the exact setting as a particular case. We begin by stating a general upper bound that applies to any matrix $\Theta^{*}$, and involves a natural decomposition into estimation and approximation error terms.

Consider any solution $\widehat{\Theta}$ to the weighted SDP (11) using regularization parameter

and define $\lambda_{n}^{*}=\max\{\lambda_{n},\sqrt{\frac{d\log d}{n}}\}$. Then with probability greater than $1-c_{2}\exp(-c_{2}\log d)$, for each $r=1,\ldots,{d_{r}}$, the error $\widetilde{\Delta}=\widehat{\Theta}-\Theta^{*}$ satisfies

Notice how the bound (13) shows a natural splitting into two terms. The first can be interpreted as the estimation error associated with a rank $r$ matrix, whereas the second term corresponds to approximation error, measuring how far $\sqrt{R}\Theta^{*}\sqrt{C}$ is from a rank $r$ matrix. Of course, the bound holds for any choice of $r$, and in the corollaries to follow, we choose $r$ optimally so as to balance the estimation and approximation error terms.

In order to provide concrete rates using Theorem 2, it remains to address two issues. First, we need to specify an explicit choice of $\lambda_{n}$ by bounding the operator norm of the matrix $\frac{1}{n}\sum_{i=1}^{n}\xi_{i}\sqrt{R}X^{(i)}\sqrt{C}$, and secondly, we need to understand how to choose the parameter $r$ so as to achieve the tightest possible bound. When $\Theta^{*}$ is exactly low-rank, then it is obvious that we should choose $r=\operatorname{rank}(\Theta^{*})$, so that the approximation error vanishes—viz. $\sum_{j=r+1}^{d_{r}}\sigma_{j}(\sqrt{R}\Theta^{*}\sqrt{C})_{j}=0$. Doing so yields the following result:

Suppose that the noise sequence $\{\xi_{i}\}$ is i.i.d., zero-mean and sub-exponential, and $\Theta^{*}$ has rank at most $r$, Frobenius norm at most $1$, and spikiness at most $\alpha_{\operatorname{sp}}(\Theta^{*})\leq\alpha^{*}$. If we solve the SDP (11) with $\lambda_{n}=4L\nu\sqrt{\frac{d\log d}{n}}$ then there is a numerical constant $c^{\prime}_{1}$ such that

with probability greater than $1-c_{2}\exp(-c_{3}\log d)$.

Note that this rate has a natural interpretation: since a rank $r$ matrix of dimension ${d_{r}}\times{d_{c}}$ has roughly $r({d_{r}}+{d_{c}})$ free parameters, we require a sample size of this order (up to logarithmic factors) so as to obtain a controlled error bound. An interesting feature of the bound (14) is the term $\nu^{2}\vee 1=\max\{\nu^{2},1\}$, which implies that we do not obtain exact recovery as $\nu\rightarrow 0$. As we discuss at more length in Section 3.4, under the mild spikiness condition that we have imposed, this behavior is unavoidable due to lack of identifiability within a certain radius, as specified in the set $\mathfrak{C}$. For instance, consider the matrix $\Theta^{*}$ and the perturbed version $\widetilde{\Theta}=\Theta^{*}+\frac{1}{\sqrt{{d_{r}}{d_{c}}}}e_{1}e_{1}^{T}$. With high probability, we have ${\mathfrak{X}_{n}}(\Theta^{*})={\mathfrak{X}_{n}}(\widetilde{\Theta})$, so that the observations—even if they were noiseless—fail to distinguish between these two models. These types of examples, leading to non-identifiability, cannot be overcome without imposing fairly restrictive matrix incoherence conditions, as we discuss at more length in Section 3.4.

For $q=0$, this set corresponds to the set of matrices with rank at most $r=\rho_{0}$, whereas for values $q\in(0,1]$, it consists of matrices whose (weighted) singular values decay at a relatively fast rate. By applying Theorem 2 to this matrix family, we obtain the following corollary:

with probability greater than $1-c_{2}\exp(-c_{3}\log d)$.

Note that this result is a strict generalization of Corollary 1, to which it reduces in the case $q=0$. (When $q=0$, we have $\rho_{0}=r$ so that the bound has the same form.) Note that the price that we pay for approximately low rank is a smaller exponent—namely, $1-q/2$ as opposed to $1$ in the case $q=0$. The proof of Corollary 2 is based on a more subtle application of Theorem 2, one which chooses the effective rank $r$ in the bound (13) so as to trade off between the estimation and approximation errors. In particular, the choice $r\asymp\rho_{q}\,(\frac{n}{d\log d})^{q/2}$ turns out to yield the optimal trade-off, and hence the given error bound (16).

In order to illustrate the sharpness of our theory, let us compare the predictions of our two corollaries to the empirical behavior of the $M$-estimator. In particular, we applied the nuclear norm SDP to simulated data, using Gaussian observation noise with variance $\nu^{2}=0.25$ and the uniform sampling model. In all cases, we solved the nuclear norm SDP using a non-smooth optimization procedure due to Nesterov , via our own implementation in MATLAB. For a given problem size $d$, we ran $T=25$ trials and computed the squared Frobenius norm error $|\!|\!|\widehat{\Theta}-\Theta^{*}|\!|\!|_{{F}}^{2}$ averaged over the trials.

Figure 1 shows the results in the case of exactly low-rank matrices ($q=0$), with the matrix rank given by $r=\lceil\log^{2}(d)\rceil$. Panel (a) shows plots of the mean-squared Frobenius error versus the raw sample size, for three different problem sizes with the number of matrix elements sizes $d^{2}\in\{40^{2},60^{2},80^{2},100^{2}\}$. These plots show that the $M$-estimator is consistent, since each of the curves decreases to zero as the sample size $n$ increases. Note that the curves shift to the right as the matrix dimension $d$ increases, reflecting the natural intuition that larger matrices require more samples. Based on the scaling predicted by Corollary 1, we expect that the mean-squared

Frobenius error should exhibit the scaling $|\!|\!|\widehat{\Theta}-\Theta^{*}|\!|\!|_{{F}}^{2}\asymp\frac{rd\log d}{n}$. Equivalently, if we plot the MSE versus the rescaled sample size $N:=\frac{n}{rd\log d}$, then all the curves should be relatively well aligned, and decay at the rate $1/N$. Panel (b) of Figure 1 shows the same simulation results re-plotted versus this rescaled sample size. Consistent with the prediction of Corollary 1, all four plots are now relatively well-aligned.

Figure 2 shows the same plots for the case of approximately low-rank matrices ($q=0.5$). Again, consistent with the prediction of Corollary 2, we see qualitatively similar behavior in the plots of the MSE versus sample size (panel (a)), and the rescaled sample size (panel (b)).

3 Information-theoretic lower bounds

Accordingly, in this section, we provide a direct and constructive argument to lower bound the minimax rates of Frobenius norm over classes of matrices that are near low-rank and not overly spiky. This argument establishes that the bounds established in Corollaries 1 and 2 are sharp up to logarithmic factors, meaning that no estimator performs substantially better than the one considered here. More precisely, consider the matrix classes

where the infimum is taken over all estimators $\widetilde{\Theta}$ that are measurable functions of $n$ samples.

There is a universal numerical constant $c_{5}>0$ such that

In the special case $q=0$, corresponding the exactly low-rank case, the bound (20) always holds, since it reduces to requiring that the rank $r=\rho_{0}$ is less than or equal to $d$. In these regimes, Theorem 3 establishes that the upper bounds obtained in Corollaries 1 and 2 are minimax-optimal up to factors logarithmic in matrix dimension $d$.

4 Comparison to other work

We now turn to a detailed comparison of our bounds to those obtained in past work on noisy matrix completion, in particular the papers by Candes and Plan (hereafter CP) and Keshavan et al. (hereafter KMO). Both papers considered only the case of exactly low-rank matrices, corresponding to the special case of $q=0$ in our notation. Since neither paper provided results for the general case of near-low rank matrices, nor the general result (with estimation and approximation errors) stated in Theorem 2, our discussion is limited to comparing Corollary 1 to their results. So as to simplify discussion, we restate all results under the scalings used in this paperThe paper CP and KMO use two different sets of scaling, one with $|\!|\!|\Theta^{*}|\!|\!|_{{F}}=\Theta(d)$ and the other with $|\!|\!|\Theta^{*}|\!|\!|_{{F}}=\sqrt{r}$, so that some care is required in converting between results. (i.e., with $|\!|\!|\Theta^{*}|\!|\!|_{{F}}=1$).

Note that if the noise standard deviation $\nu$ tends to zero while the sample size $n$, matrix size $p$ and rank $r$ all remain fixed, then this bound guarantees that the Frobenius error tends to zero. This behavior as $\nu\rightarrow 0$ is intuitively reasonable, given that their proof technique is an extrapolation from the case of exact recovery for noiseless observations ($\nu=0$). However, note that for any fixed noise deviation $\nu>0$, the first term increases to infinity as the matrix dimension $d$ increases, whereas the second term actually grows as the sample size $n$ increases. Consequently, the CP results do not guarantee statistical consistency, unlike the bounds proved here.

Keshavan et al. analyzed alternative methods based on trimming and applying the SVD. For Gaussian noise, their methods guarantee bounds (with high probability) of the form

where $d_{2}/d_{1}$ is the aspect ratio of $\Theta^{*}$, and $\kappa(\Theta^{*})=\frac{\sigma_{\operatorname{max}}(\Theta^{*})}{\sigma_{\operatorname{min}}(\Theta^{*})}$ is the condition number of $\Theta^{*}$. This result is more directly comparable to our Corollary 1; apart from the additional factor involving either the aspect ratio or the condition number, it is sharper since it does not involve the factor $\log d$ present in our bound. For a fixed noise standard deviation $\nu$, the bound (22) guarantees statistical consistency as long as $\frac{rd_{2}}{n}$ tends to zero. The most significant differences are the presence of the aspect ratio $d_{2}/d_{1}$ or the condition number $\kappa(\Theta^{*})$ in the upper bound (22). The aspect ratio is a quantity that can be as small as one, or as large as $d_{2}$, so that the pre-factor in the bound (22) can scale in a dimension-dependent way. Similarly, for any matrix with rank larger than one, the condition number can be made arbitrarily large. For instance, in the rank two case, define a matrix with $\sigma_{\operatorname{max}}(\Theta^{*})=\sqrt{1-\delta^{2}}$ and $\sigma_{\operatorname{min}}(\Theta^{*})=\delta$, and consider the behavior as $\delta\rightarrow 0$. In contrast, our bounds are invariant to both the aspect ratio and the condition number of $\Theta^{*}$.

4.2 Comparison of matrix conditions

for some constant $\mu>0$. Parts of the KMO analysis impose the related incoherence condition

Both of these conditions ensure that the singular vectors are sufficiently “spread-out”, so as not to be aligned with the standard basis.

A remarkable property of conditions (23) and (24) is that they exhibit no dependence on the singular values of $\Theta^{*}$. If one is interested only in exact recovery in the noiseless setting, then this lack of dependence is reasonable. However, if approximate recovery is the goal—as is necessarily the case in the more realistic setting of noisy observations—then it is clear that a minimal set of sufficient conditions should also involve the singular values, as is the case for our spikiness measure $\alpha_{\operatorname{sp}}(\Theta^{*})$. The following example gives a concrete demonstration of an instance where our conditions are satisfied, so that approximate recovery is possible, whereas the incoherence conditions are violated.

Consequently, for any choice of $\Gamma$ as specified above, Corollary 1 implies that the SDP will recover the matrix $\Theta^{*}$ up to a tolerance ${\mathcal{O}}(\sqrt{\frac{rd\log d}{n}})$. This captures the natural intuition that “poisoning” the matrix $\Gamma$ with the term $te_{1}^{T}e_{1}$ should have essentially no effect, as long as $t$ is not too large.

Proofs for noisy matrix completion

We now turn to the proofs of our results. This section is devoted to the results that apply directly to noisy matrix completion, in particular the achievable result given in Theorem 2, its associated Corollaries 1 and 2, and the information-theoretic lower bound given in Theorem 3. The proof of Theorem 1 is provided in Section 5 to follow.

where $\widetilde{X}^{(i)}:=R^{-1/2}\,X^{(i)}C^{-1/2}$. Note that ${\mathfrak{X}_{n}}^{\prime}(\Gamma)={\mathfrak{X}_{n}}(\Theta)$ by construction, and moreover

Based on this change of variables, let us define a modified version of the constraint set (8) as follows

In this new notation, the lower bound (9) from Theorem 1 can be re-stated as

2 Proof of Theorem 2

We now turn to the proof of Theorem 2. Defining the estimate $\widehat{\Gamma}:=\sqrt{R}\widehat{\Theta}\sqrt{C}$, we have

and our goal is to upper bound the ordinary Frobenius norm $|\!|\!|\widehat{\Gamma}-\Gamma^{*}|\!|\!|_{{F}}$.

We now state a useful technical result. Parts (a) and (b) of the following lemma were proven by Recht et al. and Negahban and Wainwright , respectively.

Let $(\widetilde{U},\widetilde{V})$ represent a pair of $r$-dimensional subspaces of left and right singular vectors of $\Gamma^{*}$. Then there exists a matrix decomposition $\widehat{\Delta}=\widehat{\Delta}^{\prime}+\widehat{\Delta}^{\prime\prime}$ of the error $\widehat{\Delta}$ such that

The matrix $\widehat{\Delta}^{\prime}$ satisfies the constraint $\operatorname{rank}(\widehat{\Delta}^{\prime})\leq 2r$, and

Given the choice (12), the nuclear norm of $\widehat{\Delta}^{\prime\prime}$ is bounded as

Note that the bound (30), combined with triangle inequality, implies that

where the second inequality uses the fact that $\operatorname{rank}(\widehat{\Delta}^{\prime})\leq 2r$.

We now split into two cases, depending on whether or not the error $\widehat{\Delta}$ belongs to the set $\mathfrak{C}^{\prime}(n;c_{0})$.

First suppose that $\widehat{\Delta}\notin\mathfrak{C}^{\prime}(n;c_{0})$. In this case, by the definition (27), we have

since $\|\widehat{\Delta}\|_{\infty}\leq\|\Gamma^{*}\|_{\infty}+\|\widehat{\Gamma}\|_{\infty}\leq\frac{2\alpha^{*}}{\sqrt{{d_{r}}{d_{c}}}}$. Now applying the bound (31), we obtain

Otherwise, we must have $\widehat{\Delta}\in\mathfrak{C}^{\prime}(n;c_{0})$. Recall the reformulated lower bound (28). On one hand, if $\frac{128\alpha_{\operatorname{sp}}^{\prime}(\widehat{\Delta})}{\sqrt{n}}>1/2$, then we have

On the other hand, if $\frac{128\alpha_{\operatorname{sp}}^{\prime}(\widehat{\Delta})}{\sqrt{n}}\leq 1/2$, then from the bound (28), we have

with high probability. Note that $\widehat{\Gamma}$ is optimal and $\Gamma^{*}$ is feasible for the convex program (29), so that we have the basic inequality

Substituting the lower bound (34) into this inequality yields

From this point onwards, the proof is identical (apart from constants) to Theorem 1 in Negahban and Wainwright , and we obtain that there is a numerical constant $c_{1}$ such that

Summarizing our results, we have shown that with high probability, one of the three bounds (32), (33) or (35) must hold. Since $\alpha^{*}\geq 1$, we can summarize by claiming that there is a universal constant $c_{1}$ such that

Translating this result back to the original co-ordinate system ($\Gamma^{*}=\sqrt{R}\Theta^{*}\sqrt{C}$) yields the claim (13).

3 Proof of Corollary 1

When $\Theta^{*}$ (and hence $\sqrt{R}\Theta^{*}\sqrt{C}$) has rank $r<{d_{r}}$, then we have $\sum_{j=r+1}^{d_{r}}\sigma_{j}(\sqrt{R}\Theta^{*}\sqrt{C})=0$. Consequently, the bound (13) reduces to $|\!|\!|\widetilde{\Delta}|\!|\!|_{{{\omega(F)}}}\leq c_{1}\,\alpha^{*}\,\lambda_{n}^{*}\sqrt{r}$. To complete the proof, it suffices to show that

We do so via the Alhswede-Winter matrix bound, as stated in Appendix F. Defining the random matrix ${Y^{(i)}}:=\xi_{i}R^{-1/2}\,X^{(i)}\,C^{-1/2}$, we first note that $\xi_{i}$ is sub-exponential with parameter $1$, and $|R^{-1/2}X^{(i)}C^{-1/2}|$ has a single entry with magnitude at most $L\sqrt{{d_{r}}{d_{c}}}$, which implies that

(Here $\|\cdot\|_{\psi_{1}}$ denotes the Orlicz norm of a random variable, as defined by the function $\psi_{1}(x)=\exp(x)-1$; see Appendix F). Moreover, we have

Since $\sqrt{{d_{r}}{d_{c}}}\leq{d_{r}}+{d_{c}}=2d$, if we set $\delta^{2}=c_{1}^{2}\nu^{2}\frac{d\log d}{n}$ for a sufficiently large constant $c_{1}$, the result follows. (Here we also use the assumption that $n=\Omega(d\log d)$, so that the term $\sqrt{\frac{d\log d}{n}}$ is dominant.)

4 Proof of Corollary 2

For this corollary, we need to determine an appropriate choice of $r$ so as to optimize the bound (13). To ease notation, let us make use of the shorthand notation $\Gamma^{*}=\sqrt{R}\Theta^{*}\sqrt{C}$. With the singular values of $\Gamma^{*}$ ordered in non-increasing order, fix some threshold $\tau>0$ to be determined, and set $r=\max\{j\,\mid\,\sigma_{j}(\Gamma^{*})>\tau\}$. This choice ensures that

Moreover, we have r\,\tau^{q}\leq\sum_{j=1}^{r}\big{\{}\sigma_{j}(\Gamma^{*})\big{\}}^{q}\;\leq\rho_{q}, which implies that $\sqrt{r}\leq\sqrt{\rho_{q}}\tau^{-q/2}$. Substituting these relations into the upper bound (13) leads to

In order to obtain the sharpest possible upper bound, we set $\tau=\alpha^{*}\lambda_{n}^{*}$. Following some algebra, we find that there is a universal constant $c_{1}$ such that

As in the proof of Corollary 1, it suffices to choose $\lambda_{n}=\Omega(\nu\sqrt{\frac{d\log d}{n}})$, so that $\lambda_{n}^{*}={\mathcal{O}}\sqrt{(\nu^{2}+1)\frac{d\log d}{n}})$, from which the claim follows.

5 Proof of Theorem 3

Our proof of this lower bound based on a combination of information-theoretic methods , which allow us to reduce to a multiway hypothesis test, and an application of the probabilistic method so as to construct a suitably large packing set. By Markov’s inequality, it suffices to prove that

If we condition on ${\mathfrak{X}_{n}}$, a variant of Fano’s inequality yields

Combined with the bound (36), we obtain the bound

The remainder of the proof hinges on the following technical lemma, which we prove in Appendix A.

Let $d\geq 10$ be a positive integer, and let $\delta>0$. Then for each $r=1,2,\ldots,d$, there exists a set of $d$-dimensional matrices $\{\Theta^{1},\ldots,\Theta^{M}\}$ with cardinality M=\lfloor\frac{1}{4}\exp\big{(}\frac{rd}{128}\big{)}\rfloor such that each matrix has rank $r$, and moreover

If we now choose $\delta^{2}=\frac{\nu^{2}}{2048}\frac{rd}{n}$, then

where the final inequality again uses the bound $rd\geq 1024\log 2$.

so that we conclude that the minimax error is lower bounded by

for $dr$ sufficiently large. (At the expense of a worse pre-factor, the same bound holds for all $d\geq 10$.)

Proof of Theorem 1

We now turn to the proof that the sampling operator in weighted matrix completion satisfies restricted strong convexity over the set $\mathfrak{C}$, as stated in Theorem 1. In order to lighten notation, we prove the theorem in the case ${d_{r}}={d_{c}}$. In terms of rates, this is a worst-case assumption, effectively amounting to replacing both ${d_{r}}$ and ${d_{c}}$ by the worst-case $\max\{{d_{r}},{d_{c}}\}$. However, since our rates are driven by $d=\frac{1}{2}({d_{r}}+{d_{c}})$ and we have the inequalities

this change has only an effect on the constant factors. The proof can be extended to the general setting ${d_{r}}\neq{d_{c}}$ by appropriate modifications if these constant factors are of interest.

In order to prove Theorem 1, it is equivalent to show that, with high probability, we have

The remainder of the proof is devoted to studying the “bad” event

Suppose that $\mathcal{E}({\mathfrak{X}_{n}}^{\prime})$ does not hold: then we have

We now show that in order to establish a tail bound on $\mathcal{E}({\mathfrak{X}_{n}}^{\prime})$, it suffices to bound the probability of some simpler events $\mathcal{E}({\mathfrak{X}_{n}}^{\prime};D)$, defined below. Since the definition of the set $\mathfrak{C}^{\prime}(n;c_{0})$ and event $\mathcal{E}({\mathfrak{X}_{n}}^{\prime})$ is invariant to rescaling of $\Gamma$, we may assume without loss of generality that $\|\Gamma\|_{\infty}=\frac{1}{d}$. The remaining degrees of freedom in the set $\mathfrak{C}^{\prime}(n;c_{0})$ can be parameterized in terms of the quantities $D=|\!|\!|\Gamma|\!|\!|_{{F}}$ and $\rho=|\!|\!|\Gamma|\!|\!|_{{1}}$. For any $\Gamma\in\mathfrak{C}^{\prime}(n;c_{0})$ with $\|\Gamma\|_{\infty}=\frac{1}{d}$ and $|\!|\!|\Gamma|\!|\!|_{{F}}\leq D$, we have $|\!|\!|\Gamma|\!|\!|_{{1}}\leq\rho(D)$, where

The following lemma shows that it suffices to upper bound the probability of the event $\mathcal{E}({\mathfrak{X}_{n}}^{\prime};D)$ for each fixed $D>0$.

Suppose that are universal constants $(c_{1},c_{2})$ such that

for each fixed $D>0$. Then there is a universal constant $c^{\prime}_{2}$ such that

The proof of this claim, provided in Appendix B, follows by a peeling argument.

Based on Lemma 3, it suffices to prove the tail bound (44) on the event $\mathcal{E}({\mathfrak{X}_{n}}^{\prime};D)$ for each fixed $D>0$. Let us define

(The only difference from $\mathfrak{B}(D)$ is that we have relaxed to the inequality $\|\Gamma\|_{\infty}\leq\frac{1}{d}$.) In the remainder of this section, we prove that there are universal constants $(c_{1},c_{2})$ such that

This tail bound means that the condition of Lemma 3 is satisfied, and so completes the proof of Theorem 1.

where we have used the triangle inequality. Following the same steps establishes that this inequality holds for the absolute value of the difference.

Moreover, since $\Delta=\Gamma^{k}-\Gamma$ with both $\Gamma^{k}$ and $\Gamma$ belonging to $\makebox[0.0pt][l]{\hskip 2.05pt\rule[8.12498pt]{4.78166pt}{0.43057pt}}{\mathfrak{B}}(D)$, we have $|\!|\!|\Delta|\!|\!|_{{1}}\leq 2\rho(D)$ and $\|\Delta\|_{\infty}\leq\frac{2}{d}$, where we have used the definition (42). Putting together the pieces, we conclude that

Note that the bound (49) holds for any choice of $\delta>0$. We establish the tail bound (48) with the choice $\delta=D/8$, and using the following two lemmas. The first lemma provides control of the maximum over the covering set:

with probability greater than 1-c\exp\big{(}-\,\frac{nD^{2}}{2048\,L^{2}}\big{)}.

See Appendix C for the proof of this claim.

Our second lemma, proved in Appendix D, provides control over the final term in the upper bound (49).

with probability at least 1-2\exp\big{(}-\frac{nD^{2}}{8192L^{2}}\big{)}.

Combining these two lemmas with the upper bound (49) with $\delta=D/8$, we obtain

with probability at least 1-4\exp\big{(}-\frac{nD^{2}}{8192}\big{)}, thereby establishing the tail bound (48) and completing the proof of Theorem 1.

Discussion

In this paper, we have established error bounds for the problem of weighted matrix completion based on partial and noisy observations. We proved both a general result, one which applies to any matrix, and showed how it yields corollaries for both the cases of exactly low-rank and approximately low-rank matrices. A key technical result is establishing that the matrix sampling operator satisfies a suitable form of restricted strong convexity over a set of matrices with controlled rank and spikiness. Since more restrictive properties such as RIP do not hold for matrix completion, this RSC ingredient is essential to our analysis. Our proof of the RSC condition relied on a number of techniques from empirical process and random matrix theory, including concentration of measure, contraction inequalities and the Ahlswede-Winter bound. Using information-theoretic methods, we also proved that up to logarithmic factors, our error bounds cannot be improved upon by any algorithm, showing that our method is essentially minimax-optimal.

There are various open questions that remain to be studied. Although our analysis applies to both uniform and non-uniform sampling models, it is limited to the case where each row (or column) is sampled with a certain probability. It would be interesting to consider extensions to settings in which the sampling probability differed from entry to entry, as investigated empirically by Salakhutdinov and Srebro .

SN and MJW were partially supported by NSF grants DMS-0907632, NSF-CDI-0941742, and Air Force Office of Scientific Research AFOSR-09NL184.

Appendix A Proof of Lemma 2

This is a sum of $rd$ i.i.d. variables, each bounded by $4$. The mean of the sum is $2$, so that the Hoeffding bound implies that

Since there are less than $(M^{\prime})^{2}$ pairs of matrices in total, setting $t=1$ yields

Setting $t=s/d$ and taking the union bound over all $d^{2}$ indices, we obtain

for $d\geq 10$. Since $r\leq d$, we conclude that

Consider the event $\mathcal{E}$ that there exists a subset $S\subset\{1,\ldots,M^{\prime}\}$ of cardinality $M=\frac{1}{4}M^{\prime}$ such that

Appendix B Proof of Lemma 3

We first observe that for any $\Gamma\in\mathfrak{C}^{\prime}(n;c_{0})$ with $\|\Gamma\|_{\infty}=\frac{1}{d}$, we have

Since $n\mu^{2}=\Omega(d\log d)$, the claim follows.

Appendix C Proof of Lemma 4

For a fixed matrix $\Gamma$, define the function $F_{\Gamma}({\mathfrak{X}_{n}}^{\prime})=\frac{1}{\sqrt{n}}\|{\mathfrak{X}_{n}}^{\prime}(\Gamma)\|_{2}$. We prove the lemma in two parts: first, we establish that for any fixed $\Gamma$, the function $F_{\Gamma}$ satisfies the tail bound

We then show that there exists a $\delta$-covering of $\makebox[0.0pt][l]{\hskip 2.05pt\rule[8.12498pt]{4.78166pt}{0.43057pt}}{\mathfrak{B}}(D)$ such that

Combining the tail bound (57) with the union bound, we obtain

where the final inequality follows uses the bound (58). Since Lemma 4 is based on the choice $\delta=D/8$, it suffices to show that

Noting that the terms involving $D^{2}$ and $n$ both cancel out, we see that for any fixed $c_{0}$, this inequality holds once $\log d$ is sufficiently large. By choosing $c_{0}$ sufficiently large, we can ensure that it holds for all $d\geq 2$.

It remains to establish the two intermediate claims (57) and (58).

Letting $\Pi_{\mathcal{S}}$ denote the projection operator under Frobenius norm onto this set, we claim that $\{\Pi_{\mathcal{S}}(\Gamma^{j}),j=1,\ldots,\widetilde{N}(\delta)\}$ is a $\delta$-cover of $\makebox[0.0pt][l]{\hskip 2.05pt\rule[8.12498pt]{4.78166pt}{0.43057pt}}{\mathfrak{B}}(D)$. Indeed, since $\mathcal{S}$ is non-empty, closed and convex, the projection operator is non-expansive , and thus for any $\Gamma\in\makebox[0.0pt][l]{\hskip 2.05pt\rule[8.12498pt]{4.78166pt}{0.43057pt}}{\mathfrak{B}}(D)\subset\mathcal{S}$, we have

Recalling the definition of the operator ${\mathfrak{X}_{n}}^{\prime}$, we have

where we have defined the random variables $Y_{i}:=\langle\!\langle{\widetilde{X}^{(i)}},\;{\Gamma}\rangle\!\rangle$. Note that each $Y_{i}$ is zero-mean, and bounded by $2L$ since

where we have used the facts that $\|\Gamma\|_{\infty}\leq 2/d$, and $\sum_{a,b}|\widetilde{X}^{(i)}|_{ab}\leq L\;d$, by definition of the matrices $\widetilde{X}^{(i)}$.

Therefore, applying Corollary 4.8 from Ledoux , we conclude that

Appendix D Proof of Lemma 5

From the proof of Lemma 4, recall the definition $F_{\Gamma}({\mathfrak{X}_{n}}^{\prime})=\frac{1}{\sqrt{n}}\|{\mathfrak{X}_{n}}^{\prime}(\Gamma)\|_{2}$ where ${\mathfrak{X}_{n}}^{\prime}$ is the random sampling operator defined by the $n$ matrices $(\widetilde{X}^{(1)},\ldots,\widetilde{X}^{(n)})$. Using this notation, our goal is to bound the function

For any fixed $\Delta\in\mathfrak{D}(\delta,R)$, we have

where we have used the fact that the matrix $\widetilde{X}^{(1)}-Z^{(1)}$ is non-zero in at most two entries with values upper bounded by $2Ld$. Combining the pieces yields $G({\mathfrak{X}_{n}}^{\prime})-G(\widetilde{{\mathfrak{X}_{n}}^{\prime}})\leq\frac{4L}{\sqrt{n}}$. Since the same argument can be applied with the roles of ${\mathfrak{X}_{n}}^{\prime}$ and $\widetilde{{\mathfrak{X}_{n}}^{\prime}}$ interchanged, we conclude that $|G({\mathfrak{X}_{n}}^{\prime})-G(\widetilde{{\mathfrak{X}_{n}}^{\prime}})|\leq\frac{4L}{\sqrt{n}}$. Therefore, by the bounded differences variant of the Azuma-Hoeffding inequality , we have

Next we bound the expectation. First applying Jensen’s inequality, we have

where $\{\varepsilon_{i}\}_{i=1}^{n}$ is an i.i.d. Rademacher sequence. Since $|\langle\!\langle{\widetilde{X}^{(i)}},\;{\Delta}\rangle\!\rangle|\leq 2L$ for all $i$, the Ledoux-Talagrand contraction inequality (p. 112, Ledoux and Talagrand ) implies that

By the duality between operator and nuclear norms, we have

and hence, since $|\!|\!|\Delta|\!|\!|_{{1}}\leq\rho(D)$ for all $\Delta\in\mathfrak{D}(\delta,R)$, we have

Thus, as long as $n=\Omega(d\log d)$, combined with the earlier bound (60), we conclude that

using the fact that $L\geq 1$. By definition of $\rho(D)$, we have

where the final inequality can be guaranteed by choosing $c_{0}$ sufficiently large.

Consequently, recalling our choice $\delta=D/8$ and using the inequality $\sqrt{a^{2}+b^{2}}\leq|a|+|b|$, we obtain

Finally, setting $t=\frac{D}{16}$ in the concentration bound (59) yields

with probability at least 1-2\exp\big{(}-c^{\prime}\,\frac{nD^{2}}{L^{2}}\big{)} as claimed.

Appendix E Proof of Lemma 6

We prove this lemma by applying a form of Ahlwehde-Winter matrix bound , as stated in Appendix F, to the matrix ${Y^{(i)}}:=\varepsilon_{i}\widetilde{X}^{(i)}$. We first compute the quantities involved in Lemma 7. Note that ${Y^{(i)}}$ is a zero-mean random matrix, and satisfies the bound

Let us now compute the quantities $\sigma_{i}$ in Lemma 7. We have

Thus, applying Lemma 7 yields the tail bound

where the second inequality follows since $L\geq 1$.

Appendix F Ahlswede-Winter matrix bound

Here we state a Bernstein version of the Ahlswede-Winter tail bound for the operator norm of a sum of random matrices. The version here is a slight weakening (but sufficient for our purposes) of a result due to Recht ; we also refer the reader to the notes of Vershynin , and the strengthened results provided by Tropp .

Let ${Y^{(i)}}$ be independent ${d_{r}}\times{d_{c}}$ zero-mean random matrices such that $|\!|\!|{Y^{(i)}}|\!|\!|_{{2}}\leq M$, and define

as well as $\sigma^{2}:=\sum_{i=1}^{n}\sigma^{2}_{i}$.

As noted by Vershynin , the same bound also holds under the assumption that each ${Y^{(i)}}$ is sub-exponential with parameter $M=\|{Y^{(i)}}\|_{\psi_{1}}$. Here we are using the Orlicz norm

defined by the function $\psi_{1}(x)=\exp(x)-1$, as is appropriate for sub-exponential variables (e.g., see the book ).

References