Title: Inner product tree for improved Orthogonal Matching Pursuit
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 des...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.Read More
Publication Year: 2012
Publication Date: 2012-11-01
Language: en
Type: article
Access and Citation
Cited By Count: 2
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot