## A Survey on Compressive Sensing: Classical Results and Recent Advancements

Ahmad Mousavi , Mehdi Rezaee ∗ † and Ramin Ayanzadeh †

## Abstract

Recovering sparse signals from linear measurements has demonstrated outstanding utility in a vast variety of real-world applications. Compressive sensing is the topic that studies the associated raised questions for the possibility of a successful recovery. This topic is well-nourished and numerous results are available in the literature. However, their dispersity makes it challenging and time-consuming for readers and practitioners to quickly grasp its main ideas and classical algorithms, and further touch upon the recent advancements in this surging field. Besides, the sparsity notion has already demonstrated its effectiveness in many contemporary fields. Thus, these results are useful and inspiring for further investigation of related questions in these emerging fields from new perspectives. In this survey, we gather and overview vital classical tools and algorithms in compressive sensing and describe significant recent advancements. We conclude this survey by a numerical comparison of the performance of described approaches on an interesting application.

Keywords. compressive sensing, glyph[lscript] p recovery, greedy algorithms

## 1 Introduction

In traditional sensing, i.e., uniform sampling, we need to densify measurements to obtain a higherresolution representation of physical systems. But in applications like multiband signals with wide spectral ranges, the required sampling rate may exceed the specifications of the best available analog-to-digital converters (ADCs) [102]. On the other hand, measurements obtained from linear sampling methods approximately carry a close amount of information, which makes them reasonably robust; for example, for packages lost in data streaming applications [97]. Compressive sensing linearly samples sparse signals at a rate lower than the traditional rate provided by the Nyquist-Shannon sampling theorem [141].

Recovering a sparse signal from a linear measurement is of high interest to preserve more storage, to have less computation, energy, and communication time, and to propose effective data compression and transmission methods [7, 13, 15, 21, 31, 54, 61, 73, 102, 103, 109, 130, 150, 154]. There are also specialised motivations behind this interest; for example, the recovery process in compressive sensing requires prior knowledge about original signals, which adds reasonable levels of security and privacy to the compressive sensing based data acquisition framework [144]. Compressive sensing-based face recognition techniques are invariant to rotation, re-scaling and data translation [102]. Besides, compressive sensing has demonstrated outstanding numerical stability in terms of not only noisy measurements but also quantization errors [106]. In machine learning, compressive sensing has demonstrated to boost the performance of pattern recognition methods.

∗ Institute for Mathematics and its Applications, University of Minnesota, Minneapolis, MN, USA

† Department of Computer Science and Electrical Engineering, University of Maryland Baltimore County, Baltimore, MD 21250, USA

Emails: amousavi@umn.edu, and { rezaee1, ayanzadeh } @umbc.edu.

The sparsity assumption as the basis of compressive sensing is not practically restrictive because it is empirically observed that desired signals in an extensive range of applications are sparse, possibly after a change of basis though. However, blind compressive sensing techniques are universal in terms of transfer domains, namely, there is no need to know the sparsifying basis while taking linear measurements [65]. Sparsity notion directly leads to NP-hard problems and thus the original problem of compressive sensing is computationally intractable; see Section 2 for the definition of this problem. Two main strategies to tackle this obstacle are convex or nonconvex relaxations and greedy algorithms; see Sections 3 and 4. There are several other effective approaches that have different ideas than these two categories. Hence, this survey attempts to briefly characterize these promising studies as well.

To relax an glyph[lscript] 0 -quasi-norm based sparse optimization problem, glyph[lscript] 0 -quasi-norm is often replaced by glyph[lscript] p -(quasi)-norm with p &gt; 0. Then, it is investigated that under which conditions on problem parameters and for which p 's both original and approximate problems uniquely obtain the same solution. The efficiency of p = 1 is well-documented [27, 28, 33, 41, 50, 51, 60]. But since this choice does not lead into strictly convex programs, the solution uniqueness shortcoming needs to be addressed [85, 143]. This case converts to a linear program and since those matrices involved in sparse optimization often inherit large dimensions, well-known methods including simplex and interior-point methods or specified algorithms are applied [25, 107]. The shape of unit balls associated with 0 &lt; p &lt; 1 encourages examining this case as well. It turns out that the recovery results for certain values of 0 &lt; p &lt; 1 are more robust and stable compared to p = 1 [38, 39]. Despite these favorable theoretical results, nonconvex relaxations ask for a global minimizer, which is an intractable task. One numerical way to bypass this is by utilizing classical schemes that obtain a local minimizer with an initial point sufficiently close to a global minimizer. For example, the solution of least squared is an empirical suggestion for this initialization [38], although there is no guarantee that such a solution is close enough. Nonetheless, a recent theoretical study proves that the main representative problems utilized in the realm of sparse optimization, such as the generalized basis pursuit and LASSO, almost always return a full-support solution for p &gt; 1 [113].

Greedy algorithms in our second class have low computational complexity, especially for relatively small sparsity levels, and yet they are effective. A well-received algorithm in this class which plays a key role is the orthogonal matching pursuit (OMP). To directly solve the original problem of compressive sensing, it exploits the best local direction in each step and adds its corresponding index to the current support set. Then, it estimates the new iteration as the orthogonal projection of the measurement vector onto the subspace generated by columns in the current support set [123, 124]. There is an extensive literature on the capability of this algorithm in identifying the exact support set that vary based on the required number of steps and accounting for noise in the measurement vector. For example, a sufficient condition for recovering an s sparse vector from an exact linear measurement asks for an ( s +1)st restricted isometry constant strictly smaller than ( √ s +1) -1 [82]. This upper bound improves to the necessary and sufficient bound of 1 / √ s +1. A result with the same spirit for the noisy measurement is available that imposes an extra assumption on the magnitude of the smallest nonzero entry of a desired sparse vector [135]. Further, stability is also achievable with the presence of noisy measurements if the number of required steps is increased [145]. Nevertheless, there are other algorithms in this class that have the same spirit but attempt to resolve issues of the OMP, such as stagewise OMP [49] and multipath matching pursuit [74]. For example, many algorithms allow more indices to enter the current support set for picking a correct index in each step such as the compressive sampling matching pursuit [89] and subspace pursuit [42]. Other effective greedy algorithms extending the OMP are simultaneous, generalized, and grouped OMP [117, 125, 128, 133]. Nonnegative and more general constrained versions of the OMP obtain similar recovery results based on variations of the restricted isometry and the orthogonality constants [23, 76, 114]. These algorithms are also generalized for block sparse signals [53, 131].

The rest of paper is organized as follows. In Section 2, we first introduce the original problem of compressive sensing and its extensions and variations. Section 3 is devoted to glyph[lscript] p recovery which covers using convex and nonconvex relaxations. In Section 4, we study several well-received greedy algorithms. Finally, we report numerical performance results in Section 5.

Notation . For a natural number N , we let [ N ] := { 1 2 , , . . . , N } . For a set S ⊆ [ N ], its number of elements and complement are denoted by card( S ) (or | S | ) and S c , respectively.

For a vector x ∈ R N and p &gt; 0, let ‖ x ‖ p := ( ∑ i ∈ [ N ] | x i | p ) 1 /p . For S = { i 1 , i 2 . . . , i | S | } ⊆ [ N ], we let x S := z ∈ R N such that z i = x i for i ∈ S and z i = 0 whenever i ∈ S c , that is, x S denotes the coordinate projection of x onto the subspace generated by { e i 1 , e i 2 , . . . , e i | S | } . Given x ∈ R N , the hard thresholding operator of order s is defined as H x s ( ) := x S where S contains s largest absolute entries of x (notation L s ( x ) denotes this index set). Further, let x + := max( x, 0). A vector is called s -sparse if it has at most s nonzero entries, i.e., its sparsity level is bounded by s . We use 〈 ., . 〉 to denote the standard inner product between two vectors. We employ 1 N to denote a vector of size N with each entry equal to 1, and simply let 0 denote a zero vector, which its dimension should be clear based on the discussed content. For a matrix A ∈ R m N × , we denote its transpose by A T , its adjacent by A ∗ and its Frobenius norm by ‖ A ‖ F . We denote the j th column of A by A j and, given a subset S ⊆ [ N ], a corresponding column submatrix is defined as A S := [ A ,A j 1 j 2 , . . . , A j | S | ]. The null and range spaces of this matrix are denoted by K er A ( ) and R ( A ), respectively. The symbol O stands for the standard big O notation.

## 2 Compressive Sensing Problem and Its Extensions and Variations

Compressive sensing (CS), also known as compressed sensing or sparse sampling, is established based on sparsity assumption. Hence, we start with preliminary definitions of sparsity and, a closely related concept, compressibility.

glyph[negationslash]

Definition 2.1. For a vector x ∈ R N , let supp( x ) := { i ∈ [ N ] | x i = 0 } and ‖ x ‖ 0 := card(supp( x )) . In particular, for s ∈ [ N ] , this vector is called s -sparse if ‖ x ‖ 0 ≤ s .

Definition 2.2. For a vector x ∈ R N , s ∈ [ N ] , and p &gt; 0 , let

$$\sigma _ { s } ( x ) _ { p } \coloneqq \min _ { z \in \mathbb { R } ^ { N } } \| x - z \| _ { p } \text{ subject to } \| z \| _ { 0 } \leq s.$$

This vector is called s -compressible if σ s ( x ) p is small for some p &gt; 0 . This vector is sometimes called nearly s -sparse in glyph[lscript] p -norm.

It is easy to show that σ s ( x ) p = ‖ x -x S ‖ p , where S ⊆ [ N ] contains all the s largest absolute entries of x (consequently, σ s ( x ) p = 0 when x is s -sparse). Roughly speaking, a vector is called sparse if most of its entries are zero and it is called compressible if it is well-approximated by a sparse vector. Sparsity as a prior assumption for a desired vector is consistent with diverse applications because it is often doable to employ a change of basis technique for finding sparse representations in a transform domain. For instance, wavelet, Radon, discrete cosine, and Fourier transforms are well-known as suitable and efficient choices for natural, medical, and digital images, and speech signals, respectively.

The original problem of compressive sensing aims to recover a sparse signal x from a linear measurement vector y = Ax , where A ∈ R m N × (with m glyph[lessmuch] N ) is the so called measurement, coding or design matrix. So, the ultimate goal of compressive sensing is reasonably formulated as follows:

$$\min _ { x \in \mathbb { R } ^ { N } } \, \| x \| _ { 0 } \text{ subject to } \ A x = y.$$

To incorporate noisy measurements, one can study this problem:

$$\min _ { x \in \mathbb { R } ^ { N } } \, \| x \| _ { 0 } \text{ subject to } \, \| A x - y \| _ { 2 } \leq \eta,$$

where η &gt; 0 controls the noise level. These problems have demonstrated to revolutionize several real-world applications in both science and engineering disciplines, including but not limited to signal processing, imaging, video processing, remote sensing, communication systems, electronics, machine learning, data fusion, manifold processing, natural language and speech processing, and processing biological signals [78, 98, 100, 104, 151].

In a broad range of real-world applications, we utilize ADCs to map the real-valued measurements of physical phenomena (over a potentially infinite range) to discrete values (over a finite range). As an illustration, when we use b bits for representing the measurements digitally, the quantization module in an ADC maps measurements to one of the 2 b distinct values that introduces error in measurements. Quantization module plays a bottleneck role in restricting the sampling rate of the ADCs because the maximum sampling rate decreases exponentially when the number of bits per measurement increases linearly. Quantization module also is the main source of energy consumption in ADCs. Single-bit (or 1bit) compressive sensing enables us to reduce the number of bits per measurements to one and introduces a proper model for successful recovery of the original signal. This extreme quantization approach only retains the sign of measurements, i.e., we have y i ∈ { 1 , - } 1 for all i ∈ [ m ], which results in a significantly efficient, simple, and fast quantization [22, 70].

A recent generalization of (CS) is the so called compressive sensing with matrix uncertainty. This uncertainty finds two formulations that incorporate measurement errors as well. The first formulation is the following:

$$\min _ { x \in \mathbb { R } ^ { N }, \ E \in \mathbb { R } ^ { m \times N } } \, \| ( A + E ) x - y \| _ { 2 } ^ { 2 } + \lambda _ { E } \| E \| _ { F } ^ { 2 } + \lambda \| x \| _ { 0 },$$

where the matrix E is the perturbation matrix. The second one is the following:

$$\min _ { x \in \mathbb { R } ^ { N }, \ d \in \mathbb { R } ^ { r } } \, \left \| ( A ^ { ( 0 ) } + \sum _ { i \in [ r ] } d _ { i } A ^ { ( i ) } ) x - y \right \| _ { 2 } ^ { 2 } + \lambda _ { d } \| d \| _ { 2 } ^ { 2 } + \lambda \| x \| _ { 0 },$$

where the measurement matrices A ( ) i 's for i = 0 1 , , . . . , r are known and the unknown vector d is the uncertainty vector. In quantized compressed sensing, we have either y = Q Ax or y = Q ( Ax + ) where v v is the noise such that v ∼ N (0 , σ 2 I ) and Q : R m →A⊆ R m is the set-valued quantization function. Wellstudied examples of such function, map Ax or Ax + v into A = { x ∈ R m | l ≤ x ≤ u } or A = { +1 , - } 1 m [70, 137, 156]. The former case leads to:

$$\min _ { x \in \mathbb { R } ^ { N } } \| x \| _ { 0 } \text{ subject to } l \leq A x + v \leq u,$$

and the latter one yields the following problem:

$$\min _ { x \in \mathbb { R } ^ { N } } \, \| x \| _ { 0 } \, \text{ subject to } \, y = \text{sign} ( A x + v ).$$

In some recent applications, we may have nonlinear measurements that encourage the so called cardinality constrained optimization:

$$\min _ { x \in \mathbb { R } ^ { N } } f ( x ) \ \text{subject to} \ \| x \| _ { 0 } \leq s.$$

Two important examples are f ( x ) = ‖ Ax -y ‖ 2 (motivated by linear measurements y = Ax ) and f ( x ) = ∑ m i ( y i -x T A ( ) i x ) 2 (proposed for quadratic measurements of y i = x T A ( ) i x for i = 1 2 , , . . . , m and

symmetric matrices A ( ) i 's) [112, 118]. Many algorithms have been proposed for solving this cardinality constrained problem with specific and general smooth functions [17, 18, 19, 24, 111]. In matrix setting, this problem converts to rank minimization, which finds numerous applications [55]. Although we listed some vital variations of compressive sensing above, our focus in this survey is on the original problem to motivate the important tools, algorithms and results in compressive sensing for a linear measurement possibly contaminated with some error or noise.

## 3 glyph[lscript] p Recovery with 0 &lt; p ≤ 1 : Main Formulations and Results

Since the problem (CS) is NP-hard [86], it is not tractable and it must be handled indirectly. Because glyph[lscript] p -norm approximates glyph[lscript] 0 -norm as p goes to zero, one approach to tackle (CS) is exploiting the so called Basis Pursuit (BS) problem:

$$\min _ { x \in \mathbb { R } ^ { N } } \| x \| _ { 1 } \text{ subject to } \ A x = y.$$

Then, one investigates under which conditions (CS) and (BP) appoint the same solution. This equivalence property occurs when the solution is highly sparse and the measurement matrix has sufficiently small mutual incoherence (defined below) [50].

Definition 3.1. For a matrix A ∈ R m N × , the mutual coherence is defined as glyph[negationslash]

$$\mu ( A ) \coloneqq \max _ { i \neq j } \frac { | \langle A _ { i }, A _ { j } \rangle | } { \| A _ { i } \| _ { 2 }. \| A _ { j } \| _ { 2 } },$$

where A i denotes the i th column vector of the matrix A .

The mutual coherence simply seeks the largest correlation between two different columns. The following global 2-coherence is a generalization of the mutual coherence ( µ = ν 1 ):

Definition 3.2. For a matrix A ∈ R m N × , its k th global 2-coherence is defined as below:

$$\nu _ { k } ( A ) \coloneqq \max _ { i \in [ N ] \ \Lambda \subseteq [ N ] \langle i \}, | \Lambda | \leq k } \left ( \sum _ { j \in \Lambda } \frac { \langle A _ { i }, A _ { j } \rangle ^ { 2 } } { \| A _ { i } \| _ { 2 } ^ { 2 }. \| A _ { j } \| _ { 2 } ^ { 2 } } \right ) ^ { 1 / 2 }.$$

This tool is useful for a successful recovery of a weak version of orthogonal matching pursuit [140], while we focus on the standard mutual coherence here to convey the main idea.

Theorem 3.1. [52] Assume that ‖ x ‖ 0 &lt; 0 5(1 + . µ A ( ) -1 ) . Then, problems CS and BP uniquely obtain the signal x .

Sparsity is an inevitable assumption in the recovery process. This assumption accompanied by other conditions on a measurement matrix such as the mutual coherence or restricted isometry property (RIP) guarantee a successful recovery through the problem BP. For example, the bound in Theorem 3.1 is improved using the RIP tool defined below.

Definition 3.3. Let A be an m × N matrix. Then, this matrix has the restricted isometry property of order s provided that there exists δ s ∈ (0 1) , such that

$$( 1 - \delta _ { s } ) \| x \| _ { 2 } ^ { 2 } \ \leq \ \| A x \| _ { 2 } ^ { 2 } \ \leq \ ( 1 + \delta _ { s } ) \| x \| _ { 2 } ^ { 2 } \quad \ \forall x ; \ \| x \| _ { 0 } \leq s.$$

This definition demands each column submatrix A S with card( S ) ≤ s to have singular values in [1 -δ , s 1 + δ s ] . Consequently, such submatrices have linearly independent columns if δ s &lt; 1. Since this definition involves all the s -tuples of columns, it is more rigorous than the mutual coherence ( δ 2 = µ ). Thus, the RIP tool derives to better upper bounds on the sparsity level of a vector to be recovered, that is, less sparse vectors are properly handled.

Theorem 3.2. [81] Problems CS and BP uniquely obtain the same s -sparse solution if δ 2 s &lt; . 0 4931 .

There are numerous similar results for recovering s -sparse signals in compressive sensing literature based on the RIP constants, which are often in the form of δ ks ≤ δ for some numbers k &gt; 0 and δ ∈ (0 , 1). For example, the BP recovers all the s -sparse signals if δ s &lt; 1 3 and this bound is sharp / [29]. Since the condition δ ks ≤ δ is not practically verifiable due to its computational complexity [121], a breakthrough in the compressive sensing field took place when random matrices, such as Gaussian and Bernoulli, demonstrated their capability to satisfy such appealing inequalities with a high probability. In fact, for an m × N random matrix, where each entry is independently drawn from Gaussian or Bernoulli distributions, we have δ s ≤ δ for m ≥ Cδ -2 s ln( eN s ) in which C &gt; 0 does not depend on s, m and N , and e is the natural number [14]. It must be mentioned that most results for constructing deterministic matrices with the RIP property depend on the mutual coherence, leading to m ≥ cs 2 with c &gt; 0. This bound is not practical because the number of measurements m scales quadratically in sparsity level s for deterministic matrices versus linearly for random matrices. This confirms the desire of using random matrices in compressive sensing. On the other hand, there are recent promising results toward the practicality of deterministic matrices in terms of not only the compression ratio of m/N but also the complexity of the recovery process [3, 30, 66, 91]. For example, deterministic sparse coding matrices have demonstrated to outperform both binary tree recovery and binary glyph[lscript] 1 -norm recovery methods in the so called binary compressive sensing [88]. The majority of analyses within compressive sensing relies on the RIP but this tool has minor drawbacks that are partially rectified via the NSP defined below.

Definition 3.4. Let A be an m × N matrix. This matrix has the null space property of order s if

$$\| v _ { S } \| _ { 1 } < \| v _ { S ^ { c } } \| _ { 1 } ; \ \forall v \in \mathcal { K } e r ( A ) \, \sum \{ 0 \} \text{ and } \forall S \subseteq [ N ] \text{ with } | S | \leq s.$$

In principle, the measurement pair ( A,y ) carries all the required information for the recovery process. Since linear systems Ax = y and PAx = Py have identical solution sets for a nonsingular matrix P , the measurement pair ( PA,Py ) has the same information but it is numerically a better choice for a suitable conditioning matrix P . Although the RIP constants of matrices A and PA can vastly differ [148], the NSP is preserved if either one holds it. In addition, this property is necessary and sufficient for the solution uniqueness of problem BP (in the uniform sense).

Theorem 3.3. [61] Every s -sparse vector x is the unique solution to BP with y = Ax if and only the measurement matrix A holds the NSP of order s .

The above theorem implies that under the NSP of order s , the convex program BP as a matter of fact solves the NP-hard problem CS.

The Range Space Property (RSP) is another useful condition in compressive sensing given by Zhao [152].

Definition 3.5. The matrix A T has the range space property of order s if for any disjoint subsets S 1 and S 2 ⊆ [ N ] with | S 1 | + | S 2 | ≤ s there exists a vector η ∈ R ( A T ) such that

$$\eta _ { i } = 1 \ \forall i \in S _ { 1 } ; \ \eta _ { i } = - 1 \ \forall i \in S _ { 2 } \ \ a n d \ \| \eta _ { ( S _ { 1 } \cup S _ { 2 } ) ^ { c } } \| _ { \infty } < 1.$$

Theorem 3.4. [152] Every s -sparse vector x is exactly recovered by the problem BP with y = Ax if and only if A T has the RSP of order s.

The matrix A T has the range space property of order s under several assumptions such as s &lt; 0 5(1 + . µ A ( ) -1 ) , δ 2 s ( A &lt; ) √ 2 -1 and the NSP of order 2 s [152]. Further, an extended version of this property is useful to provide a similar result to the above theorem for the nonnegative sparse recovery.

So far, we have only discussed noiseless measurements in this section, although a practical situation definitely imposes investigating noisy scenario as well. Taking into account noisy measurements yields in the following Quadratically Constrained Basis Pursuit (QCBP) problem (after replacing glyph[lscript] 0 by glyph[lscript] 1 ):

$$\min _ { x \in \mathbb { R } ^ { N } } \| x \| _ { 1 } \ \text{subject to} \ \| A x - y \| _ { 2 } \leq \eta.$$

Theorem 3.5. [61] Given x ∈ R N and a matrix A ∈ R m N × such that δ 2 s &lt; 4 / √ 41 ≈ 0 6246 . , every minimizer x ∗ of QCBP satisfies ‖ x ∗ -x ‖ 2 ≤ Cs -1 2 / σ s ( x ) 1 + Dη with C &gt; 0 and D &gt; 0 .

The following so called Least Absolute Shrinkage and Selection Operator (LASSO) is practically more efficient [57, 126, 136]:

$$\min _ { x \in \mathbb { R } ^ { N } } \quad \frac { 1 } { 2 } \| y - A x \| _ { 2 } ^ { 2 } + \lambda \| x \| _ { 1 }.$$

There is a trade-off between feasibility and sparsity in the nature of this problem, which is controlled by the regularization parameter λ . Not only the LASSO has been extensively studied [119], but also there are various results for it in terms of its effectiveness in sparse optimization. For instance, we bring the following theorem for deterministic measurement matrices.

Theorem 3.6. [126] Let y = Ax + e where x is supported on S ⊆ [ N ] with | S | ≤ s and e is a zero-mean additive observation noise. Assume that the measurement matrix A satisfies ‖ A T S c A S ( A A T S S ) -1 ‖ ∞ &lt; 1 , λ min ( A A T S S ) &gt; m and max j ∈ S C ‖ A j ‖ 2 ≤ √ m . Further, assume that N = O (exp( m γ )) , s = O ( m α ) , min i ∈ S x i &gt; /m 1 1 -β 2 with 0 &lt; α + γ &lt; β &lt; 1 . For λ = m 1 -δ 2 such that δ ∈ ( γ, β -α ) , the LASSO problem recovers the sparsity pattern S with probability 1 -exp( -cm δ ) for a constant c &gt; 0 .

For the case of random measurement matrices, this problem needs a sample size m &gt; 2 s ln( N -s ) to achieve exact recovery with a high probability. This probability converges to one for larger problems [126]. An efficient algorithm for solving the BP utilizes a sequence of the LASSO problems [142]. The following so called Basis Pursuit Denoising (BPD) minimizes the feasibility violation while implicitly bounding the sparsity level with a parameter τ ≥ 0 :

$$\min _ { x \in \mathbb { R } ^ { N } } \ \| y - A x \| _ { 2 } \ \text{ subject to} \quad \| x \| _ { 1 } \leq \tau.$$

There are known relations among the optimums of the QCBP, LASSO, and BPD problems, which can be found in [61]. The Dantzig Selector (DS) problem arises in several statistical applications, so it has been also employed in sparse recovery [28, 34]:

$$\min _ { x \in \mathbb { R } ^ { N } } \ \| x \| _ { 1 } \ \text{subject to } \ \| A ^ { T } ( A x - y ) \| _ { \infty } \leq \sigma.$$

This problem manages noisy measurements and reduces to a linear programming problem. To bring a pertaining result next, we need the following restricted orthogonality quantity.

Definition 3.6. Given a matrix A ∈ R m N × , its s, s ′ -restricted orthogonality (RO) constant θ s,s ′ is defined as the smallest θ &gt; 0 such that

$$| \langle A x, A x ^ { \prime } \rangle | \leq \theta \| x \| _ { 2 } \| x ^ { \prime } \| _ { 2 } \ \forall x \text{ and } x ^ { \prime } ; \ \| x \| _ { 0 } \leq s \text{ and } \| x ^ { \prime } \| _ { 0 } \leq s ^ { \prime }.$$

According to [28], for x ∈ R N , and a noisy y such that ‖ A T ( Ax -y ) ‖ ∞ ≤ σ and δ 1 5 . s + θ s, 1 5 . s &lt; 1, an optimal solution x ∗ to DS obeys ‖ x ∗ - ‖ x 2 ≤ Cs σ 1 2 + Ds -1 2 σ s ( x ) 1 , where C and D are two constants depending on δ 1 5 . s and θ s, 1 5 . s . In particular, if x is an s -sparse vector, then ‖ x ∗ -x ‖ 2 ≤ Cs σ. 1 2 A very recent result related to the recovery of this problem as reported in Corollary 5.6.1 of [154] is brought below.

Theorem 3.7. [154] Let A ∈ R m N × with m &lt; N and rank ( A ) = m. Consider the DS problem. If A T satisfies the RSP of order k , then for any x ∈ R n , there is a solution x ∗ of the DS approximating x with error

$$\| x - x ^ { * } \| _ { 2 } \leq \gamma \{ 2 \sigma _ { k } ( x ) _ { 1 } + \left ( \| A ^ { T } ( A x - y ) \| _ { \infty } - \sigma \right ) _ { + } + c _ { A } \sigma + c _ { A } \| A ^ { T } ( A x - y ) \| _ { \infty } \},$$

where γ is a constant and c A is a constant given as

$$c _ { A } = \max _ { G \subseteq \{ 1, \dots, n \}, | G | = m } \| A _ { G } ^ { - 1 } ( A A ^ { T } ) ^ { - 1 } A \| _ { \infty \to 1 },$$

where A G stands for all positive m × m invertible submatrix of A . In particular, for any x satisfying ‖ A T ( Ax -y ) ‖ ∞ ≤ σ , there is a solution x ∗ of the DS approximating x with error

$$\| x - x ^ { * } \| _ { 2 } \leq \gamma \{ 2 \sigma _ { k } ( x ) _ { 1 } + c _ { A } \sigma + c _ { A } \| A ^ { T } ( A x - y ) \| _ { \infty } \} \leq 2 \gamma \{ \sigma _ { k } ( x ) _ { 1 } + c _ { A } \sigma \}.$$

However the choice of p = 1 is the most interesting case, as glyph[lscript] 1 -norm is the closest convex norm to glyph[lscript] 0 -quasi-norm [101] and convex optimization is extremely well-nourished, the shape of a unit ball associated with glyph[lscript] p -norm for 0 &lt; p &lt; 1 motivates researchers to explore the following nonconvex problem:

$$\min _ { x \in \mathbb { R } ^ { N } } \, \| x \| _ { p } ^ { p } \, \text{ subject to } \ A x = y.$$

For certain values of p where 0 &lt; p &lt; 1, the above scheme leads to more robust and stable theoretical guarantees compared to the case of p = 1 [39, 105, 132]. In other words, much less restrictive recoverability conditions are achievable for certain p 's with 0 &lt; p &lt; 1 compared to glyph[lscript] 1 -norm recovery [155]. For instance, the following result implies that a sufficient condition for recovering an s -sparse vector in the noiseless case via glyph[lscript] 0 5 . minimization is δ 3 s +27 δ 4 s &lt; 26, where an analogous result for glyph[lscript] 1 -norm recovery requires δ 2 s +2 δ 3 s &lt; 1. We bring the following related theorem, which discusses compressible vectors. Since it is practically stringent to impose sparsity, it is desired to study compressible vectors.

Theorem 3.8. [105] Assume that A ∈ R m N × satisfies

$$\delta _ { k s } ( A ) + k ^ { \frac { 2 } { p } - 1 } \delta _ { ( k + 1 ) s } ( A ) < k ^ { \frac { 2 } { p } - 1 } - 1,$$

for k &gt; 1 such that ks is a natural number. Given x ∈ R N , let y = Ax + e with ‖ e ‖ 2 ≤ glyph[epsilon1] . Then, an optimal solution x ∗ of

$$\begin{array} { c c c } \gamma \\ \min _ { x \in \mathbb { R } ^ { N } } \| x \| _ { p } ^ { p } & \ s u b j e c t \ t o & \| A x - y \| _ { 2 } \leq \epsilon, \end{array}$$

obeys

$$\| x ^ { * } - x \| _ { 2 } ^ { p } \leq C \epsilon ^ { p } + D s ^ { \frac { p } { 2 } - 1 } [ \sigma _ { s } ( x ) _ { p } ] ^ { p },$$

where

$$C = 2 ^ { p } \left [ \frac { 1 + k ^ { p / 2 - 1 } ( 2 / p - 1 ) ^ { - p / 2 } } { ( 1 - \delta _ { ( k + 1 ) s } ) ^ { \frac { p } { 2 } } - ( 1 + \delta _ { k s } ) ^ { p / 2 } k ^ { p / 2 - 1 } } \right ], \ D = \frac { 2 ( \frac { p } { 2 - p } ) ^ { p / 2 } } { k ^ { 1 - p / 2 } } \left [ 1 + \frac { ( 1 + k ^ { p / 2 - 1 } ) ( 1 + \delta _ { k s } ) ^ { p / 2 } } { ( 1 - \delta _ { ( k + 1 ) s } ) ^ { p / 2 } - ( 1 + \delta _ { k s } ) ^ { p / 2 } k ^ { p / 2 - 1 } } \right ].$$

In particular, if x is an s -sparse vector, then ‖ x ∗ -x ‖ p 2 ≤ Cglyph[epsilon1] p .

The main issue with this result is its demand for a global minimizer of a nonconvex function for which there is no known theoretical guarantee. One way to bypass this is by utilizing classical schemes that obtain a local minimizer with an initial point that is sufficiently close to a global minimizer. For example, the solution of least-squares is experimentally suggested for this initialization [38], while there is no guarantee that such solution is in general close enough to a global minimizer. Since solving an unconstrained problem is simpler, another approach for taking advantage of nonconvex glyph[lscript] p -minimization (1) with 0 &lt; p &lt; 1 is tackling the following glyph[lscript] p -regularized least squares problem:

$$\min _ { x \in \mathbb { R } ^ { N } } \, \frac { 1 } { 2 } \| A x - y \| _ { 2 } ^ { 2 } + \lambda \| x \| _ { p } ^ { p },$$

where λ &gt; 0 is the penalty parameter. Because problems (1) and (2) are equivalent in limit, this parameter must be selected meticulously to obtain an approximate solution for the original problem. Once λ &gt; 0 is fixed, algorithms such as iteratively-reweighted least squares explained in [110] are beneficial. Furthermore, the choice of p plays a key role in the efficiency of this approach; for example, the best choices in image deconvolution are p = 1 2 and / p = 2 3. The case of / p = 1 2 is a critical choice because / it provides sparser solutions among p ∈ [1 / , 2 1) and any p ∈ (0 , 1 2) does not show significantly better / performance [138]. As a result, it is essential to have a specialized algorithm for this choice [139].

Despite p &gt; 1 leads to strictly convex programming, it is theoretically shown that in this case not only the solution is not sparse, but also each entry is almost always nonzero. The same result holds for all the primary problems mentioned above.

Theorem 3.9. [113] Let p &gt; 1 , N ≥ m,λ &gt; 0 , and τ &gt; 0 . For almost all ( A,y ) ∈ R m N × , a unique optimal solution x ∗ ( A,y ) to the any of the problems BP, QCBP, LASSO and BPD, when ‖ ‖ . 1 is replaced by ‖ ‖ . p p , satisfies | supp( x ∗ ( A,y ) ) | = N .

Recent applications in image processing, statistics and data science lead to another class of sparse optimization problems subject to the nonnegative constraint, i.e.,

$$\min _ { x \in \mathbb { R } ^ { N } } \ \| x \| _ { 0 } \ \text{ subject to } \ A x = y, \ \ x \geq 0.$$

This problem is similar to CS but their optimums differ in general. Similar convex/nonconvex relaxation approaches are advantageous to tackle NCS problem. Its convex relaxation leads to the so called Nonnegative Basis Pursuit (NBP) [51, 72, 153]:

$$\min _ { x \in \mathbb { R } ^ { N } } \, \| x \| _ { 1 } \ \text{ subject to } \ A x = y, \ \ x \geq 0.$$

Theorem 3.10. [153] Any x ≥ 0 such that ‖ x ‖ 0 ≤ s is recovered by NBP with y = Ax if and only if for any index subset S ⊆ [ N ] such that | S | ≤ s there exists η ∈ R ( A T ) such that η i = 1 for i ∈ S and ‖ η S c ‖ ∞ &lt; 1 .

For a theoretical study on the following nonnegative version of LASSO formulation, see [69]:

$$\min _ { x \in \mathbb { R } ^ { N } } \quad \frac { 1 } { 2 } \| y - A x \| _ { 2 } ^ { 2 } + \lambda \| x \| _ { 1 } \quad \text{subject to} \quad x \geq 0. \quad \text{(NLASSO)}$$

Nonnegativity is an example of possible available prior information in the recovery process, which enables us to employ sparse measurement matrices for the recovery of remarkably larger signals [72]. In applications like infrared absorption spectroscopy, the non-zero elements of the original sparse signal are

bounded. Imposing this boundary condition reduces the optimal set, and therefore its convex relaxation leads to a bounded/boxed basis pursuit that obtains better recovery properties [47, 48, 77].

Majority of studies in compressive sensing focuses on continues signals where x ∈ R N , even though there are several real-world applications that include discrete signals [77]. Examples are discrete control signal design, black-and-white or gray-scale sparse image reconstruction, machine-type multi-user communications, and blind estimation in digital communications. Here, we aim to reconstruct a discrete signal whose elements take their values from a finite set of alphabet. It is worth highlighting that when x is discrete, even the glyph[lscript] 1 -norm recovery method leads to an NP-hard problem [75]. Nevertheless, the study [75] reveals this additional prior knowledge about the original signal enhances the performance of both glyph[lscript] 0 and glyph[lscript] 1 norm recovery methods via imposing new constraints. For example, the sum of absolute values is designed to recover discrete sparse signals whose non-zero elements are generated from a finite set of alphabets with a known probability distribution. In binary compressive sensing, we can represent this model as follows:

$$\min _ { x \in \mathbb { R } ^ { N } } \ \ ( 1 - p ) \| x \| _ { 1 } + p \| x - \mathbf 1 _ { N } \| _ { 1 } \ \text{ subject to} \ \ A x = y,$$

where p is the probability of each component being one; analogous to the sparsity rate [71, 77, 87]. In this approach, when p goes to zero ( x is sparse), the problem (3) behaves like the BP. The sum of norms represents the problem of binary compressive sensing as follows:

$$\min _ { x \in \mathbb { R } ^ { N } } \quad \| x \| _ { 1 } + \lambda \, \| x - \frac { 1 } { 2 } \, \mathbf 1 _ { N } \| _ { \infty } \ \text{ subject to } \ A x = y,$$

where the parameter λ &gt; 0 keeps glyph[lscript] 1 and glyph[lscript] ∞ balanced [129]. It is observed that the glyph[lscript] ∞ -norm minimization tends to capture a representation whose coefficients have roughly the same absolute value [63, 116]. Hence, the objective function ‖ x ‖ 1 + λ ‖ x -1 2 1 N ‖ ∞ is two fold. First, the sparsity is imposed via the glyph[lscript] 1 -norm term. Second, for those remaining coefficients that are deviated from 0, the binary property is explored through the glyph[lscript] ∞ term. By the observation that solution of the glyph[lscript] ∞ -norm minimization favors to achieve a solution with the components of the same magnitude, the glyph[lscript] ∞ term encourages those (deviated from 0) nonzero coefficients to be centered at 1 (because | x i -1 2 | obtains the same value for x i = 0 or 1). Nonetheless, the smoothed glyph[lscript] 0 gradient descent technique has demonstrated to outperform such approaches in terms of recovery rate and time [77].

Finally, we emphasize on two important points. First, that most results in sparse recovery are based on asymptotic properties of random matrices but sometimes an application specifies a deterministic measurement matrix. Thus, it is vital to have tractable schemes for testing properties like the NSP, RIP, and etc. in potential situations; see, e.g., [44, 120]. In fact, the nature of this requirement, encourages RIPless conditions [32, 149]. Second, all the introduced convex minimization problems can be solved by general purpose interior-point methods, however specified algorithms designed for these problems exist as well; see, e.g., [25, 37, 108, 146].

## 4 Greedy Algorithms: Main Variations and Results

Greedy algorithms are iterative approaches that take local optimal decisions in each step to eventually obtain a global solution. Hence, their success is due to some conditions on problem parameters. Greedy algorithms are mostly simple and fast, which find numerous applications in various contemporary fields, including biology, applied mathematics, engineering, and operations research. This supports the emerging interest in their performance analysis.

Greedy algorithms are efficient in tackling those problems in compressive sensing as well. Finding an s -sparse solution for an underdetermined linear system casts as the following sparsity constrained

problem:

$$\min _ { x \in \mathbb { R } ^ { N } } \, \| A x - y \| _ { 2 } ^ { 2 } \, \text{ subject to} \, \ \| x \| _ { 0 } \leq s.$$

The most popular greedy algorithm to solve this problem is the Orthogonal Matching Pursuit (OMP). To tackle the problem SC, starting from zero as the initial iteration, the following OMP algorithm picks an appropriate index in each step to add its current support set and it estimates the new iteration as the orthogonal projection of the measurement vector onto the subspace generated by corresponding columns of the current support set [124, 127].

## Orthogonal Matching Pursuit

There is an extensive literature on the capability of the OMP in identifying the exact support set either in at most s steps or at arbitrary many steps [123, 124, 26].

Theorem 4.1. [82, 135] Assume that A ∈ R m N × satisfies the RIP of order s +1 such that δ s +1 ≤ 1 √ s +1 . Then, the OMP recovers any s -sparse vector x ∈ R N using y = Ax in at most s iterations.

Further, it is proved that, when s ≥ 2, for any δ such that 1 / √ s +1 ≤ δ &lt; 1, any matrix with δ s +1 = δ fails to recover all the s -sparse vectors [43, 80]. It is still an open question that in terms of the OMP performance what happens if δ s +1 ∈ ( 1 √ s +1 , 1 √ s +1 ). A result with the same spirit of Theorem 4.1 for noisy measurements requires an extra assumption on the magnitude of the smallest nonzero entry of the desired vector [134]. Here, we bring the next theorem that assumes δ s +2 δ 31 s ≤ 1. This inequality holds under the condition δ 31 s ≤ 1 / 3, which implies the number of required measurements to successfully recover any s -sparse signal via the OMP is O ( s ln N ), that is, the number of measurements m must be in the worst case linear in sparsity level s .

Theorem 4.2. [145] Assume that A ∈ R m N × satisfies δ s +2 δ 31 s ≤ 1 . Then, given an s -sparse vector x ∈ R N , the OMP obeys

$$\left \| x ^ { ( 3 0 s ) } - x \right \| _ { 2 } \leq \frac { 2 \sqrt { 6 } ( 1 + \delta _ { 3 1 s } ) ^ { \frac { 1 } { 2 } } } { 1 - \delta _ { 3 1 s } } \| A x - y \| _ { 2 }.$$

There are also results for the success of this algorithm in case of availability of partial information on the optimal support set [64, 67]. This partial information is of the form of either a subset of the optimal support or an approximate subset with possibly wrong indices.

In many practical situations, there is no prior information available about the sparsity of a desired signal but generalized versions of the OMP are still enabled to recover it under a more stringent condition [46].

glyph[negationslash]

The OMP is also beneficial in recovering block sparse signals [53, 68, 131]. To elaborate on this block version of the OMP, assume that x = [ x [1] T , x [2] T , . . . , x [ L ] T T ] with x i [ ] = [ x d i ( -1)+1 , x d i ( -1)+2 , . . . , x di ] T , 1 ≤ i ≤ L (we assume the number of nonzero elements in different blocks are equal only for the sake of simplicity of exposition). Then, x is called a block s -sparse signal if there are at most s blocks (indices) i such that x i [ ] = 0 ∈ R d [53]. The support of this block sparse vector is defined as Ω := { i | x i [ ] = 0 . } This definition reduces to the standard sparsity definition for d = 1. We also partition the measurement matrix A as A = [ A [1] , A [2] , . . . , A [ L ] ] , where A i [ ] = [ A d i ( -1)+1 , A d i ( -1)+2 , . . . , A di ] , 1 ≤ i ≤ L . Then,

## Block Orthogonal Matching Pursuit

| Input:     | A ∈ R m × Ld , y ∈ R m , and initialize with x 0 = 0 ∈ R Ld , and S 0 = ∅ .                                                                                                                                          |
|------------|----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| Iteration: | repeat until convergence: S n +1 = S n ∪ { j n +1 } such that j n +1 = arg max j ∈ [ L ] ∥ ∥ A [ j ] T ( y - A [ S n ] x [ S n ]) ∥ ∥ 2 , x [ S n +1 ] = arg min x ∈ R | S n +1 | d ∥ ∥ A [ S n +1 ] x - y ∥ ∥ 2 2 . |

for a set of indices S = { i 1 , i 2 , . . . , i | S | } , we have x S [ ] := [ x i [ 1 ] T , x i [ 2 ] T , . . . , x [ i | S | ] T T ] , and A S [ ] := [ A i [ 1 ] , A i [ 2 ] , . . . , A [ i | S | ] ] . The block orthogonal matching pursuit (BOMP) is as follows. To present the exact recovery result of this algorithm, we need two other tools.

Definition 4.1. [53] Consider a block measurement matrix A introduced above. The block mutual coherence of A is defined as

$$\mu _ { B } ( A ) \coloneqq \max _ { 1 \leq l \neq r \leq L } \ \frac { 1 } { d } \| A [ l ] ^ { T } A [ r ] \| _ { 2 },$$

and its block subcoherence is defined as

$$\nu _ { B } ( A ) \coloneqq \max _ { 1 \leq l \leq L } \, \max _ { 1 \leq i \neq j \leq d } \, \frac { 1 } { d } \left | A _ { i } [ l ] ^ { T } A _ { j } [ l ] \right |,$$

where A l i [ ] and A l j [ ] are the i th and j th columns of the block A l [ ] .

Theorem 4.3. [131] Let x be a block sparse vector supported on Ω and y = Ax + e where ‖ e ‖ 2 ≤ η and the measurement matrix satisfies (2 s -1) dµ B ( A ) + ( d -1) ν B ( A &lt; ) 1 . Further, suppose that

$$\min _ { i \in \Omega } \left \| x [ i ] \right \| _ { 2 } \geq \frac { \eta \sqrt { 2 ( 1 + ( 2 d - 1 ) \nu _ { B } ( A ) ) } } { 1 - ( 2 | \Omega | - 1 ) d \mu _ { B } ( A ) - ( d - 1 ) \nu _ { B } ( A ) }.$$

Then, the BOMP algorithm recovers block sparse vector x in | Ω | iterations.

A similar result for the capability of another extended version of the OMP in recovering joint block sparse matrices is found in [62, 115]. Despite many interesting features of the OMP, its index selection is problematic. Precisely, if a wrong index is chosen, the OMP fails to expel this index so that the exact support cannot be found in this situation. The Compressive Sampling Matching Pursuit (CoSaPM) is an algorithm to resolve this drawback [89]. To find an s -sparse feasible vector for an underdetermined linear system, this algorithm allows 2 s best potential indices enter the current support set. Then, the following CoSaMP keeps s entries that play the key role in the pertaining projection in the sense that their corresponding entries have most magnitude.

## Compressive Sampling Matching Pursuit

In the noiseless measurement case, the following theorem sates that any s -sparse signal, is recovered as the limit point of a sequence generated by the CoSaMP.

Theorem 4.4. [61] Assume that A ∈ R m N × satisfies δ 8 s &lt; 0 4782 . . Then, for any x ∈ R N and e ∈ R m , the sequence x n generated by CoSaMP using y = Ax + e , where s is replaced by 2 s , obeys

$$\| x - x _ { n } \| _ { 2 } \leq C s ^ { - 1 / 2 } \sigma _ { s } ( x ) _ { 1 } + D \| e \| _ { 2 } + 2 \rho ^ { n } \| x \| _ { 2 },$$

where constants C, D and ρ ∈ (0 1) , only depend on δ 8 s . In particular, if ˜ x denotes a cluster point of this sequence, then

$$\| x - \tilde { x } \| _ { 2 } \leq C s ^ { - 1 / 2 } \sigma _ { s } ( x ) _ { 1 } + D \| e \| _ { 2 }.$$

The following generalized orthogonal matching pursuit (gOMP) allows a given number of indices t ≥ 1 enter a current support set. Consequently, a faster exact recovery under the RI constants involved conditions is attained [128, 133]. A recent algorithm combines the BOMP and the gOMP to propose a

## Generalized Orthogonal Matching Pursuit

block generalized orthogonal matching pursuit for recovering block sparse vectors with possibly different number of nonzero elements in each block [99]. A closely related task to the problem SC is the following nonnegative sparsity constrained (NSC) problem

$$\min _ { x \in \mathbb { R } ^ { N } } \, \| A x - y \| _ { 2 } ^ { 2 } \, \text{ subject to} \, \ \| x \| _ { 0 } \leq s \text{ and} \quad x \geq 0.$$

Then, its solution may completely differ from the one to SC. Bruckstein et al. [23] presented an adapted version of the OMP for finding nonnegative sparse vectors of an underdetermined system, namely, the Nonnegative Orthogonal Matching Pursuit (NOMP) below. They demonstrated its capability to find sufficiently sparse vectors. In practice, it is probable not to have sparsity level in hand, this challenge is also doable [90].

## Nonnegative Orthogonal Matching Pursuit

There is an emerging interest to explore novel greedy algorithms to find a sparsest feasible point of a set [12, 19]. This casts as a minimization problem under sparsity constrained possibly intersecting a desired set. Nevertheless, the main idea of a greedy algorithm here is to start with a feasible sparse point (possibly zero) and add one or several candidate indices to the current support set. Once the support set is updated, a new iteration is obtained via a projection step. The Constrained Matching Pursuit (CMP) [114] investigates the following constrained sparse problem:

$$\min _ { x \in \mathbb { R } ^ { N } } \| x \| _ { 0 } \text{ subject to } \ A x = y \text{ \ and \ } x \in \mathcal { P },$$

where P ⊆ R N is a closed constraint set containing the origin. One can see that the OMP and NOMP can be employed for solving the above problem with the constraint set P with R N and R N + , respectively.

## Constrained Matching Pursuit

The performance of the CMP relies on the measurement matrix A as well as the involved constraint set P . In fact, there exists a set P for which there is no measurement matrix A such that the CMP is successful [114]. Hence, a class of convex coordinate-projection (CP) admissible sets is of interest. A nonempty set P ⊆ R N is called CP admissible if for any x ∈ P and any index set J ⊆ supp( x ), we have x J ∈ P . The conic hull structure of the CP sets can be used to extend the RIP and the RO constants over these sets. A verifiable exact recovery condition is then developed based on such constants for the closed convex CP admissible cones [114]. (Consequently, a verifiable condition for the NOMP is in hand because the nonnegative orthant is a closed convex CP admissible cone). These verifiable conditions are often NP-hard to check, like almost all the introduced tools in this survey such as the NSP, and RIP. But random measurement matrices with the right size hold these verifiable conditions with a high probability. This fact confirms the significance of random measurements in sparse optimization [122].

There are many other effective algorithms in sparse optimization that are applicable for the compressive sensing setting as well. For example, threshholding based algorithms use the adjacent matrix A ∗ for approximating inversion action and exploit the hard thresholding operator to solve the square system A Ax ∗ = A y ∗ via a fixed-point method [20, 36, 45, 56, 59]. Iterative reweighted algorithms often outperform algorithms presented in Section 3. The iterative reweighted glyph[lscript] p -algorithm is as follows:

$$x _ { n + 1 } \in \underset { x \in \mathbb { R } ^ { N } } { \arg \min } \, \| W _ { n } x \| _ { p } \ \text{ subject to } \ \| A x - y \| _ { 2 } \leq \epsilon,$$

where W n is a diagonal weight matrix defined based on the current iteration x n . For example, W k = diag( w , w 1 n 2 n , . . . , w N n ) where w j n = 1 ( / | x j n | + γ ) t with t and γ &gt; 0, which encourages small elements to approach zero quickly [1, 35, 40]. The so called smoothed glyph[lscript] 0 -norm takes advantage of smooth approximations of the glyph[lscript] 0 quasi-norm to tackle the CS and NCS [83, 84].

In traditional compressive sensing approaches, we recover sparse signals from m = O ( s log N/s ) linear measurements. Model-based compressive sensing enables us to substantially reduce the number of measurements to m = O ( s ) without loosing the robustness of the recovery process [16]. In fact, model based compressive sensing includes the structural dependencies between the values and locations of the signal coefficients. For example, modeling the problem of binary compressive sensing with a bi-partite graph and representing the recovery process as an edge recovery scheme recovers binary signals more accurately, compared to binary glyph[lscript] 1 -norm and tree-based binary compressive sensing methods [88].

On the other hand, quantum annealers are type of adiabatic quantum computers that tackle computationally intensive problems, which are intractable in the realm of classical computing. From a problem solving point of view, quantum annealers receive coefficients of an Ising Hamiltonian as input and return a solution that minimizes the given energy function in a fraction of a second [6, 9, 92]. Recent studies have revealed that well-posed binary compressive sensing and binary compressive sensing with matrix uncertainty problems are tractable in the realm of quantum computing [5, 8, 10, 11].

## 5 Numerical Performance Analysis

In this section, we numerically examine the performance of the most prevalent sparse recovery methods introduced in this survey in recovering unigram text representation from their linear embedding (measurement). To describe the sparse recovery task of interest, we start by an introductory explanation on document (text) unigram representations and embeddings. Suppose that a vocabulary V is available, namely, a set of all the considered words in a context. Then, a unigram representation of a document is simply a vector in R |V| , where its i th entry counts the occurrences of the i th word of V in that document [93, 95]. Unigram representations are highly sparse as the size of a vocabulary is often too large. These representations are expensive to store and further may not be able to effectively capture the semantic relations among the words of a vocabulary, so text embeddings are naturally favorable.

We start by defining word embeddings and discuss text embeddings afterward. The goal in word embedding is to encode each word of a vocabulary into a vector representation in a much lower dimensional space m glyph[lessmuch] |V| such that the semantic relations among words are preserved. Word embeddings have lately gained much attentions in broad applications of the natural language processing such as classification, question answering and part of speech tagging. There are different linear and nonlinear effective approaches for word embedding, for example, pretrained models Global Vectors For Word Representation (GloVe) [96], word2vec [79] and Rademacher embeddings. The GloVe is a neural (network) based word embedding, where the word2vec is mainly based on matrix decomposition. Assuming that word embeddings are available for all the words of a vocabulary, a text embedding is simply a linear combination of them with the coefficients coming from its unigram representation. In other words, we have Ax unigram T = y embedding T , where A ∈ R m ×|V| is an embedding (or measurement matrix) generated from a specific methodology, x unigram T ∈ R |V| is the unigram representation of a text, and y embedding T ∈ R m is its (unigram) embedding. The measurement matrices in our experiments are generated via GloVe embedding method and the Radamacher distribution with the following probability mass function:

$$f ( k ) = \begin{cases} 1 / 2 & \text{if $k=-1$,} \\ 1 / 2 & \text{if $k=+1$.} \end{cases}$$

These matrices are: m × 17000 for MR movie reviews [94] and m × 20000 for SUBJ subjectivity dataset [93], respectively. Embedding sizes for our experiments are m = 50 100 200 300 and 1600. , , ,

Figure 1: SUBJ Dataset recovery

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.01014v3-figure-b23623ce-4593-4ea3-88a0-7f131632d9bd.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.01014v3-figure-6e3de7dd-89ad-4c0e-b9d4-394010fdf8a0.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.01014v3-figure-ac1d8b92-0388-4e6c-bc20-f74658d4fff6.jpg)

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.01014v3-figure-cd9b886a-7d5b-4768-94e3-98d61e16cb6f.jpg)

These figures confirm the efficiency of glyph[lscript] 1 recovery and greedy algorithms in recovering unigram representations of 50 documents, where success is achieved if the relative error is smaller than 10 -7 . We avoid a detailed explanation on the implemented algorithms for this specific application rather finish this survey with a more general conclusion as follows. The glyph[lscript] p recovery with 0 &lt; p ≤ 1, where p &lt; 1 promises better theoretical results than p = 1, and greedy algorithms are both effective in recovering sparse vectors in various applications if the measurement matrix inherits several properties explained in

Figure 2: MR Dataset recovery

![image](https://ac.marcodsn.me/arxiv-markdown-images/1908.01014v3-figure-f483b020-5a47-4991-930c-98efc6e72968.jpg)

this survey. In the constrained case, the constraint set also plays a crucial role in the sparse recovery conditions as well [114]. Nevertheless, these properties often provide sufficient conditions and for some applications specified measurement matrices can work properly as well and even better than random matrices [4]. Further, except when the sparsity level is relatively small, the glyph[lscript] p recovery with 0 &lt; p ≤ 1 is superior to the greedy approach. For a more comprehensive study on the computational complexities and efficiency of these algorithms or related studies, see, e.g., [2, 58, 98, 147].

## Acknowledgement

The authors would like to greatly thank Professors Jinglai Shen and Maziar Salahi for their meticulous comments and constructive suggestions on this work.

## References

- [1] Mohammad Javad Abdi. Cardinality Optimization Problems . University of Birmingham, 2013.
- [2] Lasith Adhikari. Nonconvex sparse recovery methods . PhD thesis, Uinversity of California, Merced, 2017.
- [3] Arash Amini and Farokh Marvasti. Deterministic construction of binary, bipolar, and ternary compressed sensing matrices. IEEE Transactions on Information Theory , 57(4):2360-2370, 2011.
- [4] Sanjeev Arora, Mikhail Khodak, Nikunj Saunshi, and Kiran Vodrahalli. A compressed sensing view of unsupervised text embeddings, bag-of-n-grams, and lstms. 2018.
- [5] Ramin Ayanzadeh et al. Leveraging artificial intelligence to advance problem-solving with quantum annealers. 2020.
- [6] Ramin Ayanzadeh, Milton Halem, John Dorband, and Tim Finin. Quantum-assisted greedy algorithms. arXiv preprint arXiv:1912.02362 , 2019.
- [7] Ramin Ayanzadeh, Milton Halem, and Tim Finin. Compressive geospatial analytics. AGUFM , 2019:IN53B-0733, 2019.
- [8] Ramin Ayanzadeh, Milton Halem, and Tim Finin. Sat-based compressive sensing. arXiv preprint arXiv:1903.03650 , 2019.
- [9] Ramin Ayanzadeh, Milton Halem, and Tim Finin. Reinforcement quantum annealing: A hybrid quantum learning automata. Scientific reports , 10(1):1-11, 2020.

| [10]   | Ramin Ayanzadeh, Milton Halem, Tim Finin, et al. An ensemble approach for compressive sensing with quantum annealers. In IEEE International Geoscience and Remote Sensing Symposium , 2020.                                                        |
|--------|----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [11]   | Ramin Ayanzadeh, Seyedahmad Mousavi, Milton Halem, and Tim Finin. Quantum annealing based binary compressive sensing with matrix uncertainty. arXiv preprint arXiv:1901.00088 , 2019.                                                              |
| [12]   | Sohail Bahmani, Bhiksha Raj, and Petros T Boufounos. Greedy sparsity-constrained optimization. Journal of Machine Learning Research , 14(Mar):807-841, 2013.                                                                                       |
| [13]   | Lanshu Bai, Huiyi Lu, and Yike Liu. High-efficiency observations: compressive sensing and recovery of seismic waveform data. Pure and Applied Geophysics , 177(1):469-485, 2020.                                                                   |
| [14]   | Richard Baraniuk, Mark Davenport, Ronald DeVore, and Michael Wakin. A simple proof of the restricted isometry property for random matrices. Constructive Approximation , 28(3):253-263, 2008.                                                      |
| [15]   | Richard G Baraniuk. Compressive sensing. IEEE signal processing magazine , 24(4), 2007.                                                                                                                                                            |
| [16]   | Richard G Baraniuk, Volkan Cevher, Marco F Duarte, and Chinmay Hegde. Model-based com- pressive sensing. arXiv preprint arXiv:0808.3572 , 2008.                                                                                                    |
| [17]   | Amir Beck and Yonina C Eldar. Sparse signal recovery from nonlinear measurements. In 2013 IEEE International Conference on Acoustics, Speech and Signal Processing , pages 5464-5468. IEEE, 2013.                                                  |
| [18]   | Amir Beck and Yonina C Eldar. Sparsity constrained nonlinear optimization: Optimality conditions and algorithms. SIAM Journal on Optimization , 23(3):1480-1509, 2013.                                                                             |
| [19]   | Amir Beck and Nadav Hallak. On the minimization over sparse symmetric sets: Projections, optimality conditions, and algorithms. Mathematics of Operations Research , 41(1):196-223, 2016.                                                          |
| [20]   | Thomas Blumensath and Mike E Davies. Iterative hard thresholding for compressed sensing. Ap- plied and computational harmonic analysis , 27(3):265-274, 2009.                                                                                      |
| [21]   | Holger Boche, Robert Calderbank, Gitta Kutyniok, and Jan Vyb´ral. ı Compressed sensing and its applications . Springer, 2015.                                                                                                                      |
| [22]   | Petros T Boufounos and Richard G Baraniuk. 1-bit compressive sensing. In 2008 42nd Annual Conference on Information Sciences and Systems , pages 16-21. IEEE, 2008.                                                                                |
| [23]   | Alfred M Bruckstein, Michael Elad, and Michael Zibulevsky. On the uniqueness of nonnegative sparse solutions to underdetermined systems of equations. IEEE Transactions on Information Theory , 54(11):4813-4820, 2008.                            |
| [24]   | Oleg P Burdakov, Christian Kanzow, and Alexandra Schwartz. Mathematical programs with cardi- nality constraints: reformulation by complementarity-type conditions and a regularization method. SIAM Journal on Optimization , 26(1):397-425, 2016. |
| [25]   | Martin Burger, Michael M¨ller, o Martin Benning, and Stanley Osher. An adaptive inverse scale space method for compressed sensing. Mathematics of Computation , 82(281):269-299, 2013.                                                             |
| [26]   | Tianwen Tony Cai and Lie Wang. Orthogonal matching pursuit for sparse signal recovery with noise. Institute of Electrical and Electronics Engineers, 2011.                                                                                         |

| [27]   | Tianwen Tony Cai, Lie Wang, and Guangwu Xu. Shifting inequality and recovery of sparse signals. IEEE Transactions on Signal Processing , 58(3):1300-1308, 2009.                                                                                                       |
|--------|-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [28]   | Tianwen Tony Cai, Guangwu Xu, and Jun Zhang. On recovery of sparse signals via glyph[lscript] 1 minimization. IEEE Transactions on Information Theory , 55(7):3388-3397, 2009.                                                                                        |
| [29]   | Tianwen Tony Cai and Anru Zhang. Sharp rip bound for sparse signal and low-rank matrix recovery. Applied and Computational Harmonic Analysis , 35(1):74-93, 2013.                                                                                                     |
| [30]   | Emmanuel Candes and Justin Romberg. Sparsity and incoherence in compressive sampling. Inverse problems , 23(3):969, 2007.                                                                                                                                             |
| [31]   | Emmanuel J Candes et al. Compressive sampling. In Proceedings of the international congress of mathematicians , volume 3, pages 1433-1452. Madrid, Spain, 2006.                                                                                                       |
| [32]   | Emmanuel J Candes and Yaniv Plan. A probabilistic and ripless theory of compressed sensing. IEEE transactions on information theory , 57(11):7235-7254, 2011.                                                                                                         |
| [33]   | Emmanuel J Candes and Terence Tao. Decoding by linear programming. arXiv preprint math/0502327 , 2005.                                                                                                                                                                |
| [34]   | Emmanuel J Candes and Terence Tao. The dantzig selector: Statistical estimation when p is much larger than n. Ann. Statist. , 35(6):2313-2351, 12 2007.                                                                                                               |
| [35]   | Emmanuel J Candes, Michael B Wakin, and Stephen P Boyd. Enhancing sparsity by reweighted glyph[lscript] 1 minimization. Journal of Fourier Analysis and Applications , 14(5):877-905, Dec 2008.                                                                       |
| [36]   | Rafael E Carrillo, Luisa F Polania, and Kenneth E Barner. Iterative hard thresholding for com- pressed sensing with partially known support. In 2011 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) , pages 4028-4031. IEEE, 2011. |
| [37]   | Antonin Chambolle and Thomas Pock. A first-order primal-dual algorithm for convex problems with applications to imaging. Journal of mathematical imaging and vision , 40(1):120-145, 2011.                                                                            |
| [38]   | Rick Chartrand. Exact reconstruction of sparse signals via nonconvex minimization. IEEE Signal Processing Letters , 14(10):707-710, 2007.                                                                                                                             |
| [39]   | Rick Chartrand. Fast algorithms for nonconvex compressive sensing: Mri reconstruction from very few data. In 2009 IEEE International Symposium on Biomedical Imaging: From Nano to Macro , pages 262-265. IEEE, 2009.                                                 |
| [40]   | Rick Chartrand and Wotao Yin. Iteratively reweighted algorithms for compressive sensing. In 2008 IEEE International Conference on Acoustics, Speech and Signal Processing , pages 3869-3872. IEEE, 2008.                                                              |
| [41]   | Scott Shaobing Chen, David L Donoho, and Michael A Saunders. Atomic decomposition by basis pursuit. SIAM review , 43(1):129-159, 2001.                                                                                                                                |
| [42]   | Wei Dai and Olgica Milenkovic. Subspace pursuit for compressive sensing signal reconstruction. IEEE transactions on Information Theory , 55(5):2230-2249, 2009.                                                                                                       |
| [43]   | Wei Dan. A sharp rip condition for orthogonal matching pursuit. In Abstract and Applied Analysis ,                                                                                                                                                                    |

| [44]   | Alexandre d'Aspremont and Laurent El Ghaoui. Testing the nullspace property using semidefinite programming. Mathematical programming , 127(1):123-144, 2011.                                                                                                                                        |
|--------|-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [45]   | Ingrid Daubechies, Michel Defrise, and Christine De Mol. An iterative thresholding algorithm for linear inverse problems with a sparsity constraint. Communications on Pure and Applied Math- ematics: A Journal Issued by the Courant Institute of Mathematical Sciences , 57(11):1413-1457, 2004. |
| [46]   | Thong TDo, Lu Gan, NamNguyen, and Trac DTran. Sparsity adaptive matching pursuit algorithm for practical compressed sensing. In 2008 42nd Asilomar Conference on Signals, Systems and Computers , pages 581-587. IEEE, 2008.                                                                        |
| [47]   | David L Donoho and Jared Tanner. Counting the faces of randomly-projected hypercubes and orthants, with applications. Discrete & computational geometry , 43(3):522-541, 2010.                                                                                                                      |
| [48]   | David L Donoho and Jared Tanner. Precise undersampling theorems. Proceedings of the IEEE , 98(6):913-924, 2010.                                                                                                                                                                                     |
| [49]   | David Leigh Donoho, Iddo Drori, Yaakov Tsaig, and Jean-Luc Starck. Sparse solution of underde- termined systems of linear equations by stagewise orthogonal matching pursuit. IEEE Transactions on Information Theory , 58(2):1094-1121, 2012.                                                      |
| [50]   | David Leigh Donoho and Michael Elad. Optimally sparse representation in general (nonorthogonal) dictionaries via glyph[lscript] 1 minimization. Proceedings of the National Academy of Sciences , 100(5):2197- 2202, 2003.                                                                          |
| [51]   | David Leigh Donoho and Jared Tanner. Sparse nonnegative solution of underdetermined linear equations by linear programming. Proceedings of the National Academy of Sciences , 102(27):9446- 9451, 2005.                                                                                             |
| [52]   | Michael Elad and Alfred M Bruckstein. A generalized uncertainty principle and sparse representa- tion in pairs of bases. IEEE Transactions on Information Theory , 48(9):2558-2567, Sep. 2002.                                                                                                      |
| [53]   | Yonina C Eldar, Patrick Kuppinger, and Helmut Bolcskei. Block-sparse signals: Uncertainty rela- tions and efficient recovery. IEEE Transactions on Signal Processing , 58(6):3042-3054, 2010.                                                                                                       |
| [54]   | Yonina C Eldar and Gitta Kutyniok. Compressed sensing: theory and applications . Cambridge University Press, 2012.                                                                                                                                                                                  |
| [55]   | Maryam Fazel, Haitham Hindi, Stephen P Boyd, et al. A rank minimization heuristic with applica- tion to minimum order system approximation. In Proceedings of the American control conference , volume 6, pages 4734-4739. Citeseer, 2001.                                                          |
| [56]   | M´rio a AT Figueiredo and Robert D Nowak. An em algorithm for wavelet-based image restoration. IEEE Transactions on Image Processing , 12(8):906-916, 2003.                                                                                                                                         |
| [57]   | M´rio a AT Figueiredo, Robert D Nowak, and Stephen J Wright. Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems. IEEE Journal of selected topics in signal processing , 1(4):586-597, 2007.                                                |
| [58]   | Massimo Fornasier. Numerical methods for sparse recovery. Theoretical foundations and numerical methods for sparse recovery , 14:93-200, 2010.                                                                                                                                                      |

| [59]   | Massimo Fornasier and Holger Rauhut. Iterative thresholding algorithms. Applied and Computa- tional Harmonic Analysis , 25(2):187-208, 2008.                                                                                       |
|--------|------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [60]   | Simon Foucart. A note on guaranteed sparse recovery via l1-minimization. Applied and Computa- tional Harmonic Analysis , 29(1):97-103, 2010.                                                                                       |
| [61]   | Simon Foucart and Holger Rauhut. A Mathematical Introduction to Compressive Sensing . Springer, 2013.                                                                                                                              |
| [62]   | Yuli Fu, Haifeng Li, Qiheng Zhang, and Jian Zou. Block-sparse recovery via redundant block omp. Signal Processing , 97:162-171, 2014.                                                                                              |
| [63]   | Jean-Jacques Fuchs. Spread representations. In 2011 Conference Record of the Forty Fifth Asilomar Conference on Signals, Systems and Computers (ASILOMAR) , pages 814-817. IEEE, 2011.                                             |
| [64]   | Huanmin Ge and Wengu Chen. An optimal recovery condition for sparse signals with partial support information via omp. Circuits, Systems, and Signal Processing , pages 1-26, 2019.                                                 |
| [65]   | Sivan Gleichman and Yonina C Eldar. Blind compressed sensing. IEEE Transactions on Informa- tion Theory , 57(10):6958-6975, 2011.                                                                                                  |
| [66]   | Zhi Gu, Zhengchun Zhou, Yang Yang, Avik Ranjan Adhikary, and Xiaolun Cai. Deterministic compressed sensing matrices from sequences with optimal correlation. IEEE Access , 7:16704-16710, 2019.                                    |
| [67]   | C´dric e Herzet, Charles Soussen, J´rˆme e o Idier, and R´mi e Gribonval. Exact recovery conditions for sparse representations with partial support information. IEEE Transactions on Information Theory , 59(11):7509-7524, 2013. |
| [68]   | Jianwen Huang, Jianjun Wang, Wendong Wang, and Feng Zhang. Sharp sufficient condition of block signal recovery via glyph[lscript] 2 /glyph[lscript] 1 -minimisation. IET Signal Processing , 2019.                                 |
| [69]   | Yuki Itoh, Marco F Duarte, and Mario Parente. Perfect recovery conditions for non-negative sparse modeling. IEEE Transactions on Signal Processing , 65(1):69-80, 2016.                                                            |
| [70]   | Laurent Jacques, Jason N Laska, Petros T Boufounos, and Richard G Baraniuk. Robust 1-bit com- pressive sensing via binary stable embeddings of sparse vectors. IEEE Transactions on Information Theory , 59(4):2082-2102, 2013.    |
| [71]   | Sandra Keiper, Gitta Kutyniok, Dae Gwan Lee, and G¨tz o E Pfander. Compressed sensing for finite-valued signals. Linear Algebra and its Applications , 532:570-613, 2017.                                                          |
| [72]   | Mohammad Amin Khajehnejad, Alexandros G Dimakis, Weiyu Xu, and Babak Hassibi. Sparse recovery of nonnegative signals with minimal expansion. IEEE Transactions on Signal Processing 59(1):196-208, 2010.                           |
| [73]   | Gitta Kutyniok. Theory and applications of compressed sensing. GAMM-Mitteilungen , 36(1):79- 101, 2013.                                                                                                                            |
| [74]   | Suhyuk Kwon, Jian Wang, and Byonghyo Shim. Multipath matching pursuit. IEEE Transactions                                                                                                                                           |

| [75]   | Jan-Hendrik Lange, Marc E Pfetsch, Bianca M Seib, and Andreas M Tillmann. Sparse recovery with integrality constraints. arXiv preprint arXiv:1608.08678 , 2016.                                                                                           |
|--------|-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [76]   | Tsung-Han Lin and HT Kung. Stable and efficient representation learning with nonnegativity constraints. In International Conference on Machine Learning , pages 1323-1331, 2014.                                                                          |
| [77]   | Tianlin Liu and Dae Gwan Lee. Binary compressive sensing via smoothed glyph[lscript] 0 gradient descent. arXiv preprint arXiv:1801.09937 , 2018.                                                                                                          |
| [78]   | Elaine Crespo Marques, Nilson Maciel, Lirida Naviner, Hao Cai, and Jun Yang. A review of sparse recovery algorithms. IEEE Access , 7:1300-1322, 2018.                                                                                                     |
| [79]   | Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed representa- tions of words and phrases and their compositionality. In Advances in neural information processing systems , pages 3111-3119, 2013.                      |
| [80]   | Qun Mo. A sharp restricted isometry constant bound of orthogonal matching pursuit. arXiv preprint arXiv:1501.01708 , 2015.                                                                                                                                |
| [81]   | Qun Mo and Song Li. New bounds on the restricted isometry constant δ 2 k . Applied and Compu- tational Harmonic Analysis , 31(3):460-468, 2011.                                                                                                           |
| [82]   | Qun Mo and Yi Shen. Aremark on the restricted isometry property in orthogonal matching pursuit. IEEE Transactions on Information Theory , 58(6):3654-3656, 2012.                                                                                          |
| [83]   | Mohammad Reza Mohammadi, Emad Fatemizadeh, and Mohammad H Mahoor. Non-negative sparse decomposition based on constrained smoothed 0 norm. Signal Processing , 100:42-50, 2014.                                                                            |
| [84]   | Hosein Mohimani, Massoud Babaie-Zadeh, and Christian Jutten. A fast approach for overcom- plete sparse decomposition based on smoothed glyph[lscript] 0 norm. IEEE Transactions on Signal Processing 57(1):289-301, 2008.                                 |
| [85]   | Seyedahmad Mousavi and Jinglai Shen. Solution uniqueness of convex piecewise affine functions based optimization with applications to constrained glyph[lscript] 1 minimization. ESAIM: Control, Optimisa- tion and Calculus of Variations , 25:56, 2019. |
| [86]   | Shanmugavelayutham Muthukrishnan et al. Data streams: Algorithms and applications. Founda- tions and Trends R © in Theoretical Computer Science , 1(2):117-236, 2005.                                                                                     |
| [87]   | Masaaki Nagahara. Discrete signal reconstruction by sum of absolute values. IEEE Signal Process- ing Letters , 22(10):1575-1579, 2015.                                                                                                                    |
| [88]   | Ukash Nakarmi and Nazanin Rahnavard. Bcs: Compressive sensing for binary sparse signals. In MILCOM 2012-2012 IEEE Military Communications Conference , pages 1-5. IEEE, 2012.                                                                             |
| [89]   | Deanna Needell and Joel A Tropp. Cosamp: Iterative signal recovery from incomplete and inaccu- rate samples. Applied and computational harmonic analysis , 26(3):301-321, 2009.                                                                           |
| [90]   | Deanna Needell and Roman Vershynin. Signal recovery from incomplete and inaccurate measure- ments via regularized orthogonal matching pursuit. arXiv preprint arXiv:0712.1360 , 2007.                                                                     |
| [91]   | Thu LN Nguyen and Yoan Shin. Deterministic sensing matrices in compressive sensing: a survey.                                                                                                                                                             |

[91] Thu LN Nguyen and Yoan Shin. Deterministic sensing matrices in compressive sensing: a survey. The Scientific World Journal , 2013.

| [92]   | Hidetoshi Nishimori and Kabuki Takada. Exponential enhancement of the efficiency of quantum annealing by non-stoquastic hamiltonians. Frontiers in ICT , 4:2, 2017.                                                                                                                          |
|--------|----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [93]   | Bo Pang and Lillian Lee. A sentimental education: Sentiment analysis using subjectivity summa- rization based on minimum cuts. In Proceedings of the 42nd annual meeting on Association for Computational Linguistics , page 271. Association for Computational Linguistics, 2004.           |
| [94]   | Bo Pang and Lillian Lee. Seeing stars: Exploiting class relationships for sentiment categoriza- tion with respect to rating scales. In Proceedings of the 43rd annual meeting on association for computational linguistics , pages 115-124. Association for Computational Linguistics, 2005. |
| [95]   | Hristo S Paskov, Robert West, John C Mitchell, and Trevor Hastie. Compressive feature learning. In Advances in Neural Information Processing Systems , pages 2931-2939, 2013.                                                                                                                |
| [96]   | Jeffrey Pennington, Richard Socher, and Christopher Manning. Glove: Global vectors for word representation. In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP) , pages 1532-1543, 2014.                                                       |
| [97]   | Scott Pudlewski, Arvind Prasanna, and Tommaso Melodia. Compressed-sensing-enabled video streaming for wireless multimedia sensor networks. IEEE Transactions on Mobile Computing , (6):1060-1072, 2012.                                                                                      |
| [98]   | Saad Qaisar, Rana Muhammad Bilal, Wafa Iqbal, Muqaddas Naureen, and Sungyoung Lee. Com- pressive sensing: From theory to applications, a survey. Journal of Communications and networks , 15(5):443-456, 2013.                                                                               |
| [99]   | Rui Qi, Diwei Yang, Yujie Zhang, and Hongwei Li. On recovery of block sparse signals via block generalized orthogonal matching pursuit. Signal Processing , 153:34-46, 2018.                                                                                                                 |
| [100]  | Zhijin Qin, Jiancun Fan, Yuanwei Liu, Yue Gao, and Geoffrey Ye Li. Sparse representation for wireless communications: A compressive sensing approach. IEEE Signal Processing Magazine , 35(3):40-58, 2018.                                                                                   |
| [101]  | Carlos Ramirez, Vladik Kreinovich, and Miguel Argaez. Why glyph[lscript] 1 is a good approximation to glyph[lscript] 0 : A geometric explanation. Journal of Uncertain Systems , 7(3):203-207, 2013.                                                                                         |
| [102]  | Meenu Rani, SB Dhok, and RB Deshmukh. A systematic review of compressive sensing: Concepts, implementations and applications. IEEE Access , 6:4875-4894, 2018.                                                                                                                               |
| [103]  | Irina Rish and Genady Grabarnik. Sparse modeling: theory, algorithms, and applications . CRC press, 2014.                                                                                                                                                                                    |
| [104]  | Damien Rontani, Daeyoung Choi, Chien-Yuan Chang, Alexandre Locquet, and DS Citrin. Com- pressive sensing with optical chaos. Scientific reports , 6:35206, 2016.                                                                                                                             |
| [105]  | Rayan Saab, Rick Chartrand, and Ozgur Yilmaz. Stable sparse approximations via nonconvex optimization. In 2008 IEEE International Conference on Acoustics, Speech and Signal Processing , pages 3885-3888. IEEE, 2008.                                                                       |
| [106]  | Rayan Saab, Rongrong Wang, and ¨ Ozg¨r u Yılmaz. Quantization of compressive samples with stable and robust recovery. Applied and Computational Harmonic Analysis , 44(1):123-143, 2018.                                                                                                     |

| [107]   | Maziar Salahi, Jiming Peng, and Tam´s a Terlaky. On mehrotra-type predictor-corrector algorithms. SIAM Journal on Optimization , 18(4):1377-1397, 2007.                                                                                                                                           |
|---------|---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [108]   | Maziar Salahi, Jiming Peng, and Tam´s a Terlaky. On mehrotra-type predictor-corrector algorithms. SIAM Journal on Optimization , 18(4):1377-1397, 2007.                                                                                                                                           |
| [109]   | Aswin C Sankaranarayanan and Richard G Baraniuk. Compressive sensing. Computer Vision: A Reference Guide , pages 1-5, 2020.                                                                                                                                                                       |
| [110]   | John A Scales and Adam Gersztenkorn. Robust methods in inverse theory. Inverse problems 4(4):1071, 1988.                                                                                                                                                                                          |
| [111]   | Yoav Shechtman, Amir Beck, and Yonina C Eldar. Gespar: Efficient phase retrieval of sparse signals. IEEE transactions on signal processing , 62(4):928-938, 2014.                                                                                                                                 |
| [112]   | Yoav Shechtman, Yonina C Eldar, Alexander Szameit, and Mordechai Segev. Sparsity based sub- wavelength imaging with partially incoherent light via quadratic compressed sensing. Optics express 19(16):14807-14822, 2011.                                                                         |
| [113]   | Jinglai Shen and Seyedahmad Mousavi. Least sparsity of p-norm based optimization problems with p > 1. SIAM Journal on Optimization , 28(3):2721-2751, 2018.                                                                                                                                       |
| [114]   | Jinglai Shen and Seyedahmad Mousavi. Exact support and vector recovery of constrained sparse vectors via constrained matching pursuit. arXiv preprint arXiv:1903.07236 , 2019.                                                                                                                    |
| [115]   | Yanli Shi, Libo Wang, and Rong Luo. Sparse recovery with block multiple measurement vectors algorithm. IEEE Access , 7:9470-9475, 2019.                                                                                                                                                           |
| [116]   | Christoph Studer, Wotao Yin, and Richard G Baraniuk. Signal representations with minimum -norm. In 2012 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton) , pages 1270-1277. IEEE, 2012.                                                                        |
| [117]   | Grzegorz Swirszcz, Naoki Abe, and Aurelie C Lozano. Grouped orthogonal matching pursuit for variable selection and prediction. In Advances in Neural Information Processing Systems , pages 1150-1158, 2009.                                                                                      |
| [118]   | Alexander Szameit, Yoav Shechtman, Eliyahu Osherovich Osherovich, Elad Bullkich, Pavel Sidorenko, Hod Dana, S Steiner, Ernst-Bernhard Kley Kley, Snir Gazit, Tzipi Cohen-Hyams, et al. Sparsity-based single-shot subwavelength coherent diffractive imaging. Nature materials , 11(5):455, 2012. |
| [119]   | Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series B (Methodological) , 58(1):267-288, 1996.                                                                                                                                   |
| [120]   | Andreas M Tillmann. Computing the spark: Mixed-integer programming for the (vector) matroid girth problem, 2018.                                                                                                                                                                                  |
| [121]   | Andreas MTillmann and Marc E Pfetsch. The computational complexity of the restricted isometry property, the nullspace property, and related concepts in compressed sensing. IEEE Transactions on Information Theory , 60(2):1248-1259, 2013.                                                      |

| [122]   | Andreas MTillmann and Marc E Pfetsch. The computational complexity of the restricted isometry property, the nullspace property, and related concepts in compressed sensing. IEEE Transactions on Information Theory , 60(2):1248-1259, 2013.   |
|---------|------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [123]   | Joel A Tropp. Greed is good: Algorithmic results for sparse approximation. IEEE Transactions on Information theory , 50(10):2231-2242, 2004.                                                                                                   |
| [124]   | Joel A Tropp and Anna C Gilbert. Signal recovery from random measurements via orthogonal matching pursuit. IEEE Transactions on information theory , 53(12):4655-4666, 2007.                                                                   |
| [125]   | Joel A Tropp, Anna C Gilbert, and Martin J Strauss. Algorithms for simultaneous sparse approx- imation. part i: Greedy pursuit. Signal processing , 86(3):572-588, 2006.                                                                       |
| [126]   | Martin J Wainwright. Sharp thresholds for high-dimensional and noisy sparsity recovery using glyph[lscript] 1 -constrained quadratic programming (lasso). IEEE transactions on information theory , 55(5):2183- 2202, 2009.                    |
| [127]   | Jian Wang. Support recovery with orthogonal matching pursuit in the presence of noise. IEEE Transactions on Signal Processing , 63(21):5868-5877, 2015.                                                                                        |
| [128]   | Jian Wang, Seokbeop Kwon, and Byonghyo Shim. Generalized orthogonal matching pursuit. IEEE Transactions on signal processing , 60(12):6202-6216, 2012.                                                                                         |
| [129]   | Sheng Wang and Nazanin Rahnavard. Binary compressive sensing via sum of l1-norm and l (infinity)-norm regularization. In MILCOM 2013-2013 IEEE Military Communications Confer- ence , pages 1616-1621. IEEE, 2013.                             |
| [130]   | Yu Wang, Jie Yang, Miao Liu, and Guan Gui. Lightamc: Lightweight automatic modulation clas- sification via deep learning and compressive sensing. IEEE Transactions on Vehicular Technology , 69(3):3491-3495, 2020.                           |
| [131]   | Jinming Wen, Huangke Chen, and Zhengchun Zhou. An optimal condition for the block orthogonal matching pursuit algorithm. IEEE Access , 6:38179-38185, 2018.                                                                                    |
| [132]   | Jinming Wen, Dongfang Li, and Fumin Zhu. Stable recovery of sparse signals via lp-minimization. Applied and Computational Harmonic Analysis , 38(1):161-176, 2015.                                                                             |
| [133]   | Jinming Wen, Zhengchun Zhou, Dongfang Li, and Xiaohu Tang. A novel sufficient condition for generalized orthogonal matching pursuit. IEEE Communications Letters , 21(4):805-808, 2016.                                                        |
| [134]   | Jinming Wen, Zhengchun Zhou, Jian Wang, Xiaohu Tang, and Qun Mo. A sharp condition for exact support recovery with orthogonal matching pursuit. IEEE Transactions on Signal Processing , 65(6):1370-1382, 2016.                                |
| [135]   | Jinming Wen, Xiaomei Zhu, and Dongfang Li. Improved bounds on restricted isometry constant for orthogonal matching pursuit. Electronics Letters , 49(23):1487-1489, 2013.                                                                      |
| [136]   | Zaiwen Wen, Wotao Yin, Donald Goldfarb, and Yin Zhang. A fast algorithm for sparse reconstruc- tion based on shrinkage, subspace optimization, and continuation. SIAM Journal on Scientific Computing , 32(4):1832-1857, 2010.                 |
| [137]   | Chunlei Xu and Laurent Jacques. Quantized compressive sensing with rip matrices: The benefit of                                                                                                                                                |

dithering.

arXiv preprint arXiv:1801.05870

,

2018.

| [138]   | Zong-Ben XU, Hai-Liang GUO, Yao WANG, and Hai ZHANG. Representative of l 1 / 2 regularization among l q (0 < q < 1) regularizations: an experimental study based on phase diagram. Acta Automatica Sinica , 38(7):1225-1228, 2012.                 |
|---------|----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [139]   | Zongben Xu, Xiangyu Chang, Fengmin Xu, and Hai Zhang. l 1 / 2 regularization: A thresholding rep- resentation theory and a fast solver. IEEE Transactions on neural networks and learning systems 23(7):1013-1027, 2012.                           |
| [140]   | Mingrui Yang and Frank de Hoog. New coherence and rip analysis for weak orthogonal matching pursuit. In 2014 IEEE Workshop on Statistical Signal Processing (SSP) , pages 376-379. IEEE, 2014.                                                     |
| [141]   | Leonid Yaroslavsky. Is 'compressed sensing' compressive? can it beat the nyquist sampling ap- proach? arXiv preprint arXiv:1501.01811 , 2015.                                                                                                      |
| [142]   | Wotao Yin, Stanley Osher, Donald Goldfarb, and Jerome Darbon. Bregman iterative algorithms for glyph[lscript] 1 -minimization with applications to compressed sensing. SIAM Journal on Imaging sciences 1(1):143-168, 2008.                        |
| [143]   | Hui Zhang, Wotao Yin, and Lizhi Cheng. Necessary and sufficient conditions of solution uniqueness in 1-norm minimization. Journal of Optimization Theory and Applications , 164(1):109-122, 2015.                                                  |
| [144]   | Ping Zhang, Shaokai Wang, Kehua Guo, and Jianxin Wang. A secure data collection scheme based on compressive sensing in wireless sensor networks. Ad Hoc Networks , 70:73-84, 2018.                                                                 |
| [145]   | Tong Zhang. Sparse recovery with orthogonal matching pursuit under rip. IEEE Transactions on Information Theory , 57(9):6215-6221, 2011.                                                                                                           |
| [146]   | Xiaoqun Zhang, Martin Burger, and Stanley Osher. A unified primal-dual algorithm framework based on bregman iteration. Journal of Scientific Computing , 46(1):20-46, 2011.                                                                        |
| [147]   | Yin Zhang. User's guide for yall1: Your algorithms for l1 optimization. Technical report, 2011.                                                                                                                                                    |
| [148]   | Yin Zhang. Theory of compressive sensing via glyph[lscript] 1 -minimization: a non-rip analysis and extensions. Journal of the Operations Research Society of China , 1(1):79-105, 2013.                                                           |
| [149]   | Yin Zhang. Theory of compressive sensing via 1-minimization: a non-rip analysis and extensions. Journal of the Operations Research Society of China , 1(1):79-105, 2013.                                                                           |
| [150]   | Zheng Zhang, Yong Xu, Jian Yang, Xuelong Li, and David Zhang. Asurvey of sparse representation: algorithms and applications. IEEE access , 3:490-530, 2015.                                                                                        |
| [151]   | Zhimin Zhang, Xinwen Liu, Shoushui Wei, Hongping Gan, Feifei Liu, Yuwen Li, Chengyu Liu, and Feng Liu. Electrocardiogram reconstruction based on compressed sensing. IEEE Access , 2019.                                                           |
| [152]   | Yun-Bin Zhao. Rsp-based analysis for sparsest and least glyph[lscript] 1 -norm solutions to underdetermined linear systems. IEEE Transactions on Signal Processing , 61(22):5777-5788, 2013.                                                       |
| [153]   | Yun-Bin Zhao. Equivalence and strong equivalence between the sparsest and least glyph[lscript] 1 -norm nonneg- ative solutions of linear systems and their applications. Journal of the Operations Research Society of China , 2(2):171-193, 2014. |

[154] Yun-Bin Zhao. Sparse Optimization Theory and Methods . CRC Press, 2018.

- [155] Le Zheng, Arian Maleki, Haolei Weng, Xiaodong Wang, and Teng Long. Does glyph[lscript] p -minimization outperform glyph[lscript] 1 -minimization? IEEE Transactions on Information Theory , 63(11):6896-6935, 2017.
- [156] Argyrios Zymnis, Stephen Boyd, and Emmanuel Candes. Compressed sensing with quantized measurements. IEEE Signal Processing Letters , 17(2):149-152, 2009.
Ahmad Mousavi Mehdi Rezaee Ramin Ayanzadeh
A Survey on Compressive Sensing: Classical Results and Recent Advancements
Recovering sparse signals from linear measurements has demonstrated
outstanding utility in a vast variety of real-world applications. Compressive
sensing is the topic that studies the associated raised questions for the
possibility of a successful recovery. This topic is well-nourished and numerous
results are available in the literature. However, their dispersity makes it
challenging and time-consuming for readers and practitioners to quickly grasp
its main ideas and classical algorithms, and further touch upon the recent
advancements in this surging field. Besides, the sparsity notion has already
demonstrated its effectiveness in many contemporary fields. Thus, these results
are useful and inspiring for further investigation of related questions in
these emerging fields from new perspectives. In this survey, we gather and
overview vital classical tools and algorithms in compressive sensing and
describe significant recent advancements. We conclude this survey by a
numerical comparison of the performance of described approaches on an
interesting application.