Stability analysis of a class of sparse optimization problems. (3rd July 2020)

• Record Type: Journal Article
• Authors: Xu, Jialiang; Zhao, Yun-Bin
• Is Part Of: Optimization methods and software. Volume 35:Number 4(2020)
• Page Start: 836
• Page End: 854
• Publication Date: 2020-07-03
• Subjects: Sparsity optimization -- ℓ1-minimization -- stability -- optimality condition -- Hoffman theorem -- restricted weak range space property; 90C05 -- 90C25 -- 90C31 -- 94A12 -- 15A29; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2020.1734003
• Languages: English
• ISSNs: 1055-6788

Abstract

Abstract : The sparse optimization problems arise in many areas of science and engineering, such as compressed sensing, image processing, statistical and machine learning. The ℓ 0 -minimization problem is one of such optimization problems, which is typically used to deal with signal recovery. The ℓ 1 -minimization method is one of the popular approaches for solving the ℓ 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 ℓ 1 -minimization problems associated with a broad class of ℓ 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.