Iteratively Reweighted Least Squares

Iteratively Reweighted Least Squares for $\ell_1$-minimization with Global Linear Convergence Rate

Iteratively Reweighted Least Squares (IRLS), whose history goes back more than 80 years, represents an important family of algorithms for non-smooth optimization as it is able to optimize these problems by solving a sequence of linear systems. In …

A Scalable Second Order Method for Ill-Conditioned Matrix Completion from Few Samples

We propose an iterative algorithm for low-rank matrix completion that can be interpreted as an iteratively reweighted least squares (IRLS) algorithm, a saddle-escaping smoothing Newton method or a variable metric proximal gradient method applied to a …

Escaping Saddle Points in Ill-Conditioned Matrix Completion with a Scalable Second Order Method

We propose an iterative algorithm for low-rank matrix completion that can be interpreted as both an iteratively reweighted least squares (IRLS) algorithm and a saddle-escaping smoothing Newton method applied to a non-convex rank surrogate objective. …

Understanding and Enhancing Data Recovery Algorithms - From Noise-Blind Sparse Recovery to Reweighted Methods for Low-Rank Matrix Optimization

We prove new results about the robustness of noise-blind decoders for the problem of re- constructing a sparse vector from underdetermined linear measurements. Our results imply provable robustness of equality-constrained l1-minimization for random …

Completion of Structured Low-Rank Matrices via Iteratively Reweighted Least Squares

We propose a new Iteratively Reweighted Least Squares (IRLS) algorithm for the problem of completing a low-rank matrix that is linearly structured, e.g., that possesses a Hankel, Toeplitz or block-Hankel/Toeplitz structures, which is of relevance for …

Denoising and Completion of Structured Low-Rank Matrices via Iteratively Reweighted Least Squares

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 …

Harmonic Mean Iteratively Reweighted Least Squares for Low-Rank Matrix Recovery

We propose a new iteratively reweighted least squares (IRLS) algorithm for the recovery of a matrix $X \in \mathbb{C}^{d_1 \times d_2}$ of rank $r \ll \min(d_1,d_2)$ from incomplete linear observations, solv- ing a sequence of low complexity linear …

Harmonic Mean Iteratively Reweighted Least Squares for Low-Rank Matrix Recovery

This is a first conference version of the paper on Harmonic Mean Iteratively Reweighted Least Squares.