# Overview of Compressed Sensing: Sensing Model, Reconstruction Algorithm, and Its Applications
## 2 Sensing Methods
### Block-Compressed Sensing  
Block-compressed sensing (BCS) completes data acquisition and compression by lightweight measurement. When dealing with high-dimensional images and videos, BCS is the most appropriate approach and it can utilize its biggest advantage. This method divides the image into many small patches, and operates on each image patch separately during measurement and reconstruction, which reduces computational complexity and greatly saves sensing-matrix storage space. In BCS, the measurement matrix is small, which is conducive to storage. The measurement value of each image patch can be independently sent after being obtained. The receiver can also independently reconstruct the image patch according to the data, and realize real-time performance. Consider an \(I_{r}\times I_{c}\) image with a total of \(N=I_{r}I_{c}\) pixels. We divided the image into sub-blocks with a size of \(B\times B\), and sampled with the same sensing matrix. The vectorized signal of the \(i\)-th block is denoted as \(x_{i}\). Corresponding output CS vector \(y_{i}\) is  
\[y_{i}=\Phi_{B}x_{i}, \tag{9}\]  
where \(\Phi_{B}\) is an \(n_{B}\times B^{2}\) matrix and \(n_{B}=\left\lfloor\frac{nB^{2}}{N}\right\rfloor\). \(\Phi_{B}\) can be an orthonormalized random matrix, i.e., Gaussian and Bernoulli matrices. Then, measurement matrix \(\Phi\) in Equation (1) can be represented as follows:  
\[\Phi=\left(\begin{array}{ccc}\Phi_{B}&&\\ &\ddots&\\ &&\Phi_{B}\end{array}\right), \tag{10}\]  
where \(\Phi\) is a block diagonal matrix. From Equation (10), we can see that BCS is storage-saving, as it just requires to store an \(n_{B}\times B^{2}\) matrix \(\Phi_{B}\) rather than an \(n\times N\) matrix.  
Computational complexity and recovery performance are highlighted at both encoder and decoder. To solve the two problems above, [PERSON] et al. introduced and investigated the BCS strategy with matrix permutation that was used before sampling to reduce the maximal level of signal block sparseness [12]. The matrix-permutation procedure was as follows:  
1. Reshape 2D signal \(X\in R^{\sqrt{N}\times\sqrt{N}}\) to a new 2D signal \(X^{\dagger}=[X_{1},X_{2},\cdots,X_{L}]\in R^{\sqrt{n}\sqrt{NL}}\).
2. We used an appropriate permutation matrix \(P\in R^{\sqrt{NL}\times\sqrt{NL}}\) to process \(X^{\ddagger}\), and the process procedure was as follows: \[X^{\ell}=X^{\ddagger}P,\] (11) where \(X^{\ell}\in R^{\sqrt{n}\times\sqrt{NL}}\) is the permutated 2D sparse signal.  
After the matrix-permutation procedure, the block-sampling process can be performed as follows:  
\[y^{\ell}=\Phi_{B}x_{i}^{\ell}, \tag{12}\]  
where \(x_{i}^{\ell}\in R^{n}\) represents the vectorized signal of the \(i\)-th block of \(X^{\ell}\), and \(y_{i}^{\ell}\in R^{m}\) is the measurement vector of \(x_{i}^{\ell}\). Compared with traditional BCS approaches, the matrix-permutation-based BCS method has an advantage in the peak signal-to-noise ratio (PSNR) of the recovery images.  
On the basis of BCS, [PERSON] et al. presented a random-sampling approach that projected the signal onto blocks of measurement vectors [13]. There is a typical example when the block consists of horizontal lines in the two-dimensional Fourier plane. They theoretically proved the number of blocks that could be used to accurately reconstruct sparse signals. The matrices, constructed by stacking random measurement blocks, are significant in the application because they can be easily formed on many imaging devices.  
Traditional BCS methods rely on independent block image acquisition and independent block reconstruction. In order to enforce smoothness across block borders in BCS, [PERSON] et al. proposed a method that used partially overlapping blocks to modify the sensing and reconstruction process [14]. They computed a fast preview from the blocks, which imposed the similarity of block borders and was used as a predictor of the entire block.