cvpr cvpr2013 cvpr2013-87 cvpr2013-87-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Yue Lin, Rong Jin, Deng Cai, Shuicheng Yan, Xuelong Li
Abstract: Recent studies have shown that hashing methods are effective for high dimensional nearest neighbor search. A common problem shared by many existing hashing methods is that in order to achieve a satisfied performance, a large number of hash tables (i.e., long codewords) are required. To address this challenge, in this paper we propose a novel approach called Compressed Hashing by exploring the techniques of sparse coding and compressed sensing. In particular, we introduce a sparse coding scheme, based on the approximation theory of integral operator, that generate sparse representation for high dimensional vectors. We then project sparse codes into a low dimensional space by effectively exploring the Restricted Isometry Property (RIP), a key property in compressed sensing theory. Both of the theoretical analysis and the empirical studies on two large data sets show that the proposed approach is more effective than the state-of-the-art hashing algorithms.
[1] A. Andoni and P. Indyk. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Commun. ACM, 51(1): 117–122, 2008.
[2] E. Cand e`s. The restricted isometry property and its implications for compressed sensing. Comptes Rendus Mathematique, 346:589–592, 2008.
[3] E. Candes and T. Tao. Decoding by linear programming. IEEE Transactions on Information Theory, 51:4203 4215, 2005.
[4] E. J. Cand e`s, L. Demanet, and L. Ying. Fast computation of fourier integral operators. SIAM J. Scientific Computing, 29(6):2464–2493, 2007.
[5] M. Charikar. Similarity estimation techniques from rounding algorithms. In STOC, pages 380–388, 2002.
[6] M. Datar, N. Immorlica, P. Indyk, and V. S. Mirrokni. Locality-sensitive hashing scheme based on p-stable distributions. In SCG, pages 253–262, 2004.
[7] D. Donoho. Compressed sensing. IEEE Transactions on Information Theory, 52: 1289–1306, 2006.
[8] D. L. Donoho and M. Elad. Optimally sparse representation in general (non-orthogonal) dictionaries via ?1 minimization. In PNAS, pages 2197–2202, 2003.
[9] J.-P. Heo, Y. Lee, J. He, S.-F. Chang, and S.-E. Yoon. Spherical hashing. In CVPR, pages 2957–2964, 2012.
[10] W. Johnson and J. Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space. Contemporary mathematics, 26: 189–206, 1984.
[11] A. Joly and O. Buisson. Random maximum margin hashing. In CVPR, pages 873–880, 2011.
[12] B. Kulis and K. Grauman. Kernelized locality-sensitive hashing for scalable image search. In ICCV, 2009.
[13] W. Liu, J. Wang, R. Ji, Y.-G. Jiang, and S.-F. Chang. –
[14]
[15]
[16]
[17]
[18]
[19]
[20]
[21] Supervised hashing with kernels. In CVPR, pages 2074– 2081, 2012. W. Liu, J. Wang, S. Kumar, and S.-F. Chang. Hashing with graphs. In ICML, 2011. Q. Lv, W. Josephson, Z. Wang, M. Charikar, and K. Li. Multi-probe lsh: Efficient indexing for high-dimensional similarity search. In VLDB, pages 950–961, 2007. R. Panigrahy. Entropy based nearest neighbor search in high dimensions. In SODA, pages 1186–1 195, 2006. M. Raginsky and S. Lazebnik. Locality-sensitive binary codes from shift-invariant kernels. In NIPS, 2009. S. Smale and D.-X. Zhou. Geometry on probability spaces. Constr Approx, 30:3 11–323, 2009. J. Wang, S. Kumar, and S.-F. Chang. Sequential projection learning for hashing with compact codes. In ICML, 2010. X. Wang, L. Zhang, F. Jing, and W. Ma. Annosearch: Image auto-annotation by search. CVPR, 2, 2006. Y. Weiss, A. Torralba, and R. Fergus. Spectral hashing. In NIPS, pages 1753–1760, 2008. 444454991