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.
- 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.
