Best Basis Compressed Sensing
IEEE Transactions on Signal ProcessingPublished 12 February 2010Open access
Gabriel Peyré
Citations140
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A best basis extension of compressed sensing recovery is proposed that makes use of sparsity in a tree-structured dictionary of orthogonal bases and improves the recovery with respect to fixed sparsity priors.
Abstract
International audience
Keywords
Computer ScienceEngineering
BiometricsClassification and Regression Trees.
23,841 Citations1984Alexander Gordon, Leo Breiman +3 more
IEEE Transactions on Information TheoryCompressed sensing
23,147 Citations2006David L. Donoho
It is shown that "most" subspaces in Ropfm are near-optimal, and that convex optimization (Basis Pursuit) is a near-optimal way to extract information derived from these near-optimal subspaces.
Compressed sensing
17,129 Citations2004David L. Donoho
Elsevier eBooksA Wavelet Tour of Signal Processing
16,401 Citations1999Stéphane Mallat
An introduction to a Transient World and an Approximation Tour of Wavelet Packet and Local Cosine Bases.
IEEE Transactions on Information TheoryRobust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
15,775 Citations2006Emmanuel J. Candès, Justin Romberg +1 more
It is shown how one can reconstruct a piecewise constant object from incomplete frequency samples - provided that the number of jumps (discontinuities) obeys the condition above - by minimizing other convex functionals such as the total variation of f.
IEEE Transactions on Information TheorySignal Recovery From Random Measurements Via Orthogonal Matching Pursuit
9,670 Citations2007Joel A. Tropp, Anna C. Gilbert
IEEE Transactions on Information TheoryDecoding by Linear Programming
7,181 Citations2005Emmanuel J. Candès, Terence Tao
F can be recovered exactly by solving a simple convex optimization problem (which one can recast as a linear program) and numerical experiments suggest that this recovery procedure works unreasonably well; f is recovered exactly even in situations where a significant fraction of the output is corrupted.
Communications on Pure and Applied MathematicsStable signal recovery from incomplete and inaccurate measurements
7,170 Citations2006Emmanuel J. Candès, Justin Romberg +1 more
It is shown that it is possible to recover x0 accurately based on the data y from incomplete and contaminated observations.
Magnetic Resonance in MedicineSparse MRI: The application of compressed sensing for rapid MR imaging
6,980 Citations2007Michael Lustig, David L. Donoho +1 more
Practical incoherent undersampling schemes are developed and analyzed by means of their aliasing interference and demonstrate improved spatial resolution and accelerated acquisition for multislice fast spin‐echo brain imaging and 3D contrast enhanced angiography.
SIAM Journal on Scientific ComputingAtomic Decomposition by Basis Pursuit
6,899 Citations1998Scott Shaobing Chen, David L. Donoho +1 more
Basis Pursuit (BP) is a principle for decomposing a signal into an "optimal" superposition of dictionary elements, where optimal means having the smallest l1 norm of coefficients among all such decompositions.
IEEE Transactions on Information TheoryNear-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
6,835 Citations2006Emmanuel J. Candès, Terence Tao
If the objects of interest are sparse in a fixed basis or compressible, then it is possible to reconstruct f to within very high accuracy from a small number of random measurements by solving a simple linear program.
The Journal of PhysiologyReceptive fields and functional architecture of monkey striate cortex
6,636 Citations1968David H. Hubel, T. N. Wiesel
The striate cortex was studied in lightly anaesthetized macaque and spider monkeys by recording extracellularly from single units and stimulating the retinas with spots or patterns of light, with response properties very similar to those previously described in the cat.
NatureEmergence of simple-cell receptive field properties by learning a sparse code for natural images
5,840 Citations1996Bruno A. Olshausen, David J. Field
It is shown that a learning algorithm that attempts to find sparse linear codes for natural scenes will develop a complete family of localized, oriented, bandpass receptive fields, similar to those found in the primary visual cortex.
SIAM ReviewAtomic Decomposition by Basis Pursuit
5,145 Citations2001Scott Shaobing Chen, David L. Donoho +1 more
Communications on Pure and Applied MathematicsAn iterative thresholding algorithm for linear inverse problems with a sparsity constraint
4,957 Citations2004Ingrid Daubechies, Michel Defrise +1 more
It is proved that replacing the usual quadratic regularizing penalties by weighted 𝓁p‐penalized penalties on the coefficients of such expansions, with 1 ≤ p ≤ 2, still regularizes the problem.
Comptes Rendus MathématiqueThe restricted isometry property and its implications for compressed sensing
3,779 Citations2008Emmanuel J. Candès
IEEE Signal Processing MagazineSingle-pixel imaging via compressive sampling
3,555 Citations2008Marco F. Duarte, Mark A. Davenport +5 more
A new camera architecture based on a digital micromirror device with the new mathematical theory and algorithms of compressive sampling is presented that can operate efficiently across a broader spectral range than conventional silicon-based cameras.
IEEE Transactions on Information TheoryEntropy-based algorithms for best basis selection
3,173 Citations1992Ronald R. Coifman, Mladen Victor Wickerhauser
Adapted waveform analysis uses a library of orthonormal bases and an efficiency functional to match a basis to a given signal or family of signals, and relies heavily on the remarkable orthogonality properties of the new libraries.
Multiscale Modeling and SimulationSignal Recovery by Proximal Forward-Backward Splitting
2,599 Citations2005Patrick L. Combettes, Valérie R. Wajs
It is shown that various inverse problems in signal recovery can be formulated as the generic problem of minimizing the sum of two convex functions with certain regularity properties, which makes it possible to derive existence, uniqueness, characterization, and stability results in a unified and standardized fashion for a large class of apparently disparate problems.
Communications on Pure and Applied MathematicsFor most large underdetermined systems of linear equations the minimal 𝓁<sub>1</sub>‐norm solution is also the sparsest solution
2,541 Citations2006David L. Donoho
The techniques include the use of random proportional embeddings and almost‐spherical sections in Banach space theory, and deviation bounds for the eigenvalues of random Wishart matrices.
Behavioral and Brain SciencesHow brains make chaos in order to make sense of the world
2,116 Citations1987Christine A. Skarda, Walter J. Freeman
A model to describe the neural dynamics responsible for odor recognition and discrimination is developed and it is hypothesized that chaotic behavior serves as the essential ground state for the neural perceptual apparatus and a mechanism for acquiring new forms of patterned activity corresponding to new learned odors is proposed.
Communications on Pure and Applied MathematicsNew tight frames of curvelets and optimal representations of objects with piecewise <i>C</i><sup>2</sup> singularities
1,571 Citations2003Emmanuel J. Candès, David L. Donoho
This paper introduces new tight frames of curvelets to address the problem of finding optimally sparse representations of objects with discontinuities along piecewise C2 edges.
IEEE Transactions on Information TheoryModel-Based Compressive Sensing
1,279 Citations2010Richard G. Baraniuk, Volkan Cevher +2 more
A model-based CS theory is introduced that parallels the conventional theory and provides concrete guidelines on how to create model- based recovery algorithms with provable performance guarantees and a new class of structured compressible signals along with a new sufficient condition for robust structured compressable signal recovery that is the natural counterpart to the restricted isometry property of conventional CS.
IEEE Transactions on Image ProcessingAn EM algorithm for wavelet-based image restoration
1,204 Citations2003Mário A. T. Figueiredo, R.D. Nowak
An expectation-maximization (EM) algorithm for image restoration (deconvolution) based on a penalized likelihood formulated in the wavelet domain is introduced, and it is shown that under mild conditions the algorithm converges to a globally optimal restoration.
IEEE Transactions on Information TheoryRobust Recovery of Signals From a Structured Union of Subspaces
1,054 Citations2009Yonina C. Eldar, Moshe Mishali
This paper develops a general framework for robust and efficient recovery of nonlinear but structured signal models, in which x lies in a union of subspaces, and presents an equivalence condition under which the proposed convex algorithm is guaranteed to recover the original signal.
Academic Press eBooksA Wavelet Tour of Signal Processing, Third Edition: The Sparse Way
952 Citations2008Stphane Mallat
Mucolytic treatment should be considered in patients with more severe COPD who have frequent or prolonged exacerbations; those who are repeatedly admitted to hospital; or in those patients with frequent exacerbations who are unable to take tiotropium or ICS.
Signal ProcessingExtensions of compressed sensing
934 Citations2005Yaakov Tsaig, David L. Donoho
The results show that, when appropriately deployed in a favorable setting, the CS framework is able to save significantly over traditional sampling, and there are many useful extensions of the basic idea.
Communications on Pure and Applied MathematicsOn sparse reconstruction from Fourier and Gaussian measurements
883 Citations2007Mark Rudelson, Roman Vershynin
This paper improves upon best‐known guarantees for exact reconstruction of a sparse signal f from a small universal sample of Fourier measurements by showing that there exists a set of frequencies Ω such that one can exactly reconstruct every r‐sparse signal f of length n from its frequencies in Ω, using the convex relaxation.
IEEE Transactions on Image ProcessingSparse geometric image representations with bandelets
844 Citations2005Erwan Le Pennec, Stéphane Mallat
A new class of bases are introduced, called bandelet bases, which decompose the image along multiscale vectors that are elongated in the direction of a geometric flow, which leads to optimal approximation rates for geometrically regular images.
IEEE Transactions on Signal ProcessingOptimized Projections for Compressed Sensing
841 Citations2007Michael Elad
This paper considers the optimization of compressed sensing projections, and targets an average measure of the mutual coherence of the effective dictionary, and shows that this leads to better CS reconstruction performance.
SIAM Journal on Imaging SciencesBregmanized Nonlocal Regularization for Deconvolution and Sparse Reconstruction
694 Citations2010Xiaoqun Zhang, Martin Burger +2 more
The proposed general algorithm framework for inverse problem regularization with a single forward-backward operator step, namely, Bregmanized operator splitting (BOS), converges without fully solving the subproblems, and numerical results on deconvolution and compressive sensing illustrate the performance of nonlocal total variation regularization under the proposed algorithm framework.
The Annals of StatisticsWedgelets: nearly minimax estimation of edges
639 Citations1999David L. Donoho
An overcomplete collection of atoms called wedgelets, dyadically organized indicator functions with a variety of locations, scales, and orientations are developed, which provides nearly-optimal representations of objects in the Horizon model, as measured by minimax description length.
IEEE Transactions on Image ProcessingLearning to Sense Sparse Signals: Simultaneous Sensing Matrix and Sparsifying Dictionary Optimization
577 Citations2009Julio M. Duarte‐Carvajalino, Guillermo Sapiro
A framework for the joint design and optimization, from a set of training images, of the nonparametric dictionary and the sensing matrix is introduced and it is shown that this joint optimization outperforms both the use of random sensing matrices and those matrices that are optimized independently of the learning of the dictionary.
IEEE Transactions on Information TheoryCompressed Sensing and Redundant Dictionaries
551 Citations2008Holger Rauhut, Karin Schnass +1 more
It is shown that a matrix, which is a composition of a random matrix of certain type and a deterministic dictionary, has small restricted isometry constants, and signals that are sparse with respect to the dictionary can be recovered via basis pursuit from a small number of random measurements.
Advances in imaging and electron physicsRedundant Multiscale Transforms and Their Application for Morphological Component Separation
439 Citations2004Jean‐Luc Starck, Michael Elad +1 more
This chapter presents an alternative deterministic methodology, based on sparsity, toward the problem of morphological component analysis (MCA) and anchors this method with some conclusive theoretical results, essentially guaranteeing successful separation under some conditions.
Sparse solution of underdetermined linear equations by stagewise orthogonal matching pursuit
419 Citations2006David L. Donoho, Yaakov Tsaig +2 more
It is shown that for systems with ‘typical’/‘random’ Φ, a good approximation to the sparsest solution is obtained by applying a fixed number of standard operations from linear algebra, and rigorously derive a conditioned Gaussian distribution for the matched filtering coefficients at each stage of the procedure.
Foundations of Computational MathematicsRandom Projections of Smooth Manifolds
413 Citations2007Richard G. Baraniuk, Michael B. Wakin
A new approach for nonadaptive dimensionality reduction of manifold-modeled data is proposed, demonstrating that a small number of random linear projections can preserve key information about a manifold- modeled signal.
Practical Signal Recovery from Random Projections
292 Citations2005Justin Romberg
It is demonstrated empirically that it is possible to recover an object from about 3M ‐5M projections onto generically chosen vectors with the same accuracy as the ideal M -term wavelet approximation.
Lecture notes in computer scienceNon-local Regularization of Inverse Problems
244 Citations2008Gabriel Peyré, Sébastien Bougleux +1 more
A new framework to regularize linear inverse problems using the total variation on non-local graphs to adapt the penalization to the geometry of the underlying function to recover is proposed.
Computer Vision and Image UnderstandingManifold models for signals and images
221 Citations2008Gabriel Peyré
A new class of models for natural signals and images that constrain the set of patches extracted from the data to analyze to be close to a low-dimensional manifold that can be used to regularize inverse problems in signal and image processing.
Multiscale Modeling and SimulationBandelet Image Approximation and Compression
211 Citations2005Erwan Le Pennec, Stéphane Mallat
For functions that are uniformly regular outside a set of edge curves that are geometrically regular, the main theorem proves that bandelet approximations satisfy an optimal asymptotic error decay rate.
The Annals of StatisticsCART and best-ortho-basis: a connection
210 Citations1997David L. Donoho
The basis empirically selected by dyadic CART is shown to be nearly as good as a basis ideally adapted to the underlying f, and the risk of estimation in an ideally adapted anisotropic Haar basis is shows to be comparable to the minimax risk over anisotrop smoothness classes.
IEEE Transactions on ComputersComputation of the Fast Walsh-Fourier Transform
179 Citations1969John L. Shanks
An efficient Walsh transform computation algorithm is derived which is analogous to the Cooley-Tukey algorithm for the complex-exponential Fourier transform.
ACM Transactions on GraphicsSurface compression with geometric bandelets
170 Citations2005Gabriel Peyré, Stéphane Mallat
Inverse Problems and ImagingNon-local regularization of inverse problems
125 Citations2011Gabriel Peyré, Sébastien Bougleux +1 more
Communications on Pure and Applied MathematicsOrthogonal bandelet bases for geometric images approximation
88 Citations2008Gabriel Peyré, Stéphane Mallat
It is proved that C α‐images having singularities along Cα‐curves are approximated in a best orthogonal bandelet basis with an optimal asymptotic error decay.
Journal of Physiology-ParisComputations in the early visual cortex
78 Citations2003Tai Sing Lee
The evidence argues that the early visual cortex does not merely participate in the first stage of visual processing, but is involved in many levels of visual computation, subject to influence from global context, higher order perceptual inference, task requirement and behavioral experience.
SIAM Journal on Mathematical AnalysisNonstationary Subdivision Schemes and Multiresolution Analysis
75 Citations1996Albert Cohen, Nira Dyn
arXiv (Cornell University)Robust Recovery of Signals From a Union of Subspaces
62 Citations2008Yonina C. Eldar, Moshe Mishali
Applied and Computational Harmonic AnalysisModulated Malvar–Wilson Bases
16 Citations1997Ronald R. Coifman, Gregory Matviyenko +1 more
Best basis denoising with non-stationary wavelet packets
9 Citations2009Nizar Ouarti, Gabriel Peyré
An optimized labeled quad-tree that indexes the filters used for the NS wavelet packets decomposition and is made translation invariant by cycle spinning increases significantly the denoising abilities of the algorithm.