2010/03/02 by Arvind Agarwal, Agarwal, Arvind, Jeff M. Phillips +3
Computer Science · Engineering · #Advanced Image and Video Retrieval Techniques #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Computer Vision and Pattern Recognition (cs.CV) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Robotics and Sensor-Based Localization #cs.CG #cs.CV #cs.LG
paper · pdf · doi:10.48550/arxiv.1003.0529
18 pages, 7 figures. This version fixes a bug in the proof of Theorem 6.1 (dimensionality reduction for spherical data). The statement of the result remains the same.
openalex publication_date 2010/03/02 · arxiv created 2010/03/30 · arxiv updated 2010/03/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we propose a unified algorithmic framework for solving many known variants of \mds. Our algorithm is a simple iterative scheme with guaranteed convergence, and is modular; by changing the internals of a single subroutine in the algorithm, we can switch cost functions and target spaces easily. In addition to the formal guarantees of convergence, our algorithms are accurate; in most cases, they converge to better quality solutions than existing methods, in comparable time. We expect that this framework will be useful for a number of \mds variants that have not yet been studied. Our framework extends to embedding high-dimensional points lying on a sphere to points on a lower dimensional sphere, preserving geodesic distances. As a compliment to this result, we also extend the Johnson-Lindenstrauss Lemma to this spherical setting, where projecting to a random O((1/\eps2) log n)-dimensional sphere causes \eps-distortion.