## 5 AP Localization Using Compressed Sensing Method  
Typically, fingerprint-based localization methods do not rely on the location of the APs. In other words, the AP locations are assumed to be unknown. Nonetheless, better localization can be achieved if one could estimate the AP locations. Next, we discuss a compressed-sensing (CS)-based approach to estimate the AP locations. Consider a set of \(N\) discrete locations throughout the indoor area. Suppose a set of \(M\) access points can be seen at each location. It is a practical assumption that the number of grid points is much larger than the number of access point in the indoor area i.e., \(M\ll N\). We will use this assumption to apply a CS-based method to recover the location of the APs. Compressed Sensing is a signal processing technique that can efficiently reconstruct a signal by exploiting the _sparsity_ and _incoherence_ properties of the signal [28; 29; 30]. Assume corresponding to the \(i\)-th AP, we define a vector \(\theta_{i}\) of size \(N\). \(\theta_{i}\) is a vector that shows the location of the AP by assigning a one to one the \(N\) element and zero for the rest of the element. For example, if \(\theta_{i}(n)=1\) then the location of the \(i\)-th AP is estimated to be the location of the \(n\)-th grid point in the indoor area. Concatenating all such vectors for all \(M\) APs results in a so-called index matrix, \(\mathbf{\Theta}_{N\times M}\) as,  
\[\mathbf{\Theta}=[\theta_{1},\ldots,\theta_{m},\ldots,\theta_{M}], \tag{13}\]  
According to the CS theory, rather than measuring the \(M\)-sparse signal or its sparse representation \(\mathbf{\Theta}\) directly, compressive noisy RSS measurements in an \(\ell\)-dimensional space are used. These compressive measurements are obtained by multiplying a random matrix by the original signal,  
\[\mathbf{y}=\mathbf{\Phi}\mathbf{\
abla}\mathbf{\Theta}+\varepsilon, \tag{14}\]where  
1. \(\mathbf{y}_{\ell\times M}\) are the compressive noisy RSS measurements. 2. \(\mathbf{\Phi}_{\ell\times N}\) is the measurement matrix. Each row in this matrix represents the location of one RP, with an element of 1 to indicate the grid point at which the RP is located. Thus, only a few of RSS values are collected on the locations of RPs instead of measuring all the RSS values on the overall grid, which reduces the workload in the offline phase. 3. \(\mathbf{\Psi}_{N\times N}\) is the sparsity basis on which the measured signals have sparse coefficients \(\mathbf{\Theta}\). In this matrix, \(\mathbf{\Psi}_{ij}=RSS(d_{ij})\) indicates the RSS values collected at grid point \(i\) from the AP located at grip point \(j\), for all \(1\leq i\leq N\) and \(1\leq j\leq N\). Assume that the transmition power of an AP is \(P_{t}(\mathrm{dBm})\). Then \(RSS(d)\) is calculated based on the empirical indoor propagation model of [20]: \[RSS(d)=\left\{ \begin{array}{ll}P_{t}-40.2-20\mathrm{log}(d),&\text{if }d \leq 8\\ P_{t}-58.5-33\mathrm{log}(d),&\text{if }d>8\end{array} \right.\] (15) where \(d\) is the physical distance from the transmitter (AP) to the receiver. 4. \(\varepsilon\) is the measurement noise. The locations of the APs can be recovered by the following \(\ell_{0}\)-minimization:  
\[\mathbf{\hat{\Theta}}=\arg\min_{\mathbf{\Theta}}\|\mathbf{\Theta}\|_{0},\;s.t.\;\mathbf{y}=\mathbf{\Phi}\mathbf{\Psi}\mathbf{\Theta}, \tag{16}\]  
Unfortunately, solving (16) is both numerically unstable and NP-hard. Therefore, \(\ell_{1}\)-minimization is used to recover the AP locations:  
\[\mathbf{\hat{\Theta}}=\arg\min_{\mathbf{\Theta}}\|\mathbf{\Theta}\|_{1},\;s.t.\;\mathbf{y}=\mathbf{\Phi}\mathbf{\Psi}\mathbf{\Theta}, \tag{17}\]  
This is a convex optimization problem and various methods have been proposed to find the solution such as BP [31], OMP [32] and SP [33]. In this paper, we use OMP algorithm. To evaluate the performance of the proposed CS-based AP localization algorithm, a few number of APs on the fourth floor of the Bahen Building at the University of Toronto have been localized. Figure 7 shows the AP localization results.