# LESS: Link Estimation with Sparse Sampling in Intertidal WSNs
## 4 Utilization of Compressive Sensing
### Design of the Matrices
As shown in Figure 6a,  
Figure 5: The reconstruction accuracy of link quality matrix with compressive sensing in \(\Phi_{R}\) with variant \(\mathbb{F}\)s: identity matrix (\(\mathbb{F}_{I}\)), Fourier transform matrix (\(\mathbb{F}_{F}\)), and discrete cosine transform matrix (\(\mathbb{F}_{D}\)). (George Town data)  
the estimation accuracy for a given sampling rate spans a wide range. Moreover, using a higher sampling rate may not necessarily yield a higher accuracy (e.g., the minimum value with \(SR=0.9\) is even lower than the average value under \(SR=0.6\)). Further, we plot the CDF of the accuracy for variant sampling rates in Figure 5(b) and find that they are evenly distributed. For example, the cumulation of the accuracy increases approximately linearly between 73.4% to 76.4% when the sampling rate is 0.5. This result indicates that estimation errors also distribute evenly. We look into the underlying reason and find there are a few \"key nodes\" that play critical roles. The errors in random measurements mainly come from the absence of measurements of the \"key nodes\". **\"Key nodes\" are defined as those nodes who has little redundant information**, i.e., the information of those nodes shall be used as much as possible. Table 1 proves the above conjecture. It is clear that under the same sampling rate (\(SR=0.33\)), error decreases with the increase of available information from one \"key node\". Specifically, the error is 61.8% when the key node is not used and it is only 22.5% if all the information from the node is used. However, how to decide which node is a \"key node\" among all the nodes is not that easy. In general, a node with less redundant information is more likely to be a \"key node\". The choices of \"key nodes\" give rise to the importance of \(\Phi\), i.e., the scheduling algorithms. A good scheduling algorithm should have more information from the \"key nodes\" to make the recovery accurate. We introduce the scheduling algorithms which realize \(\Phi\) in Section 5.2. **The Regulation Term Design. ** From Equation (6), we can see that the performance of compressive sensing technique degrades when data is not sufficiently sparse or the measurement error is large, which are common in real-world data. Therefore, in addition to the low-rank property used by compressive sensing, we introduce and utilize additional data structures to improve the accuracy. Specifically, we consider the spatial and temporal stability in the data and add additional regularization terms to Equation (5):  
\[\underset{\theta}{argmin}\|y-\Phi\Psi\theta\|_{2}^{2}+\lambda\|\theta\|_{1}+ \beta\|P\theta\|_{F}^{2} \tag{7}\] \begin{table}
\begin{tabular}{l c c c c c} \hline \hline
**Key Node Info.** & **0\%** & **25\%** & **50\%** & **75\%** & **100\%** \\ \hline Average Error & 61.8\% & 49.5\% & 46.1\% & 28.6\% & 22.5\% \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Errors vs. key node information percentage (\(SR=0.33\)). Figure 6: Errors introduced without differentiating the nodes (George Town data). where \(\|\cdot\|_{F}\) is the Frobenius norm and \(P\) is an \(N\times N\) matrix to capture the temporal stability in \(\theta\). An intuitive choice for \(P\) is the Toeplitz matrix [54] with central diagonal given by ones, and the first upper diagonal given by negative ones, i.e.,  
\[P= \begin{bmatrix}1&-1&0&\dots\\ 0&1&-1&\ddots\\ 0&0&1&\ddots\\ \vdots&\ddots&\ddots&\ddots\end{bmatrix} \]  
A more sophisticated \(P\) can be designed based on the system-specific knowledge \(\mathbf{K}\) (which will be precisely defined in Section 5) to the data. For example, in our application, the tide introduces periodic patterns so the link quality \(X(i,t)\) is not only correlated with the last measurement result \(X(i,t-1)\) but also with \(X(i,t-\tau)\), which is the value in the last tide cycle (\(\tau\) is the tide cycle). Therefore, we can design \(P\) as:  
\[P=