## 3 Problem Formulation
In addition, the edge \((i,i)\) does not exist, therefore, there are \(\frac{1}{2}[(\ell+u)\times(\ell+u)-(\ell+u)]\) edges in the graph. In summary, only the corresponding number of graph weights are calculated which makes the weight matrix \(\mathbf{W}\) a symmetric matrix. To calculate the weights, here we use the well-known _heat-kernel_ function:  
\[w_{ij}=\exp\left\{\frac{-\|c_{i}-c_{j}\|^{2}}{\tau}\right\}, \tag{1}\]  
where \(\|c_{i}-c_{j}\|^{2}=d^{2}(S_{i},S_{j})\) is the square of the Euclidean distance between location \(S_{i}\) and \(S_{j}\) and \(\tau\) is a parameter based on the application which controls how quickly the weight decreases. The G-SSL uses \(\mathbf{W}\) to estimate the labels of the unlabelled data using the relationship between different vertices in the graph. The result is a set of estimated labels \(\hat{r}_{i}\) for \(i\in\{1,2,\ldots,\ell+u\}\). If \(c_{i}\) is close to \(c_{j}\), the estimated label \(\hat{r}_{i}\) is close to the given label \(r_{j}\) for all \(j\in\{1,2,\ldots,\ell\}\). The estimated labels \(\hat{r}_{i}\) have to satisfy two conditions. First, for the labelled data, since the labels are already known, the estimated labels \(\hat{r}_{i}\) must be close to the real labels. For the labelled data \((c_{i},r_{i})\), we should have \(\hat{r}_{i}=r_{i}\). This condition is enforced by minimizing the following loss function  
\[\min_{\hat{R}}\sum_{i=1}^{\ell}\|\hat{r}_{i}-r_{i}\|^{2}, \tag{2}\]  
Figure 2: RSS values of an AP over the corridor area of the fourth floor of the Bahen Building, University of Toronto. where \(\hat{R}\) is the \(M\times(\ell+u)\) matrix of all estimated RSS values and \(\|\bullet\|\) is the Euclidean distance. The second condition is that the graph should be smooth. The smoothness of the graph comes from the fact that data points which are close to each other should have similar labels. To satisfy the smoothness condition, the estimated labels \(\hat{r}_{i}\) and \(\hat{r}_{j}\) should meet the following loss function  
\[\min_{\hat{R}}\sum_{i=1}^{\ell+u}\sum_{j=1}^{\ell+u}w_{ij}\|\hat{r}_{i}-\hat{r }_{j}\|^{2}, \tag{3}\]  
If \(c_{i}\) and \(c_{j}\) are close to each other, the weight \(w_{ij}\) would be large, and the labels \(\hat{r}_{i}\) and \(\hat{r}_{j}\) must be close in order for the whole term to be minimized. On the other hand, if \(c_{i}\) and \(c_{j}\) are far away from each other, the weight \(w_{ij}\) would be very small and the choice of the labels does not have much effect on the minimization. Hence, the estimated labels that satisfy both conditions above can be estimated using:  
\[\hat{\mathbf{R}}^{*}= \text{arg}\ \min_{\hat{R}}\bigg{\{}\sum_{i=1}^{\ell}\|\hat{r}_{i}-r_{i} \|^{2}+\frac{\gamma}{2}\sum_{i=1}^{\ell+u}\sum_{j=1}^{\ell+u}w_{ij}\|\hat{r}_ {i}-\hat{r}_{j}\|^{2}\bigg{\}}, \tag{4}\]  
where \(\gamma\) is a the weight of the smoothness term based on the application. \(\gamma\) is a design parameter used to enforce which term is of higher importance. In conclusion, the first term of the Equation (4) penalizes the difference between the actual labels and the estimated labels and the second term ensures the smoothness of the graph. The proposed G-SSL-based RSS smoothing method for crowdsourcing is summarized in the system diagram shown in Figure 3. In the offline phase, since the actual coordinates of \(S_{i}\) and \(S_{j}\) are already known, the LR algorithm is used to obtain the uniform RSS values. Then the locations' APs are calculated by CS method. At last the RSS values can be smoothed by G-SSL method. In the online phase, the data collected simultaneously from sensors on the mobile device can be used to estimate the relative displacement between \(S_{i}\) and \(S_{j}\), that is, the distance \(d(S_{i},S_{j})\). Then the collected RSS values are processed by the LR method. After that, the RSS values can be smoothed using the calculated distance \(d(S_{i},S_{j})\). Finally, we get a more accurate positioning result.