suresh at cs utah edu
Ph: 801 581 8233
Room 3404, School of Computing
50 S. Central Campus Drive,
Salt Lake City, UT 84112.
Universal Multi-Dimensional Scaling
Saturday February 06th 2010, 2:15 am
Filed under: Papers

[author]Arvind Agarwal, Jeff Phillips and Suresh Venkatasubramanian[/author] In 16th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), 2010

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.

Links: KDD 2010 final version, and Extended version on arxiv.

Code: MATLAB code for MDS in Euclidean space (Some utility functions useful for testing). It generalizes to the other cost functions and spaces by replacing the appropriate subroutines (computeIntersections and mean).


No Comments so far

Leave a comment
Line and paragraph breaks automatic, e-mail address never displayed, HTML allowed: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>