Forward Basis Selection for Sparse Approximation over Dictionary


Xiaotong Yuan, Shuicheng Yan ;
Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, PMLR 22:1377-1388, 2012.


Recently, forward greedy selection method has been successfully applied to approximately solve sparse learning problems, characterized by a trade-off between sparsity and accuracy. In this paper, we generalize this method to the setup of sparse approximation over a pre-fixed dictionary. A fully corrective forward selection algorithm is proposed along with convergence analysis. The per-iteration computational overhead of the proposed algorithm is dominated by a subproblem of linear optimization over the dictionary and a subproblem to optimally adjust the aggregation weights. The former is cheaper in several applications than the Euclidean projection while the latter is typically an unconstrained optimization problem which is relatively easy to solve. Furthermore, we extend the proposed algorithm to the setting of non-negative/convex sparse approximation over a dictionary.Applications of our algorithms to several concrete learning problems are explored with efficiency validated on benchmark data sets.

Related Material