# Energy Efficient GNSS Signal Acquisition Using Singular Value Decomposition (SVD)
## 3 Singular Value Decomposition (SVD)
### GNSS SVD Compressed Sensing Scheme  
The method proposed for the acquisition of GNSS signals is to use SVD for sensing the signal and \(\ell_{1}\) minimization for matrix recovery which can be expressed in the following sum of terms form, where \(a_{0},a_{1},a_{2},\ldots,a_{m-1}\) are the coefficients of the basis vectors, and, where the signal can be defined on an orthonormal basis:  
\[f(x)=a_{0}+a_{1}x+a_{2}x_{2}+a_{3}x_{3}+\ldots+a_{m-1}x_{m-1} \tag{8}\]  
Let \(x\ \epsilon\ R^{M}\) be a GNSS signal and let \(\Psi=\{\Psi_{1},\ \Psi_{2},\ldots,\Psi_{M}\}\) be a basis vector spanning \(R^{M\times N}\). The discrete time signal can be represented sparsely as:  
\[\hat{x}=\sum_{i=1}^{M}\theta_{i}\Psi_{i}=\Psi\theta \tag{9}\]  
where \(\theta\ \epsilon\ R^{d}\) is a coefficient vector of \(\hat{x}\) in the \(\Psi\) domain. If \(\theta\) is sparse, then the solution to an undetermined system of the form \(x=\Psi\theta\), \(\theta\ \mathbb{R}^{N\times 1}\) where the unknowns \(d\) are greater than the observations \(M\) that can be solved using \(\ell_{o}\) minimization, but this problem is NP-hard [31].  
Defining the sensing matrix \(A=\Phi\Psi\), \(A\in R^{M\times N}\) let \(p=\min(M,N),\ K\leq r\) be the number of non-zero singular values of \(A\):  
\[Ax=y \tag{10}\]  
\[U\Sigma\underbrace{V^{T}x}=y \tag{11}\]  
Multiplying both sides by \(U^{T}\), where the superscript \"\(T\)\" means the \"transpose\" of matrix \(U\), \(U^{T}U=I\):  
\[\mathbb{I}\Sigma\underbrace{V^{T}x}=\underbrace{U^{T}y} \tag{12}\]  
where \(\hat{x}=\underbrace{V^{T}x}\), and \(\hat{y}=U^{T}y\):  
\[\Sigma\hat{x}\ =\ \hat{y} \tag{13}\]  
where \(A\) is the sum of \(k\) rank-one matrices, \(\hat{y}\) is the measurement vector and, for some scalars, \(\mathbf{\sigma_{1}},\ \mathbf{\sigma_{2}}\), \(\mathbf{\sigma_{3}},\ \ldots,\ \mathbf{\sigma_{k}}\geq 0\) and orthonormal vectors \(\mathbf{u_{1}},\ \mathbf{u_{2}},\ldots,\mathbf{u_{k}}\in R^{M}\) and \(\mathbf{v_{1}},\ \mathbf{v_{2}},\ldots,\ \mathbf{v_{k}}\in\ R^{N}\). The \(\{\sigma_{k}\}\) can be interpreted as the \(k\) largest singular values of \(A\), and the \(\{u_{i}\}\), \(\{v_{i}\}\) as the corresponding singular vectors. The collection of all such matrices form a union of subspaces in \(R^{M\times N}\) ; each set of vectors\(\{u_{i}\},\ \{v_{i}\}\) define an R-dimensional subspace, and the \([\sigma_{k}]\) correspond to an expansion in that subspace. Since \(x\) can be represented sparsely as \(\theta\) in the [PERSON] dictionary, and \(x\) is known, the desired sparse solution can be recovered by using Equation (14):  
\[\left(\ell_{k}^{1}\right):\hat{\theta}\ \text{to}\ min\|\theta\|_{\ell_{1}} \text{ subject to}\left(\theta_{i}-\frac{y_{i}}{\sigma_{i}}\right)\leq\epsilon,\ i=1,2,\ldots,p \tag{14}\]  
However, due to noise (white Gaussian) \(v\in\ R^{N}\) present in real data, \(x\) may not be expressed as a sparse superposition of \(s\), and Equation (9) needs to be modified to:  
\[\hat{x}=\Psi\theta+v \tag{15}\]  
where \(\|v\|\) is bounded by \(v_{2}\). The sparse \(\theta\) can still be recovered accurately by solving the stable \(\ell_{1}\) minimization problem via the second-order cone programming [32] using Equation (2).