# Beyond Stochastic Gradient Descent for Matrix Completion Based Indoor Localization
## 3 Proposed Matrix Completion Based Localization
### Matrix Completion: Optimization over GD and Its Variants
#### 3.2.1 Gradient Descent (GD)  
Gradient descent is an iterative method that aims to find local minimum of differentiable cost functions [36]. It is the most common first-order optimization algorithm in machine learning and deep learning. GD is based on updating each element of matrix \(\hat{\mathbf{X}}^{(t)}\) in the direction to optimize the objective function \(J(\hat{\mathbf{X}}^{(t)})\). The new parameter \(\mathbf{V}^{(t)}\) can be adjusted as  
\[\mathbf{V}^{(t)}=\alpha\
abla(J(\hat{\mathbf{X}}^{(t)})), \tag{10}\]  
\begin{table}
\begin{tabular}{l} \hline \hline
1. Input: \(\mathbf{X}\), \(\mathbf{H}\), number max of iterations \\
2. Initialization: \(\hat{\mathbf{X}}^{(0)}\), \(t\) \\
3. while \(t<\)number max of iterations \\ Update \(\hat{\mathbf{X}}\): \\  & \\ \(t=t+1\) \\ end \\
4. Return \(\hat{\mathbf{X}}\) \\ \hline \hline \end{tabular}
\end{table}
Table 1: The problem described in four steps.  
\(\alpha\) is the learning rate from range \((0,1)\). \(\
abla(J(\mathbf{\hat{X}}^{(t)}))\) is the gradient of the cost function with respect to the parameter matrix. It can be computed as follows:  
\[\
abla(J(\mathbf{\hat{X}}^{(t)}))=\
abla(f(\mathbf{\hat{X}}^{(t)}))+\lambda \times\
abla(l(\mathbf{\hat{X}}^{(t)})), \tag{11}\]  
where  
\[\
abla(f(\mathbf{\hat{X}}^{(t)})) =\mathbf{U}^{(t)}=\
abla(||\mathbf{H}\odot(\mathbf{\hat{X}}^{(t) }-\mathbf{X}^{(t)})||_{F}^{2})\] \[=2\times\mathbf{H}\odot(\mathbf{\hat{X}}^{(t)}-\mathbf{X}^{(t)}), \tag{12}\]  
\(\
abla(l(\mathbf{\hat{X}}^{(t)}))\) is calculated as follows:  
\[\
abla(l(\mathbf{\hat{X}}^{(t)})) =\mathbf{W}^{(t)}=\
abla(||(1-\mathbf{H})\odot\mathbf{\hat{X}}^{ (t)}||_{*})\] \[=(1-\mathbf{H})\odot(\mathbf{\hat{X}}^{(t)}\cdot((\mathbf{\hat{X }}^{(t)})^{T}\cdot\mathbf{\hat{X}}^{(t)})^{-0.5}), \tag{13}\]  
We might need some sort of regularization because the inverse of the square root of \((\mathbf{\hat{X}}^{(t)})^{T}\cdot\mathbf{\hat{X}}^{(t)}\) may not exist, e.g.,  
\[\
abla(l(\mathbf{\hat{X}}^{(t)}))=\
abla(||(1-\mathbf{H})\odot\mathbf{\hat{X }}^{(t)}||_{*})=(1-\mathbf{H})\odot(\mathbf{\hat{X}}^{(t)}\cdot((\mathbf{\hat{ X}}^{(t)})^{T}\cdot\mathbf{\hat{X}}^{(t)}+\epsilon\times\mathbf{I})^{-0.5}), \tag{14}\]  
where \(\epsilon\) is a regularization parameter and \(\mathbf{I}(n\times n)\) is the identity matrix. Then  
\[\
abla(J(\mathbf{\hat{X}}^{(t)}))=2\times\mathbf{H}\odot(\mathbf{\hat{X}}^{(t )}-\mathbf{X}^{(t)})+\lambda\times(1-\mathbf{H})\odot(\mathbf{\hat{X}}^{(t)} \cdot((\mathbf{\hat{X}}^{(t)})^{T}\cdot\mathbf{\hat{X}}^{(t)}+\epsilon\times \mathbf{I})^{-0.5}), \tag{15}\]  
We obtain  
\[\mathbf{V}^{(t)}=\alpha\times(2\times\mathbf{H}\odot(\mathbf{\hat{X}}^{(t)}- \mathbf{X}^{(t)})+\lambda\times(1-\mathbf{H})\odot(\mathbf{\hat{X}}^{(t)} \cdot((\mathbf{\hat{X}}^{(t)})^{T}\cdot\mathbf{\hat{X}}^{(t)}+\epsilon\times \mathbf{I})^{-0.5})), \tag{16}\]  
Using the classic Gradient descent, the known entries are very well estimated, this is why it will be used in the rest of the paper to estimate \(\mathbf{U}^{(t)}\). To estimate \(\mathbf{W}^{(t)}\), we propose to use the following algorithms.