| Abstract | A greedy-based approach to learn a compact and dis-criminative dictionary for sparse representation is pre-
sented. 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 objec-
tive function. By exploiting the monotonicity and submod-
ularity properties of the objective function and the matroid
constraint, we present a highly efficient greedy-based op-
timization algorithm. It is more than an order of magni-
tude faster than several recently proposed dictionary learn-
ing 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.
|
