The Power of Convex Relaxation: Near-Optimal Matrix Completion

Introduction

Imagine we have an $n_{1}\times n_{2}$ array of realMuch of the discussion below, as well as our main results, apply also to the case of complex matrix completion, with some minor adjustments in the absolute constants; but for simplicity we restrict attention to the real case. numbers and that we are interested in knowing the value of each of the $n_{1}n_{2}$ entries in this array. Suppose, however, that we only get to see a small number of the entries so that most of the elements about which we wish information are simply missing. Is it possible from the available entries to guess the many entries that we have not seen? This problem is now known as the matrix completion problem , and comes up in a great number of applications, including the famous Netflix Prize and other similar questions in collaborative filtering . In a nutshell, collaborative filtering is the task of making automatic predictions about the interests of a user by collecting taste information from many users. Netflix is a commercial company implementing collaborative filtering, and seeks to predict users’ movie preferences from just a few ratings per user. There are many other such recommendation systems proposed by Amazon, Barnes and Noble, and Apple Inc. to name just a few. In each instance, we have a partial list about a user’s preferences for a few rated items, and would like to predict his/her preferences for all items from this and other information gleaned from many other users.

An increasingly common assumption in the field is to suppose that the unknown matrix $M$ has low rank or has approximately low rank. In a recommendation system, this makes sense because often times, only a few factors contribute to an individual’s taste. In , the authors showed that this premise radically changes the problem, making the search for solutions meaningful. Before reviewing these results, we would like to emphasize that the problem of recovering a low-rank matrix from a sample of its entries, and by extension from fewer linear functionals about the matrix, comes up in many application areas other than collaborative filtering. For instance, the completion problem also arises in computer vision. There, many pixels may be missing in digital images because of occlusion or tracking failures in a video sequence. Recovering a scene and inferring camera motion from a sequence of images is a matrix completion problem known as the structure-from-motion problem . Other examples include system identification in control , multi-class learning in data analysis , global positioning—e.g. of sensors in a network—from partial distance information , remote sensing applications in signal processing where we would like to infer a full covariance matrix from partially observed correlations , and many statistical problems involving succinct factor models.

2 Minimal sampling

This paper is concerned with the theoretical underpinnings of matrix completion and more specifically in quantifying the minimum number of entries needed to recover a matrix of rank $r$ exactly. This number generally depends on the matrix we wish to recover. For simplicity, assume that the unknown rank-$r$ matrix $M$ is $n\times n$. Then it is not hard to see that matrix completion is impossible unless the number of samples $m$ is at least $2nr-r^{2}$, as a matrix of rank $r$ depends on this many degrees of freedom. The singular value decomposition (SVD)

so that the information about $M$ is given by $\mathcal{P}_{\Omega}({M})$. The matrix $M$ can be, in principle, recovered from $\mathcal{P}_{\Omega}({M})$ if it is the unique matrix of rank less or equal to $r$ consistent with the data. In other words, if $M$ is the unique solution to

Knowing when this happens is a delicate question which shall be addressed later. For the moment, note that attempting recovery via (1.2) is not practical as rank minimization is in general an NP-hard problem for which there are no known algorithms capable of solving problems in practical time once, say, $n\geq 10$.

In , it was proved 1) that matrix completion is not as ill-posed as previously thought and 2) that exact matrix completion is possible by convex programming. The authors of proposed recovering the unknown matrix by solving the nuclear norm minimization problem

where the nuclear norm $\|X\|_{*}$ of a matrix $X$ is defined as the sum of its singular values,

(The problem (1.3) is a semidefinite program .) They proved that if $\Omega$ is sampled uniformly at random among all subset of cardinality $m$ and $M$ obeys a low coherence condition which we will review later, then with large probability, the unique solution to (1.3) is exactly $M$, provided that the number of samples obeys

(to be completely exact, there is a restriction on the range of values that $r$ can take on).

In (1.5), the number of samples per degree of freedom is not logarithmic or polylogarithmic in the dimension, and one would like to know whether better results approaching the $nr\log n$ limit are possible. This paper provides a positive answer. In details, this work develops many useful matrix models for which nuclear norm minimization is guaranteed to succeed as soon as the number of entries is of the form $nr\text{polylog}(n)$.

3 Main results

A contribution of this paper is to develop simple hypotheses about the matrix $M$ which makes it recoverable by semidefinite programming from nearly minimally sampled entries. To state our assumptions, we recall the SVD of $M$ (1.1) and denote by $P_{U}$ (resp. $P_{V}$) the orthogonal projections onto the column (resp. row) space of $M$; i.e. the span of the left (resp. right) singular vectors. Note that

We observe that $E$ interacts well with $P_{U}$ and $P_{V}$, in particular obeying the identities

One can view $E$ as a sort of matrix-valued “sign pattern” for $M$ (compare (1.7) with (1.1)), and is also closely related to the subgradient $\partial\|M\|_{*}$ of the nuclear norm at $M$ (see (3.2)).

It is clear that some assumptions on the singular vectors $u_{i},v_{i}$ (or on the spaces $U,V$) is needed in order to have a hope of efficient matrix completion. For instance, if $u_{1}$ and $v_{1}$ are Kronecker delta functions at positions $i,j$ respectively, then the singular value $\sigma_{1}$ can only be recovered if one actually samples the $(i,j)$ coordinate, which is only likely if one is sampling a significant fraction of the entire matrix. Thus we need the vectors $u_{i},v_{i}$ to be “spread out” or “incoherent” in some sense. In our arguments, it will be convenient to phrase this incoherence assumptions using the projection matrices $P_{U},P_{V}$ and the sign pattern matrix $E$. More precisely, our assumptions are as follows.

There exists $\mu_{1}>0$ such that for all pairs $(a,a^{\prime})\in[n_{1}]\times[n_{1}]$ and $(b,b^{\prime})\in[n_{2}]\times[n_{2}]$,

There exists $\mu_{2}>0$ such that for all $(a,b)\in[n_{1}]\times[n_{2}]$,

We will say that the matrix $M$ obey the strong incoherence property with parameter $\mu$ if one can take $\mu_{1}$ and $\mu_{2}$ both less than equal to $\mu$. (This property is related to, but slightly different from, the incoherence property, which will be discussed in Section 1.6.1.)

Remark. Our assumptions only involve the singular vectors $u_{1},\ldots,u_{r},v_{1},\ldots,v_{r}$ of $M$; the singular values $\sigma_{1},\ldots,\sigma_{r}$ are completely unconstrained. This lack of dependence on the singular values is a consequence of the geometry of the nuclear norm (and in particular, the fact that the subgradient $\partial\|X\|_{*}$ of this norm is independent of the singular values, see (3.2)).

It is not hard to see that $\mu$ must be greater than 1. For instance, (1.9) implies

which forces $\mu_{2}\geq 1$. The Frobenius norm identities

and (1.8a), (1.8b) also place a similar lower bound on $\mu_{1}$.

We will show that 1) matrices obeying the strong incoherence property with a small value of the parameter $\mu$ can be recovered from fewer entries and that 2) many matrices of interest obey the strong incoherence property with a small $\mu$. We will shortly develop three models, the uniformly bounded orthogonal model, the low-rank low-coherence model, and the random orthogonal model which all illustrate the point that if the singular vectors of $M$ are “spread out” in the sense that their amplitudes all have about the same size, then the parameter $\mu$ is low. In some sense, “most” low-rank matrices obey the strong incoherence property with $\mu=O(\sqrt{\log n})$, where $n=\max(n_{1},n_{2})$. Here, $O(\cdot)$ is the standard asymptotic notation, which is reviewed in Section 1.8.

Our first matrix completion result is as follows.

then $M$ is the unique solution to (1.3) with probability at least $1-n^{-3}$. In other words: with high probability, nuclear-norm minimization recovers all the entries of ${M}$ with no error.

This result is noteworthy for two reasons. The first is that the matrix model is deterministic and only needs the strong incoherence assumption. The second is more substantial. Consider the class of bounded rank matrices obeying $\mu=O(1)$. We shall see that no method whatsoever can recover those matrices unless the number of entries obeys $m\geq c_{0}\,n\log n$ for some positive numerical constant $c_{0}$; this is the information theoretic limit. Thus Theorem 1.1 asserts that exact recovery by nuclear-norm minimization occurs nearly as soon as it is information theoretically possible. Indeed, if the number of samples is slightly larger, by a logarithmic factor, than the information theoretic limit, then (1.3) fills in the missing entries with no error.

We stated Theorem 1.1 for bounded ranks, but our proof gives a result for all values of $r$. Indeed, the argument will establish that the recovery is exact with high probability provided that

When $r=O(1)$, this is Theorem 1.1. We will prove a stronger and near-optimal result below (Theorem 1.2) in which we replace the quadratic dependence on $r$ with linear dependence. The reason why we state Theorem 1.1 first is that its proof is somewhat simpler than that of Theorem 1.2, and we hope that it will provide the reader with a useful lead-in to the claims and proof of our main result.

Under the same hypotheses as in Theorem 1.1, there is a numerical constant $C$ such that if

$M$ is the unique solution to (1.3) with probability at least $1-n^{-3}$.

This result is general and nonasymptotic.

The proof of Theorems 1.1, 1.2 will occupy the bulk of the paper, starting at Section 3.

4 A surprise

We find it unexpected that nuclear norm-minimization works so well, for reasons we now pause to discuss. For simplicity, consider matrices with a strong incoherence parameter $\mu$ polylogarithmic in the dimension. We know that for the rank minimization program (1.2) to succeed, or equivalently for the problem to be well posed, the number of samples must exceed a constant times $nr\log n$. However, Theorem 1.2 proves that the convex relaxation is rigorously exact nearly as soon as our problem has a unique low-rank solution. The surprise here is that admittedly, there is a priori no good reason to suspect that convex relaxation might work so well. There is a priori no good reason to suspect that the gap between what combinatorial and convex optimization can do is this small. In this sense, we find these findings a little unexpected.

5 Model matrices

We now discuss model matrices which obey the conditions (1.8) and (1.9) for small values of the strong incoherence parameter $\mu$. For simplicity we restrict attention to the square matrix case $n_{1}=n_{2}=n$.

In this section we shall show, roughly speaking, that almost all $n\times n$ matrices $M$ with singular vectors obeying the size property

with $\mu_{B}=O(1)$ also satisfy the assumptions A1 and A2 with $\mu_{1},\mu_{2}=O(\sqrt{\log n})$. This justifies our earlier claim that when the singular vectors are spread out, then the strong incoherence property holds for a small value of $\mu$.

We define a random model obeying (1.13) as follows: take two arbitrary families of $n$ orthonormal vectors $[u_{1},\ldots,u_{n}]$ and $[v_{1},\ldots,v_{n}]$ obeying (1.13). We allow the $u_{i}$ and $v_{i}$ to be deterministic; for instance one could have $u_{i}=v_{i}$ for all $i\in[n]$.

Select $r$ left singular vectors $u_{\alpha(1)},\ldots,u_{\alpha(r)}$ at random with replacement from the first family, and $r$ right singular vectors $v_{\beta(1)},\ldots,v_{\beta(r)}$ from the second family, also at random. We do not require that the $\beta$ are chosen independently from the $\alpha$; for instance one could have $\beta(k)=\alpha(k)$ for all $k\in[r]$.

Set $M:=\sum_{k\in[r]}\epsilon_{k}\sigma_{k}u_{\alpha(k)}v_{\beta(k)}^{*}$, where the signs $\epsilon_{1},\ldots,\epsilon_{r}\in\{-1,+1\}$ are chosen independently at random (with probability $1/2$ of each choice of sign), and $\sigma_{1},\ldots,\sigma_{r}>0$ are arbitrary distinct positive numbers (which are allowed to depend on the previous random choices).

We emphasize that the only assumptions about the families $[u_{1},\ldots,u_{n}]$ and $[v_{1},\ldots,v_{n}]$ is that they have small components. For example, they may be the same. Also note that this model allows for any kind of dependence between the left and right singular selected vectors. For instance, we may select the same columns as to obtain a symmetric matrix as in the case where the two families are the same. Thus, one can think of our model as producing a generic matrix with uniformly bounded singular vectors.

We now show that $P_{U}$, $P_{V}$ and $E$ obey (1.8) and (1.9), with $\mu_{1},\mu_{2}=O(\mu_{B}\sqrt{\log n})$, with large probability. For (1.9), observe that

and $\{\epsilon_{k}\}$ is a sequence of i.i.d. $\pm 1$ symmetric random variables. Then Hoeffding’s inequality shows that $\mu_{2}=O(\mu_{B}\sqrt{\log n})$; see for details.

For (1.8), we will use a beautiful concentration-of-measure result of McDiarmid.

Let $\{a_{1},\ldots,a_{n}\}$ be a sequence of scalars obeying $|a_{i}|\leq\alpha$. Choose a random set $S$ of size $s$ without replacement from $\{1,\ldots,n\}$ and let $Y=\sum_{i\in S}a_{i}$. Then for each $t\geq 0$,

where $S:=\{\alpha(1),\ldots,\alpha(r)\}$. For any fixed $a,a^{\prime}\in[n]$, set

Taking $\lambda$ proportional to $\sqrt{\log n}$ and applying the union bound for $a,a^{\prime}\in[n]$ proves (1.8) with probability at least $1-n^{-3}$ (say) with $\mu_{1}=O(\mu_{B}\sqrt{\log n})$.

Combining this computation with Theorems 1.1, 1.2, we have established the following corollary:

Let $M$ be a matrix sampled from a uniformly bounded model. Under the hypotheses of Theorem 1.1, if

$M$ is the unique solution to (1.3) with probability at least $1-n^{-3}$. As we shall see below, when $r=O(1)$, it suffices to have

Obviously, this does not scale like $\sqrt{r}/n$. Similarly, the sign flip (step 2) is also necessary as otherwise, we could have $E=P_{U}$ as in the case where $[u_{1},\ldots,u_{n}]=[v_{1},\ldots,v_{n}]$ and the same columns are selected. Here,

which does not scale like $\sqrt{r}/n$ either.

5.2 Low-rank low-coherence model

When the rank is small, the assumption that the singular vectors are spread is sufficient to show that the parameter $\mu$ is small. To see this, suppose that the singular vectors obey (1.13). Then

The first inequality follows from the Cauchy-Schwarz inequality

for $a\neq a^{\prime}$ and from the Frobenius norm bound

This gives $\mu_{1}\leq\mu_{B}\sqrt{r}$. Also, by another application of Cauchy-Schwarz we have

so that we also have $\mu_{2}\leq\mu_{B}\sqrt{r}$. In short, $\mu\leq\mu_{B}\sqrt{r}$.

Our low-rank low-coherence model assumes that $r=O(1)$ and that the singular vectors obey (1.13). When $\mu_{B}=O(1)$, this model obeys the strong incoherence property with $\mu=O(1)$. In this case, Theorem 1.1 specializes as follows:

Let $M$ be a matrix of bounded rank $(r=O(1))$ whose singular vectors obey (1.13). Under the hypotheses of Theorem 1.1, if

then $M$ is the unique solution to (1.3) with probability at least $1-n^{-3}$.

5.3 Random orthogonal model

Our last model is borrowed from and assumes that the column matrices $[u_{1},\ldots,u_{r}]$ and $[v_{1},\ldots,v_{r}]$ are independent random orthogonal matrices, with no assumptions whatsoever on the singular values $\sigma_{1},\ldots,\sigma_{r}$. Note that this is a special case of the uniformly bounded model since this is equivalent to selecting two $n\times n$ random orthonormal bases, and then selecting the singular vectors as in Section 1.5.1. Since we know that the maximum entry of an $n\times n$ random orthogonal matrix is bounded by a constant times $\sqrt{\frac{\log n}{n}}$ with large probability, then Section 1.5.1 shows that this model obeys the strong incoherence property with $\mu=O(\log n)$. Theorems 1.1, 1.2 then give

Let $M$ be a matrix sampled from the random orthogonal model. Under the hypotheses of Theorem 1.1, if

then $M$ is the unique solution to (1.3) with probability at least $1-n^{-3}$. The exponent $8$ can be lowered to $7$ when $r\geq\log n$ and to $6$ when $r=O(1)$.

As mentioned earlier, we have a lower bound $m\geq 2nr-r^{2}$ for matrix completion, which can be improved to $m\geq Cnr\log n$ under reasonable hypotheses on the matrix $M$. Thus, the hypothesis on $m$ in Corollary 1.6 cannot be substantially improved. However, it is likely that by specializing the proofs of our general results (Theorems 1.1 and 1.2) to this special case, one may be able to improve the power of the logarithm here, though it seems that a substantial effort would be needed to reach the optimal level of $nr\log n$ even in the bounded rank case.

Speaking of logarithmic improvements, we have shown that $\mu=O(\log n)$, which is sharp since for $r=1$, one cannot hope for better estimates. For $r$ much larger than $\log n$, however, one can improve this to $\mu=O(\sqrt{\log n})$. As far as $\mu_{1}$ is concerned, this is essentially a consequence of the Johnson-Lindenstrauss lemma. For $a\neq a^{\prime}$, write

We claim that for each $a\neq a^{\prime}$,

with probability at least $1-n^{-5}$, say. This inequality is indeed well known. Observe that $\|P_{U}x\|$ has the same distribution than the Euclidean norm of the first $r$ components of a vector uniformly distributed on the $n-1$ dimensional sphere of radius $\|x\|$. Then we have :

Choosing $x=e_{a}\pm e_{a^{\prime}}$, $\epsilon=C_{0}\sqrt{\frac{\log n}{r}}$, and applying the union bound proves the claim as long as long as $r$ is sufficiently larger than $\log n$. Finally, since a bound on the diagonal term $\|P_{U}e_{a}\|^{2}-r/n$ in (1.8) follows from the same inequality by simply choosing $x=e_{a}$, we have $\mu_{1}=O(\sqrt{\log n})$. Similar arguments for $\mu_{2}$ exist but we forgo the details.

6 Comparison with other works

The mathematical study of matrix completion began with , which made slightly different incoherence assumptions than in this paper. Namely, let us say that the matrix $M$ obeys the incoherence property with a parameter $\mu_{0}>0$ if

for all $a\in[n_{1}]$, $b\in[n_{2}]$. Again, this implies $\mu_{0}\geq 1$.

In it was shown that if a fixed matrix $M$ obeys the incoherence property with parameter $\mu_{0}$, then nuclear minimization succeeds with large probability if

Now consider a matrix $M$ obeying the strong incoherence property with $\mu=O(1)$. Then since $\mu_{0}\geq 1$, (1.19) guarantees exact reconstruction only if $m\geq C\,n^{6/5}r\log n$ (and $r=O(n^{1/5})$) while our results only need $nr\text{polylog}(n)$ samples. Hence, our results provide a substantial improvement over (1.19) at least in the regime which permits minimal sampling.

We would like to note that there are obvious relationships between the best incoherence parameter $\mu_{0}$ and the best strong incoherence parameters $\mu_{1}$, $\mu_{2}$ for a given matrix $M$, which we take to be square for simplicity. On the one hand, (1.8) implies that

so that one can take $\mu_{0}\leq 1+\mu_{1}/\sqrt{r}$. This shows that one can apply results from the incoherence model (in which we only know (1.18)) to our model (in which we assume strong incoherence). On the other hand,

so that $\mu_{1}\leq\mu_{0}\sqrt{r}$. Similarly, $\mu_{2}\leq\mu_{0}\sqrt{r}$ so that one can transfer results in the other direction as well.

We would like to mention another important paper inspired by compressed sensing, and which also recovers low-rank matrices from partial information. The model in , however, assumes some sort of Gaussian measurements and is completely different from the completion problem discussed in this paper.

6.2 Spectral methods

An interesting new approach to the matrix completion problem has been recently introduced in . This algorithm starts by trimming each row and column with too few entries; i.e. one replaces the entries in those rows and columns by zero. Then one computes the SVD of the trimmed matrix and truncate it as to only keep the top $r$ singular values (note that one would need to know $r$ a priori). Then under some conditions (including the incoherence property (1.18) with $\mu=O(1)$), this work shows that accurate recovery is possible from a minimal number of samples, namely, on the order of $nr\log n$ samples. Having said this, this work is not directly comparable to ours because it operates in a different regime. Firstly, the results are asymptotic and are valid in a regime when the dimensions of the matrix tend to infinity in a fixed ratio while ours are not. Secondly, there is a strong assumption about the range of the singular values the unknown matrix can take on while we make no such assumption; they must be clustered so that no singular value can be too large or too small compared to the others. Finally, this work only shows approximate recovery—not exact recovery as we do here—although exact recovery results have been announced. This work is of course very interesting because it may show that methods—other than convex optimization—can also achieve minimal sampling bounds.

7 Lower bounds

We would like to conclude the tour of the results introduced in this paper with a simple lower bound, which highlights the fundamental role played by the coherence in controlling what is information-theoretically possible.

Fix $1\leq m,r\leq n$ and $\mu_{0}\geq 1$, let $0<\delta<1/2$, and suppose that we do not have the condition

Then there exist infinitely many pairs of distinct $n\times n$ matrices $M\neq M^{\prime}$ of rank at most $r$ and obeying the incoherence property (1.18) with parameter $\mu_{0}$ such that $\mathcal{P}_{\Omega}(M)=\mathcal{P}_{\Omega}(M^{\prime})$ with probability at least $\delta$. Here, each entry is observed with probability $p=m/n^{2}$ independently from the others.

Clearly, even if one knows the rank and the coherence of a matrix ahead of time, then no algorithm can be guaranteed to succeed based on the knowledge of $\mathcal{P}_{\Omega}(M)$ only, since they are many candidates which are consistent with these data. We prove this theorem in Section 2. Informally, Theorem 1.7 asserts that (1.20) is a necessary condition for matrix completion to work with high probability if all we know about the matrix $M$ is that it has rank at most $r$ and the incoherence property with parameter $\mu_{0}$. When the right-hand side of (1.20) is less than $\varepsilon<1$, this implies

Recall that the number of degrees of freedom of a rank-$r$ matrix is $2nr(1-r/2n)$. Hence, to recover an arbitrary rank-$r$ matrix with the incoherence property with parameter $\mu_{0}$ with any decent probability by any method whatsoever, the minimum number of samples must be about the number of degrees of freedom times $\mu_{0}\log n$; in other words, the oversampling factor is directly proportional to the coherence. Since $\mu_{0}\geq 1$, this justifies our earlier assertions that $nr\log n$ samples are really needed.

In the Bernoulli model used in Theorem 1.7, the number of entries is a binomial random variable sharply concentrating around its mean $m$. There is very little difference between this model and the uniform model which assumes that $\Omega$ is sampled uniformly at random among all subsets of cardinality $m$. Results holding for one hold for the other with only very minor adjustments. Because we are concerned with essential difficulties, not technical ones, we will often prove our results using the Bernoulli model, and indicate how the results may easily be adapted to the uniform model.

8 Notation

Before continuing, we provide here a brief summary of the notations used throughout the paper. To simplify the notation, we shall work exclusively with square matrices, thus

Throughout, we will always assume that $m$ is at least as large as $2nr$, thus

The Euclidean inner product between two matrices is defined by the formula

and the corresponding Euclidean norm, called the Frobenius norm or Hilbert-Schmidt norm, is denoted

The nuclear norm of a matrix ${X}$ is denoted

We use the usual asymptotic notation, for instance writing $O(M)$ to denote a quantity bounded in magnitude by $CM$ for some absolute constant $C>0$. We will sometimes raise such notation to some power, for instance $O(M)^{M}$ would denote a quantity bounded in magnitude by $(CM)^{M}$ for some absolute constant $C>0$. We also write $X\lesssim Y$ for $X=O(Y)$, and $\text{poly}(X)$ for $O(1+|X|)^{O(1)}$.

We use $1_{E}$ to denote the indicator function of an event $E$, e.g. $1_{a=a^{\prime}}$ equals $1$ when $a=a^{\prime}$ and when $a\neq a^{\prime}$.

If $A$ is a finite set, we use $|A|$ to denote its cardinality.

We record some (standard) conventions involving empty sets. The set $[n]:=\{1,\ldots,n\}$ is understood to be the empty set when $n=0$. We also make the usual conventions that an empty sum $\sum_{x\in\emptyset}f(x)$ is zero, and an empty product $\prod_{x\in\emptyset}f(x)$ is one. Note however that a $k$-fold sum such as $\sum_{a_{1},\ldots,a_{k}\in[n]}f(a_{1},\ldots,a_{k})$ does not vanish when $k=0$, but is instead equal to a single summand $f()$ with the empty tuple $()\in[n]^{0}$ as the input; thus for instance the identity

is valid both for positive integers $k$ and for $k=0$ (and both for non-zero $f$ and for zero $f$, recalling of course that $0^{0}=1$). We will refer to sums over the empty tuple as trivial sums to distinguish them from empty sums.

Lower bounds

This section proves Theorem 1.7, which asserts that no method can recover an arbitrary $n\times n$ matrix of rank $r$ and coherence at most $\mu_{0}$ unless the number of random samples obeys (1.20). As stated in the theorem, we establish lower bounds for the Bernoulli model, which then apply to the model where exactly $m$ entries are selected uniformly at random, see the Appendix for details.

Now under the Bernoulli model, the number of observed entries in the first row—and in any fixed row or column—is a binomial random variable with a number of trials equal to $n$ and a probability of success equal to $p$. Therefore, the probability $\pi_{0}$ that any row is unsampled is equal to $\pi_{0}=(1-p)^{n}$. By independence, the probability that all rows are sampled at least once is $(1-\pi_{0})^{n}$, and any method succeeding with probability greater $1-\delta$ would need

or $-n\pi_{0}\geq n\log(1-\pi_{0})\geq\log(1-\delta)$. When $\delta<1/2$, $\log(1-\delta)\geq-2\delta$ and thus, any method would need

This is the desired conclusion when $\mu_{0}>1$, $r=1$.

where the $\sigma_{k}$ are drawn arbitrarily from $$(say), and the singular vectors$u_{1},\ldots,u_{r}$ are defined as follows:

together with $1-e^{-x}>x-x^{2}/2$ whenever $x\geq 0$.

Strategy and Novelty

This section outlines the strategy for proving our main results, Theorems 1.1 and 1.2. The proofs of these theorems are the same up to a point where the arguments to estimate the moments of a certain random matrix differ. In this section, we present the common part of the proof, leading to two key moment estimates, while the proofs of these crucial estimates are the object of later sections.

One can of course prove our claims for the Bernoulli model with $p=m/n^{2}$ and transfer the results to the uniform model, by using the arguments in the appendix. For example, the probability that the recovery via (1.3) is not exact is at most twice that under the Bernoulli model.

We recall the projection matrices $P_{U},P_{V}$ and the companion matrix $E$ defined by (1.6), (1.7). It is known that

and note that the complementary projection $\mathcal{P}_{T^{\perp}}:=\mathcal{I}-\mathcal{P}_{T}$ is given by the formula

In particular, $\mathcal{P}_{T^{\perp}}$ is a contraction:

Then $Z\in\partial\|{X}\|_{*}$ if and only if

With these preliminaries in place, establishes the following result.

Let the notation be as above. Suppose that the following two conditions hold:

Then ${M}$ is the unique solution to the convex program (1.3).

The second sufficient condition, namely, the injectivity of the restriction to $\mathcal{P}_{\Omega}$ has been studied in . We recall a useful result.

[7, Theorem 4.1] Suppose $\Omega$ is sampled according to the Bernoulli model and put $n:=\max(n_{1},n_{2})$. Assume that $M$ obeys (1.18). Then there is a numerical constant $C_{R}$ such that for all $\beta>1$, we have the bound

with probability at least $1-3n^{-\beta}$ provided that $a<1$, where $a$ is the quantity

We will apply this theorem with $\beta:=4$ (say). The statement (3.6) is stronger than the injectivity of the restriction of $\mathcal{P}_{\Omega}$ to $T$. Indeed, take $m$ sufficiently large so that the $a<1$. Then if $X\in T$, we have

and obviously, $\mathcal{P}_{\Omega}(X)$ cannot vanish unless $X=0$.

In order for the condition $a<1$ to hold, we must have

for a suitably large constant $C_{0}$. But this follows from the hypotheses in either Theorem 1.1 or Theorem 1.2, for reasons that we now pause to explain. In either of these theorems we have

for some large constant $C_{1}$. Recall from Section 1.6.1 that $\mu_{0}\leq 1+\mu_{1}/\sqrt{r}\leq 1+\mu/\sqrt{r}$, and so (3.9) implies (3.8) whenever $\mu_{0}\geq 2$ (say). When $\mu_{0}<2$, we can also deduce (3.8) from (3.9) by applying the trivial bound $\mu\geq 1$ noted in the introduction.

In summary, to prove Theorem 1.1 or Theorem 1.2, it suffices (under the hypotheses of these theorems) to exhibit a dual matrix $Y$ obeying the first sufficient condition of Lemma 3.1, with probability at least $1-n^{-3}/2$ (say). This is the objective of the remaining sections of the paper.

2 The dual certificate

By construction, $\mathcal{P}_{\Omega}(Y)=Y$, $\mathcal{P}_{T}(Y)=E$ and, therefore, we will establish that $M$ is the unique minimizer if one can show that

The dual matrix $Y$ would then certify that $M$ is the unique solution, and this is the reason why we will refer to $Y$ as a candidate certificate. This certificate was also used in .

Before continuing, we would like to offer a little motivation for the choice of the dual matrix $Y$. It is not difficult to check that (3.10) is actually the solution to the following problem:

Note that by the Pythagorean identity, $Y$ obeys

The interpretation is now clear: among all matrices obeying $\mathcal{P}_{\Omega}(Z)=Z$ and $\mathcal{P}_{T}(Z)=E$, $Y$ is that element which minimizes $\|{\mathcal{P}}_{T^{\perp}}({Z})\|_{F}$. By forcing the Frobenius norm of ${\mathcal{P}}_{T^{\perp}}({Y})$ to be small, it is reasonable to expect that its spectral norm will be sufficiently small as well. In that sense, $Y$ defined via (3.10) is a very suitable candidate.

3 The Neumann series

From (3.12) we have $\mathcal{P}_{T}\mathcal{P}_{\Omega}\mathcal{P}_{T}=p\mathcal{P}_{T}(\mathcal{I}+\mathcal{Q}_{\Omega})\mathcal{P}_{T}$, and owing to Theorem 3.2, one can write $(\mathcal{P}_{T}\mathcal{P}_{\Omega}\mathcal{P}_{T})^{-1}$ as the convergent Neumann series

From the identity $\mathcal{P}_{T^{\perp}}\mathcal{P}_{T}=0$ we conclude that $\mathcal{P}_{T^{\perp}}\mathcal{P}_{\Omega}\mathcal{P}_{T}=p(\mathcal{P}_{T^{\perp}}\mathcal{Q}_{\Omega}\mathcal{P}_{T})$. One can therefore express the candidate certificate $Y$ (3.10) as

where we have used $\mathcal{P}_{T}^{2}=\mathcal{P}_{T}$ and $\mathcal{P}_{T}(E)=E$. By the triangle inequality and (3.5), it thus suffices to show that

It is not hard to bound the tail of the series thanks to Theorem 3.2. First, this theorem bounds the spectral norm of $\mathcal{P}_{T}\mathcal{Q}_{\Omega}\mathcal{P}_{T}$ by the quantity $a$ in (3.7). This gives that for each $k\geq 1$, $\|(\mathcal{P}_{T}\mathcal{Q}_{\Omega}\mathcal{P}_{T})^{k}(E)\|_{F}<a^{k}\|E\|_{F}=a^{k}\sqrt{r}$ and, therefore,

Second, this theorem also bounds $\|\mathcal{Q}_{\Omega}\mathcal{P}_{T}\|$ (recall that this is the spectral norm) since

Expanding the identity $\mathcal{P}_{\Omega}^{2}=\mathcal{P}_{\Omega}$ in terms of $\mathcal{Q}_{\Omega}$, we obtain

Hence $\|\mathcal{Q}_{\Omega}\mathcal{P}_{T}\|\leq\sqrt{(a+1)/p}$. For each $k_{0}\geq 0$, this gives

provided that $a<1/2$. With $p=m/n^{2}$ and $a$ defined by (3.7) with $\beta=4$, we have

with probability at least $1-n^{-4}$. When $k_{0}+1\geq\log n$, $n^{\frac{1}{k_{0}+1}}\leq n^{\frac{1}{\log n}}=e$ and thus for each such a $k_{0}$,

To summarize this section, we conclude that since both our results assume that $m\geq c_{0}\mu_{0}nr\log n$ for some sufficiently large numerical constant $c_{0}$ (see the discussion at the end of Section 3.1), it now suffices to show that

(say) with probability at least $1-n^{-3}/4$ (say).

4 Centering

We have already normalised $\mathcal{P}_{\Omega}$ to have “mean zero” in some sense by replacing it with $\mathcal{Q}_{\Omega}$. Now we perform a similar operation for the projection $\mathcal{P}_{T}:X\mapsto P_{U}X+XP_{V}-P_{U}XP_{V}$. The eigenvalues of $\mathcal{P}_{T}$ are centered around

as this follows from the fact that $\mathcal{P}_{T}$ is a an orthogonal projection onto a space of dimension $2nr-r^{2}$. Therefore, we simply split $\mathcal{P}_{T}$ as

so that the eigenvalues of $\mathcal{Q}_{T}$ are centered around zero. From now on, $\rho$ and $\rho^{\prime}$ will always be the numbers defined above.

Let $0<\sigma<1$. Consider the event such that

Then on this event, we have that for all $0\leq k<k_{0}$,

From (3.19) and the geometric series formula we obtain the corollary

Let $\sigma_{0}$ be such that the right-hand side is less than 1/4, say. Applying this with $\sigma=\sigma_{0}$, we conclude that to prove (3.15) with probability at least $1-n^{-3}/4$, it suffices by the union bound to show that (3.18) for this value of $\sigma$. (Note that the hypothesis $8nr/m<\sigma^{3/2}$ follows from the hypotheses in either Theorem 1.1 or Theorem 1.2.)

Lemma 3.3, which is proven in the Appendix, is useful because the operator $\mathcal{Q}_{T}$ is easier to work with than $\mathcal{P}_{T}$ in the sense that it is more homogeneous, and obeys better estimates. If we split the projections $P_{U},P_{V}$ as

Let ${U}_{a,a^{\prime}},{V}_{b,b^{\prime}}$ denote the matrix elements of $Q_{U},Q_{V}$:

and similarly for ${V}_{b,b^{\prime}}$. The coefficients $c_{ab,a^{\prime}b^{\prime}}$ of $\mathcal{Q}_{T}$ obey

An immediate consequence of this under the assumptions (1.8), is the estimate

When $\mu=O(1)$, these coefficients are bounded by $O(\sqrt{r}/n)$ when $a=a^{\prime}$ or $b=b^{\prime}$ while in contrast, if we stayed with $\mathcal{P}_{T}$ rather than $\mathcal{Q}_{T}$, the diagonal coefficients would be as large as $r/n$. However, our lemma states that bounding $\|(\mathcal{Q}_{\Omega}\mathcal{Q}_{T})^{k}\mathcal{Q}_{\Omega}(E)\|$ automatically bounds $\|(\mathcal{Q}_{\Omega}\mathcal{P}_{T})^{k}\mathcal{Q}_{\Omega}(E)\|$ by nearly the same quantity. This is the main advantage of replacing the $\mathcal{P}_{T}$ by the $\mathcal{Q}_{T}$ in our analysis.

5 Key estimates

To summarize the previous discussion, and in particular the bounds (3.20) and (3.14), we see everything reduces to bounding the spectral norm of $(\mathcal{Q}_{\Omega}\mathcal{Q}_{T})^{k}\mathcal{Q}_{\Omega}(E)$ for $k=0,1,\ldots,\lfloor\log n\rfloor$. Providing good upper bounds on these quantities is the crux of the argument. We use the moment method, controlling a spectral norm a matrix by the trace of a high power of that matrix. We will prove two moment estimates which ultimately imply our two main results (Theorems 1.1 and 1.2) respectively. The first such estimate is as follows:

Set $A=(\mathcal{Q}_{\Omega}\mathcal{Q}_{T})^{k}\mathcal{Q}_{\Omega}(E)$ for a fixed $k\geq 0$. Under the assumptions of Theorem 1.1, we have that for each $j>0$,

provided that $m\geq nr_{\mu}^{2}$ and $n\geq c_{0}j(k+1)$ for some numerical constant $c_{0}$.

By Markov’s inequality, this result automatically estimates the norm of $(\mathcal{Q}_{\Omega}\mathcal{Q}_{T})^{k}\mathcal{Q}_{\Omega}(E)$ and immediately gives the following corollary.

Under the assumptions of Theorem 1.1, the matrix $Y$ (3.10) is a dual certificate, and obeys $\|\mathcal{P}_{T^{\perp}}(Y)\|\leq 1/2$ with probability at least $1-n^{-3}$ provided that $m$ obeys (1.10).

Proof Set $A=(\mathcal{Q}_{\Omega}\mathcal{Q}_{T})^{k}\mathcal{Q}_{\Omega}(E)$ with $k\leq\log n$, and set $\sigma\leq\sigma_{0}$. By Markov’s inequality

Now choose $j>0$ to be the smallest integer such that $j(k+1)\geq\log n$. Since

where we have used the fact that $n^{\frac{1}{j(k+1)}}\leq n^{\frac{1}{\log n}}=e$. Hence, if

for some numerical constant $C_{0}$, we have $\gamma<1/4$ and

has probability less or equal to $n^{-4}\log n\leq n^{-3}/2$ for $n\geq 2$. Since the corollary assumes $r=O(1)$, then (3.26) together with (3.20) and (3.14) prove the claim thanks to our choice of $\sigma$.

Of course, Theorem 1.1 follows immediately from Corollary 3.5 and Lemma 3.1. In the same way, our second result (Theorem 1.2) follows from a more refined estimate stated below.

Set $A=(\mathcal{Q}_{\Omega}\mathcal{Q}_{T})^{k}\mathcal{Q}_{\Omega}(E)$ for a fixed $k\geq 0$. Under the assumptions of Theorem 1.2, we have that for each $j>0$ ($r_{\mu}$ is given in (3.25)),

provided that $n\geq c_{0}j(k+1)$ for some numerical constant $c_{0}$.

Just as before, this theorem immediately implies the following corollary.

Under the assumptions of Theorem 1.2, the matrix $Y$ (3.10) is a dual certificate, and obeys $\|\mathcal{P}_{T^{\perp}}(Y)\|\leq 1/2$ with probability at least $1-n^{-3}$ provided that $m$ obeys (1.12).

The proof is identical to that of Corollary 3.5 and is omitted. Again, Corollary 3.7 and Lemma 3.1 immediately imply Theorem 1.2.

6 Novelty

As explained earlier, this paper derives near-optimal sampling results which are stronger than those in . One of the reasons underlying this improvement is that we use completely different techniques. In details, constructs the dual certificate (3.10) and proceeds by showing that $\|\mathcal{P}_{T^{\perp}}(Y)\|<1$ by bounding each term in the series $\sum_{k\geq 0}\|(\mathcal{Q}_{\Omega}\mathcal{P}_{T})^{k}\mathcal{Q}_{\Omega}(E)\|<1$. Further, to prove that the early terms (small values of $k$) are appropriately small, the authors employ a sophisticated array of tools from asymptotic geometric analysis, including noncommutative Khintchine inequalities , decoupling techniques of Bourgain and Tzafiri and of de la Peña , and large deviations inequalities . They bound each term individually up to $k=4$ and use the same argument as that in Section 3.3 to bound the rest of the series. Since the tail starts at $k_{0}=5$, this gives that a sufficient condition is that the number of samples exceeds a constant times $\mu_{0}n^{6/5}nr\log n$. Bounding each term $\|(\mathcal{Q}_{\Omega}\mathcal{P}_{T})^{k}\mathcal{Q}_{\Omega}(E)\|^{k}$ with the tools put forth in for larger values of $k$ becomes increasingly delicate because of the coupling between the indicator variables defining the random set $\Omega$. In addition, the noncommutative Khintchine inequality seems less effective in higher dimensions; that is, for large values of $k$. Informally speaking, the reason for this seems to be that the types of random sums that appear in the moments $(\mathcal{Q}_{\Omega}\mathcal{P}_{T})^{k}\mathcal{Q}_{\Omega}(E)$ for large $k$ involve complicated combinations of the coefficients of $\mathcal{P}_{T}$ that are not simply components of some product matrix, and which do not simplify substantially after a direct application of the Khintchine inequality.

In this paper, we use a very different strategy to estimate the spectral norm of $(\mathcal{Q}_{\Omega}\mathcal{Q}_{T})^{k}\mathcal{Q}_{\Omega}(E)$, and employ moment methods, which have a long history in random matrix theory, dating back at least to the classical work of Wigner. We raise the matrix $A:=(\mathcal{Q}_{\Omega}\mathcal{Q}_{T})^{k}\mathcal{Q}_{\Omega}(E)$ to a large power $j$ so that

(the largest element dominates the sum). We then need to compute the expectation of the right-hand side, and reduce matters to a purely combinatorial question involving the statistics of various types of paths in a plane. It is rather remarkable that carrying out these combinatorial calculations nearly give the quantitatively correct answer; the moment method seems to come close to giving the ultimate limit of performance one can expect from nuclear-norm minimization.

As we shall shortly see, the expression $\operatorname{trace}(A^{*}A)^{j}$ expands as a sum over “paths” of products of various coefficients of the operators $\mathcal{Q}_{\Omega},\mathcal{Q}_{T}$ and the matrix $E$. These paths can be viewed as complicated variants of Dyck paths. However, it does not seem that one can simply invoke standard moment method calculations in the literature to compute this sum, as in order to obtain efficient bounds, we will need to take full advantage of identities such as $\mathcal{P}_{T}\mathcal{P}_{T}=\mathcal{P}_{T}$ (which capture certain cancellation properties of the coefficients of $\mathcal{P}_{T}$ or $\mathcal{Q}_{T}$) to simplify various components of this sum. It is only after performing such simplifications that one can afford to estimate all the coefficients by absolute values and count paths to conclude the argument.

Moments

Let $j\geq 0$ be a fixed integer. The goal of this section is to develop a formula for

This will clearly be of use in the proofs of the moment bounds (Theorems 3.4, 3.6).

We first write the matrix $A$ in components as

for some scalars $A_{ab}$, where $e_{ab}$ is the standard basis for the $n\times n$ matrices and $A_{ab}$ is the $(a,b)^{\operatorname{th}}$ entry of $A$. Then

where we adopt the cyclic convention $a_{j+1}=a_{1}$. Equivalently, we can write

where the sum is over all $a_{i,\mu},b_{i,\mu}\in[n]$ for $i\in[j],\mu\in\{0,1\}$ obeying the compatibility conditions

with the cyclic convention $a_{j+1,0}=a_{1,0}$.

Example. If $j=2$, then we can write ${{\operatorname{trace}}}(A^{*}A)^{j}$ as

where the sum is over all $a_{1,0},a_{1,1},a_{2,0},a_{2,1},b_{1,0},b_{1,1},b_{2,0},b_{2,1}\in[n]$ obeying the compatibility conditions

Remark. The sum in (4.2) can be viewed as over all closed paths of length $2j$ in $[n]\times[n]$, where the edges of the paths alternate between “horizontal rook moves” and “vertical rook moves” respectively; see Figure 1.

Second, write $\mathcal{Q}_{T}$ and $\mathcal{Q}_{\Omega}$ in coefficients as

where $c_{ab,a^{\prime}b^{\prime}}$ is given by (3.23), and

where $\xi_{ab}$ are the iid, zero-expectation random variables

for any $a_{0},b_{0}\in[n]$. Note that this formula is even valid in the base case $k=0$, where it simplifies to just $A_{a_{0}b_{0}}=\xi_{a_{0}b_{0}}E_{a_{0}b_{0}}$ due to our conventions on trivial sums and empty products.

Remark. One can view the right-hand side of (4.3) as the sum over paths of length $k+1$ in $[n]\times[n]$ starting at the designated point $(a_{0},b_{0})$ and ending at some arbitrary point $(a_{k},b_{k})$. Each edge (from $(a_{i},b_{i})$ to $(a_{i+1},b_{i+1})$) may be a horizontal or vertical “rook move” (in that at least one of the $a$ or $b$ coordinates does not changeUnlike the ordinary rules of chess, we will consider the trivial move when $a_{i+1}=a_{i}$ and $b_{i+1}=b_{i}$ to also qualify as a “rook move”, which is simultaneously a horizontal and a vertical rook move.), or a “non-rook move” in which both the $a$ and $b$ coordinates change. It will be important later on to keep track of which edges are rook moves and which ones are not, basically because of the presence of the delta functions $1_{a=a^{\prime}},1_{b=b^{\prime}}$ in (3.23). Each edge in this path is weighted by a $c$ factor, and each vertex in the path is weighted by a $\xi$ factor, with the final vertex also weighted by an additional $E$ factor. It is important to note that the path is allowed to cross itself, in which case weights such as $\xi^{2}$, $\xi^{3}$, etc. may appear, see Figure 2.

Inserting (4.3) into (4.2), we see that $X$ can thus be expanded as

where the sum $\sum_{*}$ is over all combinations of $a_{i,\mu,l},b_{i,\mu,l}\in[n]$ for $i\in[j]$, $\mu\in\{0,1\}$ and $0\leq l\leq k$ obeying the compatibility conditions

with the cyclic convention $a_{j+1,0,0}=a_{1,0,0}$.

Example. Continuing our running example $j=k=2$, we have

where $a_{i,\mu,l}$ for $i=1,2$, $\mu=0,1$, $l=0,1,2$ obey the compatibility conditions

Note that despite the small values of $j$ and $k$, this is already a rather complicated sum, ranging over $n^{2j(2k+1)}=n^{20}$ summands, each of which is the product of $4j(k+1)=24$ terms.

Remark. The expansion (4.4) is the sum over a sort of combinatorial “spider”, whose “body” is a closed path of length $2j$ in $[n]\times[n]$ of alternating horizontal and vertical rook moves, and whose $2j$ “legs” are paths of length $k$, emanating out of each vertex of the body. The various “segments” of the legs (which can be either rook or non-rook moves) acquire a weight of $c$, and the “joints” of the legs acquire a weight of $\xi$, with an additional weight of $E$ at the tip of each leg. To complicate things further, it is certainly possible for a vertex of one leg to overlap with another vertex from either the same leg or a different leg, introducing weights such as $\xi^{2}$, $\xi^{3}$, etc.; see Figure 3.

As one can see, the set of possible configurations that this “spider” can be in is rather large and complicated.

2 Second step: collecting rows and columns

We now group the terms in the expansion (4.4) into a bounded number of components, depending on how the various horizontal coordinates $a_{i,\mu,l}$ and vertical coordinates $b_{i,\mu,l}$ overlap.

It is convenient to order the $2j(k+1)$ tuples $(i,\mu,l)\in[j]\times\{0,1\}\times\{0,\ldots,k\}$ lexicographically by declaring $(i,\mu,l)<(i^{\prime},\mu^{\prime},l^{\prime})$ if $i<i^{\prime}$, or if $i=i^{\prime}$ and $\mu<\mu^{\prime}$, or if $i=i^{\prime}$ and $\mu=\mu^{\prime}$ and $l<l^{\prime}$.

We then define the indices $s_{i,\mu,l},t_{i,\mu,l}\in\{1,2,3,\ldots\}$ recursively for all $(i,\mu,l)\in[j]\times\{0,1\}\times[k]$ by setting $s_{1,0,0}=1$ and declaring $s_{i,\mu,l}:=s_{i^{\prime},\mu^{\prime},l^{\prime}}$ if there exists $(i^{\prime},\mu^{\prime},l^{\prime})<(i,\mu,l)$ with $a_{i^{\prime},\mu^{\prime},l^{\prime}}=a_{i,\mu,l}$, or equal to the first positive integer not equal to any of the $s_{i^{\prime},\mu^{\prime},l^{\prime}}$ for $(i^{\prime},\mu^{\prime},l^{\prime})<(i,\mu,l)$ otherwise. Define $t_{i,\mu,l}$ using $b_{i,\mu,l}$ similarly. We observe the cyclic condition

with the cyclic convention $s_{j+1,0,0}=s_{1,0,0}$.

Example. Suppose that $j=2$, $k=1$, and $n\geq 30$, with the $(a_{i,\mu,l},b_{i,\mu,l})$ given in lexicographical ordering as

Observe that the conditions (4.5) hold for this example, which then forces (4.6) to hold also.

In addition to the property (4.6), we see from construction of $(s,t)$ that for any $(i,\mu,l)\in[j]\times\{0,1\}\times\{0,\ldots,k\}$, the sets

are initial segments, i.e. of the form $[m]$ for some integer $m$. Let us call pairs $(s,t)$ of sequences with this property, as well as the property (4.6), admissible; thus for instance the sequences in the above example are admissible. Given an admissible pair $(s,t)$, if we define the sets $J$, $K$ by

then we observe that $J=[|J|],K=[|K|]$. Also, if $(s,t)$ arose from $a_{i,\mu,l},b_{i,\mu,l}$ in the above manner, there exist unique injections $\alpha:J\to[n],\beta:K\to[n]$ such that $a_{i,\mu,l}=\alpha(s_{i,\mu,l})$ and $b_{i,\mu,l}=\beta(t_{i,\mu,l})$.

Example. Continuing the previous example, we have $J=$, $K=$, with the injections $\alpha:\to[n]$ and $\beta:\to[n]$ defined by

Conversely, any admissible pair $(s,t)$ and injections $\alpha,\beta$ determine $a_{i,\mu,l}$ and $b_{i,\mu,l}$. Because of this, we can thus expand $X$ as

where the outer sum is over all admissible pairs $(s,t)$, and the inner sum is over all injections.

Remark. As with preceding identities, the above formula is also valid when $k=0$ (with our conventions on trivial sums and empty products), in which case it simplifies to

Remark. One can think of $(s,t)$ as describing the combinatorial “configuration” of the “spider” $((a_{i,\mu,l},b_{i,\mu,l}))_{(i,\mu,l)\in[j]\times\{0,1\}\times\{0,\ldots,k\}}$ - it determines which vertices of the spider are equal to, or on the same row or column as, other vertices of the spider. The injections $\alpha,\beta$ then enumerate the ways in which such a configuration can be “represented” inside the grid $[n]\times[n]$.

3 Third step: computing the expectation

Applying this estimate and the triangle inequality, we can thus bound $X$ by

where the sum is over those admissible $(s,t)$ such that each element of $\Omega$ is visited at least twice by the sequence $(s_{i,\mu,l},t_{i,\mu,l})$; we shall call such $(s,t)$ strongly admissible. We will use the bound (4.10) as a starting point for proving the moment estimates (3.25) and (3.27).

Example. The pair $(s,t)$ in the Example in Section 4.2 is admissible but not strongly admissible, because not every element of the set $\Omega$ (which, in this example, is $\{(1,1),(2,2),(3,1),$ $(2,3),(3,4),$ $(1,2),(1,4)\}$) is visited twice by the $(s,t)$.

Remark. Once again, the formula (4.10) is valid when $k=0$, with the usual conventions on empty products (in particular, the factor involving the $c$ coefficients can be deleted in this case).

Quadratic bound in the rank

This section establishes (3.25) under the assumptions of Theorem 1.1, which is the easier of the two moment estimates. Here we shall just take the absolute values in (4.10) inside the summation and use the estimates on the coefficients given to us by hypothesis. Indeed, starting with (4.10) and the triangle inequality and applying (1.9) together with (3.23) gives

where we recall that $r_{\mu}=\mu^{2}r$, and $Q$ is the set of all $(i,\mu,l)\in[j]\times\{0,1\}\times[k]$ such that $s_{i,\mu,l-1}\neq s_{i,\mu,l}$ and $t_{i,\mu,l-1}\neq t_{i,\mu,l}$. Thinking of the sequence $\{(s_{i,\mu,l},t_{i,\mu,l})\}$ as a path in $J\times K$, we have that $(i,\mu,l)\in Q$ if and only if the move from $(s_{i,\mu,l-1},t_{i,\mu,l-1})$ to $(s_{i,\mu,l},t_{i,\mu,l})$ is neither horizontal nor vertical; per our earlier discussion, this is a “non-rook” move.

Example. The example in Section 4.2 is admissible, but not strongly admissible. Nevertheless, the above definitions can still be applied, and we see that $Q=\{(0,0,1),(0,1,1),(1,0,1),(1,1,1)\}$ in this case, because all of the four associated moves are non-rook moves.

As the number of injections $\alpha,\beta$ is at most $n^{|J|},n^{|K|}$ respectively, we thus have

Since $(s,t)$ is strongly admissible and every point in $\Omega$ needs to be visited at least twice, we see that

Also, since $Q\subset[j]\times\{0,1\}\times[k]$, we have the trivial bound