From: rif@mit.edu   
      
   ajit_v_rROMEO@yahoo.co.uk (ajit) writes:   
      
   > Hello,   
   >   
   > I have a query about some of the extensions of the ISOMAP algorithm. I   
   > basically have around N = 17000 points, each in D-dimensional space (D   
   > being 400) which supposedly lie on a manifold. I wish to use ISOMAP to   
   > project these points onto a d-dimensional space (d << D :  'd' could   
   > be around 40 or less). My problem is that the basic ISOMAP algorithm   
   > requires the computation (and storage) of a pairwise geodesic-distance   
   > matrix, which in this case would be very large, i.e. 17000 * 17000. I   
   > came to know about landmark ISOMAP, an extension of ISOMAP in which   
   > one needs to compute the matrix of geodesic distances to only some   
   > selected 'n' "landmark points" (where n << N).   
   >   
   > My problem is that even this modification would still require me to   
   > first compute a large N by N matrix of pairwise Euclidian distances   
   > (and I will then apply Dijkstra's shortest path algorithm to obtain   
   > the geodesic distances). Of course, I could keep computing the   
   > Euclidian distances from one point to all others, every single time,   
   > while running the Dijkstra's algorithm, but that is going to be very   
   > time consuming.   
   >   
   > Is there a way out?   
   >   
   >   
      
   You may be misinterpreting the Landmark Isomap algorithm.  Looking at   
   "Global versus local methods in nonlinear dimensionality reduction,"   
   by de Silva and Tenenbaum, they suggest starting with a neighborhood   
   graph G which is already itself sparse.  Instead of storing all the   
   distances in this neighborhood graph, only the k closest neighbors of   
   each point are stored.  Therefore, this step is always tractable,   
   assuming you believe that O(N^2 D) work is tractable for very large   
   datasets.   
      
   The original ISOMAP then requires the computation of a dense N by N   
   matrix of geodesic distances.  Landmark ISOMAP's modification is in   
   this step --- the geodesic matrix is only a L by N dense matrix, where   
   L is the number of landmarks.   
      
   Hope this helps.   
      
   Cheers,   
      
   rif   
      
   [ comp.ai is moderated.  To submit, just post and be patient, or if ]   
   [ that fails mail your article to , and ]   
   [ ask your news administrator to fix the problems with your system. ]   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)