{'fraction_non_alphanumeric': 0.044543277454669856, 'fraction_numerical': 0.010605542251111872, 'mean_word_length': 4.05901696088612, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 11, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Accurate low-rank matrix recovery from a small number of linear measurements

We consider the problem of recovering a lowrank matrix M from a small number of random linear measurements. A popular and useful example of this problem is matrix completion, in which the measurements reveal the values of a subset of the entries, and we wish to fill in the missing entries (this is the famous Netflix problem). When M is believed to have low rank, one would ideally try to recover M by finding the minimum-rank matrix that is consistent with the data; this is, however, problematic since this is a nonconvex problem that is, generally, intractable. Nuclear-norm minimization has been proposed as a tractable approach, and past papers have delved into the theoretical properties of nuclear-norm minimization algorithms, establishing conditions under which minimizing the nuclear norm yields the minimum rank solution. We review this spring of emerging literature and extend and refine previous theoretical results. Our focus is on providing error bounds when M is well approximated by a low-rank matrix, and when the measurements are corrupted with noise. We show that for a certain class of random linear measurements, nuclear-norm minimization provides stable recovery from a number of samples nearly at the theoretical lower limit, and enjoys order-optimal error bounds (with high probability).


I. INTRODUCTION
Low-rank matrix recovery is a quickly developing research area with a growing list of applications such as collaborative filtering, machine learning, control, remote sensing, computer vision, and quantum state tomography. In its most general (noiseless) form the problem consists of recovering a low-rank matrix, M ∈ R n1×n2 , from a series of m linear measurements, A 1 , M , A 2 , M , ..., A m , M (we use the usual inner product X, Y = Tr(X * Y ) = i,j X i,j Y i,j ). The A i 's are known and are analogous to the rows of a compressed sensing matrix. To consolidate the presentation, we write the linear model more compactly as A(M ) for the linear operator A : R n1×n2 → R m (the ith entry of A(X) is A i , X ). where X ∈ R n1×n2 is the decision variable. Unfortunately, rank minimization is an intractable problem (aside from a few rare special cases) and is in fact provably NP-hard and hard to approximate [8], [14]. To overcome this problem, nuclear-norm minimization has been introduced as the tightest convex relaxation of rank minimization [4], [6], [9], [10], [15]. Here, one solves instead, minimize X * subject to A(X) = A(M ).

(I.2)
Due to its convexity, the nuclear-norm minimization problem is tractable (and an SDP) and a number of fast algorithms have been proposed to solve it [1], [13]. A recent influx of papers has shown that for a broad range of low-rank matrix recovery problems, nuclearnorm minimization correctly recovers the original lowrank matrix [4], [6], [15], [16]. Most of these papers have focused on the matrix completion subproblem (see Section III) in which the measurements are simply entries of the unknown matrix. A main purpose of this paper is to compare the theoretical results in the matrix completion problem to those possible with 'less coherent' measurement ensembles.

A. Organization of the paper
In the first half of the paper (Section II), we present new theoretical results concerning low-rank matrix recovery from measurements obeying a certain restricted isometry property, thereby extending and refining the work of Recht et al. in [15]. A first important question we address here (and in the matrix completion subproblem) is this: how many measurements are necessary to recover a low-rank matrix? By taking the singular value decomposition of M ∈ R n1×n2 with rank M = r, one can see that M has (n 1 + n 2 − r)r degrees of freedom. This can be much lower than n 1 n 2 for r ≪ min(n 1 , n 2 ) suggesting that one may be able to recover a low-rank matrix from substantially fewer than n 1 n 2 measurements. In fact, it has been shown [15] that one may oversample the degrees of freedom by a logarithmic factor and still exactly recover M via nuclear minimization with high probability. In this paper, we show that for certain classes of linear measurements, one can reduce the number of measurements to a small multiple of (n 1 + n 2 − r)r, and still attain exact matrix recovery via nuclear-norm minimization. Further, when the measurements are corrupted by noise, we suggest a nuclear norm based algorithm that takes into account the noise in the model and show that the error when using this algorithm is order optimal. Lastly, when M has decaying singular values, the error bounds are refined and extended to exhibit an optimal bias-variance tradeoff (explained in more detail in Section II).
In the second half of the paper (Section III), we review the theory on matrix completion, noting that this is a much different problem because the RIP does not hold. We begin the section by comparing different theoretical results regarding nuclear norm minimization. We also remark that other competing algorithms have arisen to tackle low-rank matrix completion. To the authors' best knowledge, only one such alternative algorithm, proposed by Montanari et al. [11], [12], has rigorous theoretical backing. We review the theory proposed by these authors and highlight some of the differences between their approach and nuclear-norm minimization. We conclude this section by reviewing the noisy matrix completion results, and comparing them to the results when the RIP holds.

B. Notation
In the remainder of the paper, we assume M is square, with n 1 = n 2 = n, in order to simplify the notation. Simple generalizations of our results, however, hold for rectangular matrices. Below, X refers to the operator norm of X (the largest singular value), X 1,∞ is the magnitude of the largest entry of X and X F is the Frobenius norm. The standard basis vectors are denoted by e i , and A * is the adjoint of the operator A, A : R n×n → R m , so that The singular value decomposition of M (with rank(M ) = r) is written as (I.3) with U, V ∈ R n×r , Σ ∈ R r×r for orthogonal matrices U, V and the diagonal matrix of singular values, Σ.

II. RANDOM LINEAR MEASUREMENTS
A difficulty in the matrix completion problem is that unless all of the entries of the unknown matrix are sampled, there is always a rank-1 matrix in the null space of the sampling operator (see Section III). This leads to the necessity of requirements below on the flatness of the singular vectors of the underlying unknown matrix. Interestingly, such assumptions are not necessary when considering other classes of measurement ensembles. In a paper bridging the gap between compressive sensing and low-rank matrix recovery [15], the authors prove that many random measurement ensembles often satisfy a restricted isometry property (RIP), which guarantees that low-rank matrices cannot lie in the null space of A (or cannot lie 'close' to the null space of A).
Definition 1: For each integer r = 1, 2, . . . , n, define the isometry constant δ r of A as the smallest quantity such that holds for all matrices of rank at most r. A measurement ensemble, A, is said to obey the RIP at rank r if δ r ≤ δ < 1 for a constant δ whose appropriate values will be specified in what follows. How many measurements, m, are necessary to ensure that the RIP holds at a given rank r? To first achieve a lower bound on this quantity, note that the set of rank r matrices contains the set of matrices which are restricted to have nonzero entries only in the first r rows. This is an n × r dimensional vector space and thus we must have m ≥ nr or otherwise there will be a rank-r matrix in the null space of A regardless of what measurements are used. The following theorem shows that for certain classes of random measurements, this lower bound can be achieved to within a constant factor.
Theorem 2: Fix 0 ≤ δ < 1 and let A be a random measurement ensemble obeying the following property: for any given X ∈ R n×n and any fixed 0 < t < 1, 2) for fixed constants C, c > 0. If m ≥ Dnr then A satisfies the RIP with isometry constant δ r ≤ δ with probability exceeding 1 − Ee −dm for fixed constants D, E, d > 0.
As an example of a generic measurement ensemble obeying (II.2), if each A i contains iid mean zero Gaussian entries with variance 1/m then m · A(X) 2 ℓ2 / X 2 F is distributed as a chi-squared random variable with m degrees of freedom. Thus, applying a standard concentration bound, and (II.2) is satisfied. Similarly, each A i can be composed of iid sub-gaussian random variables to achieve the concentration bound (II.2). Thus one way to interpret Theorem 2 is that 'most' properly normalized measurement ensembles satisfy the RIP nearly as soon as is theoretically possible, where the measure used to define 'most' is Gaussian (or sub-Gaussian). Theorem 2 is inspired by a similar theorem in [15][Theorem 4.2] and refines this result in two ways. First, it shows that one must only oversample the number of degrees of freedom of a rank r matrix by a constant factor in order to obtain the RIP at rank r (which improves on the theoretical result in [15] by a factor of log n). Second, it shows that one must only require a single concentration bound on A, removing another assumption required in [15].

A. Minimax Error Bound
Using the RIP, Recht et. al. [15] show that exact recovery of M occurs when solving the convex problem (I.2) provided that rank(M ) = r and δ 5r ≤ δ for a certain constant δ ≈ .2. We extend this result by considering the noisy problem, where for simplicity the noise, z, is assumed to be Gaussian with iid mean zero entries of variance σ 2 .
In this case, we analyze the performance of a version of (I.2) which takes noise into account, and is analogous to the Dantzig Selector algorithm [5]: where λ = C √ nσ for an appropriate constant C. A heuristic intuition for this choice of λ is as follows: suppose that A is simply the operator which stacks the columns of its argument into a vector, so that A * A is the identity operator, and A * (z) is an n × n matrix with iid Gaussian entries. This is perhaps the simplest case to analyze. We would like the unknown matrix M to be a feasible point, which requires that A * (z) ≤ λ.
It is well known that the top singular value of a square n × n Gaussian matrix, with per-entry variance σ 2 , is concentrated around √ 2nσ, and thus we require λ ≥ √ 2nσ. Further, observe that in this simple setting the solution to (II.4) can be explicitly calculated, and is equal to T λ (M + A * (z)) where the operator T λ softthresholds the singular values of its argument by λ. If λ is too large, then T λ (M + A * (z)) becomes strongly biased towards zero, and thus (loosely) λ should be as small as possible while still allowing M to be feasible, leading to the choice λ ≈ √ 2nσ for this simple case. We are now prepared to present the simplest version of our theoretical error bounds. The following theorem states that if M has low rank then the error is order optimal with overwhelming probability.
The result in this theorem is quite similar to the adaptive error bound in compressive sensing first proved in [5] and the proofs are almost identical (see [2] for a proof).
In order to see how the result generalizes when M is rectangular, in the case when M ∈ R n1×n2 , the error bound (II.5) is replaced by We compare the above error bound (II.5), to the minimax error bound described below, Theorem 4: Any estimatorM (y), with y = A(M ) + z, obeys In other words, the minimax error over the class of matrices of rank at most r is lower bounded by just about nrσ 2 . Thus the error achieved by solving a convex program is within a constant of the expected minimax error (with high probability). As an exercise, and to help further understand the error bound (II.5), we analyze the error in the example above in which A * A is the identity operator andM = T λ (M + A * (z)). In this case, lettingM = M + A * (z), assuming that λ ≥ A * (z) . Then, Once again, assuming that λ ≥ A * (z) , we have Plugging this in with λ = C √ nσ gives the error bound (II.5).

B. Oracle Error Bound
While achieving the minimax error is useful, in many cases minimax analysis is overly focused on worstcase-scenarios and more adaptive error bounds can be reached. This is exactly the case when M has decaying singular values, with many singular values below the 'noise level' of √ nσ. In order to set the bar for error bounds in this case, we compare to the error achievable with the aid of an oracle.
To develop an oracle bound, consider the family of estimators defined as follows: for each n×r, orthogonal, matrix U , defineM [U ] as the minimizer to (II.8) 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) (II.9) The question is whether it is possible to mimic the performance of the oracle and achieve a MSE close to (II.9) with a real estimator.
Through classical calculations, one may lower bound M −M[U ] 2 (the steps required will be shown in detail in the sequel) as follows: we have The first term is a bound on the bias of the estimator which occurs when U does not span the column space of M while the second term is a bound on the variance which grows as the dimension of U grows. Thus the oracle error is lower bounded by Now for a given dimension r, the best U -that minimizing the proxy for the bias term P U ⊥ (M ) 2 F -spans the top r singular vectors of the matrix M and thus we obtain which for convenience we simplify to The right-hand side has a nice interpretation. If σ 2 i > nσ 2 , one should try to estimate the rank-1 contribution σ i u i v * i and pay the variance term (which is about nσ 2 ) whereas if σ 2 i ≤ nσ 2 , we should not try to estimate this component, and pay a squared bias term equal to σ 2 i . In other words, the right-hand side may be interpreted as an ideal bias-variance trade-off, which can be nearly achieved with the help of an oracle.
The following theorem states that when M has low rank, one achieves the optimal bias-variance trade-off when solving a convex optimization problem, up to a constant factor.
with probability at least 1 − De −dm for some numerical constants C, D, d > 0. For a proof, see the upcoming paper [2].

C. Approximately low-rank, noisy, error bounds
An important drawback of the above two theorems (Theorems 5, 3) is that they only apply when M is exactly a low-rank matrix, but do not generally apply when M is well approximated by a low-rank matrix. However, for many random measurement ensembles A, the above result can be extended to handle the case when all n of the singular values of M are nonzero. This is the content of the following theorem.
Theorem 6: Fix M . Suppose that each 'row' A i of A contains iid mean zero Gaussian entries with variance 1/m. Suppose m ≤ cn 2 / log n for some numerical constant c. Letr be the largest integer such that δ 4r ≤ Here,r is the largest value of r such that the RIP holds and thusr ≥ c m n with high probability for a fixed numerical constant c (see Theorem 2). The constant is arbitrary and could be replaced by any constant less than 1. The error bound has an interesting intuitive interpretation: decompose M as M = Mr + M c with so that Mr is the projection of M onto rank-r matrices. Then we achieve the near optimal bias-variance trade-off in estimating Mr, but cannot recover M c . An important point about Theorem 6 is that it is an example of instance optimality: the result holds with high probability for any given specific M , but it does not hold uniformly over all M . For the proof, see [2].

III. MATRIX COMPLETION
A highly applicable subset of low-rank matrix recovery problems concerns the recovery of an unknown matrix from a subset of its entries (matrix completion). An example to bear in mind is the Netflix problem in which one sees a few movie ratings for each user, which can be viewed as a row of (possible) ratings with only a few entries filled in. Stacking the rows together, creates the data matrix. Netflix would like to guess how each user would rate a movie he had not seen, in order to target advertising.A great difficulty is that there are always rank-1 matrices in the null space of the measurement operator and, thus, our problem is 'RIPless'.
In order to specialize the nuclear-norm minimization algorithm (I.2) to matrix completion, let Ω be the set of observed entries. We assume Ω is chosen uniformly at random with |Ω| = m (this turns the discussion away from adversarial sampling sets). Define P Ω : R n×n → R n×n to be the operator setting to zero each unobserved entry, Then one solves minimize X * subject to P Ω (X) = P Ω (M ).

(III.2)
To the best of our knowledge, there are five papers with novel theoretical guarantees on noiseless matrix completion [4], [6], [11], [12], [16]. We compare the results of this prior literature in Table I. The parameters µ, µ 1 , µ 2 , µ B , κ in Table I are defined further on in this section, but for now note that they depend on the

A. nuclear-norm minimization algorithms
We first review the results of [4], which pioneered the matrix completion theory. As described therein, assumptions on M are vital to ensure that matrix completion is possible. To compel this line of reasoning, suppose M = e i e * j is a (rank-1) matrix with only 1 nonzero entry. If this entry is not seen, then M is in the null space of the measurement operator and is indistinguishable from the zero matrix. Such observations are explored in more depth in [4], [6], [7] providing an argument for the necessity of the assumption that the singular vectors of M are 'spread', which is also intrinstically important to bounding the size of µ B , µ 0 , µ 1 , µ 2 and µ (but has no relation to κ).
In order to quantify 'spread', with parameter µ B , the authors of [4] require for each u k , v k (recall these are the singular vectors of M ). Note that the minimum value of µ B is 1 if all of the singular vectors have minimal ℓ ∞ norm, and that µ B can be as large as n when a singular vector has only one nonzero entry. When r = O(1), the constants µ 0 , µ 1 and µ are all O(1) · µ B (see [4], [6]), thus bounding all of the parameters involved in the nuclear norm theoretical results.
In order to prove theoretical guarantees for larger values of the rank, [4] introduces the concept of the incoherence of M with parameters µ 0 and µ 1 as defined below. Let P U = U U * be the projection onto the range of the left singular vectors of M and similarly let P V = V V * . Then [4] requires, A matrix M is said to be incoherent if µ 0 and µ 1 are small (e.g. O(1) or O(log n)...). Note that these parameters, and thus the number of measurements required in Theorem 1.3 of [4] have no dependence on the singular values of M , a quality that is ubiquitous to all of the parameters involved in the nuclear-norm minimization theory. Which matrices are incoherent? As noted above, if r = O(1) then µ 0 , µ 1 ≤ O(1) · µ B and thus the matrices with 'spread' singular vectors are incoherent. To address this question from another angle, introduce the random orthogonal model mentioned in Table I. Definition 7: A matrix M = U ΣV * of rank r is said to be drawn from the random orthogonal model if U is drawn uniformly at random from the set of n × r orthogonal matrices and similarly for V , although U and V may be dependent on each other. This is perhaps the most generic possible random model for the singular vectors of a matrix. Under this model for values of the rank r greater than log n (to avoid small sample effects) µ 0 = O(1) and µ 1 = O(log n) with very large probability [4]. A way to interpret this is that 'most' matrices have small values of µ 0 , µ 1 .
With the variables µ 0 and µ 1 defined, along with the random orthogonal model, the reader is equipped to evaluate the theoretical results of [4] in Table I. One sees that for 'most' matrices, or alternatively, for incoherent matrices (those with small values of µ 0 , µ 1 ), it is required that m n 1.2 r or m n 1.25 r (depending on r), ignoring log and constant factors. While these results show that one can drastically undersample a matrix when r ≪ n, they are above the theoretical limit of (2n − r)r ≈ nr by a factor of about n .2 or n .25 . With the aid of some slightly stronger assumptions on M , [6] removes these extra small powers of n and nearly attains the theoretical limit.
In order to present these optimal results [6] that apply for values of the rank r greater than O(1), the authors introduce the strong incoherence property with parameter µ, which we now state: it is required that for all pairs (a, a ′ ) and (b, b ′ ) with 1 ≤ a, a ′ , b, Secondly, it is required that µ ≥ µ 1 (with µ 1 defined above). As in [4], the random orthogonal model obeys µ ≤ O(log n) with high probability [6]. Examining Table I, one sees that for µ = O(log n), the number of measurements required is within a polylogarithmic factor of the theoretical low limit. Is the polylogarithmic factor necessary in the bounds above? This answer depends on the size of r. As argued in [4], [6, Theorem 1.7], when r = O(1) it is generally impossible to recover M by any algorithm if one does not oversample the degrees of freedom by at least a factor of log n. However, as shown in [16], when r is of the same order as n and M is drawn from the random orthogonal model, one can oversample the degrees of freedom by a constant factor (while still undersampling M ), and still have exact recovery with high probability.

B. OPTSPACE
We now turn to the algorithm OPTSPACE proposed in [11], [12]. This algorithm has three steps, as (roughly) described below.
(1) Remove the columns and rows that contain a disproportionate amount of sampled entries (trimming) in order to prevent these measurements from overly influencing the singular vectors in the next step. (2) Project the result of step 1 onto the space of rank r matrices and renormalize in order to attain an initial approximation of M . 1 (3) Perform local minimization via gradient descent over a locally convex, but globally nonconvex, function F (·) described in [11], [12], which has M as a local minimum. The intuitive idea of the algorithm is that the first 2 steps provide an accurate initial guess for M and that the function F (·) behaves like a parabola near M (with M achieving the minimum of the parabola) and thus gradient descent will recover M .
The success of OPTSPACE is theoretically tied to the values of the parameters κ, µ 0 and µ 2 . The last has been introduced while the first is the condition number The parameter µ 2 is somewhat analogous to µ 1 above. In fact, [11], [12] require In the special case where the singular values of M are all equal so that κ = 1, µ 1 and µ 2 have equivalent definitions, compelling the intuition that when κ = O(1) the two parameters are comparable. In this setting, and if r = O(log n), [11] poses strong theoretical results, comparable to those of [6], but with smaller powers of the parameters involved and the logarithms. However, the applicability of the theory depends strongly on the assumption that κ is small, whereas when using nuclearnorm minimization, the variations in the nonzero singular values are inconsequential to the exact recovery results.

C. Noisy matrix completion
As explained above, there is always a rank-1 matrix in the null space of the operator sampling the entries, and thus the RIP does not hold. To understand the difficulty this creates, consider that in the related field of compressive sensing, 'RIPless' error bounds have proved extremely elusive. To the authors' best knowledge, there is only one paper with such results [3], but it requires that every element of the signal should stand above the noise level. Despite this difficulty, two recent papers [7], [11] prove that matrix completion is robust vis-a-vis noise (using nuclear-norm minimization in [7] and OPTSPACE in [11]). In order to state these results, we first specify the noisy matrix completion problem.
The noisy model assumes where {Z ij : (i, j) ∈ Ω} is a noise term and, as before, Ω is chosen uniformly at random with |Ω| = m. Another way to express this model is as for some noise matrix Z (the entries of Z outside of Ω are irrelevant).

D. Stability with nuclear-norm minimization
The recovery algorithm analyzed in [7] is a relative of the Dantzig Selector, and once again draws its roots from an analogous algorithm in compressive sensing, this time the Lasso: This time, δ should be larger than the Frobenius norm of the noise, i.e. δ ≥ P Ω (Z) F -at least stochastically. 2 Thus, the algorithm just minimizes the proxy for the rank, while keeping within the noise level. The claim in [7] is that as soon as noiseless matrix completion is possible via nuclear-norm minimization, so is stable matrix completion (this argument is made in detail in [7]). We distill this result into the following simple theorem: Theorem 8: [7] Suppose that any of the requirements in [4] or [6] for exact matrix completion in the noiseless case are met (see Table I). Suppose P Ω (Z) F ≤ δ. Let p = m/n 2 . Then the solution to (III.5),M , obeys with probability at least 1 − cn −3 for a fixed numerical constant c. While this result is noteworthy in that it has no current analogue in compressive sensing 3 , it falls short of achieving oracle type error bounds. As described in [7] an oracle error bound derived by giving away the column space of M in the noisy matrix completion problem is M Oracle − M F ≈ p −1/2 δ (this oracle error is focused on adversarial noise). One sees that the oracle error is over-estimated by a factor of about √ n.

E. Stability with OPTSPACE
Another recent and noteworthy theoretical error bound for noisy matrix completion appears in a paper by Montanari et al. [11]. Once again the OPTSPACE algorithm is used, and thus having a large spread in the singular values of M can cause instabilities. However, as described in the following theorem, under suitable conditions the error bounds are comparable to those achievable with the aid of an oracle (with stochastic noise). Theorem 9: [11] Suppose rank(M ) = r and m ≥ Cnκ 2 max(µ 0 r log n, µ 2 0 r 2 κ 2 , µ 2 2 r 2 κ 4 ) for a fixed numerical constant C. LetM be the solution to the OPTSPACE algorithm. Then with probability at least 1−1/n 3 , assuming that the RHS is smaller than σ r , for a fixed numerical constant C ′ .
Here σ r is the smallest nonzero singular value of M . When Z contains iid Gaussian entries with variance σ 2 , the term P Ω (Z) can be bounded as P Ω (Z) ≤ C m log n n 1/2 σ with high probability (see [11]). Thus, in the regime when κ = O(1) and σ r ≥ C ′ κ 2 n 2 √ r m P Ω (Z) , one has M − M 2 F ≤ C n 3 r log n m σ 2 which is within a logarithmic factor of a simple oracle bound discussed in [7], in which the exact column space is given away and the noise is assumed to be stochastic. Specifically, this is the oracle bound that one achieves by examining the expected error of the estimatorM [U ] defined in equation (II.8), where U is defined as in the SVD M = U ΣV * . However, the class of low-rank matrices to which the theorem applies is very restrictive, a problem that is nonexistent when the RIP holds. In order to see this, note first that it is required that all of the singular values of M stand far above the noise level. For example, if one sees the entire matrix (m = n 2 ) then the theorem requires σ r ≥ C ′ κ 2 √ r Z , i.e. the minimal singular value of M must be larger than the noise level by a factor of about κ 2 √ r. Secondly, the number of measurements required is at least Cκ 6 µ 2 2 r 2 and thus quickly grows much larger than the degrees of freedom of M when κ and r grow.

IV. CONCLUSION
We have shown that a nuclear-norm minimization algorithm (II.4) recovers a low-rank matrix from the noisy data A i , M + z i , i = 1, . . . , m, in which each A i is Gaussian (or sub-Gaussian), and enjoys the following properties: 1) For both exact recovery from noiseless data and accurate recovery from noisy data, the number of measurements m must only exceed the number of degrees of freedom by a constant factor. 2) With high probability the error bound is within a constant factor of the expected minimax error.
3) With high probability the error bound achieves an optimal bias-variance trade-off (up to a constant). 4) The error bounds extend to the case when M has full rank (with many 'small' singular values). We close this paper with a few questions that we leave open for future research. Can the 'RIPless' theoretical guarantees be improved? In particular, in the case of nuclear-norm minimization based algorithms, can the error bound be tightened? And for other tractable algorithms, can we achieve strong error bounds without requiring the nonzero singular values of M to be nearly constant? Finally, are there useful applications in which the measurements are 'incoherent' enough that the RIP provably holds?