# Dimensionality Reduction for Optimally Preserving KNN

Do any dimensionality reduction techniques find embeddings which optimally preserve the K-nearest neighbors of each point? If no algorithm provably does this, are there algorithms which heuristically achieve this more often than, say, PCA?

I imagine that an algorithm which builds the nearest neighbors graph and then uses this to find a new embedding would do something like this.

(I'd also be interested in a python library implementing any such algorithm)

• Maybe random projections? It has guarantees on the pair-wise distance between points on the projected points. en.wikipedia.org/wiki/Random_projection. You can also look at MDS (Multi dimensional scaling). – t.f Mar 7 at 16:19

Some manifold learning algorithms (Isomap, LLE, LTSA, Hessian Eigenmaps, I think they are collectively called spectral dimensionality reduction) should in principle do this - this is because they actually use $$k$$NN graph. This results in algorithm that preserves local structure rather than global one (they aim at distorting smaller distances less than big distances, kind of reverse of what PCA does).
• construct a pairwise distance/similarity matrix $$M$$
• perform some kind of matrix decomposition on $$M$$ (like SVD for example).
For constructing $$M$$ these algorithms use neighborhood graph: run $$k$$NN for some $$k$$ and then make graph where $$x,y$$ are connected if $$x$$ is in $$k$$-neighborhood of $$y$$ or vice versa. Then they run an algorithm for finding distances in this graph.