Atomic Decomposition by Basis Pursuit
The DOI matches its Crossref record; 38 of the 38 references it cites were found in a registry or an index.
Abstract
The time-frequency and time-scale communities have recently developed a large number of overcomplete waveform dictionaries---stationary wavelets, wavelet packets, cosine packets, chirplets, and warplets, to name a few. Decomposition into overcomplete systems is not unique, and several methods for decomposition have been proposed, including the method of frames (MOF), matching pursuit (MP), and, for special dictionaries, the best orthogonal basis (BOB). 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. We give examples exhibiting several advantages over MOF, MP, and BOB, including better sparsity and superresolution. BP has interesting relations to ideas in areas as diverse as ill-posed problems, abstract harmonic analysis, total variation denoising, and multiscale edge denoising. BP in highly overcomplete dictionaries leads to large-scale optimization problems. With signals of length 8192 and a wavelet packet dictionary, one gets an equivalent linear program of size 8192 by 212,992. Such problems can be attacked successfully only because of recent advances in linear and quadratic programming by interior-point methods. We obtain reasonable success with a primal-dual logarithmic barrier method and conjugate-gradient solver.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Golub, G. (2012) · doi:10.56021/9781421407944 · Cited by 34,505
Daubechies, I. (1992) · doi:10.1137/1.9781611970104 · Cited by 15,979
Nonlinear total variation based noise removal algorithms
Rudin, L. I., Osher, S., & Fatemi, E. (1992) · Physica D: Nonlinear Phenomena · doi:10.1016/0167-2789(92)90242-f · Cited by 15,704
Daubechies, I., & Heil, C. (1992) · Computers in Physics · doi:10.1063/1.4823127 · Cited by 15,631
De-noising by soft-thresholding
Donoho, D. L. (1995) · IEEE Transactions on Information Theory · doi:10.1109/18.382009 · Cited by 9,619
Self-citationMatching pursuits with time-frequency dictionaries
Mallat, S. G., & Zhang, Z. (1993) · IEEE Transactions on Signal Processing · doi:10.1109/78.258082 · Cited by 9,112
Atomic Decomposition by Basis Pursuit
Chen, S. S., Donoho, D. L., & Saunders, M. A. (1998) · SIAM Journal on Scientific Computing · doi:10.1137/s1064827596304010 · Cited by 6,845
Self-citationLinear Programming and Extensions
Dantzig, G. (1963) · RAND Corporation eBooks · doi:10.7249/r366 · Cited by 5,755
Габор, Д. (1946) · Journal of the IEE · Cited by 5,036
A new polynomial-time algorithm for linear programming
Karmarkar, N. (1984) · Combinatorica · doi:10.1007/bf02579150 · Cited by 4,794
LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares
Paige, C. C., & Saunders, M. A. (1982) · ACM Transactions on Mathematical Software · doi:10.1145/355984.355989 · Cited by 4,387
Self-citationInterior-Point Polynomial Algorithms in Convex Programming
Nesterov, Y., & Nemirovskii, A. (1994) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611970791 · Cited by 4,334
Pati, Y. C., Rezaiifar, R., & Krishnaprasad, P. S. (2002) · Proceedings of 27th Asilomar Conference on Signals, Systems and Computers · doi:10.1109/acssc.1993.342465 · Cited by 4,323
Singularity detection and processing with wavelets
Mallat, S., & Hwang, W. L. (1992) · IEEE Transactions on Information Theory · doi:10.1109/18.119727 · Cited by 3,863
Entropy-based algorithms for best basis selection
Coifman, R. R., & Wickerhauser, M. V. (1992) · IEEE Transactions on Information Theory · doi:10.1109/18.119732 · Cited by 3,188
Primal-Dual Interior-Point Methods
Wright, S. J. (1997) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611971453 · Cited by 2,391
Uncertainty principles and ideal atomic decomposition
Donoho, D. L., & Huo, X. (2001) · IEEE Transactions on Information Theory · doi:10.1109/18.959265 · Cited by 1,949
Self-citationWavelet Shrinkage: Asymptopia?
Donoho, D. L., Johnstone, I. M., Kerkyacharian, G., & Picard, D. (1995) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1995.tb02032.x · Cited by 1,749
Self-citationOrthogonal least squares methods and their application to non-linear system identification
Chen, S., Billings, S. A., & Luo, W. (1989) · International Journal of Control · doi:10.1080/00207178908953472 · Cited by 1,540
Self-citationShiftable multiscale transforms
Simoncelli, E. P., Freeman, W. T., Adelson, E. H., & Heeger, D. J. (1992) · IEEE Transactions on Information Theory · doi:10.1109/18.119725 · Cited by 1,333
Algorithm 583: LSQR: Sparse Linear Equations and Least Squares Problems
Paige, C. C., & Saunders, M. A. (1982) · ACM Transactions on Mathematical Software · doi:10.1145/355993.356000 · Cited by 792
Self-citationTime-frequency localization operators: a geometric phase space approach
Daubechies, I. (1988) · IEEE Transactions on Information Theory · doi:10.1109/18.9761 · Cited by 649
Some remarks on greedy algorithms
DeVore, R., & Temlyakov, V. N. (1996) · Advances in Computational Mathematics · doi:10.1007/bf02124742 · Cited by 646
Wedgelets: nearly minimax estimation of edges
Donoho, D. L. (1999) · The Annals of Statistics · doi:10.1214/aos/1018031261 · Cited by 638
Self-citationBloomfield, P., & Steiger, W. L. (1984) · CERN Document Server (European Organization for Nuclear Research) · doi:10.1007/978-1-4684-8574-5 · Cited by 553
WaveLab and Reproducible Research
Buckheit, J. B., & Donoho, D. L. (1995) · Lecture Notes in Statistics · doi:10.1007/978-1-4612-2544-7_5 · Cited by 537
Self-citationA Primal-Dual Interior Point Algorithm for Linear Programming
Kojima, M., Mizuno, S., & Yoshise, A. (1989) · Springer eBooks · doi:10.1007/978-1-4613-9617-8_2 · Cited by 517
Theory and algorithms for linear optimization : an interior point approach
Roos, C., Tamás Terlaky, B., & Vial, J.-P. (1997) · Wiley eBooks · Cited by 506
Numerical Linear Algebra and Optimization
Gill, P. E., Murray, W., & Wright, M. H. (2021) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611976571 · Cited by 506
Chen, S., & Donoho, D. L. (1994) · Cited by 467
Self-citationAdaptive time-frequency decompositions
Mallat, S. G. (1994) · Optical Engineering · doi:10.1117/12.173207 · Cited by 358
Feature Article—Interior Point Methods for Linear Programming: Computational State of the Art
Lustig, I. J., Marsten, R. E., & Shanno, D. F. (1994) · INFORMS journal on computing · doi:10.1287/ijoc.6.1.1 · Cited by 315
Signal representation using adaptive normalized Gaussian functions
Qian, S., & Chen, D. (1994) · Signal Processing · doi:10.1016/0165-1684(94)90174-0 · Cited by 248
Remarques sur l'analyse de Fourier à fenêtre
Coifman, R. R., & Meyer, Y. (1991) · Comptes Rendus Mathématique · Cited by 186
A computational algorithm for minimizing total variation in image restoration
Li, Y., & Santosa, F. (1996) · IEEE Transactions on Image Processing · doi:10.1109/83.503914 · Cited by 178
Block Coordinate Relaxation Methods for Nonparametric Wavelet Denoising
Sardy, S., Bruce, A. G., & Tseng, P. (2000) · Journal of Computational and Graphical Statistics · doi:10.1080/10618600.2000.10474885 · Cited by 171
Commentary—Progress in Linear Programming
Bixby, R. E. (1994) · INFORMS journal on computing · doi:10.1287/ijoc.6.1.15 · Cited by 88
Superfast algorithms for Cauchy-like matrix computations and extensions
Pan, V. Y., & Zheng, A.-L. (2000) · Linear Algebra and its Applications · doi:10.1016/s0024-3795(00)00041-0 · Cited by 30
Cited by
Boyd, S., Parikh, N., Chu, E., Peleato, B., & Eckstein, J. (2011) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000016 · Cited by 17,075
Boyd, S. (2010) · now publishers, Inc. eBooks · doi:10.1561/9781601984616 · Cited by 12,677
Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit
Tropp, J. A., & Gilbert, A. C. (2007) · IEEE Transactions on Information Theory · doi:10.1109/tit.2007.909108 · Cited by 9,653
$rm K$-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation
Aharon, M., Elad, M., & Bruckstein, A. (2006) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2006.881199 · Cited by 9,451
Robust Face Recognition via Sparse Representation
Wright, J., Yang, A. Y., Ganesh, A., Sastry, S. S., & Ma, Y. (2009) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2008.79 · Cited by 9,388
Metadata
- Authors
- Chen, S. S., Donoho, D. L., & Saunders, M. A.
- Venue
- SIAM Review
- Published
- 2001-01
- Volume
- 43
- Issue
- 1
- Pages
- 129-159
- ISSN
- 0036-1445 (ISSN-L)
- 1095-7200
- OpenAlex
- W2078204800
- Cited by
- 5,085
- References
- 38
- FWCI
- 49.52
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.