I have N small floating point vectors of length K (typically, N is in the millions and K=9). I need to compute a lot (millions and millions) of squared euclidean distances between those vectors. It would be great if i could reduce this 9-vector elements to, say, length 3 or 4. I was thinking about PCA. I could pre-compute and store the reduced vectors and then proceed with the distances computation. Could this work? For instances, each of those vectors is a vectorized 3x3 patch around given pixel of a natural image. A patch is created for every pixel. In your opinion, could this work?
4
-
$\begingroup$ Why don't you try it? It seems you have a fairly good idea about what to do. Check the computed eigenvalues (scree-plot). That should be a first check if this dimensional reduction is fruitful. $\endgroup$– usεr11852Commented Jul 22, 2016 at 18:42
-
2$\begingroup$ This won't work, most likely. PCA or other compression (reduction) techniques will be slower than distance calculation. $\endgroup$– AksakalCommented Jul 22, 2016 at 19:06
-
$\begingroup$ @Aksakal: If the OP precomputes his basis, it might work. I haven't tried it myself and $K = 9$ is a bit too restrictive but I am not sure it is full right-off. Have you tried it? $\endgroup$– usεr11852Commented Jul 22, 2016 at 21:28
-
2$\begingroup$ May I point out that if you $N$ is in the millions (say 10), the relevant pairwise distances matrix probably would hold $N^2$ entries so... in double precision you would be in the TBytes area... are you use want to do this? Is it something else in the problem you are trying to solve that you do not tell us? $\endgroup$– usεr11852Commented Jul 25, 2016 at 0:46
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
For the image problem, a common technique used is sparse coding (Andrew Ng ppt) for dimension reduction. Maybe a sparse autoencoder, if you feel the sparse coding performance is not powerful enough.
Sounds like you are trying some convolutional neural network. Did you do something along the lines of the description here and it was not effective?.
Sparse Coding Scikit-learn implementation
-Edit Sorry, I didn't read all the way through. I am not sure what you are trying to do by computing the squared euclidean distances between the vectors. I am not sure what is applicable anymore, but sparse coding still might be a viable solution and PCA is definitely worth trying since it is computationally less expensive.
answered Jul 22, 2016 at 18:46