Estimation of (near) low-rank matrices with noise and high-dimensional scaling

Introduction

This initial set of results, though appealing in terms of their simple statements and generality, are somewhat abstractly formulated. Our next contribution is to show that by specializing our main result (Theorem 1) to three classes of models, we can obtain some concrete results based on readily interpretable conditions. In particular, Corollary 3 deals with the case of low-rank multivariate regression, relevant for applications in multitask learning. We show that the random operator $\mathfrak{X}$ satisfies the RSC property for a broad class of observation models, and we use random matrix theory to provide an appropriate choice of the regularization parameter. Our next result, Corollary 4, deals with the case of estimating the matrix of parameters specifying a vector autoregressive (VAR) process . Here we also establish that a suitable RSC property holds with high probability for the random operator $\mathfrak{X}$, and also specify a suitable choice of the regularization parameter. We note that the technical details here are considerably more subtle than the case of low-rank multivariate regression, due to dependencies introduced by the autoregressive sampling scheme. Accordingly, in addition to terms that involve the size, the matrix dimensions and rank, our bounds also depend on the mixing rate of the VAR process. Finally, we turn to the compressed sensing observation model for low-rank matrix recovery, as introduced by Recht et al. . In this setting, we again establish that the RSC property holds with high probability, specify a suitable choice of the regularization parameter, and thereby obtain a Frobenius error bound for noisy observations (Corollary 5). A technical result that we prove en route—namely, Proposition 1—is of possible independent interest, since it provides a bound on the constrained norm of a random Gaussian operator. In particular, this proposition allows us to obtain a sharp result (Corollary 6) for the problem of recovering a low-rank matrix from perfectly observed random projections, one that removes a logarithmic factor from past work .

The remainder of this paper is organized as follows. Section 2 is devoted to background material, and the set-up of the problem. We present a generic observation model for low-rank matrices, and then illustrate how it captures various cases of interest. We then define the convex program based on nuclear norm regularization that we analyze in this paper. In Section 3, we state our main theoretical results and discuss their consequences for different model classes. Section 4 is devoted to the proofs of our results; in each case, we break down the key steps in a series of lemmas, with more technical details deferred to the appendices. In Section 5, we present the results of various simulations that illustrate excellent agreement between the theoretical bounds and empirical behavior.

Background and problem set-up

We begin with some background on problems and applications in which rank constraints arise, before describing a generic observation model. We then introduce the semidefinite program (SDP) based on nuclear norm regularization that we study in this paper.

where $\{W_{a}\}_{a=1}^{n}$ is an i.i.d. sequence of $k$-dimensional zero-mean noise vectors. Given a collection of observations $\{Z_{a},Y_{a}\}_{a=1}^{n}$ of covariate-output pairs, our goal is to estimate the unknown matrix $\Theta^{*}$. This type of model has been used in many applications, including analysis of fMRI image data , analysis of EEG data decoding , neural response modeling and analysis of financial data. This model and closely related ones also arise in the problem of collaborative filtering , in which the goal is to predict users’ preferences for items (such as movies or music) based on their and other users’ ratings of related items. The papers discuss additional instances of low-rank decompositions. In all of these settings, the low-rank condition translates into the existence of a smaller set of “features” that are actually controlling the prediction.

2 A generic observation model

which is specified by the sequence of observation matrices $\{X_{i}\}_{i=1}^{N}$ and observation noise $\{\varepsilon_{i}\}_{i=1}^{N}$. This observation model can be written in a more compact manner using operator-theoretic notation. In particular, let us define the observation vector

Let us illustrate the form of the observation model (5) for some of the applications that we considered earlier.

By re-indexing this collection of $N=nk$ observations via the mapping $(a,b)\mapsto i=a+(b-1)\,k$, we recognize multivariate regression as an instance of the observation model (4) with observation matrix $X_{i}=Z_{a}e_{b}^{T}$ and scalar observation $y_{i}=V_{ab}$.

Recall that a vector autoregressive (VAR) process is defined by the recursion (2), and suppose that observe an $n$-sequence $\{Z_{t}\}_{t=1}^{n}$ produced by this recursion. Since each $Z_{t}=\begin{bmatrix}Z_{t1}&\ldots&Z_{tp}\end{bmatrix}^{T}$ is $p$-variate, the scalarized sample size is $N=np$. Letting $b=1,2,\ldots,p$ index the dimension, we have

In this case, we re-index the collection of $N=np$ observations via the mapping $(t,b)\mapsto i=t+(b-1)\,p$. After doing so, we see that the autoregressive problem can be written in the form (4) with $y_{i}=Z_{(t+1)\,b}$ and observation matrix $X_{i}=Z_{t}e_{b}^{T}$.

3 Regression with nuclear norm regularization

where $\lambda_{N}>0$ is a regularization parameter. Note that the optimization problem (9) can be viewed as the analog of the Lasso estimator , tailored to low-rank matrices as opposed to sparse vectors. An important property of the optimization problem (9) is that it can be solved in time polynomial in the sample size $N$ and the matrix dimensions $k$ and $p$. Indeed, the optimization problem (9) is an instance of a semidefinite program , a class of convex optimization problems that can be solved efficiently by various polynomial-time algorithms . For instance, interior point methods are a classical method for solving semidefinite programs; moreover, as we discuss in Section 5, there are a variety of other methods for solving the semidefinite program (SDP) defining our $M$-estimator

Like in any typical $M$-estimator for statistical inference, the regularization parameter $\lambda_{N}$ is specified by the statistician. As part of the theoretical results in the next section, we provide suitable choices of this parameter in order for the estimate $\widehat{\Theta}$ to behave well, in the sense of being close in Frobenius norm to the unknown matrix $\Theta^{*}$.

Main results and some consequences

In this section, we state our main results and discuss some of their consequences. Section 3.1 is devoted to results that apply to generic instances of low-rank problems, whereas Section 3.2 is devoted to the consequences of these results for more specific problem classes, including low-rank multivariate regression, estimation of vector autoregressive processes, and recovery of low-rank matrices from random projections.

We note that analogous conditions have been used to establish error bounds in the context of sparse linear regression , in which case the set $\mathcal{C}$ corresponded to certain subsets of sparse vectors.

With this notation, we come to the first result of our paper. It is a deterministic result, which specifies two conditions—namely, an RSC condition and a choice of the regularizer—that suffice to guarantee for any solution of the SDP (9) fall within a certain radius.

Suppose that the operator $\mathfrak{X}$ satisfies restricted strong convexity with parameter $\kappa(\mathfrak{X})>0$ over the set $\mathcal{C}(r;\delta)$, and that the regularization parameter $\lambda_{N}$ is chosen such that $\lambda_{N}\geq 2|\!|\!|\mathfrak{X}^{*}(\vec{\varepsilon})|\!|\!|_{{\operatorname{op}}}/N$. Then any solution $\widehat{\Theta}$ to the semidefinite program (9) satisfies

Apart from the tolerance parameter $\delta$, the two main terms in the bound (14) have a natural interpretation. The first term (involving $\sqrt{r}$) corresponds to estimation error, capturing the difficulty of estimating a rank $r$ matrix. The second is an approximation error, in which the projection onto the set $\mathcal{M}^{\perp}(U^{r},V^{r})$ describes the gap between the true matrix $\Theta^{*}$ and the rank $r$ approximation.

Let us begin by illustrating the consequences of Theorem 1 when the true matrix $\Theta^{*}$ has exactly rank $r$, in which case there is a very natural choice of the subspaces represented by $U$ and $V$. In particular, we form $U$ from the $r$ non-zero left singular vectors of $\Theta^{*}$, and $V$ from its $r$ non-zero right singular vectors. Note that this choice of $(U,V)$ ensures that $\Pi_{\mathcal{M}^{\perp}(U,V)}(\Theta^{*})=0$. For technical reasons to be clarified, it suffices to set $\delta=0$ in the case of exact rank constraints, and we thus obtain the following result:

Suppose that $\Theta^{*}$ has rank $r$, and $\mathfrak{X}$ satisfies RSC with respect to $\mathcal{C}(r;0)$. Then as long as $\lambda_{N}\geq 2|\!|\!|\mathfrak{X}^{*}(\vec{\varepsilon})|\!|\!|_{{\operatorname{op}}}/N$, any optimal solution $\widehat{\Theta}$ to the SDP (9) satisfies the bound

Like Theorem 1, Corollary 1 is a deterministic statement on the SDP error. It takes a much simpler form since when $\Theta^{*}$ is exactly low rank, then neither tolerance parameter $\delta$ nor the approximation term are required.

As a more delicate example, suppose instead that $\Theta^{*}$ is nearly low-rank, an assumption that we can formalize by requiring that its singular value sequence $\{\sigma_{i}(\Theta^{*})\}_{i=1}^{\min\{k,p\}}$ decays quickly enough. In particular, for a parameter $q\in$ and a positive radius $R_{q}$, we define the set

Note that the error bound (17) reduces to the exact low rank case (15) when $q=0$, and $\delta=0$. The quantity $\lambda_{N}^{-q}R_{q}$ acts as the “effective rank” in this setting; as clarified by our proof in Section 4.2. This particular choice is designed to provide an optimal trade-off between the approximation and estimation error terms in Theorem 1. Since $\lambda_{N}$ is chosen to decay to zero as the sample size $N$ increases, this effective rank will increase, reflecting the fact that as we obtain more samples, we can afford to estimate more of the smaller singular values of the matrix $\Theta^{*}$.

2 Results for specific model classes

As stated, Corollaries 1 and 2 are fairly abstract in nature. More importantly, it is not immediately clear how the key underlying assumption—namely, the RSC condition—can be verified, since it is specified via subspaces that depend on $\Theta^{*}$, which is itself the unknown quantity that we are trying to estimate. Nonetheless, we now show how, when specialized to more concrete models, these results yield concrete and readily interpretable results. As will be clear in the proofs of these results, each corollary requires overcoming two main technical obstacles: establishing that the appropriate form of the RSC property holds in a uniform sense (so that a priori knowledge of $\Theta^{*}$ is not required), and specifying an appropriate choice of the regularization parameter $\lambda_{N}$. Each of these two steps is non-trivial, requiring some random matrix theory, but the end results are simply stated upper bounds that hold with high probability.

with probability greater than $1-c_{2}\exp(-c_{3}(k+p))$.

Remarks: Corollary 3 takes a particularly simple form when $\Sigma=I_{p\times p}$: then there exists a constant $c^{\prime}_{1}$ such that |\!|\!|\widehat{\Theta}-\Theta^{*}|\!|\!|_{{F}}^{2}\leq c^{\prime}_{1}\nu^{2}\>R_{q}\;\big{(}\frac{k+p}{n}\big{)}^{1-q/2}. When $\Theta^{*}$ is exactly low rank—that is, $q=0$, and $\Theta^{*}$ has rank $r=R_{0}$—this simplifies even further to

The scaling in this error bound is easily interpretable: naturally, the squared error is proportional to the noise variance $\nu^{2}$, and the quantity $r(k+p)$ counts the number of degrees of freedom of a $k\times p$ matrix with rank $r$. Note that if we did not impose any constraints on $\Theta^{*}$, then since a $k\times p$ matrix has a total of $kp$ free parameters, we would expect at best to obtain rates of the order $|\!|\!|\widehat{\Theta}-\Theta^{*}|\!|\!|_{{F}}^{2}=\Omega(\frac{\nu^{2}\,k\,p}{n})$. Note that when $\Theta^{*}$ is low rank—in particular, when $r\ll\min\{k,p\}$—then the nuclear norm estimator achieves substantially faster rates. Finally, we note that as stated, the result requires that $\min\{k,p\}$ tend to infinity in order for the claim to hold with high probability. Although such high-dimensional scaling is the primary focus of this paper, we note that for application to the classical setting of fixed $(k,p)$, the same statement (with different constants) holds with $k+p$ replaced by $\log n$.

Next we turn to the case of estimating the system matrix $\Theta^{*}$ of an autoregressive (AR) model, as discussed in Example 2.

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

Remarks: Like Corollary 3, the result as stated requires that $p$ tend to infinity, but the same bounds hold with $p$ replaced by $\log n$, yielding results suitable for classical (fixed dimension) scaling. Second, the factor $(p/n)^{1-q/2}$, like the analogous termThe term in Corollary 3 has a factor $k+p$, since the matrix in that case could be non-square in general. in Corollary 3, shows that faster rates are obtained if $\Theta^{*}$ can be well-approximated by a low rank matrix, namely for choices of the parameter $q\in$ that are closer to zero. Indeed, in the limit $q=0$, we again reduce to the case of an exact rank constraint $r=R_{0}$, and the corresponding squared error scales as $rp/n$. In contrast to the case of multivariate regression, the error bound (19) also depends on the upper bound $|\!|\!|\Theta^{*}|\!|\!|_{{\operatorname{op}}}=\gamma<1$ on the operator norm of the system matrix $\Theta^{*}$. Such dependence is to be expected since the quantity $\gamma$ controls the (in)stability and mixing rate of the autoregressive process. As clarified in the proof, the dependence of the sampling in the AR model also presents some technical challenges not present in the setting of multivariate regression.

with probability greater than $1-c_{1}\exp(-c_{2}(k+p))$.

The central challenge in proving this result is in proving an appropriate form of the RSC property. The following result on the random operator $\mathfrak{X}$ may be of independent interest here:

Under the stated conditions, the random operator $\mathfrak{X}$ satisfies

with probability at least $1-2\exp(-N/32)$.

The proof of this result, provided in Appendix D, makes use of the Gordon-Slepian inequalities for Gaussian processes, and concentration of measure. As we show in Section 4.5, it implies the form of the RSC property needed to establish Corollary 5.

Proposition 1 also implies an interesting property of the null space of the operator $\mathfrak{X}$; one that can be used to establish a corollary about recovery of low-rank matrices when the observations are noiseless. In particular, suppose that we are given the noiseless observations $y_{i}=\langle\!\langle{X_{i}},\;{\Theta^{*}}\rangle\!\rangle$ for $i=1,\ldots,N$, and that we try to recover the unknown matrix $\Theta^{*}$ by solving the SDP

a recovery procedure that was studied by Recht et al. . Proposition 1 allows us to obtain a sharp result on recovery using this method:

Suppose that $\Theta^{*}$ has rank $r$, and that we are given $N>40^{2}r(k+p)$ noiseless samples. Then with probability at least $1-2\exp(-N/32)$, the SDP (22) recovers the matrix $\Theta^{*}$ exactly.

This result removes some extra logarithmic factors that were included in the earlier work , and provides the appropriate analog to compressed sensing results for sparse vectors . Note that (like in most of our results) we have made little effort to obtain good constants in this result: the important property is that the sample size $N$ scales linearly in both $r$ and $k+p$.

Proofs

We now turn to the proofs of Theorem 1, and Corollaries 1 through 6. In each case, we provide the primary steps in the main text, with more technical details stated as lemmas and proved in the Appendix.

By the optimality of $\widehat{\Theta}$ for the SDP (9), we have

Defining the error matrix $\Delta=\Theta^{*}-\widehat{\Theta}$ and performing some algebra yields the inequality

By definition of the adjoint and Hölder’s inequality, we have

By the triangle inequality, we have $|\!|\!|\widehat{\Theta}+\Delta|\!|\!|_{{1}}-|\!|\!|\widehat{\Theta}|\!|\!|_{{1}}\leq|\!|\!|\Delta|\!|\!|_{{1}}$. Substituting this inequality and the bound (24) into the inequality (23) yields

where the second inequality makes use of our choice $\lambda_{N}\geq\frac{2}{N}|\!|\!|\mathfrak{X}^{*}(\vec{\varepsilon})|\!|\!|_{{\operatorname{op}}}$.

It remains to lower bound the term on the left-hand side, while upper bounding the quantity $|\!|\!|\Delta|\!|\!|_{{1}}$ on the right-hand side. The following technical result allows us to do so. Recall our earlier definition (11) of the sets $\mathcal{M}$ and $\mathcal{M}^{\perp}$ associated with a given subspace pair.

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

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

If $\lambda_{N}\geq 2|\!|\!|\mathfrak{X}^{*}(\vec{\varepsilon})|\!|\!|_{{2}}/N$, then the nuclear norm of $\Delta^{\prime\prime}$ is bounded as

See Appendix A for the proof of this claim. Using Lemma 1, we can complete the proof of the theorem. In particular, from the bound (25) and the RSC assumption, we find that

Using the triangle inequality together with inequality (25), we obtain

From the rank constraint in Lemma 1(a), we have $|\!|\!|\Delta^{\prime}|\!|\!|_{{1}}\leq\sqrt{2r}|\!|\!|\Delta^{\prime}|\!|\!|_{{F}}$. Putting together the pieces, we find

2 Proof of Corollary 2

On the other hand, we also have $R_{q}\,\geq\;\sum_{i=1}^{m}|\sigma_{i}(\Theta^{*})|^{q}\;\geq\;|K|\,\tau^{q}$, which implies that $|K|\leq\tau^{-q}\,R_{q}$. From the general error bound with $r=|K|$, we obtain

Setting $\tau=\lambda_{N}/\kappa$ yields that

3 Proof of Corollary 3

For the proof of this corollary, we adopt the following notation. We first define the three matrices

With this notation and using the relation $N=nk$, the SDP objective function (9) can be written as \frac{1}{k}\big{\{}\frac{1}{2n}|\!|\!|Y-X\Theta|\!|\!|_{{F}}^{2}+\lambda_{n}|\!|\!|\Theta|\!|\!|_{{1}}\big{\}}, where we have defined $\lambda_{n}=\lambda_{N}\,k$.

In order to establish the RSC property for this model, some algebra shows that we need to establish a lower bound on the quantity

where $\sigma_{\operatorname{min}}$ denotes the minimum eigenvalue. The following lemma follows by adapting known concentration results for random matrices (see the paper for details):

As a consequence, we have $\frac{\sigma_{\operatorname{min}}(X^{T}X)}{2n}\geq\frac{\sigma_{\operatorname{min}}(\Sigma)}{18}$ with probability at least $1-4\exp(-n)$ for all $n\geq p$, which establishes that the RSC property holds with $\kappa(\mathfrak{X})=\frac{1}{20}\sigma_{\operatorname{min}}(\Sigma)$.

Next we need upper bound the quantity $|\!|\!|\mathfrak{X}^{*}(\vec{\varepsilon})|\!|\!|_{{2}}$ for this model, so as to verify that the stated choice for $\lambda_{N}$ is valid. Following some algebra, we find that

The following lemma is proved in Appendix B:

Using these two lemmas, we can complete the proof of Corollary 3. First, recalling the scaling $N=kn$, we see that Lemma 3 implies that the choice $\lambda_{N}=10\nu\sqrt{|\!|\!|\Sigma|\!|\!|_{{\operatorname{op}}}}\sqrt{\frac{k+p}{n}}$ satisfies the conditions of Corollary 2 with high probability. Lemma 2 shows that the RSC property holds with $\kappa(\mathfrak{X})=\sigma_{\operatorname{min}}(\Sigma)/20$, again with high probability. Consequently, Corollary 2 implies that

with probability greater than $1-c_{2}\exp(-c_{3}(k+p))$, as claimed.

4 Proof of Corollary 4

For the proof of this corollary, we adopt the notation

The following lemma provides the lower bound needed to establish RSC for the autoregressive model:

The eigenspectrum of the matrix $X^{T}X/n$ is well-controlled in terms of the stationary covariance matrix: in particular, as long as $n>c_{3}p$, we have

both with probability greater than $1-2c_{1}\exp(-c_{2}\,p)$.

Thus, from the bound (28)(b), we see with the high probability, the RSC property holds with $\kappa(\mathfrak{X})=\sigma_{\operatorname{min}}(\Sigma)/4$ as long as $n>c_{3}p$.

As before, in order to verify the choice of $\lambda_{N}$, we need to control the quantity $\frac{1}{n}|\!|\!|X^{T}W|\!|\!|_{{\operatorname{op}}}$. The following inequality, proved in Appendix C.2, yields a suitable upper bound:

There exist constants $c_{i}>0$, independent of $n,p,\Sigma$ etc. such that

From Lemma 5, we see that it suffices to choose $\lambda_{N}=\frac{80\,|\!|\!|\Sigma|\!|\!|_{{\operatorname{op}}}}{1-\gamma}\sqrt{\frac{p}{n}}$. With this choice, Corollary 2 of Theorem 1 yields that

with probability greater than $1-c_{2}\exp(-c_{3}p)$, as claimed.

5 Proof of Corollary 5

Let us now show how Proposition 1 implies the RSC property with an appropriate tolerance parameter. In particular, let us define \delta^{2}\;:=\;R_{q}\,\big{[}\sqrt{\frac{k}{N}}+\sqrt{\frac{p}{N}}\big{]}^{2-q}, so that if we have the inequality $|\!|\!|\Delta|\!|\!|_{{F}}\;\leq\;\delta$, the result of Corollary 5 follows immediately. Therefore, we may take $|\!|\!|\Delta|\!|\!|_{{F}}^{2}\,\geq\,\delta$. Now recall from Lemma 1 that the error $\Delta$ satisfies the bound (25). Combining these facts, we are guaranteed that $\Delta\in\mathcal{C}(r;\delta)$, where the set $\mathcal{C}$ was previously defined (12), and it is sufficient to establish the RSC property over this set.

Observe that the bound (21) implies that for any $\Delta\in\mathcal{C}$,

Following the arguments used in the proofs of Theorem 1 and Corollary 2, we find that

where $\tau>0$ is a parameter to be chosen. We now set \tau\,=\,\big{(}\sqrt{k}+\sqrt{p}\,\big{)}/\sqrt{N}, and substitute the resulting bound (31) into equation (30), thereby obtaining

If we choose $N>200\,R_{q}^{(1-q/2)}k\,p$, then we are guaranteed that $\frac{1}{4}-(4+\sqrt{32})\delta\geq\frac{1}{8}$, which shows that the RSC property holds with $\kappa(\mathfrak{X})=1/8$.

The next step is to control the quantity $\|\mathfrak{X}^{*}(\vec{\varepsilon})\|_{2}/N$, required for specifying a suitable choice of $\lambda_{N}$.

If $\|\vec{\varepsilon}\|_{2}\leq 2\nu\sqrt{N}$, then

6 Proof of Corollary 6

This corollary follows from a combination of Proposition 1 and Lemma 1. Let $\widehat{\Theta}$ be an optimal solution to the SDP (22), and let $\Delta=\widehat{\Theta}-\Theta^{*}$ be the error. Since $\widehat{\Theta}$ is optimal and $\Theta^{*}$ is feasible for the SDP, we have $|\!|\!|\widehat{\Theta}|\!|\!|_{{1}}=|\!|\!|\Theta^{*}+\Delta|\!|\!|_{{1}}\leq|\!|\!|\Theta^{*}|\!|\!|_{{1}}$. Using the decomposition $\Delta=\Delta^{\prime}+\Delta^{\prime\prime}$ from Lemma 1 and applying triangle inequality, we have $|\!|\!|\Theta^{*}+\Delta^{\prime}+\Delta^{\prime\prime}|\!|\!|_{{1}}\geq|\!|\!|\Theta^{*}+\Delta^{\prime\prime}|\!|\!|_{{1}}-|\!|\!|\Delta^{\prime}|\!|\!|_{{1}}$. From the properties of the decomposition in Lemma 1 (see Appendix A), we find that

Combining the pieces yields that $|\!|\!|\Delta^{\prime\prime}|\!|\!|_{{1}}\leq|\!|\!|\Delta^{\prime}|\!|\!|_{{1}}$, and hence $|\!|\!|\Delta|\!|\!|_{{1}}\leq 2|\!|\!|\Delta^{\prime}|\!|\!|_{{1}}$. By Lemma 1(a), the rank of $\Delta^{\prime}$ is at most $2r$, so that we obtain $|\!|\!|\Delta|\!|\!|_{{1}}\leq 2\sqrt{2r}|\!|\!|\Delta|\!|\!|_{{F}}\leq 4r|\!|\!|\Delta|\!|\!|_{{F}}$.

Note that $\mathfrak{X}(\Delta)=0$, since both $\widehat{\Theta}$ and $\Theta^{*}$ agree with the observations. Consequently, from Proposition 1, we have that

where the final inequality follows from the assumption that $N>40^{2}r(k+p)$. We have thus shown that $\Delta=0$, which implies that $\widehat{\Theta}=\Theta^{*}$ as claimed.

Experimental results

In this section, we report the results of various simulations that demonstrate the close agreement between the scaling predicted by our theory, and the actual behavior of the SDP-based $M$-estimator (9) in practice. In all cases, we solved the convex program (9) by using our own implementation in MATLAB of an accelerated gradient descent method which adapts a non-smooth convex optimization procedure to the nuclear-norm . We chose the regularization parameter $\lambda_{N}$ in the manner suggested by our theoretical results; in doing so, we assumed knowledge of quantities such as the noise variance $\nu^{2}$. (In practice, one would have to estimate such quantities from the data using standard methods.)

Figure 1 shows results for a multivariate regression model with the covariates chosen randomly from a $N(0,I)$ distribution. Panel (a) plots the Frobenius error $|\!|\!|\widehat{\Theta}-\Theta^{*}|\!|\!|_{{F}}$ on a logarithmic scale versus the sample size $N$ for three different matrix sizes, $p\in\{40,80,160\}$. Naturally, in each case, the error decays to zero as $N$ increases, but larger matrices require larger sample sizes, as reflected by the rightward shift of the curves as $p$ is increased. Panel (b) of Figure 1 shows the exact same set of simulation results, but now with the Frobenius error plotted versus the rescaled sample size $\widetilde{N}:\,=N/(rp)$. As predicted by Corollary 3, the error plots now are all aligned with one another; the degree of alignment in this particular case is so close that the three plots are now indistinguishable. (The blue curve is the only one visible since it was plotted last by our routine.) Consequently, Figure 1 shows that $N/(rp)$ acts as the effective sample size in this high-dimensional setting.

Figure 2 shows similar results for the autoregressive model discussed in Example 2. As shown in panel (a), the Frobenius error again decays as the sample size is increased, although problems involving larger matrices are shifted to the right. Panel (b) shows the same Frobenius error plotted versus the rescaled sample size $N/(rp)$; as predicted by Corollary 4, the errors for different matrix sizes $p$ are again quite well-aligned. In this case, we find (both in our theoretical analysis and experimental results) that the dependence in the autoregressive process slows down the rate at which the concentration occurs, so that the results are not as crisp as the low-rank multivariate setting in Figure 1.

Finally, Figure 3 presents the same set of results for the compressed sensing observation model discussed in Example 3. Even though the observation matrices $X_{i}$ here are qualitatively different (in comparison to the multivariate regression and autoregressive examples), we again see the “stacking” phenomenon of the curves when plotted versus the rescaled sample size $N/rp$, as predicted by Corollary 5.

Discussion

In this paper, we have analyzed the nuclear norm relaxation for a general class of noisy observation models, and obtained non-asymptotic error bounds on the Frobenius norm that hold under high-dimensional scaling. In contrast to most past work, our results are applicable to both exactly and approximately low-rank matrices. We stated a main theorem that provides high-dimensional rates in a fairly general setting, and then showed how by specializing this result to some specific model classes—namely, low-rank multivariate regression, estimation of autoregressive processes, and matrix recovery from random projections—it yields concrete and readily interpretable rates. Lastly, we provided some simulation results that showed excellent agreement with the predictions from our theory.

Acknowledgements

This work was partially supported by a Sloan Foundation Fellowship, AFOSR-09NL184 grant, and an NSF-CCF-0545862 CAREER grant to MJW.

Appendix A Proof of Lemma 1

which establishes Lemma 1(a). Moreover, we note for future reference that by construction of $\Delta^{\prime\prime}$, the nuclear norm satisfies the decomposition

We now turn to the proof of Lemma 1(b). Recall that the error $\Delta=\widehat{\Theta}-\Theta^{*}$ associated with any optimal solution must satisfy the inequality (23), which implies that

Using the triangle inequality and the relation (33), we have

Substituting this inequality into the bound (34), we obtain

Finally, since $|\!|\!|\frac{1}{N}\mathfrak{X}^{*}(\vec{\varepsilon})|\!|\!|_{{\operatorname{op}}}\leq\lambda_{N}/2$ by assumption, we conclude that

Appendix B Proof of Lemma 3

For positive scalars $a$ and $b$, define the (random) quantity

and note that our goal is to upper bound $\Psi(1,1)$. Note moreover that $\Psi(a,b)=a\,b\,\Psi(1,1)$, a relation which will be useful in the analysis.

Let $\mathcal{A}=\{u^{1},\ldots,u^{A}\}$ and $\mathcal{B}=\{v^{1},\ldots,v^{B}\}$ denote $1/4$ coverings of $S^{k-1}$ and $S^{p-1}$, respectively. We now claim that we have the upper bound

To establish this claim, we note that since the sets $\mathcal{A}$ and $\mathcal{B}$ are $1/4$-covers, for any pair $(u,v)\in S^{p-1}\times S^{p-1}$, there exists a pair $(u^{a},v^{b})\in\mathcal{A}\times\mathcal{B}$ such that $u=u^{a}+\Delta u$ and $v=v^{b}+\Delta v$, with $\max\{\|\Delta u\|_{2},\|\Delta v\|_{2}\}\leq 1/4$. Consequently, we can write

By construction, we have the bound $|\langle Xv^{b},\,W\Delta u\rangle|\leq\Psi(1,1/4)=\frac{1}{4}\Psi(1,1)$, and similarly $|\langle X\Delta v,\,Wu^{a}\rangle|\leq\frac{1}{4}\Psi(1,1)$ as well as $|\langle X\Delta v,\,W\Delta u\rangle|\leq\frac{1}{16}\Psi(1,1)$. Substituting these bounds into the decomposition (36) and taking suprema over the left and right-hand sides, we conclude that

We now apply the union bound to control the discrete maximum. It is known (e.g., ) that there exists a $1/4$ covering of $S^{k-1}$ and $S^{p-1}$ with at most $A\leq 8^{k}$ and $B\leq 8^{p}$ elements respectively. Consequently, we have

Combining this tail bound with the upper bound (37), we have

Setting $t^{2}=20\nu^{2}|\!|\!|\Sigma|\!|\!|_{{\operatorname{op}}}\frac{k+p}{n}$, this probability vanishes as long as $n>16(k+p)$.

Appendix C Technical details for Corollary 4

In this appendix, we collect the proofs of Lemmas 4 and 5.

Recalling that $S^{p-1}$ denotes the unit-norm Euclidean sphere in $p$-dimensions, we first observe that $|\!|\!|X|\!|\!|_{{\operatorname{op}}}=\sup_{u\in S^{p-1}}\|Xu\|_{2}$. Our next step is to reduce the supremum to a maximization over a finite set, using a standard covering argument. Let $\mathcal{A}=\{u^{1},\ldots,u^{A}\}$ denote a $1/2$-cover of it. By definition, for any $u\in S^{p-1}$, there is some $u^{a}\in\mathcal{A}$ such that $u=u^{a}+\Delta u$, where $\|\Delta u\|_{2}\leq 1/2$. Consequently, for any $u\in S^{p-1}$, the triangle inequality implies that

and hence that $|\!|\!|X|\!|\!|_{{\operatorname{op}}}\leq\max_{u^{a}\in\mathcal{A}}\|Xu^{a}\|_{2}+\frac{1}{2}|\!|\!|X|\!|\!|_{{\operatorname{op}}}$. Re-arranging yields the useful inequality

where the last inequality follows from the union bound, and the fact that there exists a $1/2$-covering of $S^{p-1}$ with at most $4^{p}$ elements.

Moreover, we have $\operatorname{trace}(R)/n=u^{T}\Sigma u\leq|\!|\!|\Sigma|\!|\!|_{{\operatorname{op}}}$. Applying Lemma 8 with $t=5\sqrt{\frac{p}{n}}$, we conclude that

with probability at least $1-c_{1}\,\exp(-c_{2}\,p)$, which establishes the upper bound (28)(a).

since $\Psi(\Delta v,\Delta v)\geq 0$. Since |\Psi(\Delta v,v)|\leq\epsilon\,|\!|\!|\Big{(}\frac{1}{n}X^{T}X\Big{)}|\!|\!|_{{\operatorname{op}}}, we obtain the lower bound

By the previously established upper bound(28)(a), have $|\!|\!|\frac{1}{n}X^{T}X|\!|\!|_{{\operatorname{op}}}\leq\frac{24|\!|\!|\Sigma|\!|\!|_{{\operatorname{op}}}}{(1-\gamma)}$ with high probability. Hence, choosing $\epsilon=\frac{(1-\gamma)\sigma_{\operatorname{min}}(\Sigma)}{200|\!|\!|\Sigma|\!|\!|_{{\operatorname{op}}}}$ ensures that $2\epsilon|\!|\!|\frac{1}{n}X^{T}X|\!|\!|_{{\operatorname{op}}}\leq\sigma_{\operatorname{min}}(\Sigma)/4$.

Consequently, it suffices to lower bound the minimum over the covering set. We first establish a concentration result for the function $\Psi(v,v)$ that holds for any fixed $v\in S^{p-1}$. Note that we can write

Note that this bound holds for any fixed $v\in S^{p-1}$. Setting $t^{*}=\frac{(1-\gamma)\,\sigma_{\operatorname{min}}(\Sigma)}{16|\!|\!|\Sigma|\!|\!|_{{\operatorname{op}}}}$ and applying the union bound yields that

which vanishes as long as $n>\frac{4\log(4/\epsilon)}{(t^{*})^{2}}p$.

C.2 Proof of Lemma 5

We now apply the union bound to control the discrete maximum. It is known (e.g., ) that there exists a $1/4$ covering of $S^{p-1}$ with at most $8^{p}$ elements. Consequently, we have

For each $i=1,\ldots,n$, let $X_{i}$ and $W_{i}$ denote the $i^{th}$ row of $X$ and $W$. Following some simple algebra, we have the decomposition $\frac{\langle Xv,\,Wu\rangle}{n}=T_{1}-T_{2}-T_{3}$, where

We may now bound each $T_{j},j=1,2,3$ in turn; in doing so, we make repeated use of Lemma 8, which provides concentration bounds for a random variable of the form $\|Y\|_{2}^{2}$, where $Y\sim N(0,Q)$ for some matrix $Q\succeq 0$.

We begin with $T_{2}$, which the easiest to control since (up to scaling by $\nu$), it corresponds to the deviation away from the mean of $\chi^{2}$-variable with $n$ degrees of freedom. Consequently, applying Lemma 8 with $Q=I$, we obtain

where $\delta_{ij}$ is the Kronecker delta for the event $\{i=j\}$. As before, by symmetry of $S$, we have $|\!|\!|S|\!|\!|_{{\operatorname{op}}}\leq\max_{i=1,\ldots,n}\sum_{j=1}^{n}|S_{ij}|$, and hence

Morever, we have $\operatorname{trace}(S)/n=\nu^{2}+v^{T}\Theta^{*}v$, so that by applying Lemma 8, we conclude that

which completes the analysis of this term.

Combining the bounds (45), (44) and (46), we conclude that for all $t>0$,

Setting $t=10\sqrt{p/n}$ and combining with the bound (43), we conclude that

Appendix D Proof of Proposition 1

In particular, our goal is to prove that for any $t\geq 1$, the lower bound

holds with probability at least $1-c_{1}\exp(-c_{2}N)$. By a standard peeling argument (see Raskutti et al. for details), this lower bound implies the claim (21).

We establish the lower bound (48) using Gaussian comparison inequalities and concentration of measure (see Lemma 7). For each pair $(u,\Theta)\in S^{N-1}\times\mathcal{R}(t)$, consider the random variable $Z_{u,\Theta}=\langle u,\,\mathfrak{X}(\Theta)\rangle$, and note that it is Gaussian with zero mean. For any two pairs $(u,\Theta)$ and $(u^{\prime},\Theta)$, some calculation yields

We now define a second Gaussian process $\{Y_{u,\Theta}\,\mid\,(u,\Theta)\in S^{N-1}\times\mathcal{R}(t)\}$ via

It can be shown that for all pairs $(u,\Theta),(u^{\prime},\Theta^{\prime})\in S^{N-1}\times\mathcal{R}(t)$, we have

Moreover, equality holds whenever $\Theta=\Theta^{\prime}$. The conditions of the Gordon-Slepian inequality are satisfied, so that we are guaranteed that

Finally, we need to establish sharp concentration around the mean. Note that the function $f(\mathfrak{X}):\,=\inf_{\Theta\in\mathcal{R}(t)}\|\mathfrak{X}(\Theta)\|_{2}/\sqrt{N}$ is Lipschitz with constant $1/\sqrt{N}$, so that Lemma 7 implies that

Appendix E Some useful concentration results

The following lemma is classical , and yields sharp concentration of a Lipschitz function of Gaussian random variables around its mean.

Given a Gaussian random vector $Y\sim N(0,Q)$, for all $t>2/\sqrt{n}$, we have

Let $\sqrt{Q}$ be the symmetrix matrix square root, and consider the function $f(x)=\|\sqrt{Q}x\|_{2}/\sqrt{n}$. Since it is Lipschitz with constant $|\!|\!|\sqrt{Q}|\!|\!|_{{\operatorname{op}}}/\sqrt{n}$, Lemma 7 implies that

By integrating this tail bound, we find that the variable $Z=\|\sqrt{Q}X\|_{2}/\sqrt{n}$ satisfies the bound $\operatorname{var}(Z)\leq 4|\!|\!|Q|\!|\!|_{{\operatorname{op}}}/n$, and hence conclude that

Combining this bound with the tail bound (54), we conclude that

Setting $\delta=(t-2/\sqrt{n})\,\sqrt{|\!|\!|Q|\!|\!|_{{\operatorname{op}}}}$ in the bound (56) yields that

Similarly, setting $\delta=\sqrt{|\!|\!|Q|\!|\!|_{{\operatorname{op}}}}$ in the tail bound (56) yields that with probability greater than $1-2\exp(-n/2)$, we have

References