Difference of two norms-regularizations for Q-Lasso

The process of compressive sensing (CS) [8], which consists of encoding and decoding, is rapidly consolidated year after year due to the blooming of large datasets which become increasingly important and available. The process of encoding involves taking a set of (linear) measurements, $b=Ax$⁠, where A is a matrix of size $m×n$⁠. If $m<n$⁠, we can compress the signal $x∈IRn$⁠, whereas the process of decoding is to recover x from b where x is assumed to be sparse. It can be formulated as an optimization problem, namely

where $∥⋅∥0$ is the $l0$ norm, which counts the number of nonzero entries of x; namely

with $|·|$ being here the cardinality, i.e., the number of elements of a set. Hence minimizing the $l0$ norm amounts to finding the sparsest solution. One of the difficulties in CS is solving the decoding problem above, since $l0$ optimization is NP-hard. An approach that has gained popularity is to replace $l0$ by the convex norm $l1$ since it often gives a satisfactory sparse solution and has been applied in many different fields such as geology and ultrasound imaging.

More recently, nonconvex metrics were used as alternative approaches to $l1$⁠, especially the nonconvex metric $lp$ for $p∈(0,1)$ in [6] which can be interpreted as a continued approximation strategy of $l0$ as $p→0$⁠. A great deal of research has been conducted into $lp$ problems including all kinds of variants and related algorithms, as you can see in [4] and references therein. The convex $l1$ relaxation compared to the nonconvex problem (⁠$lp$⁠) is generally more difficult to handle. However, it was shown in [12] that the potential reduction method can solve this special nonconvex problem in polynomial time with arbitrarily given accuracy.

Most recently, the majority of such sparsity inducing functions are unified as the notion of DC programming in [9], including log-sum, smoothly clipped absolute deviation and capped-$l1$ penalty. Generally, DC programming problem can be solved through a primal–dual convex relaxations algorithm which is famous in the literature of DC Programming [11]. Other algorithms appeared as for solving application problems of DC programming in the area of finance and insurance, data analysis, machine learning as well as signal processing. However, as noted in [18], among the above mentioned DC programming approaches for sparse reconstruction, most of them are mainly preserving the separability properties of both $l0$ and $l1$ norms.

To begin with, let us recall that the lasso of Tibshirani [16] is given by the following minimization problem

A being an $m×n$ real matrix, $b∈IRm$ and $γ>0$ is a tuning parameter. The latter is nothing else than the basic pursuit (BP) of Chen et al. [7], namely

However, the constraint $Ax=b$ being inexact due to errors of measurements, the problem (1.4) can be reformulated as

where $ε>0$ is the tolerance level of errors and p is often $1,2$ or $∞$⁠. It is noticed in [1] that (1.5) can be rewritten as

in the case when $Q:=Bε(b)$⁠, the closed ball in $IRn$ with center b and radius $ε$⁠.

Now, when Q is a nonempty closed convex set of $IRm$ and $PQ$ the orthogonal projection from $IRm$ onto the set Q and by observing that the constraint is equivalent to the condition $Ax−PQ(Ax)=0$⁠, this leads to the following Lagrangian formulation

$γ>0$ being a Lagrangian multiplier.

A link is also made in [1] with split feasibility problems [5] which consist in finding x satisfying

with C and Q two nonempty closed convex subsets of $IRn$ and $IRm$⁠, respectively. An equivalent formulation of (1.8) as a minimization problem is given by

and its $l1$-regularization is

with $γ>0$ a regularization parameter.

This convex relaxation approach was frequently employed, see for example [1,20] and references there in. As the level curves of $l1$-$l2$ are closer to $l0$ than those of $l1$⁠, this motivated us in [14] to propose a regularization of split feasibility problems by means of the nonconvex $l1$-$l2$⁠, namely

and present three algorithms with their convergence properties [14]. Unlike the separable sparsity inducing functions involved in the aforementioned DC programming for problem $(l0)$⁠, we are interested in the two first sections of this work to two specific types of DC programming with un-separable objective functions, which are in the form of difference functions between two norms, namely the new notion $lσq$ denoting the sum of q largest elements of a vector in magnitude (i.e., the $l1$ norm of q-term best approximation of a vector) introduced in [18] and the classical $lr$ norm with $r>1$⁠. Obviously $lσq$ and $lr$$(r>1)$ are regular convex norms. The corresponding DC programs are as follows:

and

where $ε∈(0,1],∥x∥σq$ is defined as the sum of the q largest elements of x in magnitude, $q∈{1,2,···n}$ and $r>1$⁠. We would like to emphasize that the following least-squares variant of (1.12) and (1.13), were studied in the recent work by Wang [18]:

where $μ>0$ and $ε∈(0,1)$⁠, and

where $r>0$ and $ε∈(0,1)$⁠.

This paper proposes generalizations to Q-Lasso, namely

where $μ>0$ and $ε∈(0,1)$⁠, as well as

where $r>0$ and $ε∈(0,1)$⁠, and our attention will be focused on the algorithmic aspect.

The rest of the paper is organized as follows. In Sections 2 and 3, two DC-penalty methods instead of conventional methods such as $l1$ or $l1−l2$ minimization are proposed. Their convergence to a stationary point are also analyzed. The first iterative minimization method is based on the gradient proximal algorithm and the second one is designed by means of the majored penalty strategy. Furthermore, relying on DCA (difference of convex algorithm) two other algorithms are proposed and their convergence results are established in Section 3 and 4.

First, we recall that the subdifferential of a convex function $φ$ is given by

Each element of $∂φ(x)$ is called subgradient. If $φ(x)=12∥(I−PQ)Ax∥2$⁠, it is well-known that

and when $φ(x)=∥x∥1$⁠, we have

The indicator function of a set $C⊆IRn$ is defined by

Moreover, the normal cone of a set C at $x∈C$⁠, denoted by $NC(x)$ is defined as

Connection between the above definitions is given by the key relation $∂iC=NC$⁠.

In this section our interest is in solving the DC programming

where $μ>0$ and $ε∈(0,1)$⁠.

Similar to $l1$ norm, $l2$ norm, etc., we adopt the notation $∥x∥σq$ to denote the norm of $lσq$ which is defined a line below (1.13) and we design an iterative algorithm based both on a generalized q-term shrinkage operator and on the proximal gradient algorithm framework.

At this stage, observe that the restriction on $ε$ guarantees that $f(x)≥0$ for all x. To solve (2.6), we consider the following standard proximal gradient algorithm:

• 1. Initialization: Let $x0$ be given and set $L>λmax(ATA)$ with $λmax(ATA)$ the maximal eigenvalue.

• 2. For $k=0,1,···$ find

Observe that subproblem (2.7) can equivalently formulated as

Thus, it suffices to consider the solutions to the following minimization problem

with a given vector y and positive numbers $λ1>λ2>0$⁠. An explicit solution of this problem is given by the following result, see [18].

Proposition 2.1 Let ${i1,⋯,in}$ be the indices such that

Then $x∗:=proxλ1∥x∥1−λ2∥x∥σq(y)$ with

is a solution of(2.9).

The proximal operator above (called the generalized q-term shrinkage operator in [18]) amounts to write the algorithm as follows:

Proximal Gradient Algorithm:

• 1.

  Start: Let $x0$ be given and set $L>λmax(ATA)$ with $λmax(ATA)$ the maximal eigenvalue.

• 2.

  For $k=0,1,⋯$ find

Sort $yk+1$ as $|yi1|≥|yi2|≥⋯≥|yin|,$

where $l=1,⋯,q$⁠.

End.

Now, we are in a position to show the following convergence result of the scheme (2.7):

Proposition 2.2 The sequence $(xk)$ generated by the Proximal Gradient Algorithm above converges to a stationary point of problem (2.6).

Proof. Remember that $h(x)=12∥(I−PQ)Ax∥2$ is differentiable and its gradient $∇h(x)=AT(I−PQ)Ax$ is Lipschitz continuous with constant $L˜:=λmax(ATA)$⁠. By [3]-Proposition A.24, we have

Combining this with definition of $xk+1$⁠, we obtain

Since $L>L˜$⁠, we see immediately that $f(xk+1)≤f(xk)$ and thus the sequence $(f(xk))$ is convergent since f is a non-negative function. Furthermore, we obtain that $∑k∥xk+1−xk∥2<+∞$ which follows by summing (2.12) from $k=0$ to $∞$⁠. As a further consequence, we note that

Since $μ(1−ε)>0$⁠, we have that $(xk)$ is bounded. Moreover, the objective function f is square term plus a piecewise linear function which ensures that f is semi-algebric and hence satisfies Kurdyka-Lojasiewicz inequality. [2]-Theorem 5.1 is then applicable and obtain that $(xk)$ is convergent to a stationary point of (2.6). □

Consider the following minimization problem

where $A∈IRm×n,Q$ a nonempty closed convex set of $IRm,r>0$ and $ε∈(0,1)$⁠.

First, observe again that conditions on $ε$ guarantees that $f˜(x)≥0$ for all x. We will now describe an algorithm for solving (3.1), based on the majorized penalty approach see, for example, [18] and references therein. Following the same lines as in [18], we start by constructing a majorization of $f˜$⁠. To that end let $L>λmax(ATA)$⁠, then for any $x,y∈IRn$⁠, we have

Moreover, by invoking the convexity of the norm $∥x∥r$ and definition of its subdifferential, we also have

where

Hence, if we define

hence, for every $x,y∈IRn$⁠, we get

Starting with an initial iterate $x0$⁠, the majorized penalty approach above updates $xk$ by solving

This leads to the following explicit formulation of $xk+1$ by means of the proximity (shrinkage) operator of $∥x∥1$⁠:

where

We summarize the algorithm as follows:

Majorized Penalty Algorithm:

• 1. Initialization: Let $x0$ be given and set $L>λmax(ATA)$⁠.

• 2. For $k=0,1,⋯$ find

End.

The following proposition contains the convergence result of this Penalty Algorithm.

Proposition 3.1 Let $(xk)$ be the sequence generated by the Majorized Penalty Algorithm above. Then

Furthermore, the sequence $(xk)$ is bounded and any cluster point is a stationary point of problem (3.1).

Proof. Since $xk+1$ minimizes $F(x,xk)$⁠, thanks to the first-order optimality condition we can write

$g(xk)$ being a subgradient of $∥x∥r$ at $xk+1$⁠. This combined with the definition of the subdifferential of $∥x∥1$ at $xk+1$ gives

Hence

This together with the definition of F, for any $k≥1$⁠, leads to

Consequently,

Hence $f˜(xk+1)≤f˜(xk)$ and thus the sequence $(f˜(xk))$ is convergent since $f˜$ is a non-negative function. Furthermore, the sequence $(xk)$ is such that

Indeed, by summing (3.7) from $k=0$ to $∞$⁠, we obtain that

Consequently, the sequence $(xk)$ is asymptotically regular, i.e., $limk→+∞∥xk−xk+1∥=0$⁠. On the other hand, observe that the definition of $f˜$ for any $k≥1$⁠, leads to

Since $∥xk∥1≥∥xk∥r$⁠, we obtain that $μ(1−ε)∥xk∥r≤f˜(x0)$⁠. This implies that $(xk)$ is bounded since $0<ε<1$⁠. To conclude, we prove that every cluster point of $(xk)$ is a stationary point of (3.1). Let $x∗$ be a cluster point of $(xk)$⁠, then $x∗=limVxkv,(xkv)$ being subsequence of $(xk)$⁠. By passing to the limit in (3.6) along the subsequence $(xkv)$ and in the light of the upper semicontinuity of (Clarke) subdifferentials, we obtain the desired result, namely

which is nothing else than the first-order optimality condition of (3.1). □

Now we turn our attention to a DC Algorithm (DCA), where the dual step at each iteration can be efficiently carried out due to the accessible subgradients of the largest- q-norm $∥·∥σq$ and $∥·∥r$ norm. Remember that to find critical points of $f:=φ−ψ$⁠, the DCA consists in designing of sequences $(xk)$ and $(yk)$ by the following rules

Note that by the definition of subdifferential, we can write

Since $xk+1$ minimizes $φ(x)−(ψ(xk)+〈yk,x−xk〉)$⁠, we also have

Combining the last inequalities, we obtain

Therefore, the DCA leads to a monotonically decreasing sequence $(f(xk))$ that converges as long as the objective function f is bounded below.

Now, we can decompose the objective function in (2.6) as follows

where $μ>0$⁠, $ε∈(0,1)$⁠, here $φ(x)=12∥(I−PQ)Ax∥2+μ∥x∥1$ and $ψ(x)=με∥x∥σq$⁠.

At each iteration, DCA solves The convex subproblem defined by linearizing the concave term $−ε∥x∥σq$ is solved by DCA at each iteration until a convergence condition is satisfied. More precisely, we have

Especially, if either the function $φ$ or $ψ$ is polyhedral, the DCA is said to be polyhedral and terminates in finite iterations [15]. Note that the our proposed DCA is polyhedral since the largest-q norm term $−ε∥x∥σq$ can be expressed as a pointwise maximum of $2qCnq$ linear functions, see [10]. On the other hand, the subdifferential of $∥x∥σq$ at a point $xk$ is given in, see for example [19],

that is

where $yij$ denotes the element of y corresponding to $xij$ in the linear program (4.4). Observe that a subgradient $y∈∂∥xk∥σq$ can be computed efficiently by first sorting the elements $|xi|$ in decreasing order, namely $|xi1|≥|xi2|≥⋯≥|xiq|$⁠. Then, assign 1 to $yi$ which corresponds to $xi1⋯,xiq$⁠.

To conclude, let us consider the following DC formulation of (3.1):

where $r>0$⁠, $ε∈(0,1)$⁠, here $φ(x)=12∥(I−PQ)Ax∥2+μ∥x∥1$ and $ψ(x)=με∥x∥r$⁠.

The subgradient $y∈∂∥xk∥r$ is also available via the formula (3.2) and the DCA in this context take the following form

where

For the details of DCA convergence properties, see [15].

The focus of this paper is on Q-Lasso relying on two new DC-penalty methods instead of conventional methods such as $l1$ or $l1−l2$ minimization developed in [13,17] and [21]. Two iterative minimization methods based on the gradient proximal algorithm as well as the majored penalty algorithm are designed and their convergence to a stationary point is proved. Furthermore, by means of DC (difference of convex) Algorithm, two other algorithms are devised and their convergence results are also stated.

Publishers note: The publisher wishes to inform readers that the article “Difference of two norms-regularizations for Q-Lasso” was originally published by the previous publisher of Applied Computing and Informatics and the pagination of this article has been subsequently changed. There has been no change to the content of the article. This change was necessary for the journal to transition from the previous publisher to the new one. The publisher sincerely apologises for any inconvenience caused. To access and cite this article, please use Moudafi, A. (2020), “Difference of two norms-regularizations for Q-Lasso”, New England Journal of Entrepreneurship. Vol. 17 No. 1, pp. 79-89. The original publication date for this paper was 19/17/2018.