How would I represent an image using a basis $A$, given a sparse or compressible image?
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|&gt;\exp(-\tfrac1{\sqrtε})$, which is a very small threshold, one gets $|x_k|^ε&gt;\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.