|
Multidimensional scaling and manifold learning
Embedding the Swiss roll surface (leftmost) into a 3D Euclidean surface. Shown left to right are the results of four MG MDS iterations.
Multidimensional scaling (MDS) is a generic name for a family of algorithms that construct a configuration of points in a target metric space from information about inter-point distances measured in some other metric space. Large-scale MDS problems often occur in data analysis, representation and visualization. Particularly, MDS is used as a numerical tool for representation of deformable shapes, and for manifold learning.
We have developed a multigrid and vector extrapolation numerical frameworks for MDS problems, which allows efficiently solving such problems. Our approaches outperform by an order of magnitude standard MDS methods.
Many manifold learning procedures try to embed a given feature data into a flat space of low dimensionality while preserving as much as possible the metric in the natural feature space. The embedding process usually relies on distances between neighboring features, mainly since distances between features that are far apart from each other often provide an unreliable estimation of the true distance on the feature manifold due to its non-convexity. We introduced a framework for nonlinear dimensionality reduction that uses both local and global distances in order to learn the intrinsic geometry of flat manifolds with boundaries. The resulting algorithm filters out potentially problematic distances between distant feature points based on the properties of the geodesics connecting those points and their relative distance to the boundary of the feature manifold, thus avoiding an inherent limitation of other approaches such as Isomap. Since the proposed algorithm matches non-local structures, it is robust to strong noise. We show experimental results demonstrating the advantages of the proposed approach over conventional dimensionality reduction techniques, both global and local in nature.
Papers
G. Rosman, M. M. Bronstein, A. M. Bronstein, R. Kimmel,
"Nonlinear dimensionality reduction by topologically
constrained isometric embedding", Intl. Journal of Computer Vision (IJCV), Vol. 89/1, pp. 56-68, August 2010.
G. Rosman, A. M. Bronstein, M. M. Bronstein, R. Kimmel,
"Topologically constrained isometric embedding",
In Human Motion Understanding, Modelling, Capture, and Animation, Computational Imaging and Vision, Vol. 36, Springer, pp. 243-262, 2008.
M. M. Bronstein, A. M. Bronstein, R. Kimmel, I. Yavneh,
"Multigrid multi-dimensional scaling",
Numerical Linear Algebra with Applications (NLAA), Special issue on multigrid methods, Vol. 13/2-3, pp. 149-171, March-April 2006.
M. M. Bronstein, A. M. Bronstein, R. Kimmel, I. Yavneh,
"A multigrid approach for multi-dimensional scaling",
Proc. Copper Mountain Conf. Multigrid Methods, 2005.
Patents
G. Rosman, A. Bronstein, M. Bronstein, R. Kimmel,
"Acceleration of multidimensional scaling by vector extrapolation techniques", US Patent application US2009037507, May 2009.
Software
Accelerated MDS matlab code
See also
Non-rigid shape similarity and correspondence
|