# Evaluation of the Use of Compressed Sensing in Data Harvesting for Vehicular Sensor Networks
## 2 Background  
The Compressed Sensing technology was proposed by [PERSON] and [PERSON] among others [1; 2; 3] as an alternative to the traditional sampling methods following the Nyquist-Shannon theorem. Later on, [PERSON] and [PERSON] [4] presented a straightforward introduction to the CS technology. In this paper, the authors motivate the use of this technology, also describing its primary purpose, capturing the salient information of a particular signal of interest efficiently. Traditional sampling methods require to sample a signal at least at a frequency of twice the signal bandwidth (Nyquist-Shannon sampling theorem). However, the argument posed by CS is that regarding signal information, all the elements of the signal are not always significant. For instance, if we ask somebody for a random number, it will give it in base 10 by default. For instance, 11, this base is called in signal context the acquisition basis or sensing basis, but we can change its representation using a different base like hexadecimal, obtaining a different value, \(b\). Therefore, we have selected the hexadecimal basis as its representation basis. Although we have two different values, 11 and \(b\), both of them correspond to the same number; however, \(b\) has only one digit while 11 has two of them. The same happens to the signal representation. We can obtain a signal corresponding to an image whose components are the pixels and their colors, or we can use a different basis to represent it, lowering the amount of information. For instance, Figure 1 presents a wavelet transform of an image where the black pixels of the wavelet transform do not contain information. This basis uses, therefore, fewer data to represent and store the image compared with the traditional pixel and color representation. Its advantage is that we can recover the original image in the case is needed without hardly losing accuracy. CS asserts it is possible to recover specific signals from far fewer samples than traditional methods use. In order to do it, CS relies on two principles: sparsity and incoherence:  
* A signal is sparse when the information rate is less than the signal bandwidth [1,2], i.e., only a few of the signal components are relevant, being the majority of them dispensable. For instance, if the majority of the signal components have the same values, and only a few of them have a different one, as we illustrated in the wavelet transform of the image in Figure 1. Transmitting only the relevant components in a compressed way makes it possible to reconstruct the original signal by the receiver while saving network resources. * Incoherence, on the other hand, measures the correlation between the representation, also called sparsifying basis, and the measurement one. Thus if a signal is sensed using a basis \(\Phi\) while for its representation, it is used another basis \(\Psi\). The less correlation between the elements of both bases, the more incoherence both bases will have. Samples must also be incoherent. Taking two samples, the more correlated they are, the less information will be provided in global terms because we receive two times the same value. Fulfilling the above principles of sparsity and incoherence, CS states that an original signal \(x\) of dimension \(n\) can be compressed by selecting \(k\) random measurements, \(k<<n\), in the following way:  
\[ \begin{pmatrix}y_{1}\\ y_{2}\\...\\ y_{k}\end{pmatrix} = \begin{pmatrix}a_{11}a_{12}...a_{1n}\\ a_{21}a_{22}...a_{2n}\\...\\ a_{k1}a_{k2}...a_{kn}\end{pmatrix} * \begin{pmatrix}x_{1}\\ x_{2}\\...\\ x_{k}\\...\\ x_{n}\end{pmatrix} \Rightarrow \tag{1}\] \[\Rightarrow y= \begin{pmatrix}a_{1}\\ a_{2}\\...\\ a_{k}\end{pmatrix} x\Rightarrow y=Ax,\]  
Figure 1: An image as example of a signal represented in traditional and wavelet basis. where \(y\) is the resulting compressed vector, \(A\) is the representation basis where the signal must be sparse, and \(x\) is the original signal also expressed as a vector.