Stochastic Convolutional Sparse Coding

Jinhui Xiong, Peter Richtárik, Wolfgang Heidrich

TL;DR

This paper introduces a novel stochastic spatial-domain solver for Convolutional Sparse Coding (CSC) that significantly speeds up learning by randomly subsampling the sparse codes. This approach overcomes limitations of traditional Fourier-domain methods and scales effectively to large datasets through an online learning variant, achieving substantial runtime improvements without sacrificing reconstruction quality.

What Problem Does This Paper Address?

Convolutional Sparse Coding (CSC) is a powerful technique for learning generative models, particularly for image processing tasks like inpainting and super-resolution. It represents signals as a sum of convolutions of dictionary filters with sparse codes. While effective, existing methods often rely on Fourier-domain solvers to accelerate computations. However, these frequency-domain approaches have drawbacks: they implicitly assume circular boundary conditions, which can be problematic, and they struggle to fully leverage the inherent sparsity of the problem and the small spatial support of the learned filters. This leads to computational inefficiencies and limitations, especially when dealing with large datasets.

Methods

The core innovation of this paper is a stochastic spatial-domain solver for CSC. Instead of processing all sparse codes at once, it introduces a randomized subsampling strategy. In each learning iteration, only a random subset of the sparse codes is considered. This subsampling is achieved using a binary matrix that projects the full set of codes to a random subspace.

The authors propose two main frameworks utilizing this strategy:

  • Stochastic Batch CSC (SBCSC): This is a batch-mode learning approach that processes all training images simultaneously. It alternates between updating the subsampled sparse codes and the dictionary filters. The key advantage here is that by working in the spatial domain and subsampling, it avoids the limitations of Fourier-domain methods and achieves faster computation.
  • Stochastic Online CSC (SOCSC): To address scalability to very large datasets, they extend the SBCSC to an online learning setting. Here, each iteration processes only one or a small mini-batch of training images. This drastically reduces memory and computational requirements per step, making it suitable for massive datasets. To handle the dictionary update efficiently in the online setting, they introduce surrogate matrices that store necessary information without requiring explicit storage of all training data.

Datasets

The paper uses the following datasets:

  • Fruit and City datasets: These are smaller datasets (10 training images of size 100x100) used for initial validation of the proposed algorithms.
  • ImageNet: Patches (1000 images of size 100x100) randomly sampled from ImageNet are used for training and evaluating the online learning algorithms on larger scales.

Key Insights and Ideas

  • Spatial Domain Advantage: By moving back to the spatial domain and employing subsampling, the authors demonstrate that it's possible to overcome the limitations of Fourier-domain methods, particularly in exploiting sparsity and filter support.
  • Sparsity is Key: The inherent sparsity of the sparse codes is the critical property that allows the subsampling strategy to work effectively. Even with a subset of codes, the original signal can still be well-represented, and the learning process converges without significant degradation in quality.
  • Online Learning for Scalability: The online variant of their method is a crucial step towards making CSC practical for the massive datasets encountered in modern machine learning. It decouples computational complexity from the total dataset size.
  • Over-complete Dictionaries: Learning over-complete dictionaries (more filters than necessary for a minimal representation) is shown to be beneficial. These dictionaries capture richer image features, leading to sparser representations and improved reconstruction quality, especially for tasks like image inpainting.

Key Results

  • Speedup: The proposed stochastic spatial-domain solver (SBCSC) achieves significant speedups compared to state-of-the-art frequency-domain solvers. For instance, a subsampling rate of 0.1 provides a 2x speedup over a non-subsampled spatial solver and a 6x speedup over a frequency-domain solver for one iteration. In experiments, SBCSC took 170 seconds for 14 iterations, while a comparable method took 350 seconds.
  • Online Learning Performance: The online version (SOCSC) demonstrates a 6x speedup over a comparable online frequency-domain CSC method, taking 70 seconds compared to 440 seconds to process 10 training images.
  • Reconstruction Quality: Despite the speed improvements, the learning quality is maintained. The paper shows comparable or even improved reconstruction quality (PSNR) when using over-complete dictionaries learned by their method.
  • Sparser Representations: Using over-complete dictionaries leads to approximately 8-10% reduction in the number of non-zero elements in the sparse codes and over 1 dB improvement in reconstruction PSNR on average.

Limitations and Future Work

  • Subsampling Rate Trade-off: The paper notes that a more aggressive subsampling rate leads to slower convergence and a higher objective value, indicating a trade-off between speed and convergence. The authors suggest that a rate between p=0.1 and p=0.2 offers a good balance.
  • Mini-batching for Further Speedup: The authors propose mini-batching as a practical extension for SOCSC, showing that larger mini-batch sizes can lead to faster convergence, with η=20 achieving an order of magnitude speedup over η=1. They suggest this can be further accelerated in a distributed computing system.
  • LASSO Subproblem Acceleration: The paper mentions that the subproblem of updating sparse codes is a highly sparse LASSO problem, and further acceleration could be achieved by employing specialized optimization strategies for LASSO, such as coordinate descent with safe screening.
  • General Applicability: While demonstrated for image tasks, the authors believe the principles of stochastic subsampling and online learning for CSC have broader applications in audio and other signal processing tasks.

Summary updated

Abstract

State-of-the-art methods for Convolutional Sparse Coding usually employ Fourier-domain solvers in order to speed up the convolution operators. However, this approach is not without shortcomings. For example, Fourier-domain representations implicitly assume circular boundary conditions and make it hard to fully exploit the sparsity of the problem as well as the small spatial support of the filters. In this work, we propose a novel stochastic spatial-domain solver, in which a randomized subsampling strategy is introduced during the learning sparse codes. Afterwards, we extend the proposed strategy in conjunction with online learning, scaling the CSC model up to very large sample sizes. In both cases, we show experimentally that the proposed subsampling strategy, with a reasonable selection of the subsampling rate, outperforms the state-of-the-art frequency-domain solvers in terms of execution time without losing the learning quality. Finally, we evaluate the effectiveness of the over-complete dictionary learned from large-scale datasets, which demonstrates an improved sparse representation of the natural images on account of more abundant learned image features.
BibTeX
@inproceedings{xiong2019stochastic,
  author = {Jinhui Xiong and Peter Richtárik and Wolfgang Heidrich},
  title = {{Stochastic Convolutional Sparse Coding}},
  booktitle = {VMV},
  year = {2019},
  url = {https://openreview.net/forum?id=v671z1UJxN},
}
Figure