Compressed Sensing and Sparsity

Question

Ok for first information I would like to let you know that I originally do not have any formal exposure in signal processing so I would appreciate if you consider me as a beginner. In particular in this project I have to deal with the method of compressed sensing (CS). As some of you might know that CS relies on the sparsity of the signal in some basis.

• My first question is, when a reference mentions "wavelet" with no specification of which type of wavelet being referred to, what would be the type of wavelet which is common enough so that this reference doesn't mention it, if there is any?

Second, the main matrix equation in CS is $$ \begin{align} y &= \Phi \Psi s\\ \Updownarrow\\ y &= \Phi x,\quad x = \Psi s \end{align} $$ where $y$ the measured samples, $\Phi$ measurement matrix, $\Psi$ the representing basis matrix, and $s$ the expansion coefficients in $\{\Psi_i\}$ basis which we want to solve for. Ok up to this point I hope I haven't made any mistake in interpreting that equation.

• My question is how do people normally chose the basis? I think this choice of basis is critical because the expansion coefficients $s$ depends on the chosen basis.

• As we would want $s$ to be as sparse as possible, doesn't it also mean that we need to carefully choose the most favorable basis?

• If so, how would I decide the right choice? I read in some references they mostly use wavelets representation as the basis.

and by the way, the mathematical expression of the expansion in wavelets domain contains all possible indices of the bases (wavelets), that is the signal is the sum over both indices (dilation and translation indices) of the bases.

• How should I choose which pairs of indices I better put in the matrix $\Psi$, if for example the signal is $n$ elements long? In that case I obviously only need $n$ bases and the corresponding coefficients out of the infinite possibility.
• Can I randomly take any $n$ bases provided any two different bases are always orthogonal?

Answer 1

As far as choosing the right dictionary (basis) goes, there are several things to take into account. You do want your representation $s$ to be as sparse as possible and that depends a lot on the chosen dictionary. In practice, people are often looking at a particular type of signals $x$ which they know from domain knowledge to be sparse in some dictionary (discrete wavelet transform, discrete Fourier transform, etc.). However, you also need the dictionary $\Psi$ to "work well" together with the measurement matrix $\Phi$. This can be measured by their coherence (see e.g. Candès & Wakin, 2008). If you are free to choose $\Phi$ as you like, you can select the dictionary $\Psi$ that gives you the sparsest representation and then select $\Phi$ to be incoherent with $\Psi$. In practice $\Phi$ is often limited by hardware constraints and then you may have to select a suboptimal $\Psi$ with respect to sparsity in order to achieve incoherence with $\Phi$.

Another approach is dictionary learning where you can use (many) examples of the type of signal $x$ you are looking for to learn a dictionary $\Psi$, see for example Aharon, Elad, Bruckstein, 2006.

Answer 2

An easiest way I would recommend is (provided your data set is small or you are working frame by frame) just do transformation(wave let/Forier) and count the number of non zeros. Matlab does this by using the command nnz().

Answer 3

1. You don't know; but there are some basic properties: finite support, self similarity and completeness as you go to finer and finer partitions. These allow you to draw general conclusions. The particular type of kernel used depends upon your signal analysis goals and the signal.
2. Can't give you a quantitative answer but you might consider it as optimization problem; you want the partitions you use to validate the "signal" as well as possible while rejecting "noise"/interference as well as possible. Try to find out the statistics on these things and try running them through a wavelet processing simulator to see how the type1/type2 errors pan. In reality all you ever get likelyhood.

BTW: when doing the above selections make sure you include processing power/time in your evaluation.