  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.
