Pattern Search Multidimensional Scaling
  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.
