Exact Matrix Completion via Convex Optimization

Introduction

In many practical problems of interest, one would like to recover a matrix from a sampling of its entries. As a motivating example, consider the task of inferring answers in a partially filled out survey. That is, suppose that questions are being asked to a collection of individuals. Then we can form a matrix where the rows index each individual and the columns index the questions. We collect data to fill out this table but unfortunately, many questions are left unanswered. Is it possible to make an educated guess about what the missing answers should be? How can one make such a guess? Formally, we may view this problem as follows. We are interested in recovering a data matrix $\bm{M}$ with $n_{1}$ rows and $n_{2}$ columns but only get to observe a number $m$ of its entries which is comparably much smaller than $n_{1}n_{2}$, the total number of entries. Can one recover the matrix $\bm{M}$ from $m$ of its entries? In general, everyone would agree that this is impossible without some additional information.

In many instances, however, the matrix we wish to recover is known to be structured in the sense that it is low-rank or approximately low-rank. (We recall for completeness that a matrix with $n_{1}$ rows and $n_{2}$ columns has rank $r$ if its rows or columns span an $r$-dimensional space.) Below are two examples of practical scenarios where one would like to be able to recover a low-rank matrix from a sampling of its entries.

The Netflix problem. In the area of recommender systems, users submit ratings on a subset of entries in a database, and the vendor provides recommendations based on the user’s preferences . Because users only rate a few items, one would like to infer their preference for unrated items.

A special instance of this problem is the now famous Netflix problem . Users (rows of the data matrix) are given the opportunity to rate movies (columns of the data matrix) but users typically rate only very few movies so that there are very few scattered observed entries of this data matrix. Yet one would like to complete this matrix so that the vendor (here Netflix) might recommend titles that any particular user is likely to be willing to order. In this case, the data matrix of all user-ratings may be approximately low-rank because it is commonly believed that only a few factors contribute to an individual’s tastes or preferences.

Triangulation from incomplete data. Suppose we are given partial information about the distances between objects and would like to reconstruct the low-dimensional geometry describing their locations. For example, we may have a network of low-power wirelessly networked sensors scattered randomly across a region. Suppose each sensor only has the ability to construct distance estimates based on signal strength readings from its nearest fellow sensors. From these noisy distance estimates, we can form a partially observed distance matrix. We can then estimate the true distance matrix whose rank will be equal to two if the sensors are located in a plane or three if they are located in three dimensional space . In this case, we only need to observe a few distances per node to have enough information to reconstruct the positions of the objects.

These examples are of course far from exhaustive and there are many other problems which fall in this general category. For instance, we may have some very limited information about a covariance matrix of interest. Yet, this covariance matrix may be low-rank or approximately low-rank because the variables only depend upon a comparably smaller number of factors.

Suppose for simplicity that we wish to recover a square $n\times n$ matrix $\bm{M}$ of rank $r$.We emphasize that there is nothing special about $\bm{M}$ being square and all of our discussion would apply to arbitrary rectangular matrices as well. The advantage of focusing on square matrices is a simplified exposition and reduction in the number of parameters of which we need to keep track. Such a matrix $\bm{M}$ can be represented by $n^{2}$ numbers, but it only has $(2n-r)r$ degrees of freedom. This fact can be revealed by counting parameters in the singular value decomposition (the number of degrees of freedom associated with the description of the singular values and of the left and right singular vectors). When the rank is small, this is considerably smaller than $n^{2}$. For instance, when $\bm{M}$ encodes a 10-dimensional phenomenon, then the number of degrees of freedom is about $20\,n$ offering a reduction in dimensionality by a factor about equal to $n/20$. When $n$ is large (e.g. in the thousands or millions), the data matrix carries much less information than its ambient dimension suggests. The problem is now whether it is possible to recover this matrix from a sampling of its entries without having to probe all the $n^{2}$ entries, or more generally collect $n^{2}$ or more measurements about $\bm{M}$.

In general, one cannot hope to be able to recover a low-rank matrix from a sample of its entries. Consider the rank-1 matrix $\bm{M}$ equal to

where here and throughout, $\bm{e}_{i}$ is the $i$th canonical basis vector in Euclidean space (the vector with all entries equal to 0 but the $i$th equal to 1). This matrix has a 1 in the top-right corner and all the other entries are 0. Clearly this matrix cannot be recovered from a sampling of its entries unless we pretty much see all the entries. The reason is that for most sampling sets, we would only get to see zeros so that we would have no way of guessing that the matrix is not zero. For instance, if we were to see 90% of the entries selected at random, then 10% of the time we would only get to see zeroes.

It is therefore impossible to recover all low-rank matrices from a set of sampled entries but can one recover most of them? To investigate this issue, we introduce a simple model of low-rank matrices. Consider the singular value decomposition (SVD) of a matrix $\bm{M}$

where the $\bm{u}_{k}$’s and $\bm{v}_{k}$’s are the left and right singular vectors, and the $\sigma_{k}$’s are the singular values (the roots of the eigenvalues of $\bm{M}^{*}\bm{M}$). Then we could think of a generic low-rank matrix as follows: the family $\{\bm{u}_{k}\}_{1\leq k\leq r}$ is selected uniformly at random among all families of $r$ orthonormal vectors, and similarly for the the family $\{\bm{v}_{k}\}_{1\leq k\leq r}$. The two families may or may not be independent of each other. We make no assumptions about the singular values $\sigma_{k}$. In the sequel, we will refer to this model as the random orthogonal model. This model is convenient in the sense that it is both very concrete and simple, and useful in the sense that it will help us fix the main ideas. In the sequel, however, we will consider far more general models. The question for now is whether or not one can recover such a generic matrix from a sampling of its entries.

1.2 Which sampling sets?

Then if we do not have samples from the first row for example, one could never guess the value of the first component $x_{1}$, by any method whatsoever; no information about $x_{1}$ is observed. There is of course nothing special about the first row and this argument extends to any row or column. To have any hope of recovering an unknown matrix, one needs at least one observation per row and one observation per column.

We have just seen that if the sampling is adversarial, e.g. one observes all of the entries of $\bm{M}$ but those in the first row, then one would not even be able to recover matrices of rank $1$. But what happens for most sampling sets? Can one recover a low-rank matrix from almost all sampling sets of cardinality $m$? Formally, suppose that the set $\Omega$ of locations corresponding to the observed entries ($(i,j)\in\Omega$ if $M_{ij}$ is observed) is a set of cardinality $m$ sampled uniformly at random. Then can one recover a generic low-rank matrix $M$, perhaps with very large probability, from the knowledge of the value of its entries in the set $\Omega$?

1.3 Which algorithm?

If the number of measurements is sufficiently large, and if the entries are sufficiently uniformly distributed as above, one might hope that there is only one low-rank matrix with these entries. If this were true, one would want to recover the data matrix by solving the optimization problem

where $\bm{X}$ is the decision variable and $\operatorname{rank}(\bm{X})$ is equal to the rank of the matrix $\bm{X}$. The program (1.3) is a common sense approach which simply seeks the simplest explanation fitting the observed data. If there were only one low-rank object fitting the data, this would recover $\bm{M}$. This is unfortunately of little practical use because this optimization problem is not only NP-hard, but all known algorithms which provide exact solutions require time doubly exponential in the dimension $n$ of the matrix in both theory and practice .

If a matrix has rank $r$, then it has exactly $r$ nonzero singular values so that the rank function in (1.3) is simply the number of nonvanishing singular values. In this paper, we consider an alternative which minimizes the sum of the singular values over the constraint set. This sum is called the nuclear norm,

where, here and below, $\sigma_{k}(\bm{X})$ denotes the $k$th largest singular value of $\bm{X}$. The heuristic optimization is then given by

1.4 A first typical result

Our first result shows that, perhaps unexpectedly, this heuristic optimization recovers a generic $\bm{M}$ when the number of randomly sampled entries is large enough. We will prove the following:

Let $\bm{M}$ be an $n_{1}\times n_{2}$ matrix of rank $r$ sampled from the random orthogonal model, and put $n=\max(n_{1},n_{2})$. Suppose we observe $m$ entries of $\bm{M}$ with locations sampled uniformly at random. Then there are numerical constants $C$ and $c$ such that if

the minimizer to the problem (1.5) is unique and equal to $\bm{M}$ with probability at least $1-cn^{-3}$; that is to say, the semidefinite program $\eqref{eq:sdp}$ recovers all the entries of $\bm{M}$ with no error. In addition, if $r\leq n^{1/5}$, then the recovery is exact with probability at least $1-cn^{-3}$ provided that

The theorem states that a surprisingly small number of entries are sufficient to complete a generic low-rank matrix. For small values of the rank, e.g. when $r=O(1)$ or $r=O(\log n)$, one only needs to see on the order of $n^{6/5}$ entries (ignoring logarithmic factors) which is considerably smaller than $n^{2}$—the total number of entries of a squared matrix. The real feat, however, is that the recovery algorithm is tractable and very concrete. Hence the contribution is twofold:

Under the hypotheses of Theorem 1.1, there is a unique low-rank matrix which is consistent with the observed entries.

Further, this matrix can be recovered by the convex optimization (1.5). In other words, for most problems, the nuclear norm relaxation is formally equivalent to the combinatorially hard rank minimization problem (1.3).

Theorem 1.1 is in fact a special instance of a far more general theorem that covers a much larger set of matrices $\bm{M}$. We describe this general class of matrices and precise recovery conditions in the next section.

2 Main results

As seen in our first example (1.1), it is impossible to recover a matrix which is equal to zero in nearly all of its entries unless we see all the entries of the matrix. To recover a low-rank matrix, this matrix cannot be in the null space of the sampling operator giving the values of a subset of the entries. Now it is easy to see that if the singular vectors of a matrix $\bm{M}$ are highly concentrated, then $\bm{M}$ could very well be in the null-space of the sampling operator. For instance consider the rank-2 symmetric matrix $\bm{M}$ given by

where the singular values are arbitrary. Then this matrix vanishes everywhere except in the top-left $2\times 2$ corner and one would basically need to see all the entries of $\bm{M}$ to be able to recover this matrix exactly by any method whatsoever. There is an endless list of examples of this sort. Hence, we arrive at the notion that, somehow, the singular vectors need to be sufficiently spread—that is, uncorrelated with the standard basis—in order to minimize the number of observations needed to recover a low-rank matrix.Both the left and right singular vectors need to be uncorrelated with the standard basis. Indeed, the matrix $\bm{e}_{1}\bm{v}^{*}$ has its first row equal to $\bm{v}$ and all the others equal to zero. Clearly, this rank-1 matrix cannot be recovered unless we basically see all of its entries. This motivates 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. We shall be primarily interested in subspace with low coherence as matrices whose column and row spaces have low coherence cannot really be in the null space of the sampling operator. For instance, we will see that the random subspaces discussed above have nearly minimal coherence.

To state our main result, we introduce two assumptions about an $n_{1}\times n_{2}$ matrix $\bm{M}$ whose SVD is given by $\bm{M}=\sum_{1\leq k\leq r}\sigma_{k}\bm{u}_{k}\bm{v}_{k}^{*}$ and with column and row spaces denoted by $U$ and $V$ respectively.

The coherences obey $\max(\mu(U),\mu(V))\leq\mu_{0}$ for some positive $\mu_{0}$.

The $n_{1}\times n_{2}$ matrix $\sum_{1\leq k\leq r}\bm{u}_{k}\bm{v}_{k}^{*}$ has a maximum entry bounded by $\mu_{1}\sqrt{r/(n_{1}n_{2})}$ in absolute value for some positive $\mu_{1}$.

The $\mu$’s above may depend on $r$ and $n_{1},n_{2}$. Moreover, note that A1 always holds with $\mu_{1}=\mu_{0}\,\sqrt{r}$ since the $(i,j)$th entry of the matrix $\sum_{1\leq k\leq r}\bm{u}_{k}\bm{v}_{k}^{*}$ is given by $\sum_{1\leq k\leq r}u_{ik}v_{jk}$ and by the Cauchy-Schwarz inequality,

Hence, for sufficiently small ranks, $\mu_{1}$ is comparable to $\mu_{0}$. As we will see in Section 2, for larger ranks, 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}$. Below we will assume that $\mu_{1}$ is greater than or equal to 1.

We are in the position to state our main result: if a matrix has row and column spaces that are incoherent with the standard basis, then nuclear norm minimization can recover this matrix from a random sampling of a small number of entries.

Let $\bm{M}$ be an $n_{1}\times n_{2}$ matrix of rank $r$ obeying A0 and A1 and put $n=\max(n_{1},n_{2})$. Suppose we observe $m$ entries of $\bm{M}$ with locations sampled uniformly at random. Then there exist constants $C$, $c$ such that if

for some $\beta>2$, then the minimizer to the problem (1.5) is unique and equal to $\bm{M}$ with probability at least $1-cn^{-\beta}$. For $r\leq\mu_{0}^{-1}n^{1/5}$ this estimate can be improved to

Theorem 1.3 asserts that if the coherence is low, few samples are required to recover $\bm{M}$. For example, if $\mu_{0}=O(1)$ and the rank is not too large, then the recovery is exact with large probability provided that

We give two illustrative examples of matrices with incoherent column and row spaces. This list is by no means exhaustive.

The first example is the random orthogonal model. For values of the rank $r$ greater than $\log n$, $\mu(U)$ and $\mu(V)$ are $O(1)$, $\mu_{1}=O(\log n)$ both with very large probability. Hence, the recovery is exact provided that $m$ obeys (1.6) or (1.7). Specializing Theorem 1.3 to these values of the parameters gives Theorem 1.1. Hence, Theorem 1.1 is a special case of our general recovery result.

The second example is more general and, in a nutshell, simply requires that the components of the singular vectors of $\bm{M}$ are small. Assume that the $\bm{u}_{j}$ and $\bm{v}_{j}$’s obey

for some value of $\mu_{B}=O(1)$. Then the maximum coherence is at most $\mu_{B}$ since $\mu(U)\leq\mu_{B}$ and $\mu(V)\leq\mu_{B}$. Further, we will see in Section 2 that ${\bf A1}$ holds most of the time with $\mu_{1}=O(\sqrt{\log n})$. Thus, for matrices with singular vectors obeying (1.12), the recovery is exact provided that $m$ obeys (1.11) for values of the rank not exceeding $\mu_{B}^{-1}n^{1/5}$.

3 Extensions

This comes up in a number of applications. As a motivating example, there has been a great deal of interest in the machine learning community in developing specialized algorithms for the multiclass and multitask learning problems (see, e.g., ). In multiclass learning, the goal is to build multiple classifiers with the same training data to distinguish between more than two categories. For example, in face recognition, one might want to classify whether an image patch corresponds to an eye, nose, or mouth. In multitask learning, we have a large set of data, but have a variety of different classification tasks, and, for each task, only partial subsets of the data are relevant. For instance, in activity recognition, we may have acquired sets of observations of multiple subjects and want to determine if each observed person is walking or running. However, a different classifier is to be learned for each individual, and it is not clear how having access to the full collection of observations can improve classification performance. Multitask learning aims precisely to take advantage of the access to the full database to improve performance on the individual tasks.

In the abstract formulation of this problem for linear classifiers, we have $K$ classes to distinguish and are given training examples $\bm{f}_{1},\ldots,\bm{f}_{n}$. For each example, we are given partial labeling information about which classes it belongs or does not belong to. That is, for each example $\bm{f}_{j}$ and class $k$, we may either be told that $\bm{f}_{j}$ belongs to class $k$, be told $\bm{f}_{j}$ does not belong to class $k$, or provided no information about the membership of $\bm{f}_{j}$ to class $k$. For each class $1\leq k\leq K$, we would like to produce a linear function $\bm{w}_{k}$ such that $\bm{w}_{k}^{*}\bm{f}_{i}>0$ if $\bm{f}_{i}$ belongs to class $k$ and $\bm{w}_{k}^{*}\bm{f}_{i}<0$ otherwise. Formally, we can search for the vector $\bm{w}_{k}$ that satisfies the equality constraints $\bm{w}_{k}^{*}\bm{f}_{i}=y_{ik}$ where $y_{ik}=1$ if we are told that $\bm{f}_{i}$ belongs to class $k$, $y_{ik}=-1$ if we are told that $\bm{f}_{i}$ does not belong to class $k$, and $y_{ik}$ unconstrained if we are not provided information. A common hypothesis in the multitask setting is that the $\bm{w}_{k}$ corresponding to each of the classes together span a very low dimensional subspace with dimension significantly smaller than $K$ . That is, the basic assumption is that

is low-rank. Hence, the multiclass learning problem can be cast as (1.13) with observations of the form $\bm{f}_{i}^{*}\bm{W}\bm{e}_{j}$.

To see that our theorem provides conditions under which (1.13) can be solved via nuclear norm minimization, note that there exist unitary transformations $\bm{F}$ and $\bm{G}$ such that $\bm{e}_{j}=\bm{F}\bm{f}_{j}$ and $\bm{e}_{j}=\bm{G}\bm{g}_{j}$ for each $j=1,\ldots,n$. Hence,

Then if the conditions of Theorem 1.3 hold for the matrix $\bm{F}\bm{X}\bm{G}^{*}$, it is immediate that nuclear norm minimization finds the unique optimal solution of (1.13) when we are provided a large enough random collection of the inner products $\bm{f}_{i}^{*}\bm{M}\bm{g}_{j}$. In other words, all that is needed is that the column and row spaces of $\bm{M}$ be respectively incoherent with the basis $(\bm{f}_{i})$ and $(\bm{g}_{i})$.

From this perspective, we additionally remark that our results likely extend to the case where one observes a small number of arbitrary linear functionals of a hidden matrix $\bm{M}$. Set $N=n^{2}$ and $\bm{A}_{1},\ldots,\bm{A}_{N}$ be an orthonormal basis for the linear space of $n\times n$ matrices with the usual inner product $\langle\bm{X},\bm{Y}\rangle=\operatorname{trace}(\bm{X}^{*}\bm{Y})$. Then we expect our results should also apply to the rank minimization problem

where $\Omega\subset\{1,\ldots,N\}$ is selected uniformly at random. In fact, (1.14) is (1.3) when the orthobasis is the canonical basis $(\bm{e}_{i}\bm{e}_{j}^{*})_{1\leq i,j\leq n}$. Here, those low-rank matrices which have small inner product with all the basis elements $\bm{A}_{k}$ may be recoverable by nuclear norm minimization. To avoid unnecessary confusion and notational clutter, we leave this general low-rank recovery problem for future work.

4 Connections, alternatives and prior art

Nuclear norm minimization is a recent heuristic introduced by Fazel in , and is an extension of the trace heuristic often used by the control community, see e.g. . Indeed, when the matrix variable is symmetric and positive semidefinite, the nuclear norm of $\bm{X}$ is the sum of the (nonnegative) eigenvalues and thus equal to the trace of $\bm{X}$. Hence, for positive semidefinite unknowns, (1.5) would simply minimize the trace over the constraint set:

This is a semidefinite program. Even for the general matrix $\bm{M}$ which may not be positive definite or even symmetric, the nuclear norm heuristic can be formulated in terms of semidefinite programming as, for instance, the program (1.5) is equivalent to

with optimization variables $\bm{X}$, $\bm{W}_{1}$ and $\bm{W}_{2}$, (see, e.g., ). There are many efficient algorithms and high-quality software available for solving these types of problems.

From this viewpoint, the results in this paper greatly extend the theory of compressed sensing by showing that other types of interesting objects or structures, beyond sparse signals and images, can be recovered from a limited set of measurements. Moreover, the techniques for proving our main results build upon ideas from the compressed sensing literature together with probabilistic tools such as the powerful techniques of Bourgain and of Rudelson for bounding norms of operators between Banach spaces.

Our notion of incoherence generalizes the concept of the same name in compressive sampling. Notably, in , the authors introduce the notion of the incoherence of a unitary transformation. Letting $\bm{U}$ be an $n\times n$ unitary matrix, the coherence of $\bm{U}$ is given by

This quantity ranges in values from $1$ for a unitary transformation whose entries all have the same magnitude to $n$ for the identity matrix. Using this notion, showed that with high probability, a $k$-sparse signal could be recovered via linear programming from the observation of the inner product of the signal with $m=\Omega(\mu(\bm{U})k\,\log n)$ randomly selected columns of the matrix $\bm{U}$. This result provided a generalization of the celebrated results about partial Fourier observations described in , a special case where $\mu(\bm{U})=1$. This paper generalizes the notion of incoherence to problems beyond the setting of sparse signal recovery.

In , the authors studied the nuclear norm heuristic applied to a related problem where partial information about a matrix $\bm{M}$ is available from $m$ equations of the form

where for each $k$, $\{A^{(k)}_{ij}\}_{ij}$ is an i.i.d. sequence of Gaussian or Bernoulli random variables and the sequences $\{\bm{A}^{(k)}\}$ are also independent from each other (the sequences $\{\bm{A}^{(k)}\}$ and $\{b_{k}\}$ are available to the analyst). Building on the concept of restricted isometry introduced in in the context of sparse signal recovery, establishes the first sufficient conditions for which the nuclear norm heuristic returns the minimum rank element in the constraint set. They prove that the heuristic succeeds with large probability whenever the number $m$ of available measurements is greater than a constant times $2nr\log n$ for $n\times n$ matrices. Although this is an interesting result, a serious impediment to this approach is that one needs to essentially measure random projections of the unknown data matrix—a situation which unfortunately does not commonly arise in practice. Further, the measurements in (1.15) give some information about all the entries of $\bm{M}$ whereas in our problem, information about most of the entries is simply not available. In particular, the results and techniques introduced in do not begin to address the matrix completion problem of interest to us in this paper. As a consequence, our methods are completely different; for example, they do not rely on any notions of restricted isometry. Instead, as we discuss below, we prove the existence of a Lagrange multiplier for the optimization (1.5) that certifies the unique optimal solution is precisely the matrix that we wish to recover.

Finally, we would like to briefly discuss the possibility of other recovery algorithms when the sampling happens to be chosen in a very special fashion. For example, suppose that $\bm{M}$ is generic and that we precisely observe every entry in the first $r$ rows and columns of the matrix. Write $\bm{M}$ in block form as

with $\bm{M}_{11}$ an $r\times r$ matrix. In the special case that $\bm{M}_{11}$ is invertible and $\bm{M}$ has rank $r$, then it is easy to verify that $\bm{M}_{22}=\bm{M}_{21}\bm{M}_{11}^{-1}\bm{M}_{12}$. One can prove this identity by forming the SVD of $\bm{M}$, for example. That is, if $\bm{M}$ is generic, and the upper $r\times r$ block is invertible, and we observe every entry in the first $r$ rows and columns, we can recover $\bm{M}$. This result immediately generalizes to the case where one observes precisely $r$ rows and $r$ columns and the $r\times r$ matrix at the intersection of the observed rows and columns is invertible. However, this scheme has many practical drawbacks that stand in the way of a generalization to a completion algorithm from a general set of entries. First, if we miss any entry in these rows or columns, we cannot recover $\bm{M}$, nor can we leverage any information provided by entries of $\bm{M}_{22}$. Second, if the matrix has rank less than $r$, and we observe $r$ rows and columns, a combinatorial search to find the collection that has an invertible square sub-block is required. Moreover, because of the matrix inversion, the algorithm is rather fragile to noise in the entries.

5 Notations and organization of the paper

The paper is organized as follows. We first argue in Section 2 that the random orthogonal model and, more generally, matrices with incoherent column and row spaces obey the assumptions of the general Theorem 1.3. To prove Theorem 1.3, we first establish sufficient conditions which guarantee that the true low-rank matrix $\bm{M}$ is the unique solution to (1.5) in Section 3. One of these conditions is the existence of a dual vector obeying two crucial properties. Section 4 constructs such a dual vector and provides the overall architecture of the proof which shows that, indeed, this vector obeys the desired properties provided that the number of measurements is sufficiently large. Surprisingly, as explored in Section 5, the existence of a dual vector certifying that $\bm{M}$ is unique is related to some problems in random graph theory including “the coupon collector’s problem.” Following this discussion, we prove our main result via several intermediate results which are all proven in Section 6. Section 7 introduces numerical experiments showing that matrix completion based on nuclear norm minimization works well in practice. Section 8 closes the paper with a short summary of our findings, a discussion of important extensions and improvements. In particular, we will discuss possible ways of improving the 1.2 exponent in (1.10) so that it gets closer to 1. Finally, the Appendix provides proofs of auxiliary lemmas supporting our main argument.

Further, we will also manipulate linear transformation which acts on matrices and will use caligraphic letters for these operators as in ${\cal A}(\bm{X})$. In particular, the identity operator will be denoted by $\mathcal{I}$. The only norm we will consider for these operators is their spectral norm (the top singular value) denoted by $\|{\cal A}\|=\sup_{\bm{X}:\|\bm{X}\|_{F}\leq 1}\,\|{\cal A}(\bm{X})\|_{F}$.

Which matrices are incoherent?

In this section we restrict our attention to square $n\times n$ matrices, but the extension to rectangular $n_{1}\times n_{2}$ matrices immediately follows by setting $n=\max(n_{1},n_{2})$.

Almost all $n\times n$ matrices $\bm{M}$ with singular vectors $\{\bm{u}_{k}\}_{1\leq k\leq r}$ and $\{\bm{v}_{k}\}_{1\leq k\leq r}$ obeying the size property (1.12) also satisfy the assumptions A0 and A1 with $\mu_{0}=\mu_{B}$, $\mu_{1}=C\mu_{B}\sqrt{\log n}$ for some positive constant $C$. As mentioned above, A0 holds automatically, but, observe that A1 would not hold with a small value of $\mu_{1}$ if two rows of the matrices $[\bm{u}_{1},\ldots,\bm{u}_{r}]$ and $[\bm{v}_{1},\ldots,\bm{v}_{r}]$ are identical with all entries of magnitude $\sqrt{\mu_{B}/n}$ since it is not hard to see that in this case

Certainly, this example is constructed in a very special way, and should occur infrequently. We now show that it is generically unlikely.

where $\{\epsilon_{k}\}_{1\leq k\leq r}$ is an arbitrary sign sequence. For almost all choices of sign sequences, A1 is satisfied with $\mu_{1}=O(\mu_{B}\sqrt{\log n})$. Indeed, if one selects the signs uniformly at random, then for each $\beta>0$,

This is of interest because suppose the low-rank matrix we wish to recover is of the form

with scalars $\lambda_{k}$. Since the vectors $\{\bm{u}_{k}\}$ and $\{\bm{v}_{k}\}$ are orthogonal, the singular values of $\bm{M}$ are given by $|\lambda_{k}|$ and the singular vectors are given by $\textrm{sgn}(\lambda_{k})\bm{u}_{k}$ and $\bm{v}_{k}$ for $k=1,\ldots,r$. Hence, in this model A1 concerns the maximum entry of the matrix given by (2.1) with $\epsilon_{k}=\textrm{sgn}(\lambda_{k})$. That is to say, for most sign patterns, the matrix of interest obeys an appropriate size condition. We emphasize here that the only thing that we assumed about the $\bm{u}_{k}$’s and $\bm{v}_{k}$’s was that they had small entries. In particular, they could be equal to each other as would be the case for a symmetric matrix.

The claim (2.2) is a simple application of Hoeffding’s inequality. The $(i,j)$th entry of (2.1) is given by

and is a sum of $r$ zero-mean independent random variables, each bounded by $\mu_{B}/n$. Therefore,

Setting $\lambda$ proportional to $\sqrt{\log n}$ and applying the union bound gives the claim.

To summarize, we say that $\bm{M}$ is sampled from the incoherent basis model if it is of the form

$\{\epsilon_{k}\}_{1\leq k\leq r}$ is a random sign sequence, and $\{\bm{u}_{k}\}_{1\leq k\leq r}$ and $\{\bm{v}_{k}\}_{1\leq k\leq r}$ have maximum entries of size at most $\sqrt{\mu_{B}/n}$.

There exist numerical constants $c$ and $C$ such that for any $\beta>0$, matrices from the incoherent basis model obey the assumption A1 with $\mu_{1}\leq C\mu_{B}\sqrt{(\beta+2)\log n}$ with probability at least $1-cn^{-\beta}$.

2 Random subspaces span incoherent subspaces

In this section, we prove that the random orthogonal model obeys the two assumptions A0 and A1 (with appropriate values for the $\mu$’s) with large probability.

Set $\bar{r}=\max(r,\log n)$. Then there exist constants $C$ and $c$ such that the random orthogonal model obeys:When $r\geq C^{\prime}(\log n)^{3}$ for some positive constant $C^{\prime}$, a better estimate is possible, namely, $\|\bm{\sum_{1\leq k\leq r}\bm{u}_{k}\bm{v}_{k}^{*}}\|_{\infty}\leq C\,\sqrt{r\log n}/n$.

$\max_{i}\|\bm{P}_{U}\bm{e}_{i}\|^{2}\leq C\,\bar{r}/n$,

$\|\sum_{1\leq k\leq r}\bm{u}_{k}\bm{v}_{k}^{*}\|_{\infty}\leq C\,\log n\,\sqrt{\bar{r}}/n$.

We note that an argument similar to the following proof would give that if $C$ of the form $K\beta$ where $K$ is a fixed numerical constant, we can achieve a probability at least $1-cn^{-\beta}$ provided that $n$ is sufficiently large. To establish these facts, we make use of the standard result below .

Let $Y_{d}$ be distributed as a chi-squared random variable with $d$ degrees of freedom. Then for each $t>0$

We will use (2.5) as follows: for each $\epsilon\in(0,1)$ we have

We begin with the second assertion of Lemma 2.2 since it will imply the first as well. Observe that it follows from

that $Z_{r}\equiv\|\bm{P}_{U}\bm{e}_{i}\|^{2}$ ($a$ is fixed) is the squared Euclidean length of the first $r$ components of a unit vector uniformly distributed on the unit sphere in $n$ dimensions. Now suppose that $x_{1},x_{2},\ldots,x_{n}$ are i.i.d. $N(0,1)$. Then the distribution of a unit vector uniformly distributed on the sphere is that of $\bm{x}/\|\bm{x}\|$ and, therefore, the law of $Z_{r}$ is that of $Y_{r}/Y_{n}$, where $Y_{r}=\sum_{k\leq r}x_{k}^{2}$. Fix $\epsilon>0$ and consider the event $A_{n,\epsilon}=\{Y_{n}/n\geq 1-\epsilon\}$. For each $\lambda>0$, it follows from (2.6) that

Now pick $\epsilon=4(n^{-1}\log n)^{1/2}$, $\lambda=8\sqrt{2\log n}$ and assume that $n$ is sufficiently large so that

Assume now that $r\geq 4\log n$ (which means that $\lambda\leq 4\sqrt{2r}$). Then it follows from (2.5) that

by the union bound. Note that (2.8) establishes the first claim of the lemma (even for $r<4\log n$ since in this case $Z_{r}\leq Z_{\lceil 4\log n\rceil}$).

It remains to establish the second claim. Notice that by symmetry, $\bm{E}=\sum_{1\leq k\leq r}\bm{u}_{k}\bm{v}_{k}^{*}$ has the same distribution as

where $\{\epsilon_{k}\}$ is an independent Rademacher sequence. It then follows from Hoeffding’s inequality that conditional on $\{\bm{u}_{k}\}$ and $\{\bm{v}_{k}\}$ we have

Our previous results indicate that $\max_{ij}|v_{ij}|^{2}\leq(10\log n)/n$ with large probability and thus

Set $\bar{r}=\max(r,\log n)$. Since $\|\bm{P}_{U}\bm{e}_{i}\|^{2}\leq C\bar{r}/n$ with large probability, we have

with large probability. Hence the marginal distribution of $F_{ij}$ obeys

for some numerical constant $\gamma$. Picking $\lambda=\gamma^{\prime}\log n$ where $\gamma^{\prime}$ is a sufficiently large numerical constant gives

with large probability. Since $\bm{E}$ and $\bm{F}$ have the same distribution, the second claim follows.

The claim about the size of $\max_{ij}|v_{ij}|^{2}$ is straightforward since our techniques show that for each $\lambda>0$

since the maximum is taken over at most $4n\log n$ pairs.

Duality

With these notations, $\bm{Y}$ is a subgradient of the nuclear norm at $\bm{X}_{0}$ if and only if it is of the form

where $\bm{W}$ obeys the following two properties:

the column space of $\bm{W}$ is orthogonal to $U\equiv\operatorname{span}{(\bm{u}_{1},\ldots,\bm{u}_{r})}$, and the row space of $\bm{W}$ is orthogonal to $V\equiv\operatorname{span}{(\bm{v}_{1},\ldots,\bm{v}_{r})}$;

the spectral norm of $\bm{W}$ is less than or equal to 1.

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$. Note here that while $\bm{P}_{U}$ and $\bm{P}_{V}$ are matrices, ${\cal P}_{T}$ is a linear operator mapping matrices to matrices. We also have

where $\bm{I}_{d}$ denotes the $d\times d$ identity matrix. With these notations, $\bm{Y}\in\partial\|\bm{X}_{0}\|_{*}$ if

${\cal P}_{T}(\bm{Y})=\sum_{1\leq k\leq r}\bm{u}_{k}\bm{v}_{k}^{*}$,

and $\|{\cal P}_{T^{\perp}}\bm{Y}\|\leq 1$.

Now that we have characterized the subgradient of the nuclear norm, the lemma below gives sufficient conditions for the uniqueness of the minimizer to (1.5).

Consider a matrix $\bm{X}_{0}=\sum_{k=1}^{r}\sigma_{k}\,\bm{u}_{k}\bm{v}_{k}^{*}$ of rank $r$ which is feasible for the problem (1.5), and suppose that the following two conditions hold:

there exists a dual point $\lambda$ such that $\bm{Y}={\cal R}^{*}_{\Omega}\lambda$ obeys

the sampling operator ${\cal R}_{\Omega}$ restricted to elements in $T$ is injective.

Then $\bm{X}_{0}$ is the unique minimizer.

Before proving this result, we would like to emphasize that this lemma provides a clear strategy for proving our main result, namely, Theorem 1.3. Letting $\bm{M}=\sum_{k=1}^{r}\sigma_{k}\,\bm{u}_{k}\bm{v}_{k}^{*}$, $\bm{M}$ is the unique solution to (1.5) if the injectivity condition holds and if one can find a dual point $\lambda$ such that $\bm{Y}={\cal R}^{*}_{\Omega}\lambda$ obeys (3.6).

The proof of Lemma 3.1 uses a standard fact which states that the nuclear norm and the spectral norm are dual to one another.

For each pair $\bm{W}$ and $\bm{H}$, we have

In addition, for each $\bm{H}$, there is a $\bm{W}$ obeying $\|\bm{W}\|=1$ which achieves the equality.

A variety of proofs are available for this Lemma, and an elementary argument is sketched in . We now turn to the proof of Lemma 3.1.

Proof [of Lemma 3.1] Consider any perturbation $\bm{X}_{0}+\bm{H}$ where ${\cal R}_{\Omega}(\bm{H})=0$. Then for any $\bm{W}^{0}$ obeying (i)–(ii), $\sum_{k=1}^{r}\bm{u}_{k}\bm{v}_{k}^{*}+\bm{W}^{0}$ is a subgradient of the nuclear norm at $X_{0}$ and, therefore,

Letting $\bm{W}={\cal P}_{T^{\perp}}(\bm{Y})$, we may write $\sum_{k=1}^{r}\bm{u}_{k}\bm{v}_{k}^{*}={\cal R}^{*}_{\Omega}\lambda-\bm{W}$. Since $\|\bm{W}\|<1$ and ${\cal R}_{\Omega}(\bm{H})=0$, it then follows that

We use Lemma 3.2 and set $\bm{W}^{0}={\cal P}_{T^{\perp}}(\bm{Z})$ where $\bm{Z}$ is any matrix obeying $\|\bm{Z}\|\leq 1$ and $\langle\bm{Z},{\cal P}_{T^{\perp}}(\bm{H})\rangle=\|{\cal P}_{T^{\perp}}(\bm{H})\|_{*}$. Then $\bm{W}^{0}\in T^{\perp}$, $\|\bm{W}^{0}\|\leq 1$, and

which by assumption is strictly positive unless ${\cal P}_{T^{\perp}}(\bm{H})=0$. In other words, $\|\bm{X}_{0}+\bm{H}\|_{*}>\|\bm{X}_{0}\|_{*}$ unless ${\cal P}_{T^{\perp}}(\bm{H})=0$. Assume then that ${\cal P}_{T^{\perp}}(\bm{H})=0$ or equivalently that $\bm{H}\in T$. Then ${\cal R}_{\Omega}(\bm{H})=0$ implies that $\bm{H}=0$ by the injectivity assumption. In conclusion, $\|\bm{X}_{0}+\bm{H}\|_{*}>\|\bm{X}\|_{*}$ unless $\bm{H}=0$.

Architecture of the proof

Our strategy to prove that $\bm{M}=\sum_{1\leq k\leq r}\sigma_{k}\bm{u}_{k}\bm{v}_{k}^{*}$ is the unique minimizer to (1.5) is to construct a matrix $\bm{Y}$ which vanishes on $\Omega^{c}$ and obeys the conditions of Lemma 3.1 (and show the injectivity of the sampling operator restricted to matrices in $T$ along the way). Set ${\cal P}_{\Omega}$ to be the orthogonal projector onto the indices in $\Omega$ so that the $(i,j)$th component of ${\cal P}_{\Omega}(\bm{X})$ is equal to $X_{ij}$ if $(i,j)\in\Omega$ and zero otherwise. Our candidate $\bm{Y}$ will be the solution to

The matrix $\bm{Y}$ vanishes on $\Omega^{c}$ as otherwise it would not be an optimal solution since ${\cal P}_{\Omega}(\bm{Y})$ would obey the constraint and have a smaller Frobenius norm. Hence $\bm{Y}={\cal P}_{\Omega}(\bm{Y})$ and ${\cal P}_{T}(\bm{Y})=\sum_{k=1}^{r}\bm{u}_{k}\bm{v}_{k}^{*}$. Since the Pythagoras formula gives

minimizing the Frobenius norm of $\bm{X}$ amounts to minimizing the Frobenius norm of ${\cal P}_{T^{\perp}}(\bm{X})$ under the constraint ${\cal P}_{T}(\bm{X})=\sum_{k=1}^{r}\bm{u}_{k}\bm{v}_{k}^{*}$. Our motivation is twofold. First, the solution to the least-squares problem (4.1) has a closed form that is amenable to analysis. Second, by forcing ${\cal P}_{T^{\perp}}(\bm{Y})$ to be small in the Frobenius norm, we hope that it will be small in the spectral norm as well, and establishing that $\|{\cal P}_{T^{\perp}}(\bm{Y})\|<1$ would prove that $\bm{M}$ is the unique solution to (1.5).

To compute the solution to (4.1), we introduce the operator $\mathcal{A}_{\Omega T}$ defined by

Then, if $\mathcal{A}_{\Omega T}^{*}\mathcal{A}_{\Omega T}={\cal P}_{T}{\cal P}_{\Omega}{\cal P}_{T}$ has full rank when restricted to $T$, the minimizer to (4.1) is given by

We clarify the meaning of (4.2) to avoid any confusion. $(\mathcal{A}_{\Omega T}^{*}\mathcal{A}_{\Omega T})^{-1}(\bm{E})$ is meant to be that element $\bm{F}$ in $T$ obeying $(\mathcal{A}_{\Omega T}^{*}\mathcal{A}_{\Omega T})(\bm{F})=\bm{E}$.

To summarize the aims of our proof strategy,

Having established that $\bm{Y}$ is well-defined, we will show that

thus proving the first sufficient condition.

Instead of showing that the theorem holds when $\Omega$ is a set of size $m$ sampled uniformly at random, we prove the theorem for a subset $\Omega^{\prime}$ sampled according to the Bernoulli model. Here and below, $\{\delta_{ij}\}_{1\leq i\leq n_{1},1\leq j\leq n_{2}}$ is a sequence of independent identically distributed $0/1$ Bernoulli random variables with

2 The injectivity property

We study the injectivity of $\mathcal{A}_{\Omega T}$, which also shows that $\bm{Y}$ is well-defined. To prove this, we will show that the linear operator $p^{-1}{\cal P}_{T}({\cal P}_{\Omega}-p\mathcal{I}){\cal P}_{T}$ has small operator norm, which we recall is $\sup_{\|\bm{X}\|_{F}\leq 1}\,p^{-1}\|{\cal P}_{T}({\cal P}_{\Omega}-p\mathcal{I}){\cal P}_{T}(\bm{X})\|_{F}$.

Suppose $\Omega$ is sampled according to the Bernoulli model (4.3)–(4.4) and put $n=\max(n_{1},n_{2})$. Suppose that the coherences obey $\max(\mu(U),\mu(V))\leq\mu_{0}$. Then, there is a numerical constants $C_{R}$ such that for all $\beta>1$,

with probability at least $1-3n^{-\beta}$ provided that $C_{R}\,\sqrt{\frac{\mu_{0}\,nr(\beta\log n)}{m}}<1$.

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

Hence, ${\cal P}_{\Omega}{\cal P}_{T}(\bm{X})=\sum_{ab}\delta_{ab}\,\langle\bm{X},{\cal P}_{T}(\bm{e}_{a}\bm{e}_{b}^{*})\rangle\,\bm{e}_{a}\bm{e}_{b}^{*}$ which gives

It follows from the definition (3.5) of ${\cal P}_{T}$ that

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

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

in the spectral norm is related to Rudelson’s selection theorem . The first part of the theorem below may be found in for example, see also for a very similar statement.

There exists a constant $C^{\prime}_{R}$ such that

provided that the right-hand side is smaller than 1.

for some positive constant $\gamma^{\prime}_{0}$.

for some $C>0$ provided that the right-hand side is less than 1. The proof may be found in the cited literature, e.g. in . Hence, the first part follows from applying this result to vectors of the form ${\cal P}_{T}(\bm{e}_{a}\bm{e}_{b}^{*})$ and using the available bound on $\|{\cal P}_{T}(\bm{e}_{a}\bm{e}_{b}^{*})\|_{F}$. The second part follows from Talagrand’s concentration inequality and may be found in the Appendix.

Set $\lambda=\sqrt{\beta/\gamma^{\prime}_{0}}$ and assume that $m>(\beta/\gamma^{\prime}_{0})\mu_{0}\,nr\log n$. Then the left-hand side of (4.10) is bounded by $3n^{-\beta}$ and thus, we established that

with probability at least $1-3n^{-\beta}$. Setting $C_{R}=C^{\prime}_{R}+1/\sqrt{\gamma^{\prime}_{0}}$ finishes the proof.

Take $m$ large enough so that $C_{R}\,\sqrt{\mu_{0}\,(nr/m)\log n}\leq 1/2$. Then it follows from (4.5) that

for all $\bm{X}$ with large probability. In particular, the operator $\mathcal{A}_{\Omega T}^{*}\mathcal{A}_{\Omega T}={\cal P}_{T}{\cal P}_{\Omega}{\cal P}_{T}$ mapping $T$ onto itself is well-conditioned and hence invertible. An immediate consequence is the following:

Assume that $C_{R}\,\sqrt{\mu_{0}nr(\log n)/m}\leq 1/2$. With the same probability as in Theorem 4.1, we have

Proof We have $\|{\cal P}_{\Omega}{\cal P}_{T}(\bm{X})\|_{F}^{2}=\langle\bm{X},({\cal P}_{\Omega}{\cal P}_{T})^{*}({\cal P}_{\Omega}{\cal P}_{T})\bm{X}\rangle=\langle\bm{X},({\cal P}_{T}{\cal P}_{\Omega}{\cal P}_{T})\bm{X}\rangle$ and thus

where the inequality is due to Cauchy-Schwarz. The conclusion (4.12) follows from (4.11).

3 The size property

In this section, we explain how we will show that $\|{\cal P}_{T^{\perp}}(\bm{Y})\|<1$. This result will follow from five lemmas that we will prove in Section 6. Introduce

which obeys $\|\mathcal{H}(\bm{X})\|_{F}\leq C_{R}\,\sqrt{\mu_{0}(nr/m)\,\beta\log n}\|{\cal P}_{T}(\bm{X})\|_{F}$ with large probability because of Theorem 4.1. For any matrix $\bm{X}\in T$, $({\cal P}_{T}{\cal P}_{\Omega}{\cal P}_{T})^{-1}(\bm{X})$ can be expressed in terms of the power series

for $\mathcal{H}$ is a contraction when $m$ is sufficiently large. Since $\bm{Y}={\cal P}_{\Omega}{\cal P}_{T}({\cal P}_{T}{\cal P}_{\Omega}{\cal P}_{T})^{-1}(\sum_{1\leq k\leq r}\bm{u}_{k}\bm{v}_{k}^{*})$, ${\cal P}_{T^{\perp}}(\bm{Y})$ may be decomposed as

To bound the norm of the left-hand side, it is of course sufficient to bound the norm of the summands in the right-hand side. Taking the following five lemmas together establishes Theorem 1.3.

Fix $\beta\geq 2$ and $\lambda\geq 1$. There is a numerical constant $C_{0}$ such that if $m\geq\lambda\,\mu_{1}^{2}\,nr\beta\log n$, then

with probability at least $1-n^{-\beta}$.

Fix $\beta\geq 2$ and $\lambda\geq 1$. There are numerical constants $C_{1}$ and $c_{1}$ such that if $m\geq\lambda\,\mu_{1}\max(\sqrt{\mu_{0}},\mu_{1})\,nr\beta\log n$, then

with probability at least $1-c_{1}n^{-\beta}$.

Fix $\beta\geq 2$ and $\lambda\geq 1$. There are numerical constants $C_{2}$ and $c_{2}$ such that if $m\geq\lambda\,\mu_{0}^{4/3}\,nr^{4/3}\beta\log n$, then

with probability at least $1-c_{2}n^{-\beta}$.

Fix $\beta\geq 2$ and $\lambda\geq 1$. There are numerical constants $C_{3}$ and $c_{3}$ such that if $m\geq\lambda\mu_{0}^{2}\,nr^{2}\beta\log n$, then

with probability at least $1-c_{3}n^{-\beta}$.

Under the assumptions of Theorem 4.1, there is a numerical constant $C_{k_{0}}$ such that if $m\geq(2C_{R})^{2}\mu_{0}nr\beta\log n$, then

with probability at least $1-n^{-\beta}$.

Let us now show how we may combine these lemmas to prove our main results. Under all of the assumptions of Theorem 1.3, consider the four Lemmas 4.4, 4.5, 4.6 and 4.8, the latter applied with $k_{0}=3$. Together they imply that there are numerical constants $c$ and $C$ such that $\|{\cal P}_{T^{\perp}}(\bm{Y})\|<1$ with probability at least $1-cn^{-\beta}$ provided that the number of samples obeys

for some constant $C$. The four expressions in the maximum come from Lemmas 4.4, 4.5, 4.6 and 4.8 in this order. Now the bound (4.19) is only interesting in the range when $\mu_{0}n^{1/4}r$ is smaller than a constant times $n$ as otherwise the right-hand side is greater than $n^{2}$ (this would say that one would see all the entries in which case our claim is trivial). When $\mu_{0}r\leq n^{3/4}$, $(\mu_{0}r)^{4/3}\leq\mu_{0}n^{5/4}r$ and thus the recovery is exact provided that $m$ obeys (1.9).

For the case concerning small values of the rank, we consider all five lemmas and apply Lemma 4.8, the latter applied with $k_{0}=4$. Together they imply that $\|{\cal P}_{T^{\perp}}(\bm{Y})\|<1$ with probability at least $1-cn^{-\beta}$ provided that the number of samples obeys

for some constant $C$. The two expressions in the maximum come from Lemmas 4.7 and 4.8 in this order. The reason for this simplified formulation is that the terms $\mu_{1}^{2}$, $\mu_{0}^{1/2}\mu_{1}$ and $\mu_{0}^{4/3}r^{1/3}$ which come from Lemmas 4.4, 4.5 and 4.6 are bounded above by $\mu_{0}^{2}r$ since $\mu_{1}\leq\mu_{0}\sqrt{r}$. When $\mu_{0}r\leq n^{1/5}$, the recovery is exact provided that $m$ obeys (1.10).

Connections with Random Graph Theory

We argued in the Introduction that to have any hope of recovering an unknown matrix of rank 1 by any method whatsoever, one needs at least one observation per row and one observation per column. Sample $m$ entries uniformly at random. Viewing the row indices as bins, assign the $k$th sampled entry to the bin corresponding to its row index. Then to have any hope of recovering our matrix, all the bins need to be occupied. Quantifying how many samples are required to fill all of the bins is the famous coupon collector’s problem.

Coupon collection is also connected to the injectivity of the sampling operator ${\cal P}_{\Omega}$ restricted to elements in $T$. Suppose we sample the entries of a rank 1 matrix equal to $\bm{x}\bm{y}^{*}$ with left and right singular vectors $\bm{u}=\bm{x}/\|\bm{x}\|$ and $\bm{v}=\bm{y}/\|\bm{y}\|$ respectively and have not seen anything in the $i$th row. Then we claim that ${\cal P}_{\Omega}$ (restricted to $T$) has a nontrivial null space and thus ${\cal P}_{T}{\cal P}_{\Omega}{\cal P}_{T}$ is not invertible. Indeed, consider the matrix $\bm{e}_{i}\bm{v}^{*}$. This matrix is in $T$ and

since $\bm{e}_{i}\bm{v}^{*}$ vanishes outside of the $i$th row. The same applies to the columns as well. If we have not seen anything in column $j$, then the rank-1 matrix $\bm{u}\bm{e}_{j}^{*}\in T$ and ${\cal P}_{\Omega}(\bm{u}\bm{e}_{j}^{*})=0$. In conclusion, the invertibility of ${\cal P}_{T}{\cal P}_{\Omega}{\cal P}_{T}$ implies a complete collection.

When the entries are sampled uniformly at random, it is well known that one needs on the order of $n\log n$ samples to sample all the rows. What is interesting is that Theorem 4.1 implies that ${\cal P}_{T}{\cal P}_{\Omega}{\cal P}_{T}$ is invertible—a stronger property—when the number of samples is also on the order of $n\log n$. A particular implication of this discussion is that the logarithmic factors in Theorem 4.1 are unavoidable.

2 The injectivity property and the connectivity problem

To recover a matrix of rank 1, one needs much more than at least one observation per row and column. Let $R$ be the set of row indices, $1\leq i\leq n$, and $C$ be the set of column indices, $1\leq j\leq n$, and consider the bipartite graph connecting vertices $i\in R$ to vertices $j\in C$ if and only if $(i,j)\in\Omega$, i.e. the $(i,j)$th entry is observed. We claim that if this graph is not fully connected, then one cannot hope to recover a matrix of rank 1.

To see this, we let $I$ be the set of row indices and $J$ be the set of column indices in any connected component. We will assume that $I$ and $J$ are nonempty as otherwise, one is in the previously discussed situation where some rows or columns are not sampled. Consider a rank 1 matrix equal to $\bm{x}\bm{y}^{*}$ as before with singular vectors $\bm{u}=\bm{x}/\|\bm{x}\|$ and $\bm{v}=\bm{y}/\|\bm{y}\|$. Then all the information about the values of the $x_{i}$’s with $i\in I$ and of the $y_{j}$’s with $j\in J$ are given by the sampled entries connecting $I$ to $J$ since all the other observed entries connect vertices in $I^{c}$ to those in $J^{c}$. Now even if one observes all the entries $x_{i}y_{j}$ with $i\in I$ and $j\in J$, then at least the signs of $x_{i}$, $i\in I$, and of $y_{j}$, $j\in J$, would remain undetermined. Indeed, if the values $(x_{i})_{i\in I}$, $(y_{j})_{j\in J}$ are consistent with the observed entries, so are the values $(-x_{i})_{i\in I}$, $(-y_{j})_{j\in J}$. However, since the same analysis holds for the sets $I^{c}$ and $J^{c}$, there are at least two matrices consistent with the observed entries and exact matrix completion is impossible.

The connectivity of the graph is also related to the injectivity of the sampling operator ${\cal P}_{\Omega}$ restricted to elements in $T$. If the graph is not fully connected, then we claim that ${\cal P}_{\Omega}$ (restricted to $T$) has a nontrivial null space and thus ${\cal P}_{T}{\cal P}_{\Omega}{\cal P}_{T}$ is not invertible. Indeed, consider the matrix

where $a_{i}=-u_{i}$ if $i\in I$ and $a_{i}=u_{i}$ otherwise, and $b_{j}=v_{j}$ if $j\in J$ and $b_{j}=-v_{j}$ otherwise. Then this matrix is in $T$ and obeys

if $(i,j)\in I\times J$ or $(i,j)\in I^{c}\times J^{c}$. Note that on the complement, i.e. $(i,j)\in I\times J^{c}$ or $(i,j)\in I^{c}\times J$, one has $M_{ij}=2u_{i}v_{j}$ and one can show that $\bm{M}\neq 0$ unless $\bm{u}\bm{v}^{*}=0$. Since $\Omega$ is included in the union of $I\times J$ and $I^{c}\times J^{c}$, we have that ${\cal P}_{\Omega}(\bm{M})=0$. In conclusion, the invertibility of ${\cal P}_{T}{\cal P}_{\Omega}{\cal P}_{T}$ implies a fully connected graph.

When the entries are sampled uniformly at random, it is well known that one needs on the order of $n\log n$ samples to obtain a fully connected graph with large probability (see, e.g., ). Remarkably, Theorem 4.1 implies that ${\cal P}_{T}{\cal P}_{\Omega}{\cal P}_{T}$ is invertible—a stronger property—when the number of samples is also on the order of $n\log n$.

Proofs of the Critical Lemmas

In this section, we prove the five lemmas of Section 4.3. Before we begin, however, we develop a simple estimate which we will use throughout. For each pair $(a,b)$ and $(a^{\prime},b^{\prime})$, it follows from the expression of ${\cal P}_{T}(\bm{e}_{a}\bm{e}_{b}^{*})$ (4.6) that

Fix $\mu_{0}$ obeying $\mu(U)\leq\mu_{0}$ and $\mu(V)\leq\mu_{0}$ and note that

and similarly for $\langle\bm{e}_{b},\bm{P}_{V}\bm{e}_{b^{\prime}}\rangle$. Suppose that $b=b^{\prime}$ and $a\neq a^{\prime}$, then

We have a similar bound when $a=a^{\prime}$ and $b\neq b^{\prime}$ whereas when $a\neq a^{\prime}$ and $b\neq b^{\prime}$,

In short, it follows from this analysis (and from (4.8) for the case where $(a,b)=(a^{\prime},b^{\prime})$) that

which we will apply several times. A related estimate is this:

and the same is true by exchanging the role of $a$ and $b$. To see this, write

and the conclusion follows from the coherence property.

We will prove the lemmas in the case where $n_{1}=n_{2}=n$ for simplicity, i.e. in the case of square matrices of dimension $n$. The general case is treated in exactly the same way. In fact, the argument only makes use of the bounds (6.2), (6.3) (and sometimes (6.4)), and the general case is obtained by replacing $n$ with $\min(n_{1},n_{2})$.

Each of the following subsections computes the operator norm of some random variable. In each section, we denote $\bm{S}$ as the quantity whose norm we wish to analyze. We will also frequently use the notation $\bm{H}$ for some auxiliary matrix variable whose norm we will need to bound. Hence, we will reuse the same notation many times rather than introducing a dozens new names—just like in computer programming where one uses the same variable name in distinct routines.

where the equality follows from ${\cal P}_{T^{\perp}}{\cal P}_{T}=0$, and the inequality from ${\cal P}_{T}(\bm{E})=\bm{E}$ together with $\|{\cal P}_{T^{\perp}}(\bm{X})\|\leq\|\bm{X}\|$ which is valid for any matrix $\bm{X}$. Set

where $\bm{S}^{\prime}=p^{-1}\sum_{ab}(\delta^{\prime}_{ab}-p)E_{ab}\bm{e}_{a}\bm{e}_{b}^{*}$ is an independent copy of $\bm{S}$. Since $(\delta_{ab}-\delta^{\prime}_{ab})$ is symmetric, $\bm{S}-\bm{S}^{\prime}$ has the same distribution as

where $\{\epsilon_{ab}\}$ is an independent Rademacher sequence and $\bm{S}_{\epsilon}=p^{-1}\sum_{ab}\epsilon_{ab}\delta_{ab}E_{ab}\bm{e}_{a}\bm{e}_{b}^{*}$. Further, the triangle inequality gives