# GNSS Signal Compression Acquisition Algorithm Based on Sensing Matrix Optimization
## 2 GNSS Compression Acquisition Algorithm
### Compression Acquisition  
From (4), the sparse vector \(\mathbf{X}\) can be estimated by using the CS theory [19]. Hence, the GNSS signal is compressed by the measurement matrix \(\mathbf{\Phi}\) to obtain the \(M\times 1\) dimensional measured value \(\mathbf{Y}\)[15]  
\[\mathbf{Y}_{M\times 1}{=}\mathbf{\Phi}_{M\times N}\cdot\mathbf{r}_{N\times 1}{=} \mathbf{\Theta}_{M\times N}\cdot\mathbf{X}_{N\times 1}{=}\mathbf{\Phi}_{M \times N}\cdot\mathbf{\
abla}_{N\times N}\cdot\mathbf{X}_{N\times 1} \tag{5}\]  
where \(\mathbf{\Theta}=\mathbf{\Phi}\cdot\mathbf{\
abla}\) denotes the sensing matrix. The choice of sensing matrix \(\mathbf{\Theta}\) has a significant impact on signal reconstruction. When the sensing matrix \(\mathbf{\Theta}\) meets the Restricted Isometry Property (RIP) condition [20], it will be beneficial for signal reconstruction. In other words, each column is a unit vector, and the sum of squares of all columns meets the Welch bound [21; 22].  
\[\sum_{i=1}^{N}\left|\left\langle\theta_{i}\theta_{i}\right\rangle\right|^{2} \geq\frac{N^{2}}{M} \tag{6}\]  
By reconstructing the measured value \(\mathbf{Y}\), we can obtain the code phase and Doppler frequency values. Replacing circular correlation with compressed reconstruction in this method decreases the usage of dedicated hardware resources in general.  
As \(\mathbf{X}\) is sparse, the solution of \(\mathbf{X}\) can be converted into a \(l_{0}\) norm problem  
\[\min\left\|\mathbf{X}\right\|_{0}\qquad\text{s.t.}\quad\mathbf{Y}=\mathbf{ \Theta}\cdot\mathbf{X} \tag{7}\]  
where \(\left\|\cdot\right\|_{0}\) means \(l_{0}\) norm, which counts the number of nonzero elements in its argument. Then we can obtain the estimated code phase according to the position of the maximum element in \(\mathbf{X}\).  
It is a NP-hard problem of solving Equation (7), and can be transformed into a convex optimization problem by replacing \(l_{0}\) norm with \(l_{1}\) norm. Then, Equation (7) can be written as  
\[\min\left\|\mathbf{X}\right\|_{1}\qquad\text{s.t.}\quad\mathbf{Y}=\mathbf{ \Theta}\cdot\mathbf{X} \tag{8}\]  
Figure 1: The model of autocorrelation function output.  
In Equation (8), the greedy algorithms [23; 24; 25] can be used to reconstruct the elements of the measured value \(\mathbf{Y}\).  
The difference between the compression acquisition algorithm and the traditional algorithm is that the former uses the sensing matrix \(\mathbf{\Theta}\) to compress the sparse signal \(\mathbf{X}\) instead of cyclic correlation. The row vector of the sensing matrix can be viewed as the compression correlator. Hence, the number of correlators is reduce to \(M/N\) times by compressed sensing, which reduces the resource overhead.  
The existing compression acquisition algorithms use the Gaussian random matrix as the measurement matrix \(\mathbf{\Phi}\) to construct the sensing matrix, which reconstructs the original signal with a certain probability but has SNR loss. Thus, it is necessary to improve the existing compression acquisition algorithms by constructing a new sensing matrix.  
The work in [26] indicates that any \(K\) sparse signal \(\mathbf{x}\) can be recovered from the observation vector \(\mathbf{y}\) exactly. Hence, the spark of the sensing matrix is a sufficient condition to make the solution unique, which can be defined as  
\[\text{spark}(\mathbf{\Theta})>2K \tag{9}\]  
where \(\text{spark}(\mathbf{\Theta})\) is the minimal number of columns from \(\mathbf{\Theta}\) that are linearly dependent, and \(K\) is the sparsity of \(\mathbf{x}\).  
From Equation (9), a larger spark is beneficial to recover the signal more precisely for the CS system. It is not tractable to directly compute the spark of a matrix, but there are some useful properties in \(\mathbf{\Theta}\) that have been implemented to guarantee recovery, such as mutual incoherence. The incoherence between sparse basis \(\mathbf{\Psi}\) and measurement matrix \(\mathbf{\Phi}\) can be optimized by using the conjugate gradient method.