Stability analysis of a class of sparse optimization problems

Abstract

The sparse optimization problems arise in many areas of science and engineering, such as compressed sensing, image processing, statistical and machine learning. The ${\ell }_0$-minimization problem is one of such optimization problems, which is typically used to deal with signal recovery. The ${\ell }_1$-minimization method is one of the popular approaches for solving the ${\ell }_0$-minimization problems, and the stability of such a numerical method is vital for solving such sparse optimization problems and particularly vital for signal recovery. In this paper, we establish a stability result for the ${\ell }_1$-minimization problems associated with a broad class of ${\ell }_0$-minimization problems. To this goal, we introduce the concept of restricted weak range space property (RSP) of a transposed sensing matrix, which is a generalized version of the weak RSP of the transposed sensing matrix introduced in [Zhao et al., Math. Oper. Res. 44 (2019), pp. 175–193]. The stability result established in this paper includes several existing ones as special cases.

Keywords:

• Sparsity optimization
• ${\ell }_1$-minimization
• stability
• optimality condition
• Hoffman theorem
• restricted weak range space property

2010 Mathematics Subject Classifications:

• 90C05
• 90C25
• 90C31
• 94A12
• 15A29

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Notes on contributors

Jialiang Xu

Jialiang Xu received his PhD in Management Mathematics in 2019 from the University of Birmingham, UK. He is currently a post-doctoral research fellow at the Academy of Mathematics and Systems Science, Chinese Academy of Sciences. His research interest is in optimization methods and applications.

Yun-Bin Zhao

Yun-Bin Zhao received his PhD in Operations Research and Control Theory in 1998 from the Chinese Academy of Sciences. From 2003 to 2007 he was an Associate Professor in the Academy of Mathematics and Systems Science, Chinese Academy of Sciences. He joined to the University of Birmingham (in UK) in 2007. He has been serving as the associate editors for Applied Mathematics and Computation (2007–2017) and European Journal on Pure and Applied Mathematics (2008-). His research interests include optimization, compressed sensing, signal and image processing, and big-data processing. He is the author of the book Sparse Optimization Theory and Methods, CRC Press, Boca Raton, FL, 2018.