Regularized Least Squares Optimization for Sparse Approximations

Xiaojun Chen
Department of Applied Mathematics
The Hong Kong Polytechnic University


Wednesday July 27, 2011
4:30 - 5:30 PM
Y2E2 101

Abstract:

We consider linear least squares problems with nonconvex regularization and their applications in variable selection and image reconstruction. For unconstrained problems with l_p norm (0<p<1) regularization, we show that finding a global optimal solution is strongly NP-hard and present lower bounds of nonzero entries in every local optimal solution. Such lower bounds can be used to classify zero and nonzero entries in local optimal solutions and select regularization parameters for desirable sparsity of solutions. For box constrained problems with first-order difference regularization operator, we show the difference between any two relative entries of a local optimal solution is either 0 or larger than a computable number. Moreover, we present a smoothing conjugate gradient methods which can find a stationary point of the nonsmooth, nonconvex regularized least squares problem from any starting point.

This talk is based on the following four joint papers.
1. X. Chen, D. Ge, Z. Wang and Y.Ye, Complexity of unconstrained L2-Lp minimization, May 2011
2. X. Chen, M. K. Ng and C. Zhang, Nonconvex l_p regularization and box constrained model for image restoration, December , 2010 submitted to SIAM J. Imaging Sciences, under revision.
3. X. Chen, F. Xu and Y. Ye, Lower bound theory of nonzero entries in solutions of l_2-l_p minimization, SIAM J. Scientific Computing, 32(2010), 2832-2852.
4. X. Chen and W. Zhou, Smoothing nonlinear conjugate gradient method for image restoration using nonsmooth nonconvex minimization, SIAM J. Imaging Sciences 3(2010), pp. 765-790.

---

Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html