# Optimization Methods of Compressively Sensed Image Reconstruction Based on Single-Pixel Imaging
## 2 Related Works and Theory Formulation
### Compressed Sensing Measurement Matrix  
Compressed sensing measurement matrix is an important intermediate bridge between \(x\) and \(y\) in CS-based signal processing to reduce the measurements number of the vector \(x\), and it is directly related to the efficiency of signal sampling and the quality of signal reconstruction. It has been proved that sensing matrix should satisfy some necessary conditions to accurately reconstruct the original signal with high probability [4; 5; 36; 37]. Among these conditions, the most important one is that sensing matrix \(\Phi\) should satisfy the restricted isometry property (RIP) [50] as follows:  
\[(1-\delta_{K})\|x\|_{2}^{2}\leq\|\Phi x\|_{2}^{2}\leq(1+\delta_{K})\|x\|_{2}^ {2},\ (0<\delta_{K}<1), \tag{6}\]  
where \(\delta_{K}\) is the restricted isometry constant (RIC), \(\delta_{K}\in(0,1)\), \(K\) is the sparsity level of \(x\) with \(K\) non-zero elements.  
RIP condition is a necessary condition to ensure that the original signal can be recovered with high probability. However, it is very complicated to verify whether the sensing matrix satisfies the RIP and also difficult to compute \(\delta_{K}\) from the known sensing matrix \(\Phi\)[51]. Thus, finding a simple and efficient alternative condition that can replace RIP is very important to construct a sensing matrix of good performance. In [37], it has been proved that a sensing matrix would meet RIP with large probability if the sensing matrix \(\Phi\) and sparsifying basis \(\Psi\) (or orthogonal dictionary) were as incoherent (orthogonal) as possible, and the recovered signal would have higher reconstruction precision [52]. That is to say, if \(\Phi\) and \(\Psi\) are incoherent or uncorrelated, sampling data from the original signal can add more new information that has not already represented by the known basis \(\Psi\). In other words, in the sampling process of CS, the incoherence between \(\Phi\) and \(\Psi\) can ensure that the new information that has not be represented by the known decomposition matrix \(\Psi\) can be sampled.  
Some classic random compressed sensing measurement matrices and binary sensing matrices satisfy the RIP condition well and can guarantee the CS-based signals reconstruction with high probability [50; 53; 54; 55; 56; 57]. These commonly used classical compressed sensing matrices include Gaussian random matrix, Bernoulli random matrix, Fourier random matrix, 0-1 sparse binary matrix, part Hadamard binary matrix and so on. Among them, 0-1 sparse binary matrix and part Hadamard binary matrix are usually applied and are fixed as the conventional deterministic binary sensing matrices in single-pixel imaging system.  
According to the theoretical analysis in [58; 59], the mutual incoherence between sensing matrix and sparsifying basis means that the corresponding Gram matrix is as close as possible to an identity matrix, and the Gram matrix is defined as:  
\[Gram:=\Theta^{H}\Theta, \tag{7}\]  
where \(\Theta^{H}\) is the conjugate transpose operator of \(\Theta\), \(\Theta=\Phi\Psi\).  
Thus, minimizing the mutual coherence is equivalent to shrinking the absolute off-diagonal elements of the corresponding Gram matrix. The more closely Gram matrix approximates the identity matrix, the less the coherence between \(\Phi\) and \(\Psi\) is. In order to obtain the compressed sensing matrix of better performance, the following optimization problem is denoted as:  
\[\hat{\Phi}=\operatorname*{argmin}_{\Phi}\left\|(\Phi\Psi)^{H}\Phi\Psi-I\right\| _{F}^{2}, \tag{8}\]  
where \(I\) is an identity matrix of size \(n\times n\). Therefore, to construct an optimized sensing matrix, Equation (8) has to be solved.