# Method of Lagrange Multipliers for Normalized Zero Norm Minimization

Authors: Bamrung Tausiesakul
Journal: Mathematical Problems in Engineering
 (2022)

---

## Abstract

We present a normalization of thep-norm. A compressive sensing criterion is proposed using the normalized zero norm. Based on the method of Lagrange multipliers, we derive the solution of the proposed optimization framework. It turns out that the new solution is a limit case of the least fractional norm solution for p=0, where its fixed-point iteration algorithm can readily follow an existing algorithm. The derivation of the minimal normalized zero norm solution herein gives a relation in the aspect of Lagrange multiplier method to existing works that invoke least fractional norm and least pseudo zero norm criteria.


---

## Body

## 1. Introduction

Various applications in science and engineering need to recover a desired signalx∈ℝN×1 from a set of observed data or measured data b∈ℝM×1 based on a modeling or measurement matrix A∈ℝM×N, which either depends on the model or can be chosen beforehand, for N∈ℕ1×1 and M∈ℕ1×1. A linear system in Figure 1 can be represented by(1)Ax+δb=b,where δb∈ℝM×1 is the amount of perturbation hidden in the output b.Figure 1
A noisy linear input-output system.The signal can be recovered by solving an optimization problem related to linear least squares (LLS), i.e.,(2)x^LLS=argminxx22s.t.x∈x∈ℝN×1|Ax=b,noiseless,x∈ℝN×1|Ax−b2<ε,noisy,where ε is the square root of the maximal allowable noise power [1]. Usually, the matrix A is of full rank, i.e.,(3)rankA=minM,N,where rank⋅ is the rank of matrix. Whether the number of provided data M is greater than, equal to, or less than the number of unknown variables N, i.e., the size of the matrix A, the LLS problem can be classified into(4)x^LLS=argminxAx−b22,M>N,argxAx=b,M=N,argminxx22s.t.Ax=b,M<N.The solution of (4) is well known as the LLS estimate(5)x^LLS=ATA−1ATb,M>N,A−1b,M=N,ATAAT−1b,M<N,where ⋅T is the transpose of a vector or matrix, and ⋅−1 is the inverse of square matrix. The LLS estimate exists provided that the matrix ATA or A or AAT is invertible, i.e., the measurement matrix A needs to be of full rank. The LLS estimate x^LLS provides all nonzero entries to the desired signal x.Many works indicate that the desired signal often is subject to sparsity, i.e., the situation when a number of elements inx are zeros. Even though the signal sometimes does not strictly entail the sparsity, it is efficient to keep an approximate value of the signal that contains only a sufficient amount of its largest components, from which we called compressible signal. The sparsity nature of the signal is usually hidden and can be exposed by discovering a sparse basis and its associated spanning coefficients. The decomposition of the coefficient vector can be seen as a superposition of dictionary elements with a remaining term [2]. Compressed sensing was an emerging field that spans many applications in science and engineering, e.g., imaging and vision [3], photonic mixer device [4], electronic defense [5], security and cryptosystem [6], radar [7, 8], earth observation [9], wireless networks [10, 11], biometric watermarking [12], and healthcare [13].In compressive sensing, theℓ0-norm is originally adopted to impose the zero elements in the solution. The optimization of ℓ0-norm criterion however appears to be a combinatorial nondeterministic polynomial-time hard (NP-hard) problem, which appears to be prohibitive. The performance of the above optimization problem can however be analyzed, e.g., in [14].Instead of theℓ0-norm, ℓ1-norm is often of interest because it is more convenient than ℓ0-norm optimization in terms of computability while its accuracy is comparable (see e.g., [15, 16]). A widely considered method designed for norm minimization of dictionary coefficients is known as matching pursuit [17]. Its variations are presented in terms of basis pursuit denoising [2], orthogonal matching pursuit [18], compressive sampling matching pursuit [19], stagewise orthogonal matching pursuit [20], gradient pursuits [21], etc. Most approaches based on the matching pursuit involve the ℓ2-norm, except for basis pursuit denoising, which considers the ℓ1-norm.In this work, we point out that the zero norm that is mostly adopted in compressed sensing literature is not the actual zero norm, but rather a pseudo zero norm. We also show that the actual zero norm is unbounded and thus trivial. Later we present a normalizedp-norm and apply its special case for p=0 to be a new objective function. By using the method of Lagrange multipliers, the proposed constrained optimization is solved and the emerging solution is equal to the limit case of that given by the least fractional norm for p=0.This paper is organized as follows. In Section2, we point out that the ℓ0 norm is diverged or undefined, whereas the so-called zero norm adopted in compressive sensing is actually not a proper norm or is only a pseudonorm. In Section 3, we propose a normalized ℓp norm. It is later shown that for p=0 the normalized zero norm is approximately a geometrical mean and unfortunately it does not hold the triangle inequality of the proper norm. In Section 4, we consider the compressive sensing model. The fractional norm for p∈0,1 and its criterion presented in the past are revisited herein. The corresponding solution is found by the method of Lagrange multiplier. In Section 5, we propose an alternative criterion based on the normalized zero norm. We later derive its solution through the method of Lagrange multiplier. The solution is found in a closed form and unfortunately turns to be a limiting case to that of the least fractional norm criterion in the former works. In Section 6, numerical examples of the solution are provided in conjunction with other works. Concluding remarks of the paper are provided in Section 7.


## 2. Conventional Zero Norm

Letz∈ℂN×1 be a complex-valued vector, expressed as(6)z=z1z2⋯zNT.Letp∈ℤ+ be a positive integer. The ℓp-norm, or simply the p-norm, ⋅p:ℂN×1↦ℝ1×1, is given by(7)zp=z1p+z2p+⋯+zNp1/p,where ⋅ is the absolute value of ⋅. Basic properties of the p-norm in (7) are as follows:(i)
Thep-norm is positive-definite, i.e.,(8)zp≥0.(ii)
Thep-norm is zero if and only if the vector z is zero, i.e.,(9)zp=0⇔z=0,where0 is a zero vector whose all elements are zeros.(iii)
Thep-norm has a triangle inequality, i.e.,(10)z+βp≤zp+βp,forz∈ℂN×1 and β∈ℂN×1.(iv)
Furthermore, thep-norm has a scalability or homogeneity, which can be shown as(11)azp=azp,fora∈ℝ1×1 and z∈ℂN×1.


### 2.1. Zero Norm

Whenp is zero, the 0-norm of a vector can be determined from(12)z0=limp⟶0z1p+z2p+⋯+zNp1/p=limp⟶0eplnz1+eplnz2+⋯+eplnzN1/p,where e⋅ is the exponential function of ⋅. From the Taylor’s series expansion, we can express(13)eplnzn=∑k=0∞1k!plnznk=10!plnzn0+11!plnzn+12!plnzn2+….For a small value ofp, i.e., p⟶0, we can approximate(14)eplnzn=1+plnzn+Op2ln2zn≈1+plnzn,where O⋅ is the big ‘oh’ notation of Bachmann–Landau symbols, i.e.,(15)fx=Ogx;x⟶a⇔limsupx⟶afxgx<∞.Substituting (14) into (12), we obtain(16)z0≈limp⟶01+plnz1+1+plnz2+⋯+1+plnzN1/p=limp⟶0N+p∑n=1Nlnzn1/p.By using a property of logarithm power, we can show that(17)z0=limp→0N1/p1+1Npln∏n=1Nzn1/p=limp→0N1/p1+pln∏n=1Nzn1/N1/p≈limp→0N1/peln∏n=1NznN=limp→0N1/p∏n=1NznN→∞.It is obvious that the 0-norm is unbounded and thus trivial.


### 2.2. Pseudo Zero Norm

Most works, however, instead consider(18)limp⟶0zpp=limp⟶0z1p+z2p+⋯+zNp1/pp=z10+z20+⋯+zN0.By assigning00 to 0, we have a convenient relation(19)limp⟶0zpp=zn|zn≠0;n=1,2,…,N,where ⋅ is the cardinality of a set ⋅ or herein the number of nonzero members in a set ⋅. The pseudo zero norm counts the number of nonzero elements in z. It is important to note that the pseudo zero norm limp⟶0⋅pp actually is not the zero norm ⋅0 and is not a proper norm, because it does not preserve the homogeneity. However, it is widely used to replace the zero norm ⋅0 due to its simple computability.


## 2.1. Zero Norm

Whenp is zero, the 0-norm of a vector can be determined from(12)z0=limp⟶0z1p+z2p+⋯+zNp1/p=limp⟶0eplnz1+eplnz2+⋯+eplnzN1/p,where e⋅ is the exponential function of ⋅. From the Taylor’s series expansion, we can express(13)eplnzn=∑k=0∞1k!plnznk=10!plnzn0+11!plnzn+12!plnzn2+….For a small value ofp, i.e., p⟶0, we can approximate(14)eplnzn=1+plnzn+Op2ln2zn≈1+plnzn,where O⋅ is the big ‘oh’ notation of Bachmann–Landau symbols, i.e.,(15)fx=Ogx;x⟶a⇔limsupx⟶afxgx<∞.Substituting (14) into (12), we obtain(16)z0≈limp⟶01+plnz1+1+plnz2+⋯+1+plnzN1/p=limp⟶0N+p∑n=1Nlnzn1/p.By using a property of logarithm power, we can show that(17)z0=limp→0N1/p1+1Npln∏n=1Nzn1/p=limp→0N1/p1+pln∏n=1Nzn1/N1/p≈limp→0N1/peln∏n=1NznN=limp→0N1/p∏n=1NznN→∞.It is obvious that the 0-norm is unbounded and thus trivial.


## 2.2. Pseudo Zero Norm

Most works, however, instead consider(18)limp⟶0zpp=limp⟶0z1p+z2p+⋯+zNp1/pp=z10+z20+⋯+zN0.By assigning00 to 0, we have a convenient relation(19)limp⟶0zpp=zn|zn≠0;n=1,2,…,N,where ⋅ is the cardinality of a set ⋅ or herein the number of nonzero members in a set ⋅. The pseudo zero norm counts the number of nonzero elements in z. It is important to note that the pseudo zero norm limp⟶0⋅pp actually is not the zero norm ⋅0 and is not a proper norm, because it does not preserve the homogeneity. However, it is widely used to replace the zero norm ⋅0 due to its simple computability.


## 3. Normalized Zero Norm

Let us introduce a normalization of thep-norm ⋅p as(20)zp¯=1Nz1p+z2p+⋯+zNp1/p.In statistical analysis ([22], Ch. 3), the above quantity is known as p-mean, a generalized mean, Hölder mean, mean of degree p, power mean, etc. We can represent the relation between the normalized p-norm and the conventional p-norm by(21)zp¯=1N1/pz1p+z2p+⋯+zNp1/p=1N1/pzp¯.Whenp is zero, we can derive(22)z0¯=limp⟶01N1/pz1p+z2p+⋯+zNp1/p=limp⟶01N1/peplnz1+eplnz2+⋯+eplnzN1/p.Using the Taylor’s series expansion of the exponential function, we have(23)z0¯=limp⟶01N1/p∑n=1N∑k=0∞1k!plnznk1/p=limp⟶01N1/p∑k=0∞1k!pk∑n=1Nlnkzn1/p.It is hard to deal with the result in (23). We would rather consider an approximation of (22) associated with (14), which is given by(24)z0¯≈limp⟶01N1/p1+plnz1+1+plnz2+⋯+1+plnzN1/p.Under the same manipulation, we can show that(25)z0¯+limp⟶01N1/pN+p∑n=1Nlnzn1/p=limp⟶01N1/pN1/p1+1Np∑n=1Nlnzn1/p=limp⟶01+p∑n=1Nlnzn1/N1/p=limp⟶01+pln∏n=1Nzn1/N1/p≈limp⟶0epln∏n=1Nzn1/N1/p=limp⟶0∏n=1NznN=∏n=1NznN.We can see that due to the first-order Taylor series approximation,z0¯ can be approximated by the geometric mean of z. The geometric mean ∏n=1NznN has the following properties:(i)
It is positive-definite for anyz, i.e.,(26)z1z2…zN1/N≥0.(ii)
It can simply be zero when only one of all entries inz is zero, i.e.,(27)z1z2…zN1/N=0⇔zn=0;n∈1,2,…,N.(iii)
It does not hold the triangle inequality, e.g., forα∈ℂ1×1 and β∈ℂ1×1,(28)α0+0β0¯=αβ0¯=α‖β,α00¯+0β0¯=0+0=0,which meanα0+0β0¯≰α00¯+0β0¯.(iv)
It is homogeneous, i.e.,(29)αz0¯=αz1αz2…αzN1/N=αz1αz2…αzN1/N=αNz1z2…zN1/N=αz1z2…zN1/N=αz0¯.(v)
It is concave for anyz (see, e.g., [23]) and a monotonically increasing function.


## 4. Compressive Sensing

Let us consider an underdetermined system where there are more unknown signal components than equations, i.e.,M<N. In this case, there is infinite number of solutions for x. Recent works indicate that the desired signal often is subject to sparsity, i.e., the situation when a number of elements in x are zeros. Even though sometimes the signal does not strictly entail the sparsity, it is efficient to keep an approximate version that contains only a sufficient amount of its largest components, from which we called compressible signal. The sparsity nature of the signal is hidden and can be imposed by discovering a sparse basis and its associated spanning coefficients. The decomposition of the coefficient vector can be seen as a superposition of dictionary elements with a remaining term [2]. Let K∈ℤ+1×1 be the number of nonzero elements in x. If x0 is the true value of x, there is a relation(30)limp⟶0x0pp=suppx0=K,where ⋅ is the cardinality of set, and suppx=n|xn≠0 is the support set or the sparsity pattern of x. The number K is often known as sparsity degree. Compressive sensing can be seen as a problem of finding a K-sparse signal x [24]. Unfortunately, the solution in (5) does not preserve the inherent sparsity of the signal. A different kind of vector norms can be used to explore the signal sparsity. The signal recovery can be formulated as an optimization problem, i.e.,(31)x^0=argminxlimp⟶0xpps.t.x∈x|Ax=b,noiseless,x|Ax−b2<ε,noisy.Note that we do not express the norm in (31) as ⋅0 similarly to most works, because the zero norm in most works is equal to the pseudo zero norm limp⟶0⋅pp in this paper. In general, the objective function in terms of the modified zero norm limp⟶0⋅pp is nonconvex. If A is an identity matrix, an exact solution of (31) is a hard shrinkage of b. For arbitrary matrix A, one may resort to combinatorial optimization. Even an approximate value of the true minimum of the problem in (31) is nondeterministic polynomial-time hard or NP-hard, which appears to be prohibitive. The performance of the above optimization problem can, however, be analyzed, e.g., in [14].


### 4.1. Compressive Sensing by Fractional Norm

An alternative way is the consideration ofp≤1 [24–26]. When p lies in the range 0,1,(i)
the normxp accepts only a positive real-valued argument, i.e., x∈ℝ+N×1,(ii)
it is a concave function, and(iii)
the fractional norm does not hold the triangle property, e.g.,(32)10+01p=11p=1p+1p1/p=21/p,(33)10p+01p=1p1/p+1p1/p=2,mean(34)10+01p≰10p+01p.The last one implies that the fractional norm is not a proper norm or is only a quasinorm. Forp∈0,1, the compressive sensing problem(35)x^p=argminxxpps.t.x∈x|Ax=b,noiseless,x|Ax−b2<ε,noisy,is nonconvex, nonsmooth, and non-Lipschitz. The fractional norm gives a closer approximation to the pseudo zero norm than the 1-norm, since the smaller the norm index p, the sparser the solutions. It is shown in [27] that although a local minimum is found, exact reconstruction is possible with much sparser solution than that required by the 1-norm reconstruction. The case of p=1/2 provides the sparsest solution for p∈1/2,1, while the compressive sensing solution with p∈0,1/2 has no significant difference from that with p∈1/2,1 [28, 29].


### 4.2. Method of Lagrange Multipliers

Letλ∈ℂM×1 be the Lagrange constants. The constrained optimization problem in (35) can be solved by [25], i.e.,(36)x^p,λ^p=argminx,λLpx,λ,where Lpx,λ is given by(37)Lpx,λ=xpp+λTAx−b.The solution of (36) is given by [30](38)x^p=Dx2−pATADx2−pAT−1b,where D⋅ is the diagonal matrix whose diagonal is taken from vector ⋅, and xa is given by(39)xa=x1ax2a⋮xNa.We can see that whenp is equal to 2, the least fractional norm criterion provides the same result as that shown in (5), i.e.,(40)limp⟶2x^p=x^2=x^LLS.Unlike the solution by the LLS criterion in (5), the solution by the fractional norm in (38) depends on the unknown variable x, which later needs to be involved with an iterative computation. The computation procedure in an iterative way, which is known as FOCal Underdetermined System Solver (FOCUSS), is summarized in [30].Algorithm 1: FOCal Underdetermined System Solver [30].
Input:A∈ℝM×N, b∈ℝM×1, p∈0,1, Nmax∈ℤ+1×1, εmin∈ℝ+1×1Output:x^p∈ℝN×1x^0←1i←0εx^←εmin+1whileεx^>εmin∧i≤Imaxdoi←i+1x^i←Dx2−pATADx2−pAT−1b|x=x^i−1εx^←x^i−x^i−12/x^i−12end whilereturnx^iAlgorithm1 can suffer from many local minima. An alternative tries to avoid the NP-hard problem for p∈0,1 by sequentially minimizing a smooth function.Sometimes, the least fractional exponent norm criterion is called iteratively reweighted least squares (IRLS) in compressive sensing [31–33]. When the vector x^i−1 in Algorithm 1 converges to the true value of x, a number of elements in x^i−1 may be close to zeros, which can cause an ill condition of the matrix ADx^i−1|2−pAT. It is suggested in [31] that(41)x^i←Dx2+εr11−1/2pAT,ADx2+εr11−1/2pAT−1b|x=x^i−1,where εr∈ℝ1×1 is a regularization quantity that is large at the beginning of the iteration and gradually smaller when the iteration converges. In [32], the regularization quantity εr in (41) is replaced by its square εr2. Let ℓx be a nonincreasing set of all elements in x, which can be represented by(42)ℓx=ln1|ln1=xn2;n1,n2∈1,2,…,N∧l1≥l2≥…≥lN.LetLkx be the kth element of the nonincreasing set ℓx, i.e., Lkx=lk.Algorithm 2: Iteratively reweighted least squares [31, 32].
Input:A∈ℝM×N, b∈ℝM×1, p∈0,1, k∈ℤ+1×1Output:x^p∈ℝN×1x^0←1w^0←1ε^r0←1i←0whileε^ri≠0doi←i+1ε^ri←minε^ri−1,1/NLk+1x^i−1x^i←Dw^i−1ATADw^i−1AT−1bw^i←x^2i+ε^r2i11−1/2pend whilereturnx^iAlgorithm2 is different from [32] in two aspects. First, the regularization parameter εri in [32] is computed from the updated x^i at the ith iteration, which is unavailable. Second, the procedure addressed in [32] considers only p=1.


## 4.1. Compressive Sensing by Fractional Norm

An alternative way is the consideration ofp≤1 [24–26]. When p lies in the range 0,1,(i)
the normxp accepts only a positive real-valued argument, i.e., x∈ℝ+N×1,(ii)
it is a concave function, and(iii)
the fractional norm does not hold the triangle property, e.g.,(32)10+01p=11p=1p+1p1/p=21/p,(33)10p+01p=1p1/p+1p1/p=2,mean(34)10+01p≰10p+01p.The last one implies that the fractional norm is not a proper norm or is only a quasinorm. Forp∈0,1, the compressive sensing problem(35)x^p=argminxxpps.t.x∈x|Ax=b,noiseless,x|Ax−b2<ε,noisy,is nonconvex, nonsmooth, and non-Lipschitz. The fractional norm gives a closer approximation to the pseudo zero norm than the 1-norm, since the smaller the norm index p, the sparser the solutions. It is shown in [27] that although a local minimum is found, exact reconstruction is possible with much sparser solution than that required by the 1-norm reconstruction. The case of p=1/2 provides the sparsest solution for p∈1/2,1, while the compressive sensing solution with p∈0,1/2 has no significant difference from that with p∈1/2,1 [28, 29].


## 4.2. Method of Lagrange Multipliers

Letλ∈ℂM×1 be the Lagrange constants. The constrained optimization problem in (35) can be solved by [25], i.e.,(36)x^p,λ^p=argminx,λLpx,λ,where Lpx,λ is given by(37)Lpx,λ=xpp+λTAx−b.The solution of (36) is given by [30](38)x^p=Dx2−pATADx2−pAT−1b,where D⋅ is the diagonal matrix whose diagonal is taken from vector ⋅, and xa is given by(39)xa=x1ax2a⋮xNa.We can see that whenp is equal to 2, the least fractional norm criterion provides the same result as that shown in (5), i.e.,(40)limp⟶2x^p=x^2=x^LLS.Unlike the solution by the LLS criterion in (5), the solution by the fractional norm in (38) depends on the unknown variable x, which later needs to be involved with an iterative computation. The computation procedure in an iterative way, which is known as FOCal Underdetermined System Solver (FOCUSS), is summarized in [30].Algorithm 1: FOCal Underdetermined System Solver [30].
Input:A∈ℝM×N, b∈ℝM×1, p∈0,1, Nmax∈ℤ+1×1, εmin∈ℝ+1×1Output:x^p∈ℝN×1x^0←1i←0εx^←εmin+1whileεx^>εmin∧i≤Imaxdoi←i+1x^i←Dx2−pATADx2−pAT−1b|x=x^i−1εx^←x^i−x^i−12/x^i−12end whilereturnx^iAlgorithm1 can suffer from many local minima. An alternative tries to avoid the NP-hard problem for p∈0,1 by sequentially minimizing a smooth function.Sometimes, the least fractional exponent norm criterion is called iteratively reweighted least squares (IRLS) in compressive sensing [31–33]. When the vector x^i−1 in Algorithm 1 converges to the true value of x, a number of elements in x^i−1 may be close to zeros, which can cause an ill condition of the matrix ADx^i−1|2−pAT. It is suggested in [31] that(41)x^i←Dx2+εr11−1/2pAT,ADx2+εr11−1/2pAT−1b|x=x^i−1,where εr∈ℝ1×1 is a regularization quantity that is large at the beginning of the iteration and gradually smaller when the iteration converges. In [32], the regularization quantity εr in (41) is replaced by its square εr2. Let ℓx be a nonincreasing set of all elements in x, which can be represented by(42)ℓx=ln1|ln1=xn2;n1,n2∈1,2,…,N∧l1≥l2≥…≥lN.LetLkx be the kth element of the nonincreasing set ℓx, i.e., Lkx=lk.Algorithm 2: Iteratively reweighted least squares [31, 32].
Input:A∈ℝM×N, b∈ℝM×1, p∈0,1, k∈ℤ+1×1Output:x^p∈ℝN×1x^0←1w^0←1ε^r0←1i←0whileε^ri≠0doi←i+1ε^ri←minε^ri−1,1/NLk+1x^i−1x^i←Dw^i−1ATADw^i−1AT−1bw^i←x^2i+ε^r2i11−1/2pend whilereturnx^iAlgorithm2 is different from [32] in two aspects. First, the regularization parameter εri in [32] is computed from the updated x^i at the ith iteration, which is unavailable. Second, the procedure addressed in [32] considers only p=1.


## 5. Compressive Sensing by Normalized Zero Norm

We propose a new criterion by using the normalized zero norm. Under a similar idea to (32), the usual compressive sensing problem can alternatively be formulated as(43)x^0¯=argminxx0¯s.t.x∈x|Ax=b,noiseless,x|Ax−b2<ε,noisy,≈argminx∏n=1NxnNs.t.x∈x|Ax=b,noiseless,x|Ax−b2<ε,noisy.Fortunately, when approximated as the geometrical mean in (25), the normalized zero norm makes the optimization problem nonconvex under a concave objective function and an affine/convex constraint.The Lagrange function can be expressed as(44)L0¯x,λ=∏n=1NxnN+λTAx−b.The derivative of the Lagrange functionL0¯x,λ with respect to x and λ can be written as(45)∂∂x∂∂λL0¯x,λ=∂∂x∏n=1NxnN+∂∂xλTAx−b∂∂λλTAx−b=∂∂x∏n=1NxnN+∂∂xxTATλAx−b=ATλ+ddx∏n=1NxnNAx−b.We can show that(46)ddx∏n=1NxnN=ddx1ddx2⋮ddxN∏n=1Nxn1/N=ddx1x11/N∏n=2,≠1Nxn1/Nddx2x21/N∏n=1,≠2Nxn1/N⋮ddxNxN1/N∏n=1,≠NNxn1/N.Using the chain rule for a real-valued variablexn, the derivative d/dxn∑n=1Nxnp can be written as(47)ddxnxnp=ddxnxnp,xn≥0,−xnp,xn<0,=pxnp−1,xn≥0,−p−xnp−1,xn<0,=xnxnpxnp−1=pxnp−2xn.By using the result from (47), we can derive(48)ddx∏n=1NxnN=1Nx11/N−2x1∏n=2,≠1Nxn1/N1Nx21/N−2x2∏n=1,≠2Nxn1/N⋮1NxN1/N−2xN∏n=1,≠NNxn1/N=1Nx1x12∏n=1Nxn1/Nx2x22∏n=1Nxn1/N⋮xNxN2∏n=1Nxn1/N=1N∏n=1NxnND−1x2x.At the critical point∂/∂xL0¯x,λ=0, we have(49)ATλ+1N∏n=1NxnD−1x2xN=0⇔x^0¯=−1∏n=1NxnNNDx2ATλ.At the critical point∂/∂λ∗L0¯x^0¯,λ=0, we have(50)Ax−b=0⇔−1∏n=1NxnNNADx2ATλ=b⇔λ^0¯=−1N∏n=1NxnNADx2AT−1b.Substituting (50) into (49), we obtain(51)x^0¯=Dx2ATADx2AT−1b.It should be noted that the result in (51) is equal to (38) with p=0. Thus, the compressive sensing problem using the geometric mean is the limit case of the fractional norm problem for p∈0,1 in (35), i.e.,(52)limp⟶0x^p=x^0¯,and tends to be the desired but complicated problem with the pseudo zero norm in (31). Although the solution of the minimization of the normalized zero norm by Lagrange multiplier method appears to be the same as the former works, it gives a relation in the Lagrange multiplier method point of view to existing works that invoke least fractional norm and least pseudo zero norm criteria.


## 6. Numerical Examples

All computer simulations in this work are conducted using Python language. The root-mean-squared relative error (RMSRE), denoted by(53)Ex0x^−x022x022=Ex0x^−x02x022,is the index for evaluating the performance of each algorithm. It is calculated by the square root of the probabilistic average of the square of the normalized estimation error, where the expectation Ex0⋅ is taken into account with respect to the randomization caused by(i)
the true value ofx0, which is assumed to follow an identical and independent real-valued Gaussian distribution with zero mean and unit variance, i.e.,(54)x0∼Nℝ0,IN,(ii)
the sparsity pattern of allK nonzero elements in x0, which is assumed to have an equal probability for K locations on all N possible positions (K<N for a sparse signal vector).The algorithms intended to comparison include(i)
ℓ1-norm, the problem in (4) whose Euclidean norm ⋅2 is replaced by the ℓ1-norm, i.e., ⋅1,(ii)
ℓ2-norm, the problem in (4),(iii)
FOCUSS, Algorithm1 with εmin=10−7 and the maximum number of iterations of Nmax=30,(iv)
IRLS, Algorithm2 with k=K−1, and(v)
Theoretical approximate normalized zero norm (TANZN); the best possibility of the first iteration of the fixed-point iteration in (52), calculated by substituting x by the theoretical or true value x=x0, i.e.,(55)x^0¯=Dx02ATADx02AT−1b.The minimizations of theℓ1-norm and ℓ2-norm subject to Ax=b are conducted by an interior-point solver for convex optimization [34]. For both fixed-point iteration methods, such as the FOCUSS and the IRLS, the norm exponent is assumed to be p=0.8. It should be noted that the solution in (55) is the ideal case of (51), because the true value x0 is unknown. The realistic implementations of (55) were addressed in the past, e.g., in terms of the FOCUSS, the IRLS, etc. The design of a more accurate algorithm to the fixed-point iteration required by (51) may remain open for a future work. The matrix inverse in (55) is usually subject to a large condition number, which can cause a numerical failure. One has to resolve this numerical instability by adding a tiny amount, e.g., 10−6, to each diagonal element of ADx02AT before its inverse operation.In Figure2, numerical computation is done with M=128 and N=256 from NR=10,000 independent runs for each value of K. One can see that the ℓ1-norm approach is very precise from K=2 to K=32. At this critical region, the error abruptly arises probably because it is beyond the capability of the interior-point method in the convex optimization. The ℓ2-norm method does not explore the sparsity nature of the signal vector and thus performs worst. The IRLS performs almost identically to the FOCUSS, except for a little better performance during the transition region. The ideal TANZN method stays constant for any value of K. It is worse than its actual implementations, such as the FOCUSS and the IRLS, for K<10. However, it is worth noting that both fixed-point iteration techniques each involve multiple iterations, e.g., maximal Nmax=30 iterations in the FOCUSS, while the TANZN represents the best case for a single substitution or the first iteration.Figure 2
RMSRE as a function ofK from NR=10,000 independent runs.In Figure3, we assume that the length of the input elements is N=256 and the number of nonzero elements is K=⌊0.3125M⌋, which depends on the number output elements M, where ⌊⋅⌋ is the operator of rounding to the nearest lower integer. One can see that when more observed data are available, the RMSRE decreases or the signal acquisition is more precise from all the abovementioned methods. The FOCUSS approach preforms identically to the IRLS algorithm. The ℓ1-norm minimization is the realistic method that provides the least amount of signal recovery error. The TANZAN technique indicates that if the desired signal x reaches its true value, the possible acquisition error can be lower than that by the ℓ1-norm minimization.Figure 3
RMSRE as a function ofM from NR=10,000 independent runs.


## 7. Conclusion

A normalization of thep-norm, denoted by ⋅p¯ is presented. A compressive sensing criterion using the normalized zero norm ⋅0¯ is proposed. Based on the method of Lagrange multipliers, the solution of the proposed optimization framework, i.e., x^0¯ is derived. It turns out that the new solution is a limit case of the fractional norm solution for p=0, where its fixed-point algorithm can readily follow the FOCUSS algorithm in [30]. In our companion works, we find that the minimization of the normalized zero norm by Tikhonov regularization method provides a different solution from that of the fractional norm [28, 29].



---

*Source: 8711843-2022-01-20.xml*