Speeding Up Graph Regularized Sparse Coding by Dual Gradient Ascent

Graph regularized Sparse Coding (GSC) considers data relationships during Sparse Coding (SC) and thus has better performance in certain image analysis tasks. However, it is very time consuming. This letter aims at speeding up GSC. The alternating optimization framework for GSC involves repeatedly solving a variant of ${\ell _1}$ minimization referred to as GSRsub in this letter. Traditional ways to deal with GSRsub are to generalize optimization strategies for ${\ell _1}$ minimization to solve its primal problem that is strongly convex but non-differentiable, thus converging slowly. We propose that GSC can be accelerated by solving a new dual problem of GSRsub called D-GSRsub. Compared with the primal form and the existing dual form of GSRsub, D-GSRsub has a strongly convex and smooth objective function with less variables. Based on these properties, four dual gradient ascent strategies with lower computational complexities are developed. Experimental results on real-world datasets demonstrate that these strategies can dramatically and stably speed up GSC without affecting its performance in the corresponding image analysis tasks.