Title: Iteratively reweighted $\ell_1$ algorithms with extrapolation,
Abstract: Iteratively reweighted $\ell_1$ algorithm is a popular algorithm for solving
a large class of optimization problems whose objective is the sum of a
Lipschitz differentiable loss function and a possibly nonconvex sparsity
inducing regularizer. In this paper, motivated by the success of extrapolation
techniques in accelerating first-order methods, we study how widely used
extrapolation techniques such as those in [4,5,22,28] can be incorporated to
possibly accelerate the iteratively reweighted $\ell_1$ algorithm. We consider
three versions of such algorithms. For each version, we exhibit an explicitly
checkable condition on the extrapolation parameters so that the sequence
generated provably clusters at a stationary point of the optimization problem.
We also investigate global convergence under additional Kurdyka-$\L$ojasiewicz
assumptions on certain potential functions. Our numerical experiments show that
our algorithms usually outperform the general iterative shrinkage and
thresholding algorithm in [21] and an adaptation of the iteratively reweighted
$\ell_1$ algorithm in [23, Algorithm 7] with nonmonotone line-search for
solving random instances of log penalty regularized least squares problems in
terms of both CPU time and solution quality.