The sparsity of underdetermined linear system via \(l_p\) minimization for \(0 < p < 1\) (Q1666063)

Summary: 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_{m \times n} X = b\), that although it is not certain that the problem \((P_p)\) (i.e., \(\min_X \|X\|_p^p\) subject to \(A X = b\), where \(0 < p < 1\)) generates sparser solutions as the value of \(p\) decreases and especially the problem \((P_p)\) generates sparser solutions than the problem \((P_1)\) (i.e., \(\min_X \|X\|_1\) subject to \(A X = b\)), there exists a sparse constant \(\gamma(A, b) > 0\) such that the following conclusions hold when \(p < \gamma(A, b)\): (1) the problem \((P_p)\) generates 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_{p_1})\) and \((P_{p_2})(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 \in [p_1, p_2]\) such that \(X_1\) is the sparsest optimal solution to the problem \((P_t)(\forall t \in [p_1, t_1])\) and \(X_2\) is the sparsest optimal solution to the problem \((P_t)\) (\(\forall t \in(t_2, p_2]\)).