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?

  • $\begingroup$ Could you give a rough idea of your goals for basis set $A$: speed, memory, running code vs. theory ? For classification or compression ? For still or moving images ? $\endgroup$ – denis Jan 12 '14 at 11:42

The textbook algorithm is to minimize


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


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


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.

  • $\begingroup$ That's great to know! Thank you for answering. All this seems theoretical. How would I compute A practically? And would you mind pointing me to a standard textbook where I might learn this better (not my field). $\endgroup$ – val Jan 6 '14 at 17:34
  • $\begingroup$ Actually, I do not know if there already are standard textbooks on compressive sensing. But any research article should contain this formulation. Names to look for for good surveys are the wavelet people, Daubechies, Mallat, Dahmen, Strang. $\endgroup$ – Lutz Lehmann Jan 6 '14 at 17:38
  • $\begingroup$ OK - I will look for the wavelet people. I didn't know that getting A was so difficult! Thank you. $\endgroup$ – val Jan 6 '14 at 17:40
  • 1
    $\begingroup$ There is a book by Dahmen, DeVore and two others called "Compressed sensing and electron microscopy", and from the TU-Berlin an Introduction to compressed sensing. And see (dsp.rice.edu/cs). $\endgroup$ – Lutz Lehmann Jan 6 '14 at 17:46
  • 1
    $\begingroup$ Because I answered on the question of finding the coefficients $x$, not the basis $A$. As an ad-hoc idea, You could start with an SVD of your sample set to exhibit any linear dependence and then use chunks of the singular vectors for the largest singular values, zeroing out small coefficients, to initialize the search for the basis matrix $A$. If the system generating the samples is time invariant or periodic, enlarge the sample set by shifts of the samples. $\endgroup$ – Lutz Lehmann Jan 6 '14 at 19:23

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.

  • $\begingroup$ thanks for the references. I've seen stuff by Candes and Wakin on CS but not the other ones you mentioned. I'm coming at it "backwards" because I have the samples and I also have the full dataset. From that set up I am trying to understand how I get the "sampling" basis and/or the representation basis of my signal. I can't control the sampling since it's already been done for me. As for a representation basis, this part I'm confused about, I don't understand if I chose the basis or if there is some "native" basis that best suits my signal (forgive my naive terminology/understanding) $\endgroup$ – val Jan 6 '14 at 18:23
  • $\begingroup$ Ad sampling: You can resample by interpolating. Ad dataset: if you have a specific dataset in mind, then a learning algorithm is likely effective, and then it's not typically necessary to choose a basis, you just start with a random one. $\endgroup$ – drizzd Jan 6 '14 at 18:30
  • 1
    $\begingroup$ In most articles on CS the basis has been pre-selected by the author. So you can use complex exponentials if you are interested in frequencies. For images you could use DCT basis vectors. Your question is like asking what is the best wavelet to use for image compression - there isn't one particular answer. It helps if you have some knowledge of what it is you're trying to find. CS techniques will work as long as the signal is sparse in the particular basis you choose/find. $\endgroup$ – David Jan 6 '14 at 18:44
  • $\begingroup$ @David Thanks for your comments. "It helps if you have some knowledge of what it is you're trying to find". I want to go here: a measure of incoherence bit.ly/19NeRpH. As you say, normally people will chose a sampling basis and a representation basis and then check that these two are maximally incoherent to minimize the number of samples required for signal reconstruction. In my case, the sampling of the image has already been done and I'm not allowed to resample the true image. I thought "sampling pattern" dictated the "sampling basis".Am I still free to define the sampling basis here? $\endgroup$ – val Jan 6 '14 at 19:37
  • $\begingroup$ Actually, I think the common approach is to randomize the sampling - that way it is very likely to have an incoherence with the representation basis (whatever that may be). In your case, the sampling is already done so all you can do is choose the representation basis. You want to try to choose it so the support is sparse - otherwise using the $L_1$ or $L_0$ norm won't give you anything useful. If you try to maximize the incoherence, but the representation is not sparse - then you haven't really gained anything. $\endgroup$ – David Jan 7 '14 at 18:05

Your Answer

