Improved iteratively reweighted least squares for unconstrained smoothed lq minimization

To appear in SIAM Journal on Numerical Analysis.

• Technical report

Overview

This paper studies nonconvex lq minimization and its associated iterative reweighted algorithm for recovering sparse vectors and low-rank matrices.

Unlike most existing work, this paper focuses on unconstrained lq minimization, for which we show a few advantages on noisy measurements and/or approximately sparse vectors. Inspired by the results in Daubechies, DeVore, Fornasier, and Guntuk for constrained lq minimization, we start with a novel analysis for unconstrained one, which includes convergence, error bound, and local convergence behavior. Then, the algorithm and analysis are extended to the recovery of low-rank matrices.

Besides the theoreical novelty, the algorithms for both vector and matrix recovery have been compared to some state-of-the-arts and show superior performance on recovering sparse vectors and low-rank matrices.

Citation

M.-J. Lai, Y. Xu, and W. Yin, Improved iteratively reweighted least squares for unconstrained smoothed lq minimization, To appear in SIAM Journal on Numerical Analysis.