## 3 Problem Formulation  
Suppose a set of \(\ell\) RPs are selected throughout the indoor area and \(M\) APs are visible at each RP location. In the offline training phase, we collect the \(i\)-th _fingerprint_\((c_{i},r_{i})\) at RP \(S_{i}\), where \(c_{i}=(x_{i},y_{i})^{T}\) is the geographical coordinates of \(S_{i}\) and \(r_{i}\) is an \(M\times 1\) RSS vector. We refer to these fingerprints as _labeled_ data. In the online phase, the user's location can be estimated by comparing the RSS value \(r_{k}\) collected at the unknown location of the user \(S_{k}\) with the fingerprints in the radio map. If \(r_{k}\) is similar to a particular \(r_{i}\), then we reason that user's location \(S_{k}\) must be close to RP location \(S_{i}\). In practice, the RSS values measured by a mobile device are subject to multiple sources of noise, such as multi-path fading and shadowing. Figure 1 illustrates the histogram of 100 RSS values from a single AP at a particular location inside the Bahen Building at the University of Toronto. The RSS values are distributed in a wide range of \(-70\) dBm to \(-50\) dBm. Occasionally, we cannot receive any power from this AP and a value of \(-110\) dBm is used to denote the missing RSS value. Figure 2 shows the RSS value from a single AP throughout the fourth floor of the Bahen Building after removing \(-110\) dBm measurements and averaging over RSS values at each location. Next, we explain how we apply the G-SSL method to reduce the effect of noise in the radio map. Consider a set of \(u\) locations within the localization area that are not associated with RSS measurements hence we call them _unlabelled_ data. In addition to these unlabelled locations, there are \(\ell\) labelled RP locations as explained previously. Consequently, we have \(\ell+u\) locations of labelled and unlabelled data. In the G-SSL method, a weighted graph is constructed using both labelled and unlabelled data. In this graph, the vertices represent the training data and all the vertices are connected by edges. The edge weight matrix, which is calculated by the training data, represents the relationship between vertices in the graph by assigning a weight to each edge connecting two vertices in the graph. Each vertex on the graph corresponds to a location and the weighted edges between vertices represent the relationship between both RSS values and locations corresponding to those vertices. As mentioned earlier in this section, measured RSS values in an indoor environment are affected by different types of noise. However, in the graph representation of the G-SSL method, any two vertices on the graph  
Figure 1: Histogram of 100 RSS values of a single AP measured at a location. are related not only by the RSS values measured at those vertices but also by the physical locations corresponding to those vertices. Therefore, the G-SSL is able to reduce the effect of noise in the measured RSS value by incorporating both RSS and location information. Next, we will explain the G-SSL method with more details. Suppose \(\Omega=(V,E)\) denotes the graph of the G-SSL method. The vertices of the graph, \(V\), is defined as \(\mathbf{V}=\{c_{1},c_{2},\ldots,c_{\ell},c_{\ell+1},\ldots,c_{\ell+u}\}\) where the first \(\ell\) elements are the location coordinates of the labelled data and the next \(u\) elements are the location coordinates of the unlabelled data. For every edge between two vertices at \(S_{i}\) and \(S_{j}\), we can calculate its weight \(w_{ij}\). \(w_{ij}\) indicates the similarity between the two vertices and takes values in the range \([0,1]\) with 0 indicating no similarity between the vertices. The result is an \((\ell+u)\times(\ell+u)\) weight matrix \(\mathbf{W}\) containing all the calculated weights. The graph edges are usually undirected, so the edge \((i,j)\) (weighted by \(w_{ij}\)) and the edge \((j,i)\) (weighted by \(w_{ji}\)) are the same edge in the graph, which means \(w_{ij}=w_{ji}\).