Looking for a Basis representation: Given a sparse or compressible image M, how would one represent this image using a basis A?
If I let m = vec(M)
m = Ax
where A is my "representation" basis and x is the vector of coefficients in the A domain, what is the method for actually getting A?
The textbook algorithm is to minimize
$$\|Ax-m\|_1+\alpha\|x\|_0$$
where $\|x\|_0$ counts the number of non-zero coefficients. Since that is a bad function for the determination of a descent direction, one softens the counting norm to
$$\|x\|_ε=\sum_k|x_k|^ε$$
for some small value of $ε$. For instance, for $|x_k|>\exp(-\tfrac1{\sqrtε})$, which is a very small threshold, one gets $|x_k|^ε>\exp(-\sqrtε)\ge 1-\sqrtε$, so that all not too small and not too large values get mapped to $1$ and only really small values get mapped to zero.
To get a really smooth function, mostly for theoretical purposes, one can smoothen the kink at $0$ by using
$$\|x\|'_ε=\sum_k(\delta^2+|x_k|^2)^{ε/2}$$
and obviously choosing $δ$ small enough so that $x_k=0$ still gets mapped close to $0$, for instance by choosing $δ=\exp(-\tfrac1{\sqrtε^3})$.
Now that this answer is completely orthogonal to the question in its current form, I hope that someone else has more insight into the topic of matrix selection. What I know is this:
In the beginning, before compressed or compressive sensing existed as word, $A$ was a matrix of wavelet or wavelet-like coefficients. The whole idea of wavelet based compression (and JPEG) is to zero out small coefficients (and truncate the binary representation of non-null coefficients). This can be improved upon in one direction by observing and utilizing correlations in the detail coefficients over multiple scales, or in the other direction by making the basis vectors even more uncorrelated and thus reducing those fractal features.
There may also be algorithms that start with a random matrix and modify or reject it based on certain frame conditions.
The DCT is often used in practice, for example in the classical, non-wavelet, version of JPEG.
There are many algorithms to find the solution vector x, given a basis matrix A. But you are asking how to find the basis matrix A.
In many problems you can choose it. For example in a sparse frequency estimation problem, the columns of A correspond to samples from a particular complex exponential at a particular frequency.
There are also algorithms for handling the off-grid problem i.e. when the basis vector is slightly misaligned with your data. Most of the algorithms start with a hypothesized set of vectors and then use a gradient descent approach to modifying the basis vectors.
Another set of algorithms are referred to as Dictionary Learning algorithms. These algorithms tend to use a training database to find a good set of basis vectors.
I've found Michael Elad's book - Sparse and Redundant Representations quite good. It's not too mathematical - he also has a chapter on Dictionary Learning algorithms. There are also some tutorial like articles in the IEEE Signal Processing Magazine by Candes. There is also a very good chapter on compressive sensing in "Principles of Modern Radar - Advanced Techniques" by Melvin, Scheer which provides a good overview and a large number of reference papers.
