# Beyond Stochastic Gradient Descent for Matrix Completion Based Indoor Localization
## 4 Simulation Results and Discussion
### Complexity
#### Analysis  
According to the closed-form expressions mentioned in Section 4.5.1, it is possible to numerically calculate the complexity of the different algorithms, since the value of \(n\) is known, as given in Table 3. The complexity of each iteration and the complexity of the algorithm are normalized with respect to the complexity of GD, in order to highlight the contribution of other cited algorithms compared to GD. The localization mean error in Table 3 corresponds to the best mean error registered by each algorithm at different values of sigma shadowing.  
The best localization mean errors reached by GD and NAG are close. However, in terms of execution time, the GD wins. In terms of number of iterations required to converge, NAG converges fast compared to GD. However, the complexity taken by each iteration, which represents 1.9839 operations instead of 1 operation registered by GD. The worst localization mean error is introduced by Adagrad. It is also associated with the highest computational complexity. Its required number of operations per iteration is the best one compared to other used algorithms (except GD). However, the number of iterations to converge is too high, which increases significantly the complexity of the algorithm. The complexity of RMSProp to converge is around 0.4 of the one registered by Adagrad. However, it is still high and cannot be adapted in large networks or in real time localization systems.  
The required number of operations per iteration for Adadelta and Adam is around \(1.5\times c_{GD}\). However, the number of iterations required by Adadelta to converge is significantly higher than the number needed by Adam. For this, the execution time and the computational complexity are higher for Adadelta than Adam. Adam corresponds to the best complexity, it is 0.2 of the complexity reached by GD. Compared to other cited algorithms, it is associated to the lowest complexity. It does not require a high computational time, so, it can be adapted to real time localization systems. Thus, considering the trade-off between localization accuracy and computational complexity, Adam outperforms other optimization algorithms.  
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline  & Algorithm & Localization Mean Error (m) & Number of Operations per Iteration & Number of Iterations to Reach the & Complexity of the Algorithm to Reach the Convergence \\  & & & **per Iterations for GD** & \\ \hline \multirow{4}{*}{**Signa shadowing = 0**} & Without & & & \\  & matrix completion & & & \\ \cline{2-5}  & CD & 0.56 & 1 & 5910 & 1 \\ \cline{2-5}  & NAG & 0.56 & 1.9809 & 3100 & 1.0065 \\ \cline{2-5}  & Adjusted & 1.8 & 1.2673 & 120,000 & 25.3281 \\ \cline{2-5}  & RMSProp & 1.8 & 1.5 & 44,750 & 11.1041 \\ \cline{2-5}  & Adadelta & 0.07 & 1.5054 & 14,350 & 3.602 \\ \cline{2-5}  & Adam & 0.55 & 1.5 & 790 & 0.2005 \\ \hline \multirow{4}{*}{**Signa shadowing = 2**} & Without & & & \\  & matrix completion & & & & \\ \cline{2-5}  & CD & 1.2 & 1 & 5335 & 1 \\ \cline{2-5}  & NAG & 1.2 & 1.9809 & 3942 & 1.4129 \\ \cline{2-5}  & Adjusted & 2.2 & 1.2673 & 125,000 & 25.3716 \\ \cline{2-5}  & RMSProp & 2.1 & 1.5 & 45,640 & 12.886 \\ \cline{2-5}  & Adadelta & 1.2 & 1.5054 & 10,530 & 2.869 \\ \cline{2-5}  & Adam & 1.2 & 1.5 & 775 & 0.21 \\ \hline \multirow{4}{*}{**Signa shadowing = 5**} & Without & & & \\  & matrix completion & & & & \\ \cline{2-5}  & CD & 2.6 & 1 & 4435 & 1 \\ \cline{2-5}  & NAG & 2.6 & 1.9809 & 3281 & 1.4677 \\ \cline{2-5}  & Adjusted & 3.4 & 1.2673 & 121,000 & 34.2835 \\ \cline{2-5}  & RMSProp & 3.4 & 1.5 & 43,020 & 14.8846 \\ \cline{2-5}  & Adadelta & 2.7 & 1.5054 & 9742 & 3.3067 \\ \cline{2-5}  & Adam & 2.6 & 1.5 & 751 & 0.2540 \\ \hline \hline \end{tabular}
\end{table}
Table 3: Algorithms’ complexity normalized with respect to ‘Gradient descent’ (GD).