The Theory And DC Algorithm For The L₀-norm Minimization Based On Fractional Function

In recent years, solving the sparse solution problem for the underdetermined system of linear equations has been widely applied to error correcting code, image de-convolution, real field decoding, password system, and other domains. The sparse problem can be expressed as the following Lo-norm optimization problem Lo-norm optimization problem is not only a NP-hard problem, but also very sensitive to the noise, which causes an obstacle to solve Lo-norm optimization problem. For the Lo-norm optimization problem, the current methods are mainly greedy algorithm, convex relaxation optimization (Li-norm optimization problem) and non-convex optimization algorithm.In this paper, the Lo-norm is replaced by the fractional function and the Lo-norm optimization problem can be converted to the (FP0) optimization problem:minΣNi=1(?) s.t. Ax= y. This thesis further illustrates the basic properties of the optimal solutions for the (FP0) optimization problem, the equivalence conditions between the (FP0) optimization problem and the Lo-norm optimization problem, and the algorithm which is utilized to solve the (FP0) optimization problem. They are as follows:(1) This thesis studies the properties of the fractional function proves that the fractional function has something in common with the norm, and concludes that the optimal solution to the (FP0) optimization problem must be sparse and the columns of the observation matrix corresponding to the optimal solution are linearly independent.(2) Firstly, based on the Restricted Isometry Properties (RIP), this thesis presents a sufficient condition for the equivalence of the (FP0) optimization problem and the Lo-norm optimization problem, and the stability of the optimal solution of the (FP0ε optimization problem. That is to say, when the RIP constant of observation matrix A satisfies the inequality condition such that the optimal solution of (FP0) optimization problem also solves the Lo-norm optimization problem. Secondly, the concept of FP-Null Space Property is introduced. And by the FP-Null Space Property, a necessary and sufficient condition for the equivalence of two optimization problems is given. (3) The FP-DC algorithm, inspired by the DC A (difference of convex function algorithm) is proposed to solve the unconstrained (FP0) optimization problem. The experimental results show that the successful rate of its signal reconstruction is higherthan other algorithms.