Outline Preliminaries MDS approximations LMDS and FastMap are Nystrom approximation Some results References MDS approximations for sparse similarity graphs Elio Damaggio May 3 2007 Paper presentation for CSE291f Spring 2007 University of California San Diego Elio Damaggio MDS approximations for sparse similarity graphs Outline Preliminaries MDS approximations LMDS and FastMap are Nystrom approximation Some results References 1 Preliminaries Motivation Classical MDS review 2 MDS approximations Main idea Landmark MDS FastMap Complexity 3 LMDS and FastMap are Nystrom approximation Nystrom approximation LMDS FastMap 4 Some results 5 References Elio Damaggio MDS approximations for sparse similarity graphs Outline Preliminaries MDS approximations LMDS and FastMap are Nystrom approximation Some results References Motivation Classical MDS review Our data In 1 the data is a big graph 267K nodes 3 22M edges of similarities between songs and artists We want to embed these data in order to perform interpolation playlist generation Also for visualization compression Elio Damaggio MDS approximations for sparse similarity graphs Outline Preliminaries MDS approximations LMDS and FastMap are Nystrom approximation Some results References Motivation Classical MDS review Motivating the presentation structure In 1 Platt proposes the use of FastMap instead of LandmarkMDS to perform fast embedding of very large sparse graphs FastMap and LandmarkMDS are both approximations of MDS Sparse graphs can arise in many different contexts Isomap human generated data I will present the two approximations and the experimental comparison Elio Damaggio MDS approximations for sparse similarity graphs Outline Preliminaries MDS approximations LMDS and FastMap are Nystrom approximation Some results References Motivation Classical MDS review Classical MDS Input nxn matrix n of squared distances n ij Dn 2ij Construct mean centered inner product matrix 1 Bn Hn n Hn 2 Hn Hn ij ij 1 n Compute k largest eigenvalues vectors of Bn vi i k dimensional embedding is given by the columns of 1 v 1 T 2 v 1 T Lk T k v k Elio Damaggio MDS approximations for sparse similarity graphs Outline Preliminaries MDS approximations LMDS and FastMap are Nystrom approximation Some results References Main idea Landmark MDS FastMap Complexity Analyzing MDS application Computing the full distance matrix Floyd O N 3 Dijkstra on every node O NMlogN MDS on NxN matrix O N 2 Kd K iterations d embedding dimensionality The approximations will try to avoid both bottlenecks by considering a subset of points Elio Damaggio MDS approximations for sparse similarity graphs Outline Preliminaries MDS approximations LMDS and FastMap are Nystrom approximation Some results References Main idea Landmark MDS FastMap Complexity Landmarks intuition Observation In a d dimensional space we can derive the coordinates of a point given its distances from d 1 points with known coordinates Pick m landmark points and perform classical MDS on them Given these points embed the other ones Not a perfect solution A d dimensional perfect embedding may not be possible Landmark points should be in a general position their span should be a d dimensional sub space Usually the of landmarks is increased for stability Elio Damaggio MDS approximations for sparse similarity graphs Outline Preliminaries MDS approximations LMDS and FastMap are Nystrom approximation Some results References Main idea Landmark MDS FastMap Complexity Distance based triangulation After performing MDS on m landmark point embedding the other points is just a linear transformation P Let 1 n be the columns of n n1 k k Let L k be the pseudo inverse transpose of Lk which is L k Elio Damaggio v 1 T 1 v 2 T 2 T v k k MDS approximations for sparse similarity graphs Outline Preliminaries MDS approximations LMDS and FastMap are Nystrom approximation Some results References Main idea Landmark MDS FastMap Complexity Distance based triangulation continued After performing MDS on m landmark point embedding the other points is just a linear transformation Input a vector a of distances from the landmarks for a new point to be embedded Output the embedding is just 1 x a L a 2 k Elio Damaggio MDS approximations for sparse similarity graphs Outline Preliminaries MDS approximations LMDS and FastMap are Nystrom approximation Some results References Main idea Landmark MDS FastMap Complexity Proof Show that i th component of 12 L k a is equal to the projection of y a additional data point on the i th principal axis 1 v i T a p i T y a 2 i Compute j th entries of a and yj 2 a j y a 2 2 yj T y a j n n k k 1X 1X y k 2 2 yj T y k yj 2 n n Elio Damaggio MDS approximations for sparse similarity graphs Outline Preliminaries MDS approximations LMDS and FastMap are Nystrom approximation Some results References Main idea Landmark MDS FastMap Complexity Proof continued Remember y 1 y n are the landmark points coordinates column of Y Lk Principal axes p i are given by the eigenvectors of YY T So i v i T p i T Y Subtract a and a c 1 2Y T y a P where c y a 2 n1 nk y k 2 Elio Damaggio MDS approximations for sparse similarity graphs Outline Preliminaries MDS approximations LMDS and FastMap are Nystrom approximation Some results References Main idea Landmark MDS FastMap Complexity Proof continued Notice that 1 is an eigenvector of the inner product matrix with eigenvalue 0 It follows that v i T 1 0 so substituting a we have p i T YY T y a i p i T y a This is true because pi is the i th eigenvector with eigenvalue i Elio Damaggio MDS approximations for sparse similarity graphs Outline Preliminaries MDS approximations LMDS and FastMap are Nystrom approximation Some results References Main idea Landmark MDS FastMap Complexity LMDS accuracy Elio Damaggio MDS approximations for sparse similarity graphs Outline Preliminaries MDS approximations LMDS and FastMap are Nystrom approximation Some results References Main idea Landmark MDS FastMap Complexity FastMap algorithm main idea FastMap creates a k dimensional embedding iterating k times Estimation of the principal eigenvector Computation of the coordinates of the points relative to it Computation of the nxn distances in the subspace orthogonal to the eigenvector Elio Damaggio MDS approximations for sparse similarity graphs Outline Preliminaries MDS approximations LMDS and FastMap are Nystrom approximation Some results References Main idea Landmark MDS FastMap Complexity Estimation of the principal eigenvector The
View Full Document
Unlocking...