Fast decomposed gradient projection algorithm for sparse representation

Abstract

Finding the sparse representation of a signal on an over-complete dictionary plays a very important role in many problems, such as pattern recognition and compressive sensing. In this paper we propose a novel technique called fast decomposed gradient projection algorithm (FDGP) to solve the sparse representation problem by minimizing a bound-constrained quadratic problem (BCQP) containing a quadratic error term and a regularization term. Different from the original gradient projection method, FDGP iterates from an all-zero vector and only updates the positions that are most likely nonzero in each iteration. In view of that the sparse solution usually contains a very small number of nonzero elements, the proposed method can efficiently improve convergence rate of the gradient projection method for sparse representation especially on large scale problems. As we will show, the complexity of the proposed method can be little influenced by the size of the dictionary and only depends on the sparsity of a given signal. Experimental results show the proposed methods can achieve effective and efficient decomposition performance under the over-complete dictionary.