Sparse coding is a widespread framework in signal and image processing. For instance, it has been employed in image/video classification to decompose visual feature vectors, such as local gradient descriptors into a linear combination of few elements of an over-complete basis, which is called dictionary. In order to learn such sparse representations, greedy algorithms like Orthogonal Matching Pursuit (OMP) have been successfully proposed, and are now widely used for several applications. In this paper, we address the problem of sparse coding of a large number of high-dimensional data onto a large dictionary, which would require computing a huge number of inner products according to the standard formulation. Namely, we drastically reduce the computational cost of searching for the maximum inner product, which is the main computational bottleneck of OMP, by using a tailored data structure allowing for fast, high-quality approximate search. We validated our approach, called IP-TREE-OMP, both on synthetic and on real image data, with very promising results on both.

Inner product tree for improved Orthogonal Matching Pursuit

Sona, Diego;
2012

Abstract

Sparse coding is a widespread framework in signal and image processing. For instance, it has been employed in image/video classification to decompose visual feature vectors, such as local gradient descriptors into a linear combination of few elements of an over-complete basis, which is called dictionary. In order to learn such sparse representations, greedy algorithms like Orthogonal Matching Pursuit (OMP) have been successfully proposed, and are now widely used for several applications. In this paper, we address the problem of sparse coding of a large number of high-dimensional data onto a large dictionary, which would require computing a huge number of inner products according to the standard formulation. Namely, we drastically reduce the computational cost of searching for the maximum inner product, which is the main computational bottleneck of OMP, by using a tailored data structure allowing for fast, high-quality approximate search. We validated our approach, called IP-TREE-OMP, both on synthetic and on real image data, with very promising results on both.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11582/251438
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
social impact