Isomap computational cost

The neighbourhood around a point Xj is then iteratively built by adding another point Xj if and only iiOj <6 and (I — QiQf)(Xy — Xj) p < f Xi). Although this method may overcome some of the shortcomings of the parameterless Isomap method, it is not without its own problems. For example, it relies on an angle threshold, 9 that must be supplied, as weU as a relaxation factor, f, that, although can be computed automatically, comes at an extra computational cost. 

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... 

Where MVU differs from Isomap is the construction of the feature matrix F. Recall from Sect. 2.3.2 that the feature matrix is built by solving a semidefiniteprogramming problem. One of the disadvantages of semidefinite programming is the possible large computational cost. The computational cost of semidefinite programming is explained in terms of the number of constraints, c, with the overall complexity being 0(c ) [5]. The number of constraints for MVU is c = [6] so therefore the... 

---