Entropy Function-Based Algorithms for Solving a Class of Nonconvex Minimization Problems

  • PDF / 657,545 Bytes
  • 18 Pages / 439.37 x 666.142 pts Page_size
  • 78 Downloads / 181 Views

DOWNLOAD

REPORT


Entropy Function-Based Algorithms for Solving a Class of Nonconvex Minimization Problems Yu-Fan Li1 · Zheng-Hai Huang1,2 · Min Zhang1

Received: 22 May 2015 / Revised: 28 August 2015 / Accepted: 12 October 2015 © Operations Research Society of China, Periodicals Agency of Shanghai University, Science Press, and Springer-Verlag Berlin Heidelberg 2015

Abstract Recently, the l p minimization problem ( p ∈ (0, 1)) for sparse signal recovery has been studied a lot because of its efficiency. In this paper, we propose a general smoothing algorithmic framework based on the entropy function for solving a class of l p minimization problems, which includes the well-known unconstrained l2 –l p problem as a special case. We show that any accumulation point of the sequence generated by the proposed algorithm is a stationary point of the l p minimization problem, and derive a lower bound for the nonzero entries of the stationary point of the smoothing problem. We implement a specific version of the proposed algorithm which indicates that the entropy function-based algorithm is effective. Keywords l p minimization problem · Entropy function · Smoothing conjugate gradient method Mathematics Subject Classification

65K05 · 90C26 · 90C59

This research was supported by the National Natural Science Foundation of China (Nos. 11171252 and 11431002).

B

Zheng-Hai Huang [email protected] Yu-Fan Li [email protected] Min Zhang [email protected]

1

Department of Mathematics, School of Science, Tianjin University, Tianjin 300072, China

2

Center for Applied Mathematics of Tianjin University, Tianjin 300072, China

123

Y.-F. Li et al.

1 Introduction Recently, the problem of recovering an unknown sparse signal by solving the underdetermined linear system has aroused lots of concerns due to its wide applications such as compressed sensing, signal processing, machine learning, and computer vision [1]. The mathematical model is the famous l0 minimization problem: min x0 s.t. Ax = b,

x∈Rn

where A ∈ Rm×n , b ∈ Rm , and x0 denote the number of nonzero elements of x ∈ Rn . One of the popular convex relaxation models is as follows: min x1 s.t. Ax = b,

x∈Rn

n |xi | is the l1 -norm of x ∈ Rn . where x1 := i=1 A great deal of effort has been made recently by many researchers for studying the nonconvex relaxation of the l0 minimization problem, i.e., the l p minimization problem: p

min x p s.t. Ax = b,

x∈Rn

(1.1)

1 n where x p := ( i=1 |xi | p ) p with p ∈ (0, 1) is the l p quasi-norm of x ∈ Rn . Since the l p quasi-norm is nonconvex and nonsmooth, the l p minimization problem is hard to solve; in fact, it is NP-hard [2,3]. Many researchers have established the sufficient conditions for recovering the sparsest solution to the underdetermined linear system Ax = b by model (1.1) (see, for example, [4–7]). Several algorithms have been developed for solving problem (1.1), including the famous iteratively reweighted l1 (IRL1) minimization algorithm [6,8–10] and the iteratively reweighted least square (IRLS) algorithm [5,11

Data Loading...