The Constrained L_p-L_q Basis Pursuit Denoising Problem

07/01/2019
by   Lei Yang, et al.
0

In this paper, we consider the constrained L_p-L_q basis pursuit denoising problem, which aims to find a minimizer of x_p^p subject to Ax-b_q≤σ for given A ∈R^m × n, b∈R^m, σ≥0, 0≤ p≤1 and q ≥ 1. We first study the properties of the optimal solutions of this problem. Specifically, without any condition on the matrix A, we provide upper bounds in cardinality and infinity 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 ∈{1,∞}, 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<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 remains unchanged. An estimation of such p^* is also provided. We then propose a smoothing penalty method to solve the problem with 0<p<1 and q=1, and show that, under some mild conditions, any cluster point of the sequence generated is a KKT 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 L_p-L_1 basis pursuit denoising problem under different noises.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset