  Sparse recovery is ubiquitous in machine learning and signal processing. Due
to the NP-hard nature of sparse recovery, existing methods are known to suffer
either from restrictive (or even unknown) applicability conditions, or high
computational cost. Recently, iterative regularization methods have emerged as
a promising fast approach because they can achieve sparse recovery in one pass
through early stopping, rather than the tedious grid-search used in the
traditional methods. However, most of those iterative methods are based on the
$\ell_1$ norm which requires restrictive applicability conditions and could
fail in many cases. Therefore, achieving sparse recovery with iterative
regularization methods under a wider range of conditions has yet to be further
explored. To address this issue, we propose a novel iterative regularization
algorithm, IRKSN, based on the $k$-support norm regularizer rather than the
$\ell_1$ norm. We provide conditions for sparse recovery with IRKSN, and
compare them with traditional conditions for recovery with $\ell_1$ norm
regularizers. Additionally, we give an early stopping bound on the model error
of IRKSN with explicit constants, achieving the standard linear rate for sparse
recovery. Finally, we illustrate the applicability of our algorithm on several
experiments, including a support recovery experiment with a correlated design
matrix.
