Efficient nearest neighbors via robust sparse hashing

Anoop Cherian, Suvrit Sra, Vassilios Morellas, Nikolaos P Papanikolopoulos

Research output: Contribution to journalArticle

13 Citations (Scopus)

Abstract

This paper presents a new nearest neighbor (NN) retrieval framework: robust sparse hashing (RSH). Our approach is inspired by the success of dictionary learning for sparse coding. Our key idea is to sparse code the data using a learned dictionary, and then to generate hash codes out of these sparse codes for accurate and fast NN retrieval. But, direct application of sparse coding to NN retrieval poses a technical difficulty: when data are noisy or uncertain (which is the case with most real-world data sets), for a query point, an exact match of the hash code generated from the sparse code seldom happens, thereby breaking the NN retrieval. Borrowing ideas from robust optimization theory, we circumvent this difficulty via our novel robust dictionary learning and sparse coding framework called RSH, by learning dictionaries on the robustified counterparts of the perturbed data points. The algorithm is applied to NN retrieval on both simulated and real-world data. Our results demonstrate that RSH holds significant promise for efficient NN retrieval against the state of the art.

Original languageEnglish (US)
Article number6824781
Pages (from-to)3646-3655
Number of pages10
JournalIEEE Transactions on Image Processing
Volume23
Issue number8
DOIs
StatePublished - Jan 1 2014

Fingerprint

Glossaries

Keywords

  • Dictionary learning
  • nearest neighbors.
  • robust optimization
  • sparse coding

Cite this

Efficient nearest neighbors via robust sparse hashing. / Cherian, Anoop; Sra, Suvrit; Morellas, Vassilios; Papanikolopoulos, Nikolaos P.

In: IEEE Transactions on Image Processing, Vol. 23, No. 8, 6824781, 01.01.2014, p. 3646-3655.

Research output: Contribution to journalArticle

Cherian, Anoop ; Sra, Suvrit ; Morellas, Vassilios ; Papanikolopoulos, Nikolaos P. / Efficient nearest neighbors via robust sparse hashing. In: IEEE Transactions on Image Processing. 2014 ; Vol. 23, No. 8. pp. 3646-3655.
@article{5c4bbde24b9846a9b997522306e9b64f,
title = "Efficient nearest neighbors via robust sparse hashing",
abstract = "This paper presents a new nearest neighbor (NN) retrieval framework: robust sparse hashing (RSH). Our approach is inspired by the success of dictionary learning for sparse coding. Our key idea is to sparse code the data using a learned dictionary, and then to generate hash codes out of these sparse codes for accurate and fast NN retrieval. But, direct application of sparse coding to NN retrieval poses a technical difficulty: when data are noisy or uncertain (which is the case with most real-world data sets), for a query point, an exact match of the hash code generated from the sparse code seldom happens, thereby breaking the NN retrieval. Borrowing ideas from robust optimization theory, we circumvent this difficulty via our novel robust dictionary learning and sparse coding framework called RSH, by learning dictionaries on the robustified counterparts of the perturbed data points. The algorithm is applied to NN retrieval on both simulated and real-world data. Our results demonstrate that RSH holds significant promise for efficient NN retrieval against the state of the art.",
keywords = "Dictionary learning, nearest neighbors., robust optimization, sparse coding",
author = "Anoop Cherian and Suvrit Sra and Vassilios Morellas and Papanikolopoulos, {Nikolaos P}",
year = "2014",
month = "1",
day = "1",
doi = "10.1109/TIP.2014.2324280",
language = "English (US)",
volume = "23",
pages = "3646--3655",
journal = "IEEE Transactions on Image Processing",
issn = "1057-7149",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "8",

}

TY - JOUR

T1 - Efficient nearest neighbors via robust sparse hashing

AU - Cherian, Anoop

AU - Sra, Suvrit

AU - Morellas, Vassilios

AU - Papanikolopoulos, Nikolaos P

PY - 2014/1/1

Y1 - 2014/1/1

N2 - This paper presents a new nearest neighbor (NN) retrieval framework: robust sparse hashing (RSH). Our approach is inspired by the success of dictionary learning for sparse coding. Our key idea is to sparse code the data using a learned dictionary, and then to generate hash codes out of these sparse codes for accurate and fast NN retrieval. But, direct application of sparse coding to NN retrieval poses a technical difficulty: when data are noisy or uncertain (which is the case with most real-world data sets), for a query point, an exact match of the hash code generated from the sparse code seldom happens, thereby breaking the NN retrieval. Borrowing ideas from robust optimization theory, we circumvent this difficulty via our novel robust dictionary learning and sparse coding framework called RSH, by learning dictionaries on the robustified counterparts of the perturbed data points. The algorithm is applied to NN retrieval on both simulated and real-world data. Our results demonstrate that RSH holds significant promise for efficient NN retrieval against the state of the art.

AB - This paper presents a new nearest neighbor (NN) retrieval framework: robust sparse hashing (RSH). Our approach is inspired by the success of dictionary learning for sparse coding. Our key idea is to sparse code the data using a learned dictionary, and then to generate hash codes out of these sparse codes for accurate and fast NN retrieval. But, direct application of sparse coding to NN retrieval poses a technical difficulty: when data are noisy or uncertain (which is the case with most real-world data sets), for a query point, an exact match of the hash code generated from the sparse code seldom happens, thereby breaking the NN retrieval. Borrowing ideas from robust optimization theory, we circumvent this difficulty via our novel robust dictionary learning and sparse coding framework called RSH, by learning dictionaries on the robustified counterparts of the perturbed data points. The algorithm is applied to NN retrieval on both simulated and real-world data. Our results demonstrate that RSH holds significant promise for efficient NN retrieval against the state of the art.

KW - Dictionary learning

KW - nearest neighbors.

KW - robust optimization

KW - sparse coding

UR - http://www.scopus.com/inward/record.url?scp=84904299600&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84904299600&partnerID=8YFLogxK

U2 - 10.1109/TIP.2014.2324280

DO - 10.1109/TIP.2014.2324280

M3 - Article

VL - 23

SP - 3646

EP - 3655

JO - IEEE Transactions on Image Processing

JF - IEEE Transactions on Image Processing

SN - 1057-7149

IS - 8

M1 - 6824781

ER -