Sparse Solutions of a Class of Constrained Optimization Problems

In this paper, we consider a well-known sparse optimization problem that aims to find a sparse solution of a possibly noisy underdetermined system of linear equations. Mathematically, it can be modeled in a unified manner by minimizing parallel to x parallel to(p)(p) subject to parallel to Ax - b parallel to(q) <= sigma for given A is an element of R-mxn, b is an element of R-m, sigma >= 0, 0 <= p <= 1 and q >= 1. We then study various properties of the optimal solutions of this problem. Specifically, without any condition on the matrix A, we provide upper bounds in cardinality and infin-ity norm for the optimal solutions and show that all optimal solutions must be on the boundary of the feasible set when 0 < p <= 1. Moreover, for q is an element of{1, infinity}, we show that the problem with 0 < p < 1 has a finite number of optimal solutions and prove that there exists 0 < p* < 1 such that the solution set of the problem with any 0 < (p) over bar < p* is contained in the solution set of the problem with p = 0, and there further exists 0 < p < p* such that the solution set of the problem with any 0 < p <= (p) over bar remains unchanged. An estimation of such p* is also provided. In addition, to solve the constrained nonconvex non-Lipschitz L-p-L-1 problem (0 < p < 1 and q = 1), we propose a smoothing penalty method and show that, under some mild conditions, any cluster point of the sequence generated is a stationary point of our problem. Some numerical examples are given to implicitly illustrate the theoretical results and show the efficiency of the proposed algorithm for the constrained L-p-L-1 problem under different noises.