Sparse Coding with Gated Learned ISTA

Kailun Wu, Yiwen Guo, Ziang Li, Changshui ZhangICLR 2020 · OpenReview

Introduction

Sparse coding is the fundamental task of recovering a sparse signal $x_s$ from a noisy observation $y = Ax_s + \epsilon$. While the Iterative Shrinkage-Thresholding Algorithm (ISTA) is the classic solver for this problem, it is notoriously slow to converge. To address this, researchers introduced Learned ISTA (LISTA) in 2010, which "unrolls" the iterations of ISTA into layers of a neural network, allowing the model to learn optimal parameters directly from data.

However, standard LISTA suffers from two hidden weaknesses. First, to ensure the model avoids picking the wrong indices (preventing "false positives" in the support), the learned biases often force the estimated coefficients to be smaller than their true values. Second, because ISTA relies on a conservative upper bound of the objective function, the updates often "lag behind" the optimal solution.

This paper introduces Gated Learned ISTA (GLISTA), an evolution of the unrolled sparse coding algorithm that uses learnable gating mechanisms to fix these exact flaws. By adding gain and overshoot gates, GLISTA achieves faster convergence and significantly lower reconstruction errors across both synthetic and real-world tasks.

The GLISTA Architecture

To bridge the gap between theoretical convergence and practical estimation accuracy, the authors propose incorporating two specific gating mechanisms inspired by Gated Recurrent Units (GRUs):

  1. Gain Gates: These act on the input to the current estimation. The authors theoretically prove that for LISTA to converge without false positives, it must underestimate the magnitudes of the non-zero components. The gain gate ($g_t$) provides a learnable "boost" to these components, allowing the network to scale up its estimations as it becomes more confident in the signal's support.
  2. Overshoot Gates: Standard ISTA uses a fixed, conservative step size (usually $1/L$, where $L$ is the Lipschitz constant). The overshoot gate ($o_t$) allows the network to adaptively "jump" further toward the solution. This effectively implements a learnable, time-varying step size that can safely exceed traditional theoretical limits.
Architectural comparison of standard LISTA, LISTA with overshoot gates, and LISTA with gain gates.

The overall architecture remains an unrolled network, but each layer now includes these gates, which are formulated as functions of the current estimate $x^{(t)}$ and the observation $y$.

Key Insights and Theoretical Grounding

  • The "Requirement of Gains": One of the most interesting theoretical contributions of the paper is Proposition 1. It formally proves that if you want a LISTA-like network to have zero false positives, the resulting coefficients will inherently be smaller than the ground truth. This provides rigorous mathematical justification for why "gating" or "boosting" is necessary in the first place.
  • Alliance of Gate Functions: The authors found that different mathematical forms for the gates (e.g., exponential vs. inverse proportional) perform differently depending on the layer depth. They suggest an "alliance" strategy where simpler piece-wise linear gates work well in early layers, while more complex inverse-proportional gates excel in deeper layers.
  • Dynamic Step Sizes: Unlike previous "Fast ISTA" (FISTA) methods that use a fixed momentum sequence, GLISTA learns to adjust its "overshoot" based on the specific input data, making it far more flexible and adaptive.

Empirical Results

The authors evaluated GLISTA on synthetic simulations (using Gaussian dictionary matrices and Bernoulli sparse vectors) and a real-world Photometric Stereo task (estimating 3D surface normals from 2D images under varying lighting).

GLISTA consistently outperformed standard LISTA and other state-of-the-art variants like ALISTA and LFISTA:

  • Accuracy (NMSE): On synthetic data at 40dB SNR, GLISTA achieved a Normalized Mean Squared Error of -45.22 dB, compared to -38.72 dB for standard LISTA.
  • Convergence Speed: As shown below, GLISTA reaches lower error levels with significantly fewer layers (iterations) than its competitors.
Convergence plot showing NMSE (dB) versus the number of layers for various LISTA and GLISTA models.
  • Real-world Task: In the Photometric Stereo task, GLISTA reduced the mean angular error to 0.00210 degrees (with 35 observations), which is an order of magnitude better than standard LISTA (0.0237 degrees).

Limitations and Future Work

While highly effective, GLISTA does have limitations. Much of the theoretical proof for the gain gates relies on the "no false positive" regime; while the authors relax this in practice, the theoretical guarantees are strongest when the support is correctly identified. Additionally, adding gates increases the number of learnable parameters and the computational cost per layer, though this is generally offset by needing fewer layers overall.

For future directions, the authors suggest extending this gated approach to Convolutional Neural Networks (CNNs) to handle more complex image processing tasks where sparse priors are common.

Summary updated

Abstract

In this paper, we study the learned iterative shrinkage thresholding algorithm (LISTA) for solving sparse coding problems. Following assumptions made by prior works, we first discover that the code components in its estimations may be lower than expected, i.e., require gains, and to address this problem, a gated mechanism amenable to theoretical analysis is then introduced. Specific design of the gates is inspired by convergence analyses of the mechanism and hence its effectiveness can be formally guaranteed. In addition to the gain gates, we further introduce overshoot gates for compensating insufficient step size in LISTA. Extensive empirical results confirm our theoretical findings and verify the effectiveness of our method.
BibTeX
@inproceedings{wu2020sparse,
  author = {Kailun Wu and Yiwen Guo and Ziang Li and Changshui Zhang},
  title = {{Sparse Coding with Gated Learned ISTA}},
  booktitle = {International Conference on Learning Representations},
  year = {2020},
  url = {https://openreview.net/forum?id=E7uwyz6yyM},
}
Figure