ROBUST SPARSE HASHING

We study Nearest Neighbors (NN) retrieval by introducing a new approach: Robust Sparse Hashing (RSH). Our approach is inspired by the success of dictionary learning for sparse coding; the key innovation is to use learned sparse codes as hashcodes for speeding up NN. But sparse coding suffers from a major drawback: when data are noisy or uncertain, for a query point, an exact match of the hashcode seldom hap-pens, breaking the NN retrieval. We tackle this difficulty via our novel dictionary learning and sparse coding framework called RSH by learning dictionaries on the robustified coun-terparts of uncertain data points. The algorithm is applied to NN retrieval for Scale Invariant Feature Transform (SIFT) descriptors. The results demonstrate that RSH is noise toler-ant, and at the same time shows promising NN performance over the state-of-the-art. Index Terms — Sparse coding, Robust optimization, Nearest neighbor