# Getting over High-Dimensionality: How Multidimensional Projection Methods Can Assist Data Science
## 4 Multidimensional Projection Approaches and Domains
### FastMap  
[PERSON] and [PERSON] [60] created the FastMap projection, a global nonlinear technique that reaches high efficacy but generates low accuracy, depending on the structure of the projected data. FastMap maps objects from an \(\mathbb{R}^{m}\) space into an \(\mathbb{R}^{p}\), with \(p<m\), where \begin{table}
\begin{tabular}{c c c c} \hline \hline
**Technique** & **Transformation** & **Nature** & **Complexity** \\ \hline LSP & Nonlinear & Global & \(O(n^{3})\) \\ \hline HiPP & Nonlinear & Global & \(O(n\sqrt{n})\) \\ \hline t-SNE & Nonlinear & Local & \(O(n^{2})\) \\ \hline Glimmer & Nonlinear & Global & \(O(n^{2})\) \\ \hline PLMP & Partially linear & Global & \(O(n^{3})\) \\ \hline PLP & Nonlinear & Local & \(O(n\sqrt{n})\) \\ \hline LAMP & Nonlinear & Local-Hybrid & \(O(sn)\) \\ \hline LoCH & Nonlinear & Local & \(O(n\sqrt{n})\) \\ \hline UMAP & Nonlinear & Local & \(O(n^{1.14})\) \\ \hline TopoMap & Nonlinear & Global & \(O(n\log n)\) \\ \hline GRMP & Nonlinear & Local & \(O(n+|E|)\) \\ \hline \hline \end{tabular} Source: elaborated by the authors.  
\end{table} 
Table 1: Cont. each data item is projected into \(p\) orthogonal hyperplanes representing projected data coordinates. The approach's core is to project items in a particular line segment contained on a hyperplane. The process starts with a set of instances \(\mathcal{O}\) and the distance matrix \(\mathcal{D}\) generated with the Euclidean distance function \(\delta\) of the instances. As depicted in Figure 2, two instances, \(O_{a}\) and \(O_{b}\), furthest apart, are selected from the high-dimensional space. This selection requires \(O(n^{2})\) computations; however, [PERSON] and [PERSON] [60] also proposed a linear heuristic to perform it. Firstly, it selects an arbitrary instance \(O_{r}\). In the sequel, it chooses the farthest apart instance from \(O_{r}\) to be the \(O_{a}\) pivot. Finally, it selects the instance that is farthest apart from \(O_{a}\) to be the \(O_{b}\) pivot. The line \(O_{a}O_{b}\) is into a hyperplane Y, and it will represent the first coordinate of the new projected space \(\mathbb{R}^{p}\). Then, each object \(O_{i}\) is projected into \(O_{a}O_{b}\) line through the calculation of \(x_{i}\) coordinate that manipulates the cosine-law formulation as in Equation (16). In Figure 2, \(x_{i}\) is calculated using the \(O_{a}O_{i}O_{b}\) triangle and \(x_{j}\) is calculated using \(O_{a}O_{j}O_{b}\). \[x_{i}=\frac{\delta(O_{a},O_{i})^{2}+\delta(O_{a},O_{b})^{2}-\delta(O_{b},O_{i })^{2}}{2\delta(O_{a},O_{b})} \tag{16}\]  
The next step involves calculating distances in the hyperplane \(Y\), generating a new \(\mathcal{D}\) matrix. As described by Equation (17), the new distance is related to the previous one and the difference between the coordinates of the new point-object:  
\[\delta(x_{i}^{\prime},x_{j}^{\prime})^{\prime}=\sqrt{\delta(O_{i},O_{j})^{2}- (x_{i}-x_{j})^{2}},\ \ \ \ i,j=1,\ldots,n \tag{17}\]  
Lastly, other dimensions can be generated by applying the same process. For example, according to Figure 2, starting now with the new distance matrix, encountering new pivot objects in a hyperplane \(H\), calculating the position of all objects on the pivot line, and creating another distance matrix. This process guarantees that the current line \(O_{a}O_{b}\), and consequently the hyperplane \(H\) that contains it, is orthogonal to the previous one. The process continues until all \(p\) dimensions are calculated. FastMap is based on classical Euclidean geometry, requiring only data dissimilarities and employing just two representative samples to guarantee orthogonality of dimensions to lead data projection [6]. The algorithm has linear complexity, being faster than other ones. Sadly, it presents high levels of information loss and can not represent nonlinear datasets properly. Figure 2: Projection of \(O_{i}\) and \(O_{j}\) into \(H\) hyperplane that is orthogonal to the previous one.