# Energy Efficient GNSS Signal Acquisition Using Singular Value Decomposition (SVD)
## 3 Singular Value Decomposition (SVD)
### Algorithm  
In terms of algorithms to solve convex problems, one approach has been used in this paper and is explicitly specified where needed; as a general guideline, once a convex formulation of a problem is found, testing it with the aid of modeling languages, such as CVX [34], allow its solution by means of general solvers that handle linear or quadratic programming [35].  
Recent advances in algorithms for solving convex optimization problems, along with significant advances in processor power, have dramatically reduced solution times. Perhaps more exciting is the possibility that convex optimization can be embedded directly in signal processing algorithms that run online, with strict real-time deadlines, even at rates of tens of kilohertz [34]. The automatic code generator discovers the sparsity, and calculates how to exploit it, at code-generation time.  
CVX is a MATLAB-based modeling system for convex optimization. CVX turns MATLAB into a modeling language, allowing constraints and objectives to be specified using standard MATLAB expression syntax. For this paper the use of CVX (a package for specifying and solving convex programs [36; 37]) in the MATLAB programing language was used to solve Equation (19) and to run Algorithm 1.  
\[\mathbf{min}\|\mathbf{\theta}\|_{\mathbf{\ell_{1}}}S.T.\ \|\mathbf{\theta_{i}}-\frac{\mathbf{y_{i}}}{ \mathbf{\sigma_{i}}}\|_{\mathbf{\ell_{2}}}\leq\mathbf{e},\ i=\mathbf{1},\mathbf{2},\ldots,\mathbf{p} \tag{19}\]  
```
Input: Measurements are segmented into \(\mathbf{m}\times\mathbf{n}\) vector of length \(\mathbf{m}\)\(\mathbf{x_{01}}=[\mathbf{x_{0}},\mathbf{x_{1}},\ldots,\mathbf{x_{M}}]\) Steps
1. Compute the desired compression ratio \(R=\frac{N}{\mathbf{M}}\ \mathbf{R}\ \in(\mathbf{0},\mathbf{1})\) to establish input \(\mathbf{N}\) columns for the Toeplitz matrix after establishing the soft threshold from the scree plot
2. Construct the Rectangular Toeplitz Matrix \(bm{bmT}z=\left\{[\mathbf{x_{0}},\mathbf{x_{1}},\ldots,\mathbf{x_{M}}],[\mathbf{x_{0}},\mathbf{x_{ 1}},\ldots,\mathbf{x_{N}}]^{T}\right\}\)
3. Compute the SVD for the Toeplitz matrix output arguments:
4. \(\mathbf{U}-\)Left Singular Vectors\((\textbf{Matrix})\)
5. \(\mathbf{V}-\)Right Singular Vectors\((\textbf{Matrix})\)
6. \(\mathbf{\Sigma}-\)Singular Values\((\textbf{Diagonal Matrix})\)
7. Compress the signal \(\mathbf{y}=\mathbf{U}^{T}\mathbf{x_{01}}\) for all subsequent \(x\) in buckets of the same size \(\mathbf{M}\) e.g., \(\mathbf{xb2}=[\mathbf{x_{M+1}},\mathbf{x_{M+2}},\ldots,\mathbf{x_{K=M}}]\)
8. Calculate the sparse vector signal using \(\mathbf{\ell_{1}}-\textbf{minimization}\) by solving the convex optimization problem of Equation (19). Return: Once \(\mathbf{\theta}\) is computed, the original signal \(\mathbf{x}\) is decoded by computing \(\mathbf{x}=\mathbf{\Psi}\mathbf{V}\mathbf{\theta}=\mathbf{U}\mathbf{\Sigma}\mathbf{V}^{T}\mathbf{V}\mathbf{\theta}\) for each one of the buckets or windows compressed on step 7. By using the proposed method, only a small set of measurements is required to recover the vector \(\mathbf{x}\ \in\ \mathbb{R}^{M\times 1}\).
```  
**Algorithm 1** Compressive sensing GNSS-SVD-C.