## 2 Compressed Sensing  
[PERSON]'s sampling theorem stipulates that a signal should be sampled at a rate higher than twice the bandwidth of the signal for a successful recovery. For high bandwidth signals, such as image and video, the required sampling rate becomes very high. Fortunately, only a relatively small number of the discrete cosine transform (DCT) or wavelet transform (WT) coefficients of these signals have significant magnitudes. Therefore, coefficients with small magnitudes can be discarded without affecting the quality of the reconstructed signal significantly. This is the basic idea exploited by all existing lossy signal compression techniques. The idea of CS is to acquire (sense) these significant information directly without first sampling the signal in the traditional sense. It has been shown that if the signal is \"sparse\" or compressible, then the acquired information is sufficient to reconstruct the original signal with a high probability [5,6]. Sparsity is defined with respect to an appropriate basis, such as DCT or WT, for that signal. The theory also stipulates that the CS measurements of the signal must be acquired through a process that is incoherent with the signal. Incoherence makes certain that the information acquired is randomly spread out in the basis concerned. In CS, the ability of a sensing technique to effectively retain the features of the underlying signal is very important. The sensing strategy should provide a sufficient number of CS measurements in a non-adaptive manner that enables near perfect reconstruction. Let \(\mathbf{f}=\{f_{1},\ldots,f_{N}\}\) be \(N\) real-valued samples of a signal, which can be represented by the transform coefficients, \(\mathbf{x}\). That is,  
\[\mathbf{f}=\Psi\mathbf{x}=\sum_{i=1}^{N}x_{i}\psi_{i} \tag{1}\]  
where \(\Psi=\left[\psi_{1},\psi_{2}\ldots\psi_{N}\right]\) is the transform basis matrix and \(\mathbf{x}=\left[x_{1},\ldots,x_{N}\right]\) is an \(N\)-vector of coefficients with \(x_{i}=<\mathbf{x},\psi_{i}>\). We assume that \(x\) is \(S\)-sparse, meaning that there are only \(S<<N\) significant elements in \(x\). Suppose a general linear measurement process computes \(M<N\) inner products between \(\mathbf{f}\) and a collection of vectors, \(\phi_{j}\), giving \(y_{j}=\left\langle\mathbf{f},\phi_{j}\right\rangle,j=1,\ldots,M\). If \(\Phi\) denotes the \(M\times N\) matrix with \(\phi_{j}\) as row vectors, then the measurements \(\mathbf{y}=\left[y_{1},\ldots,y_{M}\right]\) is given by:  
\[\mathbf{y}=\Phi\mathbf{f}=\Phi\Psi\mathbf{x}=\Theta\mathbf{x} \tag{2}\]  
using Equation (1) with \(\Theta=\Phi\Psi\). These measurements are non-adaptive if the measurement matrix, \(\Phi\), is fixed and does not depend on the structure of the signal [13]. The minimum number of measurements needed to reconstruct the original signal depends on the matrices, \(\Phi\) and \(\Psi\). The reconstruction problem involves using \(\mathbf{y}\) to reconstruct the length-\(N\) signal, \(\mathbf{x}\), that is \(S\)-sparse, given \(\Phi\) and \(\Psi\). Since \(M<N\), this is an ill-conditioned problem. The conventional approach to solving ill-conditioned problems of this kind is to minimize the \(l_{2}\) norm. In this case, the optimization problem is given by:  
\[\hat{s}=argmin\left\|s^{\prime}\right\|_{2}\text{, such that }\Theta s^{ \prime}=y \tag{3}\]  
However, it has been proven that this \(l_{2}\) minimization can only produce a non-sparse \(\hat{s}\)[13]. The reason is that the \(l_{2}\) norm measures the energy of the signal, and signal sparsity properties could not be incorporated in this measure. The \(l_{0}\) norm counts the number of non-zero entries and, therefore, allows us to specify the sparsity requirement. The optimization problem using this norm can be stated as:  
\[\hat{s}=argmin\left\|s^{\prime}\right\|_{0}\text{, such that }\Theta s^{ \prime}=y \tag{4}\]  
There is a high probability of obtaining a solution using only \(M=S+1\) i.i.d.Gaussian measurements [14]. However, the solution produced is numerically unstable [13].