Title :
Submodular dictionary learning for sparse coding
Author :
Jiang, Zhuolin ; Zhang, Guangxiao ; Davis, Larry S.
Author_Institution :
Inst. for Adv. Comput. Studies, Univ. of Maryland, College Park, MD, USA
Abstract :
A greedy-based approach to learn a compact and discriminative dictionary for sparse representation is presented. We propose an objective function consisting of two components: entropy rate of a random walk on a graph and a discriminative term. Dictionary learning is achieved by finding a graph topology which maximizes the objective function. By exploiting the monotonicity and submodularity properties of the objective function and the matroid constraint, we present a highly efficient greedy-based optimization algorithm. It is more than an order of magnitude faster than several recently proposed dictionary learning approaches. Moreover, the greedy algorithm gives a near-optimal solution with a (1/2)-approximation bound. Our approach yields dictionaries having the property that feature points from the same class have very similar sparse codes. Experimental results demonstrate that our approach outperforms several recently proposed dictionary learning techniques for face, action and object category recognition.
Keywords :
dictionaries; graph theory; greedy algorithms; image coding; learning (artificial intelligence); optimisation; action recognition; discriminative dictionary; face recognition; graph topology; greedy-based optimization algorithm; matroid constraint; monotonicity; near-optimal solution; object category recognition; sparse codes; sparse coding; sparse representation; submodular dictionary learning; submodularity property; Dictionaries; Encoding; Entropy; Image color analysis; Matching pursuit algorithms; Partitioning algorithms; Training;
Conference_Titel :
Computer Vision and Pattern Recognition (CVPR), 2012 IEEE Conference on
Conference_Location :
Providence, RI
Print_ISBN :
978-1-4673-1226-4
Electronic_ISBN :
1063-6919
DOI :
10.1109/CVPR.2012.6248082