Image compression via least-squares
We can use least-squares to represent an image in terms of a linear combination of ‘‘basic’’ images, at least approximately.
An image can be represented, via its pixel values or some other mechanism, as a (usually long) vector 
. Now assume that we have a library of 
‘‘basic’’ images, also in pixel form, that are represented as vectors 
. Each vector 
could contain the pixel representation of a unit vector on some basis, such as a two-dimensional Fourier basis; however, we do not necessarily assume here that the ‘s form a basis.
Let us try to find the best coefficients 
, which allow approximating the given image (given by ) as a linear combination of the ‘s with coefficients 
. Such a combination can be expressed as the matrix-vector product 
, where ![A=\left[a_1, \ldots, a_n\right]](https://pressbooks.pub/app/uploads/quicklatex/quicklatex.com-85063cf6b2a138d9eac87d4d665d3190_l3.png "Rendered by QuickLaTeX.com")
is the 
matrix that contains the basic images. The best fit can be found via the least-squares problem
![\[\min _x\|A x-y\|_2\]](https://pressbooks.pub/app/uploads/quicklatex/quicklatex.com-f445eb139d8919dd47278d7531bc7be5_l3.png "Rendered by QuickLaTeX.com")
Once the representation is found, and if the optimal value of the problem above is small, we can safely represent the given image via the vector 
. If the vector is sparse, in the sense that it has many zeros, such a representation can yield a substantial saving in memory, over the initial pixel representation 
.
The sparsity of the solution of the problem above for a range of possible images is highly dependent on the images’ characteristics, as well as on the collection of basic images contained in 
. In practice, it is desirable to trade-off the accuracy measure above, against some measure of the sparsity of the optimal vector .
