Bag of Pursuits and Neural Gas for Improved Sparse Coding

Sparse coding employs low-dimensional subspaces in order to encode high-dimensional signals. Finding the optimal subspaces is a difficult optimization task. We show that stochastic gradient descent is superior in finding the optimal subspaces compared to MOD and K-SVD, which are both state-of-the art methods. The improvement is most significant in the difficult setting of highly overlapping subspaces. We introduce the so-called ``Bag of Pursuits'' that is derived from Orthogonal Matching Pursuit. It provides an improved approximation of the optimal sparse coefficients, which, in turn, significantly improves the performance of the gradient descent approach as well as MOD and K-SVD. In addition, the ``Bag of Pursuits'' allows to employ a generalized version of the Neural Gas algorithm for sparse coding, which finally leads to an even more powerful method.