Timezone: »

Global Linear and Local Superlinear Convergence of IRLS for Non-Smooth Robust Regression
Liangzu Peng · Christian Kümmerle · Rene Vidal

Wed Nov 30 09:00 AM -- 11:00 AM (PST) @ Hall J #310
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 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.

Author Information

Liangzu Peng (Johns Hopkins University)
Christian Kümmerle (University of North Carolina at Charlotte)
Rene Vidal (Mathematical Institute for Data Science, Johns Hopkins University, USA)

More from the Same Authors