Manifold Analysis by Topologically Constrained Isometric Embedding

Authors: Guy Rosman, Alexander M. Bronstein, Michael M. Bronstein, Ron Kimmel

Abstract:

We present a new algorithm for nonlinear dimensionality reduction that consistently uses global information, and that enables understanding the intrinsic geometry of non-convex manifolds. Compared to methods that consider only local information, our method appears to be more robust to noise. Unlike most methods that incorporate global information, the proposed approach automatically handles non-convexity of the data manifold. We demonstrate the performance of our algorithm and compare it to state-of-the-art methods on synthetic as well as real data.

Keywords: Dimensionality reduction, manifold learning, multidimensional scaling, geodesic distance, boundary detection.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1080454

References:

[1] R. R. Coifman, S. Lafon, A. B. Lee, M. Maggioni, B. Nadler, F. Warner, and S. W. Zucker, "Geometric diffusions as a tool for harmonic analysis and structure definition of data," Proceedings of the National Academy of Sciences, vol. 102, no. 21, pp. 7426-7431, May 2005.
[2] R. Pless, "Using Isomap to explore video sequences," in Proceedings of the 9th International Conference on Computer Vision, Nice, France, October 2003, pp. 1433-1440.
[3] M. Aharon and R. Kimmel, "Representation analysis and synthesis of lip images using dimensionality reduction," International Journal of Computer Vision, vol. 67, no. 3, pp. 297-312, 2006.
[4] M. Belkin and P. Niyogi, "Laplacian eigenmaps for dimensionality reduction and data representation," 2002.
[Online]. Available: citeseer. ist.psu.edu/article/belkin02laplacian.html
[5] R. M. Diaz and A. Q. Arencibia, Eds., Coloring of DT-MRI FIber Traces using Laplacian Eigenmaps. Las Palmas de Gran Canaria, Spain: Springer Verlag, February 24-28 2003.
[6] A. M. Bronstein, M. M. Bronstein, and R. Kimmel, "Three-dimensional face recognition," International Journal of Computer Vision (IJCV), vol. 64, no. 1, pp. 5-30, August 2005.
[7] R. O. Duda, P. E. Hart, and D. G. Stork, Pattern Classification and Scene Analysis, 2nd ed. Wiley-Interscience, 2000.
[8] S. T. Roweis and L. K. Saul, "Nonlinear dimensionality reduction by locally linear embedding," Science, vol. 290, pp. 2323-2326, 2000.
[9] M. Belkin and P. Niyogi, "Laplacian eigenmaps and spectral techniques for embedding and clustering," in Advances in Neural Information Processing Systems, T. G. Dietterich, S. Becker, and Z. Ghahramani, Eds., vol. 14. Cambridge, MA: MIT Press, 2002, pp. 585-591.
[10] C. Grimes and D. L. Donoho, "Hessian eigenmaps: Locally linear embedding techniques for high-dimensional data," Proceedings of the National Academy of Sciences, vol. 100, no. 10, pp. 5591-5596, May 2003.
[11] K. Q. Weinberger and L. K. Saul, "Unsupervised learning of image manifolds by semidefinite programming," in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, vol. 2. Washington D.C.: IEEE Computer Society, 2004, pp. 988-995.
[12] K. Q. Weinberger, B. D. Packer, and L. K. Saul, "Nonlinear dimensionality reduction by semidefinite programming and kernel matrix factorization," in Proceedings of the 10th International Workshop on Artificial Intelligence and Statistics, Barbados, January 2005.
[13] E. L. Schwartz, A. Shaw, and E. Wolfson, "A numerical solution to the generalized mapmaker-s problem: Flattening nonconvex polyhedral surfaces," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 11, pp. 1005-1008, November 1989.
[14] I. Borg and P. Groenen, Modern multidimensional scaling: Theory and applications. New York: Springer Verlag, 1997.
[15] C. Grimes and D. L. Donoho, "When does isomap recover the natural parameterization of families of articulates images?" Department of Statistics, Stanford University, Stanford, CA 94305-4065, Tech. Rep. 2002-27, 2002.
[16] M. Bernstein, V. de Silva, J. C. Langford, and J. B. Tenenbaum, "Graph approximations to geodesics on embedded manifolds," Stanford University," Technical Report, January 2001.
[17] A. M. Bronstein, M. M. Bronstein, and R. Kimmel, "Generalized multidimensional scaling: a framework for isometry-invariant partial surface matching," Proceedings of the National Academy of Sciences, vol. 103, no. 5, pp. 1168-1172, January 2006.
[18] G. Guy and G. Medioni, "Inference of surfaces, 3D curves, and junctions from sparse, noisy, 3D data," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 19, no. 11, pp. 1265-1277, November 1997.
[19] T. E. Boult and J. R. Kender, "Visual surface reconstruction using sparse depth data," in Computer Vision and Pattern Recognition, vol. 86, 1986, pp. 68-76.
[20] M. M. Bronstein, A. M. Bronstein, and R. Kimmel, "Multigrid multidimensional scaling," Numerical Linear Algebra with Applications (NLAA), vol. 13, no. 2-3, pp. 149-171, March-April 2006.
[21] A. Sidi, "Efficient implementation of minimal polynomial and reduced rank extrapolation methods," J. Comput. Appl. Math., vol. 36, no. 3, pp. 305-337, 1991.
[22] S. Cabay and L. Jackson, "Polynomial extrapolation method for finding limits and antilimits of vector sequences," SIAM Journal on Numerical Analysis, vol. 13, no. 5, pp. 734-752, October 1976.
[23] R. P. Eddy, "Extrapolationg to the limit of a vector sequence," in Information Linkage between Applied Mathematics and Industry, P. C. Wang, Ed. Academic Press, 1979, pp. 387-396.
[24] D. A. Smith, W. F. Ford, and A. Sidi, "Extrapolation methods for vector sequences," SIAM Review, vol. 29, no. 2, pp. 199-233, June 1987.
[25] Y. Eldar, M. Lindenbaum, M. Porat, and Y. Zeevi, "The farthest point strategy for progressive image sampling," IEEE Transactions on Image Processing, vol. 6, no. 9, pp. 1305-1315, September 1997.
[Online]. Available: citeseer.ist.psu.edu/eldar97farthest.html
[26] A. Kearsley, R. Tapia, and M. W. Trosset, "The solution of the metric stress and sstress problems in multidimensional scaling using newton-s method," Computational Statistics, vol. 13, no. 3, pp. 369-396, 1998.
[27] J. B. Tenenbaum, V. de Silva, and J. C. Langford, "A global geometric framework for nonlinear dimensionality reduction," Science, vol. 290, no. 5500, pp. 2319-2323, December 2000.