Hong-Kun XU

1 Introduction

The lasso,abbreviation of“the least absolute shrinkage and selection operator”,was introduced by Tibshirani[16]in 1996,and is formulated as the minimization problem

whereAis anm×n(real)matrix,x∈Rn,b∈Rm,t≥0 is a tuning parameter.An equivalent formulation of(1.1)is the following regularized minimization problem:

whereγ≥0 is a regularization parameter.

The lasso has been received much attention due to the involvement of theℓ1norm which promotes sparsity,phenomenon of many practical problems arising from image/signal processing,machine learning,and so on.As a matter offact,in imaging science,an image ofinterest is to be recovered from a set of linear measurements taken randomly.Mathematically this can be modeled by the linear system

whereAis anm×nmatrix,b∈Rmis an input,andx∈Rnrepresents the image ofinterest to be recovered.Since the dimension ofxis high(i.e.,nis big),and since the number of measurements is restricted due to some constraints(i.e.,mis small compared ton),the system(1.3)is underdetermined(indeed,m≪n),and therefore,admits infinitely many solutions(if any).

If a certain appropriate sparsity condition is imposed,then even a unique solution of the underdetermined linear system(1.3)can be achieved.This is the crucial role played by sparsity which has brought a revolution in the imaging science and which is pioneered by Donoho,Candes,Tao,Romberg,and others(see[1–4,7]),which has given birth to a new research fieldcompressed sensing.Sparsity is based on the observation that,upon a cleverly chosen basis,such as a Fourier or wavelet basis,it will often be the case that an image/signal ofinterest is concentrated on a small subset of the basis,hence it can be well approximated by vectors with a small number of nonzero coefficients.Conversely,an image/signal is ofinterest ifit can be described with a small number of the basis vectors.An uninteresting image/signal is actually viewed as noise as commented in[5].

Sparsity is described by the quasiℓ0-“norm”:

forx=(xj)t∈Rn.For a given integerk≥0,x∈Rnis said to bek-sparse if

The sparse recovery problem is stated as finding the sparsest vectorxwithAx=b.Put in another way,the problem is

The minimization(1.4)is numerically unstable and combinatorial NP-hard,and therefore,not an ideal way to recover the sparse signalx.

Theℓ1norm plays an intermediation role between theℓ0norm and theℓ2norm since it shares the sensitivity of theℓ0norm to sparsity and the convexity of the unit ball that theℓ2norm has.However,minimizing theℓ0norm is NP-complete and untractable,while minimizing theℓ2norm,though much easier and efficient,requires too many measurements to guarantee an accurate recovery.Therefore,minimizing theℓ1norm is ideal as it combines the parsimony ofℓ0and the computational efficiency ofℓ2(see[5]).

The theory of compressed sensing surprisingly guarantees that the NP-hard combinatorial minimization(1.4)can be exactly reconstructed under certain conditions by solving a convex polynomial-timeℓ1-minimization.

It is known(see[1,3])that if a sufficiently sparsex0exists such thatAx0=b,then the basis pursuit(BP for short)

will find it;indeed(1.5)can be recast as a linear program.

When measurements take errors(which is often the case),the exact system(1.3)turns out to be inexact:

In this case,one looks for a vector with minimumℓ1norm and within some error range,that is,the minimization problem

or the equivalentℓ1regularized minimization(1.2)will be taken into consideration.

Candes,Romberg and Tao[2]showed that if a sufficiently sparsex0exists such thatb=Ax0+e,for some small error termthen the solutionx∗to(1.7)will be close tox0,that is,whereCis a constant.

In this paper we will exploit certain basic properties of the lasso(1.1)and iterative methods for solving it.The main iterative method will be the proximal algorithm which will also be used to solve variants of the lasso such as the elastic net(see[20])and the smooth-lasso(see[10]).

2 Properties of the Lasso

Letγ>0 and let

be the objective function of the lasso(1.1).Observing thatφγis continuous,convex,and coercive(i.e.,φγ(x)→∞aswe have that the lasso(1.1)has a closed convex nonempty solution set which is denoted asSγ.

Proposition 2.1We have the following assertions:

(i)A andtake constant values on the solution set Sγ,that is,andConsequently,the functions

are well-defined for γ>0(not depending upon a particular choice xγ∈Sγ).This is mentioned in[15].

(ii)ρ(γ)is decreasing and continuous in γ>0.

(iii)η(γ)is increasing in γ>0.

(iv)Axγis continuous in γ>0.

ProofForxγ∈Sγ,we have the optimality condition

HereAtis the transpose ofAand∂stands for the subdifferential in the sense of convex analysis.Equivalently,

It turns out by the subdifferential inequality that

In particular,for

Interchangexγandto get

Adding up(2.2)and(2.3)yields

Consequently,and(2.2)–(2.3)imply thatandrespectively.Henceand the functions

are well-defined forγ>0.

It turns out from(2.1)that,forxβ∈Sβ,

Interchangeγandβ,andxγandxβto find

Adding up(2.4)and(2.5)obtains

We therefore find that ifγ>β,thenthat is,ρ(γ)is nonincreasing.(2.6)also shows thatAxγis continuous,so isη(γ)forγ>0.

To see that the functionis increasing,we use the inequality(asxγ∈Sγ)

which implies that

Now ifβ>γ>0,then aswe immediately find thatNamely,η(γ)≤η(β).

Finally we prove the continuity ofρ(γ)forγ>0.Rewrite(2.4)as

SinceAxγis continuous inγ>0,it follows from(2.7)that

Hence,ρ(γ+)≥ρ(γ)which in turns implies thatρ(γ+)=ρ(γ)forρis nonincreasing.Hence,ρis right-continuous inγ>0.

Taking the limit in(2.7)asγ→β−yieldsρ(β)≥ρ(β−)that again impliesρ(β)=ρ(β−)due to the nonincreasingness ofρ.Hence,ρis also left-continuous.Consequently,ρ(γ)is continuous inγ>0.

Proposition 2.2We have the following assertions:

Proof(i)Taking the limit asγ→0 in the inequality

immediately yields the result in(i).

As for(ii),we claim thatfor any∈S.As a matter offact,

It turns out thatIn particular,wherex†is anℓ1minimum-norm element ofS,that is,

Assumeγk→0 is such thatxγk→bx.Then for anyx,

It turns out thatsolves the least-squares problemthat is,∈S.Consequently,

This suffices to ensure that the conclusion of(ii)holds.

Proposition 2.3If

ProofThe optimality condition

implies that

Takingx=2xγin the subdifferential inequality(2.1)yields

It follows that

It turns out from(2.9)that ifxγ≠0,we must have

Notice that(2.8)shows thatcan be determined byAxγ.Hence we arrive at the following characterization of solutions of the lasso(1.2).

Proposition 2.4Let γ>0and xγ∈Sγ.Thenis a solution to the lasso(1.2)ifand only ifandIt turns out that

where N(A)={x∈Rn:Ax=0}is the null space of A,and Brdenotes the closed ball centered at the origin and with radius of r>0.This shows that if we can find one solution to the lasso(1.2),then all solutions are found by(2.10).

ProofIfthen from the relation

we obtainThis together with the assumption ofyields thatwhich in turns implies thatand hence

Remark 2.1As the solution setSγmay contain more than one point,it is unclear what kind of continuity of the set-valued functionγ→Sγone can get.

Definition 2.1The function from(0,∞)to[0,∞)×[0,∞)defined by

is referred to as the L-curve associating with the lasso(1.2).

Proposition 2.5The L-curve ℓ(γ)is continuous on(0,∞).

Remark 2.2For more details onL-curves and properties about theℓ1regularization,the reader is referred to[15].

3 Iterative Methods

In this section we discuss the proximal iterative methods for solving the lasso(1.1).The basics are Moreau’s concept of proximal operators.

3.1 Proximal operators

LetHbe a Hilbert space and let Γ0(H)be the space of convex functions inHthat are proper,lower semicontinuous and convex.

Definition 3.1(see[13–14])The proximal operator of φ∈Γ0(H)is defined by

The proximal operator of φ of order λ>0is defined as the proximal operator of λφ,that is,

We list some of the useful properties of the proximal operators.

Proposition 3.1(see[6,12])Let φ∈Γ0(H)and λ∈(0,∞).

(i)If C is a nonempty closed convex subset of H and φ=ICis the indicator function of C,then the proximal operatorsproxλφ=PCfor all λ>0,where PCis the metric projection from H onto C.

(ii)proxλφis firmly nonexpansive(hence nonexpansive).Recall that a mapping T:H→H is firmly nonexpansive if

and T is nonexpansive if

(iii)proxλφ=the resolvent of the subdifferential∂φ of φ.

(iv)y∈∂φ(x)⇔x=proxφ(x+y).

The proximal operator can have a closed-form expression in some cases as shown in the examples below(see[6]).

(a)If we takeφto be the norm ofH,then

In particular,ifH=R,then the above operator is reduced to the scalar soft-thresholding operator:

(b)Letbe an orthonormal basis ofHand let{ωn}be a sequence of real positive numbers.Defineφ∈Γ0(H)by

Then proxφwhere

Below is a restatement,in terms of proximal operators,of the resolvent identity of monotone operators.

Lemma 3.1The proximal identity

holds for φ∈Γ0(H),x∈H,λ>0andµ>0.

3.2 Proximal algorithm

The proximal operators can be used to minimize the sum of two convex functions

wheref,g∈Γ0(H).It is often the case where one of them is differentiable.The following is an equivalent fixed point formulation of(3.2).

Proposition 3.2Let f,g∈Γ0(H).Let x∗∈H and λ>0.Assume that fis finite-valued and differentiable on H.Then x∗is a solution to(3.2)if and only if x∗solves the fixed point equation

Proofx∗is a solution to(3.2)if and only if

The fixed point equation(3.3)immediately yields the following fixed point algorithm which is also known as the proximal algorithm for solving(3.2)as follows.

Initializex0∈Hand iterate

where{λn}is a sequence of positive real numbers.

Theorem 3.1Let f,g∈Γ0(H)and assume that(3.2)is consistent.Assume in addition that

(i)∇fis Lipschitz continuous on H:

(ii)

Then the sequence(xn)generated by the proximal algorithm(3.4)converges weakly to a solution of(3.2).No strong convergence in general is guaranteed ifdimH=∞.

To prove Theorem 3.1,we need the concept of averaged mappings.Letα∈(0,1).We say that a mappingT:H→His anα-averaged mapping(α-av for short)if

It is known that projections and proximal operators are all(equivalently,firmly nonexpansive).We will use the fact(see[18])that under the assumption(i)of Theorem 3.1,the operator

isfor each

It is known(see[9])that ifTis averaged with fixed points,then for eachx∈H,the iteratesTnxconverge weakly to a fixed point ofT.

It is also known(see[9])that ifTis nonexpansive,then the graph ofI−Tis demiclosed,namely,ifxn→xweakly and(I−T)xn→yin norm,then it follows that(I−T)x=y.This is named the demiclosedness principle of nonexpansive mappings in Hilbert spaces.

Proof of Theorem 3.1A sketch of the proofis given in[6].Here we provide a slightly different proof by using the technique of averaged mappings(see[18]).LetSbe the nonempty solution set of(3.2).For the sake of simplicity,we may assume,due to condition(ii),that

for alln,wherea,bare constants.

We follow the proof of[18,Theorem 4.1](see also[11]).AsVλgiven in(3.5)iswe can rewrite

whereTλis nonexpansive,that is,x,y∈H.Putting

we then get

It turns out that,forx∗∈S=Fix(Vγ)for allγ>0,

whereConsequently,we getfor alln.In particular,(xn)is bounded and moreover,

We also find from(3.9)that

This implies thatwhich,together with(3.8),in turns implies that

We next prove that

Hereωw(xn)is the set of all weak cluster points of(xn).Note that(3.10)and(3.12)together guarantee that(xn)converges weakly to a point inSand then the proofis complete.To see(3.12)we proceed as follows.Takeand assume that{xnj}is a subsequence of{xn}weakly converging toHence by(3.11),weakly as well.Without loss of generality,We may assumeThendue to(3.6).SettingT=proxλg(I−λ∇f),thenTis nonexpansive.Setting

we getUsing the proximal identity of Lemma 3.1,we deduce that

As(xn)is bounded,∇fis Lipschitz continuous(hence{∇f(xn)}is bounded),andwe immediately derive from the last relation thatAs a result,we find

Now the demiclosedness of the nonexpansive mappingI−Timplies that(I−T=0.Namely,∈Fix(T)=S.Therefore,(3.12)is proven.

3.3 The relaxed proximal algorithm

The relaxed proximal algorithm generates a sequence(xn)by the following iteration process.Initializex0∈Hand iterate

where{αn}is the sequence of relaxation parameters and{λn}is a sequence of positive real numbers.

Theorem 3.2Let f,g∈Γ0(H)and assume(3.2)is consistent.Assume in addition that

(i)∇fis Lipschitz continuous on H:

(ii)

(iii)

Then the sequence(xn)generated by the proximal algorithm(3.4)converges weakly to a solution of(3.2).No strong convergence in general is guaranteed ifdimH=∞.

ProofSet

Notice thatVncan be rewritten as

whereandTnis nonexpansive.We can further rewritexn+1as

Also observe from the assumption(iii)that

Repeating the proof of Theorem 3.1,we can see(details omitted)that the relations(3.10)and(3.12)remain valid and consequently,(xn)converges weakly to a solution of(3.2).

If we takethen the relaxation parametersαncan be chosen from a larger pool;they are allowed to be close to zero.More precisely,we have the following theorem(the proof of which is omitted here).

Theorem 3.3Let f,g∈Γ0(H)and assume that(3.2)is consistent.Define the sequence(xn)by the following relaxed proximal algorithm:

Suppose that

(a)∇f satisfies the Lipschitz continuity condition(i)in Theorem3.2;

(b)andfor all n;

(c)=∞.

Then(xn)converges weakly to a solution of(3.2).

3.4 Proximal algorithms applied to lasso

For the lasso(1.2),we takeandg(x)=Noticing that∇f(x)=At(Ax−b)which is Lipschitz continuous with constantwe find that the proximal algorithm(3.4)is reduced to the following algorithm for solving the lasso(1.2):

Here we have that forα>0 andx=(xj)t∈Rn,

with proxα|·|(β)=sgn(β)max

The convergence theorem of the general proximal algorithm(1.2)reads the following for the lasso(1.2).

Theorem 3.4AssumeThen the sequence(xk)generatedby the proximal algorithm(3.17)converges to a solution of the lasso(1.2).

Remark 3.1The relaxed proximal algorithms(3.13)and(3.16)also apply to the lasso(1.2).We however do not elaborate on the details.

3.5 A dual method

WriteandThen the lasso(1.2)can be rewritten as the minimization

The optimality condition of(3.18)is thatx∗∈Rnsolves(3.18)if and only of

This is equivalent,by the Young-Fenchel equality,to

whereg∗is the conjugate ofg,that is,

Settingy=x∗−λ∇f(x∗)withλ>0,we rewrite(3.19)as

Further settingwe get

Note that(3.22)can be rewritten as

This is equivalent to the fact

Since the homogeneity ofg(i.e.,g(σx)=σg(x)for allσ≥0 andx∈Rn)implies that the conjugate ofg,g∗,is the indicator of the setK:=∂g(0):

it turns out that(3.24)is reduced equivalently to

HerePKis the projection from RntoK.Now by the definition ofz,(3.26)implies that

It follows from(3.27)thatx∗is a solution of(3.18)if and only ifx∗satisfies the fixed point equation

Consequently,we immediately get the following fixed point algorithm for the lasso(1.2):

Similarly to the proximal algorithm(3.4),we have the following convergence result for the algorithm(3.29)with the proof omitted.

Theorem 3.5Let(λk)satisfy the condition

Then the sequence(xk)generated by the algorithm(3.29)converges to a solution of the lasso(1.2).

Remark 3.2Sincewe see that for each positive numberλ>0,PλKis the projection of the Euclidean space Rnto theℓ∞ball with radius ofλ,i.e.,{x∈Rn:It is not hard to find that the algorithm(3.29)and the proximal algorithm(3.4)coincide whenbecause it is not hard to find that proxλγK=I−PλγK.Indeed if we set

then we have

This corresponds to(3.21)in the case wherev:=x∗andu:=y.It therefore turns out by(3.27)that proxλγK(u)=v=u−PλγKu.

4 Two Variants of the Lasso

The lasso(1.2)promotes sparsity.It is however ill-posed and regularization is needed to accommodate other purposes except for sparsity.Various variants of the lasso have therefore been proposed.Here we focus on the elastic net(see[20])and S-lasso(see[10]).More variants,such as group lasso and sparse group lasso can be found in[8,17,19].

4.1 The elastic net

Zou and Hastie[20]used theℓ2norm(i.e.,the Tikhonov regularization)to regularize the lasso(1.2)and therefore introduced the concept of the elastic net(EN for short)which is the minimization problem

The advantage of EN lies in its unique solvability(due to the strict convexity if theℓ2norm).Letxγ,δdenote this unique solution of EN(4.1).Set

and

which are the limits ofφγ,δ(x)asδ→0 andγ→0,respectively.

Proposition 4.1Assume that the least-squares problem

is consistent and let S be its nonempty set of solutions.

(i)As δ→0(for each fixed γ>0),andis the(ℓ2)minimum-norm solutionto the lasso(1.2).Moreover,as γ→0,every cluster point ofis an(ℓ1)minimum-normsolution of the least-squares problem(4.4),i.e.,a point in the set

(ii)As γ→0(for each fixed δ>0),is the unique solution to the ℓ2regularized problem:

Moreover,aswhich is the ℓ2minimal norm solution of(4.4),that is,=

ProofSince the subdifferential

it turns out that the optimality condition 0∈∂φγ,δ(xγ,δ)is reduced to

Then the subdifferential inequality implies that

forx∈Rn.Replacingxwithxγ′,δ′forγ′>0 andδ′>0 yields

Interchangeγandγ′andδandδ′to get

Adding up(4.8)and(4.9)results in

Since the elastic net is the Tikhonov regularization of the lasso(1.2),we know that

Hereandcis a constant.It follows that{xγ,δ}is bounded.Hence,it follows from(4.10)that(γ,δ)7→xγ,δis a continuous curve forγ,δ>0.

Now by the properties of Tikhonov’s regularization,we have that for each fixedγ>0,xγ,δconverges asδ→0 to theℓ2minimal norm solution of the lasso(1.2),i.e.,the unique elementMoreover,by Proposition 2.2 ,we find that every cluster point(asγ→0)of the netbelongs to the set

Next fixδ>0 and letbe the unique solution to the minimization(4.3).This uniqueness and Proposition 2.2 imply thatNow the standard property of Tikhonov’s regularization ensures that

The elastic net(4.1)can be solved by the proximal algorithm(3.4).Takeandthen the proximal algorithm(3.4)is reduced to

The convergence of this algorithm is given as follows.

Theorem 4.1Assume

Then the sequence(xk)generated by the algorithm(4.11)converges to the solution of the EN(4.1).

We can also takethen proxµg(x)=withand the proximal algorithm(3.4)is reduced to

whereConvergence of this algorithm is given below.

Theorem 4.2Assume

Then the sequence(xk)generated by the algorithm(4.12)converges to the solution of the EN(4.1).

4.2 The S-lasso

The smooth-lasso(S-lasso for short)of Hebiri and van der Geer[10]is formulated as the minimization problem

This is also an adaption to the fused lasso of Tibshirani,et al[17],

A more general version of the S-lasso is the minimization

whereJis ak×nmatrix.The S-lasso of(4.13)corresponds to the choice ofJgiven by

We can apply the proximal algorithm(3.4)to the S-lasso(4.15)by taking

Since∇f(x)=At(Ax−b)+2δJtJ(x),we find that the proximal algorithm(3.4)is reduced to the algorithm

The convergence of this algorithm is given below.

Theorem 4.3Assume

Then the sequence(xk)generated by the algorithm(4.16)converges to the solution of the EN(4.15).

[1]Candes,E.J.,Romberg,J.and Tao,T.,Robust uncertainty principles:Exact signal reconstruction from highly incomplete frequency information,IEEE Trans.Inform.Theory,52(2),2006,489–509.

[2]Candes,E.J.,Romberg,J.and Tao,T.,Stable signal recovery from incomplete and inaccurate measurements,Comm.Pure Applied Math.,59(2),2006,1207–1223.

[3]Candes,E.J.and Tao,T.,Near-optimal signal recovery from random projections:Universal encoding strategies?IEEE Trans.Inform.Theory,52(12),2006,5406–5425.

[4]Candes,E.J.and Wakin,M.B.,An introduction to compressive sampling,IEEE Signal Processing Magazine,2008,21–30.

[5]Cipra,B.A.,ℓ1-magic,SIAM News,39(9),2006.

[6]Combettes,P.L.and Wajs,R.,Signal recovery by proximal forward-backward splitting,Multiscale Model.Simul.,4(4),2005,1168–1200.

[7]Donoho,D.,Compressed sensing,IEEE Trans.Inform.Theory,52(4),2006,1289–1306.

[8]Friedman,J.,Hastie,T.and Tibshirani,R.,A note on the group lasso and a sparse group lasso,arXiv:1001.0736V1.

[9]Geobel,K.and Kirk,W.A.,Topics in Metric Fixed Point Theory,Cambridge Studies in Advanced Mathematics,Vol.28,Cambridge University Press,1990.

[10]Hebiri,M.and van de Geer,S.,The smooth-lasso and otherℓ1+ℓ2-penalized methods,Electron.J.Statist.,5,2011,1184–1226.

[11]Marino,G.and Xu,H.K.,Convergence of generalized proximal point algorithms,Comm.Pure Appl.Anal.,3(3),2004,791–808.

[12]Micchelli1,C.A.,Shen,L.and Xu,Y.,Proximity algorithms for image models:Denoising,Inverse Problems,27,2011,045009,30pp.

[13]Moreau,J.J.,Proprietes des applications“prox”,C.R.Acad.Sci.Paris Ser.A Math.,256,1963,1069–1071.

[14]Moreau,J.J.,Proximite et dualite dans un espace hilbertien,Bull.Soc.Math.France,93,1965,272–299.

[15]Raasch,T.,On theL-curve criterion inℓ1regularization of linear discrete ill-posed problems,International Conference on Inverse Problems and Related Topics,Nanjing,2012.

[16]Tibshirani,R.,Regression shrinkage and selection via the lasso,J.Royal Statist.Soc.Ser.B,58,1996,267–288.

[17]Tibshirani,R.,Saunders,M.,Rosset,R.,et al.,Sparsity and smoothness via the fused lasso,J.Royal Statist.Soc.,Ser.B,67,2005,91–108.

[18]Xu,H.K.,Averaged mappings and the gradient-projection algorithm,J.Optim.Theory Appl.,150,2011,360–378.

[19]Yuan,M.and Lin,Y.,Model selection and estimation in regression with grouped variables,J.Royal Statist.Soc.,Ser.B,68,2006,49–67.

[20]Zou,H.and Hastie,T.,Regularization and variable selection via the elastic net,J.Royal Statist.Soc.,Ser.B,67,2005,301–320.