Complexity of Spectral Dimensionality Reduction Algorithms

The following sections provide brief sketches of the computational cost of each of the spectral dimensionality reduction techniques described in Chap. 2. 

For MDS, the computational complexity is dependent not upon the size of the original dimensionality but rather upon the number of data points n. From Sect. 2.2.2 it can be seen that the feature matrix of MDS is of size n x n as it densely describes the Euclidean distance between all data points. Since eigendecomposition is performed on this matrix, the computational complexity of MDS is O(n ). 

To obtain a low-dimensional embedding using Isomap, three steps are followed a fc-nearest neighbour graph is built the shortest path matrix of the neighbourhood graph is computed Anally, eigendecomposition of the shortest path matrix is computed. As such, the computational complexity of each of these parts are considered separately before an overall complexity for Isomap can be obtained. 

The final step of the Isomap algorithm is the eigendecomposition of the shortest path matrix, as with MDS the computational cost of this step is 0 n ). Therefore, the overall complexity of the Isomap algorithm is 0(D log(A )n log(n)) -I- 0 n k + log(n))) + 0 n ) and since only the most computationally expensive term is being considered the complexity of Isomap can be thought of being 0 n ). 

The computational cost of MVU is similar to that of Isomap in many respects. The first step of MVU is to search for the -nearest neighbours, therefore the cost of the first step can be thought of as 0 D log( ) log( )). Also, the final eigendecomposition is performed on an n x n feature matrix so the computational cost of this step is 

---