Maximum Variance Unfolding Variants

As described above, the original MVU algorithm can be very computationally expensive as performing semidefinite programming on an n x n matrix leads to a complexity of 0 nk) ). Therefore, a landmark approach to MVU has been presented that seeks to decrease the complexity of MVU and thus enable it to be used for a broader class of problems [26]. So called Landmark MVU (L-MVU) seeks to work on a random subset of m landmarks so that the feature matrix F can be reformed as 

The semidefinite programming problem is then performed on the matrix QLQ. The transformation matrix Q is derived by a sparse weighted graph whose nodes represents the n data points and the edges are used to propagate the positions of the m landmarks onto the remaining n — m nodes [26]. The use of the smaller m x m inner product matrix L allows for an order of magnitude reduction in computation time and also allows for MVU to be used on a previously unusable class of datasets. 

---