# An Overview on Deep Learning Techniques for Video Compressive Sensing
## 2 Compressive Sensing
### Mathematical Introduction  
To understand the mathematics behind the CS technique we recall here some basis principles: Instead of acquiring N samples of a signal \(x\in\mathbb{R}^{N\times 1}\), M random measures are acquired with \(M\ll N\) (CS theory states that the number of measurement sufficient to reconstruct the signal \(x\) is \(M=O(Klog(N/K))\) such that:  
\[y=\Phi x \tag{1}\]  
where \(y\in\mathbb{R}^{M\times 1}\) is the known compressed measurement vector and \(\Phi\in\mathbb{R}^{M\times N}\) is the sensing matrix that will be discussed in the next section. To recover the signal \(x\) given \(y\) and \(\Phi\), \(x\) must be sparse in a given base \(\Psi\):  
\[x=\Psi s \tag{2}\]  
where \(s\) is K-sparse which means that \(s\) has at most K non-zero elements. From (1) and (2):  
\[y=As \tag{3}\]  
where \(A=\Phi\Psi\). Figure 1 shows the compressed sensing framework.  
However, the reconstruction of \(x\) or \(s\) from \(y\) is not possible. Therefore, an approximate solution can be obtained by solving the following \(l_{1}\) minimization problem [3; 10]:  
\[\hat{s}=\text{argmin}||s||_{1}\text{ }s.t.\text{ }y=\Phi\Psi s \tag{4}\]  
To reconstruct s from \(y\), CS algorithms use different reconstruction approaches. Then \(x\) can be reconstructed from \(\hat{s}=\Psi\hat{s}\).  
Figure 1: Compressive sensing framework.  
Since there is only one measurement vector, the above problem is generally referred to as a Single Measurement Vector (SMV) problem in the compressive sensing. However, when the input becomes a 3D signal (video) instead of 1D signal, the SMV problem becomes a Multiple Measurement Vector (MMV) problem. The sparse vector \(s\) becomes in this case a set of vectors \(s_{i}\) which must be recovered jointly from a set of measurement vectors \(y_{i}\)[11].  
The set of the known measurement vectors \(y_{i}\) can correspond to different frames of the video signal. In fact, the video could be cut into series of images and then each image obtained could be associated to a measurement vector \(y_{i}\) and then it is possible to apply MMV model on the video. Therefore, the common approach used to deal with sequence data is Recurrent neural networks (RNN). However, RNN work well when we are dealing with short-term dependencies. In other words, these neural networks remember things for short periods of time and if a lot of information has been entered, it suffers from important losses. This problem could be solved by applying a modified version of the RNN: LSTM (Long Short Term Memory) [12]. The advantage of LSTM is that it avoids the problem of long term dependency i.e., it allows to remember information for a long period of time.  
As a result, and in agreement with CS properties, CS has a great potential to be applied to images and videos because of their huge spatial and temporal redundancies which allow to have sparse representations to enable their reconstruction.  
Nevertheless, RNNs are not the only Deep Learning approach experimented in video compressive sensing recovery phase. Indeed, many methods will be discussed in the following sections.