# Primary User Localization Algorithm Based on Compressive Sensing in Cognitive Radio Networks
## 3 Compressive Sensing Theory  
Compressive sensing is a technique that can efficiently acquire a signal using relatively few measurements, by which unique representation of the signal can be found based on the sparseness or compressibility of signal in some domain. As the authorised spectrum is inherently sparse due to its low spectrum utilization, compressive sensing becomes a promising candidate to realize spectrum sensing by using sub-Nyquist sampling rates [14]. Compressive sensing theory indicates that if signal \(\mathbf{u}\in\mathbf{R}^{N\times 1}\) is sparse in a transform domain, then the high-dimensional coefficient \(\mathbf{f}\) in domain \(\mathbf{\
abla}\) of the signal \(\mathbf{u}\) can be projected into a low-dimensional space through measurement matrix, and the original sparse signal can be reconstructed with high probability by solving an optimization problem [18; 19]. In CS model, sparse transformation is first proceeded for signal \(\mathbf{u}\):  
\[\mathbf{u}=\sum_{i=1}^{N}\mathbf{\varphi}_{i}f_{i}=\mathbf{\
abla}f \tag{3}\]  
where for a sparse signal vector \(\mathbf{u}\in\mathbf{R}^{N\times 1}\), sparse matrix basis \(\mathbf{\
abla}\in\mathbf{R}^{N\times N}\) and coefficient vector \(\mathbf{f}\in\mathbf{R}^{N\times 1}\), if \(\mathbf{\
abla}\) is full rank and only \(k(k\ll N)\) of the \(\mathbf{f}\) are nonzero, then define the signal \(\mathbf{u}\) is \(k\) sparse in the sparse matrix \(\mathbf{\
abla}\). Afterwards, signal \(\mathbf{u}\) is projected into a measurement matrix \(\mathbf{\Phi}\) which satisfies the restricted isometric property (RIP) condition, then the measurement vector \(\mathbf{y}\) is obtained:  
\[\mathbf{y}=\mathbf{\Phi}\mathbf{u} \tag{4}\]  
where \(\mathbf{y}\in\mathbf{R}^{M\times 1}\) and \(\mathbf{\Phi}\in\mathbf{R}^{M\times N}(M\ll N)\) is the measurement matrix. Finally, substitute Equation (2) into Equation (3), then obtain:  
\[\mathbf{y}=\mathbf{\Phi}\mathbf{\
abla}\mathbf{f}=\mathbf{A}\mathbf{f} \tag{5}\]  
where \(\mathbf{A}=\mathbf{\Phi}\mathbf{\
abla}\) is observation dictionary and the measurement \(\mathbf{\Phi}\) is incoherence with the basis \(\mathbf{\
abla}\). Theoretically speaking, reconstructing the sparse coefficient sequence \(\mathbf{f}\) is equivalent to solving an optimization problem, the \(l_{0}\) minimization problem, as follows:  
\[\min_{f}\lVert f\rVert_{0},\quad s.t.\quad\mathbf{A}\mathbf{f}=\mathbf{y} \tag{6}\]  
Since the problem as formulated in Equation (5) is a NP-hard problem and numerically unfeasible, we may opt for the basis pursuit algorithm with minimization. \[\min_{f}\lVert f\rVert_{1},\quad s.t.\quad\mathbf{A}\mathbf{f}=\mathbf{y} \tag{7}\]The reconstruction of the signal, namely the process of recovering \(N\)-dimensional sparse signal \(\mathbf{f}\) from \(M\)-dimensional observation signal \(\mathbf{y}\), can be solved by conducting \(l_{0}\)-norm minimization optimization to Equation (5). In the theory of compressive sensing, observation dictionary must satisfy the RIP condition, selecting \(L\) column from \(\mathbf{A}\) (\(L\subset\{1,2,\cdots,N\}\), \(|M|\leq S\)) to constitute one submatrix \(\mathbf{A}_{L}\), \(\mathbf{A}_{L}\) satisfies:  
\[1-\delta_{S}\leq\frac{\|\mathbf{A}_{L}\mathbf{X}\|_{2}^{2}}{\|\mathbf{X}\|_{2}^{2}}\leq 1+ \delta_{S} \tag{8}\]  
where \(\delta_{S}\) represents the \(S\)-restricted isometric constant of \(\mathbf{A}\), and it is the minimum value to hold the above formula. The essence of the above-mentioned conditions is that the requirement of matrix \(\mathbf{A}\) is a kind of approximate orthogonal matrix (due to \(M\ll N\), the complete orthogonal cannot be realized). The sparse transformation matrix \(\mathbf{\Psi}\) is commonly an orthogonal type of matrix; therefore, to render \(\mathbf{A}=\mathbf{\Phi}\mathbf{\Psi}\) it is necessary to meet the RIP property, which takes only matrix \(\mathbf{\Phi}\) satisfying RIP conditions. Normally, if matrix \(\mathbf{\Phi}_{M\times N}\) is a stochastic matrix, then it satisfies the RIP with a large probability.