Pattern Search Multidimensional Scaling
This work addresses manifold learning for data analysis, but it is incremental as it modifies an existing method with a new optimization approach.
The paper tackles the problem of nonlinear manifold learning by extending classical multi-dimensional scaling (MDS) with a derivative-free optimization technique, resulting in accurate inference of intrinsic geometry in high-dimensional spaces and state-of-the-art performance on real data under noisy conditions.
We present a novel view of nonlinear manifold learning using derivative-free optimization techniques. Specifically, we propose an extension of the classical multi-dimensional scaling (MDS) method, where instead of performing gradient descent, we sample and evaluate possible "moves" in a sphere of fixed radius for each point in the embedded space. A fixed-point convergence guarantee can be shown by formulating the proposed algorithm as an instance of General Pattern Search (GPS) framework. Evaluation on both clean and noisy synthetic datasets shows that pattern search MDS can accurately infer the intrinsic geometry of manifolds embedded in high-dimensional spaces. Additionally, experiments on real data, even under noisy conditions, demonstrate that the proposed pattern search MDS yields state-of-the-art results.