Manifold Analysis by Topologically Constrained Isometric Embedding
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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:62102", author = "Guy Rosman and Alexander M. Bronstein and Michael M. Bronstein and Ron Kimmel", title = "Manifold Analysis by Topologically Constrained Isometric Embedding", 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.", volume = "2", number = "10", pages = "3559-7", }
