Classical Scaling Revisited

Gil Shamai, Yonathan Aflalo, Michael Zibulevsky, Ron Kimmel

ICCV 2015

doi:10.1109/ICCV.2015.260 /iccv/2015/shamai2015iccv-classical/

Abstract

Multidimensional-scaling (MDS) is an information analysis tool. It involves the evaluation of distances between data points, which is a quadratic space-time problem. Then, MDS procedures find an embedding of the points in a low dimensional Euclidean (flat) domain, optimizing for the similarity of inter-points distances. We present an efficient solver for Classical Scaling (a specific MDS model) by extending the distances measured from a subset of the points to the rest, while exploiting the smoothness property of the distance functions. The smoothness is measured by the L2 norm of the Laplace-Beltrami operator applied to the unknown distance function. The Laplace Beltrami reflects the local differential relations between points, and can be computed in linear time. Classical-scaling is thereby reformulated into a quasi-linear space-time complexities procedure.

PDF ICCV Semantic Scholar

Cite

Text

Shamai et al. "Classical Scaling Revisited." International Conference on Computer Vision, 2015. doi:10.1109/ICCV.2015.260

Markdown

[Shamai et al. "Classical Scaling Revisited." International Conference on Computer Vision, 2015.](https://mlanthology.org/iccv/2015/shamai2015iccv-classical/) doi:10.1109/ICCV.2015.260

BibTeX

@inproceedings{shamai2015iccv-classical,
  title     = {{Classical Scaling Revisited}},
  author    = {Shamai, Gil and Aflalo, Yonathan and Zibulevsky, Michael and Kimmel, Ron},
  booktitle = {International Conference on Computer Vision},
  year      = {2015},
  doi       = {10.1109/ICCV.2015.260},
  url       = {https://mlanthology.org/iccv/2015/shamai2015iccv-classical/}
}