Tight oracle bounds for low-rank matrix recovery from a minimal number of random measurements

Introduction

Low-rank matrix recovery is a burgeoning topic drawing the attention of many researchers in the closely related field of sparse approximation and compressive sensing. To draw an analogy, in the sparse approximation setup, the signal $y$ is modeled as a sparse linear combination of elements from a dictionary $D$ so that

In both cases, signal recovery appears to be an ill-posed problem because there are many more unknowns than equations. However, as has been shown extensively in the sparse-approximation literature, the assumption that the object of interest is sparse makes this problem meaningful even when the linear system of equations is apparently underdetermined. Further, when the measurements are corrupted by noise, we now know that by taking into account the parsimony of the model, one can insure that the recovery error is within a log factor of the error one would achieve by regressing $y$ onto the low-dimensional subspace spanned by those columns with $x_{i}\neq 0$; the squared error is adaptive, and proportional to the true dimension of the signal .

In this paper, we derive similar results for matrix recovery. In contrast to results available in the literature on compressive sensing or sparse regression, we show that the error bound is within a constant factor (rather than a log factor) of an idealized ‘oracle’ error bound achieved by projecting the data onto a smaller subspace given by the ‘oracle’ (and also within a constant of the minimax error bound). This error bound also applies to full-rank matrices (which are well-approximated by low-rank matrices), and there appears to be no analogue of this in the compressive sensing world.

The dimension of $T$ is $r(n_{1}+n_{2}-r)$. Thus, if $m<(n_{1}+n_{2}-r)r$, there exists $M=UX^{*}-YV^{*}\neq 0$ in $T$ such that $\mathcal{A}(M)=0$. This proves the claim since $\mathcal{A}(UX^{*})=\mathcal{A}(YV^{*})$ for two distinct matrices of rank at most $r$. Now a novel result of this paper is that, even without knowing that $M\in T$, one can stably recover $M$ from a constant times $(n_{1}+n_{2})r$ measurements via nuclear-norm minimization. Once again, in contrast to similar results in compressive sensing, the number of measurements required is within a constant of the theoretical lower limit – there is no extra log factor.

Following a series of advances in the theory of low-rank matrix recovery from undersampled linear measurements , a number of new applications have sprung up to join ranks with the already established ones. A quick survey shows that low-rank modeling is getting very popular in science and engineering, and we present a few eclectic examples to illustrate this point.

Quantum state tomography . In quantum state tomography, a mixed quantum state is represented as a square positive semidefinite matrix, $M$ (with trace 1). If $M$ is actually a pure state, then it has rank 1, and more generally, if it is approximately pure then it will be well approximated by a low-rank matrix .

Face recognition . Here the sequence of signals $\{y_{i}\}$ are images of the same face under varying illumination. In theory and under idealized circumstances (the images are assumed to be convex, Lambertian objects), these faces all reside near the same nine-dimensional linear subspace . In practice, face-recognition techniques based on the assumption that these images reside in a low-dimensional subspace are highly successful .

Quantum state tomography lends itself perfectly to the compressive sensing framework. On an abstract level, one sees measurements consisting of linear combinations of the unknown quantum state $M$ – inner products with certain observables which can be chosen with some flexibility by the physicist – and the goal is to recover a good approximation of $M$. The size of $M$ grows exponentially with the number of particles in the system, so one would like to use the structure of $M$ to reduce the number of measurements required, thus necessitating compressive sensing (see for a more in depth discussion and a specific analysis of this problem). An interesting point about quantum state tomography is that if one enforces the constraints $\operatorname{trace}(M)=1$ and $M\succeq 0$ then this ensures that $||M||_{*}=1$, and the scientist is left with a feasibility problem. In the authors suggest to solve this feasibility problem by removing a constraint and then performing nuclear-norm minimization and they show that under certain conditions this is sufficient for exact recovery (and thus of course the solution obeys the unenforced constraint). Another more established example is sensor localization, in which one sees a subset of the entries of a distance matrix because the sensors have low power and can only sense reliably its distance to nearby sensors. The goal is to fill in the missing entries (matrix completion). In some applications of the face recognition example, one would see the entire set of faces (the sampling operator is the identity), and the low-rank structure can be used to remove sparse errors, but otherwise arbitrarily gross, from the data as described in (we include this example to illustrate the different uses of the low-rank matrix model, but also note that it is quite different than the problem addressed in our paper).

2 Prior literature

The theory regarding the power of nuclear-norm minimization in recovering low-rank matrices from undersampled measurements began with a paper by Recht et al. , which sought to bridge compressive-sensing with low-rank matrix recovery via the RIP (to be defined in Section 2.1). Subsequently, several papers specialized the theory of nuclear-norm minimization to the matrix completion problem which turns out to be ‘RIPless’; this literature is motivated by very clear applications such as recommender systems and network localizations, and has required very sophisticated mathematical techniques.

With the recent increase in attention given to the low-rank matrix model, which the authors surmise is due to the spring of new theory, new applications are being quickly discovered that deviate from the matrix completion setup (such as quantum state tomography ), and could benefit from a different analysis. Our paper returns to measurement ensembles obeying the RIP as in , which are of a different nature than those involved in matrix completion. As in compressive sensing, the only known measurement ensembles which provably satisfy the RIP at a nearly minimal sampling rate are random (such as the Gaussian measurement ensemble in Section 2.1) Having said this, two comments are in order. First, our results provide an absolute benchmark of what is achievable, thus allowing direct comparisons with other methods and other sampling operators $\mathcal{A}$. For instance, one can quantify how far the error bounds for the RIPless matrix completion are from what is then known to be essentially unimprovable. Second, since our results imply that the restricted isometry property alone guarantees a near-optimal accuracy, we hope that this will encourage more applications with random ensembles, and also encourage researchers to establish whether or not their measurements obey this desirable property. Finally, we hope that our analysis offers insights for applications with nonrandom measurement ensembles.

3 Problem setup

We pause to demonstrate the form of $\mathcal{A}(X)$ explicitly: the $i$th entry of $\mathcal{A}(X)$ is $[\mathcal{A}(X)]_{i}=\langle A_{i},X\rangle$ for some sequence of matrices $\{A_{i}\}$ and with the standard inner product $\langle A,X\rangle=\operatorname{trace}(A^{*}X)$. Each $A_{i}$ can be likened to a row of a compressive sensing matrix, and in fact it can aid the intuition to think of $\mathcal{A}$ as a large matrix, i.e. one could write $\mathcal{A}(X)$ as

where vec$(X)$ is a long vector obtained by stacking the columns of $X$. In the common matrix completion problem, each $A_{i}$ is of the form $e_{k}e_{j}^{*}$ so that the $i$th component of $\mathcal{A}(X)$ is of the form $\langle e_{k}e_{j}^{*},M\rangle=e_{k}^{*}Me_{j}=M_{kj}$ for some $(j,k)$.

4 Algorithms

To recover $M$, we propose solving one of two nuclear-norm-minimization based algorithms. The first is an analogue to the Dantzig Selector from compressive sensing , defined as follows:

where the optimal solution is our estimate $\hat{M}$, $\|\cdot\|$ is the operator norm and $||\cdot||_{*}$ is its dual, i.e. the nuclear norm, and $\mathcal{A}^{*}$ is the adjoint of $\mathcal{A}$. We call this convex program the matrix Dantzig selector.

To pick a useful value for the parameter $\lambda$ in (1.3), we stipulate that the ‘true’ matrix $M$ should be feasible (this is a necessary condition for our proofs). In other words, one should have $\|\mathcal{A}^{*}(z)\|\leq\lambda$; Section 2.2 provides further intuition about this requirement. In the case of Gaussian noise, this corresponds to $\lambda=Cn\sigma$ for some numerical constant $C$ as in the following lemma.

Suppose $z$ is a Gaussian vector with i.i.d. $\mathcal{N}(0,\sigma^{2})$ entries and let $n=\max(n_{1},n_{2})$. Then if $C_{0}>4\sqrt{(1+\delta_{1})\log 12}$

with probability at least $1-2e^{-cn}$ for a fixed numerical constant $c>0$.

This lemma is proved in Section 3 using a standard covering argument. The scalar $\delta_{1}$ is the isometry constant at $\operatorname{rank}1$, as defined in Section 2.1, but suffice for now that it is a very small constant bounded by $\sqrt{2}-1$ (with high probability) under the assumptions of all of our theorems.

The optimization program (1.3) may be formulated as a semidefinite program (SDP) and can thus be solved by any of the standard SDP solvers. To see this, we first recall that the nuclear norm admits an SDP characterization since $\|X\|_{*}$ is the optimal value of the SDP

This shows that (1.3) can be formulated as the SDP

However, a few algorithms have recently been developed to solve similar nuclear-norm minimization problems without using interior-point methods which work extremely efficiently in practice . The nuclear-norm minimization problem solved using fixed-point continuation in is an analogue to the LASSO, and is defined as follows:

We call this convex program the matrix Lasso and it is the second convex program whose theoretical properties are analyzed in this paper.

5 Organization of the paper

The results in this paper mostly concern random measurements and random noise and so they hold with high probability. In Section 2.1, we show that certain classes of random measurements satisfy the RIP when only sampling a constant number of measurements per degree of freedom. In Section 2.2 we present the simplest of our error bounds, demonstrating that when the RIP holds, the solution to (1.3) is within a constant of the minimax risk. This error bound is refined in Section 2.3 to provide a more adaptive error that holds improvements when the singular values of $M$ decay below the noise level. It is shown that this error bound is within a constant of the expected value of a certain ‘oracle’ error bound. In Section 2.4, we present an error bound handling the case when $M$ has full rank but is well approximated by a low-rank matrix. Section 3 contains the proofs and we finish with some concluding remarks in Section 4.

6 Notation

Main Results

The matrix version of the RIP is an integral tool in proving our theoretical results and we begin by defining the RIP in this setting and describing measurement ensembles that satisfy it. To characterize the RIP, we introduce the isometry constants of a linear map $\mathcal{A}$.

For each integer $r=1,2,\ldots,n$, the isometry constant $\delta_{r}$ of ${\cal A}$ is the smallest quantity such that

holds for all matrices of rank at most $r$.

We say that $\mathcal{A}$ satisfies the RIP at rank $r$ if $\delta_{r}$ is bounded by a sufficiently small constant between 0 and 1, the value of which will become apparent in further sections (see e.g. Theorem 2.4).

Which linear maps $\mathcal{A}$ satisfy the RIP? As a quintessential example, we introduce the Gaussian measurement ensemble.

$\mathcal{A}$ is a Gaussian measurement ensemble if each ‘row’ $A_{i}$, $1\leq i\leq m$, contains i.i.d. $\mathcal{N}(0,1/m)$ entries (and the $A_{i}$’s are independent from each other).

This is of course highly analogous to the Gaussian random matrices in compressive sensing. Our first result is that Gaussian measurement ensembles, along with many other random measurement ensembles, satisfy the RIP when $m\geq C\,nr$ (with high probability) for some constant $C>0$.

for fixed constants $C,c>0$ (which may depend on $t$). Then if $m\geq Dnr$, $\mathcal{A}$ satisfies the RIP with isometry constant $\delta_{r}\leq\delta$ with probability exceeding $1-Ce^{-dm}$ for fixed constants $D,d>0$.

Similarly, $\mathcal{A}$ satisfies equation (2.3) in the case when each entry of each ‘row’ $A_{i}$ has i.i.d. entries that are equally likely to take the value $1/\sqrt{m}$ or $-1/\sqrt{m}$, or if $\mathcal{A}$ is a random projection . Further, $\mathcal{A}$ satisfies (2.2) if the ‘rows’ $A_{i}$ contain sub-Gaussian entries (properly normalized) , although in this case the constants involved depend on the parameters of the sub-Gaussian entries.

In order to ascertain the strength of Theorem 2.3, note that the number of degrees of freedom of an $n_{1}\times n_{2}$ matrix of rank $r$ is equal to $r(n_{1}+n_{2}-r)$.This can be seen by counting the number of equations and unknowns in the singular value decomposition. Thus, one may expect that if $m<r(n_{1}+n_{2}-r)$, there should be a rank-$r$ matrix in the null space of $\mathcal{A}$ leading to a failure to achieve the lower bound in (2.1). In order to make this intuition rigorous (to within a constant) assume without loss of generality that $n_{2}\geq n_{1}$, and observe that the set of rank-$r$ matrices contains all those matrices restricted to have nonzero entries only in the first $r$ rows. This is an $n\times r$ dimensional vector space and thus we must have $m\geq nr$ or otherwise there will be a rank-$r$ matrix in the null space of $\mathcal{A}$ regardless of what measurements are used. (This is a similar alternative to the null-space argument posed in the introduction.)

Theorem 2.3 is inspired by a similar theorem in [Theorem 4.2] and refines this result in two ways. First, it shows that one only needs a constant number of measurements per degree of freedom of the underlying rank-$r$ matrix in order to obtain the RIP at rank $r$ (which improves on the result in by a factor of $\log n$ and also achieves the theoretical lower bound to within a constant). Second, it shows that one must only require a single concentration bound on $\mathcal{A}$, removing another assumption required in . A possible third benefit is that the proof follows simply and quickly from a specialized covering argument. The novelty is in the method used to cover low-rank matrices.

2 The matrix Dantzig selector and the matrix Lasso are nearly minimax

In this section, we present our first and simplest error bound, which only requires that $\mathcal{A}$ satisfies the RIP.

Assume that $\operatorname{rank}(M)\leq r$ and let $\hat{M}_{DS}$ be the solution to the matrix Dantzig selector (1.3) and $\hat{M}_{L}$ be the solution to the matrix Lasso (1.5). If $\delta_{4r}<\sqrt{2}-1$ and $\|{\cal A}^{*}(z)\|\leq\lambda$ then

and if $\delta_{4r}<(3\sqrt{2}-1)/17$ and $\|\mathcal{A}^{*}(z)\|\leq\mu/2$, then

above, $C_{0}$ and $C_{1}$ are small constants depending only on the isometry constant $\delta_{4r}$. In particular, if $z$ is a Gaussian error and $\hat{M}$ is either $\hat{M}_{DS}$ with $\lambda=8n\sigma$, or $\hat{M}_{L}$ with $\mu=16n\sigma$, we have

with probability at least $1-2e^{-cn}$ for a constant $C^{\prime}_{0}$ (depending only on $\delta_{4r}$).

Note that (2.6) follows from (2.4) and (2.5) simply by plugging in $\lambda,\mu/2=8n\sigma$ into Lemma 1.1. In a nutshell, the error is proportional to the number of degrees of freedom times the noise level.

An important point is that one may expect the error to be reduced when further measurements are taken i.e. one may expect the error to be inversely proportional to $m$. In fact, this is the case for the Gaussian measurement ensemble, but this extra factor is absorbed into the definition in order to normalize the measurements so that they satisfy the RIP. If instead, each row ‘$A_{i}$’ in the Gaussian measurement ensemble is defined to have i.i.d. standard normal entries, then by a simple rescaling argument (apply Theorem 2.4 to $y/\sqrt{m}$), the error bound reads

A second remark is that exploiting the low-rank structure helps to denoise. For example, if we measured every entry of $M$ (a measurement ensemble with isometry constant $\delta_{r}=0$), but with each measurement corrupted by a $\mathcal{N}(0,\sigma^{2})$ noise term, then taking the measurements as they are as the estimate of $M$ would lead to an expected error equal to

Nuclear-norm minimizationOf course if one sees all of the entries of the matrix plus noise, nuclear-norm minimization is unnecessary, and one can achieve minimax error bounds by truncating the singular values. reduces this error by a factor of about $n/r$.

The strength of Theorem 2.4 is that the error bound (2.6) is nearly optimal in the sense that no estimator can do essentially better without further assumptions, as seen by lower-bounding the expected minimax error.

If $z$ is a Gaussian error, then any estimator $\hat{M}(y)$ obeys

In other words, the minimax error over the class of matrices of rank at most $r$ is lower bounded by about $nr\sigma^{2}$.

Before continuing, it may be helpful to analyze the solutions to the matrix Dantzig selector and the matrix Lasso in a simple case in order to understand the error bounds in Theorem 2.4 intuitively, and also to understand our choice of $\lambda$ and $\mu$. Suppose $\mathcal{A}$ is the identity so that changing the notation a bit, the model is $Y=M+Z$, where $Z$ is an $n\times n$ matrix with i.i.d. Gaussian entries. We would like the unknown matrix $M$ to be a feasible point, which requires that $\|Z\|\leq\lambda$ (for example, if $\|Z\|>\lambda$, we already have problems when $M=0$). It is well known that the top singular value of a square $n\times n$ Gaussian matrix, with per-entry variance $\sigma^{2}$, is concentrated around $\sqrt{2n}\sigma$, and thus we require $\lambda\geq\sqrt{2n}\sigma$ (this provides a slightly sharper bound than Lemma 1.1). Let $T_{\lambda}(X)$ denote the singular value thresholding operator given by

where $X=\sum_{i}\sigma_{i}(X)u_{i}v_{i}^{*}$ is any singular value decomposition. In this simple setting, the solution to (1.3) and (1.5) can be explicitly calculated, and for $\lambda=\mu$ they are both equal to $T_{\lambda}(M+Z)$. If $\lambda$ is too large, then $T_{\lambda}(M+Z)$ becomes strongly biased towards zero, and thus (loosely) $\lambda$ should be as small as possible while still allowing $M$ to be feasible for the matrix Dantzig selector (1.3), leading to the choice $\lambda\approx\sqrt{2n}\sigma$.

Further, in this simple case we can calculate the error bound in a few lines. We have

Once again, assuming that $\lambda\geq\|Z\|$, we have $\operatorname{rank}(\hat{M}-M)\leq\operatorname{rank}(\hat{M})+\operatorname{rank}(M)\leq 2r$. Plugging this in with $\lambda=C\sqrt{n}\sigma$ gives the error bound (2.6).

3 Oracle inequalities

Showing that an estimator achieves the minimax risk is reassuring but is sometimes not considered completely satisfactory. As is frequently discussed in the literature, the minimax approach focuses on the worst-case performance and it is quite reasonable to expect that for matrices of general interest, better performances are possible. In fact, a recent trend in statistical estimation is to compare the performance of an estimator with what is achievable with the help of an oracle that reveals extra information about the problem. A good match indicates an overall excellent performance.

To develop an oracle bound, assume w.l.o.g. that $n_{2}\geq n_{1}$ so that $n=n_{2}$, and consider the family of estimators defined as follows: for each $n_{1}\times r$ orthogonal matrix $U$, define

In other words, we fix the column space (the linear space spanned by the columns of the matrix $U$), and then find the matrix with that column space which best fits the data. Knowing the true matrix $M$, an oracle or a genie would then select the best column space to use as to minimize the mean-squared error (MSE)

The question is whether it is possible to mimic the performance of the oracle and achieve a MSE close to (2.10) with a real estimator.

Before giving a precise answer to this question, it is useful to determine how large the oracle risk is. To this end, consider a fixed orthogonal matrix $U$, and write the least-squares estimate (2.9) as

Then decompose the MSE as the sum of the squared bias and variance

The variance term is classically equal to

Due to the restricted isometry property, all the eigenvalues of the linear operator ${\cal A}_{U}^{*}{\cal A}_{U}$ belong to the interval $[1-\delta_{r},1+\delta_{r}]$, see Lemma 3.12. Therefore, the variance term obeys

Hence, the bias is the sum of two matrices: the first has a column space included in the span of the columns of $U$ while the column space of the other is orthogonal to this span. Put $P_{U^{\perp}}(M)=(I-UU^{*})M$; that is, $P_{U^{\perp}}(M)$ is the (left) multiplication with the orthogonal projection matrix $(I-UU^{*})$. We have

Now for a given dimension $r$, the best $U$ – that minimizing the squared bias term or its proxy $\|P_{U^{\perp}}(M)\|_{F}^{2}$ – spans the top $r$ singular vectors of the matrix $M$. Denoting the singular values of $M$ by $\sigma_{i}(M)$, we obtain

The right-hand side has a nice interpretation. Write the SVD of $M$ as $M=\sum_{i=1}^{r}\sigma_{i}(M)u_{i}v_{i}^{*}$. Then if $\sigma_{i}^{2}(M)>n\sigma^{2}$, one should try to estimate the rank-$1$ contribution $\sigma_{i}(M)\,u_{i}v_{i}^{*}$ and pay the variance term (which is about $n\sigma^{2}$) whereas if $\sigma_{i}^{2}(M)\leq n\sigma^{2}$, we should not try to estimate this component, and pay a squared bias term equal to $\sigma_{i}^{2}(M)$. In other words, the right-hand side may be interpreted as an ideal bias-variance trade-off.

The main result of this section is that the matrix Dantzig Selector and matrix Lasso achieve this same ideal bias-variance trade-off to within a constant.

Assume that $\operatorname{rank}(M)\leq r$ and let $\hat{M}_{DS}$ be the solution to the matrix Dantzig selector (1.3) and $\hat{M}_{L}$ be the solution to the matrix Lasso (1.5). Suppose $z$ is a Gaussian error and let $\lambda=16n\sigma$ and $\mu=32n\sigma^{2}$. If $\delta_{4r}<\sqrt{2}-1$, then

and if $\delta_{4r}<(3\sqrt{2}-1)/17$, then

with probability at least $1-2e^{-cn}$ for constants $C_{0}$ and $C_{1}$ (depend only on $\delta_{4r}$).

In other words, not only does nuclear-norm minimization mimic the performance that one would achieve with an oracle that gives the exact column space of $M$ (as in Theorem 2.5), but in fact the error bound is within a constant of what one would achieve by projecting onto the optimal column space corresponding only to the significant singular values.

While a similar result holds in the compressive sensing literature , we derive the result here using a novel technique. We use a middle estimate $\bar{M}$ which is the optimal solution to a certain rank-minimization problem (see Section 3) and is provably near $\hat{M}$ and $M$. With this technique, the proof is a fairly simple extension of Theorem 2.4.

4 Extension to full-rank matrices

In some applications, such as sensor localization, $M$ has exactly low rank, i.e. only the top few of its singular values are nonzero. However, in many applications, such as quantum state tomography, $M$ has full rank, but is well approximated by a low-rank matrix. In this section, we demonstrate an extension of the preceding error bound when $M$ has full rank.

First, suppose $n_{1}\leq n_{2}$ and note that a result of the form

would be impossible when undersampling $M$ because it would imply that as the noise level $\sigma$ approaches zero, an arbitrary full-rank $n\times n$ matrix could be exactly reconstructed from fewer than $n^{2}$ linear measurements. Instead, our result essentially splits $M$ into two parts,

where $\bar{r}\approx m/n$, and $M_{\bar{r}}$ is the best rank-$\bar{r}$ approximation to $M$. The error bound in the theorem reflects a near-optimal bias-variance trade-off in recovering $M_{\bar{r}}$, but an inability to recover $M_{c}$ (and indeed the proof essentially considers $M_{c}$ as non-Gaussian noise). Note that $\bar{r}(n_{1}+n_{2}-\bar{r})$ is of the same order as $m$ so that the part of the matrix which is well recovered has about as many degrees of freedom as the number of measurements. In other words, even in the noiseless case this theorem demonstrates instance optimality i.e. the error bound is proportional to the norm of the part of $M$ that is irrecoverable given the number of measurements (see for an analogous result in compressive sensing). In the noisy case there does not seem to be any current analogue to this error bound in compressive sensing, although the detailed analysis can be translated to the compressive sensing problem and the authors are currently writing a short paper containing this result.

Fix $M$. Suppose that $\mathcal{A}$ is sampled from the Gaussian measurement ensemble with $m\leq c_{0}n^{2}/\log(m/n)$ and let $\bar{r}\leq c_{1}m/n$ for some fixed numerical constants $c_{0}$ and $c_{1}$. Let $\hat{M}$ be the solution to the matrix Dantzig selector $\eqref{eq:ds}$ with $\lambda=16\sqrt{n}\sigma$ or the solution to the matrix Lasso (1.5) with $\mu=32\sqrt{n}\sigma$. Then

with probability greater than $1-De^{-dn}$ for fixed numerical constants $C,D,d>0$. Roughly, the same conclusion extends to operators obeying the NNQ condition, see below.

An interesting note is that in the noiseless case this error bound provides a case of ‘instance optimality’

First note that $\bar{r}$ is small enough so that the RIP holds with high probability (see Lemma 2.3). However, the theorem requires more than just the RIP. The other main requirement is a certain NNQ condition, which holds for Gaussian measurement ensembles and is introduced in Section 3. It is an analogous requirement to the LQ condition introduced by Wojtaszczyk in compressive sensing. To keep the presentation of the Theorem simple, we defer the explanation of the NNQ condition to the proofs section and simply state the theorem for the Gaussian measurement ensemble. However, the proof is not sensitive to the use of this ensemble (for example sub-Gaussian measurements yield the same result). Many generalizations of this Theorem are available and the lemmas necessary to make such generalizations are spelled out in Section 3.

The assumption that $m\leq cn^{2}/\log(m/n)$ seems to be an artifact of the proof technique. Indeed, one would not expect further measurements to negatively impact performance. In fact, when $m\geq c^{\prime}n^{2}$ for a fixed constant $c^{\prime}$, one can use Lemma 3.2 from Section 3 to derive the error bound (2.16) (with high probability), leaving the necessity for a small ‘patch’ in the theory when $cn^{2}/\log(m/n)\leq n\leq c^{\prime}n^{2}$. However, our results intend to address the situation in which $M$ is significantly undersampled, i.e. $m\ll n^{2}$, so the requirement that $m\leq cn^{2}/\log(m/n)$ should be intrinsic to the problem setup.

Proofs

The proofs of several of the theorems use $\epsilon$-nets. For a set $S$, an $\epsilon$-net $S_{\epsilon}$ with respect to a norm $\|\cdot\|$ satisfies the following property: for any $v\in S$, there exists $v_{0}\in S_{\epsilon}$ with $\|v_{0}-v\|\leq\epsilon$. In other words, $S_{\epsilon}$ approximates $S$ to within distance $\epsilon$ with respect to the norm $\|\cdot\|$. As shown in , there always exists an $\epsilon$-net $S_{\epsilon}$ satisfying $S_{\epsilon}\subset S$ and

where $\frac{1}{2}D$ is an $\epsilon/2$ ball (with respect to the norm $\|\cdot\|$) and $S+\frac{1}{2}D=\{x+y:x\in S,y\in\frac{1}{2}D\}$. In particular, if $S$ is a unit ball in $n$ dimensions (with respect to the norm $\|\cdot\|$) or if it is the surface of the unit ball or any other subset of the unit ball, then $S+\frac{1}{2}D$ is contained in the $1+\epsilon/2$ ball, and the thus

where the last inequality follows because we always take $\epsilon\leq 1$. See for a more detailed argument. We will require in all of our proofs that $S_{\epsilon}\subset S$.

We assume that $\sigma=1$ without loss of generality. Put $Z={\cal A}^{*}(z)$. The norm of $Z$ is given by

where the supremum is taken over all pairs of vectors on the unit sphere $S^{n-1}$. Consider a $1/4$-net ${\cal N}_{1/4}$ of $S^{n-1}$ with $|{\cal N}_{1/4}|\leq 12^{n}$. For each $v,w\in S^{n-1}$,

so that by a standard tail bound for Gaussian random variables

which is bounded by $2e^{-cn}$ with $c=\gamma^{2}/2-2\log 12$ (we require $\gamma>2\sqrt{\log 12}$ so that $c>0$).

2 Proof of Theorem 2.3

The proof uses a covering argument, starting with the following lemma.

Proof Recall the SVD $X=U\Sigma V^{*}$ of any $X\in S_{r}$ obeying $\|\Sigma\|_{F}=1$. Our argument constructs an $\epsilon$-net for $S_{r}$ by covering the set of permissible $U,V$ and $\Sigma$. We work in the simpler case where $n_{1}=n_{2}=n$ since the general case is a straightforward modification.

Fix $X\in S_{r}$ and decompose $X$ as $X=U\Sigma V^{*}$ as above. Then there exist $\bar{X}=\bar{U}\bar{\Sigma}\bar{V}^{*}\in\bar{S}_{r}$ with $\bar{U},\bar{V}\in\bar{O}_{n,r}$, $\bar{\Sigma}\in\bar{D}$ obeying $||U-\bar{U}||_{1,2}\leq\epsilon/3,||V-\bar{V}||_{1,2}\leq\epsilon/3$, and $\|\Sigma-\bar{\Sigma}\|_{F}\leq\epsilon/3$. This gives

For the first term, note that since $V$ is an orthogonal matrix, $\|(U-\bar{U})\Sigma V^{*}\|_{F}=\|(U-\bar{U})\Sigma\|_{F}$, and

Hence, $\|(U-\bar{U})\Sigma V^{*}\|_{F}\leq\epsilon/3$. The same argument gives $\|\bar{U}\bar{\Sigma}(V-\bar{V})^{*}\|_{F}\leq\epsilon/3$. To bound the middle term, observe that $\|\bar{U}(\Sigma-\bar{\Sigma})V^{*}\|_{F}=\|\Sigma-\bar{\Sigma}\|_{F}\leq\epsilon/3$. This completes the proof.

We now prove Theorem 2.3. It is a standard argument from this point, and is essentially the same as the proof of Lemma 4.3 in , but we repeat it here to keep the paper self-contained. We begin by showing that $\mathcal{A}$ is an approximate isometry on the covering set $\bar{S}_{r}$. Lemma 3.1 with $\epsilon=\delta/(4\sqrt{2})$ gives

Then it follows from (2.2) together with the union bound that

where $d=c-\frac{\log(36\sqrt{2}/\delta)}{C}$ and we plugged in both requirements $m\geq C(n_{1}+n_{2}+1)r$ and $C>\log(36\sqrt{2}/\delta)/c$.

(which occurs with probability at least $1-C\exp(-dm)$). We begin by showing that the upper bound in the RIP condition holds. Set

For any $X\in S_{r}$, there exists $\bar{X}\in\bar{S}_{r}$ with $\|X-\bar{X}\|_{F}\leq\delta/(4\sqrt{2})$ and, therefore,

Put $\Delta X=X-\bar{X}$ and note that $\operatorname{rank}(\Delta X)\leq 2r$. Write $\Delta X=\Delta X_{1}+\Delta X_{2}$, where $\langle\Delta X_{1},\Delta X_{2}\rangle=0$, and $\operatorname{rank}(\Delta X_{i})\leq r$, $i=1,2$ (for example by splitting the SVD). Note that $\Delta X_{1}/\|\Delta X_{1}\|_{F}$, $\Delta X_{2}/\|\Delta X_{2}\|_{F}\in S_{r}$ and, thus,

Since this holds for all $X\in S_{r}$, we have $\kappa_{r}\leq\kappa_{r}\delta/4+1+\delta/2$ and thus $\kappa_{r}\leq(1+\delta/2)/(1-\delta/4)\leq 1+\delta$ which essentially completes the upper bound. Now that this is established, the lower bound now follows from

which can then be easily translated into the desired version of the RIP bound.

3 Proof of Theorem 2.4

We prove Theorems 2.4, 2.6, and 2.7 for the matrix Dantzig selector (1.3) and describe in Section 3.7 how to extend these proofs to the matrix Lasso. We also assume that we are dealing with square matrices from this point forward ($n=n_{1}=n_{2}$) for notational simplicity; the generalizations of the proofs to rectangular matrices are straightforward.

We begin by a lemma, which applies to full-rank matrices, and contains Theorem 2.4 as a special case.We did not present this lemma in the main portion of the paper because it does not seem to have an intuitive interpretation.

Suppose $\delta_{4r}<\sqrt{2}-1$ and let $M_{r}$ be any rank-r matrix. Let $M_{c}=M-M_{r}$. Suppose $\lambda$ obeys $\|{\cal A}^{*}(z)\|\leq\lambda$. Then the solution $\hat{M}$ to (1.3) obeys

where $C_{0}$ and $C_{1}$ are small constants depending only on the isometry constant $\delta_{4r}$.

We shall use the fact that $\mathcal{A}$ maps low-rank orthogonal matrices to approximately orthogonal vectors.

For all $X$, $X^{\prime}$ obeying $\langle X,X^{\prime}\rangle=0$, and $\operatorname{rank}(X)\leq r$, $\operatorname{rank}(X^{\prime})\leq r^{\prime}$,

Proof This is a simple application of the parallelogram identity. Suppose without loss of generality that $X$ and $X^{\prime}$ have unit Frobenius norms. Then

since $\operatorname{rank}(X\pm X^{\prime})\leq r+r^{\prime}$. We have $\|X\pm X^{\prime}\|_{F}^{2}=\|X\|_{F}^{2}+\|X^{\prime}\|_{F}^{2}=2$ and the parallelogram identity asserts that

The proof of Lemma 3.2 parallels that of Candès and Tao about the recovery of nearly sparse vectors from a limited number of measurements . It is also inspired by the work of Fazel, Recht, Candès and Parrilo . Set $H=\hat{M}-M$ and observe that by the triangle inequality,

since $M$ is feasible for the problem (1.3). Decompose $H$ as

where $\operatorname{rank}(H_{0})\leq 2r$, $M_{r}H_{c}^{*}=0$ and $M_{r}^{*}H_{c}=0$ (see ). We have

Since by definition, $\|M+H\|_{*}\leq\|M\|_{*}\leq\|M_{r}\|_{*}+\|M_{c}\|_{*}$, this gives

Next, we use a classical estimate developed in (see also ). Let $H_{c}=U\textrm{diag}(\vec{\sigma})V^{*}$ be the SVD of $H_{c}$, where $\vec{\sigma}$ is the list of ordered singular values (not to be confused with the noise standard deviation). Decompose $H_{c}$ into a sum of matrices $H_{1},H_{2},\ldots$, each of rank at most $2r$ as follows. For each $i$ define the index set $I_{i}=\{2r(i-1)+1,...,2ri\}$, and let $H_{i}:=U_{I_{i}}\textrm{diag}(\vec{\sigma}_{I_{i}})V_{I_{i}}^{*}$; that is, $H_{1}$ is the part of $H_{c}$ corresponding to the $2r$ largest singular values, $H_{2}$ is the part corresponding to the next $2r$ largest and so on. A now standard computation shows that

since $\|H_{0}\|_{*}\leq\sqrt{2r}\,\|H_{0}\|_{F}$ by Cauchy-Schwarz.

Now the restricted isometry property gives

To see why this is true, let $U\Sigma V^{*}$ be the reduced SVD of $H_{0}+H_{1}$ in which $U$ and $V$ are $n\times r^{\prime}$, and $\Sigma$ is $r^{\prime}\times r^{\prime}$ with $r^{\prime}=\operatorname{rank}(H_{0}+H_{1})\leq 4r$. We have

The claim follows from $\|U^{*}[{\cal A}^{*}{\cal A}(H)]V\|_{F}\leq\sqrt{r^{\prime}}\|{\cal A}^{*}{\cal A}(H)\|$, which holds since $U^{*}[{\cal A}^{*}{\cal A}(H)]V$ is an $r^{\prime}\times r^{\prime}$ matrix with spectral norm bounded by $\|{\cal A}^{*}{\cal A}(H)\|$. Second, Lemma 3.3 implies that for $j\geq 2$

and similarly with $H_{1}$ in place of $H_{0}$. Note that because $H_{0}$ is orthogonal to $H_{1}$, we have that $\|H_{0}+H_{1}\|_{F}^{2}=\|H_{0}\|_{F}^{2}+\|H_{1}\|_{F}^{2}$ and thus $\|H_{0}\|_{F}+\|H_{1}\|_{F}\leq\sqrt{2}\|H_{0}+H_{1}\|_{F}$. This gives

Taken together, (3.9), (3.10) and (3.12) yield

provided that $C_{1}>0$. Our claim (2.4) then follows from (3.6) together with

4 Proof of Theorem 2.4

Theorem 2.4 follows by simply plugging $M_{r}=M$ into Theorem 3.2. To generalize the results, note that there are only two requirements on $M,\mathcal{A}$ and $y$ used in the proof.

$\|\mathcal{A}^{*}(\mathcal{A}(M)-y)\|\leq\lambda$

$\operatorname{rank}(M)=r$ and $\delta_{4r}<\sqrt{2}-1$.

Thus, the steps above also prove the following Lemma which is useful in proving Theorem 2.6.

Assume that $X$ is of rank at most $r$ and that $\delta_{4r}<\sqrt{2}-1$. Suppose $\lambda$ obeys $\|{\cal A}^{*}(y-\mathcal{A}(X))\|\leq\lambda$. Then the solution $\hat{M}$ to (1.3) obeys

where $C_{0}$ is a small constant depending only on the isometry constant $\delta_{4r}$.

5 Proof of Theorem 2.6

In this section, $\lambda=16n\sigma^{2}$ and we take as given that $\|\mathcal{A}^{*}(z)\|\leq\lambda/2$ (and thus, by Lemma 1.1, the end result holds with probability at least $1-2e^{-cn}$). The novelty in this proof – the way it differs from analogous proofs in compressive sensing – is in the use of a middle estimate $\bar{M}$. Define $K$ as

and let $\bar{M}=\text{argmin}_{X}K(X,M)$. In words, $\bar{M}$ achieves a compromise between goodness of fit and parsimony in the model with noiseless data. The factor $\gamma$ could be replaced by $\lambda^{2}$, but the derivations are cleanest in the present form. We begin by bounding the distance between $M$ and $\bar{M}$ using the RIP, and obtain

where the use of the isometry constant $\delta_{2r}$ follows from the fact that $\operatorname{rank}(\bar{M})\leq\operatorname{rank}(M)$.

i.e. $\bar{M}$ is feasible for (1.3). Also, $\operatorname{rank}(\bar{M})\leq\operatorname{rank}(M)$ and, thus, plugging $\bar{M}$ into Lemma 3.4 gives

where $C^{\prime}=\max(8C(1+\delta_{1}),2/(1-\delta_{2r}))$.

Now $\bar{M}$ is the minimizer of $K(\cdot;M)$, and so $K(\bar{M};M)\leq K(M_{0};M)$, where

In conclusion, the proof follows from $\lambda=16n\sigma^{2}$ since

6 Proof of Theorem 2.7

Three useful lemmas are established in the course of the proof of this more involved result, and we would like to point out that these can be used as powerful error bounds themselves. Throughout the proof, $C$ is a constant that may depend on $\delta_{4r}$ only, and whose value may change from line to line. An important fact to keep in mind is that under the assumptions of the theorem, $\delta_{4\bar{r}}$ can be bounded, with high probability, by an arbitrarily small constant depending on the size of the scalar $c_{1}$ appearing in the condition $\bar{r}\leq c_{1}m/n$. This is a consequence of Theorem 2.3. In particular, $\delta_{4\bar{r}}\leq(\sqrt{2}-1)/2$ with probability at least $1-De^{-dm}$.

Let $\bar{M}$ and $M_{0}$ be defined via (3.14) and (3.17), and set

Suppose that $\delta_{4r}<\sqrt{2}-1$ and that $\lambda$ obeys $\|{\cal A}^{*}(z)\|\leq\lambda/2$. Then the solution $\hat{M}$ to (1.3) obeys

where $C_{0}$ is a small constant depending only on the isometry constant $\delta_{4r}$.

Proof The proof is essentially the same as that of Theorem 2.6, and so we quickly go through the main steps. Set $M_{c}=M-M_{0}$ so that $M_{c}$ only contains the singular values below the noise level. First,

Second, we bound $\|\hat{M}-\bar{M}\|_{F}$ using the exact same steps as in the proof of Theorem 2.6, and obtain

Finally, use $K(\bar{M};M)\leq K(M_{0};M)$ as before, and simplify to attain (3.18).

with probability at least $1-De^{-cm}$ for fixed constants $D,c$. An important point here is that this inequality only holds (with high probability) when $M_{c}$ is fixed, and $\mathcal{A}$ is chosen randomly (independently). In the worst-case-scenario, one could have

where $\|\mathcal{A}\|$ is the operator norm of $\mathcal{A}$. Thus we emphasize that the bound holds with high probability for a given $M$ verifying our conditions, but may not hold uniformly over all such $M$’s.

Returning to the proof, (3.24) together with

Fix $M$ and suppose $\mathcal{A}$ obeys (2.2). Then under the assumptions of Lemma 3.6, the solution $\hat{M}$ to (1.3) obeys

with probability at least $1-De^{-cn}$ where $C_{0}$ is a small constant depending only on the isometry constant $\delta_{4r}$, and $c$, $D$ are fixed constants.

The above two lemmas require a bound on the rank of $M_{0}$. However, as the noise level approaches zero, the rank of $M_{0}$ approaches the rank of $M$, which can be as large as the dimension. This requires further analysis, and in order to provide theoretical error bounds when the noise level is low (and $M$ has full rank, say), a certain property of many measurement operators is useful. We call it the NNQ property, and is inspired by a similar property from compressive sensing, see .

Suppose $\mathcal{A}$ is a Gaussian measurement ensemble and $m\leq Cn^{2}/\log(m/n)$ for some fixed constant $C>0$. Then $\mathcal{A}$ satisfies $\text{NNQ}(\mu\sqrt{n/m})$ with probability at least $1-3e^{-cn}$ for fixed constants $c$ and $\mu$.

where $u,v$ are the left and right singular vectors of $\mathcal{A}^{*}(\bar{x}-x)$ corresponding to the top singular value. Then

assuming $\delta_{1}\leq 1$ (this occurs with probability at least $1-2e^{-cn}$ when $m\geq Cn$ for fixed constants $c,C$).

We will provide the contradiction by showing that with high probability, $\|\mathcal{A}^{*}(\bar{x})\|>3\alpha$, for all $\bar{x}\in\bar{B}_{*}^{n\times n}$. For each $\bar{x}$, $\mathcal{A}^{*}(\bar{x})$ is equal in distribution to $\frac{1}{\sqrt{m}}Z$, where $Z$ is a matrix with i.i.d. standard normal entries. Let $Z_{i}$ be the $i$th column of $Z$. Then

where $c=(1-9\mu^{2})^{2}/4$ (we require $\mu<1/3$ here). Thus, by the union bound,

provided that $m\leq Cn^{2}/\log(m/n)$ for fixed constants, $C,c^{\prime}$. The theorem is established.

Note that the preceding proof can be repeated when $\mathcal{A}$ is a sub-Gaussian measurement ensemble; the only difference is that $Z$ above will contain sub-Gaussian entries, rather than Gaussian entries.

Using the NNQ property, we can now bound the error when the noise level is low; this does not involve any condition on the rank of $M_{0}$, and does not involve a term in the bound depending on $||M-M_{0}||_{*}$.

Suppose that $\mathcal{A}$ satisfies NNQ($\mu\sqrt{n/m}$) for a fixed constant $\mu$ and that $\|\mathcal{A}^{*}(z)\|\leq\lambda$. Let $\bar{r}\geq cm/n$ for some fixed numerical constant $c$, and suppose that that $\delta_{4\bar{r}}\leq\frac{1}{2}(\sqrt{2}-1)$. Let

Let $\hat{M}$ be the solution to $\eqref{eq:ds}$. Then

Proof Set $M_{c}=M-M_{\bar{r}}=\sum_{i=\bar{r}+1}^{n}\sigma_{i}(M)u_{i}v_{i}^{*}$. The $\text{NNQ}(\alpha)$ property with $\alpha=\mu\sqrt{n/m}$ gives

Inserting this into (3.23) completes the proof of the lemma.

We are now in position to prove our main theorem concerning the recovery of matrices with decaying singular values (Theorem 2.7). There are three cases to consider depending on the number of singular values of $M$ standing above the noise level. In each case, we need the inequality

which holds with probability at least $1-De^{-cn}$ for any measurement ensemble satisfying $\eqref{eq:concentration}$ (including the Gaussian measurement ensemble). Put $\lambda=16n\sigma^{2}$ and recall the definition of $M_{0}$:

whose rank is exactly the number of singular values of $M$ above the noise level. There are three cases to consider depending mostly on the interplay between the singular values of $M$ and the noise level.

Case 1: high noise level

Suppose $K(M_{0};M)\leq\frac{\lambda^{2}}{4(1+\delta_{1})}\bar{r}$. Then $\operatorname{rank}(M_{0})\leq\bar{r}$ and $\operatorname{rank}(\bar{M})\leq\bar{r}$ by definition of $\bar{M}$. Hence, Lemma 3.7 gives

Case 2: low noise level

Suppose $K(M_{0};M)>\frac{\lambda^{2}}{4(1+\delta_{1})}\bar{r}$ and $\operatorname{rank}(M_{0})\geq\bar{r}$. It follows from (2.2) that

with probability at least $1-De^{-cn}$. Now, for the Gaussian measurement ensemble, the requirements of Lemma 3.10 are met with probability at least $1-Ce^{-cn}$. Combining (3.25) with Lemma 3.10 yields

Since $\lambda=16n\sigma^{2}$, this is (3.23).

Case 3: medium noise level

Suppose $K(M_{0};M)>\frac{\lambda^{2}}{4(1+\delta_{1})}\bar{r}$ and $\operatorname{rank}(M_{0})<\bar{r}$. As in Case 2, we have

From $\lambda^{2}\bar{r}<4(1+\delta_{1})K(M_{0};M)$, it follows that

These three cases comprise all possibilities. In short, the proof of Theorem 2.7 is complete.

7 Extension of proofs to the solution to the Lasso (1.5)

In the sparse regression setup, Bickel et al. showed that the Dantzig Selector and the Lasso have analogous properties, leading to analogous error bounds. The analogies still hold in the low-rank matrix recovery problem (for similar reasons). In fact, all of the theorems above also hold for the solution to (1.5) aside from a shift in those constants appearing in the assumptions, and those appearing in the error bounds. To see this, note that our proofs only used two crucial properties about $\hat{M}$:

$\|\mathcal{A}^{*}(\mathcal{A}(\hat{M})-y)\|\leq\lambda$.

The second property automatically holds for the solution to (1.5) (but with $\lambda$ replaced by $\mu$). This follows from the optimality conditions which states that $\mathcal{A}^{*}(y-\mathcal{A}(\hat{M}))\in\partial\|\hat{M}\|_{*}$ where $\|\hat{M}\|_{*}$ is the family of subgradients to the nuclear norm at the minimizer. Formally, let $U\Sigma V^{*}$ be the SVD of $\hat{M}$, then

for some $W$ obeying $\|W\|\leq 1$ and $U^{*}W=0,WV=0$ (see e.g. ). Hence, the second property follows from $\|UV^{*}+W\|\leq 1$.

The first property does not necessarily hold for the matrix Lasso, but a close enough approximation is verified (this is analogous to an argument made in ). Suppose that $\|\mathcal{A}^{*}(z)\|\leq c_{0}\mu$ for a small constant $c_{0}$ (which, by Lemma 1.1, holds with high probability for Gaussian noise if $\mu=Cn\sigma^{2}$). Then since $\hat{M}$ minimizes (1.5), we have

Plug in $y=\mathcal{A}(M)+z$ and rearrange terms to give

Since the nuclear norm and the operator norm are dual to each other, we have $\langle\hat{M}-M,\mathcal{A}^{*}(z)\rangle\leq||\hat{M}-M||_{*}\cdot\|\mathcal{A}^{*}(z)\|\leq c_{0}\mu||H||_{*}$, where we use the notation $H=\hat{M}-M$ as in the proof of Lemma 3.2. This gives

which nearly is the first property. When $c_{0}$ is chosen to be a small constant, this factor has no essential detrimental effects on the proof. In particular, (3.7) in the proof of Lemma 3.2 is replaced by

8 Proof of Theorem 2.5

Let $\lambda_{i}(A^{*}A)$ be the eigenvalues of the matrix $A^{*}A$. Then

In particular, if one of the eigenvalues vanishes (as in the case in which $m<n$), then the minimax risk is unbounded.

Proof Suppose first that $A$ is the identity matrix. Then it is well known that the minimax risk is $n\sigma^{2}$ and is achieved by $\hat{x}=y$. To see this, recall that for any prior on $x$, the minimax risk is lower bounded by the Bayes risk. Consider then the prior which assumes that all the components of $x$ are i.i.d. ${\cal N}(0,\tau^{2})$. Then the Bayes’ estimator for this prior is the shrinkage estimate given by

Clearly, as $\tau\rightarrow\infty$, the lower bound on the minimax risk goes to $n\sigma^{2}$. Since this quantity is the risk of the maximum-likelihood estimate $y$, this proves the claim. Note that by a simple rescaling argument, this also proves that the minimax risk for estimating $x$ from $y_{i}=d_{i}x_{i}+z_{i}$ is $\sum_{i=1}^{n}1/d^{2}_{i}$.

We can now prove (3.27). We will assume that $m\geq n$ for simplicity since for $m<n$, the minimax risk is unbounded. Let $U\Sigma V^{*}$ be the SVD of $A$, where $U$ is $m\times n$, $\Sigma$ is $n\times n$ and $V$ is $n\times n$. All the information about $x$ is in $U^{*}y$, and so we may just assume that the data is given by

Now $z^{\prime}=U^{*}z$ is a Gaussian vector with i.i.d. ${\cal N}(0,\sigma^{2})$ components. Further, set $x^{\prime}=V^{*}x$. Since $V$ is an orthogonal matrix, the minimax risk for estimating $x$ or $x^{\prime}$ is the same and, therefore, our problem is that of computing the minimax risk for estimating $x^{\prime}$ from

Since $\Sigma$ is a diagonal matrix with diagonal elements $\sqrt{\lambda_{i}(A^{*}A)}$, our previous result applies and establishes (3.27).

We are now in position to prove Theorem 2.5. The set of rank-$r$ matrices is (much) larger than the set of matrices of the form

where $U$ is a fixed orthogonal $n\times r$ matrix with orthonormal columns (note that the matrices of this form have a fixed $r$-dimensional column space). Thus,

Knowing that $M=UR$ for some unknown $r\times n$ matrix $R$, one can of course limit ourselves to estimators of the form $\hat{M}=U\hat{R}$, and since

the minimax risk is lower bounded that by of estimating $R$ from the data

where ${\cal A}_{U}$ is the linear map (2.11). We then apply Lemma 3.11 to conclude that the minimax rate is lower bounded by

The claim follows from the simple lemma below.

Let $U$ be an $n\times r$ matrix with orthonormal columns. Then all the eigenvalues of ${\cal A}_{U}^{*}{\cal A}_{U}$ belong to the interval $[1-\delta_{r},1+\delta_{r}]$.

and similarly for $\lambda_{\text{max}}({\cal A}_{U}^{*}{\cal A}_{U})$ with a $\sup$ in place of $\inf$. Since

which is valid since $\operatorname{rank}(UR)\leq r$ together with $\|UR\|_{F}^{2}=\|R\|_{F}^{2}$.

Discussion

Using RIP-based analysis, this paper has shown that low-rank matrices can be stably recovered via nuclear-norm minimization from nearly the minimal possible number of linear samples. Further, the error bound is within a constant of the expected minimax error, and of an expected oracle error, and extends to the case when $M$ has full rank.

This work differs from the main thrust of the recent literature on low-rank matrix recovery, which has concentrated on the ‘RIPless’ matrix completion problem. An interesting observation regarding matrix completion is that when the measurements are randomly chosen entries of $M$, one requires at least about $nr\log n$ measurements to recover $M$ by any method when $\operatorname{rank}(M)=O(1)$ . In contrast, this paper shows that on the order of $nr$ measurements are enough provided these are sufficiently random.

The popularity of the matrix completion model stems from the fact that this setup currently dominates the applications of low-rank matrix recovery. There are far fewer applications in which the measurements are random linear combinations of many entries of $M$ (quantum-state tomography is a notable application though). As a great deal of attention is given to low-rank matrix modeling these days, with new applications being discovered all the time, this may change rapidly. We hope that our theory encourages further applications and research in this direction.

References