Universal Multi-Dimensional Scaling

author: Arvind Agarwal, School of Computing, University of Utah
published: Oct. 1, 2010,   recorded: July 2010,   views: 3203

Related Open Educational Resources

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.


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 O((1/eps2) log n)-dimensional sphere causes only an eps-distortion in the geodesic distances.

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Reviews and comments:

Comment1 smilesdl, June 7, 2013 at 3:41 p.m.:

Interesting topic and presentation, It would be great if the sound and video quality were better. In particular the slides being presented. Tt is hard to understand due to the quality of the sound. And the slides are not presented on their own but through the video.

Write your own review or comment:

make sure you have javascript enabled or clear this field: