Fast convolutional sparse coding using matrix inversion lemma

• Interesting alternative to sparse coding for shift-invariant signals (images, audio).
• New fast algorithm, which makes sparse coding feasible even for large problems.
• 3 versions of the algorithm, one of them designed for parallel implementation.
• Convolution kernels can be learned at several scales simultaneously.
• Algorithms are demonstrated on images but can be used for arbitrary signals.

Convolutional sparse coding is an interesting alternative to standard sparse coding in modeling shift-invariant signals, giving impressive results for example in unsupervised learning of visual features. In state-of-the-art methods, the most time-consuming parts include inversion of a linear operator related to convolution. In this article we show how these inversions can be computed non-iteratively in the Fourier domain using the matrix inversion lemma. This greatly speeds up computation and makes convolutional sparse coding computationally feasible even for large problems. The algorithm is derived in three variants, one of them especially suitable for parallel implementation. We demonstrate algorithms on two-dimensional image data but all results hold for signals of arbitrary dimension.