• PDF / 261,477 Bytes
• 13 Pages / 439.36 x 666.15 pts Page_size
• 45 Downloads / 217 Views

DOWNLOAD

REPORT

---

Nonconvex Sparse Regularization and Splitting Algorithms Rick Chartrand and Wotao Yin

Abstract Nonconvex regularization functions such as the  p quasinorm (0 < p < 1) can recover sparser solutions from fewer measurements than the convex 1 regularization function. They have been widely used for compressive sensing and signal processing. This chapter briefly reviews the development of algorithms for nonconvex regularization. Because nonconvex regularization usually has different regularity properties from other functions in a problem, we often apply operator splitting (forward-backward splitting) to develop algorithms that treat them separately. The treatment on nonconvex regularization is via the proximal mapping. We also review another class of coordinate descent algorithms that work for both convex and nonconvex functions. They split variables into small, possibly parallel, subproblems, each of which updates a variable while fixing others. Their theory and applications have been recently extended to cover nonconvex regularization functions, which we review in this chapter. Finally, we also briefly mention an ADMM-based algorithm for nonconvex regularization, as well as the recent algorithms for the so-called nonconvex sort 1 and 1 − 2 minimization.

1 Early History of Nonconvex Regularization for Sparsity The attempt to compute a sparse solution of a problem (such as a linear system of equations) by minimizing a nonconvex penalty function can be traced back at least to Leahy and Jeffs [31], who used a simplex algorithm (essentially a nonlinear version R. Chartrand () Descartes Labs, Los Alamos, NM 87544, USA e-mail: [email protected] W. Yin Department of Mathematics, University of California, Los Angeles, CA 90095, USA e-mail: [email protected] © Springer International Publishing Switzerland 2016 R. Glowinski et al. (eds.), Splitting Methods in Communication, Imaging, Science, and Engineering, Scientific Computation, DOI 10.1007/978-3-319-41589-5_7

237

238

R. Chartrand and W. Yin

of linear programming) to minimize the  p norm1 subject to a linear constraint. They describe the algorithm as similar to one of Barrodale and Roberts [3], where  p norm minimization is considered in a different context. The next algorithmic development came from Gorodnitsky and Rao, named FOCUSS (for FOCal Underdetermined System Solver) [25]. In fact, the approach was a much older method, iteratively reweighted least squares (IRLS) [30], applied to 0 norm minimization. This was extended to general  p minimization by Rao and Kreutz-Delgado [45]. Global convergence was erroneously claimed in [26], based on Zangwill’s Global Convergence Theorem [65], which only provides that subsequential limits are local minima. Attention to nonconvex regularization for sparsity was next spurred by the development of compressive sensing [12, 23], which mostly featured 1 minimization. Generalization to  p minimization with p < 1 was carried out by Chartrand, initially with a projected gradient algorithm [15], followed by an IRLS