  We advance both the theory and practice of robust $\ell_p$-quasinorm
regression for $p \in (0,1]$ by using novel variants of iteratively reweighted
least-squares (IRLS) to solve the underlying non-smooth problem. In the convex
case, $p=1$, we prove that this IRLS variant converges globally at a linear
rate under a mild, deterministic condition on the feature matrix called the
\textit{stable range space property}. In the non-convex case, $p\in(0,1)$, we
prove that under a similar condition, IRLS converges locally to the global
minimizer at a superlinear rate of order $2-p$; the rate becomes quadratic as
$p\to 0$. We showcase the proposed methods in three applications: real phase
retrieval, regression without correspondences, and robust face restoration. The
results show that (1) IRLS can handle a larger number of outliers than other
methods, (2) it is faster than competing methods at the same level of accuracy,
(3) it restores a sparsely corrupted face image with satisfactory visual
quality. https://github.com/liangzu/IRLS-NeurIPS2022
