Minimization of Fraction Function Penalty in Compressed Sensing.

Abstract

In this paper, we study the minimization problem of a non-convex sparsity-promoting penalty function, i.e., fraction function, in compressed sensing. First, we discuss the equivalence of l₀ minimization and fraction function minimization. It is proved that the optimal solution to fraction function minimization solves l₀ minimization and the optimal solution to the regularization problem also solves fraction function minimization if the certain conditions are satisfied, which is similar to the regularization problem in a convex optimization theory. Second, we study the properties of the optimal solution to the regularization problem, including the first-order and second-order optimality conditions and the lower and upper bounds of the absolute value for its nonzero entries. Finally, we derive the closed-form representation of the optimal solution to the regularization problem and propose an iterative FP thresholding algorithm to solve the regularization problem. We also provide a series of experiments to assess the performance of the FP algorithm, and the experimental results show that the FP algorithm performs well in sparse signal recovery with and without measurement noise.