Multidimensional Spectral Hashing

Description

What makes a good similarity-preserving binary code? One option is to define a code as good if Hamming distance matches the original Euclidean distance. In this paper, we have shown that this definition may be problematic, since in applications where we care about retrieving \similar” neighbors, matching all distances exactly may be a waste of bits. Instead we have suggested an alter-native criterion, where the goal is to have Hamming affinity match the desired affinity matrix. We have shown that this leads to an intractable, binary matrix factorization problem but that the spectral relaxation can be used to build excellent codes with very simple learning algorithms.

Results on 1 million Tiny images with 32 bits. Top and Middle left: precision recall curve with T = sigma/4; T = sigma/20. Bottom left: The average rank in terms of Euclidean similarity for the kth neighbor retrieved by each code. Low curves are better. Bottom middle: Expected rank at 100 as a function of number of bits. Low curves are better. Right: 2 randomly selected test images and the retrieved neighbors.

Weiss, Yair, Rob Fergus, and Antonio Torralba. “Multidimensional spectral hashing.” European Conference on Computer Vision. Springer, Berlin, Heidelberg, 2012.

Segmenting moving objects using spectral clustering

MATLAB code for method of spectral ratios for the determination of the fundamental period of soil vibration

https://people.csail.mit.edu/torralba/publications/msh_eccv12.pdf