# Usage and origin of the terms dictionary and atom in compressed sensing

In compressed sensing two terms or perhaps fancy word are frequently encountered. One is the dictionary and the other is atom. The dictionary is the matrix and its columns are called "atoms" as explained below. Michael Elad's book on Sparse and Redundant Representations (pg. 172), justifies the terminology,

9.2 The Sparse-Land Model

Let us return to the linear system $$\mathbf{A x}=\mathbf{y}$$ and interpret it as a way of constructing signals $$\mathbf{y}$$. Every column in $$\mathbf{A}$$ is a possible signal in $$\mathbb{R}^n$$ - we refer to these $$m$$ columns as atomic signals, and the matrix A displays a dictionary of atoms. One can consider A as the periodic table of the fundamental elements in the "chemistry" that describes our signals.

The multiplication of $$\mathbf{A}$$ by a sparse vector $$\mathbf{x}$$ with $$\|\mathbf{x}\|_0^0=k_0 \ll n$$ produces a linear combination of $$k_0$$ atoms with varying portions, generating the signal $$\mathbf{y}$$. The vector $$\mathbf{x}$$ that generates $$\mathbf{y}$$ will be called its representation, since it describes which atoms and what "portions" thereof were used for its construction. This process of combining atoms linearly to form a signal (think of it as a molecule in the chemistry of our signals) may be referred to as atomic-composition.

Elsewhere,in a web article, Compressed sensing and dictionary learning by Guangliang Chen and Deanna Needell, another analogy is given.

Briefly speaking, a dictionary is a redundant system consisting of prototype signals that are used to express other signals. Due to the redundancy, for any given signal, there are many ways to represent it, but normally the sparsest representation is preferred for simplicity and easy interpretability. A good analog is the English language where the dictionary is the collection of all words (prototype signals) and sentences (signals) are short and concise combinations of words. Here we will introduce the problem of dictionary learning, its applications, and existing solutions.

1. Does anyone know who started called the matrix A, as a dictionary and its columns as "atoms". Semantically, dictionary and atoms do not have a direct connection.

In the unabridged Oxford English Dictionary, atom in mathematics had a different meaning from 1942.

Atom: Mathematics. In measure theory: a set, contained in a metric space, that has non-zero measure and with the property that any measurable subset has either equal measure or zero measure.

942: An element..is an atom if it contains no proper sub-elements. Annals of Mathematics vol. 43 334

Dictionary: Computing. A list stored in and used by a computer; spec. (a) A list of words recognized by an application such as a word processor, against which text or code can be checked; (b) a list of the contents of a database.

This goes back to 1952.

So how did atom and dictionary get attached to a matrix in compressed sensing? The "dictionary" is also called a sensing matrix in some places.

• This seems appropriate for HSMSE. Commented Jun 20 at 18:46
• HSMSE is good for generalized questions. MathOverflow does have a history tag and I have had good responses here before on terminologies, so a down vote or a closure suggestion seems excessive.
– ACR
Commented Jun 20 at 19:00
• A lot of authors also use compressive sensing along with compressed sensing.
– ACR
Commented Jun 22 at 4:34

## 1 Answer

The terms "dictionary" and "atoms" predate compressed sensing, they are more generally used in signal processing. An example is the Gabor atom for wavelets. For an early use of "dictionary" and "atom", see Matching pursuits with time-frequency dictionaries by Mallat and Zhang (1993).

This nomenclature borrowed from atomic physics goes further. The 1992 text book Wavelets and operators by Meyer speaks of "atomic decomposition" if the wavelets have a compact support, and "molecular decomposition" if they do not.

• Atomic decompositions for Hardy spaces go back to 1974 at least, see Coifman's paper eudml.org/doc/217919 (who attributes the observation to Fefferman as a dual version of the main results of the celebrated 1972 Fefferman-Stein paper projecteuclid.org/journals/acta-mathematica/volume-129/… ). Commented Jun 20 at 22:02
• Based on this and Coifman's foundational work on wavelets, I would hypothesize that Coifman was at least partially responsible for importing the terminology of atomic decomposition from real-variable harmonic analysis to applied harmonic analysis, from which it then migrated to other areas of signal processing including compressed sensing. Commented Jun 20 at 22:05
• Atomic decompositions describe a function in some function space (such as a Hardy space) as a linear combination of "atoms", where the $\ell^1$ norm of the coefficients of the combination are comparable to the norm of the original space (i.e., the norm is equivalent to the atomic norm induced by the family of atoms). This is pretty much the same concept that appears in the modern compressed sensing literature, e.g., arun.chagantys.org/assets/files/blog/atomic-norms.pdf Commented Jun 21 at 5:12
• The 2001 paper of Chen, Donoho and Saunders epubs.siam.org/doi/pdf/10.1137/… explicitly credits the Mallat-Zhang paper for introducing the "dictionary" and "atom" terminology to the field (see Section 2.1). Also, Mallat-Zhang cites some papers of Coifman, Meyer, and Wickerhauser, referring to their "wavelet wavepackets" (which we would now just call "wavelets") as "dictionaries of time-frequency atoms".- Commented Jun 21 at 5:50
• Finally, these wavelets also happen to essentially be Hardy space atoms (albeit with an L^2 normalization rather than an L^1 or L^p normalization) as in the sense of the 1974 Coifman paper: they are compactly supported, bounded by a suitable normalization factor, and have mean zero. See also the 1977 Coifman-Weiss paper projecteuclid.org/journals/… which also introduces the concept of a molecue (like atoms, but not compactly supported). Commented Jun 21 at 5:53