# Linear Convergence of Reshuffling Kaczmarz Methods With Sparse Constraints

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 47 references that are in the map.
- First posted on arXiv 20 Apr 2023.

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

- [Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz algorithm](https://mlsanity.com/paper/1310.5715/) (2013)
- [Random Reshuffling: Simple Analysis with Vast Improvements](https://mlsanity.com/paper/2006.05988/) (2020)
- [Why Random Reshuffling Beats Stochastic Gradient Descent](https://mlsanity.com/paper/1510.08560/) (2015)
- [Regularized M-estimators with nonconvexity: Statistical and algorithmic theory for local optima](https://mlsanity.com/paper/1305.2436/) (2013)
- [Solving Linear Inverse Problems Using GAN Priors: An Algorithm with Provable Guarantees](https://mlsanity.com/paper/1802.08406/) (2018)
- [SGD with shuffling: optimal rates without component convexity and large epoch requirements](https://mlsanity.com/paper/2006.06946/) (2020)
- [Proximal and Federated Random Reshuffling](https://mlsanity.com/paper/2102.06704/) (2021)
- [Algorithmic Guarantees for Inverse Imaging with Untrained Network Priors](https://mlsanity.com/paper/1906.08763/) (2019)
- [Sparse sketches with small inversion bias](https://mlsanity.com/paper/2011.10695/) (2020)
- [Recht-R'e Noncommutative Arithmetic-Geometric Mean Conjecture is False](https://mlsanity.com/paper/2006.01510/) (2020)
- [Linear Convergence of Stochastic Iterative Greedy Algorithms with Sparse Constraints](https://mlsanity.com/paper/1407.0088/) (2014)
- [Iterative Hard Thresholding for Low CP-rank Tensor Models](https://mlsanity.com/paper/1908.08479/) (2019)
- [Dimensionality reduction with subgaussian matrices: a unified theory](https://mlsanity.com/paper/1402.3973/) (2014)

## Abstract (arXiv)

The Kaczmarz method (KZ) and its variants, which are types of stochastic gradient descent (SGD) methods, have been extensively studied due to their simplicity and efficiency in solving linear equation systems. The iterative thresholding (IHT) method has gained popularity in various research fields, including compressed sensing or sparse linear regression, machine learning with additional structure, and optimization with nonconvex constraints. Recently, a hybrid method called Kaczmarz-based IHT (KZIHT) has been proposed, combining the benefits of both approaches, but its theoretical guarantees are missing. In this paper, we provide the first theoretical convergence guarantees for KZIHT by showing that it converges linearly to the solution of a system with sparsity constraints up to optimal statistical bias when the reshuffling data sampling scheme is used. We also propose the Kaczmarz with periodic thresholding (KZPT) method, which generalizes KZIHT by applying the thresholding operation for every certain number of KZ iterations and by employing two different types of step sizes. We establish a linear convergence guarantee for KZPT for randomly subsampled bounded orthonormal systems (BOS) and mean-zero isotropic sub-Gaussian random matrices, which are most commonly used models in compressed sensing, dimension reduction, matrix sketching, and many inverse problems in neural networks. Our analysis shows that KZPT with an optimal thresholding period outperforms KZIHT. To support our theory, we include several numerical experiments.