The Sparsity of Underdetermined Linear System via l (p) Minimization for 0 < p < 1

摘要

The sparsity problems have attracted a great deal of attention in recent years, which aim to find the sparsest solution of a representation or an equation. In the paper, we mainly study the sparsity of underdetermined linear system via l(p) minimization for 0 < p < 1. We show, for a given underdetermined linear system of equations A(mxn)X=b , that although it is not certain that the problem (P-p) (i.e., min(x)parallel to X parallel to(p)(p) subject to AX = b, where 0 < p < 1) generates sparser solutions as the value of decreases and especially the problem (P-p) generates sparser solutions than the problem (P-1) (i.e., min(x)parallel to X parallel to(1) subject to AX = b), there exists a sparse constant gamma(a, b) > 0 such that the following conclusions hold when p < gamma(a, b):(1) the problem generates (P-p) sparser solution as the value of p decreases; (2) the sparsest optimal solution to the problem (P-p) is unique under the sense of absolute value permutation; (3) let X-1 and X-2 be the sparsest optimal solution to the problems (P-p1) and (P-p2) (p(1) < p(2)) , respectively, and let X-1 not be the absolute value permutation of X-2. Then there exist t(1), t(2) is an element of[p(1), p(2)] such that X-1 is the sparsest optimal solution to the problem (P-t) (for all t is an element of [p(1), t(1)]) and X-2 is the sparsest optimal solution to the problem .