  We propose a new Iteratively Reweighted Least Squares (IRLS) algorithm for
the problem of completing or denoising low-rank matrices that are structured,
e.g., that possess a Hankel, Toeplitz or block-Hankel/Toeplitz structure. The
algorithm optimizes an objective based on a non-convex surrogate of the rank by
solving a sequence of quadratic problems. Our strategy combines computational
efficiency, as it operates on a lower dimensional generator space of the
structured matrices, with high statistical accuracy which can be observed in
experiments on hard estimation and completion tasks. Our experiments show that
the proposed algorithm StrucHMIRLS exhibits an empirical recovery probability
close to 1 from fewer samples than the state-of-the-art in a Hankel matrix
completion task arising from the problem of spectral super-resolution of badly
separated frequencies. Furthermore, we explain how the proposed algorithm for
structured low-rank recovery can be used as preprocessing step for improved
robustness in frequency or line spectrum estimation problems.
