The Sparsity of Underdetermined Linear System via Minimization for

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 minimization for . We show, for a given underdetermined linear system of equations , that although it is not certain that the problem (i.e., subject to , where ) generates sparser solutions as the value of decreases and especially the problem generates sparser solutions than the problem (i.e., subject to ), there exists a sparse constant such that the following conclusions hold when : the problem generates sparser solution as the value of decreases; the sparsest optimal solution to the problem is unique under the sense of absolute value permutation; let and be the sparsest optimal solution to the problems and , respectively, and let not be the absolute value permutation of . Then there exist such that is the sparsest optimal solution to the problem and is the sparsest optimal solution to the problem .