# Optimization Methods of Compressively Sensed Image Reconstruction Based on Single-Pixel Imaging
## 2 Related Works and Theory Formulation
### Compressive Sensing  
Compressive sensing-based signal processing includes two major processes: signal measurement and signal reconstruction. First, the original signal is denoted as \(x\), \(x=\left[x_{1},x_{2},\ldots,x_{n}\right]^{T}\), \(x\in C^{n}\), \(\left|\right|^{T}\) is the transpose operator. Considering the signal \(x\) is measured in a noisy environment, the measured value is expressed as the vector \(y\), \(y=\left[y_{1},y_{2},\ldots,y_{m}\right]^{T}\), \(y\in C^{m}\), \(m\) is the number of measurements for sampling the original signal. So:  
\[y=\Phi x+e, \tag{1}\]  
where \(\Phi\) is the sensing matrix [34], \(\Phi\in C^{m\circ n}(m\ll n)\), reducing the number of measurements compared with the vector \(x\). \(e\) is the Gaussian white noise, \(e\in C^{m}\). The dimensions of \(y\) are far less than the dimensions of \(x\), so the original signal is compressed by reducing the signal's dimensions without the intermediate stage of Nyquist sampling. Therefore, after compressed sensing on the original signal \(x\), it is easier to transmit and store the data \(y\) than \(x\). \(y\) is the data that needs to be processed for restoring the original scene image \(x\) through the computer in CS-based single-pixel imaging system.  
Since the high-dimensional data \(x\) is reconstructed from the low-dimensional data \(y\), the underdetermined equations have to be solved. There are more unknown variables than equations in the process of compressed sensing, thus making it underdetermined (\(n\gg m\)), and it is very difficult to solve the underdetermined equations. In order to restore the original signal \(x\) by solving the underdetermined equations, it is usually required that the original signal is compressible (sparse) or can be represented sparsely [3; 5; 36; 37].  
If \(x\) is sparse, the sparsity level of is usually expressed using the \"L0 norm\" \(\left\|x\right\|_{0}\). \(\left\|x\right\|_{0}\) denotes the number of non-zero elements in. So \(\left\|x\right\|_{0}\) is added as the regularization penalty term in Equation (1) via L0 norm minimization, Equation (1) is updated as:  
\[\hat{x}=\arg\!\min_{x}\left\|x\right\|_{0}\text{ s.t. }\left\|\left\|\Phi x-y \right\|_{2}^{2}\leq\varepsilon, \tag{2}\]  
where \(\varepsilon\) is a non-negative upper bound that denotes the noise level to limit the error between the reconstructed signal and the original signal.  
If \(x\) is non-sparse, it is usually necessary to use an orthogonal decomposition basis or sparsifying dictionary for representing the original signal \(x\) sparsely [3] as follows:  
\[x=\sum_{1}^{n}s_{i}\psi_{i}=\Psi s, \tag{3}\]where \(s\) is the sparse coefficients that represent \(x\) by the sparsifying decomposition basis \(\Psi\), \(s=[s_{1},s_{2},\ldots,s_{n}]^{T},s\in C^{n}\), \(\Psi=[\psi_{1},\psi_{2},\ldots,\psi_{n}]\), \(\Psi\in C^{m\times n}\). So in order to acquire the sparse representation \(s\), Equation (2) is transformed as:  
\[\hat{s}=\underset{s}{\mathrm{argmin}}\|s\|_{0}\text{ s.t.}\left\|\Phi\Psi s-y \right\|_{2}^{2}\leq\varepsilon, \tag{4}\]  
where \(\hat{s}\) is the estimation of \(s\), \(\Theta=\Phi\Psi\) is called the equivalent dictionary [38], reducing the number of the basic decomposition dictionary \(\Psi\). Equation (4) is the L0 norm minimization in signal sparse decomposition [12], so we can get the estimation \(\hat{x}\) of the original signal from \(\hat{x}=\Psi s\) through CS-based reconstruction algorithms.  
For CS-based reconstruction algorithms, the commonly used algorithms mainly include greedy pursuit algorithms [39; 40; 41; 42], minimum norm optimization algorithms [43; 44; 45] and iterative threshold algorithms [46; 47]. Among these algorithms, orthogonal matching pursuit (OMP) algorithm is one of the greedy pursuit algorithms and has stable performance in reconstructing signals because of its simplicity and efficiency [41; 42], so the OMP algorithm is usually used quite effectively to get an approximated solution in compressed sensing.