# Overview of Compressed Sensing: Sensing Model, Reconstruction Algorithm, and Its Applications
## 1 Introduction  
With the expansion of some traditional networks and the advent of the Internet of Things in recent years, network structures are more complex, and transmitted data in the networks are bigger, as is shown in Figure 1. The numbers of smart sensors and connected devices continue to grow in many practical network applications. This is a huge challenge for network communication, such as with regard to transmission efficiency and network security. Compressed sensing (CS) emerged, which is able to satisfy the needs of transmission efficiency and security at the same time. Compressed sensing is an advanced method of acquiring and processing signals, and it was first proposed by [PERSON] [1; 2]. It can accurately recover the original signal from a few incoherent measurements. In CS, fewer samples are required to reconstruct sparse or compressible signals, which breaks through the traditional Nyquist-Shannon sampling theorem. Suppose that \(x\) is a discrete signal, which is transformed into matrix \(y\) by a matrix \(\Phi\) with \(M\times N\) dimensions. The CS process can be expressed as  
\[y=\Phi x, \tag{1}\]where \(M<N\), \(y\in R^{M}\), and \(\Phi\) is the sensing or measurement matrix. From Equation (1), signal \(x\) with \(N\times N\)-dimension is compressed into signal \(y\) with \(M\times N\) dimensions. \(x\) is unsolvable by \(y\) from Equation (1) because the number of equations is less than that of the unknowns. The precondition of solvability for \(x\) is that \(x\) be sparse or that \(x\) be sparse on some orthogonal bases, that is,  
\[x=\Psi s, \tag{2}\]  
where \(\Psi\) is an orthogonal matrix with \(N\times N\) dimensions, which satisfies the conditions that \(\Psi\Psi^{T}=I\) and \(\Psi^{T}\Psi=I\). Here, \(\Psi\) is the sparsity matrix, and \(s\) is a sparse vector. When \(K\) values of \(s\) are nonzero, and other \(N-K\) values are zero (\(K\ll N\)), we call the vector \(s\)\(K\)-sparse. Common sparsity matrices are discrete Fourier transform (DFT) [3], discrete-wavelet-transform (DWT) [4], and discrete-cosine-transform (DCT) [5] matrices. As is shown in Figure 2, on the basis of Equations (1) and (2), we have  
\[y=\Phi x=\Phi\Psi s=\Theta s, \tag{3}\]  
where \(\Phi\Psi\) is the sensing matrix. To construct \(x\) from \(y\), sensing matrix \(\Phi\Psi\) must be in accordance with the restricted isometry property (RIP) [6]. RIP is  
\[1-\delta_{k}\leq\frac{\left\|\Theta v\right\|_{2}}{\left\|v\right\|_{2}}\leq 1 +\delta_{k}, \tag{4}\]  
where \(\delta_{k}\in(0,1)\), \(v\) is an arbitrary sparsity signal. The process of reconstruction can be described as  
\[\min_{g}\left\|g\right\|_{l_{1}}\ \ s.t.\ \ y=\Theta s, \tag{5}\]  
which is a convex-optimization problem. A large amount of work has been done on CS theory and applications [7; 8]. Based on the CS introduction above, CS is principally composed of two important parts, sensing and reconstruction. In the sensing part, we use a sensing matrix that satisfies certain conditions to obtain a sparse signal. There are many classical sensing matrices, such as the random, deterministic, and structured random matrices. The Gaussian and Bernoulli matrices are typical random matrices. Common deterministic matrices are the polynomial and chaotic matrices. The Toeplitz and the Hadamard matrices are structured random matrices. In the reconstruction step, we use a measurement vector and CS algorithms to reconstruct the original signal. There are many kinds of reconstruction CS algorithms, such as the convex-optimization, greedy, and Bayesian algorithms. In addition to theoretical research, CS has also been utilized in many different domains such as data compression, image encryption, and cryptography. This paper is divided into five sections. Section 2 introduces several common CS methods, including sparse dictionary, block CS, chaotic CS, deep-learning CS, and semitensor-product CS. Figure 1: Network architecture is increasingly complex, and transmitted network data increasingly bigger.