  For solving a wide class of nonconvex and nonsmooth problems, we propose a
proximal linearized iteratively reweighted least squares (PL-IRLS) algorithm.
We first approximate the original problem by smoothing methods, and second
write the approximated problem into an auxiliary problem by introducing new
variables. PL-IRLS is then built on solving the auxiliary problem by utilizing
the proximal linearization technique and the iteratively reweighted least
squares (IRLS) method, and has remarkable computation advantages. We show that
PL-IRLS can be extended to solve more general nonconvex and nonsmooth problems
via adjusting generalized parameters, and also to solve nonconvex and nonsmooth
problems with two or more blocks of variables. Theoretically, with the help of
the Kurdyka- Lojasiewicz property, we prove that each bounded sequence
generated by PL-IRLS globally converges to a critical point of the approximated
problem. To the best of our knowledge, this is the first global convergence
result of applying IRLS idea to solve nonconvex and nonsmooth problems. At
last, we apply PL-IRLS to solve three representative nonconvex and nonsmooth
problems in sparse signal recovery and low-rank matrix recovery and obtain new
globally convergent algorithms.
