A Simpler Approach to Matrix Completion

Introduction

Recovering a low rank matrix from a given subset of its entries is a recurring problem in collaborative filtering , dimensionality reduction , and multi-class learning . While a variety of heuristics have been developed across many disciplines, the general problem of finding the lowest rank matrix satisfying equality constraints is NP-hard. All known algorithms which can compute the lowest rank solution for all instances require time at least exponential in the dimensions of the matrix in both theory and practice .

Nuclear norm minimization had long been observed to produce very low-rank solutions in practice (see, for example ), but only very recently was there any theoretical basis for when it produced the minimum rank solution. The first paper to provide such foundations was , where Recht, Fazel, and Parrilo developed probabilistic techniques to study average case behavior and showed that the nuclear norm heuristic could solve most instances of the rank minimization problem assuming the number of linear constraints was sufficiently large. The results in inspired a groundswell of interest in theoretical guarantees for rank minimization, and these results lay the foundation for . Candès and Recht’s bounds were subsequently improved by Candès and Tao and Keshavan, Montanari, and Oh to show that one could, in special cases, reconstruct a low-rank matrix by observing a set of entries of size at most a polylogarithmic factor larger than the intrinsic dimension of the variety of rank $r$ matrices.

This paper sharpens the results in to provide a bound on the number of entries required to reconstruct a low rank matrix which is optimal up to a small numerical constant and one logarithmic factor. The main theorem makes minimal assumptions about the low rank matrix of interest. Moreover, the proof is very short and relies on mostly elementary analysis.

In order to precisely state the main result, we need one definition. Candès and Recht observed that it is impossible to recover a matrix which is equal to zero in nearly all of its entries unless all of the entries of the matrix are observed (consider, for example, the rank one matrix which is equal to $1$ in one entry and zeros everywhere else). In other words, the matrix cannot be mostly equal to zero on the observed entries. This motivated the following definition

Note that for any subspace, the smallest $\mu(U)$ can be is $1$, achieved, for example, if $U$ is spanned by vectors whose entries all have magnitude $1/\sqrt{n}$. The largest possible value for $\mu(U)$ is $n/r$ which would correspond to any subspace that contains a standard basis element. If a matrix has row and column spaces with low coherence, then each entry can be expected to provide about the same amount of information.

Recall that the nuclear norm of an $n_{1}\times n_{2}$ matrix $\bm{X}$ is the sum of the singular values of $\bm{X}$, $\|\bm{X}\|_{*}=\sum_{k=1}^{\min\{n_{1},n_{2}\}}\sigma_{k}(\bm{X})$, where, here and below, $\sigma_{k}(\bm{X})$ denotes the $k$th largest singular value of $\bm{X}$. The main result of this paper is the following

Let $\bm{M}$ be an $n_{1}\times n_{2}$ matrix of rank $r$ with singular value decomposition $\bm{U}\bm{\Sigma}\bm{V}^{*}$. Without loss of generality, impose the conventions $n_{1}\leq n_{2}$, $\bm{\Sigma}$ is $r\times r$, $\bm{U}$ is $n_{1}\times r$ and $\bm{V}$ is $n_{2}\times r$. Assume that

The row and column spaces have coherences bounded above by some positive $\mu_{0}$.

The matrix $\bm{U}\bm{V}^{*}$ has a maximum entry bounded by $\mu_{1}\sqrt{r/(n_{1}n_{2})}$ in absolute value for some positive $\mu_{1}$.

Suppose $m$ entries of $\bm{M}$ are observed with locations sampled uniformly at random. Then if

for some $\beta>1$, the minimizer to the problem

is unique and equal to $\bm{M}$ with probability at least $1-6\log(n_{2})(n_{1}+n_{2})^{2-2\beta}-n_{2}^{2-2\beta^{1/2}}$.

The assumptions $\bf{A0}$ and $\bf{A1}$ were introduced in . Both $\mu_{0}$ and $\mu_{1}$ may depend on $r$, $n_{1}$, or $n_{2}$. Moreover, note that $\mu_{1}\leq\mu_{0}\,\sqrt{r}$ by the Cauchy-Schwarz inequality. As shown in , both subspaces selected from the uniform distribution and spaces constructed as the span of singular vectors with bounded entries are not only incoherent with the standard basis, but also obey A1 with high probability for values of $\mu_{1}$ at most logarithmic in $n_{1}$ and/or $n_{2}$. Applying this theorem to the models studied in Section 2 of , we find that there is a numerical constant $c_{u}$ such that $c_{u}r(n_{1}+n_{2})\log^{5}(n_{2})$ entries are sufficient to reconstruct a rank $r$ matrix whose row and column spaces are sampled from the Haar measure on the Grassmann manifold. If $r>\log(n_{2})$, the number of entries can be reduced to $c_{u}r(n_{1}+n_{2})\log^{4}(n_{2})$. Similarly, there is a numerical constant $c_{i}$ such that $c_{i}\mu_{0}^{2}r(n_{1}+n_{2})\log^{3}(n_{2})$ entries are sufficient to recover a matrix of arbitrary rank $r$ whose singular vectors have entries with magnitudes bounded by $\sqrt{\mu_{0}/n_{1}}$.

Theorem 1.1 greatly improves upon prior results. First of all, it has the weakest assumptions on the matrix to be recovered. In addition to assumption A1, Candès and Tao require a “strong incoherence condition” (see ) which is considerably more restrictive than the assumption A0 in Theorem 1.1. Many of their results also require restrictions on the rank of $\bm{M}$, and their bounds depend superlinearly on $\mu_{0}$. Keshavan et al require the matrix rank to be no more than $\log(n_{2})$, and require bounds on the maximum magnitude of the entries in $\bm{M}$ and the ratios $\sigma_{1}(\bm{M})/\sigma_{r}(\bm{M})$ and $n_{2}/n_{1}$. Theorem 1.1 makes no such assumptions about the rank, aspect ratio, nor condition number of $\bm{M}$. Moreover, (1.2) has a smaller log factor than , and features numerical constants that are both explicit and small.

Also note that there is not much room for improvement in the bound for $m$. It is a consequence of the coupon collector’s problem that at least $n_{2}\log n_{2}$ uniformly sampled entries are necessary just to guarantee that at least one entry in every row and column is observed with high probability. In addition, rank $r$ matrices have $r(n_{1}+n_{2}-r)$ parameters, a fact that can be verified by counting the number of degrees of freedom in the singular value decomposition. Interestingly, Candès and Tao showed that $C\mu_{0}n_{2}r\log(n_{2})$ entries were necessary for completion when the entries are sampled uniformly at random . Hence, (1.2) is optimal up to a small numerical constant times $\log(n_{2})$.

Most importantly, the proof of Theorem 1.1 is short and straightforward. Candès and Recht employed sophisticated tools from the study of random variables on Banach spaces including decoupling tools and powerful moment inequalities for the norms of random matrices. Candès and Tao rely on intricate moment calculations spanning over $30$ pages. The present work only uses basic matrix analysis, elementary large deviation bounds, and a noncommutative version of Bernstein’s Inequality proven here in the Appendix.

The proof of Theorem 1.1 is inspired by a recent paper in quanutm information which considered the problem of reconstructing the density matrix of a quantum ensemble using as few measurements as possible . Their work adapted results from and to the quantum regime by using special algebraic properties of quantum measurements. Their proof followed a methodology analogous to the approach of Candès and Recht but had two main differences: they used a sampling with replacement model as a proxy for uniform sampling, and they deployed a powerful noncommutative Chernoff bound developed by Ahlswede and Winter for use in quantum information theory . In this paper, I adapt these two strategies from to the matrix completion problem. In section 3 I show how the sampling with replacement model bounds probabilities in the uniform sampling model, and present very short proofs of some of the main results in . Surprisingly, this yields a simple proof of Theorem 1.1, provided in Section 4, which has the least restrictive assumptions of any assertion proven thus far.

Preliminaries and notation

Before continuing, let us survey the notations used throughout the paper. I closely follow the conventions established in , and invite the reader to consult this reference for a more thorough discussion of the matrix completion problem and the associated convex geometry. A thorough introduction to the necessary matrix analysis used in this paper can be found in .

Linear transformations that act on matrices will be denoted by calligraphic letters. In particular, the identity operator will be denoted by $\mathcal{I}$. The spectral norm (the top singular value) of such an operator will be denoted by $\|{\cal A}\|=\sup_{\bm{X}:\|\bm{X}\|_{F}\leq 1}\,\|{\cal A}(\bm{X})\|_{F}$.

The orthogonal projection ${\cal P}_{T}$ onto $T$ is given by

where $\bm{P}_{U}$ and $\bm{P}_{V}$ are the orthogonal projections onto $U$ and $V$ respectively. Note here that while $\bm{P}_{U}$ and $\bm{P}_{V}$ are matrices, ${\cal P}_{T}$ is a linear operator mapping matrices to matrices. The orthogonal projection onto $T^{\perp}$ is given by

where $\bm{I}_{d}$ denotes the $d\times d$ identity matrix. It follows from the definition (2.1) of ${\cal P}_{T}$ that

Since $\|\bm{P}_{U}\bm{e}_{a}\|^{2}\leq\mu(U)r/n_{1}$ and $\|\bm{P}_{V}\bm{e}_{b}\|^{2}\leq\mu(V)r/n_{2}$,

I will make frequent use of this calculation throughout the sequel.

Sampling with Replacement

As discussed above, the main contribution of this work is an analysis of uniformly sampled sets of entries via the study of a sampling with replacement model. All of the previous work studied a Bernoulli sampling model as a proxy for uniform sampling. There, each entry was revealed independently with probability equal to $p$. In all of these results, the theorem statements concerned sampling sets of $m$ entries uniformly, but it was shown that probability of failure under Bernoulli sampling with $p=\tfrac{m}{n_{1}n_{2}}$ closely approximated the probability of failure under uniform sampling. The present work will analyze the situation where each entry index is sampled independently from the uniform distribution on $\{1,\ldots,n_{1}\}\times\{1,\ldots,n_{2}\}$. This modification of the sampling model gives rise to all of the simplifications below.

It would appear that sampling with replacement is not suitable for analyzing matrix completion as one might encounter duplicate entries. However, just as is the case with Bernoulli sampling, bounding the likelihood of error when sampling with replacement allows us to bound the probability of the nuclear norm heuristic failing under uniform sampling.

The probability that the nuclear norm heuristic fails when the set of observed entries is sampled uniformly from the collection of sets of size $m$ is less than or equal to the probability that the heuristic fails when $m$ entries are sampled independently with replacement.

Proof The proof follows the argument in Section II.C of . Let $\Omega^{\prime}$ be a collection of $m$ entries, each sampled independently from the uniform distribution on $\{1,\ldots,n_{1}\}\times\{1,\ldots,n_{2}\}$. Let $\Omega_{k}$ denote a set of entries of size $k$ sampled uniformly from all collections of entries of size $k$. It follows that

Where the inequality follows because $P(\mbox{Failure}(\Omega_{m}))\geq P(\mbox{Failure}(\Omega_{m^{\prime}}))$ if $m\leq m^{\prime}$. That is, the probability decreases as the number of entries revealed is increased.

Surprisingly, changing the sampling model makes most of the theorems from simple consequences of a noncommutative variant of Bernstein’s Inequality.

Note that in the case that $d_{1}=d_{2}=1$, this is precisely the two sided version of the standard Bernstein Inequality. When the $\bm{X}_{k}$ are diagonal, this bound is the same as applying the standard Bernstein Inequality and a union bound to the diagonal of the matrix summation. Furthermore, observe that the right hand side is less than $(d_{1}+d_{2})\exp(-\tfrac{3}{8}\tau^{2}/(\sum_{k=1}^{L}\rho_{k}^{2}))$ as long as $\tau\leq\tfrac{1}{M}\sum_{k=1}^{L}\rho_{k}^{2}$. This condensed form of the inequality will be used exclusively throughout. Theorem 3.2 is a corollary of an Chernoff bound for finite dimensional operators developed by Ahlswede and Winter . A similar inequality for symmetric i.i.d. matrices is proposed in . The proof is provided in the Appendix.

Let us now record two theorems, proven for the Bernoulli model in , that admit very simple proofs in the sampling with replacement model. The theorem statements requires some additional notation. Let $\Omega=\{(a_{k},b_{k})\}_{k=1}^{l}$ be a collection of indices sampled uniformly with replacement. Set ${\cal R}_{\Omega}$ to be the operator

Note that the $(i,j)$th component of ${\cal R}_{\Omega}(\bm{X})$ is zero unless $(i,j)\in\Omega$. For $(i,j)\in\Omega$, ${\cal R}_{\Omega}(\bm{X})$ is equal to $X_{ij}$ times the multiplicity of $(i,j)\in\Omega$. Unlike in previous work on matrix completion, ${\cal R}_{\Omega}$ is not a projection operator if there are duplicates in $\Omega$. Nonetheless, this does not adversely affect the argument, and ${\cal R}_{\Omega}(\bm{X})=0$ if and only if $X_{ab}=0$ for all $(a,b)\in\Omega$. Moreover, we can show that the maximum duplication of any entry is always less than $\tfrac{8}{3}\log(n_{2})$ with very high probability.

With probability at least $1-n_{2}^{2-2\beta}$, the maximum number of repetitions of any entry in $\Omega$ is less than $\tfrac{8}{3}\beta\log(n_{2})$ for $n_{2}\geq 9$ and $\beta>1$.

Proof This assertion can be proven by applying a standard Chernoff bound for the Bernoulli distribution. Note that for a fixed entry, the probability it is sampled more than $t$ times is equal to the probability of more than $t$ heads occurring in a sequence of $m$ tosses where the probability of a head is $\tfrac{1}{n_{1}n_{2}}$. This probability can be upper bounded by

(see , for example). Applying the union bound over all of the $n_{1}n_{2}$ entries and the fact that $\tfrac{m}{n_{1}n_{2}}<1$, we have

This application of the Chernoff bound is very crude, and much tighter bounds can be derived using more careful analysis. For example in , the maximum oversampling is shown to be bounded by $O(\tfrac{\log(n_{2})}{\log\log(n_{2})})$. For our purposes here, the loose upper bound provided by Proposition 3.3 will be more than sufficient.

In addition to this bound on the norm of ${\cal R}_{\Omega}$, the following theorem asserts that the operator ${\cal P}_{T}{\cal R}_{\Omega}{\cal P}_{T}$ is also very close to an isometry on $T$ if the number of sampled entries is sufficiently large. This result is analgous to the Theorem 4.1 in for the Bernoulli model, whose proof uses several powerful theorems from the study of probability in Banach spaces. Here, one only needs to compute a few low order moments and then apply Theorem 3.2.

Suppose $\Omega$ is a set of entries of size $m$ sampled independently and uniformly with replacement. Then for all $\beta>1$,

with probability at least $1-2n_{2}^{2-2\beta}$ provided that $m>\tfrac{16}{3}\mu_{0}r(n_{1}+n_{2})\,\beta\log(n_{2})$.

Proof Decompose any matrix $\bm{Z}$ as $\bm{Z}=\sum_{ab}\langle\bm{Z},\bm{e}_{a}\bm{e}_{b}^{*}\rangle\bm{e}_{a}\bm{e}_{b}^{*}$ so that

For $k=1,\ldots,m$ sample $(a_{k},b_{k})$ from $\{1,\ldots,n_{1}\}\times\{1,\ldots,n_{2}\}$ uniformly with replacement. Then ${\cal R}_{\Omega}{\cal P}_{T}(\bm{Z})=\sum_{k=1}^{m}\,\langle\bm{Z},{\cal P}_{T}(\bm{e}_{a_{k}}\bm{e}_{b_{k}}^{*})\rangle\,\bm{e}_{a_{k}}\bm{e}_{b_{k}}^{*}$ which gives

Now the fact that the operator ${\cal P}_{T}{\cal R}_{\Omega}{\cal P}_{T}$ does not deviate from its expected value

in the spectral norm can be proven using the Noncommutative Bernstein Inequality.

Observe that if $\bm{A}$ and $\bm{B}$ are positive semidefinite, we have $\|\bm{A}-\bm{B}\|\leq\max\{\|\bm{A}\|,\|\bm{B}\|\}$. Using this fact, we can compute the bound

where the final inequality follows from (2.2). We also have

The theorem now follows by applying the Noncommutative Bernstein Inequality.

The next theorem is an analog of Theorem 6.3 in or Lemma 3.2 in . This theorem asserts that for a fixed matrix, if one sets all of the entries not in $\Omega$ to zero it remains close to a multiple of the original matrix in the operator norm.

Suppose $\Omega$ is a set of entries of size $m$ sampled independently and uniformly with replacement and let $\bm{Z}$ be a fixed $n_{1}\times n_{2}$ matrix. Assume without loss of generality that $n_{1}\leq n_{2}$, Then for all $\beta>1$,

with probability at least $1-(n_{1}+n_{2})^{1-\beta}$ provided that $m>6\beta n_{1}\log(n_{1}+n_{2})$.

Proof First observe that the operator norm can be upper bounded by a multiple of the matrix infinity norm

Note that $\tfrac{n_{1}n_{2}}{m}{\cal R}_{\Omega}(\bm{Z})-\bm{Z}=\frac{1}{m}\sum_{k=1}^{m}n_{1}n_{2}Z_{a_{k}b_{k}}\bm{e}_{a_{k}}\bm{e}_{b_{k}}^{*}-\bm{Z}$. This is a sum of zero-mean random matrices, and $\|n_{1}n_{2}Z_{a_{k}b_{k}}\bm{e}_{a_{k}}\bm{e}_{b_{k}}^{*}-\bm{Z}\|\leq\|n_{1}n_{2}Z_{a_{k}b_{k}}\bm{e}_{a_{k}}\bm{e}_{b_{k}}^{*}\|+\|\bm{Z}\|<\tfrac{3}{2}n_{1}n_{2}\|\bm{Z}\|_{\infty}$ for $n_{1}\geq 2$. We also have

where we again use the fact that $\|\bm{A}-\bm{B}\|\leq\max\{\|\bm{A}\|,\|\bm{B}\|\}$ for positive semidefinite $\bm{A}$ and $\bm{B}$. A similar calculation holds for $(n_{1}n_{2}Z_{a_{k}b_{k}}\bm{e}_{a_{k}}\bm{e}_{b_{k}}^{*}-\bm{Z})(n_{1}n_{2}Z_{a_{k}b_{k}}\bm{e}_{a_{k}}\bm{e}_{b_{k}}^{*}-\bm{Z})^{*}$. The theorem now follows by the Noncommutative Bernstein Inequality.

Finally, the following Lemma is required to prove Theorem 1.1. Succinctly, it says that for a fixed matrix in $T$, the operator ${\cal P}_{T}{\cal R}_{\Omega}$ does not increase the matrix infinity norm.

Suppose $\Omega$ is a set of entries of size $m$ sampled independently and uniformly with replacement and let $\bm{Z}\in T$ be a fixed $n_{1}\times n_{2}$ matrix. Assume without loss of generality that $n_{1}\leq n_{2}$. Then for all $\beta>2$,

with probability at least $1-2n_{2}^{2-\beta}$ provided that $m>\tfrac{8}{3}\beta\mu_{0}r(n_{1}+n_{2})\log n_{2}$.

Since the $(c,d)$ entry of $\frac{n_{1}n_{2}}{m}{\cal P}_{T}{\cal R}_{\Omega}(\bm{Z})-\bm{Z}$ is identically distributed to $\tfrac{1}{m}\sum_{k=1}^{m}\xi_{cd}^{(k)}$, where $\xi_{cd}^{(k)}$ are i.i.d. copies of $\xi_{cd}$, we have by Bernstein’s Inequality and the union bound:

Proof of Theorem 1.1

The proof follows the program developed in which itself adapted the strategy proposed in . The main idea is to approximate a dual feasible solution of (1.3) which certifies that $\bm{M}$ is the unique minimum nuclear norm solution. In such a certificate was constructed via an infinite series using a construction developed in the compressed sensing literature . The terms in this series were then analyzed individually using the decoupling inequalities of de la Peña and Montgomery-Smith . Truncating the infinite series after $4$ terms gave their result. In , the authors bounded the contribution of $O(\log(n_{2}))$ terms in this series using intensive combinatorial analysis of each term. The insight in was that, when sampling observations with replacement, a dual feasible solution could be closely approximated by a modified series where each term involved the product of independent random variables. This change in the sampling model allows one to avoid decoupling inequalities and gives rise to the dramatic simplification here.

To proceed, recall again that by Proposition 3.1 it suffices to consider the scenario when the entries are sampled independently and uniformly with replacement. I will first develop the main argument of the proof assuming many conditions hold with high probability. The proof is completed by subsequently bounding probability that all of these events hold. Suppose that

Also suppose there exists a $\bm{Y}$ in the range of ${\cal R}_{\Omega}$ such that

If (4.1) holds, then for any $\bm{Z}\in\ker{{\cal R}_{\Omega}}$, ${\cal P}_{T}(\bm{Z})$ cannot be too large. Indeed, we have

and $\|{\cal R}_{\Omega}{\cal P}_{T^{\perp}}(\bm{Z})\|_{F}\leq\tfrac{8}{3}\beta^{1/2}\log(n_{2})\|{\cal P}_{T^{\perp}}(\bm{Z})\|_{F}$. Collecting these facts gives that for any $\bm{Z}\in\ker{{\cal R}_{\Omega}}$,

Now recall that $\|\bm{A}\|_{*}=\sup_{\|B\|\leq 1}\langle\bm{A},\bm{B}\rangle$. For $\bm{Z}\in\ker{\cal R}_{\Omega}$, pick $\bm{U}_{\perp}$ and $\bm{V}_{\perp}$ such that $[\bm{U},\bm{U}_{\perp}]$ and $[\bm{V},\bm{V}_{\perp}]$ are unitary matrices and that $\langle\bm{U}_{\perp}\bm{V}_{\perp}^{*},{\cal P}_{T^{\perp}}(\bm{Z})\rangle=\|{\cal P}_{T^{\perp}}(\bm{Z})\|_{*}$. Then it follows that

The first inequality holds from the variational characterization of the nuclear norm. We also used the fact that $\langle\bm{Y},\bm{Z}\rangle=0$ for all $\bm{Z}\in\ker{{\cal R}_{\Omega}}$. Thus, if a $\bm{Y}$ exists obeying (4.2), we have that for any $\bm{X}$ obeying ${\cal R}_{\Omega}(\bm{X}-\bm{M})=\bm{0}$, $\|\bm{X}\|_{*}>\|\bm{M}\|_{*}$. That is, any if $\bm{X}$ has $M_{ab}=X_{ab}$ for all $(a,b)\in\Omega$, $\bm{X}$ has strictly larger nuclear norm than $\bm{M}$, and hence $\bm{M}$ is the unique minimizer of (1.3). The remainder of the proof shows that such a $\bm{Y}$ exists with high probability.

To this end, partition $1,\ldots,m$ into $p$ partitions of size $q$. By assumption, we may choose

Let $\Omega_{j}$ denote the set of indices corresponding to the $j$th partition. Note that each of these partitions are independent of one another when the indices are sampled with replacement. Assume that

for all $k$. Define $\bm{W}_{0}=\bm{U}\bm{V}^{*}$ and set $\bm{Y}_{k}=\frac{n_{1}n_{2}}{q}\sum_{j=1}^{k}{\cal R}_{\Omega_{j}}(\bm{W}_{j-1})$, $\bm{W}_{k}=\bm{U}\bm{V}^{*}-{\cal P}_{T}(\bm{Y}_{k})$ for $k=1,\ldots,p$. Then

and it follows that $\|\bm{W}_{k}\|_{F}\leq 2^{-k}\|\bm{W}_{0}\|_{F}=2^{-k}\sqrt{r}$. Since $p\geq\tfrac{3}{4}\log(2n_{2})\geq\tfrac{1}{2}\log_{2}(2n_{2})=\log_{2}\sqrt{2n_{2}}$, then $\bm{Y}=\bm{Y}_{p}$ will satisfy the first inequality of (4.2). Also suppose that

To see that $\|{\cal P}_{T^{\perp}}(\bm{Y}_{p})\|\leq\frac{1}{2}$ when (4.4) and (4.5) hold, observe $\|\bm{W}_{k}\|_{\infty}\leq 2^{-k}\|\bm{U}\bm{V}^{*}\|_{\infty}$, and it follows that

since $q>\tfrac{128}{3}\mu_{1}^{2}rn_{2}\beta\log(n_{2})$. The first inequality follows from the triangle inequality. The second line follows because $\bm{W}_{j-1}\in T$ for all $j$. The third line follows because, for any $\bm{Z}$,

The fourth line applies (4.5). The next line follows from (4.4). The final line follows from the assumption A1.

All that remains is to bound the probability that all of the invoked events hold. With $m$ satisfying the bound in the main theorem statement, the first inequality in (4.1) fails to hold with probability at most $2n_{2}^{2-2\beta}$ by Theorem 3.4, and the second inequality fails to hold with probability at most $n_{2}^{2-2\beta^{1/2}}$ by Proposition 3.3. For all $k$, (4.3) fails to hold with probability at most $2n_{2}^{2-2\beta}$, (4.4) fails to hold with probability at most $2n_{2}^{2-2\beta}$, and (4.5) fails to hold with probability at most $(n_{1}+n_{2})^{1-2\beta}$. Summing these all together, all of the events hold with probability at least

by the union bound. This completes the proof.

Discussion and Conclusions

The results proven here are nearly optimal, but small improvements can possibly be made. The numerical constant $32$ in the statement of the theorem may be reducible by more clever bookkeeping, and it may be possible to derive a linear dependence on the logarithm of the matrix dimensions. But further reduction is not possible because of the necessary conditions provided by Candès and Tao. One minor improvement that could be made would be to remove the assumption A1. For instance, while $\mu_{1}$ is known to be small in most of the models of low rank matrices that have been analyzed, no one has shown that an assumption of the form A1 is necessary for completion. Nonetheless, all prior results on matrix completion have imposed an assumption like A1 , and it would be interesting to see if it can be removed as a requirement, or if it is somehow necessary.

Surprisingly, the simplicity of the argument presented here mostly arises from the abandonment of Bernoulli sampling in favor of sampling with replacement. It would be of interest to review results investigating noise robustness of matrix completion or deconvolution of sparse and low rank matrices to see if results can be improved by appealing to sampling with replacement. Furthermore, since much of the work on rank minimization and matrix completion borrows tools from the compressed sensing community, it is of interest to revisit this related body of work and to see if proofs can be simplified or bounds can be improved there as well. The noncommutative versions of Chernoff and Bernstein’ s Inequalities may be useful throughout machine learning and statistical signal processing, and a fruitful line of inquiry would examine how to apply these tools from quantum information to the study of classical signals and systems.

B.R. would like to thank Aram Harrow for introducing him to the operator Chernoff bound and many helpful clarifying conversations, Silvia Gandy for pointing out several typos in the original version of this manuscript, and Rob Nowak, Ali Rahimi, and Stephen Wright for many fruitful discussions about this paper.

References

Appendix A Operator Chernoff Bounds

In this section, I present a proof of 3.2, and also provide new proofs of some probability bounds from quantum information theory. To review, a symmetric matrix $\bm{A}$ is positive semidefinite if all of its eigenvalues are nonnegative. If $\bm{A}$ and $\bm{B}$ are positive semidefinite matrices, $\bm{A}\preceq\bm{B}$ means $\bm{B}-\bm{A}$ is positive semidefinite. For square matrices $\bm{A}$, the matrix exponential will be denoted $\exp(\bm{A})$ and is given by the power series

The following theorem is a generalization of Markov’s inequality originally proven in . My proof closely follows the standard proof of the traditional Markov inequality, and does not rely on discrete summations.

Let $\bm{X}$ be a random positive semidefinite matrix and $\bm{A}$ a fixed positive definite matrix. Then

Proof Note that if $\bm{X}\not\preceq\bm{A}$, then $\bm{A}^{-1/2}\bm{X}\bm{A}^{-1/2}\not\preceq\bm{I}$, and hence $\|\bm{A}^{-1/2}\bm{X}\bm{A}^{-1/2}\|>1$. Let $I_{\bm{X}\not\preceq\bm{A}}$ denote the indicator of the event $\bm{X}\not\preceq\bm{A}$. Then $I_{\bm{X}\not\preceq\bm{A}}\leq\operatorname{Tr}(\bm{A}^{-1/2}\bm{X}\bm{A}^{-1/2})$ as the right hand side is always nonnegative, and, if the left hand side equals $1$, the trace of the right hand side must exceed the norm of the right hand side which is greater than $1$. Thus we have

where the last equality follows from the linearity and cyclic properties of the trace.

Next I will derive a noncommutative version of the Chernoff bound. This was also proven in for i.i.d. matrices. The version stated here is more general in that the random matrices need not be identically distributed, but the proof is essentially the same.

Proof The proof relies on an estimate from statistical physics which is stated here without proof.

For any symmetric matrices $\bm{A}$ and $\bm{B}$,

Much like the proof of the standard Chernoff bound, the theorem now follows from a long chain of inequalities.

Here, the first three lines follow from standard properties of the semidefinite ordering. The fourth line invokes the Operator Markov Inequality. The sixth line follows from the Golden-Thompson inequality. The seventh line follows from independence of the $\bm{X}_{k}$. The eighth line follows because for positive definite matrices $\operatorname{Tr}(\bm{A}\bm{B})\leq\operatorname{Tr}(\bm{A})\|\bm{B}\|$. This is just another statement of the duality between the nuclear and operator norms. The ninth line iteratively repeats the previous two steps. The final line follows because for a positive definite matrix $\bm{A}$, $\operatorname{Tr}(\bm{A})$ is the sum of the eigenvalues of $\bm{A}$, and all of the eigenvalues are at most $\|\bm{A}\|$.

Let us now turn to proving the Noncommutative Bernstein Inequality presented in Section 3. The authors in proposed a similar inequality for symmetric i.i.d. random matrices with a slightly worse constant. The proof here is more general and follows the standard derivation of Bernstein’s inequality.

Then $\bm{Y}_{k}$ are symmetric random variables, and for all $k$

Moreover, the maximum singular value of $\sum_{k=1}^{L}\bm{X}_{k}$ is equal to the maximum eigenvalue of $\sum_{k=1}^{L}\bm{Y}_{k}$. By Theorem A.2, we have for all $\lambda>0$

For each $k$, let $\bm{Y}_{k}=\bm{U}_{k}\bm{\Lambda}_{k}\bm{U}_{k}^{*}$ be an eigenvalue decomposition, where $\bm{\Lambda}_{k}$ is the diagonal matrix of the eigenvalues of $\bm{Y}_{k}$. In turn, it follows that for $s>0$

This final expression is now just a real number, and only has to be minimized as a function of $\lambda$. The theorem now follows by algebraic manipulation: the right hand side is minimized by setting $\lambda=\frac{1}{M}\log(1+\frac{tLM}{\sum_{k=1}^{L}\rho_{k}^{2}})$, then basic approximations can be employed to complete the argument (see, for example , lectures 4 and 5).