# Energy Efficient GNSS Signal Acquisition Using Singular Value Decomposition (SVD)
## 3 Singular Value Decomposition (SVD)
### Theorem 1  
Let A be a \(n\times d\) matrix with right singular vectors \(\mathbf{v_{1}}\), \(\mathbf{v_{2}}\),..., \(\mathbf{v_{k}}\), left singular vectors \(\mathbf{u_{1}}\), \(\mathbf{u_{2}}\),..., \(\mathbf{u_{k}}\), and corresponding singular values \(\mathbf{\sigma_{1}}\), \(\mathbf{\sigma_{2}}\),..., \(\mathbf{\sigma_{k}}\). Then A can be decomposed into a sum of rank one matrices as  
\[A=\sum_{i=1}^{k}\sigma_{i}u_{i}v_{i}^{T}\approx\sigma_{1}u_{1}v_{1}^{T}+\sigma _{2}u_{2}v_{2}^{T}+\ldots+\ \sigma_{k}u_{k}v_{k}^{T}=U\Sigma V^{T} \tag{3}\]  
Proof: For each singular vector \(v_{j}\), \(A\sigma_{j}=\sum_{i=1}^{k}\sigma_{i}u_{i}v_{i}^{T}v_{j}\). Since any vector \(v\) can be expressed as a linear combination of the singular vectors plus a vector perpendicular to the \(v_{i}\), \(A\sigma=\sum_{i=1}^{k}\sigma_{i}u_{i}v_{i}^{T}v\), given two matrices are identical if for all vectors \(v\ Av=Bv\), then \(A=\sum_{i=1}^{k}\sigma_{i}u_{i}v_{i}^{T}\).  
Suppose \(A\) is an \(m\times n\) matrix whose entries come from field \(K\), which is the field of real or complex numbers, then there exists a factorization called singular value decomposition of \(A\), where the matrix \(A\) can be expressed as a sum of \(k\) outer product of vectors \(\sigma_{1}u_{1}v_{1}^{T}+\sigma_{2}u_{2}v_{2}^{T}+\ldots+\ \sigma_{k}u_{k}v_{k}^{T}\), where \(\sigma_{1}\geq\sigma_{2}\geq\sigma_{3}\ldots\geq\sigma_{n}\geq 0\). \(U\) is an \(m\times n\) unitary matrix (if \(K=\mathbb{R}\), unitary matrices are orthogonal matrices), \(V\) is an \(n\times n\) unitary matrix over \(K\), and \(V^{T}\) is the conjugate transpose of \(V\).  
\(\Sigma=U^{T}AV=\mathrm{diag}\big{(}\sigma_{1},\sigma_{2},\ldots,\sigma_{p} \big{)}\) and the diagonal entries \(\sigma_{i}\) of \(\Sigma\) are known as the singular values of \(A\), where:  
\[\Sigma^{-1}=V^{T}A^{-1}U \tag{4}\]  
\(U\) and \(V\) are orthogonal such that: \(U^{T}U=I^{n\times n}\), and \(V^{T}V=I^{n\times n}\), where \(I\) is the identity matrix.  
Given the \(m\times n\) matrix \(A=U\Sigma V^{T}\) from Equation (3) and a target rank \(k\geq 1\), it produces a rank-\(k\) approximation of \(A\) as follows. See also Figure 5.  
1. Compute \(A\ =\ U\Sigma V^{T}\).
2. Keep only the top \(k\) right singular vectors: set \(V^{T}\) equal to the \(k\) rows of \(V^{T}\) (a \(k\ \times\ N\) matrix).
3. Keep only the top \(k\) left singular vectors: set \(U_{k}\) equal to the first \(k\) columns of \(U\) (an \(M\ \times\ k\) matrix).  
4. Keep only the top \(k\) singular values: set \(\Sigma_{k}\) equal to the first \(k\) rows and columns of \(\Sigma\) (a \(k\ \times\ k\) matrix), corresponding to the \(k\) largest singular values of \(A\).  
The computed low-rank approximation is then:  
\[A_{k}=\ U_{k}\ \Sigma_{k}V_{k}^{\ T} \tag{5}\]  
Storing the matrices on the right-hand side of takes \(O(k(n\ +\ d))\) space, in contrast to the \(O(nd)\) space required to store the original matrix \(A\). This is an enormous gain when \(k\) is relatively small, and \(n\) and \(d\) are relatively large [28].  
In the matrix \(A_{k}\), defined in Equation (5), all of the rows are linear combinations of the top \(k\) right singular vectors of \(A\) (with coefficients given by the rows of \(U_{k}\ \Sigma_{k}\)), and all of the columns are linear combinations of the top \(k\) left singular vectors of \(A\) (with coefficients given by the columns of \(\Sigma_{k}\ V_{k}^{\ T}\)). Thus, \(A_{k}\) has rank \(k\), then, it might be possible to accurately recover a low-rank matrix from relatively few measurements.