Learning orthogonal sparse representations by using geodesic flow optimization

In this paper we propose the novel algorithm GF-OSC, which learns an orthogonal basis that provides an optimal K-sparse data representation for a given set of training samples. The underlying optimization problem is composed of two nested subproblems: (i) given a basis, to determine an optimal K-sparse coefficient vector for each data sample, and (ii) given a K-sparse coefficient vector for each data sample, to determine an optimal basis. Both subproblems have closed form solutions, which can be computed alternately in an iterative manner. Due to the nesting of the subproblems, however, this approach can only find an optimal solution if the underlying sparsity level is sufficiently high. To overcome this shortcoming, our GF-OSC algorithm solves subproblem (ii) via gradient descent on the corresponding cost function within the underlying lower dimensional space of free dictionary parameters. This algorithmic substep is based on the geodesic flow optimization framework proposed by Plumbley. On synthetic data, we show in a comparison with four alternative learning algorithms the superior recovery performance of GF-OSC and show that it needs significantly fewer learning epochs to converge. Furthermore, we demonstrate the potential of GF-OSC for image compression. For five standard test images, we derived sparse image approximations based on a GF-OSC basis that was trained on natural image patches. In terms of PSNR, the approximation performance of the GF-OSC basis is between 0.09 to 0.32 dB higher compared to using the 2D DCT basis, and between 1.66 to 3.4 dB higher compared to using the 2D Haar wavelet basis.