2010 UniversalMultiDimensionalScalin

• (Agarwal et al., 2010) ⇒ Arvind Agarwal, Jeff M. Phillips, and Suresh Venkatasubramanian. (2010). “Universal Multi-dimensional Scaling.” In: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2010). doi:10.1145/1835804.1835948

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%22Universal+multi-dimensional+scaling%22+2010
• http://portal.acm.org/citation.cfm?id=1835948&preflayout=flat#citedby

Quotes

Author Keywords

Multi-dimensional scaling, dimensionality reduction.

Abstract

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. Moreover, they have a small memory footprint and scale effectively for large data sets. 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 complement to this result, we also extend the Johnson-Lindenstrauss Lemma to this spherical setting, by showing that projecting to a random [math]\displaystyle{ O((1/\varepsilon^2) \log n) }[/math]-dimensional sphere causes only an [math]\displaystyle{ \varepsilon }[/math]-distortion in the geodesic distances.

References

,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2010 UniversalMultiDimensionalScalin	Arvind Agarwal Jeff M. Phillips Suresh Venkatasubramanian			Universal Multi-dimensional Scaling		KDD-2010 Proceedings	http://www.cs.utah.edu/~suresh/papers/smds/kdd10-final.pdf	10.1145/1835804.1835948		2010