{ "id": "ep4q4b7y4m", "slug": "atomic-decomposition", "title": "Atomic decomposition", "updated": "2026-10-15", "topic_path": [ { "id": "technology", "label": "Technology and the built world", "api_url": "https://www.edgepedia.org/api/v1/topics/technology" }, { "id": "technology.computing", "label": "Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing" }, { "id": "technology.computing.ai", "label": "Artificial intelligence and data", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai" }, { "id": "technology.computing.ai.algorithms", "label": "Algorithms and computational methods", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai.algorithms" }, { "id": "technology.computing.ai.numerical_string_geometry", "label": "Numerical, string, and geometric algorithms", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai.numerical_string_geometry" }, { "id": "technology.computing.ai.numerical_string_geometry.fourier_signal_transforms", "label": "Fourier and signal transforms", "api_url": "https://www.edgepedia.org/api/v1/topics/technology.computing.ai.numerical_string_geometry.fourier_signal_transforms" } ], "geo": [ { "id": "geo.nongeo.t1946.technology.computing.ai.numerical_string_geometry.fourier_signal_transforms", "label": "Non-geographic · 1946 to 2000: Fourier and signal transforms", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai.numerical_string_geometry.fourier_signal_transforms", "path": [ { "id": "geo.nongeo", "label": "Non-geographic", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo" }, { "id": "geo.nongeo.t1946", "label": "Non-geographic · 1946 to 2000", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946" }, { "id": "geo.nongeo.t1946.technology", "label": "Technology and the built world", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology" }, { "id": "geo.nongeo.t1946.technology.computing", "label": "Computing and digital systems", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing" }, { "id": "geo.nongeo.t1946.technology.computing.ai", "label": "Artificial intelligence and data", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai" }, { "id": "geo.nongeo.t1946.technology.computing.ai.algorithms", "label": "Algorithms and computational methods", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai.algorithms" }, { "id": "geo.nongeo.t1946.technology.computing.ai.numerical_string_geometry", "label": "Numerical, string, and geometric algorithms", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai.numerical_string_geometry" }, { "id": "geo.nongeo.t1946.technology.computing.ai.numerical_string_geometry.fourier_signal_transforms", "label": "Fourier and signal transforms", "api_url": "https://www.edgepedia.org/api/v1/geo/geo.nongeo.t1946.technology.computing.ai.numerical_string_geometry.fourier_signal_transforms" } ] } ], "excerpt": "Atomic decomposition is a signal processing method that represents a signal as a sparse linear combination of elementary waveforms, called atoms, drawn from a redundant dictionary.", "snippet": "Atomic decomposition is a signal processing method that represents a signal as a sparse linear combination of elementary waveforms, called atoms, drawn from a redundant dictionary.", "node": "technology.computing.ai.numerical_string_geometry.fourier_signal_transforms", "markdown": "# Atomic decomposition\n\nAtomic decomposition represents a signal as a sparse linear combination of elementary waveforms, called atoms, drawn from a redundant dictionary, and it solves the problem of expressing a signal with far fewer active components than a fixed transform would require. The idea sits at the center of sparse approximation and dictionary learning: instead of expanding a signal in an orthonormal basis such as Fourier or wavelets, the analyst selects a small subset of atoms, from a collection that contains more vectors than the signal dimension, that best matches the signal's structure.\n\n| Key fact | Detail |\n|---|---|\n| Core problem | Given a signal \\( x \\in \\mathbb{R}^{N} \\) and a dictionary \\( D \\) of size \\( N \\times L \\) with \\( L \\gg N \\), find a coefficient vector \\( \\gamma \\) with \\( D \\cdot \\gamma = x \\) and as few nonzeros as possible [1](https://pmc.ncbi.nlm.nih.gov/articles/PMC153464/) • [2](https://link.springer.com/article/10.1186/1687-6180-2011-34) |\n| Common formulation | \\( \\hat{\\gamma} = \\operatorname{Argmin}_{\\gamma} \\|\\gamma\\|_{0} \\) subject to \\( \\|x - D\\gamma\\|_{2}^{2} \\leq \\varepsilon \\), where \\( \\varepsilon \\) is an error tolerance [3](https://csaws.cs.technion.ac.il/~ronrubin/Publications/KSVD-OMP-v2.pdf) |\n| Exact-recovery condition | Orthogonal Matching Pursuit recovers any \\( K \\)-sparse signal exactly when dictionary columns are unit-norm and the mutual coherence satisfies \\( \\mu < 1/(2K-1) \\) [4](https://ar5iv.labs.arxiv.org/html/0909.0083) |\n| Problem size | Basis pursuit on a length-8192 signal with a wavelet packet dictionary becomes a linear program of size 8192 by 212,992 [5](https://doi.org/10.1137/s1064827596304010) |\n| Fast greedy cost | CoSaMP runs in \\( O(N \\log^{2} N) \\) time for compressible signals, using only matrix-vector products and \\( O(N) \\) working storage [6](https://doi.org/10.48550/arxiv.0803.2392) |\n| Dictionary learning | K-SVD alternates sparse coding of the examples with atom-by-atom dictionary updates, generalizing K-means clustering [7](https://doi.org/10.1109/tsp.2006.881199) |\n| Main applications | Speech and audio compression, denoising, source separation, automatic indexing, and compressive sensing recovery [2](https://link.springer.com/article/10.1186/1687-6180-2011-34) • [4](https://ar5iv.labs.arxiv.org/html/0909.0083) |\n\n## How it works\n\nA dictionary is a matrix whose columns are candidate atoms: Gabor functions, wavelet packets, sinusoids, or spikes. Because the dictionary is overcomplete, with more columns \\( L \\) than signal dimension \\( N \\), infinitely many coefficient vectors \\( \\gamma \\) satisfy \\( D \\cdot \\gamma = x \\); the goal is the sparsest one, measured by the \\( \\ell_{0} \\) norm \\( \\|\\gamma\\|_{0} \\), the count of nonzero entries.[1](https://pmc.ncbi.nlm.nih.gov/articles/PMC153464/) • [2](https://link.springer.com/article/10.1186/1687-6180-2011-34) When the signal can be written as a highly sparse sum of atoms in only one way, and an optimization principle finds that decomposition, the result is called an ideal atomic decomposition.[8](http://www.rctn.org/w/images/6/6e/00959265.pdf)\n\nThe contrast with a fixed basis is computational. If the dictionary is an orthonormal basis, the sparse approximation problem has a straightforward solution built one term at a time.[9](https://dl.acm.org/doi/10.1109/TIT.2004.834793) In a redundant dictionary the atoms interact, so choosing the best \\( K \\)-term subset requires, in general, enumerating subsets of the dictionary, and the cost of that search grows exponentially with \\( L \\).[1](https://pmc.ncbi.nlm.nih.gov/articles/PMC153464/)\n\nTwo dictionary properties determine when exact recovery is provable. The mutual coherence \\( \\mu := \\max_{i,j} |\\langle \\phi_{i}, \\phi_{j} \\rangle| \\) measures the largest absolute inner product between unit-norm dictionary columns; when \\( \\mu < 1/(2K-1) \\), OMP recovers any \\( K \\)-sparse signal exactly.[4](https://ar5iv.labs.arxiv.org/html/0909.0083) The restricted isometry property (RIP) of order \\( k \\) requires a constant \\( \\delta \\) such that the matrix approximately preserves the norms of all \\( k \\)-sparse vectors; it is a sufficient condition for exact sparse recovery by \\( \\ell_{1} \\)-minimization and related algorithms.[4](https://ar5iv.labs.arxiv.org/html/0909.0083)\n\n## How it is done\n\nGreedy algorithms build the decomposition one atom at a time. [Matching pursuit](https://www.edgepedia.org/matching-pursuit), the founding procedure, computes the inner products of the current residual with all dictionary elements, selects the most correlated atom, and subtracts its contribution.[10](https://doi.org/10.1109/78.258082) • [11](https://elad.cs.technion.ac.il/wp-content/uploads/2018/02/23_Stability_IEEE_TIT.pdf) Orthogonal Matching Pursuit (OMP) adds a least-squares minimization at each step to obtain the best approximation of the signal over the atoms already chosen, which significantly improves the rate of convergence over plain matching pursuit; it applies to nonorthogonal and possibly overcomplete dictionaries.[9](https://dl.acm.org/doi/10.1109/TIT.2004.834793) • [12](https://www.khoury.northeastern.edu/home/eelhami/courses/EE290A/OMP_Krishnaprasad.pdf) CoSaMP ([Compressive Sampling Matching Pursuit](https://www.edgepedia.org/compressive-sampling-matching-pursuit)) is an iterative method based on OMP that delivers the same guarantees as the best optimization-based approaches, with rigorous bounds on computational cost and storage.[6](https://doi.org/10.48550/arxiv.0803.2392)\n\nThe convex-relaxation line replaces the \\( \\ell_{0} \\) objective with the \\( \\ell_{1} \\) norm. [Basis pursuit](https://www.edgepedia.org/basis-pursuit) decomposes a signal into the superposition of dictionary atoms with the smallest \\( \\ell_{1} \\) norm of coefficients; strictly speaking it is a principle rather than an algorithm, replacing \\( \\min \\|x - \\Phi \\cdot b\\|_{2} \\) subject to \\( \\|b\\|_{0} = m \\) with \\( \\min \\|b\\|_{1} \\) subject to \\( \\Phi \\cdot b = x \\).[5](https://doi.org/10.1137/s1064827596304010) • [9](https://dl.acm.org/doi/10.1109/TIT.2004.834793) Over signals with coefficient magnitudes bounded by 1, the \\( \\ell_{1} \\) norm is the largest convex function less than the \\( \\ell_{0} \\) norm, making the \\( \\ell_{1} \\) problem the closest convex optimization problem to the \\( \\ell_{0} \\) problem, and it can be cast as a linear program solved by interior-point methods even for large \\( N \\) and \\( L \\).[1](https://pmc.ncbi.nlm.nih.gov/articles/PMC153464/)\n\n## Origin\n\nThe dictionary methodology in computational harmonic analysis is associated with S. G. Mallat and Zhifeng Zhang's 1993 paper \"Matching pursuits with time-frequency dictionaries\" in IEEE Transactions on Signal Processing, which presented matching pursuit as a way to decompose any signal into a linear expansion of waveforms selected from a redundant dictionary to best match the signal structures.[10](https://doi.org/10.1109/78.258082) Shortly after, Chen, Donoho, and Saunders published \"Atomic Decomposition by Basis Pursuit\" in SIAM Journal on Scientific Computing in 1998.[5](https://doi.org/10.1137/s1064827596304010) CoSaMP was reported by D. Needell and J. A. Tropp in 2008 on arXiv [6](https://doi.org/10.48550/arxiv.0803.2392), and the K-SVD dictionary learning algorithm was reported by M. Aharon, M. Elad, and A. Bruckstein in IEEE Transactions on Signal Processing in 2006.[7](https://doi.org/10.1109/tsp.2006.881199) The greedy selection idea itself is older than signal processing: in statistical modeling the same stepwise least-squares procedure is called forward stepwise regression and has been widely practiced since the 1960s.[11](https://elad.cs.technion.ac.il/wp-content/uploads/2018/02/23_Stability_IEEE_TIT.pdf)\n\n## Variants\n\nExtensions of the basic matching pursuit include Optimized Orthogonal Matching Pursuit, Gradient Pursuit, Complementary Matching Pursuit, and Orthogonal Complementary Matching Pursuit.[2](https://link.springer.com/article/10.1186/1687-6180-2011-34) CoSaMP's guarantee is stated in the same terms as the recovery conditions above: for a sampling matrix with restricted isometry constant \\( \\delta_{4s} \\leq c \\), it produces a \\( 2s \\)-sparse approximation \\( a \\) with \\( \\|x - a\\|_{2} \\leq C \\cdot \\max\\{\\eta, (1/\\sqrt{s})\\|x - x_{s}\\|_{1} + \\|e\\|_{2}\\} \\), where \\( x_{s} \\) is the best \\( s \\)-sparse approximation.[6](https://doi.org/10.48550/arxiv.0803.2392)\n\nWhen no analytic dictionary fits the data, the dictionary itself is learned from examples, a problem closely related to sparse coding. The K-SVD algorithm generalizes the [K-means clustering](https://www.edgepedia.org/k-means-clustering) process: it alternates between sparse coding of the examples under the current dictionary and updating dictionary atoms to better fit the data, updating each atom together with its sparse coefficients via a rank-1 (SVD) approximation, which accelerates convergence and makes it less demanding than the MOD method.[7](https://doi.org/10.1109/tsp.2006.881199) • [13](https://elad.cs.technion.ac.il/wp-content/uploads/2018/02/IEEE_Proc_Dictionary.pdf) K-SVD is flexible and can work with any pursuit method, including basis pursuit, FOCUSS, or matching pursuit [7](https://doi.org/10.1109/tsp.2006.881199), and batch Orthogonal Matching Pursuit provides an efficient implementation for training overcomplete dictionaries.[3](https://csaws.cs.technion.ac.il/~ronrubin/Publications/KSVD-OMP-v2.pdf)\n\n## Applications\n\n[Sparse decomposition](https://www.edgepedia.org/sparse-decomposition-signal-processing) and models are used in speech and audio compression, denoising, source separation, and automatic indexing.[2](https://link.springer.com/article/10.1186/1687-6180-2011-34) With a Gabor dictionary, matching pursuit defines an adaptive time-frequency transform whose energy distribution avoids the interference terms of Wigner and Cohen class distributions.[10](https://doi.org/10.1109/78.258082) OMP is also commonly used in compressive sensing to recover sparse or nearly-sparse signals from compressive measurements, and one of its attractive features is its simplicity.[4](https://ar5iv.labs.arxiv.org/html/0909.0083)\n\n## Limitations and alternatives\n\nThe optimal expansion of a signal in a redundant dictionary is an NP-hard problem, which is what motivates greedy matching pursuit algorithms that compute a suboptimal expansion.[14](https://geoffdavis.net/papers/spie.pdf) Solving the \\( \\ell_{0} \\) problem exactly requires a subset search whose complexity grows exponentially with the dictionary size \\( L \\).[1](https://pmc.ncbi.nlm.nih.gov/articles/PMC153464/) Matching pursuit itself is known not to provide sparse approximations in general, with published counterexamples; in Chen's empirical test, basis pursuit recovered exactly the indexes and coefficients of a sum of four sinusoids and two spikes in a combined time-frequency dictionary across a wide range of amplitude ratios, whereas matching pursuit recovery became very inexact when the sinusoid and spike components were at very different amplitudes.[8](http://www.rctn.org/w/images/6/6e/00959265.pdf) [Dictionary learning](https://www.edgepedia.org/dictionary-learning) is also NP-hard.[15](https://arxiv.org/abs/1405.6664) K-SVD and MOD suffer from high non-convexity and can get caught in local minima or even saddle points; the trained dictionaries are unstructured and relatively costly to apply, so they suit mainly small signal patches.[13](https://elad.cs.technion.ac.il/wp-content/uploads/2018/02/IEEE_Proc_Dictionary.pdf)\n\n## References\n\n1. [Optimally sparse representation in general (nonorthogonal) dictionaries via l1 minimization (PNAS, Donoho & Elad)](https://pmc.ncbi.nlm.nih.gov/articles/PMC153464/)\n2. [Greedy sparse decompositions: a comparative study (EURASIP Journal on Advances in Signal Processing)](https://link.springer.com/article/10.1186/1687-6180-2011-34)\n3. [Efficient Implementation of the K-SVD Algorithm using Batch Orthogonal Matching Pursuit (Rubinstein, Zibulevsky & Elad)](https://csaws.cs.technion.ac.il/~ronrubin/Publications/KSVD-OMP-v2.pdf)\n4. [Analysis of Orthogonal Matching Pursuit using the Restricted Isometry Property (Davenport & Wakin)](https://ar5iv.labs.arxiv.org/html/0909.0083)\n5. [Scott Shaobing Chen, David L. Donoho, Michael A. Saunders (1998). Atomic Decomposition by Basis Pursuit. SIAM Journal on Scientific Computing.](https://doi.org/10.1137/s1064827596304010)\n6. [Needell, D., Tropp, J. A. (2008). CoSaMP: Iterative signal recovery from incomplete and inaccurate samples. arXiv (Cornell University).](https://doi.org/10.48550/arxiv.0803.2392)\n7. [M. Aharon, M. Elad, A. Bruckstein (2006). $rm K$-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation. IEEE Transactions on Signal Processing.](https://doi.org/10.1109/tsp.2006.881199)\n8. [Uncertainty principles and ideal atomic decomposition (IEEE Transactions on Information Theory; Tropp)](http://www.rctn.org/w/images/6/6e/00959265.pdf)\n9. [Greed is good: algorithmic results for sparse approximation (IEEE Trans. Information Theory, 2004, Tropp)](https://dl.acm.org/doi/10.1109/TIT.2004.834793)\n10. [S.G. Mallat, Zhifeng Zhang (1993). Matching pursuits with time-frequency dictionaries. IEEE Transactions on Signal Processing.](https://doi.org/10.1109/78.258082)\n11. [Stable Recovery of Sparse Overcomplete Representations (IEEE Trans. Information Theory)](https://elad.cs.technion.ac.il/wp-content/uploads/2018/02/23_Stability_IEEE_TIT.pdf)\n12. [Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition (Asilomar 1993)](https://www.khoury.northeastern.edu/home/eelhami/courses/EE290A/OMP_Krishnaprasad.pdf)\n13. [Dictionaries for Sparse Representation Modeling (Proceedings of the IEEE, Elad)](https://elad.cs.technion.ac.il/wp-content/uploads/2018/02/IEEE_Proc_Dictionary.pdf)\n14. [Adaptive greedy approximations (SPIE paper, Davis et al.)](https://geoffdavis.net/papers/spie.pdf)\n15. [On the Computational Intractability of Exact and Approximate Dictionary Learning](https://arxiv.org/abs/1405.6664)\n\n---\n*Topic: Encyclopedia › Technology and the built world › Computing and digital systems › Artificial intelligence and data › Algorithms and computational methods › Numerical, string, and geometric algorithms › Fourier and signal transforms*\n\n*Initially written Sep 29, 2026 · Reviewed: Sep 30, 2026 · Edited: Oct 15, 2026 · Last review: Sep 30, 2026*\n\n*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*\n\nLicense: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license\n", "same_as": [], "url": "https://www.edgepedia.org/atomic-decomposition", "markdown_url": "https://www.edgepedia.org/atomic-decomposition.md", "license": { "name": "Edgepedia Community License 1.0", "url": "https://www.edgepedia.org/edgepedia/license", "summary": "Free with credit, commercial use included. AI training is open to everyone. For other uses, organizations over USD 100M in revenue or 100M monthly users license separately.", "spdx": "LicenseRef-Edgepedia-Community-1.0" }, "credit": "\"Atomic decomposition\", Edgepedia (EdgeChat), https://www.edgepedia.org/atomic-decomposition. Edgepedia Community License 1.0.", "credit_md": "\"[Atomic decomposition](https://www.edgepedia.org/atomic-decomposition)\", Edgepedia (EdgeChat), [https://www.edgepedia.org/atomic-decomposition](https://www.edgepedia.org/atomic-decomposition). [Edgepedia Community License 1.0](https://www.edgepedia.org/edgepedia/license).", "credit_html": "\"Atomic decomposition\", Edgepedia (EdgeChat), https://www.edgepedia.org/atomic-decomposition. Edgepedia Community License 1.0.", "speakable": "Atomic decomposition is a signal processing method that represents a signal as a sparse linear combination of elementary waveforms, called atoms, drawn from a redundant dictionary." }