# Deep greedy unfolding: Sorting out argsorting in greedy sparse recovery algorithms

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 46 references that are in the map.
- First posted on arXiv 21 May 2025.

## Builds on (most cited first, 15 of 15)

- [Categorical Reparameterization with Gumbel-Softmax](https://mlsanity.com/paper/1611.01144/) (2016)
- [Algorithm Unrolling: Interpretable, Efficient Deep Learning for Signal and Image Processing](https://mlsanity.com/paper/1912.10557/) (2019)
- [Fast Differentiable Sorting and Ranking](https://mlsanity.com/paper/2002.08871/) (2020)
- [Learning Latent Permutations with Gumbel-Sinkhorn Networks](https://mlsanity.com/paper/1802.08665/) (2018)
- [On the Properties of the Softmax Function with Application in Game Theory and Reinforcement Learning](https://mlsanity.com/paper/1704.00805/) (2017)
- [Differentiable Ranks and Sorting using Optimal Transport](https://mlsanity.com/paper/1905.11885/) (2019)
- [Stochastic Optimization of Sorting Networks via Continuous Relaxations](https://mlsanity.com/paper/1903.08850/) (2019)
- [SoftSort: A Continuous Relaxation for the argsort Operator](https://mlsanity.com/paper/2006.16038/) (2020)
- [Can stable and accurate neural networks be computed? -- On the barriers of deep learning and Smale's 18th problem](https://mlsanity.com/paper/2101.08286/) (2021)
- [Maximal Sparsity with Deep Networks?](https://mlsanity.com/paper/1605.01636/) (2016)
- [Fast, Differentiable and Sparse Top-k: a Convex Analysis Perspective](https://mlsanity.com/paper/2302.01425/) (2023)
- [Theoretical Perspectives on Deep Learning Methods in Inverse Problems](https://mlsanity.com/paper/2206.14373/) (2022)
- [Compressive Sensing and Neural Networks from a Statistical Learning Perspective](https://mlsanity.com/paper/2010.15658/) (2020)
- [Learned Greedy Method (LGM): A Novel Neural Architecture for Sparse Coding and Beyond](https://mlsanity.com/paper/2010.07069/) (2020)
- [The greedy side of the LASSO: New algorithms for weighted sparse recovery via loss function-based orthogonal matching pursuit](https://mlsanity.com/paper/2303.00844/) (2023)

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

- [Generative Neural Operators of Log-Complexity Can Simultaneously Solve Infinitely Many Convex Programs](https://mlsanity.com/paper/2508.14995/) (2025)
- [Algorithmic Foundations of Deep Learning: Complexity-Theoretic Rates and a Characterization of Universal Approximation](https://mlsanity.com/paper/2606.26705/) (2026)

## Abstract (arXiv)

Gradient-based learning imposes (deep) neural networks to be differentiable at all steps. This includes model-based architectures constructed by unrolling iterations of an iterative algorithm onto layers of a neural network, known as algorithm unrolling. However, greedy sparse recovery algorithms depend on the non-differentiable argsort operator, which hinders their integration into neural networks. In this paper, we address this challenge in Orthogonal Matching Pursuit (OMP) and Iterative Hard Thresholding (IHT), two popular representative algorithms in this class. We propose permutation-based variants of these algorithms and approximate permutation matrices using "soft" permutation matrices derived from softsort, a continuous relaxation of argsort. We demonstrate -- both theoretically and numerically -- that Soft-OMP and Soft-IHT, as differentiable counterparts of OMP and IHT and fully compatible with neural network training, effectively approximate these algorithms with a controllable degree of accuracy. This leads to the development of OMP- and IHT-Net, fully trainable network architectures based on Soft-OMP and Soft-IHT, respectively. Finally, by choosing weights as "structure-aware" trainable parameters, we connect our approach to structured sparse recovery and demonstrate its ability to extract latent sparsity patterns from data.