I had a question about dimensionality reduction for finding nearest neighbors and was hoping someone could help me out here.
Suppose I have good features for images, say penultimate layer features from VGG-16 trained on ImageNet classification. I want to find nearest neighbors in this space, however, it is of dimensionality 4096, and this makes life hard when the number of data points is large, say a million. Given this, I would like to reduce the dimensionality of the features, to something really small, say 2 or 3.
PCA would not be a good choice as this focuses on preserving directions of highest variance and I am really interested in
preserving pairwise distances because I want to use this for NN search.
t-SNE, commonly used for visualization of high dimensional data, can reduce points to 2/3 dimensions. However, the author warns that
Notice that t-SNE does not retain distances but probabilities, so measuring some error between the Euclidean distances in high-D and low-D is useless.
Here's my question: Is the above concern really valid if I am only interested in retrieving the local neighborhood around a point? After all, t-SNE preserves the local structure of data. Further, is there something better than t-SNE if I want to go to such low dimensions? I just need something that can maintain pairwise distance / similarity while going down to a few dimensions.