[latexpage]
 |
In image compression applications, we are given the pixel representation of a “target” image, as a vector in \(y \in \mathbb{R}^m\). We would like to represent the image as a linear combination of “basic” images \(a_j\), \(j=1,\ldots,n\), where the matrix \(A=[a_1,\ldots,a_n] \in \mathbb{R}^{m \times n}\) is called the dictionary. The picture on the left shows a total of \(n\) “basic” images. |
To represent the image in terms of the dictionary, we would like to find coefficients \(x_j\), \(j=1,\ldots,n\) such that
\[y = \sum_{j=1}^{n} x_j a_j,\]
or, more compactly, \(y = Ax\).
If the representation of the image (that is, the vector \(x\)) has many zeros (we say: \(x\) is sparse), then we can represent the entire image with only a few values (the components of \(x\) that are not zero). We may then, for example, send the image over a communication network at high speed. Provided the receiver has the dictionary handy, it can reconstruct perfectly the image.
In practice, it may be desirable to trade off the sparsity of the representation (via \(x\)) against the accuracy of the representation. Namely, we may prefer a representation \(x\) that achieves \(Ax = y\) only approximately, but has way more zeros. The process of searching for a good sparsity/accuracy trade-off is called image compression.
