Locality Preserving Projections. He, Niyogi. NIPS 2003

  1. LPPs are “linear projective maps that arise by solving a variational problem that optimally preserves the neighborhood structure of the data set.”
    1. An alternative to PCA
  2. “When the high dimensional data lies on a low dimensional manifold embedded in the ambient space, the LPP are obtained by finding the optimal linear approximations to the eigenfunctions of the Laplace Beltrami operator <whatever that is, oh its the Laplacian on general spaces, not Euclidian> on the manifold.”
  3. LPP has many data representation properties nonlinear methods like Laplacian Eigenmaps or LLE, but LPP is linear and therefore is defined everywhere and not solely on the data points used for training
  4. Because LPP preserves local structure, nearest-neighbor search in the low dimensional space found by the LPP may be similar to that of the raw high-D space, so NN can be done more cheaply
  5. Fact that LPP is linear makes it “fast and suitable for practical application.”  Other similar methods are nonlinear and don’t have this property
  6. “LPP may be conducted in the original space or in the reproducing kernel Hilbert space (RKHS) into which data points are mapped.  This gives rise to kernel LPP.”
  7. LPP is a linear approximation of nonlinear Laplacian Eigenmap
  8. <LPP, SFA, a number of other methods are unified in: http://link.springer.com/chapter/10.1007%2F978-3-662-44851-9_30>
  9. Construct adjacency graphs either by epsilon-ball or k-nn, either choose weights as unit, or some other method (like Gaussian bump)
  10. Then solve eigenvector problem
  11. “While the Laplace Beltrami for a manifold is generated by the Riemannian metric, for a graph it comes from the adjacency relation.”
  12. <skipping the math>
  13. Kernel LPP generalizes to the nonlinear case

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: