Compressed sensing and best k-term approximation

By Albert Cohen, Wolfgang Dahmen, Ronald A. DeVore. 2008

1,051 citations recorded by the source corpus.

The typical paradigm for obtaining a compressed version of a discrete signal represented by a vector x ∈ R is to choose an appropriate basis, compute the coefficients of x in this basis, and then retain only the k largest of these with k < N . If we are interested in a bit stream representation, we also need in addition to quantize these k coefficients. Assuming, without loss of generality, that x already represents the coefficients of the signal in the appropriate basis, this means that we pick an approximation to x in the set Σk of k-sparse vectors (1.1) Σk := {x ∈ R : # supp(x) ≤ k}, where supp(x) is the support of x, i.e., the set of i for which xi = 0, and #A is the number of elements in the set A. The best performance that we can achieve by such an approximation process in some given norm ‖ · ‖X of interest is described by the best k-term approximation error

Subfields: Applied Mathematics, Biomedical Engineering, Computational Mechanics

View Paper: https://www.semanticscholar.org/paper/0ae5418c629e089661cc519db60add20bad40ad7

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Biomedical Engineering

In Computational Mechanics

Citations in the corpus

Learning to Sense Sparse Signals: Simultaneous Sensing Matrix and Sparsifying Dictionary Optimization (2009, methodology): “We start by reviewing prior related work, following by the presentation of our proposed algorithm and the first results showing the computational and reconstruction advantages of this new approach.”
A Probabilistic and RIPless Theory of Compressed Sensing (2010, background): “This literature is, of course, extremely large and we cannot cite all contributions but a partial list would include [15], [21], [46], [13], [16], [5], [19], [50], [51], [3], [37], [29], [7], [2].”
CoSaMP: Iterative signal recovery from incomplete and inaccurate samples (2008, neutral): “This idea appears in the work of Candès–Romberg–Tao on convex relaxation [3]; it is used in the analysis of HHS pursuit [18]; it also plays a role in the theoretical treatment of Cohen–Dahmen–DeVore [7].”
Combining geometry and combinatorics: A unified approach to sparse signal recovery (2008, background): “In [ CDD06 ], the authors show that an approximation guarantee of the form “l2 ≤ C k1/2 l1” implies a “l1 ≤ (1 + O(C))l1” guarantee, and that it is impossible to achieve “l2 ≤ Cl2” deterministically (or for all signals simultaneously) unless the number of measurements is (n).”
Exact Recovery of Chaotic Systems from Highly Corrupted Data (2016, background): “As shown in [Don06, CRT06, CDD09], a certain null-space property for an m × n matrix A is a suﬃcient and necessary condition for sparse solutions to be exactly recovered via (cid:96) 1 minimization.”
Non-convex Optimization for Machine Learning (2017, neutral): “Definition 7.1 (Nullspace Property [Cohen et al., 2009]).”
Estimation of (near) low-rank matrices with noise and high-dimensional scaling (2009, methodology): “ts some κ(X) >0 such that 1 2N kX(∆)k2 2 ≥ κ(X) |||∆|||2 F for all ∆ ∈ C. (10) We note that analogous conditions have been used to establish error bounds in the context of sparse linear regression [9, 15], in which case the set C corresponded to certain subsets of sparse vectors. Of course, the d”
Compressed Sensing (2012, background): “The related so-called null space property, first introduced in [15], is defined as follows.”
Iteratively reweighted least squares minimization for sparse recovery (2008, background): “We suppose that the weight w is strictly positive which we deﬁne to mean that w j > 0 for all j ∈ { 1 , . . . , N } .”
Rank Awareness in Joint Sparse Recovery (2010, methodology): “In SMV the necessary and sufficien t co dition for the recovery of vectors x with supportΩ is given by theNull Space Property(see [31], [37], [38]):”
A Simple Proof of the Restricted Isometry Property for Random Matrices (2008, background): “9) is quite elementary; see [2] for the original proof and [5] for this particular formulation.”
Deterministic constructions of compressed sensing matrices (2007, background): “Given a set K , the optimal performance En,N(K) Np of CS is directly connected with the Gelfand widths of the set K .”
Spectrum sensing in cognitive radio (2016, background): “Null Space Property (NSP) The null space property [57], [25, Ch.”
Minimax Rates of Estimation for High-Dimensional Linear Regression Over q -Balls (2009, neutral): “[10] (see, in particular, their Lemma 3.”