# Understanding the Learned Iterative Soft Thresholding Algorithm with matrix factorization

arXiv: https://arxiv.org/abs/1706.01338 · HTML: https://mlsanity.com/paper/1706.01338/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Jun 2017.

## Built on by (most cited first, 9 of 9)

- [Learning to Optimize: A Primer and A Benchmark](https://mlsanity.com/paper/2103.12828/) (2021)
- [Heavy Ball Neural Ordinary Differential Equations](https://mlsanity.com/paper/2110.04840/) (2021)
- [Learning to Learn Graph Topologies](https://mlsanity.com/paper/2110.09807/) (2021)
- [Rotation Equivariant Proximal Operator for Deep Unfolding Methods in Image Restoration](https://mlsanity.com/paper/2312.15701/) (2023)
- [Symbolic Learning to Optimize: Towards Interpretability and Scalability](https://mlsanity.com/paper/2203.06578/) (2022)
- [MomentumSMoE: Integrating Momentum into Sparse Mixture of Experts](https://mlsanity.com/paper/2410.14574/) (2024)
- [Momentum Transformer: Closing the Performance Gap Between Self-attention and Its Linearization](https://mlsanity.com/paper/2208.00579/) (2022)
- [Diffusion Sampling with Momentum for Mitigating Divergence Artifacts](https://mlsanity.com/paper/2307.11118/) (2023)
- [Accelerating Multi-Block Constrained Optimization Through Learning to Optimize](https://mlsanity.com/paper/2409.17320/) (2024)

## Abstract (arXiv)

Sparse coding is a core building block in many data analysis and machine learning pipelines. Typically it is solved by relying on generic optimization techniques, such as the Iterative Soft Thresholding Algorithm and its accelerated version (ISTA, FISTA). These methods are optimal in the class of first-order methods for non-smooth, convex functions. However, they do not exploit the particular structure of the problem at hand nor the input data distribution. An acceleration using neural networks, coined LISTA, was proposed in Gregor and Le Cun (2010), which showed empirically that one could achieve high quality estimates with few iterations by modifying the parameters of the proximal splitting appropriately. In this paper we study the reasons for such acceleration. Our mathematical analysis reveals that it is related to a specific matrix factorization of the Gram kernel of the dictionary, which attempts to nearly diagonalise the kernel with a basis that produces a small perturbation of the ℓ1 ball. When this factorization succeeds, we prove that the resulting splitting algorithm enjoys an improved convergence bound with respect to the non-adaptive version. Moreover, our analysis also shows that conditions for acceleration occur mostly at the beginning of the iterative process, consistent with numerical experiments. We further validate our analysis by showing that on dictionaries where this factorization does not exist, adaptive acceleration fails.