# LESS: Link Estimation with Sparse Sampling in Intertidal WSNs
## 4 Utilization of Compressive Sensing
### Design of the Matrices  
We have described the prime of the compressive sensing technology for one-dimensional signals. It can be extended for a two-dimensional matrix and uses \(\Psi\) to transform it to a low-rank matrix [44; 49; 50]. The challenges in our scenario are mainly as follows:  
Figure 4: (**a**) Original data matrix (Avg. error \(=0\)); (**b**) processed by standard toolbox in Matlab (Avg. error \(=20.69\)); and (**c**) processed by LESS (Avg. error \(=4.89\)). Heat map for the original (**a**); and recovered (**b,c**) data matrices. Larger error is introduced by standard CS than LESS does. (Sampling rate \(=0.5\), data from George Town system). * How to represent the collected data in a proper format to fit for CS. * What is the best transform matrix \(\Psi\) to make the data matrix sparse. * How to further improve the reconstruction accuracy beyond compressive sensing by taking into account the additional data structure the systems share. Recall that, in Section 3.2, we mentioned the original data show low-rank but noisy property. Directly using standard CS leads to a larger error, i.e., an absolute error of 20.69 in average, as is shown in Figure 4b, when compared with the original data in Figure 4a. To decrease the errors, we refine the design of the above-mentioned matrices by incorporating the spatial, temporal and system-specific data structures. In Figure 4c, we achieve an absolute error of 4.89 in average, which leads to nearly 90% accuracy (see Section 7 for details). In the following, we elaborate the design of the CS matrices. **Data Matrix \(X\):** In a sensor network with \(N\) nodes, we represent the link quality between nodes over time as a matrix \(X:X\in\mathbb{R}^{N^{2}\times T}\), where each element \(X(i,t)\) represents the link quality of the \(i\)-th link at the \(t\)-th time cycle. **Low-Rank Transform Matrix \(\mathbb{Y}\):** As we mentioned above, to make \(X\) a proper low-rank basis, transformations shall be conducted. Generally, the transform matrix \(\Psi\) could be Fourier transform, discrete cosine transform, and etc [51; 52]. The best \(\Psi\) varies for different data matrix \(X\). To choose the best transform matrix, we compare three most frequently used transform matrices which are identity matrix (\(\mathbb{F}_{I}\)), Fourier transform matrix (\(\mathbb{F}_{F}\)), and discrete cosine transform matrix (\(\mathbb{F}_{D}\)) in Figure 5. We use a 10-h long data trace collected in George Town system, and reconstruct the link quality matrix with different transform matrices (\(\mathbb{F}_{I}\), \(\mathbb{F}_{F}\), \(and\mathbb{F}_{D}\)) above with the same measurement matrix: random measurement matrix (\(\Phi_{R}\)). We calculate the reconstruction accuracy by comparing the reconstructed matrix and the original data matrix, and the result in Figure 5 reveals the discrete cosine transform matrix (\(\mathbb{F}_{D}\)) has better performance than the other two transform matrices for each sampling rate. Therefore, we set \(\Psi\) to the discrete cosine transform matrix (\(\mathbb{F}_{D}\)) in our design. **Measurement Matrix \(\Phi\):** There are different strategies to conduct measurement in real-world as shown in Section 5.2. Candes [53] shows that one can stably reconstruct \(x\) from Equation (5) and the estimated signal \(\hat{x}\) obeys:  
\[||\hat{x}-x||_{2}\leq C_{0}k^{-1/2}||x-x_{k}||_{1}+C_{1}\epsilon \tag{6}\]  
where \(x_{k}\) is the vector \(x\) with all but the \(k\)-largest entries set to zero, \(C_{0}\) and \(C_{1}\) are constants, and \(\epsilon\) is the upper bound on the size of the noise \(z\). Equation (6) shows that one may observe various magnitude of estimation error when the measurement is noisy. In Figure 6, we investigate the errors using a random measurement strategy and see the errors in it with the George Town dataset. The results are based on 500 rounds.