Minimization of fraction function penalty in compressed sensing

Abstract

In the paper, we study the minimization problem of a non-convex sparsity promoting penalty function $$P_a(x)=\sum _{i=1}^n{p}_a(x_i)=\sum _{i=1}^n\frac{a|x_i|}{1+a|x_i|}$$ in compressed sensing, which is called fraction function. Firstly, we discuss the equivalence of ${\ell }_0$ minimization and fraction function minimization. It is proved that there corresponds a constant $a^{\ast \ast }>0$ such that, whenever $a>a^{\ast \ast }$, every solution to $(F{P}_a)$ also solves $(P_0)$, that the uniqueness of global minimizer of $(F{P}_a)$ and its equivalence to $(P_0)$ if the sensing matrix $A$ satisfies a restricted isometry property (RIP) and, last but the most important, that the optimal solution to the regularization problem $(F{P}_a^{\lambda })$ also solves $(F{P}_a)$ if the certain condition is satisfied, which is similar to the regularization problem in convex optimal theory. Secondly, we study the properties of the optimal solution to the regularization problem $(F{P}_a^{\lambda })$ including the first-order and the second optimality condition and the lower and upper bound of the absolute value for its nonzero entries. Finally, we derive the closed form representation of the optimal solution to the regularization problem ($F{P}_a^{\lambda }$) for all positive values of parameter $a$, and propose an iterative $FP$ thresholding algorithm to solve the regularization problem $(F{P}_a^{\lambda })$. We also provide a series of experiments to assess performance of the $FP$ algorithm, and the experiment results show that, compared with soft thresholding algorithm and half thresholding algorithms, the $FP$ algorithm performs the best in sparse signal recovery with and without measurement noise.

12 pages

References in corpus (2)

• Sparsity-Aware Learning and Compressed Sensing: An Overview
• On the Performance of Sparse Recovery via L_p-minimization (0<=p <=1)

Cited by in corpus (7)

• Nonconvex fraction function recovery sparse signal by convex optimization algorithm
• Affine matrix rank minimization problem via non-convex fraction function penalty
• Sparse Portfolio Selection via Non-convex Fraction Function
• A non-convex approach to low-rank and sparse matrix decomposition
• Non-convex Fraction Function Penalty: Sparse Signals Recovered from Quasi-linear Systems
• Off-grid Multi-Source Passive Localization Using a Moving Array
• Recovering Sparse Nonnegative Signals via Non-convex Fraction Function Penalty