# The Sparsity of Underdetermined Linear System vialp Minimization for 0<p<1

Authors: Haiyang Li; Jigen Peng; Shigang Yue
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

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 vialp minimization for 0<p<1. We show, for a given underdetermined linear system of equations Am×nX=b, that although it is not certain that the problem (Pp) (i.e., minXXpp subject to AX=b, where 0<p<1) generates sparser solutions as the value of p decreases and especially the problem (Pp) generates sparser solutions than the problem (P1) (i.e., minXX1 subject to AX=b), there exists a sparse constant γ(A,b)>0 such that the following conclusions hold when p<γ(A,b): (1) the problem (Pp) generates sparser solution as the value of p decreases; (2) the sparsest optimal solution to the problem (Pp) is unique under the sense of absolute value permutation; (3) let X1 and X2 be the sparsest optimal solution to the problems (Pp1) and (Pp2)(p1<p2), respectively, and let X1 not be the absolute value permutation of X2. Then there exist t1,t2∈[p1,p2] such that X1 is the sparsest optimal solution to the problem (Pt)(∀t∈[p1,t1]) and X2 is the sparsest optimal solution to the problem (Pt)(∀t∈(t2,p2]).


---

## Body

## 1. Introduction

Recently, considerable attention has been paid to the following sparsity problem. Given a full-rank matrixA of size m×n with m≪n, m-vector b, and knowing that b=AX∗, where X∗∈Rn is an unknown sparse vector, we expect to recover X∗. Although the system of equations is underdetermined and hence it is not a properly posed problem in linear algebra, sparsity of X∗ is a very useful priority that sometimes allows unique solution. Accordingly, one naturally proposes to use the following optimization model P0 to obtain the sparsest solutions: (1)P0min⁡XX0s.t.AX=b,where X0 denotes the number of nonzero components of X (we call ·0l0 norm). This is one of critical problems in compressed sensing research. This problem is motivated by data compression, error correcting codes, n-term approximation, and so forth (see, e.g., [1]). It is known that the problem P0 needs nonpolynomial time to solve (cf. [2]). It is crucial to recognize that one natural approach to tackle P0 is to solve the following convex minimization problem: (2)P1min⁡XX1s.t.AX=b,where X1=∑i=1n‍|xi| is the standard l1 norm. The study of this problem P1 was pioneered by Donoho, Candès, and their collaborators and many researchers have made a lot of contributions related to the existence, uniqueness, and other properties of the sparse solution as well as computational algorithms and their convergence analysis to tackle the problem P0 (see survey papers in [3–5]). However, the solutions to the problem P1 are often not as sparse as those to the problem P0. It is definitely imperative and required for many applications to find solutions which are more sparse than that to the problem P1. A natural try for this purpose is to apply the problem Pp  (0<p<1), that is, to solve the following model: (3)Ppmin⁡XXpps.t.AX=b,where Xpp=∑i=1n‍|xi|p (we call ·plp-norm, though it is no longer norms for p<1 as the triangle inequality is no longer satisfied). Obviously, the problem Pp is no longer a convex optimization problem. This minimization is motivated by the following fact:(4)limp→0+⁡Xpp=X0.This model was initiated by [6] and many researchers have worked on this direction [1, 2, 7–16]. They demonstrate that (1) for a Gaussian random matrix A, the restricted p-isometry property of order s holds if s is almost proportional to m when p→0+ (cf. [8]); (2) when δ2s<1 (or δ2s+1<1, δ2s+2<1), the optimal solution to the problem Pp is the same as the optimal solution to the problem P0 when p>0 small enough, where δ2s<1 is the restricted isometry constants of matrix A (similar for δ2s+1<1, δ2s+2<1) (cf. [7, 10, 13]); and (3) the lp minimization can be applied to a wider class of random matrices A (cf. [11]). In addition, in [7, 15], the authors show that the problem Pp generates sparser solution than the problem P1 and the problem Pp generates sparser solution as the value of p decreases by taking phase diagram studies with a set of experiments. Nevertheless, are the conclusions showed by taking phase diagram studies true in theory? In the paper, we will answer this question by studying the sparsity of lp minimization. Firstly, using Example 2 we show, in general, that the answer to the question above is negative. Secondly, although the answer to the question above is negative, we can prove that, for a given underdetermined linear system of equations Am×nX=b, there exists a constant γ(A,b)>0 (we call it sparsity constant) such that the following conclusions hold when p<γ(A,b).(1)
The problemPp generates sparser solution as the value of p decreases (Theorem 7).(2)
LetXp be the sparsest optimal solution to the problem Pp. Then Xp is the unique sparsest optimal solution to the problem Pp under the sense of absolute value permutation (Corollary 6).(3)
LetX1 and X2 be the sparsest optimal solution to the problem (Pp1) and problem (Pp2) (p1<p2), respectively, and let X1 not be the absolute value permutation of X2. Then there exist t1,t2∈[p1,p2] such that X1 is the sparsest optimal solution to the problem (Pt) (∀t∈[p1,t1]) and X2 is the sparsest optimal solution to the problem (Pt) (∀t∈(t2,p2]) (Theorem 8).


## 2. The Sparsity of Underdetermined Linear System vialp Minimization

LetX be the set of all solutions to the underdetermined linear systems AX=b. For the convenience of account, we call X1 the absolute value permutation of X2, which means that (|x11|,|x12|,…,|x1n|) is the permutation of (|x21|,|x22|,…,|x2n|), where X1=(x11,x12,…,x1n)T and X2=(x21,x22,…,x2n)T∈X.Lemma 1 (see [17]).
The problemP1 may have more than one solution. Nevertheless, even if there are infinitely many possible solutions to this problem, we can claim that (1) these solutions are gathered in a set that is bounded and convex, and (2) among these solutions, there exists at least one with at most m nonzeros.The following example shows that, in general, it is not certain that the problemPp generates sparser solution than the problem P1 and the problem Pp generates sparser solution as the value of p decreases.Example 2.
We consider the underdetermined linear system of equationsAX=b, where(5)A=α1,α2,α3,α4=-202913187001815160290463435-1,b=(1,2,3)T. By Lemma 1, the l0-norm of the optimal solutions to the problem P1 are not more than 3, and hence the optimal solution is one of the following feasible solutions:(1)
X1=(0,-4/27,29/9,58/135)T;(2)
X2=(0.1,0,3,0.4)T;(3)
X3=(1.45,2,0,0)T;(4)
X4=(1.45,2,0,0)T.
Furthermore, we can show that the optimal solution to the problemPp  (p=0.8,0.95) is one of above feasible solutions. It is easy to calculate that(6)X10.80.8=3.2756,X20.80.8=3.0472,X30.80.8=X40.80.8=3.0873,X10.950.95=3.6502,X20.950.95=3.3706,X30.950.95=X40.950.95=3.3552,X11=3.7999,X1=3.5,X31=X41=3.45.Thus X2 is the optimal solution when p=0.8 and X3 is the optimal solution when p=0.95 and p=1. However, X20=3, X30=2. Therefore, the problem Pp does not generate sparser solution than the problem P1 and the problem Pp does not generate sparser solution as the value of p decreases.In the following, we will prove the conclusions mentioned in Introduction.We define two functionsf(t)=Xt=(|x1|t+⋯+|xk|t)1/t (t>0) and g(t)=Xtt=|x1|t+⋯+|xk|t (t>0), where X=(x1,…,xk) and xi≠0. Then f(t)=(g(t))1/t.Theorem 3.
f
(
t
) is a monotone decreasing convex function and(7)f′t=fttg′tgt-ln⁡⁡ft.Proof.
It is easy to show that (7) holds. Without loss of generality, we assume that x1≤x2≤⋯≤|xk|. Because(8)f′t=fttg′tgt-ln⁡⁡ft=ftt2∑i=1kxitln⁡⁡xitgt-ln⁡⁡gt≤ftt2ln⁡⁡xkt-ln⁡⁡gt≤0,f(t) is monotone decreasing.
Furthermore,f(t) is a convex function. In fact, we have, by the convexity of function f(x)=x2, (9)∑i=1kxitln⁡⁡xi∑i=1kxit2≤∑i=1kxitln⁡2⁡xi∑i=1kxit.That is,(10)g′tgt2≤g′′tgt.Thus(11)g′tgt′=g′′tgt-g′tgt2≥0and hence g′(t)/g(t) is monotone increasing. Since f(t) is monotone decreasing, we know that g′(t)/g(t)-ln⁡f(t) is monotone increasing. Because f(t)/t is monotone decreasing, g′(t)/g(t) is monotone increasing and g′(t)/g(t)-ln⁡f(t)≤0, (12)f′′t=ftt′g′tgt-ln⁡⁡ft+fttg′tgt-ln⁡⁡ft′≥0which implies that f(t) is convex function.Theorem 4.
For a given underdetermined linear system of equationsAm×nX=b, there exists a constant γ>0 such that, for any X1,X2∈X, either f1′(t)=X1t′<f2′(t)=X2t′ or f2′(t)=X2t′<f1′(t)=X1t′ when 0<t<γ.Proof.
LetXk={X∣X0=k,X∈X} and Xβk={X∈Xk∣; there exists β such that ∏i=1kxi=β}. Clearly, we have Xk=∪βXβk, X=∪k=1nXk.
Firstly, for anyX1,X2∈Xβk, there exists a constant γβk>0 such that when 0<t<γβk, either f1′t=X1t′<f2′t=X2t′ or f2′(t)=X2t′<f1′(t)=X1t′.
Obviously, for any givenX1,X2∈Xβk, there is a positive number {γβk}j such that when 0<t<{γβk}j, either f1′t=X1t′<f2′(t)=X2t′ or f2′(t)=X2t′<f1′(t)=X1t′. Hence, it suffices to show inf⁡j{γβk}j=γβk≠0. Otherwise, for an arbitrarily small positive number ɛ, there exists t with 0<t<ɛ, Y1∈Xβk, and Y2∈Xβk such that (13)f1′t=Y1t′=f2′t=Y2t′.Using (7) we obtain (14)f1ttg1′tg1t-ln⁡⁡f1t=f2ttg2′tg2t-ln⁡⁡f2t.That is, (15)g1′t/g1t-ln⁡⁡f1tg2′t/g2t-ln⁡⁡f2t=f2tf1t.Since Y1,Y2∈Xβk, we have ∏i=1k|y1i|=∏i=1k|y2i|=β.
Hence(16)∑i=1kln⁡⁡y1i=∑i=1kln⁡⁡y2i.Therefore, there is a positive integer M such that (17)∑i=1kln⁡M⁡y1i≠∑i=1kln⁡M⁡y2iand, for any positive integer N with N<M, (18)∑i=1kln⁡N⁡y1i=∑i=1kln⁡N⁡y2i.Since, for any positive integer K,(19)g1K0=y11t+⋯+y1ktKt=0=∑i=1kln⁡K⁡y1i,g2K0=y21t+⋯+y2ktKt=0=∑i=1kln⁡K⁡y2i,we obtain, for M and N mentioned above,(20)g1M0≠g2M0,g1N0=g2N0.We assume, without loss of generality, that g1(M)(0)<g2(M)(0). For the M mentioned above, (15) becomes(21)g1′t/g1t-ln⁡⁡f1tg2′t/g2t-ln⁡⁡f2t1/tM-1=f2tf1t1/tM-1=g2tg1t1/tM.For the right of (21), we obtain (22)limt→0⁡g2tg1t1/tM=exp⁡⁡limt→0⁡ln⁡⁡g2t-ln⁡⁡g1ttM=exp⁡⁡limt→0⁡g2′t/g2t-g1′t/g1tMtM-1=exp⁡⁡limt→0⁡g2′′t/g2t-g1′′t/g1t-g2′2t/g22t+g2′2t/g12tMtM-1=⋯=exp⁡⁡g2M0-g1M0k>1.And for the left of (21), we obtain(23)limt→0⁡g1′t/g1t-ln⁡⁡f1tg2′/g2t-ln⁡⁡f2t1/tM-1=exp⁡⁡limt→0⁡ln⁡⁡ln⁡⁡g1t-g1′t/g1t×t-ln⁡⁡ln⁡⁡g2t-g2′t/g2t×ttM-1=1.This is a contradiction and thus when 0<t<γβk, either f1′(t)=X1t′<f2′(t)=X2t′ or f2′(t)=X2t′<f1′(t)=X1t′.
Secondly, for anyX1,X2∈Xk, there exists a constant γk>0 such that when 0<t<γk, either f1′(t)=X1t′<f2′(t)=X2t′ or f2′(t)=X2t′<f1′(t)=X1t′.
It suffices to show thatinf⁡βγβk=γk≠0. Otherwise, for an arbitrarily small positive number ɛ, there is t with 0<t<ɛ, Y1∈Xβ1k and Y2∈Xβ2k (β1≠β2) such that (24)f1′t=Y1t′=f2′t=Y2t′.Using (7) again, we also obtain (15).
For the right of (15), we have(25)limt→0⁡f2tf1t=exp⁡⁡limt→0⁡ln⁡⁡g2t-ln⁡⁡g1tt=∏iy1i∏iy2i≠1.And for the left of (15), we have (26)limt→0⁡g1′t/g1t-ln⁡⁡f1tg2′t/g2t-ln⁡⁡f2t=limt→0⁡g1′t/g1t×t-ln⁡⁡g1tg2′t/g2t×t-ln⁡⁡g2t=1.This is a contradiction and thus inf⁡βγβk=γk≠0.
Thirdly, for anyX1∈Xk, X2∈Xs, k≠s, there exists a constant γk,s>0 such that when 0<t<γk,s, either f1′(t)=X1t′<f2′(t)=X2t′ or f2′(t)=X2t′<f1′(t)=X1t′.
We assume, without loss of generality, thatX10=k<s=X20. Then (27)limt→0⁡g1′t/g1t-ln⁡⁡f1tg2′t/g2t-ln⁡⁡f2t=limt→0⁡g1′t/g1t×t-ln⁡⁡g1tg2′t/g2t×t-ln⁡⁡g2t=ln⁡⁡kln⁡⁡s<1,limt→0⁡f2tf1t=exp⁡⁡limt→0⁡ln⁡⁡g2t-ln⁡⁡g1tt=∞.So there is a positive number γk,s such that when t<γk,s, (28)g1′t/g1t-ln⁡⁡f1tg2′t/g2t-ln⁡⁡f2t<f2tf1t,which implies that (29)f2′t=X2t′<f1′t=X1t′.
In conclusion, we takeγ=min⁡{γk,γk,s∣k,s=1,2,…,n} and thus when 0<t<γ, for any X1,X2∈X, either f1′(t)=X1t′<f2′(t)=X2t′ or f2′(t)=X2t′<f1′(t)=X1t′.Obviously, for a given underdetermined linear system of equationsAm×nX=b, there are infinitely many constants γi>0 such that when 0<t<γi Theorem 7 holds. The supremum of γi is called the sparse constant of underdetermined linear system of equations Am×nX=b and denoted γ(A,b).Corollary 5.
Let equationsAm×nX=b be an underdetermined linear system. Then f1(t)=X1t and f2(t)=X2t have at most one intersection in (0,γ(A,b)), where X1,X2∈X and X1 is not the absolute value permutation of X2.Proof.
It is easy to prove that the conclusion holds by Theorems4 and 7.Corollary 6.
LetXp be the sparsest optimal solution to the problem Pp (p<γ(A,b)). Then Xp is the unique sparsest optimal solution to the problem Pp under the sense of absolute value permutation.Proof.
Suppose thatXp∗ is another sparsest optimal solution to the problem Pp and Xp∗ is not the absolute value permutation of Xp. By Theorem 7, ∀t∈(0,p), either f1′(t)=(Xpt)′<f2′(t)=(Xp∗t)′ or f1′(t)=(Xpt)′>f2′(t)=(Xp∗t)′. We suppose that f1′(t)=(Xpt)′<f2′(t)=(Xp∗t)′ and hence ∀t∈(0,p) we have f1(t)>f2(t), which implies that Xp0>Xp∗0. This is a contradiction.Theorem 7.
The problemPp generates sparser solution as the value of p decrease when p<γ(A,b).Proof.
If the conclusion does not hold, then there exists the optimal solutionsX1 to the problems (Pp1) and the optimal solutions X2 to the problems (Pp2) satisfying p1<p2<γ(A,b) and X10=s>k=X20. We consider the following two cases.(1)
IfX1p1=X2p1, then X1p2<X2p2 because of Corollary 5 and s>k. This contradicts with the fact that X2 is the optimal solutions to (Pp2).(2)
IfX1p1<X2p1, then X1t and X2t have at least one intersection in (0,p1) because of s>k. Since X2p2≤X1p2, X1t, and X2t have at least one intersection in (p1,p2]. This is contradictory to Corollary 5.Theorem 8.
LetX1 and X2 be the sparsest optimal solution to the problem (Pp1) and problem (Pp2) (p1<p2<γ(A,b)), respectively, and X1 is not the absolute value permutation of X2. Then there exist t1,t2∈[p1,p2] such that when p1≤t≤t1, X1 is the sparsest optimal solution to the problem (Pt) and when t2<t≤p2, X2 is the sparsest optimal solution to the problem (Pt).Proof.
Firstly,X1 is not the optimal solution to Pp2 and hence X1p2>X2p2. In fact, if X1p2=X2p2, then X1p1<X2p1 by Corollary 5 and X1 is the optimal solution to the problem (Pp1). By Corollary 5 again, we have X10<X20 which contradicts with the fact that X2 is the sparsest optimal solutions to (Pp2).
We consider the following two cases.(1)
IfX1p1=X2p1, then, for any p2≥t>p1, X2 is the sparsest optimal solution to the problem (Pt). Otherwise, there exists X3 such that X3t<X2t or X3t=X2t and X30<X20. If X3t<X2t, then X30>X20 by Corollary 5 and X3p1≥X1p1=X2p1, which is contradictory to Theorem 8. If X3t=X2t and X30<X20, then X3p1<X2p1=X1p1 by Corollary 5, which contradicts the fact that X1 is the optimal solutions to (Pp1). Therefore, we pick t1=t2=p1.(2)
IfX1p1<X2p1, then, by X1p2>X2p2, X1t and X2t have one intersection t0 in (p1,p2), and hence X10<X20. We assume, without loss of generality, that X10+2=X20. Let X3 be the sparsest optimal solution to the problem Pt0. Then X3 is not the absolute value permutation of X2. Otherwise, we have X3t0=X2t0=X1t0, that is, X1 is the optimal solution to the problem Pt0. Since X1p1<X2p1=X3p1, we have X10<X30 which contradicts the fact that X3 is the sparsest optimal solution to the problem Pt0.
IfX3 is the absolute value permutation of X1, then X3t0=X1t0=X2t0 and thus, by the proof of case (1), for any p2≥t>t0, X2 is the sparsest optimal solution to the problem (Pt). Obviously, for any p1≤t≤t0, X1 is the sparsest optimal solution to the problem (Pt). Therefore, we pick t1=t2=t0.
IfX3 is not the absolute value permutation of X1, then X30=X10+1 by Corollary 6, and there exist t1∈(p1,t0), t2∈(t0,p2) such that t1 is the intersection of X3t and X1t and t2 is the intersection of X3t and X2t. By the proof above, we have that, for any t≤t1, X1 is the sparsest optimal solution to the problem (Pt) and for any t>t2, X2 is the sparsest optimal solution to the problem (Pt).


## 3. Conclusion

In this paper, the sparsity of underdetermined linear system vialp minimization for 0<p<1 has been studied. Our research reveals that for a given underdetermined linear system of equations Am×nX=b there exists a sparse constant γ(A,b)>0 such that when p<γ(A,b), the problem (Pp) generates sparser solution as the value of p decreases and the sparsest optimal solution to the problem (Pp) is unique under the sense of absolute value permutation and if X1 is not the absolute value permutation of X2 where X1 and X2 are the sparsest optimal solution to the problems (Pp1) and (Pp2) (p1<p2), respectively, then there exist t1,t2∈[p1,p2] such that X1 is the sparsest optimal solution to the problem (Pt) (∀t∈[p1,t1]) and X2 is the the sparsest optimal solution to the problem (Pt) (∀t∈(t2,p2]).



---

*Source: 584712-2015-04-28.xml*