## 3 Compressive Sensing
### Compressive Sensing Fundamentals  
Compressive sensing includes three parts:  
* Sparsity: Let \(\mathbf{x}=[x_{1},...,x_{n}]^{T}\) represent the \(N\)-dimension original signal and \(\mathbf{\Psi}=[\psi_{1},...,\psi_{N}]\) be an orthogonal basis (dictionary), such that: \[\mathbf{x}=\sum_{i=1}^{N}\alpha_{i}\psi_{i}= \mathbf{\Psi}\alpha\] (1) where \(\alpha=[\alpha_{\mathbf{1}},...,\alpha_{\mathbf{N}}]^{\mathbf{T}}\) is the vector that represent \(\mathbf{x}\) on the basis \(\mathbf{\Psi}\). The signal is sparse if most of the elements of \(\alpha\) are zero or they can be discarded without much loss of information. Specifically, if there are \(K(K\ll N)\) nonzero coefficients in \(\alpha\), the signal can be regarded as being \(K\)-sparse. In fact, sparse signals are rather ubiquitous, such as acoustic signal, temperature, the density of carbon dioxide and images, which allows compressive sensing to be applied in many far-reaching applications in WSNs [23]. * Incoherent measurement: For any \(N\)-dimensional signal \(\mathbf{x}\), its measurement \(\mathbf{y}\) is taken as follows: \[\mathbf{y}=\mathbf{\Phi}\mathbf{x}=\mathbf{\Phi}\mathbf{\Psi}\alpha=\mathbf{A}\alpha\] (2) where \(\mathbf{y}\in\mathbf{R}^{\mathbf{M}}\) is the \(M\)-dimensional linear measurement data, \(\mathbf{\Phi}=[\phi_{1},...,\phi_{\mathbf{M}}]^{\mathbf{T}}\) is the \(M\times N\) projection matrix and \(\mathbf{A}=\mathbf{\Phi}\mathbf{\Psi}\) is the equivalent matrix. Compressive sensing theory requires the projection matrix \(\mathbf{\Phi}\) and the sparse dictionary to be as incoherent as possible, such that the samples add new information that is not already represented by the known basis \(\mathbf{\Psi}\). It has been proven [24] that \(\mathbf{\Phi}\) with i.i.d. Gaussian entries with zero mean and variance \(\frac{1}{M}\) or binary matrices with independent entries taking values \(\pm\frac{1}{\sqrt{M}}\) are largely incoherent with any fixed sparse dictionary \(\mathbf{\Psi}\) with overwhelming probability as long as the measurement number conforms to the following condition, holding for some constant \(c\): \[M\geq cK\log(N/K)\] (3)
* Reconstruction algorithms: \(K\)-sparse \(\mathbf{x}\) can be reconstructed by solving the \(l_{0}\) norm [10] from \(\mathbf{y}\) as follows: \[\min||\mathbf{x}||_{\mathbf{0}}\quad\mathbf{s.t.}\quad\mathbf{\Phi}\mathbf{ \Psi}\mathbf{x}=\mathbf{y}\] (4) This optimization problem relies on an exhaustive search and is successful for all \(x\in\sum_{K}\) when the matrix \(\mathbf{\Phi}\) has the sparse solution uniqueness property. However, this algorithm hascombinatorial computational complexity [25]. An alternative to the above \(l_{0}\) norm optimization is to use the \(l_{1}\) norm. \(l_{1}\) norm optimization is convex, which can be solved by using linear programming, and the global optimal solutions can be achieved. An alternative to optimization-based approaches is greedy algorithms for sparse signal recovery. These methods are iterative in nature and select columns of \(\mathbf{\Phi}\) according to their correlation with the measurements \(\mathbf{y}\) determined by an appropriate inner product. A typical example is orthogonal matching pursuit algorithms (OMP), which we use in our framework due to the low complexity. Still, the computational complexity of this solution is greater than that of traditional decoding and data interpolation, but CS shifts this burden to the base station, which we assume to have a significantly higher energy budget than the ordinary sensor nodes.