Deterministic constructions of compressed sensing matrices

By Ronald A. DeVore. Journal of Complexity, 2007

620 citations recorded by the source corpus.

Subfields: Biomedical Engineering, Computational Mechanics, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/d0682e1dbdec523567c1167036aa8d46c5a8ab3e

How researchers see this paper

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

In Biomedical Engineering

In Computational Mechanics

In Computer Networks and Communications

Citations in the corpus

Structured Compressed Sensing: From Theory to Applications (2011, background): “om the Alltop sequence [42] and more general equiangular tight frames [33]. It is also possible to construct deterministic CS matrices of size M N that have the (K;)-RIP for K = O( p MlogM=log(N=M)) [43]. These constructions restrict the number of measurements needed to recover a K-sparse signal to ”
Kernel Sparse Representation-Based Classifier (2012, methodology): “The -norm regularization is widely used to recover a compressible signal in compressed sensing domain [1]–[4], [6],”
Compressive Sensing with structured random matrices (2012, neutral): “3) – or Gershgorin’s theorem [8, 71, 135] that is often applied in the sparse approximation literature [127, 37] – which is used to establish Propostion 2.”
Steiner equiangular tight frames (2010, background): “Instead, the best known deterministic constructions, such as the one given in [13], have M = O(K(2)).”
The Computational Complexity of the Restricted Isometry Property, the Nullspace Property, and Related Concepts in Compressed Sensing (2012, background): “s are highly likely to satisfy the RIP with desirable values of δk, see, for instance, [3,7]. There also has been work on deterministic matrix constructions aiming at relatively good RIPs, see, e.g., [21,32,8]. The RIP also provides sparse recovery guarantees for other heuristics such as Orthogonal ”
Restricted isometry properties and nonconvex compressive sensing (2007, neutral): “More general matrices are considered in [3, 11].”
Compressed Sensing (2012, background): “The first noteworthy construction was presented by DeVore and requires m & k, see [17].”
Combining geometry and combinatorics: A unified approach to sparse signal recovery (2008, background): “ﬃcient sketch update is not possible. In addition, the problem of ﬁnding an explicit construction of eﬃcient matrices satisfying the RIP property is open [Tao07]; the best known explicit construction [DeV07] yields Ω(k2) measurements. Connections. There has been some recent progress in obtaining the”
Deterministic Designs with Deterministic Guarantees: Toeplitz Compressed Sensing Matrices, Sequence Designs and System Identification (2008, background): “Earlier work on CS established RIP property for random constructions and recent work has produced deterministic designs based on deterministic sequence constructions [8, 11].”
New and Improved Johnson-Lindenstrauss Embeddings via the Restricted Isometry Property (2010, positive): “Using ﬁnite ﬁelds, DeVore [16] provides deterministic constructs of cyclic 0-1-valued matrices with ( k, δ )-RIP with m & δ − 2 k 2 log 2 ( N ).”
Multi-Label Prediction via Compressed Sensing (2009, background): “g.[15]), the best guarantees are obtained when the matrix is chosen randomly from an appro priate distribution, such as one of the following [16, 17].”
Toeplitz Compressed Sensing Matrices With Applications to Sparse Channel Estimation (2010, methodology): “In addition, Geršgorin-like techniques arise in the proof of RIP for the deterministic constructions of [38], and are mentioned in [40] in the context of determining the eigenvalues of randomly chosen submatrices of a given dictionary matrix.”
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.”
Label-Embedding for Image Classification (2015, positive): “The class embeddings are drawn from a standard normal distribution, similar to random projections in compressed sensing [68].”
Linearized Bregman iterations for compressed sensing (2009, background): “, see [8, 19, 23, 24, 29, 33, 34]) concentrating on proving the equivalence between (1.”