# Compressed Sensing and Sparsity

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?

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.