# Getting over High-Dimensionality: How Multidimensional Projection Methods Can Assist Data Science
## 4 Multidimensional Projection Approaches and Domains
### Least Square Projection  
The Least Square Projection (LSP) [9] is a nonlinear global projection that preserves neighbor relationships at a high level and allows user interactions. It consists of two steps: (i) a small subset of data samples is carefully chosen and projected with some MDS approach; (ii) the positions of the remaining data instances are calculated with a linear system that considers the previous projected points and a Laplacian matrix operator that maps the neighbor relations of each instance to place it close to its nearest points.  
The initial subset of samples, named here as control points, leads the geometry of the final map, and its position in the projected space significantly impacts the LSP result; thus, they must accurately represent the different groupings of instances from the original space. To select them, a dataset \(X\) with \(n\) instances is split into \(s=\sqrt{n}\) clusters using the _k-medoids_ algorithm [13], and the clusters' medoids are then considered as the control points. According to [PERSON] et al. [9], the definition of \(s\) with the squared root of dataset size can accurately represent the whole dataset, keeping LSP complexity feasible. An MDS technique or a user interaction-based method is applied to lay the control points out, allowing the user to manipulate the mapping process.  
In the next step, LSP maps the remaining instances \(x_{i}\) with a strategy that generates a list \(V_{i}\) with \(k\) neighbors of \(x_{i}\). The coordinates of the projected point \(y_{i}\) are generated through the solution of Equation (24) that bounds \(y_{i}\) points to their neighbor convex hull. Each \(\alpha_{ij}\) weights the impact of neighbors over \(y_{i}\) position and when \(\alpha_{ij}=\frac{1}{|V_{i}|}\), \(y_{i}\) turns into \(V_{i}\) centroid.  
\[y_{i}-\sum_{x_{j}\in V_{i}}\alpha_{ij}y_{j}=0,\quad\text{, being }\ 0\leq\alpha_{ij}\leq 1\ \ \text{ and }\ \ \sum_{j}\alpha_{ij}=1 \tag{24}\]  
The solution of Equation (24) reaches the linear system \(LY=0\), where \(L_{n\times n}\) is a Laplacian matrix (a matrix representation of a graph) and its elements are defined as:  
\[l_{ij}=\begin{cases}1&\text{if }i=j,\\ -\alpha_{ij}&\text{if }x_{j}\in V_{i},\\ 0&\text{otherwise.}\end{cases} \tag{25}\]  
Sadly, \(L\) has no geometric information, and the system solutions can be useless. This issue is handled through the insertion of new lines in \(L\) containing geometric information of the projected control points turning the Laplacian system into a new non-homogeneous system \(AY=b\), where \(A=\left[\frac{L}{5}\right]\), \(S_{s\times n}\), and \(b\) vector (let us consider \(\bar{Y}\) the inner product space) defined as:  
\[s_{ij}=\begin{cases}1&\text{if }y_{j}\in\bar{Y},\\ 0&\text{otherwise.}\end{cases}\ \ \ \ \text{e }\ \ \ b_{i}=\begin{cases}0&\text{if }i\leq n,\\ y_{i}&\text{otherwise.}\end{cases} \tag{26}\]  
LSP calculates the system solution with the least square method [68] minimizing \(\left\|AY-b\right\|^{2}\) since an exact solution is unlikely. As a result, the final system is sparse and symmetric, which facilitates an interactive solution [9].  
LSP presents a good level o neighbor preservation, but there are \(n\) variables to solve the system with an \(O(n^{2})\) complexity, which is infeasible in huge datasets [6]. Then, [PERSON] et al. [71] created _Piecewise Laplacian-based Projection_ (PLP) to mitigate this complexity issue. PLP splits the dataset and maps the subsets with LSP. The spatial coherence is achieved through the initial projection of the control points, and the computer time is reduced because PLP calculates small systems instead of a big and more complex ones. However, this solution is often less accurate than LSP [6].