TR2005-117

Nonrigid Embeddings for Dimensionality Reduction

    •  Brand, M., "Nonrigid Embeddings for Dimensionality Reduction", European Conference on Machine Learning (ECML), October 2005, vol. 3720.
      BibTeX TR2005-117 PDF
      • @inproceedings{Brand2005oct,
      • author = {Brand, M.},
      • title = {Nonrigid Embeddings for Dimensionality Reduction},
      • booktitle = {European Conference on Machine Learning (ECML)},
      • year = 2005,
      • volume = 3720,
      • month = oct,
      • isbn = {3-540-29243-8},
      • url = {https://www.merl.com/publications/TR2005-117}
      • }
  • MERL Contact:
TR Image
This paper shows how to obtain well-conditioned problems from very sparse neighborhood graphs and combine them with distance constraints to obtain high quality solutions in linear time
Abstract:

Spectral methods for embedding graphs and immersing data manifolds in low-dimensional speaces are notoriously unstable due to insufficient and/or numberically ill-conditioned constraint sets. Why show shy this is endemic to spectral methods, and develop low-complexity solutions for stiffening ill-conditioned problems and regulatizing ill-posed problems, with proofs of correctness. The regularization exploits sparse but complementary constraints on affine rigidity and edge lengths to obtain isometric embeddings. Am implemented algorithm is fast, accurate and industrial-strength: Experiments with problem sizes spanning four orders of magnitude show O (N) scaling. We demonstrate with speech data.

 

  • Related News & Events

    •  NEWS    ECML 2005: publication by Matthew Brand
      Date: October 3, 2005
      Where: European Conference on Machine Learning (ECML)
      MERL Contact: Matthew Brand
      Brief
      • The paper "Nonrigid Embeddings for Dimensionality Reduction" by Brand, M. was presented at the European Conference on Machine Learning (ECML).
    •