American Mathematical Society

Compressed sensing and best k -term approximation

By Albert Cohen, Wolfgang Dahmen, Ronald DeVore

Abstract

Compressed sensing is a new concept in signal processing where one seeks to minimize the number of measurements to be taken from signals while still retaining the information necessary to approximate them well. The ideas have their origins in certain abstract results from functional analysis and approximation theory by Kashin but were recently brought into the forefront by the work of Candès, Romberg, and Tao and of Donoho who constructed concrete algorithms and showed their promise in application. There remain several fundamental questions on both the theoretical and practical sides of compressed sensing. This paper is primarily concerned with one of these theoretical issues revolving around just how well compressed sensing can approximate a given signal from a given budget of fixed linear measurements, as compared to adaptive linear measurements. More precisely, we consider discrete signals x element-of double-struck upper R Superscript upper N , allocate n less-than upper N linear measurements of x , and we describe the range of k for which these measurements encode enough information to recover x in the sense of script l Subscript p to the accuracy of best k -term approximation. We also consider the problem of having such accuracy only with high probability.

1. Introduction

The typical paradigm for obtaining a compressed version of a discrete signal represented by a vector x element-of double-struck upper R Superscript upper N is to choose an appropriate basis, compute the coefficients of x in this basis, and then retain only the k largest of these with k less-than upper N . If we are interested in a bit stream representation, we also need in addition to quantize these k coefficients.

Assuming, without loss of generality, that x already represents the coefficients of the signal in the appropriate basis, this means that we pick an approximation to x in the set normal upper Sigma Subscript k of k -sparse vectors

StartLayout 1st Row with Label left-parenthesis 1.1 right-parenthesis EndLabel normal upper Sigma Subscript k Baseline colon equals StartSet x element-of double-struck upper R Superscript upper N Baseline colon number-sign s u p p left-parenthesis x right-parenthesis less-than-or-equal-to k EndSet comma EndLayout

where s u p p left-parenthesis x right-parenthesis is the support of x , i.e., the set of i for which x Subscript i Baseline not-equals 0 , and number-sign upper A is the number of elements in the set upper A . The best performance that we can achieve by such an approximation process in some given norm double-vertical-bar dot double-vertical-bar Subscript upper X of interest is described by the best k -term approximation error

StartLayout 1st Row with Label left-parenthesis 1.2 right-parenthesis EndLabel sigma Subscript k Baseline left-parenthesis x right-parenthesis Subscript upper X Baseline colon equals inf Underscript z element-of normal upper Sigma Subscript k Baseline Endscripts double-vertical-bar x minus z double-vertical-bar Subscript upper X Baseline period EndLayout

This approximation process should be considered as adaptive since the indices of those coefficients which are retained vary from one signal to another. On the other hand, this procedure is stressed on the front end by the need to first compute all of the basis coefficients. The view expressed by Candès, Romberg, and Tao Reference5Reference3Reference4 and Donoho Reference8 is that since we retain only a few of these coefficients in the end, perhaps it is possible to actually compute only a few nonadaptive linear measurements in the first place and still retain the necessary information about x in order to build a compressed representation.

These ideas have given rise to a very lively area of research called compressed sensing which poses many intriguing questions, of both a theoretical and practical flavor. The present paper is an excursion into this area, focusing our interest on the question of just how well compressed sensing can perform in comparison to best k -term approximation.

To formulate the problem, we are given a budget of n questions we can ask about x . These questions are required to take the form of asking for the values lamda 1 left-parenthesis x right-parenthesis comma ellipsis comma lamda Subscript n Baseline left-parenthesis x right-parenthesis where the lamda Subscript j are fixed linear functionals. The information we gather about x can therefore by described by

StartLayout 1st Row with Label left-parenthesis 1.3 right-parenthesis EndLabel y equals normal upper Phi x comma EndLayout

where normal upper Phi is an n times upper N matrix called the encoder and y element-of double-struck upper R Superscript n is the information vector. The rows of normal upper Phi are representations of the linear functionals lamda Subscript j , j equals 1 comma ellipsis comma n .

To extract the information that y holds about x , we use a decoder normal upper Delta which is a mapping from double-struck upper R Superscript n Baseline right-arrow double-struck upper R Superscript upper N . We emphasize that normal upper Delta is not required to be linear. Thus, normal upper Delta left-parenthesis y right-parenthesis equals normal upper Delta left-parenthesis normal upper Phi x right-parenthesis is our approximation to x from the information we have retained. We shall denote by script upper A Subscript n comma upper N the set of all encoder-decoder pairs left-parenthesis normal upper Phi comma normal upper Delta right-parenthesis with normal upper Phi an n times upper N matrix.

There are two common ways to evaluate the performance of an encoding-decoding pair left-parenthesis normal upper Phi comma normal upper Delta right-parenthesis element-of script upper A Subscript n comma upper N . The first is to ask for the largest value of k such that the encoding-decoding is exact for all k -sparse vectors, i.e.,

StartLayout 1st Row with Label left-parenthesis 1.4 right-parenthesis EndLabel x element-of normal upper Sigma Subscript k Baseline right double arrow normal upper Delta left-parenthesis normal upper Phi x right-parenthesis equals x period EndLayout

It is easy to see (see §2) that given n comma upper N , there are left-parenthesis normal upper Delta comma normal upper Phi right-parenthesis element-of script upper A Subscript n comma upper N such that (Equation1.4) holds for all k less-than-or-equal-to n slash 2 . Or put in another way, given k , we can achieve exact recovery on normal upper Sigma Subscript k whenever n greater-than-or-equal-to 2 k . Unfortunately such encoder/decoder pairs are not numerically friendly as is explained in §2.

Generally speaking, our signal will not be in normal upper Sigma Subscript k with k small but may be approximated well by the elements in normal upper Sigma Subscript k . Therefore, we would like our algorithms to perform well in this case as well. One way of comparing compressed sensing with best k -term approximation is to consider their respective performance on a specific class of vectors upper K subset-of double-struck upper R Superscript upper N . For such a class we can define on the one hand

StartLayout 1st Row with Label left-parenthesis 1.5 right-parenthesis EndLabel sigma Subscript k Baseline left-parenthesis upper K right-parenthesis Subscript upper X colon equals sup Underscript x element-of upper K Endscripts sigma Subscript k Baseline left-parenthesis x right-parenthesis Subscript upper X EndLayout

and

StartLayout 1st Row with Label left-parenthesis 1.6 right-parenthesis EndLabel upper E Subscript n Baseline left-parenthesis upper K right-parenthesis Subscript upper X colon equals inf Underscript left-parenthesis normal upper Phi comma normal upper Delta right-parenthesis element-of script upper A Subscript n comma upper N Endscripts sup Underscript x element-of upper K Endscripts double-vertical-bar x minus normal upper Delta left-parenthesis normal upper Phi x right-parenthesis double-vertical-bar Subscript upper X EndLayout

which describe, respectively, the performance of the two methods over this class. We are now interested in the largest value of k such that upper E Subscript n Baseline left-parenthesis upper K right-parenthesis Subscript upper X Baseline less-than-or-equal-to upper C 0 sigma Subscript k Baseline left-parenthesis upper K right-parenthesis Subscript upper X for a constant upper C 0 independent of the parameters k comma n comma upper N . Results of this type were established already in the 1970’s under the umbrella of what is called n -widths. The deepest results of this type were given by Kashin Reference14 with later improvements by Garnaev and Gluskin Reference9Reference13. We recall this well-known story briefly in §2.

The results on n -widths referred to above give matching upper and lower estimates for upper E Subscript n Baseline left-parenthesis upper K right-parenthesis Subscript upper X in the case that upper K is a typical sparsity class such as a ball in script l Subscript p Superscript upper N where

StartLayout 1st Row with Label left-parenthesis 1.7 right-parenthesis EndLabel double-vertical-bar x double-vertical-bar Subscript script l Sub Subscript p Baseline colon equals double-vertical-bar x double-vertical-bar Subscript script l Sub Subscript p Sub Superscript upper N Baseline colon equals StartLayout Enlarged left-brace 1st Row 1st Column left-parenthesis sigma-summation Underscript j equals 1 Overscript upper N Endscripts StartAbsoluteValue x Subscript j Baseline EndAbsoluteValue Superscript p Baseline right-parenthesis Superscript 1 slash p Baseline comma 2nd Column 0 less-than p less-than normal infinity comma 2nd Row 1st Column max Underscript j equals 1 comma ellipsis comma upper N Endscripts StartAbsoluteValue x Subscript j Baseline EndAbsoluteValue comma 2nd Column p equals normal infinity period EndLayout EndLayout

This in turn determines the largest range of k for which we can obtain comparisons of the form upper E Subscript n Baseline left-parenthesis upper K right-parenthesis Subscript upper X Baseline less-than-or-equal-to upper C 0 sigma Subscript k Baseline left-parenthesis upper K right-parenthesis Subscript upper X . One such result is the following: for upper K equals upper U left-parenthesis script l 1 Superscript upper N Baseline right-parenthesis , upper X equals script l 2 Superscript upper N , one has

StartLayout 1st Row with Label left-parenthesis 1.8 right-parenthesis EndLabel upper E Subscript k Baseline left-parenthesis upper U left-parenthesis script l 1 Superscript upper N Baseline right-parenthesis right-parenthesis Subscript script l 2 Sub Superscript upper N Baseline less-than-or-equal-to upper C 0 sigma Subscript k Baseline left-parenthesis upper U left-parenthesis script l 1 Superscript upper N Baseline right-parenthesis right-parenthesis Subscript script l 2 Sub Superscript upper N EndLayout

whenever

StartLayout 1st Row with Label left-parenthesis 1.9 right-parenthesis EndLabel k less-than-or-equal-to c 0 n slash log left-parenthesis upper N slash n right-parenthesis EndLayout

with absolute constants upper C 0 comma c 0 .

The decoders used in proving these theoretical bounds are far from being practical or numerically implementable. One of the remarkable achievements of the recent work of Candès, Romberg and Tao Reference3 and Donoho Reference8 is to give probabilistic constructions of matrices normal upper Phi which provide these bounds where the decoding can be done by solving the script l 1 minimization problem

StartLayout 1st Row with Label left-parenthesis 1.10 right-parenthesis EndLabel normal upper Delta left-parenthesis y right-parenthesis colon equals normal upper A times normal r times normal g times normal m times normal i times normal n Underscript normal upper Phi z equals y Endscripts double-vertical-bar z double-vertical-bar Subscript script l 1 Baseline period EndLayout

The above results on approximation of classes is governed by the worst elements in the class. It is a more subtle problem to obtain estimates that depend on the individual characteristics of the target vector x . The main contribution of the present paper is to study a stronger way to compare the performance of k -term approximation in a compressed sensing algorithm. Namely, we address the following question:

For a given norm double-vertical-bar dot double-vertical-bar Subscript upper X and k less-than upper N , what is the minimal value of n for which there exists a pair left-parenthesis normal upper Phi comma normal upper Delta right-parenthesis element-of script upper A Subscript n comma upper N such that

StartLayout 1st Row with Label left-parenthesis 1.11 right-parenthesis EndLabel double-vertical-bar x minus normal upper Delta left-parenthesis normal upper Phi x right-parenthesis double-vertical-bar Subscript upper X Baseline less-than-or-equal-to upper C 0 sigma Subscript k Baseline left-parenthesis x right-parenthesis Subscript upper X Baseline comma EndLayout

for all x element-of double-struck upper R Superscript upper N , with upper C 0 a constant independent of k and upper N ?

If a result of the form (Equation1.11) has been established, then one can derive a result for a class upper K by simply taking the supremum over all x element-of upper K . However, results on classes are less precise and informative than (Equation1.11).

We shall say a pair left-parenthesis normal upper Phi comma normal upper Delta right-parenthesis element-of script upper A Subscript n comma upper N satisfying (Equation1.11) is instance optimal of order k with constant upper C 0 for the space upper X . In particular, we want to understand under what circumstances the minimal value of n is roughly of the same order as k , similar to (Equation1.9). We shall see that the answer to this question strongly depends on the norm upper X under consideration.

The approximation accuracy of a compressed sensing matrix is determined by the null space

StartLayout 1st Row with Label left-parenthesis 1.12 right-parenthesis EndLabel script upper N equals script upper N left-parenthesis normal upper Phi right-parenthesis colon equals StartSet x element-of double-struck upper R Superscript upper N Baseline colon normal upper Phi x equals 0 EndSet period EndLayout

The importance of script upper N is that if we observe y equals normal upper Phi x without any a priori information on x , the set of z such that normal upper Phi z equals y is given by the affine space

StartLayout 1st Row with Label left-parenthesis 1.13 right-parenthesis EndLabel script upper F left-parenthesis y right-parenthesis colon equals x plus script upper N period EndLayout

We bring out the importance of the null space in §3 where we formulate a property of the null space which is necessary and sufficient for normal upper Phi to have a decoder normal upper Delta for which the instance optimality (Equation1.11) holds.

We apply this property in §4 to the case upper X equals script l 1 . In this case, we show the minimal number of measurements n which ensures (Equation1.11) is of the same order as k up to a logarithmic factor. In that sense, compressed sensing performs almost as well as best k -term approximation. We also show that, similar to the work of Candès, Romberg, and Tao this is achieved with the decoder normal upper Delta defined by script l 1 minimization. We should mention that our results in this section are essentially contained in the work of Candès, Romberg, and Tao Reference5Reference6Reference4 and we build on their ideas.

We next treat the case upper X equals script l 2 in §5. In this case, the situation is much less in favor of compressed sensing, since the minimal number of measurements n which ensures (Equation1.11) is now of the same order as upper N .

In §6, we consider an important variant of the script l 2 case where we ask for script l 2 instance optimality in the sense of probability. Here, rather than requiring that (Equation1.11) holds for all x element-of double-struck upper R Superscript upper N , we ask only that for each given x it holds with high probability. We shall see that in the case upper X equals script l 2 the minimal number of measurements n for such results is dramatically reduced, down to the order given by condition (Equation1.9). Moreover, we show that standard constructions of random matrices such as Gaussian and Bernoulli ensembles achieve this performance.

The striking contrast between the results of §5 and §6 shows that the probabilistic setting plays a crucial role in script l 2 instance optimality. Similar results in the sense of probability have been obtained earlier in a series of paper Reference7Reference10Reference11Reference12 that reflect the theoretical computer science approach to compressed sensing, also known as data sketching. A comparison with our results is in order.

First, the instance optimality bounds obtained in these papers are quantitatively more precise than ours, since they have the general form

StartLayout 1st Row with Label left-parenthesis 1.14 right-parenthesis EndLabel double-vertical-bar x minus normal upper Delta left-parenthesis normal upper Phi x right-parenthesis double-vertical-bar Subscript script l squared Baseline less-than-or-equal-to left-parenthesis 1 plus epsilon right-parenthesis sigma Subscript k Baseline left-parenthesis x right-parenthesis Subscript script l squared Baseline comma EndLayout

where epsilon greater-than 0 can be made arbitrarily small, at the expense of raising n , while in most of our results the constant upper C 0 in (Equation1.11) cannot get arbitrarily close to 1 . On the other hand, for a fixed epsilon greater-than 0 , the ratio between n and k is generally not as good as in (Equation1.9): for instance the decoders proposed in Reference7 and Reference11, respectively, use n tilde StartFraction k Over epsilon EndFraction log left-parenthesis upper N right-parenthesis Superscript 5 slash 2 and n tilde StartFraction k Over epsilon cubed EndFraction log left-parenthesis upper N right-parenthesis samples in order to achieve (Equation1.14).

Secondly, the types of encoding matrices which are proposed in these papers are of fairly different nature than those which are considered in §6, and our analysis actually does not apply to these matrices. Let us mention that one specific interest of the Gaussian matrices which are considered in the present paper is that they give rise to an encoding which is “robust” with respect to a change of the basis in which the signal is sparse, since the product of such a normal upper Phi and any upper N times upper N unitary matrix upper U results in a matrix normal upper Phi overTilde with the same probability law.

Finally, one of the significant achievements in Reference7Reference10Reference11Reference12 is the derivation of practical decoding algorithms of polynomial complexity in k up to logarithmic factors, therefore typically faster than solving the script l 1 minimization problem, while we do not propose any such algorithm in the present paper.

Generally speaking, an important issue in compressed sensing is the practical implementation of the decoder normal upper Delta by a fast algorithm. While being aware of this fact, the main goal of the present paper is to understand the theoretical limits of compressed sensing in comparison to nonlinear approximation. Therefore the main question that we address is, “How many measurements do we need so that some decoder recovers x up to some prescribed tolerance?”, rather than, “What is the fastest algorithm which allows to recover x from these measurements up to the same tolerance?”

The last sections of the paper are devoted to additional results which complete the theory. In order to limit the size of the paper, we only give a sketch of the proofs in those sections. The case upper X equals script l Subscript p for 1 less-than p less-than 2 is treated in §7, and in §8 we discuss another type of estimate that we refer to as mixed-norm instance optimality. Here the estimate (Equation1.11) is replaced by an estimate of the type

StartLayout 1st Row with Label left-parenthesis 1.15 right-parenthesis EndLabel double-vertical-bar x minus normal upper Delta left-parenthesis normal upper Phi x right-parenthesis double-vertical-bar Subscript upper X Baseline less-than-or-equal-to upper C 0 k Superscript negative s Baseline sigma Subscript k Baseline left-parenthesis x right-parenthesis Subscript upper Y Baseline comma EndLayout

where upper Y differs from upper X and s greater-than 0 is some relevant exponent. This type of estimate was introduced in Reference4 in the particular case upper X equals script l 2 and upper Y equals script l 1 . We give examples in the case upper X equals script l Subscript p and upper Y equals script l Subscript q in which mixed-norm estimates allow us to recover better approximation estimates for compressed sensing than (Equation1.11).

2. Performance over classes

We begin by recalling some well-known results concerning best k -term approximation which we shall use in the course of this paper. Given a sequence norm double-vertical-bar dot double-vertical-bar Subscript upper X on double-struck upper R Superscript upper N and a positive integer r greater-than 0 , we define the approximation class script upper A Superscript r by means of

StartLayout 1st Row with Label left-parenthesis 2.1 right-parenthesis EndLabel double-vertical-bar x double-vertical-bar Subscript script upper A Sub Superscript r Subscript left-parenthesis upper X right-parenthesis Baseline colon equals max Underscript 1 less-than-or-equal-to k less-than-or-equal-to upper N Endscripts k Superscript r Baseline sigma Subscript k Baseline left-parenthesis x right-parenthesis Subscript upper X Baseline period EndLayout

Notice that since we are in a finite dimensional space double-struck upper R Superscript upper N , this (quasi-)norm will be finite for all x element-of double-struck upper R Superscript upper N .

A simple, yet fundamental, chapter in k -term approximation is to connect the approximation norm in (Equation2.1) with traditional sequence norms. For this, we define for any 0 less-than q less-than normal infinity , the weak script l Subscript q norm as

StartLayout 1st Row with Label left-parenthesis 2.2 right-parenthesis EndLabel double-vertical-bar x double-vertical-bar Subscript w script l Sub Subscript q Subscript Superscript q Baseline colon equals sup Underscript epsilon greater-than 0 Endscripts epsilon Superscript q Baseline number-sign StartSet i semicolon StartAbsoluteValue x Subscript i Baseline EndAbsoluteValue greater-than epsilon EndSet period EndLayout

Again, for any x element-of double-struck upper R Superscript upper N all of these norms are finite.

If we fix the script l Subscript p norm in which approximation error is to be measured, then for any x element-of double-struck upper R Superscript upper N , we have for q colon equals left-parenthesis r plus 1 slash p right-parenthesis Superscript negative 1 ,

StartLayout 1st Row with Label left-parenthesis 2.3 right-parenthesis EndLabel upper B 0 double-vertical-bar x double-vertical-bar Subscript w script l Sub Subscript q Subscript Baseline less-than-or-equal-to double-vertical-bar x double-vertical-bar Subscript script upper A Sub Superscript r Subscript Baseline less-than-or-equal-to upper B 1 r Superscript negative 1 slash p Baseline double-vertical-bar x double-vertical-bar Subscript w script l Sub Subscript q Subscript Baseline comma x element-of double-struck upper R Superscript upper N Baseline comma EndLayout

for two absolute constants upper B 0 comma upper B 1 greater-than 0 . Notice that the constants in these inequalities do not depend on upper N . Therefore, x element-of script upper A Superscript r is equivalent to x element-of w script l Subscript q with equivalent norms.

Since the script l Subscript q norm is larger than the weak script l Subscript q norm, we can replace the weak script l Subscript q norm by the script l Subscript q norm in the right inequality of (Equation2.3). However, the constant can be improved via a direct argument. Namely, if 1 slash q equals r plus 1 slash p , then for any x element-of double-struck upper R Superscript upper N ,

StartLayout 1st Row with Label left-parenthesis 2.4 right-parenthesis EndLabel sigma Subscript k Baseline left-parenthesis x right-parenthesis Subscript script l Sub Subscript p Subscript Baseline less-than-or-equal-to double-vertical-bar x double-vertical-bar Subscript script l Sub Subscript q Subscript Baseline k Superscript negative r Baseline comma k equals 1 comma 2 comma ellipsis comma upper N period EndLayout

To prove this, take normal upper Lamda as the set of indices corresponding to the k largest entries in x . If epsilon is the size of the smallest entry in normal upper Lamda , then epsilon less-than-or-equal-to double-vertical-bar x double-vertical-bar Subscript w script l Sub Subscript q Baseline k Superscript negative 1 slash q Baseline less-than-or-equal-to double-vertical-bar x double-vertical-bar Subscript script l Sub Subscript q Baseline k Superscript negative 1 slash q and therefore

StartLayout 1st Row with Label left-parenthesis 2.5 right-parenthesis EndLabel sigma Subscript k Baseline left-parenthesis x right-parenthesis Subscript script l Sub Subscript p Subscript Superscript p Baseline equals sigma-summation Underscript i not-an-element-of normal upper Lamda Endscripts StartAbsoluteValue x Subscript i Baseline EndAbsoluteValue Superscript p Baseline less-than-or-equal-to epsilon Superscript p minus q Baseline sigma-summation Underscript i not-an-element-of normal upper Lamda Endscripts StartAbsoluteValue x Subscript i Baseline EndAbsoluteValue Superscript q Baseline less-than-or-equal-to k Superscript minus StartFraction p minus q Over q EndFraction Baseline double-vertical-bar x double-vertical-bar Subscript script l Sub Subscript q Subscript Superscript p minus q Baseline double-vertical-bar x double-vertical-bar Subscript script l Sub Subscript q Subscript Superscript q Baseline comma EndLayout

so that (Equation2.4) follows.

From this, we see that if we consider the class upper K equals upper U left-parenthesis script l Subscript q Superscript upper N Baseline right-parenthesis , we have

StartLayout 1st Row with Label left-parenthesis 2.6 right-parenthesis EndLabel sigma Subscript k Baseline left-parenthesis upper K right-parenthesis Subscript script l Sub Subscript p Subscript Baseline less-than-or-equal-to k Superscript negative r Baseline comma EndLayout

with r equals 1 slash q minus 1 slash p . On the other hand, taking x element-of upper K such that x Subscript i Baseline equals left-parenthesis 2 k right-parenthesis Superscript negative 1 slash q for 2 k indices and 0 otherwise, we find that

StartLayout 1st Row with Label left-parenthesis 2.7 right-parenthesis EndLabel sigma Subscript k Baseline left-parenthesis x right-parenthesis Subscript script l Sub Superscript p Subscript Baseline equals left-bracket k left-parenthesis 2 k right-parenthesis Superscript negative p slash q Baseline right-bracket Superscript 1 slash p Baseline equals 2 Superscript negative 1 slash q Baseline k Superscript negative r Baseline comma EndLayout

so that sigma Subscript k Baseline left-parenthesis upper K right-parenthesis Subscript upper X can be framed by

StartLayout 1st Row with Label left-parenthesis 2.8 right-parenthesis EndLabel 2 Superscript negative 1 slash q Baseline k Superscript negative r Baseline less-than-or-equal-to sigma Subscript k Baseline left-parenthesis upper K right-parenthesis Subscript script l Sub Subscript p Subscript Baseline less-than-or-equal-to k Superscript negative r Baseline period EndLayout

We next turn to the performance of compressed sensing over classes of vectors, by studying the quantity upper E Subscript n Baseline left-parenthesis upper K right-parenthesis Subscript upper X defined by (Equation1.6). As we have mentioned, the optimal performance of sensing algorithms is closely connected to the concept of Gelfand widths which are in some sense dual to the perhaps better known Kolmogorov widths. If upper K is a compact set in upper X and n is a positive integer, then the Gelfand width of upper K and of order n is by definition

StartLayout 1st Row with Label left-parenthesis 2.9 right-parenthesis EndLabel d Superscript n Baseline left-parenthesis upper K right-parenthesis Subscript upper X colon equals inf Underscript upper Y Endscripts sup left-brace double-vertical-bar x double-vertical-bar Subscript upper X Baseline semicolon x element-of upper K intersection upper Y right-brace EndLayout

where the infimum is taken over all subspaces upper Y of upper X of codimension less than or equal to n . This quantity is equivalent to upper E Subscript n Baseline left-parenthesis upper K right-parenthesis Subscript upper X , according to the following well-known result.

Lemma 2.1

Let upper K subset-of double-struck upper R Superscript upper N be any set for which upper K equals negative upper K and for which there is a upper C 0 greater-than 0 such that upper K plus upper K subset-of upper C 0 upper K . If upper X subset-of double-struck upper R Superscript upper N is any normed space, then

StartLayout 1st Row with Label left-parenthesis 2.10 right-parenthesis EndLabel d Superscript n Baseline left-parenthesis upper K right-parenthesis Subscript upper X Baseline less-than-or-equal-to upper E Subscript n Baseline left-parenthesis upper K right-parenthesis Subscript upper X Baseline less-than-or-equal-to upper C 0 d Superscript n Baseline left-parenthesis upper K right-parenthesis Subscript upper X Baseline comma 1 less-than-or-equal-to n less-than-or-equal-to upper N period EndLayout

Proof.

We give a proof for completeness of this paper. We first remark that the null space upper Y equals script upper N of normal upper Phi is of codimension less than or equal to n . Conversely, given any space upper Y subset-of double-struck upper R Superscript upper N of codimension n , we can associate its orthogonal complement upper Y Superscript up-tack which is of dimension n and the n times upper N matrix normal upper Phi whose rows are formed by any basis for upper Y Superscript up-tack . Through this identification, we see that

StartLayout 1st Row with Label left-parenthesis 2.11 right-parenthesis EndLabel d Superscript n Baseline left-parenthesis upper K right-parenthesis Subscript upper X Baseline equals inf Underscript normal upper Phi Endscripts sup left-brace double-vertical-bar eta double-vertical-bar Subscript upper X Baseline colon eta element-of script upper N intersection upper K right-brace comma EndLayout

where the infimum is taken over all n times upper N matrices normal upper Phi .

Now, if ( normal upper Phi comma normal upper Delta ) is any encoder-decoder pair and z equals normal upper Delta left-parenthesis 0 right-parenthesis , then for any eta element-of script upper N , we also have negative eta element-of script upper N . It follows that either double-vertical-bar eta minus z double-vertical-bar Subscript upper X Baseline greater-than-or-equal-to double-vertical-bar eta double-vertical-bar Subscript upper X or double-vertical-bar negative eta minus z double-vertical-bar Subscript upper X Baseline greater-than-or-equal-to double-vertical-bar eta double-vertical-bar Subscript upper X . Since upper K equals negative upper K , we conclude that

StartLayout 1st Row with Label left-parenthesis 2.12 right-parenthesis EndLabel d Superscript n Baseline left-parenthesis upper K right-parenthesis Subscript upper X Baseline less-than-or-equal-to sup Underscript eta element-of script upper N intersection upper K Endscripts double-vertical-bar eta minus normal upper Delta left-parenthesis normal upper Phi eta right-parenthesis double-vertical-bar Subscript upper X Baseline period EndLayout

Taking an infimum over all encoder-decoder pairs in script upper A Subscript n comma upper N , we obtain the left inequality in (Equation2.10).

To prove the right inequality, we choose an optimal upper Y for d Superscript n Baseline left-parenthesis upper K right-parenthesis Subscript upper X and use the matrix normal upper Phi associated to upper Y (i.e., the rows of normal upper Phi are a basis for upper Y Superscript up-tack ). We define a decoder normal upper Delta for normal upper Phi as follows. Given y in the range of normal upper Phi , we recall that script upper F left-parenthesis y right-parenthesis is the set of x such that normal upper Phi x equals y . If script upper F left-parenthesis y right-parenthesis intersection upper K not-equals normal empty-set , we take any ModifyingAbove x With bar left-parenthesis y right-parenthesis element-of script upper F left-parenthesis y right-parenthesis intersection upper K and define normal upper Delta left-parenthesis y right-parenthesis colon equals ModifyingAbove x With bar left-parenthesis y right-parenthesis . When script upper F left-parenthesis y right-parenthesis intersection upper K equals normal empty-set , we define normal upper Delta left-parenthesis y right-parenthesis as any element from script upper F left-parenthesis y right-parenthesis . This gives

StartLayout 1st Row with Label left-parenthesis 2.13 right-parenthesis EndLabel upper E Subscript n Baseline left-parenthesis upper K right-parenthesis Subscript upper X Baseline less-than-or-equal-to sup Underscript x comma x prime element-of script upper F left-parenthesis y right-parenthesis intersection upper K Endscripts double-vertical-bar x minus x Superscript prime Baseline double-vertical-bar Subscript upper X Baseline less-than-or-equal-to sup Underscript eta element-of upper C 0 left-bracket upper K intersection script upper N right-bracket Endscripts double-vertical-bar eta double-vertical-bar Subscript upper X Baseline less-than-or-equal-to upper C 0 d Superscript n Baseline left-parenthesis upper K right-parenthesis Subscript upper X Baseline comma EndLayout

where we have used the fact that x minus x prime element-of script upper N and x minus x prime element-of upper C 0 upper K by our assumptions on upper K . This proves the right inequality in (Equation2.10).

The orders of the Gelfand widths of script l Subscript q balls in script l Subscript p are known except perhaps for the case q equals 1 comma p equals normal infinity . For the range of p comma q that is relevant here even the constants are known. We recall the following results of Gluskin, Garnaev and Kashin which can be found in Reference13Reference9Reference14; see also Reference15. For upper K equals upper U left-parenthesis script l Subscript q Superscript upper N Baseline right-parenthesis , we have

StartLayout 1st Row with Label left-parenthesis 2.14 right-parenthesis EndLabel upper C 1 normal upper Psi left-parenthesis n comma upper N comma q comma p right-parenthesis less-than-or-equal-to d Superscript n Baseline left-parenthesis upper K right-parenthesis Subscript script l Sub Subscript p Subscript Baseline less-than-or-equal-to upper C 2 normal upper Psi left-parenthesis n comma upper N comma q comma p right-parenthesis comma EndLayout

where upper C 1 comma upper C 2 only depend on p and q and where

StartLayout 1st Row with Label left-parenthesis 2.15 right-parenthesis EndLabel normal upper Psi left-parenthesis n comma upper N comma q comma p right-parenthesis colon equals left-bracket min left-parenthesis 1 comma upper N Superscript 1 minus 1 slash q Baseline n Superscript negative 1 slash 2 Baseline right-parenthesis right-bracket Superscript StartFraction 1 slash q minus 1 slash p Over 1 slash q minus 1 slash 2 EndFraction Baseline comma 1 less-than-or-equal-to n less-than-or-equal-to upper N comma 1 less-than q less-than p less-than-or-equal-to 2 comma EndLayout

and

StartLayout 1st Row with Label left-parenthesis 2.16 right-parenthesis EndLabel normal upper Psi left-parenthesis n comma upper N comma 1 comma 2 right-parenthesis colon equals min left-brace 1 comma StartRoot StartFraction log left-parenthesis upper N slash n right-parenthesis Over n EndFraction EndRoot right-brace period EndLayout

Since upper K equals upper U left-parenthesis script l Subscript q Superscript upper N Baseline right-parenthesis obviously satisfies the assumptions of Lemma 2.1 with upper C 0 equals 2 , we also have

StartLayout 1st Row with Label left-parenthesis 2.17 right-parenthesis EndLabel upper C 1 normal upper Psi left-parenthesis n comma upper N comma q comma p right-parenthesis less-than-or-equal-to upper E Subscript n Baseline left-parenthesis upper K right-parenthesis Subscript script l Sub Subscript p Subscript Baseline less-than-or-equal-to 2 upper C 2 normal upper Psi left-parenthesis n comma upper N comma q comma p right-parenthesis period EndLayout

From (Equation2.14), (Equation2.16), (Equation2.10) we deduce indeed the announced fact that upper E Subscript n Baseline left-parenthesis upper U left-parenthesis script l 1 Superscript upper N Baseline right-parenthesis right-parenthesis Subscript script l 2 Baseline less-than-or-equal-to upper C 0 sigma Subscript k Baseline left-parenthesis upper U left-parenthesis script l 1 Superscript upper N Baseline right-parenthesis right-parenthesis Subscript script l 2 can only hold when k and the necessary number of measurements n are interrelated by (Equation1.9). The possible range of k for which even instance optimality could hold is therefore also limited by (Equation1.9), a relation that will turn up frequently in what follows.

3. Instance optimality and the null space of normal upper Phi

We now turn to the main question addressed in this paper, namely the study of instance optimality as expressed by (Equation1.11). In this section, we shall see that (Equation1.11) can be reformulated as a property of the null space script upper N of normal upper Phi . As was already remarked in the proof of Lemma 2.1, this null space has codimension not larger than n .

We shall also need to consider sections of normal upper Phi obtained by keeping some of its columns: for upper T subset-of StartSet 1 comma ellipsis comma upper N EndSet , we denote by normal upper Phi Subscript upper T the n times number-sign upper T matrix formed from the columns of normal upper Phi with indices in upper T . Similarly we shall have to deal with restrictions x Subscript upper T of vectors x element-of double-struck upper R Superscript upper N to sets upper T . However, it will be convenient to view such restrictions still as elements of double-struck upper R Superscript upper N , i.e., x Subscript upper T agrees with x on upper T and has all components equal to zero whose indices do not belong to upper T .

We begin by studying under what circumstances the measurement vector y equals normal upper Phi x uniquely determines each k -sparse vector x element-of normal upper Sigma Subscript k . This is expressed by the following trivial lemma.

Lemma 3.1

If normal upper Phi is any n times upper N matrix and 2 k less-than-or-equal-to n , then the following are equivalent:

(i) There is a decoder normal upper Delta such that normal upper Delta left-parenthesis normal upper Phi x right-parenthesis equals x , for all x element-of normal upper Sigma Subscript k .

(ii) normal upper Sigma Subscript 2 k Baseline intersection script upper N equals StartSet 0 EndSet .

(iii) For any set upper T with number-sign upper T equals 2 k , the matrix normal upper Phi Subscript upper T has rank 2 k .

(iv) The symmetric nonnegative matrix normal upper Phi Subscript upper T Superscript t Baseline normal upper Phi Subscript upper T is invertible, i.e., positive definite.

Proof.

The equivalence of (ii), (iii), (iv) is linear algebra.

(i) right double arrow (ii): Suppose (i) holds and x element-of normal upper Sigma Subscript 2 k intersection script upper N . We can write x equals x 0 minus x 1 where both x 0 comma x 1 element-of normal upper Sigma Subscript k Baseline . Since normal upper Phi x 0 equals normal upper Phi x 1 , we have, by (i), that x 0 equals x 1 and hence x equals x 0 minus x 1 equals 0 .

(ii) right double arrow (i): Given any y element-of double-struck upper R Superscript n , we define normal upper Delta left-parenthesis y right-parenthesis to be any element in script upper F left-parenthesis y right-parenthesis with smallest support. Now, if x 1 comma x 2 element-of normal upper Sigma Subscript k Baseline with normal upper Phi x 1 equals normal upper Phi x 2 , then x 1 minus x 2 element-of script upper N intersection normal upper Sigma Subscript 2 k . From (ii), this means that x 1 equals x 2 . Hence, if x element-of normal upper Sigma Subscript k , then normal upper Delta left-parenthesis normal upper Phi x right-parenthesis equals x as desired.

The properties discussed in Lemma 3.1 are algebraic properties of normal upper Phi . If upper N comma k are fixed, the question arises as to how large we need to make n so that there is a matrix normal upper Phi having the properties of the lemma. It is easy to see that we can take n equals 2 k . Indeed, for any k and upper N greater-than-or-equal-to 2 k , we can find a set normal upper Lamda Subscript upper N of upper N vectors in double-struck upper R Superscript 2 k such that any 2 k of them are linearly independent. For example if 0 less-than x 1 less-than x 2 less-than midline-horizontal-ellipsis less-than x Subscript upper N , then the matrix whose left-parenthesis i comma j right-parenthesis entry is x Subscript j Superscript i minus 1 has the properties of Lemma 3.1. Its 2 k times 2 k minors are Vandermonde matrices which are well known to be nonsingular. Unfortunately, such matrices are poorly conditioned when upper N is large and the process of recovering x element-of normal upper Sigma Subscript k from y equals normal upper Phi x is therefore numerically unstable.

Stable recovery procedures have been proposed by Candès, Romberg, and Tao and by Donoho under stronger conditions on normal upper Phi . We shall make heavy use in this paper of the following property introduced by Candès and Tao. We say that normal upper Phi satisfies the restricted isometry property (RIP) of order k if there is a 0 less-than delta Subscript k Baseline less-than 1 such that

StartLayout 1st Row with Label left-parenthesis 3.1 right-parenthesis EndLabel left-parenthesis 1 minus delta Subscript k Baseline right-parenthesis double-vertical-bar z double-vertical-bar Subscript script l 2 Baseline less-than-or-equal-to double-vertical-bar normal upper Phi Subscript upper T Baseline z double-vertical-bar Subscript script l 2 Baseline less-than-or-equal-to left-parenthesis 1 plus delta Subscript k Baseline right-parenthesis double-vertical-bar z double-vertical-bar Subscript script l 2 Baseline comma z element-of double-struck upper R Superscript upper N Baseline comma EndLayout

holds for all upper T of cardinality k .Footnote1 The RIP condition could be replaced by the assumption that upper C 0 double-vertical-bar z double-vertical-bar Subscript script l 2 Baseline less-than-or-equal-to double-vertical-bar normal upper Phi Subscript upper T Baseline z double-vertical-bar Subscript script l 2 Baseline less-than-or-equal-to upper C 1 double-vertical-bar z double-vertical-bar Subscript script l 2 holds for all number-sign left-parenthesis upper T right-parenthesis equals k , with absolute constants upper C 0 comma upper C 1 in all that follows. However, this latter condition is equivalent to having a rescaled matrix alpha normal upper Phi satisfy RIP for some alpha and the rescaled matrix extracts exactly the same information from a vector x as normal upper Phi does. The RIP condition is equivalent to saying that the symmetric matrix normal upper Phi Subscript upper T Superscript t Baseline normal upper Phi Subscript upper T is positive definite with eigenvalues in left-bracket left-parenthesis 1 minus delta Subscript k Baseline right-parenthesis squared comma left-parenthesis 1 plus delta Subscript k Baseline right-parenthesis squared right-bracket . Note that RIP of order k always implies RIP of order l less-than-or-equal-to k . Note also that RIP of order 2 k guarantees that the properties of Lemma 3.1 hold.

Candès and Tao have shown that any matrix normal upper Phi which satisfies the RIP property for k and sufficiently small delta Subscript k will extract enough information about x to approximate it well and moreover the decoding can be done by script l 1 minimization. The key question then is, given a fixed n comma upper N , how large can we take k and still have matrices which satisfy RIP for k ? It was shown by Candès and Tao Reference5, as well as Donoho Reference8, that certain families of random matrices will, with high probability, satisfy RIP of order k with delta Subscript k Baseline less-than-or-equal-to delta less-than 1 for some prescribed delta independent of upper N provided k less-than-or-equal-to c 0 n slash log left-parenthesis upper N slash k right-parenthesis . Here c 0 is a constant which when made small will make delta Subscript k small as well. It should be stressed that all available constructions of such matrices (so far) involve random variables. For instance, as we shall recall in more detail in §6, the entries of normal upper Phi can be picked as i.i.d. Gaussian or Bernoulli variables with proper normalization.

We turn to the question of whether y contains enough information to approximate x to accuracy sigma Subscript k Baseline left-parenthesis x right-parenthesis as expressed by (Equation1.11). The following theorem shows that this can be understood through the study of the null space script upper N of normal upper Phi .

Theorem 3.2

Given an n times upper N matrix normal upper Phi , a norm double-vertical-bar dot double-vertical-bar Subscript upper X and a value of k , then a sufficient condition that there exists a decoder normal upper Delta such that (Equation1.11) holds with constant upper C 0 is that

StartLayout 1st Row with Label left-parenthesis 3.2 right-parenthesis EndLabel double-vertical-bar eta double-vertical-bar Subscript upper X Baseline less-than-or-equal-to StartFraction upper C 0 Over 2 EndFraction sigma Subscript 2 k Baseline left-parenthesis eta right-parenthesis Subscript upper X Baseline comma eta element-of script upper N period EndLayout

A necessary condition is that

StartLayout 1st Row with Label left-parenthesis 3.3 right-parenthesis EndLabel double-vertical-bar eta double-vertical-bar Subscript upper X Baseline less-than-or-equal-to upper C 0 sigma Subscript 2 k Baseline left-parenthesis eta right-parenthesis Subscript upper X Baseline comma eta element-of script upper N period EndLayout

Proof.

To prove the sufficiency of (Equation3.2), we will define a decoder normal upper Delta for normal upper Phi as follows. Given any y element-of double-struck upper R Superscript upper N , we consider the set script upper F left-parenthesis y right-parenthesis and choose

StartLayout 1st Row with Label left-parenthesis 3.4 right-parenthesis EndLabel normal upper Delta left-parenthesis y right-parenthesis colon equals normal upper A times normal r times normal g times normal m times normal i times normal n Underscript z element-of script upper F left-parenthesis y right-parenthesis Endscripts sigma Subscript k Baseline left-parenthesis z right-parenthesis Subscript upper X Baseline period EndLayout

We shall prove that for all x element-of double-struck upper R Superscript upper N

StartLayout 1st Row with Label left-parenthesis 3.5 right-parenthesis EndLabel double-vertical-bar x minus normal upper Delta left-parenthesis normal upper Phi x right-parenthesis double-vertical-bar Subscript upper X Baseline less-than-or-equal-to upper C 0 sigma Subscript k Baseline left-parenthesis x right-parenthesis Subscript upper X Baseline period EndLayout

Indeed, eta colon equals x minus normal upper Delta left-parenthesis normal upper Phi x right-parenthesis is in script upper N and hence by (Equation3.2), we have

StartLayout 1st Row 1st Column double-vertical-bar x minus normal upper Delta left-parenthesis normal upper Phi x right-parenthesis double-vertical-bar Subscript upper X 2nd Column less-than-or-equal-to left-parenthesis upper C 0 slash 2 right-parenthesis sigma Subscript 2 k Baseline left-parenthesis x minus normal upper Delta left-parenthesis normal upper Phi x right-parenthesis right-parenthesis Subscript upper X Baseline 2nd Row 1st Column Blank 2nd Column less-than-or-equal-to left-parenthesis upper C 0 slash 2 right-parenthesis left-parenthesis sigma Subscript k Baseline left-parenthesis x right-parenthesis Subscript upper X Baseline plus sigma Subscript k Baseline left-parenthesis normal upper Delta left-parenthesis normal upper Phi x right-parenthesis Subscript upper X Baseline right-parenthesis 3rd Row 1st Column Blank 2nd Column less-than-or-equal-to upper C 0 sigma Subscript k Baseline left-parenthesis x right-parenthesis Subscript upper X Baseline comma EndLayout

where the second inequality uses the fact that sigma Subscript 2 k Baseline left-parenthesis x plus z right-parenthesis Subscript upper X Baseline less-than-or-equal-to sigma Subscript k Baseline left-parenthesis x right-parenthesis Subscript upper X Baseline plus sigma Subscript k Baseline left-parenthesis z right-parenthesis Subscript upper X and the last inequality uses the fact that normal upper Delta left-parenthesis normal upper Phi x right-parenthesis minimizes sigma Subscript k Baseline left-parenthesis z right-parenthesis over script upper F left-parenthesis y right-parenthesis .

To prove the necessity of (Equation3.3), let normal upper Delta be any decoder for which (Equation1.11) holds. Let eta be any element in script upper N equals script upper N left-parenthesis normal upper Phi right-parenthesis and let eta 0 be the best 2 k -term approximation of eta in upper X . Letting eta 0 equals eta 1 plus eta 2 be any splitting of eta 0 into two vectors of support size k , we can write

StartLayout 1st Row with Label left-parenthesis 3.6 right-parenthesis EndLabel eta equals eta 1 plus eta 2 plus eta 3 comma EndLayout

with eta 3 equals eta minus eta 0 . Since minus eta 1 element-of normal upper Sigma Subscript k , we have by (Equation1.11) that minus eta 1 equals normal upper Delta left-parenthesis normal upper Phi left-parenthesis minus eta 1 right-parenthesis right-parenthesis , but since eta element-of script upper N , we also have minus normal upper Phi eta 1 equals normal upper Phi left-parenthesis eta 2 plus eta 3 right-parenthesis so that minus eta 1 equals normal upper Delta left-parenthesis normal upper Phi left-parenthesis eta 2 plus eta 3 right-parenthesis right-parenthesis . Using again (Equation1.11), we derive

StartLayout 1st Row 1st Column double-vertical-bar eta double-vertical-bar Subscript upper X 2nd Column equals 3rd Column double-vertical-bar eta 2 plus eta 3 minus normal upper Delta left-parenthesis normal upper Phi left-parenthesis eta 2 plus eta 3 right-parenthesis right-parenthesis double-vertical-bar Subscript upper X Baseline less-than-or-equal-to upper C 0 sigma Subscript k Baseline left-parenthesis eta 2 plus eta 3 right-parenthesis 2nd Row 1st Column Blank 2nd Column less-than-or-equal-to 3rd Column upper C 0 double-vertical-bar eta 3 double-vertical-bar Subscript upper X Baseline equals upper C 0 sigma Subscript 2 k Baseline left-parenthesis eta right-parenthesis comma EndLayout

which is (Equation3.3).

When upper X is an script l Subscript p space, the best k -term approximation is obtained by leaving the k largest components of x unchanged and setting all the others to 0 . Therefore the property

StartLayout 1st Row with Label left-parenthesis 3.7 right-parenthesis EndLabel double-vertical-bar eta double-vertical-bar Subscript upper X Baseline less-than-or-equal-to upper C sigma Subscript k Baseline left-parenthesis eta right-parenthesis Subscript upper X EndLayout

can be reformulated by saying that

StartLayout 1st Row with Label left-parenthesis 3.8 right-parenthesis EndLabel double-vertical-bar eta double-vertical-bar Subscript upper X Baseline less-than-or-equal-to upper C double-vertical-bar eta Subscript upper T Sub Superscript c Subscript Baseline double-vertical-bar Subscript upper X EndLayout

holds for all upper T subset-of StartSet 1 comma period period period comma upper N EndSet such that number-sign upper T less-than-or-equal-to k , where upper T Superscript c is the complement set of upper T in StartSet 1 comma period period period comma upper N EndSet . In going further, we shall say that normal upper Phi has the null space property in upper X of order k with constant upper C if (Equation3.8) holds for all eta element-of script upper N and number-sign upper T less-than-or-equal-to k . Thus, we have

Corollary 3.3

Suppose that upper X is an script l Subscript p Superscript upper N space, k greater-than 0 an integer and normal upper Phi an encoding matrix. If normal upper Phi has the null space property (Equation3.8) in upper X of order 2 k with constant upper C 0 slash 2 , then there exists a decoder normal upper Delta so that left-parenthesis normal upper Phi comma normal upper Delta right-parenthesis satisfies (Equation1.11) with constant upper C 0 . Conversely, the validity of (Equation1.11) for some decoder normal upper Delta implies that normal upper Phi has the null space property (Equation3.8) in upper X of order 2 k with constant upper C 0 .

In the next two sections, we shall use this corollary in order to study instance optimality in the case where the upper X norm is script l 1 and script l 2 , respectively.

4. The case upper X equals script l 1

In this section, we shall study the null space property (Equation3.8) in the case where upper X equals script l 1 . We shall make use of the restricted isometry property (Equation3.1) introduced by Candès and Tao. We begin with the following lemma whose proof is inspired by results in Reference4.

Lemma 4.1

Let a equals script l slash k , b equals script l prime slash k with script l comma script l prime greater-than-or-equal-to k integers. If normal upper Phi is any matrix which satisfies the RIP of order left-parenthesis a plus b right-parenthesis k with delta equals delta Subscript left-parenthesis a plus b right-parenthesis k Baseline less-than 1 . Then normal upper Phi satisfies the null space property in script l 1 of order a k with constant upper C 0 equals 1 plus StartFraction StartRoot a EndRoot left-parenthesis 1 plus delta right-parenthesis Over StartRoot b EndRoot left-parenthesis 1 minus delta right-parenthesis EndFraction .

Proof.

It is enough to prove (Equation3.8) in the case when upper T is the set of indices of the largest a k entries of eta . Let upper T 0 equals upper T , upper T 1 denote the set of indices of the next b k largest entries of eta , upper T 2 the next b k largest, and so on. The last set upper T Subscript s defined this way may have less than b k elements.

We define eta 0 colon equals eta Subscript upper T 0 plus eta Subscript upper T 1 . Since eta element-of script upper N , we have normal upper Phi eta 0 equals minus normal upper Phi left-parenthesis eta Subscript upper T 2 Baseline plus dot dot dot plus eta Subscript upper T Sub Subscript s Subscript Baseline right-parenthesis , so that

StartLayout 1st Row 1st Column double-vertical-bar eta Subscript upper T Baseline double-vertical-bar Subscript script l 2 2nd Column less-than-or-equal-to 3rd Column double-vertical-bar eta 0 double-vertical-bar Subscript script l 2 Baseline less-than-or-equal-to left-parenthesis 1 minus delta right-parenthesis Superscript negative 1 Baseline double-vertical-bar normal upper Phi eta 0 double-vertical-bar Subscript script l 2 Baseline equals left-parenthesis 1 minus delta right-parenthesis Superscript negative 1 Baseline double-vertical-bar normal upper Phi left-parenthesis eta Subscript upper T 2 Baseline plus dot dot dot plus eta Subscript upper T Sub Subscript s Subscript Baseline right-parenthesis double-vertical-bar Subscript script l 2 Baseline 2nd Row 1st Column Blank 2nd Column less-than-or-equal-to 3rd Column left-parenthesis 1 minus delta right-parenthesis Superscript negative 1 Baseline sigma-summation Underscript j equals 2 Overscript s Endscripts double-vertical-bar normal upper Phi eta Subscript upper T Sub Subscript j Subscript Baseline double-vertical-bar Subscript script l 2 Baseline less-than-or-equal-to left-parenthesis 1 plus delta right-parenthesis left-parenthesis 1 minus delta right-parenthesis Superscript negative 1 Baseline sigma-summation Underscript j equals 2 Overscript s Endscripts double-vertical-bar eta Subscript upper T Sub Subscript j Subscript Baseline double-vertical-bar Subscript script l 2 Baseline comma EndLayout

where we have used both bounds in (Equation3.1). Now for any i element-of upper T Subscript j plus 1 and i prime element-of upper T Subscript j , we have StartAbsoluteValue eta Subscript i Baseline EndAbsoluteValue less-than-or-equal-to StartAbsoluteValue eta Subscript i prime Baseline EndAbsoluteValue so that StartAbsoluteValue eta Subscript i Baseline EndAbsoluteValue less-than-or-equal-to left-parenthesis b k right-parenthesis Superscript negative 1 Baseline double-vertical-bar eta Subscript upper T Sub Subscript j Subscript Baseline double-vertical-bar Subscript script l 1 . It follows that

StartLayout 1st Row with Label left-parenthesis 4.1 right-parenthesis EndLabel double-vertical-bar eta Subscript upper T Sub Subscript j plus 1 Subscript Baseline double-vertical-bar Subscript script l 2 Baseline less-than-or-equal-to left-parenthesis b k right-parenthesis Superscript negative 1 slash 2 Baseline double-vertical-bar eta Subscript upper T Sub Subscript j Subscript Baseline double-vertical-bar Subscript script l 1 Baseline comma j equals 1 comma 2 comma ellipsis comma s minus 1 comma EndLayout

so that

StartLayout 1st Row with Label left-parenthesis 4.2 right-parenthesis EndLabel StartLayout 1st Row 1st Column double-vertical-bar eta Subscript upper T Baseline double-vertical-bar Subscript script l 2 2nd Column less-than-or-equal-to left-parenthesis 1 plus delta right-parenthesis left-parenthesis 1 minus delta right-parenthesis Superscript negative 1 Baseline left-parenthesis b k right-parenthesis Superscript negative 1 slash 2 Baseline sigma-summation Underscript j equals 1 Overscript s minus 1 Endscripts double-vertical-bar eta Subscript upper T Sub Subscript j Subscript Baseline double-vertical-bar Subscript script l 1 Baseline 2nd Row 1st Column Blank 2nd Column less-than-or-equal-to left-parenthesis 1 plus delta right-parenthesis left-parenthesis 1 minus delta right-parenthesis Superscript negative 1 Baseline left-parenthesis b k right-parenthesis Superscript negative 1 slash 2 Baseline double-vertical-bar eta Subscript upper T Sub Superscript c Subscript Baseline double-vertical-bar Subscript script l 1 Baseline period EndLayout EndLayout

By the Cauchy-Schwartz inequality double-vertical-bar eta Subscript upper T Baseline double-vertical-bar Subscript script l 1 Baseline less-than-or-equal-to left-parenthesis a k right-parenthesis Superscript 1 slash 2 Baseline double-vertical-bar eta Subscript upper T Baseline double-vertical-bar Subscript script l 2 , and we therefore obtain

StartLayout 1st Row with Label left-parenthesis 4.3 right-parenthesis EndLabel double-vertical-bar eta double-vertical-bar Subscript script l 1 Baseline equals double-vertical-bar eta Subscript upper T Baseline double-vertical-bar Subscript script l 1 Baseline plus double-vertical-bar eta Subscript upper T Sub Superscript c Subscript Baseline double-vertical-bar Subscript script l 1 Baseline less-than-or-equal-to left-parenthesis 1 plus StartFraction StartRoot a EndRoot left-parenthesis 1 plus delta right-parenthesis Over StartRoot b EndRoot left-parenthesis 1 minus delta right-parenthesis EndFraction right-parenthesis double-vertical-bar eta Subscript upper T Sub Superscript c Subscript Baseline double-vertical-bar Subscript script l 1 Baseline comma EndLayout

which verifies the null space property with the constant upper C 0 .

Combining Corollary 3.3 and Lemma 4.1 (with a equals 2 and b equals 1 ), we have therefore proved the following.

Theorem 4.2

Let normal upper Phi be any matrix which satisfies the RIP of order 3 k . Define the decoder normal upper Delta for normal upper Phi as in (Equation3.4) for upper X equals script l 1 . Then (Equation1.11) holds in upper X equals script l 1 with constant upper C 0 equals 2 left-parenthesis 1 plus StartRoot 2 EndRoot StartFraction 1 plus delta Over 1 minus delta EndFraction right-parenthesis . Generally speaking, we cannot derive a constant of the type 1 plus epsilon from an analysis based on Lemma 4.1, since it requires that the null space property holds with constant upper C 0 slash 2 which is therefore larger than 1 .

As was mentioned in the previous section, one can build matrices normal upper Phi which satisfy the RIP of order k under the condition n greater-than-or-equal-to c k log left-parenthesis upper N slash n right-parenthesis where c is some fixed constant. We therefore conclude that instance optimality of order k in the script l 1 norm can be achieved at the price of script upper O left-parenthesis k log left-parenthesis upper N slash n right-parenthesis right-parenthesis measurements.

Remark 4.3

More generally, if normal upper Phi satisfies the RIP of order left-parenthesis 2 plus b right-parenthesis k and normal upper Delta is defined by (Equation3.4) for upper X equals script l 1 , then (Equation1.11) holds in upper X equals script l 1 with constant upper C 0 equals 2 left-parenthesis 1 plus StartRoot 2 slash b EndRoot StartFraction 1 plus delta Over 1 minus delta EndFraction right-parenthesis . Therefore, if we make b large, the constant upper C 0 in (Equation1.11) is of the type 2 plus epsilon under a condition of the type n greater-than-or-equal-to c StartFraction k Over epsilon squared EndFraction log left-parenthesis upper N slash n right-parenthesis .

Note that on the other hand, since instance optimality of order k in any norm upper X always implies that the reconstruction is exact when x element-of normal upper Sigma Subscript k , it cannot be achieved with less than 2 k measurements according to Lemma 3.1.

Before addressing the script l 2 case, let us briefly discuss the decoder normal upper Delta which achieves (Equation1.11) for such a normal upper Phi . According to the proof of Theorem 3.2, one can build normal upper Delta as the solution of the minimization problem (Equation3.4). It is not clear to us whether this minimization problem can be solved in polynomial time in upper N . The following result shows that it is possible to define normal upper Delta by script l 1 minimization if normal upper Phi satisfies the RIP with some additional control on the constants in (Equation3.1).

Theorem 4.4

Let normal upper Phi be any matrix which satisfies the RIP of order 3 k with delta Subscript 3 k Baseline less-than-or-equal-to delta less-than left-parenthesis StartRoot 2 EndRoot minus 1 right-parenthesis squared slash 3 . Define the decoder normal upper Delta for normal upper Phi as in (Equation1.10). Then, left-parenthesis normal upper Phi comma normal upper Delta right-parenthesis satisfies (Equation1.11) in upper X equals script l 1 with upper C 0 equals StartFraction 2 StartRoot 2 EndRoot plus 2 minus left-parenthesis 2 StartRoot 2 EndRoot minus 2 right-parenthesis delta Over StartRoot 2 EndRoot minus 1 minus left-parenthesis StartRoot 2 EndRoot plus 1 right-parenthesis delta EndFraction .

Proof.

We apply Lemma 4.1 with a equals 1 , b equals 2 to see that normal upper Phi satisfies the null space property in script l 1 of order k with constant upper C equals 1 plus StartFraction 1 plus delta Over StartRoot 2 EndRoot left-parenthesis 1 minus delta right-parenthesis EndFraction less-than 2 . This means that for any eta element-of script upper N and upper T such that number-sign upper T less-than-or-equal-to k , we have

StartLayout 1st Row with Label left-parenthesis 4.4 right-parenthesis EndLabel double-vertical-bar eta double-vertical-bar Subscript script l 1 Baseline less-than-or-equal-to upper C double-vertical-bar eta Subscript upper T Sub Superscript c Subscript Baseline double-vertical-bar Subscript script l 1 Baseline comma EndLayout

and therefore

StartLayout 1st Row with Label left-parenthesis 4.5 right-parenthesis EndLabel double-vertical-bar eta Subscript upper T Baseline double-vertical-bar Subscript script l 1 Baseline less-than-or-equal-to left-parenthesis upper C minus 1 right-parenthesis double-vertical-bar eta Subscript upper T Sub Superscript c Subscript Baseline double-vertical-bar Subscript script l 1 Baseline period EndLayout

Let x Superscript asterisk Baseline equals normal upper Delta left-parenthesis normal upper Phi x right-parenthesis be the solution of (Equation1.10) so that eta equals x Superscript asterisk Baseline minus x element-of script upper N and

StartLayout 1st Row with Label left-parenthesis 4.6 right-parenthesis EndLabel double-vertical-bar x Superscript asterisk Baseline double-vertical-bar Subscript script l 1 Baseline less-than-or-equal-to double-vertical-bar x double-vertical-bar Subscript script l 1 Baseline period EndLayout

Denoting by upper T the set of indices of the largest k coefficients of x , we can write

StartLayout 1st Row with Label left-parenthesis 4.7 right-parenthesis EndLabel double-vertical-bar x Subscript upper T Superscript asterisk Baseline double-vertical-bar Subscript script l 1 Baseline plus double-vertical-bar x Subscript upper T Sub Superscript c Subscript Superscript asterisk Baseline double-vertical-bar Subscript script l 1 Baseline less-than-or-equal-to double-vertical-bar x Subscript upper T Baseline double-vertical-bar Subscript script l 1 Baseline plus double-vertical-bar x Subscript upper T Sub Superscript c Subscript Baseline double-vertical-bar Subscript script l 1 Baseline period EndLayout

It follows that

StartLayout 1st Row with Label left-parenthesis 4.8 right-parenthesis EndLabel double-vertical-bar x Subscript upper T Baseline double-vertical-bar Subscript script l 1 Baseline minus double-vertical-bar eta Subscript upper T Baseline double-vertical-bar Subscript script l 1 Baseline plus double-vertical-bar eta Subscript upper T Sub Superscript c Subscript Baseline double-vertical-bar Subscript script l 1 Baseline minus double-vertical-bar x Subscript upper T Sub Superscript c Subscript Baseline double-vertical-bar Subscript script l 1 Baseline less-than-or-equal-to double-vertical-bar x Subscript upper T Baseline double-vertical-bar Subscript script l 1 Baseline plus double-vertical-bar x Subscript upper T Sub Superscript c Subscript Baseline double-vertical-bar Subscript script l 1 Baseline comma EndLayout

and therefore

StartLayout 1st Row with Label left-parenthesis 4.9 right-parenthesis EndLabel double-vertical-bar eta Subscript upper T Sub Superscript c Subscript Baseline double-vertical-bar Subscript script l 1 Baseline less-than-or-equal-to double-vertical-bar eta Subscript upper T Baseline double-vertical-bar Subscript script l 1 Baseline plus 2 double-vertical-bar x Subscript upper T Sub Superscript c Subscript Baseline double-vertical-bar Subscript script l 1 Baseline equals double-vertical-bar eta Subscript upper T Baseline double-vertical-bar Subscript script l 1 Baseline plus 2 sigma Subscript k Baseline left-parenthesis x right-parenthesis Subscript script l 1 Baseline period EndLayout

Using (Equation4.5) and the fact that upper C less-than 2 , we thus obtain

StartLayout 1st Row with Label left-parenthesis 4.10 right-parenthesis EndLabel double-vertical-bar eta Subscript upper T Sub Superscript c Subscript Baseline double-vertical-bar Subscript script l 1 Baseline less-than-or-equal-to StartFraction 2 Over 2 minus upper C EndFraction sigma Subscript k Baseline left-parenthesis x right-parenthesis Subscript script l 1 Baseline period EndLayout

We finally use again (Equation4.4) to conclude that

StartLayout 1st Row with Label left-parenthesis 4.11 right-parenthesis EndLabel double-vertical-bar x minus x Superscript asterisk Baseline double-vertical-bar Subscript script l 1 Baseline less-than-or-equal-to StartFraction 2 upper C Over 2 minus upper C EndFraction sigma Subscript k Baseline left-parenthesis x right-parenthesis Subscript script l 1 Baseline comma EndLayout

which is the announced result.

5. The case upper X equals script l 2

In this section, we shall show that instance optimality is not a very viable concept in upper X equals script l 2 in the sense that it will not even hold for k equals 1 unless n greater-than-or-equal-to c upper N . We know from Corollary 3.3 that if normal upper Phi is a matrix of size n times upper N which satisfies

StartLayout 1st Row with Label left-parenthesis 5.1 right-parenthesis EndLabel double-vertical-bar x minus normal upper Delta left-parenthesis normal upper Phi x right-parenthesis double-vertical-bar Subscript script l 2 Baseline less-than-or-equal-to upper C 0 sigma Subscript k Baseline left-parenthesis x right-parenthesis Subscript script l 2 Baseline comma x element-of double-struck upper R Superscript upper N Baseline comma EndLayout

for some decoder normal upper Delta , then its null space script upper N will need to have the property

StartLayout 1st Row with Label left-parenthesis 5.2 right-parenthesis EndLabel double-vertical-bar eta double-vertical-bar Subscript script l 2 Superscript 2 Baseline less-than-or-equal-to upper C 0 squared double-vertical-bar eta Subscript upper T Sub Superscript c Subscript Baseline double-vertical-bar Subscript script l 2 Superscript 2 Baseline comma number-sign upper T less-than-or-equal-to 2 k period EndLayout

Theorem 5.1

For any matrix normal upper Phi of dimension n times upper N , property (Equation5.2) with k equals 1 implies that upper N less-than-or-equal-to upper C 0 squared n .

Proof.

We start from (Equation5.2) with k equals 1 from which we trivially derive

StartLayout 1st Row with Label left-parenthesis 5.3 right-parenthesis EndLabel double-vertical-bar eta double-vertical-bar Subscript script l 2 Superscript 2 Baseline less-than-or-equal-to upper C 0 squared double-vertical-bar eta Subscript upper T Sub Superscript c Subscript Baseline double-vertical-bar Subscript script l 2 Superscript 2 Baseline comma number-sign upper T less-than-or-equal-to 1 comma EndLayout

or equivalently for all j element-of StartSet 1 comma period period period comma upper N EndSet ,

StartLayout 1st Row with Label left-parenthesis 5.4 right-parenthesis EndLabel sigma-summation Underscript i equals 1 Overscript upper N Endscripts StartAbsoluteValue eta Subscript i Baseline EndAbsoluteValue squared less-than-or-equal-to upper C 0 squared sigma-summation Underscript i not-equals j Endscripts StartAbsoluteValue eta Subscript i Baseline EndAbsoluteValue squared period EndLayout

From this, we derive that for all j element-of StartSet 1 comma period period period comma upper N EndSet ,

StartLayout 1st Row with Label left-parenthesis 5.5 right-parenthesis EndLabel StartAbsoluteValue eta Subscript j Baseline EndAbsoluteValue squared less-than-or-equal-to left-parenthesis upper C 0 squared minus 1 right-parenthesis sigma-summation Underscript i not-equals j Endscripts StartAbsoluteValue eta Subscript i Baseline EndAbsoluteValue squared equals left-parenthesis upper C 0 squared minus 1 right-parenthesis left-parenthesis double-vertical-bar eta double-vertical-bar Subscript script l 2 Superscript 2 Baseline minus StartAbsoluteValue eta Subscript j Baseline EndAbsoluteValue squared right-parenthesis comma EndLayout

and therefore

StartLayout 1st Row with Label left-parenthesis 5.6 right-parenthesis EndLabel StartAbsoluteValue eta Subscript j Baseline EndAbsoluteValue squared less-than-or-equal-to upper A double-vertical-bar eta double-vertical-bar Subscript script l 2 Superscript 2 Baseline comma EndLayout

with upper A equals 1 minus StartFraction 1 Over upper C 0 squared EndFraction .

Let left-parenthesis e Subscript j Baseline right-parenthesis Subscript j equals 1 comma period period period comma upper N be the canonical basis of double-struck upper R Superscript upper N so that eta Subscript j Baseline equals mathematical left-angle eta comma e Subscript j Baseline mathematical right-angle and let v 1 comma ellipsis comma v Subscript upper N minus n Baseline be an orthonormal basis for script upper N . Denoting by upper P equals upper P Subscript script upper N the orthognal projection onto script upper N , we apply (Equation5.6) to eta colon equals upper P left-parenthesis e Subscript j Baseline right-parenthesis element-of script upper N and find that for any j element-of StartSet 1 comma ellipsis comma upper N EndSet

StartLayout 1st Row with Label left-parenthesis 5.7 right-parenthesis EndLabel StartAbsoluteValue mathematical left-angle upper P left-parenthesis e Subscript j Baseline right-parenthesis comma e Subscript j Baseline mathematical right-angle EndAbsoluteValue squared less-than-or-equal-to upper A period EndLayout

This means

StartLayout 1st Row with Label left-parenthesis 5.8 right-parenthesis EndLabel sigma-summation Underscript i equals 1 Overscript upper N minus n Endscripts StartAbsoluteValue mathematical left-angle e Subscript j Baseline comma v Subscript i Baseline mathematical right-angle EndAbsoluteValue squared less-than-or-equal-to upper A comma j equals 1 comma ellipsis comma upper N period EndLayout

We sum (Equation5.8) over j element-of StartSet 1 comma ellipsis comma upper N EndSet and find

StartLayout 1st Row with Label left-parenthesis 5.9 right-parenthesis EndLabel upper N minus n equals sigma-summation Underscript i equals 1 Overscript upper N minus n Endscripts double-vertical-bar v Subscript i Baseline double-vertical-bar Subscript script l 2 Superscript 2 Baseline less-than-or-equal-to upper A upper N period EndLayout

It follows that left-parenthesis 1 minus upper A right-parenthesis upper N less-than-or-equal-to n . That is, upper N less-than-or-equal-to n upper C 0 squared as desired.

The above result means that when measuring the error in script l 2 , the comparison between compressed sensing and best k -term approximation on a general vector of double-struck upper R Superscript n is strongly in favor of best k -term approximation. However, this conclusion should be moderated in two ways. On the one hand, we shall see in §8 that one can obtain mixed-norm estimates of the form (Equation1.15) from which one finds that compressed sensing compares favorably with best k -term approximation over sufficiently concentrated classes of vectors. On the other hand, we shall prove in the next section that (Equation5.1) can be achieved with n of the same order as k up to a logarithmic factor, if one accepts that this result holds with high probability.

6. The case upper X equals script l 2 in probability

In order to formulate the results of this section, we let normal upper Omega be a probability space with probability measure upper P and let normal upper Phi equals normal upper Phi left-parenthesis omega right-parenthesis , omega element-of normal upper Omega , be an n times upper N random matrix. We seek results of the following type: for any x element-of double-struck upper R Superscript upper N , if we draw normal upper Phi at random with respect to upper P , then

StartLayout 1st Row with Label left-parenthesis 6.1 right-parenthesis EndLabel double-vertical-bar x minus normal upper Delta left-parenthesis normal upper Phi x right-parenthesis double-vertical-bar Subscript script l 2 Baseline less-than-or-equal-to upper C 0 sigma Subscript k Baseline left-parenthesis x right-parenthesis Subscript script l 2 EndLayout

holds for this particular x with high probability for some decoder normal upper Delta (dependent on the draw normal upper Phi ). We shall even give explicit decoders which will yield this type of inequality. It should be understood that normal upper Phi is drawn independently for each x in contrast to building a normal upper Phi such that (Equation6.1) holds simultaneously for all x element-of double-struck upper R Superscript upper N , which was our original definition of instance optimality.

Two simple instances of random matrices which are often considered in compressed sensing are

(1)

Gaussian matrices: normal upper Phi Subscript i comma j Baseline equals script upper N left-parenthesis 0 comma StartFraction 1 Over n EndFraction right-parenthesis are i.i.d. Gaussian variables of variance 1 slash n ,

(2)

Bernoulli matrices: normal upper Phi Subscript i comma j Baseline equals StartFraction plus-or-minus 1 Over StartRoot n EndRoot EndFraction are i.i.d. Bernoulli variables of variance 1 slash n .

In order to establish such results, we shall need that the random matrix normal upper Phi has two properties which we now describe. The first of these relates to the restricted isometry property which we know plays a fundamental role in the performance of the matrix normal upper Phi in compressed sensing.

Definition 6.1

We say that the random matrix normal upper Phi satisfies RIP of order k with constant delta and probability 1 minus epsilon if there is a set normal upper Omega 0 subset-of normal upper Omega with upper P left-parenthesis normal upper Omega 0 right-parenthesis greater-than-or-equal-to 1 minus epsilon such that for all omega element-of normal upper Omega 0 , the matrix normal upper Phi left-parenthesis omega right-parenthesis satisfies (Equation3.1) with constant delta Subscript k Baseline less-than-or-equal-to delta .

This property has been shown for random matrices of the above Gaussian or Bernoulli type. Namely, given any c greater-than 0 and delta greater-than 0 , there is a constant c 0 greater-than 0 such that for all n greater-than-or-equal-to c 0 k log left-parenthesis upper N slash n right-parenthesis this property will hold with epsilon less-than-or-equal-to e Superscript minus c n ; see Reference2Reference5Reference8Reference16.

The RIP controls the behavior of normal upper Phi on normal upper Sigma Subscript k , or equivalently on all the k dimensional spaces spanned by any subset of StartSet e 1 comma period period period comma e Subscript upper N Baseline EndSet of cardinality k . On the other hand, for a general vector x element-of double-struck upper R Superscript upper N , the image vector normal upper Phi x might have a much larger norm than x . However, for standard constructions of random matrices the probability that normal upper Phi x has large norm is small. We formulate this by the following definition.

Definition 6.2

We say that the random matrix normal upper Phi has the boundedness property with constant upper C and probability 1 minus epsilon if for each x element-of double-struck upper R Superscript upper N , there is a set normal upper Omega 0 left-parenthesis x right-parenthesis subset-of normal upper Omega with upper P left-parenthesis normal upper Omega 0 left-parenthesis x right-parenthesis right-parenthesis greater-than-or-equal-to 1 minus epsilon such that for all omega element-of normal upper Omega 0 left-parenthesis x right-parenthesis ,

StartLayout 1st Row with Label left-parenthesis 6.2 right-parenthesis EndLabel double-vertical-bar normal upper Phi left-parenthesis omega right-parenthesis x double-vertical-bar Subscript script l 2 Baseline less-than-or-equal-to upper C double-vertical-bar x double-vertical-bar Subscript script l 2 Baseline period EndLayout

Note that the property which is required in this definition is clearly weaker than asking that the spectral norm double-vertical-bar normal upper Phi double-vertical-bar colon equals sup Underscript double-vertical-bar x double-vertical-bar Subscript script l 2 Baseline equals 1 Endscripts double-vertical-bar normal upper Phi x double-vertical-bar Subscript script l 2 be not greater than upper C with probability 1 minus epsilon .

Again, this property has been shown for various random families of matrices and in particular for the Gaussian or Bernoulli families. Namely, given any upper C greater-than 1 , this property will hold with constant upper C and epsilon less-than-or-equal-to 2 e Superscript minus beta n with beta equals beta left-parenthesis upper C right-parenthesis greater-than 0 ; see Reference1 or the discussion in Reference2. Thus, the standard constructions of random matrices will satisfy both of these properties.

We now describe our process for decoding y equals normal upper Phi x , when normal upper Phi equals normal upper Phi left-parenthesis omega right-parenthesis is our given realization of the random matrix. Let upper T subset-of StartSet 1 comma ellipsis comma upper N EndSet be any subset of column indices with number-sign left-parenthesis upper T right-parenthesis equals k and let upper X Subscript upper T be the linear subspace of double-struck upper R Superscript upper N which consists of all vectors supported on upper T . For this upper T , we define

StartLayout 1st Row with Label left-parenthesis 6.3 right-parenthesis EndLabel x Subscript upper T Superscript asterisk Baseline colon equals normal upper A times normal r times normal g times normal m times normal i times normal n Underscript z element-of upper X Subscript upper T Baseline Endscripts double-vertical-bar normal upper Phi z minus y double-vertical-bar Subscript script l 2 Baseline period EndLayout

In other words, x Subscript upper T Superscript asterisk is chosen as the least squares minimizer of the residual in approximation by elements of upper X Subscript upper T . Notice that x Subscript upper T Superscript asterisk is supported on upper T . If normal upper Phi satisfies RIP of order k , then the matrix normal upper Phi Subscript upper T Superscript t Baseline normal upper Phi Subscript upper T is nonsingular and the nonzero entries of x Subscript upper T Superscript asterisk are given by

StartLayout 1st Row with Label left-parenthesis 6.4 right-parenthesis EndLabel left-parenthesis normal upper Phi Subscript upper T Superscript t Baseline normal upper Phi Subscript upper T Baseline right-parenthesis Superscript negative 1 Baseline normal upper Phi Subscript upper T Superscript t Baseline y period EndLayout

To decode y , we search over all subsets upper T of cardinality k and choose

StartLayout 1st Row with Label left-parenthesis 6.5 right-parenthesis EndLabel upper T Superscript asterisk Baseline colon equals normal upper A times normal r times normal g times normal m times normal i times normal n Underscript number-sign left-parenthesis upper T right-parenthesis equals k Endscripts double-vertical-bar y minus normal upper Phi x Subscript upper T Superscript asterisk Baseline double-vertical-bar Subscript script l 2 Sub Superscript n Subscript Baseline period EndLayout

Our decoding of y is now given by

StartLayout 1st Row with Label left-parenthesis 6.6 right-parenthesis EndLabel x Superscript asterisk Baseline equals normal upper Delta left-parenthesis y right-parenthesis colon equals x Subscript upper T Sub Superscript asterisk Subscript Superscript asterisk Baseline period EndLayout

The main result of this section is the following.

Theorem 6.3

Assume that normal upper Phi is a random matrix which satisfies RIP of order 2 k with constant delta and probability 1 minus epsilon and also satisfies the boundedness property with constant upper C and probability 1 minus epsilon . Then, for each x element-of double-struck upper R Superscript upper N , there exists a set normal upper Omega left-parenthesis x right-parenthesis subset-of normal upper Omega with upper P left-parenthesis normal upper Omega left-parenthesis x right-parenthesis right-parenthesis greater-than-or-equal-to 1 minus 2 epsilon such that for all omega element-of normal upper Omega left-parenthesis x right-parenthesis and normal upper Phi equals normal upper Phi left-parenthesis omega right-parenthesis , the estimate (Equation6.1) holds with upper C 0 equals 1 plus StartFraction 2 upper C Over 1 minus delta EndFraction . Here the decoder normal upper Delta equals normal upper Delta left-parenthesis omega right-parenthesis is given by (Equation6.6).

Proof.

Let x element-of double-struck upper R Superscript upper N be arbitrary and let normal upper Phi equals normal upper Phi left-parenthesis omega right-parenthesis be the draw of the matrix normal upper Phi from the random ensemble. We denote by upper T the set of indices corresponding to the k largest coefficients of x . Thus

StartLayout 1st Row with Label left-parenthesis 6.7 right-parenthesis EndLabel double-vertical-bar x minus x Subscript upper T Baseline double-vertical-bar Subscript script l 2 Baseline equals sigma Subscript k Baseline left-parenthesis x right-parenthesis Subscript script l 2 Baseline period EndLayout

We consider the set normal upper Omega prime colon equals normal upper Omega 0 intersection normal upper Omega left-parenthesis x minus x Subscript upper T Baseline right-parenthesis where normal upper Omega 0 is the set in the definition of RIP in probability and normal upper Omega left-parenthesis x minus x Subscript upper T Baseline right-parenthesis is the set in the definition of boundedness in probability for the vector x minus x Subscript upper T . Then upper P left-parenthesis normal upper Omega prime right-parenthesis greater-than-or-equal-to 1 minus 2 epsilon . For any omega element-of normal upper Omega prime , we have

StartLayout 1st Row with Label left-parenthesis 6.8 right-parenthesis EndLabel double-vertical-bar x minus x Superscript asterisk Baseline double-vertical-bar Subscript script l 2 Baseline less-than-or-equal-to double-vertical-bar x minus x Subscript upper T Baseline double-vertical-bar Subscript script l 2 Baseline plus double-vertical-bar x Subscript upper T Baseline minus x Superscript asterisk Baseline double-vertical-bar Subscript script l 2 Baseline less-than-or-equal-to sigma Subscript k Baseline left-parenthesis x right-parenthesis Subscript script l 2 Baseline plus double-vertical-bar x Subscript upper T Baseline minus x Superscript asterisk Baseline double-vertical-bar Subscript script l 2 Baseline period EndLayout

We bound the second term by

StartLayout 1st Row 1st Column double-vertical-bar x Subscript upper T Baseline minus x Superscript asterisk Baseline double-vertical-bar Subscript script l Sub Subscript upper T Sub Superscript upper N 2nd Column less-than-or-equal-to left-parenthesis 1 minus delta right-parenthesis Superscript negative 1 Baseline double-vertical-bar normal upper Phi left-parenthesis x Subscript upper T Baseline minus x Superscript asterisk Baseline right-parenthesis double-vertical-bar Subscript script l 2 Baseline 2nd Row 1st Column Blank 2nd Column less-than-or-equal-to left-parenthesis 1 minus delta right-parenthesis Superscript negative 1 Baseline left-parenthesis double-vertical-bar normal upper Phi left-parenthesis x minus x Subscript upper T Baseline right-parenthesis double-vertical-bar Subscript script l 2 Baseline plus double-vertical-bar normal upper Phi left-parenthesis x minus x Superscript asterisk Baseline right-parenthesis double-vertical-bar Subscript script l 2 Baseline right-parenthesis 3rd Row 1st Column Blank 2nd Column equals left-parenthesis 1 minus delta right-parenthesis Superscript negative 1 Baseline left-parenthesis double-vertical-bar y minus normal upper Phi x Subscript upper T Baseline double-vertical-bar Subscript script l 2 Baseline plus double-vertical-bar y minus normal upper Phi x Superscript asterisk Baseline double-vertical-bar Subscript script l 2 Baseline right-parenthesis 4th Row 1st Column Blank 2nd Column less-than-or-equal-to 2 left-parenthesis 1 minus delta right-parenthesis Superscript negative 1 Baseline double-vertical-bar y minus normal upper Phi x Subscript upper T Baseline double-vertical-bar Subscript script l 2 Baseline equals 2 left-parenthesis 1 minus delta right-parenthesis Superscript negative 1 Baseline double-vertical-bar normal upper Phi left-parenthesis x minus x Subscript upper T Baseline right-parenthesis double-vertical-bar Subscript script l 2 Baseline 5th Row 1st Column Blank 2nd Column less-than-or-equal-to 2 upper C left-parenthesis 1 minus delta right-parenthesis Superscript negative 1 Baseline double-vertical-bar x minus x Subscript upper T Baseline double-vertical-bar Subscript script l 2 Baseline equals 2 upper C left-parenthesis 1 minus delta right-parenthesis Superscript negative 1 Baseline sigma Subscript k Baseline left-parenthesis x right-parenthesis Subscript script l 2 Baseline comma EndLayout

where the first inequality uses the RIP and the fact that x Subscript upper T Baseline minus x Superscript asterisk is a vector with support of size less than 2 k , the third inequality uses the minimality of upper T Superscript asterisk and the fourth inequality uses the boundedness property in probability for x minus x Subscript upper T .

By virtue of the remarks on the properties of Gaussian and Bernoulli matrices, we derive the following quantitative result.

Corollary 6.4

If normal upper Phi is a random matrix of either Gaussian or Bernoulli type, then for any epsilon greater-than 0 and upper C 0 greater-than 3 , there exists a constant c 0 such that if n greater-than-or-equal-to c 0 k log left-parenthesis upper N slash n right-parenthesis , the following holds: for every x element-of double-struck upper R Superscript upper N , there exists a set normal upper Omega left-parenthesis x right-parenthesis subset-of normal upper Omega with upper P left-parenthesis normal upper Omega left-parenthesis x right-parenthesis right-parenthesis greater-than-or-equal-to 1 minus 2 epsilon such that (Equation6.1) holds for all omega element-of normal upper Omega left-parenthesis x right-parenthesis and normal upper Phi equals normal upper Phi left-parenthesis omega right-parenthesis .

Remark 6.5

Our analysis yields a constant of the form upper C 0 equals 3 plus eta , where eta can be made arbitraritly small at the expense of raising n , and it is not clear to us how to improve this constant down to 1 plus eta as in Reference7Reference10Reference11Reference12.

A variant of the above results deals with the situation where the vector x itself is drawn from a probability measure upper Q on double-struck upper R Superscript upper N . In this case, the following result shows that we can first pick the matrix normal upper Phi so that (Equation6.1) will hold with high probability on the choice of x . In other words, only a few pathological signals are not reconstructed up to the accuracy of best k -term approximation.

Corollary 6.6

If normal upper Phi a random matrix of either Gaussian or Bernoulli type, then for any epsilon greater-than 0 and upper C 0 greater-than 3 , there exists a constant c 0 such that if n greater-than-or-equal-to c 0 k log left-parenthesis upper N slash n right-parenthesis , the following holds: there exists a matrix normal upper Phi and a set normal upper Omega left-parenthesis normal upper Phi right-parenthesis subset-of normal upper Omega with upper Q left-parenthesis normal upper Omega left-parenthesis normal upper Phi right-parenthesis right-parenthesis greater-than-or-equal-to 1 minus 2 epsilon