J Charles Gilbert

On the solution uniqueness characterization in the ℓ 1 norm and polyhedral gauge recovery

Keywords: basis pursuit -convex polyhedral function -gauge recoveryℓ 1 minimization -Minkowski function -optimality conditions -sharp minimum -solution existence and uniqueness AMS MSC 2010: 65K05, 90C05, 90C25, 90C46

This paper first proposes another proof of the necessary and sufficient conditions of solution uniqueness in 1-norm minimization given recently by H. Zhang, W. Yin, and L. Cheng. The analysis avoids the need of the surjectivity assumption made by these authors and should be mainly appealing by its short length (it can therefore be proposed to students exercising in convex optimization). In the second part of the paper, the previous existence and uniqueness characterization is extended to the recovery problem where the ℓ 1 norm is substituted by a polyhedral gauge. In addition to present interest for a number of practical problems, this extension clarifies the geometrical aspect of the previous uniqueness characterization. Numerical techniques are proposed to compute a solution to the polyhedral gauge recovery problem in polynomial time and to check its possible uniqueness by a simple linear algebra test.

Introduction

In [40; 2015], H. Zhang, W. Yin, and L. Cheng have highlighted necessary and sufficient conditions (NSCs) ensuring uniqueness of a given solution to the ℓ 1 norm minimization problem (P 1 ) inf x 1 Ax = b.

In this problem, the unknown is the real vector x ∈ R n , while the map x ↦ x 1 ∶= ∑ n i=1 x i is the ℓ 1 norm, A is an m × n real matrix, and b ∈ R m . This problem, sometimes called basis pursuit, was proposed by S.S. Chen, D.L. Donoho, and M.A. Saunders [13; 1998] as a promising convex surrogate of the more difficult problem

(P 0 ) inf x 0 Ax = b,
in which one minimizes the number x 0 ∶= {i ∈ [1 ∶ n] ∶ x i ≠ 0} of nonzero components of the vector x (despite its notation, which is standard, ⋅ 0 is not a norm, for lack of positive homogeneity), subject to the same affine constraint as in (P 1 ). We have used the notation [1 ∶ n] ∶= {1, . . . , n} for the set formed of the n first nonzero integers. Problem (P 0 ) is actually the one that is most often interesting in applications, but it is much harder to solve than (P 1 ): the former is indeed NP-hard [32; 2005], while the latter can be solved in polynomial time because it can be recast as a linear optimization problem [START_REF] Chen | Atomic decomposition by basis pursuit[END_REF].

There are many testimonies of the efficiency of modeling based to or inspired from (P 1 ) to give an appropriate answer to many problems in fields as diverse as information theory, compressed sensing in signal processing [START_REF] Chen | Atomic decomposition by basis pursuit[END_REF][START_REF] Candès | Decoding by linear programming[END_REF][START_REF] Donoho | Compressed sensing[END_REF][START_REF] Blanchard | Compressed sensing: how sharp is the restricted isometry property?[END_REF][START_REF]Compressed Sensing -Theory and Applications[END_REF], and machine learning [START_REF] Harchaoui | Conditional gradient algorithms for normregularized smooth convex optimization[END_REF], to mention a few. These problems have therefore attracted much attention from the optimization community [START_REF] Juditsky | Verifiable conditions of ℓ 1 -recovery for sparse signals with sign restrictions[END_REF][START_REF] Juditsky | Accuracy guarantees for ℓ 1 -recovery[END_REF][START_REF] Juditsky | On verifiable sufficient conditions for sparse signal recovery via ℓ 1 minimization[END_REF][START_REF] Aspremont | Testing the nullspace property using semidefinite programming[END_REF][START_REF] Nesterov | On first-order algorithms for l1/nuclear norm minimization[END_REF].

Finding conditions ensuring uniqueness of a solution x to (P 1 ) is one particular aspect of the important problem dealing with the determination of conditions on A that ensure that a large and sparse vector x can be recovered from the vector b ∶= Ax by solving problem (P 1 ) [START_REF] Donoho | Uncertainty principles and ideal atomic decomposition[END_REF][START_REF] Zhang | A simple proof for recoverability of ℓ 1 -minimization: go over or under?[END_REF][START_REF] Candès | Decoding by linear programming[END_REF][START_REF] Candès | Near-optimal signal recovery from random projections: universal encoding strategies[END_REF][START_REF] Cohen | Compressed sensing and best k-term approximation[END_REF][START_REF] Chandrasekaran | The convex geometry of linear inverse problems[END_REF][START_REF] Candès | Simple bounds for recovering low-complexity models[END_REF]. Therefore, several researchers have contributed to the clarification of these NSCs of solution existence and uniqueness. Those considered in [40; 2015] and below read for a point x satisfying Ax = b:

∃ ȳ ∈ R m such that A T I ȳ = s and A T I c ȳ ∞ < 1, (1.1a)
A I is injective, (1.1b) where

I ∶= {i ∈ [1 ∶ n] ∶ xi ≠ 0}, I c ∶= [1 ∶ n] ∖ I, A I
is the submatrix of A formed of its columns with index in I, A T I is the transpose of A I , s ∶= sign(x I ), and v ∞ = max i v i is the ℓ ∞ norm. These conditions have a dual nature since the vector ȳ appearing in (1.1a) is a solution to the Lagrange dual of (P 1 ). Several contributions are related to these conditions. Fuchs [22; 2004] gave a sufficient condition, similar to (1.1), but with the vector ȳ fixed to y † ∶= A I (A T I A I ) -1 s, which is the minimum norm solution to A T I y = s (see [8; 2013, lemma 1] for a related result). Dossal [19; 2012] found restrictive conditions on the data of (P 1 ) such that (1.1) with ȳ = y † becomes necessary for the solution existence and uniqueness (actually, example 3.5 will show that, without these restrictive conditions, (1.1a) may not be satisfied when ȳ is fixed to y † ). Grasmair, Haltmeier, and Scherzer [25; 2011, theorem 4.7] consider the problem in infinite dimension and show that conditions similar to (1.1) are necessary and sufficient to get uniqueness of a solution x satisfying an additional condition involving the Tikhonov regularization. Finally Zhang, Yin, and Cheng [40; 2015, theorem 2.2] showed that the conditions (1.1) (hence without fixing ȳ to y † ) are necessary and sufficient for the solution existence and uniqueness (see also [9; 2006, lemme 2.1] for a similar result with a particular set of data). In [START_REF] Zhang | Necessary and sufficient conditions of solution uniqueness in 1-norm minimization[END_REF] however, the surjectivity of A is assumed. This surjectivity assumption can always be satisfied by some linear algebra transformations, but the proof of proposition 3.2 below shows that this hypothesis can be discarded, which makes the result cleaner and easier to apply. Another advantage of the proposed proof, and this was the motivation for writing what was initially a brief note, is that it is very short (half a page, instead of two pages and a half in [START_REF] Zhang | Necessary and sufficient conditions of solution uniqueness in 1-norm minimization[END_REF]), which makes it a possible exercise for students learning convex optimization.

Another outcome of the proposed analysis is to highlight the fact that (1.1a) is not directly linked to the uniqueness of the solution, but is rather a characterization of the fact that x is in the relative interior of the solution set or equivalently, for polyhedral functions (lemma 2.1), that zero is in the relative interior of the subdifferential at x of the map

f ∶ x ∈ R n ↦ x 1 + I X (x), (1.2)
where I X denotes the indicator function of the feasible set X ∶= {x ∈ R n ∶ Ax = b} (that is I X (x) = 0 if x ∈ X , and I X (x) = +∞ if x ∉ X ). A unique solution is, of course, in the relative interior of the solution set, so that this fact may be viewed as another reason why (1.1a) appears in the NSCs for existence and uniqueness. On the other hand, condition (1.1b) expresses the fact that the affine hull of ∂ f (x) is the full space R n , which, combined with (1.1a), is equivalent to the fact that zero is in the interior of ∂ f (x). Furthermore, since (1.1a) is automatically satisfied by a point in the relative interior of the solution set (some solvers can ensure that property), checking uniqueness amounts to verify the injectivity of A I , which is a quite easy numerical task (in exact arithmetic); this subject is discussed in section 4.4.2 in the broader framework presented in the next paragraph.

In the second part of the paper (section 4), the approach followed for the ℓ 1 norm recovery is applied to a similar problem obtained from (P 1 ) by substituting the ℓ 1 norm by a polyhedral gauge f (section 4.1) defined on an arbitrary Euclidean space or, equivalently, a Minkowski function associated with a convex polyhedron containing the origin. The problem then reads

(P f ) inf f (x) Ax = b.
The gauge f may take infinite values, which may be used to represent implicit polyhedral constraints (see section 4.5). A number of interesting applications enter that framework [START_REF] Chandrasekaran | The convex geometry of linear inverse problems[END_REF]; for example, x may be a real matrix and f the nuclear norm. It is shown in sections 4.2 and 4.3 that the approach proposed for analyzing (P 1 ) is general and powerful enough to yield similar NSCs of existence and uniqueness for problem (P f ). In section 4.4, problem (P f ) with a polyhedral gauge f is shown to be equivalent to a linear optimization problem (P ′ f ), making it solvable in polynomial time. Finally, a way of detecting the uniqueness of a solution to (P f ) is proposed; it involves the use of an interior-point algorithm to solve (P ′ f ) and the checking of a linear algebra condition.

2 Convex analysis tools

Notation

We denote by

R + ∶= {t ∈ R ∶ t ⩾ 0}, R ++ ∶= {t ∈ R ∶ t > 0}, and R ∶= R ∪ {-∞, +∞}.
The relative complement of a set I 0 in a set I is denoted by I c 0 ∶= I ∖ I 0 (the reference to I is not mentioned in the notation I c 0 but should be clear from the context). The notation and concepts of convex analysis that we employ are standard [START_REF] Rockafellar | Convex Analysis[END_REF][START_REF] Hiriart-Urruty | Convex Analysis and Minimization Algorithms[END_REF][START_REF] Borwein | Convex Analysis and Nonlinear Optimization -Theory and Examples[END_REF]. Let E be a finite dimensional vector space. We denote by aff S the affine hull of a set S ⊂ E [36; p. 6], by int S its interior, and by ri S its relative interior [36; § 6]; the relative boundary of S is formed of the points that are in its closure but not in its relative interior. We shall use repetitively the nice and powerful identity [36; cor. 6.6.2]

ri(C 1 + C 2 ) = ri C 1 + ri C 2 , (2.1)
which is valid for two convex sets Suppose now that E is a Euclidean vector space, meaning that it is a finite dimensional vector space endowed with a scalar product, which is denoted by ⟨⋅, ⋅⟩. If E 0 is a subspace of E, E ⊥ 0 denotes its orthogonal complement in E. If P is a subset of E, P + ∶= {d ∈ E ∶ ⟨d, x⟩ ⩾ 0, for all x ∈ P } is its positive dual cone; its negative dual cone is P -∶= -P + . For a closed convex set C, we denote its normal cone at x ∈ C by N C (x) ∶= {d ∈ E ∶ ⟨x ′x, d⟩ ⩽ 0, for all x ′ ∈ C} and its tangent cone at x ∈ C by T C (x) ∶= N C (x) -. The subdifferential of f ∈ Conv(E) at x ∈ dom f is the set denoted by ∂f (x) and defined by one of the following equivalent identities [36; p. 214, th. 23.2]

C 1 and C 2 in E. The domain of a function f ∶ E → R is defined and denoted by dom f ∶= {x ∈ E ∶ f (x) < +∞} and its epigraph by epi f ∶= {(x, α) ∈ E × R ∶ f (x) ⩽ α}. As in [27], Conv(E) is the set of functions f ∶ E → R ∪ {+∞} that are convex (i.e.,
∂f (x) ∶= {x * ∈ E ∶ f (x ′ ) ⩾ f (x) + ⟨x * , x ′ -x⟩, for all x ′ ∈ E}, (2.2a) ∶= {x * ∈ E ∶ f ′ (x; d) ⩾ ⟨x * , d⟩, for all d ∈ E}. (2.2b) If x ∉ dom f , ∂f (x) = ∅ by convention (the inequality in (2.2a) is not verified at a point x ′ in the nonempty domain of f , actually).
The set of minimizers of a function f ∶ E → R is denoted by "arg min f " and the set of its maximizers is denoted by "arg max f ". We denote the optimal value of a problem (P ) by val(P ) and its solution set by Sol(P ).

Polyhedral convex function

The functions considered in this paper are convex polyhedral, meaning that their epigraph are convex polyhedrons [36; p. 172]. In this section, we quote two convex analysis results related to convex polyhedral functions that play a major part in the sequel.

The first result is helpful for clarifying the meaning of condition (1.1a), to give it a "geometrical" interpretation. As we shall see in the examples after the lemma, the equivalence (2.3) essentially holds for polyhedral functions, so that this assumption of polyhedrality intervenes in a crucial manner in the proof. Lemma 2.1 (relative interior of a polyhedral function minimizer) Let E be a Euclidean vector space and f ∈ Conv(E) be polyhedral. Then

x ∈ ri arg min f ⇐⇒ 0 ∈ ri ∂f (x) . (2.3)
Proof. Let us simplify the notation by setting M ∶= arg min f .

[⇒] Let x ∈ ri M, so that 0 ∈ ∂f (x) [(2.2a)].
If the subdifferential contains no other point than zero, then 0 ∈ ri(∂f (x)) and the implication is proved. Otherwise, there is some nonzero x * ∈ ∂f (x) and it is enough to show that -ε x * ∈ ∂f (x) for some ε > 0 to get the result [36; th. 6.4].

For any direction d in the open half space

H ∶= {d ∈ E ∶ ⟨x * , d⟩ > 0}, the directional derivative f ′ (x; d) ⩾ ⟨x * , d⟩ > 0 [(2.2b)]
, so that f increases from its minimizer x in any direction d of H. Now, there must also hold f ′ (x; -d) > 0 for d ∈ H (since otherwise f ′ (x; -d) = 0 by the minimality of x, implying that xtd ∈ M for t > 0 sufficiently small by the polyhedrality of f , leading to x+td ∈ M for some small t > 0 by the fact that x is on the relative interior of M [36; th. 6.4], which contradicts

f ′ (x; d) > 0). These observations, namely f ′ (x; d) > 0 for all d ∈ H ∪ (-H), yield N ∂f (x) (0) ⊂ (Rx * ) ⊥ .
(

Indeed, if d is in the normal cone to ∂f (x) at zero, there holds ⟨x * 1 , d⟩ ⩽ 0 for all

x * 1 ∈ ∂f (x), implying in sequence that f ′ (x; d) = sup{⟨x * 1 , d⟩ ∶ x * 1 ∈ ∂f (x)} ⩽ 0 [
Rx * ⊂ T ∂f (x) (0).
Remembering that the tangent cone to the polyhedral set ∂f (x) [36; th. 23.10] is identical to the cone of feasible directions, one finds that -ε x * ∈ ∂f (x) for ε > 0 sufficiently small.

[⇐] We prove the contrapositive, assuming that x ∉ ri M. If x ∉ M, then 0 ∉ ∂f (x) [(2.2a)], proving the result. The other possibility is that x is on the relative boundary of M. Then there is x′ ∈ M such that for all t > 1, (1-t)x ′ +tx ∉ M [36; th. 6.4] (hence x′ ≠ x). By the optimality of x and the polyhedrality of f , there must hold f ′ (x; (1t)x ′ + txx) > 0 or f ′ (x; x -x′ ) > 0, which implies that there is some x * ∈ ∂f (x) such that [36; th. 23.10] ⟨x * , x -x′ ⟩ > 0.

(2.5)

The consequence of this inequality is certainly that 0 ∉ ri ∂f (x) (hence concluding the proof). Indeed otherwise, there would be a t > Note that any of the implications in (2.3) may not hold for a closed proper convex function that is not polyhedral. The implication "⇒" does not hold for example for f ∶ R → R defined at x ∈ R by f (x) = max(x 2 , x), since its unique minimizer is x = 0, so that x ∈ ri(arg min f ), but zero is not in the relative interior of ∂f (x) = [0, 1]. The implication "⇐" does not hold for example for f ∶ R → R defined at x ∈ R by f (x) = max(0, x) 2 , since zero is in the relative interior of ∂f (x) = {0} whatever is the minimizer x, but the minimizer x = 0 is not on the relative interior of arg min f = ] -∞, 0].

The previous result showed that the abstract condition 0 ∈ ri ∂f (x) is equivalent to the fact that x is in the relative interior of the solution set (for a polyhedral convex function). The next result shows that the stronger condition 0 ∈ int ∂f (x) is equivalent to the uniqueness of the solution x (for a polyhedral convex function also). This result is somehow standard and derives from the notion of sharp minimum (see [START_REF] Polyak | the IIASA Workshop on Generalized Lagrangians and Their Applications[END_REF] and [35; § 5.2.3]). We give it a short proof in order to be comprehensive and because it intervenes several times in the sequel: the necessity part uses polyhedrality in a place located well behind the front of the scene (it can also be deduced, for example, from [7; cor. 3.6 and 2.3]), the sufficiency part is straightforward and does not require polyhedrality.

The conjugate of an arbitrary function

f ∶ E → R ∪ {+∞} is the function f * ∈ Conv(E) defined at x * ∈ E by f * (x * ) = sup{⟨x * , x⟩ -f (x) ∶ x ∈ E} [36; p. 104].
The subdifferential of f ∈ Conv(E) at x ∈ dom f can also be rewritten in terms of its conjugate [36; th. 23.5]: [START_REF] Borwein | Convex Analysis and Nonlinear Optimization -Theory and Examples[END_REF]].

∂f (x) = {x * ∈ E ∶ f (x) + f * (x * ) = ⟨x * ,
: f * (x * ) = f * (0) + ⟨x, x * ⟩ for x * in some neighborhood V of zero. Using f * (0) = -f (x) [definition of f * ], there holds for x * ∈ V : f * (x * ) + f (x) = ⟨x, x * ⟩, meaning that V ⊂ ∂f (x) [(2.
[⇐] The converse implication holds for any function f ∈ Conv(E). Suppose that 0 ∈ int ∂f (x). Then for any x ∈ E, different from x, ε(xx) ∈ ∂f (x) for a sufficiently small ε > 0, so that f

(x) ⩾ f (x) + ⟨ε(x -x), x -x⟩ = f (x) + ε x -x 2 > f (x). ◻ 3 ℓ 1 norm

recovery

The goal of this section is to provide a short proof of the NSCs for the existence and uniqueness of solution to the ℓ 1 recovery problem (P 1 ). We do not try to be exhaustive, in the sense that additional properties of (P 1 ) can be obtained as corollaries of results in section 4 on the more general gauge recovery problem and will not be given (all the results of this section could have been obtained that way, actually). In particular, a technique for detecting uniqueness numerically can be deduced from the one proposed in section 4.4.2, so that this topics will not be discussed in the present section. The priority is therefore to give access to the NSCs rapidly, without a long detour by a more general problem. Even though the standard optimality conditions of problem (P 1 ) are not useful for getting the NSCs for uniqueness, we first recall them in section 3.1 to emphasize their structural similarity with the NSCs of existence and uniqueness of section 3.2, the latter being obtained by a natural strengthening of the former (in its statement and its proof technique).

In this section, we denote the feasible set of problem (P 1 ) by

X ∶= {x ∈ R n ∶ Ax = b}.

Existence

It is clear that problem (P 1 ) has a solution if and only if b is in the range space R(A) of the matrix A. This is because the assumption "b ∈ R(A)" makes the feasible set nonempty, while the existence of a solution is ensured by the coercivity of the norm. This NSC of solution existence has an absolute character: it is only expressed in terms of the problem data, that are A and b. Now, problem (P 1 ) is convex, hence its optimality condition also provides a NSC for a given point x ∈ R n to be a solution [START_REF] Bertsekas | Nonlinear Programming (second edition)[END_REF][START_REF] Bonnans | Numerical Optimization -Theoretical and Practical Aspects[END_REF]; the absolute character of the previous NSCs of solution existence is lost however, but the new condition gives interesting "dual information". This optimality condition has been given by many (see the introduction).

A few words on the notation. For a vector x ∈ R n , sign(x) ∈ R n is the sign vector of x: sign(x) i = 1 if x i > 0 and sign(x) i = -1 if x i < 0 (it is undetermined if x i = 0, but this case will not occur). The null space of A is denoted by N (A).

∃ ȳ ∈ R m such that A T I ȳ = s and A T I c ȳ ∞ ⩽ 1. (3.1) Proof. Since problem (P 1 ) is convex, x ∈ R n is
0 ∈ ∂( ⋅ 1 )(x) + ∂I X (x). (3.2) Now [27; § VI.3.1] ∂( ⋅ 1 )(x) = {z ∈ R n ∶ z ∞ ⩽ 1, z T x = x 1 } = {z ∈ R n ∶ z I = s, z I c ∞ ⩽ 1}. (3.3) It is known that ∂I X (x) is the normal cone N X (x) to X at x [36; p. 215] and it is easy to see that, in the present case, N X (x) = N (A) ⊥ = R(A T ), so that (3.2) claims the existence of some ȳ ∈ R m such that A T ȳ ∈ ∂( ⋅ 1 )(x). With the expression (3.3) of ∂( ⋅ 1 )(x), we get (3.

1). ◻

It is not difficult to show that, when x ∈ Sol(P 1 ), the vector ȳ satisfying (3.1) is actually a solution to the Lagrange dual of (P 1 ), which reads

(D 1 ) sup b T y A T y ∞ ⩽ 1.

Existence and uniqueness

The NSCs of solution existence and uniqueness (3.4) below is very close to (3.1) and the proof that we give to it has a structure resembling the one of proposition 3.1. The difference with the conditions given in [START_REF] Zhang | Necessary and sufficient conditions of solution uniqueness in 1-norm minimization[END_REF] is that proposition 3.2 does not assume the surjectivity of A. Admittedly, this is not a major improvement, but it makes its application easier.

On the other hand, the proposed proof gives another point of view on the result. The key ingredient that makes the proof simpler than in [START_REF] Zhang | Necessary and sufficient conditions of solution uniqueness in 1-norm minimization[END_REF] is the use of the fact that the function (1.2) is convex polyhedral together with the easy lemma 2.2.

Proposition 3.2 (solution existence and uniqueness

) Let x ∈ R n be a point sat- isfying Ax = b, I ∶= {i ∈ [1 ∶ n] ∶ xi ≠ 0}
, and s ∶= sign(x I ). Then Sol(P 1 ) = {x} if and only if

∃ ȳ ∈ R m such that A T I ȳ = s and A T I c ȳ ∞ < 1, (3.4a)
A I is injective.

Proof. By lemma 2.2, x is the unique minimizer of the convex polyhedral function f defined by (1.2) if and only if

0 ∈ int ∂ f (x) = int S(x) + R(A T ) ,
where we have used the same arguments as in the proof of proposition 3.1 and set S(x) ∶=

∂( ⋅ 1 )(x) = {z ∈ R n ∶ z I = s, z I c ∞ ⩽ 1}. Using (2.
1), this claim can also be written as the following two properties:

0 ∈ ri S(x) + R(A T ), (3.5a) aff S(x) + R(A T ) = R n . (3.5b) Condition (3.5a) is equivalent to the existence of a ȳ ∈ R m such that A T ȳ ∈ ri S(x) = {z ∈ R n ∶ z I = s and z I c ∞ < 1}, which is (3.4a). Let x0 ∶= (s, 0 I c ) and S 0 ∶= S(x) -x0 . Then (3.5b) can also be written R n = aff x0 + S 0 + R(A T ) ≡ x0 + aff S 0 + R(A T ), which is equivalent to R n = aff S 0 + R(A T ). Now aff S 0 = {0 I } × R I c , so that, after taking the orthogonal, (3.5b) is equivalent to {0} = (R I × {0 I c }) ∩ N (A) or {0} = N (A I ) or A I is injective, which is (3.4b).
◻

The proof has shown that condition (3.4a) is equivalent to (3.5a), which expresses the fact that 0 ∈ ri ∂ f (x), where f is defined by (1.2), or x ∈ ri(arg min f ) by lemma 2.1. Hence

x ∈ ri(Sol(P 1 )) ⇐⇒ 0 ∈ ri ∂ f (x) ⇐⇒ (3.4a) holds.
(3.6a)

In addition, condition (3.4b) is equivalent to (3.5b), which expresses the fact that the affine hull of

∂ f (x) is R n : aff ∂ f (x) = R n ⇐⇒ (3.4b) holds. (3.6b)
In the presence of this property, condition (3.4a) is now equivalent to 0 ∈ int ∂ f (x), which for its part is equivalent to the uniqueness of the solution for a polyhedral function by lemma 2.2. One could also relate condition (3.4b) to the fact that, when b = Ax with x 0 = p,

problem (P 0 ) recovers x if A J is injective for any J ⊂ [1 ∶ n] of size 2p [33; p. 510].
Let us now illustrate the above "geometrical interpretation" of the result of proposition 3.2 on two simple examples.

Example 3.3 (nonuniqueness) Suppose that n = 2, m = 1, A = 1 1 , and b = 1. Then Sol(P 1 ) = {x ∈ R 2 ∶ x1 + x2 = 1, 0 ⩽ x1 ⩽ 1} is not a singleton.
If one considers the solution x = (1, 0) ∉ ri Sol(P 1 ), there hold

I = {1}, ∂( ⋅ 1 )(x) = {1} × [-1, 1], and ∂I X (x) = R(A T ) = R{(1, 1)}, so that ∂ f (x) is the strip R{(1, 1)} + ({0} × [-2, 0]
), which has zero on its boundary. As expected from (3.6a) and (3.6b), the following equivalent properties hold:

x ∉ ri Sol(P 1 ) ⇐⇒ 0 ∉ ri ∂ f (x) ⇐⇒ (3.4a) fails, aff ∂ f (x) = R 2 ⇐⇒ (3.4b) holds.
The fact that x is not a unique solution is expressed by the failure of (3.4a) (ȳ must be set to 1 to satisfy the first condition, but then the second condition does not hold).

If one considers the solution x = (1 2, 1 2) ∈ ri Sol(P 1 ), there hold

I = {1, 2}, ∂( ⋅ 1 )(x) = {(1, 1)}, and ∂I X (x) = R(A T ) = R{(1, 1)}, so that ∂ f (x) = R{(1, 1)
}, which has zero in its relative interior. As expected from (3.6a) and (3.6b), the following equivalent properties hold:

x ∈ ri Sol(P 1 ) ⇐⇒ 0 ∈ ri ∂ f (x) ⇐⇒ (3.4a) holds, aff ∂ f (x) ≠ R 2 ⇐⇒ (3.4b) fails.
This time, the fact that x is not a unique solution is revealed by the failure of (3.4b) ((3.4a) holds with ȳ = 1,

I c = ∅). ◻ Example 3.4 (uniqueness) Suppose that n = 2, m = 1, A = 1 0 , and b = 1.
Then Sol(P 1 ) is the singleton {x}, where x = (1, 0). There hold

I = {1}, ∂( ⋅ 1 )(x) = {1} × [-1, 1], and ∂I X (x) = R(A T ) = R × {0}, so that ∂ f (x) is the strip R × [-1, 1],
which has zero in its relative interior. As expected from (3.6a) and (3.6b), the following equivalent properties hold:

x ∈ ri Sol(P 1 ) ⇐⇒ 0 ∈ ri ∂ f (x) ⇐⇒ (3.4a) holds [with ȳ = 1], aff ∂ f (x) = R 2 ⇐⇒ (3.4b) holds.
One deduces from the satisfaction of (3.4) that x is the unique solution to (P 1 ), which we already knew. ◻ Example 3.5 (failure of the minimum norm dual vector) In [START_REF] Fuchs | On sparse representations in arbitrary redundant bases[END_REF][START_REF]A necessary and sufficient condition for exact sparse recovery by ℓ 1 minimization[END_REF], the conditions in (3.4) are written with ȳ = y † , where y † ∶= A I (A T I A I ) -1 s is the minimum norm solution to A T I y = s (recall that A I is injective). The following example shows that conditions (3.4) may not be satisfied with ȳ = y † .

Consider indeed problem (P 1 ) with n = m = 2 and the following data

A = 1 α 1 0 and b = 1 1 ,
where α ∉ ] -2, 2[ is a parameter. Then, the feasible set of (P 1 ) is reduced to the single point

x = 1 0 ,
which is therefore the unique solution to the problem. We see that conditions (3.4) are satisfied for

ȳ = 0 1 , since A T ȳ = 1 0 ,
but not when ȳ is the minimum norm multiplier

y † = 1 2 1 2 , since A T y † = 1 α 2 .
We see that y † is not even feasible for the Lagrange dual (D 1 ) of (P 1 ) when α ∉ [-2, 2].

In conclusion, conditions (3.4) with ȳ = y † are sufficient conditions for uniqueness, but are not necessary. ◻

Polyhedral gauge recovery

Propositions 3.1 and 3.2 have a natural extension to the problem where the ℓ 1 norm is substituted by a polyhedral gauge f defined on a (finite dimensional) Euclidean space E (its scalar product is denoted by ⟨⋅, ⋅⟩). This section deals with such a problem, which can therefore be written

(P f ) inf f (x) Ax = b,
where f ∶ E → R ∪ {+∞} is a polyhedral gauge (see sections 4.1 and 4.2 for a precise definition), A ∶ E → F is a linear map from E to another Euclidean space F (whose scalar product is also denoted by ⟨⋅, ⋅⟩), and b ∈ F. In this section, we denote the feasible set of (P f ) by

X ∶= {x ∈ E ∶ Ax = b}
and the adjoint of the linear map

A ∶ E → F is denoted by A * ∶ F → E.
The ℓ 1 norm is a polyhedral gauge, so that the properties given in this section extend those of section 3. As shown by the examples in [START_REF] Chandrasekaran | The convex geometry of linear inverse problems[END_REF][START_REF] Friedlander | Gauge optimization and duality[END_REF], the above gauge minimization model encompasses various frequently encountered problems, including the nuclear norm penalization for rank minimization, conic optimization, problems in machine learning, etc. This model can also be used to represent polyhedral constraints (see section 4.5). In addition to be useful, this extension highlights by its abstraction the geometrical aspect behind the NSCs (3.1) and (3.4).

We start by recalling the definition of a gauge in section 4.1 and quote some of its properties, those that will be used below, including a description of its polar function and of its subdifferential. Section 4.2 establishes conditions ensuring the existence and uniqueness of the solution to the polyhedral gauge recovery problem (P f ). They are of the same nature as those given for the ℓ 1 norm recovery problem in sections 3.1 and 3.2. In section 4.3, we make the results more specific when the unit sublevel set of the polyhedral gauge, which is a convex polyhedron, is specified by its so-called inner description (the sum of the convex hull of a finite number of points c i and the conic hull of a finite number of directions d j ). Implementation issues are discussed in section 4.4, which includes the rewriting of the polyhedral problem (P f ) as a linear optimization problem (P ′ f ) and the proposal of a numerical technique for checking the uniqueness of a solution to (P f ).

Gauge

A gauge is a function f ∶ E → R ∪ {+∞} that is convex, nonnegative (i.e., f (x) ⩾ 0 for all x ∈ E), positively homogeneous of degree one (i.e., f (αx) = αf (x) for all α > 0 and x ∈ E), and that vanishes at the origin [36; p. 128]. The unit sublevel set of a gauge f , namely

B ∶= {x ∈ E ∶ f (x) ⩽ 1} (4.1)
is therefore a convex set that contains the origin (it is the "unit ball" of the gauge f ).

Reciprocally, f can be viewed as the Minkowski function associated with B, meaning that, when B is defined by (4.1), there holds

∀ x ∈ E ∶ f (x) = inf t {t > 0 ∶ x ∈ t B}. (4.2)
The polar of a set S ⊂ E is the closed convex set defined and denoted by [36; p. 125]

S ▵ ∶= {x * ∈ E ∶ ⟨x * , x⟩ ⩽ 1 for all x ∈ S}. (4.3)
The polar of a gauge f is the closed gauge

f ▵ ∶ E → R ∪ {+∞} defined at x * ∈ E by [36; p. 128] f ▵ (x * ) ∶= inf s {s > 0 ∶ ⟨x * , x⟩ ⩽ s f (x), ∀ x ∈ E}. (4.4)
and its bipolar f ▵▵ ∶ E → R ∪ {+∞} is the polar gauge of f ▵ . One deduces from the definition (4.4) that f and f ▵ satisfy the following generalized Cauchy-Schwarz inequality:

∀ (x * , x) ∈ E 2 ∶ ⟨x * , x⟩ ⩽ f ▵ (x * ) f (x). (4.5)
If f is a norm, then B is its unit ball, f ▵ is its dual norm, and B ▵ is often called its unit dual ball. With this example in mind the following properties will look rather natural. Proposition 4.1 (gauge properties) For a gauge f ∶ E → R ∪ {+∞}, for B given by (4.1), and for x, x * ∈ E, the following properties hold:

f ▵ (x * ) = sup x∶ f (x)⩽1 ⟨x * , x⟩ = sup x∈B ⟨x * , x⟩, (4.6
)

{x * ∶ f ▵ (x * ) ⩽ 1} = B ▵ . (4.7) f ▵▵ (x) = sup x * ∶ f ▵ (x * )⩽1 ⟨x * , x⟩ = sup x * ∈B ▵ ⟨x * , x⟩, (4.8)
f is closed ⇒ f = f ▵▵ , (4.9
)

f * = I B ▵ , (4.10) ∂f (x) = {x * ∈ B ▵ ∶ ⟨x * , x⟩ = f (x)} ⊂ arg max x * ∈B ▵ ⟨x * , x⟩, (4.11)
f is closed ⇒ ∂f (x) = arg max x * ∈B ▵ ⟨x * ,
* ∶ f ▵ (x * ) ⩽ 1} = {x * ∶ ⟨x * , x⟩ ⩽ 1, for all x ∈ B} = B ▵ . [(4.8)]
For the first identity, apply the first identity in (4.6) to the gauge f ▵ instead of f . For the second identity, use (4.7).

[(4.

Abstract polyhedral gauge recovery

The results given in this section assume that the gauge f is polyhedral, which means that its epigraph is a polyhedron in E×R. This implies that f is also closed, so that the nuances introduced in (4.9) and (4.12) no longer matter. In particular, the subdifferential of f at x ∈ E is the set that we denote by S(x) ∶= arg max

x * ∈B ▵ ⟨x * , x⟩. (4.13)
Proposition 4.2 (solution existence) Let f be a polyhedral gauge whose domain intersects X , B be its unit sublevel set (4.1), x ∈ X , and S(x) be defined by (4.13).

Then

x ∈ Sol(P f ) ⇐⇒ ∃ ȳ ∈ F such that A * ȳ ∈ S(x), (4.14)
x ∈ ri Sol(P f ) ⇐⇒ ∃ ȳ ∈ F such that A * ȳ ∈ ri S(x). (4.15)

Proof. Since f ∈ Conv(E), since X is convex, and since (dom f ) ∩ X ≠ ∅, the function f ∶= f + I X is proper and convex. Furthermore, x ∈ Sol(P f ) if and only if 0 ∈ ∂ f (x). By the polyhedrality of f and I X , this can be written [36; th. 23.8]

0 ∈ ∂f (x) + ∂I X (x). (4.16)
It is known that ∂I X (x) is the normal cone N X (x) to X at x [36; p. 215] and it is easy to see that, in the present case, N X (x) = N (A) ⊥ = R(A * ), so that (4.16) claims the existence of some ȳ ∈ F such that A * ȳ ∈ ∂f (x) = S(x) by (4.12) and (4.13). Hence, we have the equivalence (4.14). Now, by the polyhedrality of f and lemma 2.1, x is in the relative interior of the solution set of (P f ) if and only if 0 ∈ ri ∂ f (x). Using (2.1) and the observations made above: ri ∂ f (x) = ri S(x) + R(A * ). The equivalence (4.15) follows.

◻

Similarly to the ℓ 1 norm recovery (see problem (D 1 ) at the end of section 3.1), the vector ȳ given in (4.14) solves the Lagrange dual of problem

(P f ), namely [21; § 4.2] (D f ) sup y∶ A * y∈B ▵ ⟨b, y⟩.
This claim will be proved in proposition 4.16, together with another form of the equivalence (4.14), namely (4.41a). We have put this optimality condition in the form (4.14) to highlight the analogy with the conditions (4.17) below.

Proposition 4.3 (solution existence and uniqueness) Let f be a polyhedral gauge whose domain intersects X , B be its unit sublevel set (4.1), x ∈ X , and S(x) be given by (4.13). Then Sol(P f ) = {x} if and only if

∃ ȳ ∈ F such that A * ȳ ∈ ri S(x), (4.17a)
aff

S(x) + R(A * ) = E. (4.17b)
Proof. Since f is a polyhedral function and X is a polyhedral set, by lemma 2.2, x is the unique minimizer of the proper convex polyhedral function f ∶= f + I X if and only if

0 ∈ int ∂ f (x) = int S(x) + R(A * ) , (4.18)
where we have used the same arguments as in the proof of proposition 4.2 to get the equality. Now property (4.18) can also be written as the following two properties:

0 ∈ ri S(x) + R(A * ) = ri S(x) + R(A * ), E = aff S(x) + R(A * ) = aff S(x) + R(A * ).
These two conditions are equivalent to (4.17).

◻

Finitely generated polyhedral gauge recovery

This section provides more precise expressions of the NSCs (4.14), (4.15), and (4.17), when one knows a so-called inner description of the polyhedron B, which is the unit sublevel set of the polyhedral gauge f . More specifically, we assume in this section that B is the polyhedron defined by

B ∶= co{c i ∶ i ∈ I} + cone{d j ∶ j ∈ J}, (4.19a)
where I and J are finite set of indices with I ∪ J ≠ ∅, the points c i ∈ E for i ∈ I, the directions d j ∈ E for j ∈ J, "co" denotes the convex hull, and "cone" denotes the conic convex hull. When I or J = ∅, we do not consider that B = ∅ but that the corresponding term in (4.19a) is absent. Any convex polyhedron can be written that way. The set B is unbounded if and only if some d j ≠ 0. The gauge f is then determined as the Minkowski function associated with B, namely

f (x) ∶= inf t {t > 0 ∶ x ∈ t B}. (4.19b)
We must assume that 0 ∈ B (4.19c) in order to have f (0) = 0. Since it is not supposed that 0 ∈ int B, the gauge f may take infinite value.

To simplify the presentation, we introduce some notation. We associate with I ′ ⊂ I and J ′ ⊂ J the linear maps

C I ′ ∶ α I ′ ∈ R I ′ ↦ C I ′ α I ′ ∶= ∑ i∈I ′ α i c i ∈ E, C ∶= C I , D J ′ ∶ β ∈ R J ′ ↦ D J ′ β ∶= ∑ j∈J ′ β j d j ∈ E, D ∶= D J . (4.20)
We adopt the matrix notation for the linear map

(C I ′ D J ′ ) ∶ (α I ′ , β J ′ ) ∈ R I ′ × R J ′ ↦ (C I ′ D J ′ )(α I ′ , β J ′ ) = C I ′ α I ′ + D J ′ β J ′ ∈ E (4.21)
and we note (C D) ∶= (C I D J ). With this notation, B can be written

B = {Cα + Dβ ∶ α ∈ ∆ I , β ∈ R J + }. (4.22)
where

∆ I ∶= {α ∈ R I + ∶ ∑ i∈I α i = 1} is the unit simplex in R I .
Observe that (4.19c) ensures the equivalence (the implication "⇒" is true without (4.19c), actually) The maximization problem defining the solution set S(x) by (4.25) is linear and it is therefore easy to give a characterization of the elements of S(x) and ri S(x).

f (x) = 0 ⇐⇒ x = Dβ for some β ⩾ 0 (or x = 0 if J = ∅). ( 4
x = C ᾱ + D β, (4.26a) ∀ i ∈ I, there holds: ᾱi > 0 ⇒ ⟨x * , c i ⟩ = 1, (4.26b) ∀ j ∈ J, there holds: βj > 0 ⇒ ⟨x * , d j ⟩ = 0, ( 4.26c)
2) x * ∈ ri S(x) if and only if there exists (ᾱ, β) ∈ R

I + × R J + such that x = C ᾱ + D β, (4.27a) ∀ i ∈ I, there holds: ᾱi > 0 ⇔ ⟨x * , c i ⟩ = 1, (4.27b) ∀ j ∈ J, there holds: βj > 0 ⇔ ⟨x * , d j ⟩ = 0. ( 4.27c)
Proof. 1) One may prefer rewriting the linear maximization problem in (4.25) as a minimization one:

inf x * {-⟨x * , x⟩ ∶ ⟨x * , c i ⟩ ⩽ 1 for i ∈ I, ⟨x * , d j ⟩ ⩽ 0 for j ∈ J }. (4.28)
The Lagrangian of that problem then reads

(x * , (α, β)) ∈ E × (R I × R J ) ↦ -⟨x * , x⟩ + i∈I α i (⟨x * , c i ⟩ -1) + j∈J β j ⟨x * , d j ⟩.
The necessary and sufficient optimality conditions ensuring that x * is a solution to (4.28) is precisely the existence of optimal multipliers (ᾱ, β) ∈ R I + ×R J + such that (4.26) holds [14, 3, 5]: (4.26a) expresses that the gradient of the Lagrangian with respect to x * vanishes and (4.26b)-(4.26c) express the complementarity (the constraints are satisfied by the assumption x * ∈ B ▵ ).

2) Recall that a point is in the relative interior of the solution set of a linear optimization problem if and only if one can find a dual solution with strict complementarity (this is a consequence of the existence of strict complementarity solutions in linear optimization [START_REF] Goldman | Theory of linear programming[END_REF][START_REF] Balinski | Duality theory of linear programs, a constructive approach with applications[END_REF], see [38; th. 3.3.6] for a similar claim). This is precisely what is expressed in point 2. ◻ Remarks 4.5 1) The point x given in the preamble of lemma 4.4 is arbitrary in E, but to guarantee the existence of a solution to the linear optimization problem in (4.25) it must be in cone{{c i } i∈I ∪ {d j } j∈J }, as shown by (4.26a). Furthermore, as shown in the proof of the lemma, the coefficients (ᾱ, β) of x in cone{{c i } i∈I ∪ {d j } j∈J } are the optimal multipliers associated with the constraints of the linear optimization problem in (4.25). 2) We quote for further reference that the proof of point 2 has shown that the pair (ᾱ, β) used in (4.27) are arbitrary optimal multipliers of the linear optimization problem in (4.25) satisfying strict complementarity.

As shown by the next proposition, problem (P f ) has a solution if and only if it is feasible. This property is shared with the linear optimization problem and problem (P 1 ), although, contrary to the ℓ 1 norm, the objective f of (P f ) is not necessarily coercive, so that it is the linear optimization proof that is inspiring here. Note also that problem (P f ) may well have a solution but an infinite optimal value: this situation will occur if and only if X ≠ ∅ and X ∩ (dom f ) = ∅. Proposition 4.6 (solution existence I) Let f be a polyhedral gauge. Then the solution set of (P f ) is a convex polyhedron. Furthermore, problem (P f ) has a solution if and only if its feasible set X is nonempty.

Proof. The solution set of (P f ) is a convex polyhedron, since it is a sublevel set of the polyhedral function f + I X . Obviously, X ≠ ∅ if (P f ) has a solution. Conversely, suppose that X ≠ ∅. If X ∩ (dom f ) = ∅, any point in X is a solution to the problem and the proposition is proved.

Consider now the case when X ∩ (dom f ) ≠ ∅, so that val(P f ) is finite (and nonnegative). Let {x k } be a minimizing sequence, meaning that {x k } ⊂ X and f (x k ) ↓ val(P f ). One can always assumed that f is determined by (4.19). By (4.19b), there exist sequences

{t k } ⊂ R ++ , {α k } ⊂ ∆ I , and {β k } ⊂ R J + such that t k ↓ val(P f ) and x k = t k (Cα k + Dβ k ).
We pursue by considering two cases.

r If val(P f ) = 0, then t k ↓ 0 and t k α k → 0. Since Ax k = b and x k -D(t k β k ) → 0, and since A(E) × (E -D(R J + )) is a closed set (it is a convex polyhedron), there exist (x, β) ∈ E × R J + such that Ax = b and x = D β. By (4.23), f (x) = 0, which implies that x is a solution to (P f ). r If val(P f ) ≠ 0, then Ax k t k → b val(P f ) and x k t k -Cα k -Dβ k = 0. Since A(E) × (E - C(∆ I ) -D(R J + )) is a closed set (it is a convex polyhedron), there exist (x ′ , ᾱ, β) ∈ E × ∆ I × R J + such that Ax ′ = b val(P f ) and x′ = C ᾱ + D β. Therefore the point x ∶= val(P f )x ′ verifies Ax = b and x = val(P f )(C ᾱ + D β),
showing that x ∈ X and f (x) ⩽ val(P f ). Hence x is a solution to (P f ). ◻

The next proposition particularizes proposition 4.2 to the case when the polyhedral gauge f is given by (4.19). Proposition 4.7 (solution existence II) Let f be the polyhedral gauge determined by (4.19) whose domain intersects X and let x ∈ X . Then 1) x ∈ Sol(P f ) if and only if the following two conditions hold

x = C ᾱ + D β for some (ᾱ, β) ∈ R I + × R J + , (4.29a)
∃ ȳ ∈ F such that for any i ∈ I and j ∈ J, there hold

⟨A * ȳ, c i ⟩ = 1 if ᾱi > 0, ⟨A * ȳ, c i ⟩ ⩽ 1 if ᾱi = 0, ⟨A * ȳ, d j ⟩ = 0 if βj > 0, and ⟨A * ȳ, d j ⟩ ⩽ 0 if βj = 0, ⎫ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎭ (4.29b)
2) x ∈ ri Sol(P f ) if and only if the following two conditions hold

x = C ᾱ + D β for some (ᾱ, β) ∈ R I + × R J + , (4.30a)
∃ ȳ ∈ F such that for any i ∈ I and j ∈ J, there hold

⟨A * ȳ, c i ⟩ = 1 if ᾱi > 0, ⟨A * ȳ, c i ⟩ < 1 if ᾱi = 0, ⟨A * ȳ, d j ⟩ = 0 if βj > 0, and ⟨A * ȳ, d j ⟩ < 0 if βj = 0. ⎫ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎭ (4.30b)
Proof. 1) By proposition 4.2, x ∈ Sol(P f ) if and only if there is some ȳ ∈ F such that A * ȳ is in the set S(x) defined by (4.25). By lemma 4.4, this is equivalent to the existence of (ᾱ, β, ȳ) ∈ R r Assume that (4.29) holds. Then for all i ∈ [1 ∶ n], xi = ᾱiᾱ-i with ᾱi ⩾ 0 and ᾱ-i ⩾ 0 by (4.29a) and ᾱi ᾱ-i = 0 by (4.29b), so that ᾱi = max(0, xi ) and ᾱ-i = max(0, -x i ).

I + × R J + × F such that
Then (4.29b) provides a ȳ ∈ R m such that xi > 0 ⇒ ᾱi > 0 ⇒ (A * ȳ) i = 1, xi < 0 ⇒ ᾱ-i > 0 ⇒ (A * ȳ) i = -1, xi = 0 ⇒ ᾱi = ᾱ-i = 0 ⇒ (A * ȳ) i ⩽ 1.
Hence (A T ȳ) i = sign(x i ) if xi ≠ 0 and (A T ȳ) i ⩽ 1 otherwise, which is precisely (3.1).

r Conversely, assume that (3.1) holds. Then one gets (4.29) by taking ᾱi = max(0, xi ), ᾱ-i = max(0, -x i ) and the same ȳ.

2) Not every decomposition of x like in (4.29a) is appropriate to get (4.29). A straightforward counter-example is the following.

Assume that B is bounded (equivalently J = ∅), that the origin is not a vertex of B, and that b = 0. Then x = 0 is the unique solution to (P f ) and (4.29) is satisfied with ᾱ = 0 and ȳ = 0. Now, one can also write x = ∑ i∈I ᾱi c i with some nonzero ᾱ ∈ R I + (since 0 is not a vertex of B); but one cannot find a ȳ such that ⟨A * ȳ, c i ⟩ = 1 when ᾱi > 0, since this would imply 0 = ⟨A * ȳ, x⟩ = ∑ i∈I ᾱi ⟨A * ȳ, c i ⟩ = ∑ i∈I ᾱi > 0, which yields a contradiction.

In the previous counter-example, for the solution x = 0, there holds S(x) = B ▵ . Since x * ∶= A * 0 = 0 ∈ B ▵ , one can take ȳ = 0 in (4.14) or (4.29b). Since the constraints of the problem in (4.25) are all inactive at x * = 0, all the multipliers ᾱi must vanish. This is the reason why taking ᾱ ≠ 0 in (4.29) for decomposing x is not acceptable. ◻

We recall that a face F of a convex set C is a convex part of C such that, whenever x ∈ C, y ∈ C, t ∈ ]0, 1[, and (1t)x + ty ∈ F, then x and y ∈ F. It is not difficult to see that the set of solutions of a linear optimization problem is a face of its feasible set (it is called an exposed face, actually).

To characterize the solution uniqueness, we shall need an analytic description of the affine hull of S(x), which is the goal of the next lemma. where

I + ∶= {i ∈ I ∶ ⟨x * , c i ⟩ = 1} and J + ∶= {j ∈ J ∶ ⟨x * , d j ⟩ = 0}.
Proof.

[⊂] Let u * ∈ aff S(x)x * . We only have to show that u * satisfies the constraints in the second term of the right hand side of (4.32). Since x * ∈ ri S(x) by ssumption and x * + u * ∈ aff S(x), x * t ∶= x * + tu * = (1t)x * + t(x * + u * ) is in S(x) for small t . In particular ⟨x * t , c i ⟩ ⩽ 1 and ⟨x * t , d j ⟩ ⩽ 0 for small t , i ∈ I, and j ∈ J (since S(x) ⊂ B ▵ ). Using ⟨x * , c i ⟩ = 1 and ⟨x * , d j ⟩ = 0 for i ∈ I + and j ∈ J + , one gets t⟨u * , c i ⟩ ⩽ 0 and t⟨u * , d j ⟩ ⩽ 0 for small t , i ∈ I + , and j ∈ J + , which implies that ⟨u * , c i ⟩ = 0 and ⟨u * , d j ⟩ = 0 for i ∈ I + and j ∈ J + .

[⊃] Assume that u * ∈ E is such that ⟨u * , c i ⟩ = 0 and ⟨u * , d j ⟩ = 0 for i ∈ I + and j ∈ J + .

We only have to show that x * + u * ∈ aff S(x). Observe that x * t ∶= x * + tu * ∈ B ▵ for small t (i.e., ⟨x * t , c i ⟩ ⩽ 1 and ⟨x * t , d j ⟩ ⩽ 0 for small t , i ∈ I, and j ∈ J, which comes from the definitions of I + and J + , and from the assumed properties of u * ). Now S(x) is a face of B ▵ by its definition (4.25) and x * ∈ S(x) by assumption, so that x * t ∈ S(x) for small t . This implies that, for some small t ≠ 0, x *

+ u * = (1 -1 t)x * + (1 t)(x * + tu * ) = (1 -1 t)x * + (1 t)x * t ∈ aff{x * , x * t } ⊂ aff S(x). ◻
The motivation for introducing condition (ii) in the next proposition, which is apparently a little stronger in its formulation than condition (iii) (but the proposition claims that they are equivalent), is that this form of the uniqueness characterization is useful for the uniqueness detection process proposed in section 4.4.2. In the proposed process, some index sets I + ⊂ I and J + ⊂ J such that (4.33a) and (4.33b) hold are first determined; then the occurrence of uniqueness is verified by checking whether (4.33c) holds for the computed index sets. In other words, the index sets I + and J + are not computed such that the three properties in (4.33) hold, but only the first two; the third one is automatically satisfied for the index sets determined in that manner, provided x is the unique solution to (P f ).

Proposition 4.10 (solution existence and uniqueness) Let f be the polyhedral gauge determined by (4.19) whose domain intersects X and x ∈ X . Then, the following three conditions are equivalent (i) x is the unique solution to (P f ), (ii) there are sets of indices I + ⊂ I and J + ⊂ J such that x = C I+ ᾱI+ + D J+ βJ+ for some ᾱI+ > 0 and βJ+ > 0, (4.33a)

∃ ȳ ∈ F such that ⟨A * ȳ, c i ⟩ = 1 if i ∈ I + , ⟨A * ȳ, c i ⟩ < 1 if i ∈ I c + , ⟨A * ȳ, d j ⟩ = 0 if j ∈ J + , ⟨A * ȳ, d j ⟩ < 0 if j ∈ J c + , (4.33b)
and, for any such index sets, there holds

N (A) ∩ R(C I+ D J+ ) = {0}, (4.33c)
where (C I+ D J+ ) is the linear map defined by (4.21), (iii) there are sets of indices I + ⊂ I and J + ⊂ J such that (4.33) holds.

Proof. [(i) ⇒ (ii)] The fact that Sol(P f ) is the singleton {x} implies that x ∈ ri Sol(P f ). Then, by point 2 of proposition 4.7, (4.30) holds. Defining I + ∶= {i ∈ I ∶ ᾱi > 0} and J + ∶= {j ∈ J ∶ βj > 0}, we get (4.33a) and (4.33b). Now, let I + ⊂ I and J + ⊂ J be arbitrary index subsets such that (4.33a) and (4.33b) hold for some ᾱI+ > 0, βJ+ > 0, and ȳ ∈ F. Setting ᾱI c + = 0 and βJ c + = 0, we get real vectors ᾱ and β that satisfy (4.27) with x * ∶= A * ȳ ∈ B ▵ . Therefore, thanks to lemma 4.4, the vector ȳ given by (4.33b) verifies

A * ȳ ∈ ri S(x), (4.34)
where S(x) is defined by (4.25). By (i) and proposition 4.3, we also have

aff S(x) + R(A * ) = E, (4.35)
since this identity does not depend on the previously determined ȳ. Using lemma 4.9 with x * ∶= A * ȳ ∈ ri S(x) by (4.34), we get

aff S(x) = A * ȳ + {u * ∈ E ∶ ⟨u * , c i ⟩ = 0 for i ∈ I + , ⟨u * , d j ⟩ = 0 for j ∈ J + }. (4.36)
One can now prove that the identities (4.35) and (4.33c) are equivalent:

(4.35) ⇐⇒ {u * ∈ E ∶ ⟨u * , c i ⟩ = 0 for i ∈ I + , ⟨u * , d j ⟩ = 0 for j ∈ J + } + R(A * ) = E [by (4.36)] ⇐⇒ {u * ∈ E ∶ ⟨u * , c i ⟩ = 0 for i ∈ I + , ⟨u * , d j ⟩ = 0 for j ∈ J + } ⊥ ∩ R(A * ) ⊥ = {0}
[by taking the orthogonal of both sides] ⇐⇒ (4.33c).

[(ii) ⇒ (iii)] Straightforward.

[(iii) ⇒ (i)] We have seen in the proof of the implication (i) ⇒ (ii) that (4.33a)-(4.33b) imply (4.34). Therefore, (4.36) still holds and therefore also the equivalence between (4.33c) and (4.35). Now, by proposition 4.3, (4.34) and (4.35) show that x is the unique solution to (P f ). ◻

The two examples below show that, knowing a solution x to (P f ), it is not necessarily easy to see whether one can find coefficients (ᾱ, β) in (4.33a) and a ȳ ∈ F, such that the pair (A * ȳ, (ᾱ, β)) satisfies (4.33), which would guarantee the uniqueness of the solution by proposition 4.10. The proof has shown that the key issue is that (A * ȳ, (ᾱ, β)) must be a primal-dual solution to the linear optimization problem in (4.25) with strict complementarity.

Examples 4.11 1) Not all the subsets I + ⊂ I and J + ⊂ J allowing x to be represented by (4.33a) are appropriate to get (4.33b) (for some ȳ ∈ F) and (4.33c).

Consider indeed the case where E = F = R 2 and B = co{c 1 , c 2 , c 3 , c 4 } (hence J = ∅), with

c 1 = 0 0 , c 2 = 1 1 , c 3 = 1 0 , c 4 = 1 -1 , A = 1 0 0 1 , and b = 1 0 .
By the nonsingularity of A, the feasible set of (P f ) is reduced to the single point e 1 , so that (P f ) has for unique solution x = e 1 . Now, with the representation x = c 3 , (4.33a) holds with I + = {3} and (4.33c) holds by the nonsingularity of A. Nevertheless, it is not possible to find ȳ ∈ R 2 ensuring (4.33b), since

A * ȳ = ȳ ∈ R 2 should verify ȳ1 + ȳ2 < 1, ȳ1 = 1, and ȳ1 -ȳ2 < 1,
which is an infeasible system. For this problem, an appropriate representation of x uses all the c i 's belonging to the face of x in B (taking only two of them is not enough), namely the three vectors c 2 , c 3 , and c 4 , and could be x = According to (4.24), for this example,

B ▵ = {x * ∈ R 2 ∶ x * 1 + x * 2 ⩽ 1, x * 1 ⩽ 1, x * 1 -x * 2 ⩽ 1},
so that the set of maximizers of ⟨⋅, x⟩ on B ▵ is the singleton S(x) = {(1, 0)}. This one is, of course, in the relative interior of S(x), so that it has an associated strict complementarity multiplier ᾱ (see point 2 of remark 4.5). Such a multiplier must satisfy ᾱ1 = 0 and ᾱi > 0 for i ∈ {2, 3, 4}, which is the reason why x can and must be decomposed in (4.33a) with I + = {2, 3, 4}.

2) As a counterpoint to the previous example, it is not true that, when J = ∅, representing x by all the c i 's belonging to the face of x in B is appropriate to get (4.33).

Consider indeed the case where E = R 2 and B = co{c 1 , c 2 , c 3 }, with

c 1 = 1 1 , c 2 = 1 -1 , c 3 = -1 0
, and b = 0.

Since B is bounded and b = 0, x = 0 is the unique solution to (P f ) (see (4.23) and use J = ∅). Now, with the representation x = 1 4 c 1 + 1 4 c 2 + 1 2 c 3 , (4.33a) holds with

I + = {1, 2, 3} and (4.33c) holds, provided A is injective. Nevertheless, it is not possible to find ȳ ensuring (4.33b), since x * ∶= A * ȳ ∈ R 2 should verify x * 1 + x * 2 = 1, x * 1 -x * 2 = 1, and -x * 1 = 1,
which is an incompatible system. For this problem, the appropriate representation of x uses none of the c i 's: x = 0c 1 + 0c 2 + 0c 3 . Then I + = ∅ and x * = A * 0 = 0 satisfies (4.33b), which now reads

x * 1 + x * 2 < 1, x * 1 -x * 2 < 1, and -x * 1 < 1.
Like in the previous example, the good way of determining the decomposition of x in (4.33a) follows point 2 of remark 4.5. According to (4.24), for this example,

B ▵ = {x * ∈ R 2 ∶ x * 1 + x * 2 ⩽ 1, x * 1 -x * 2 ⩽ 1, -x * 1 ⩽ 1}.
Since x = 0, the set of maximizers of ⟨⋅, x⟩ on B ▵ is the full feasible set B ▵ . A strict complementarity solution to this problem is formed of an interior point of B ▵ and a zero vector of multipliers ᾱ (or ᾱi > 0 for i ∈ ∅). This is the reason why x can and must be decomposed in (4.33a) with I + = ∅.

Remarks 4.12 1) Condition (4.33c) is weaker than the injectivity of A(C I+ D J+ ), where (C I+ D J+ ) is the linear map defined by (4.21).

The injectivity of A(C I+ D J+ ) requires indeed, in addition to (4.33c), the injectivity of (C I+ D J+ ) or, equivalently, the linear independence of the vectors

{c i ∶ i ∈ I + } ∪ {d j ∶ i ∈ J + }. Actually, condition (4.33c) is equivalent to the injectivity of A(C I ′ + D J ′ + )
, where I ′ + and J ′ + are subsets of I + and J + respectively such that the vectors

{c i ∶ i ∈ I ′ + } ∪ {d j ∶ j ∈ J ′ + } form a basis of R((C I+ D J+ )).
In case of the ℓ 1 norm recovery (continued from example 4.8(1)), B is given by (4.31) and the indices in I + refer to ±e i , for some i ∈ [1 ∶ n], but not both +e i and -e i are refered to for the same i (since ⟨A * ȳ, e i ⟩ = 1 and ⟨A * ȳ, -e i ⟩ = 1 cannot be both true), so that the vectors {c i ∶ i ∈ I + } are linearly independent. In that case condition (4.33c) immediately provides (3.4b).

2) Conditions (3.4) can be deduced from conditions (4.33) when the spaces E = R n and F = R m , both equipped with the Euclidean scalar product (x, y) ↦ x T y, and f is the ℓ 1 norm (continued from example 4.8(1)).

Indeed, by the same reasoning as the one made in example 4.8(1), we see that condition (4.33b) implies (3.4a). In addition, we have also shown at the end of the previous remark that (4.33c) implies (3.4b). ◻

Implementation issues

Solution computation

In this section, we show that computing a solution to problem (P f ), where f is the polyhedral gauge determined by (4.19), can be done by solving the linear optimization problem:

(P ′ f ) ⎧ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎩ sup (α,β,t)∈R I ×R J ×R t A(Cα + Dβ) = tb (α, β) ∈ ∆ I × R J +
, where the linear maps C and D have been defined by (4.20). Roughly speaking, in problem (P f ), the unit sublevel set B is scaled in order to make its boundary just in contact with the affine space X = {x ∈ E ∶ Ax = b} (by the positive homogeneity of f this amounts to finding its appropriate sublevel set), while in (P ′ f ), the same affine space is translated to make it just in contact with the unit sublevel set B. The sense of the equivalence between (P f ) and (P ′ f ) is clarified by the next proposition.

Proposition 4.13 (equivalence between (P f ) and (P ′ f )) Let f be the polyhedral gauge determined by (4.19). Then, there exists a pair (α 0 , β 0 )

∈ ∆ I × R J + such that Cα 0 + Dβ 0 = 0. Furthermore 1) b ∈ AD(R J + ) ⇐⇒ Dβ ∈ Sol(P f ) for some β ⩾ 0 ⇐⇒ val(P f ) = 0 ⇐⇒ val(P ′ f ) = +∞; 2) b ∉ A(R + B) ⇐⇒ val(P f ) = +∞ ⇐⇒ val(P ′ f ) = 0 ⇐⇒ (α 0 , β 0 , 0) ∈ Sol(P ′ f ); 3) if b ∈ A(R + B) ∖ AD(R J + ), then 0 < val(P ′ f ) = 1 val(P f ) < +∞; in addition, r if (ᾱ, β, t) is a solution to (P ′ f ), then x = (C ᾱ + D β) t is a solution to (P f ); r conversely, if x is a solution to (P f ), then x = f (x)(C ᾱ + D β) for some (ᾱ, β) ∈ ∆ I × R J +
and, for any such writing of x, (ᾱ, β, 1 f (x)) is a solution to (P ′ f ).

Proof. Since 0 ∈ B by (4.19c), there is a pair (α 0 , β 0 ) ∈ ∆ I × R J + such that Cα 0 + Dβ 0 = 0. Observe that (α 0 , β 0 , 0) is feasible for (P ′ f ), so that val(P ′ f ) ⩾ 0. Also val(P f ) ⩾ 0. [Dβ ∈ Sol(P f ) for some β ⩾ 0 ⇐⇒ val(P f ) = 0] This is a consequence of (4.23) and the fact that problem (P f ) has a solution when val(P f ) is finite (proposition 4.6).

[b ∈ AD(R

J + ) ⇐⇒ val(P ′ f ) = +∞] If b ∈ AD(R J + )
, then b = ADβ for some β ⩾ 0 and, whatever is t ⩾ 0, (α 0 , β 0 + tβ, t) is feasible for

(P ′ f ), hence (P ′ f ) is unbounded. Conversely, if (P ′ f ) is unbounded, there is a sequence (α k , β k , t k ) ∈ ∆ I × R J + × R with A(Cα k + Dβ k ) = t k b and t k → ∞, which implies that (ADβ k ) t k → b. Since AD(R J + ) is closed (it is a polyhedral cone), b is in that set. 2) [b ∉ A(R + B) ⇐⇒ val(P f ) = +∞]
We show the contrapositives thanks to the following sequence of equivalences: val

(P f ) < +∞ ⇐⇒ X ∩ (dom f ) ≠ ∅ ⇐⇒ ∃ x such that Ax = b and f (x) < +∞ ⇐⇒ ∃ x such that Ax = b and x ∈ R + B ⇐⇒ b ∈ A(R + B).
[b ∉ A(R + B) ⇐⇒ val(P ′ f ) = 0] First note that the pair (α 0 , β 0 , 0) is feasible for (P ′ f ) and gives a zero value to its objective. Therefore, val(P ′ f ) = 0 ⇐⇒ there is no feasible point (α, β, t) of (P

′ f ) with t > 0 ⇐⇒ b ∉ A(R + B). [val(P ′ f ) = 0 ⇐⇒ (α 0 , β 0 , 0) ∈ Sol(P ′ f )] Clear. 3) Assume now that b ∈ A(R + B) ∖ AD(R J + ). Let us show that 0 < val(P ′ f ) = 1 val(P f ) < +∞. (4.37)
By points 1 and 2, val(P f ) is positive and finite. Therefore, for any ε > 0, one can find x ε ∈ E such that Ax ε = b and f (x ε ) ⩽ val(P f ) + ε, implying that x ε ∈ (val(P f ) + 2ε)B, so that 1 (val(P f ) + 2ε) ⩽ val(P ′ f ). Since ε > 0 is arbitrary, there holds 1 ⩽ val(P f ) val(P ′ f ). Conversely, by points 1 and 2, val(P ′ f ) is positive and finite. Therefore, for any ε in ]0, val(P ′ f )[, one can find

(α ε , β ε , t ε ) ∈ ∆ I × R J + × R such that A(Cα ε + Dβ ε ) = t ε b and t ε ⩾ val(P ′ f ) -ε > 0. Since (Cα ε + Dβ ε ) t ε is feasible for (P f ), there holds val(P f ) ⩽ f ((Cα ε + Dβ ε ) t ε ) = f (Cα ε + Dβ ε ) t ε ⩽ 1 t ε [since Cα ε + Dβ ε ∈ B] ⩽ 1 (val(P ′ f ) -ε)
. Now ε > 0 can be taken arbitrary small, so that val(P f ) val(P ′ f ) ⩽ 1. We have shown (4.37). If (ᾱ, β, t) ∈ Sol(P ′ f ), then t = val(P ′ f ) > 0 and x ∶= (C ᾱ + D β) t is feasible for (P f ), so that val

(P f ) ⩽ f (x) = f (C ᾱ + D β) t ⩽ 1 t = 1 val(P ′ f ) = val(P f ) by (4.37); hence x ∈ Sol(P f ). Conversely, if x ∈ Sol(P f ), val(P f ) = f (x), which implies that x ∈ f (x)B or x = f (x)(C ᾱ + D β) for some (ᾱ, β) ∈ ∆ I × R J + . Now, Ax = b shows that (ᾱ, β, 1 f (x)) is feasible for (P ′ f ), so that val(P ′ f ) ⩾ 1 f (x) = 1 val(P f ) = val(P ′ f ) by (4.37); hence (ᾱ, β, 1 f (x)) ∈ Sol(P ′ f ). ◻
The fact that problem (P f ) is equivalent to the linear optimization problem (P ′ f ) makes it possible to solve (P f ) in polynomial time, for example by using an interior point method [START_REF] Roos | Theory and Algorithms for Linear Optimization -An Interior Point Approach[END_REF][START_REF] Wright | Primal-Dual Interior-Point Methods[END_REF][START_REF] Armand | A feasible BFGS interior point algorithm for solving strongly convex minimization problems[END_REF][START_REF] Gilbert | Examples of ill-behaved central paths in convex optimization[END_REF].

Uniqueness detection

This section proposes a technique for detecting uniqueness of a solution to problem (P f ). It consists in solving problem (P ′ f ) by an interior point method and then checking the linear algebra condition (4.33c). Let us look at the method in detail.

The easy cases are when b ∈ AD(R

J + ) or b ∉ A(R + B). r If b ∈ AD(R J + )
, which implicitly assumes that J ≠ ∅, then val(P f ) = 0 (by point 1 of proposition 4.13) and Sol(P f ) = D(R J + ) by (4.23). In that case the solution is not unique.

r If b ∉ A(R + B), then (P f ) has no solution (by point 2 of proposition 4.13). From now on, we assume that b ∈ A(R + B) ∖ AD(R J + ). When J ≠ ∅, this assumption implies that b ≠ 0.

Consider the following Lagrangian of problem

(P ′ f ): ((α, β, t), (y, s, u, v)) ↦ -t -⟨y, A(Cα + Dβ) -tb⟩ + s(½ T α -1) -u T α -v T β, where (y, s, u, v) ∈ F × R × R I + × R J +
and ½ is a vector of all ones. We see that (ᾱ ′ , β′ , t) is a solution to the linear optimization problem (P ′ f ) if and only if there exist multipliers (ȳ ′ , s, ū′ , v′ ) such that [3, 5]

C * A * ȳ′ + ū′ = s½, D * A * ȳ′ + v′ = 0, ⟨b, ȳ′ ⟩ = 1, A(C ᾱ′ + D β′ ) = tb, ½ T ᾱ′ = 1, 0 ⩽ ᾱ′ ⊥ ū′ ⩾ 0, and 0 ⩽ β′ ⊥ v′ ⩾ 0. When b ∈ A(R + B) ∖ AD(R J + ), t = val(P ′ f
) is a positive number (proposition 4.13), so that ᾱ ∶= ᾱ′ t and β ∶= β′ t are well defined and the above optimality conditions become

C * A * ȳ′ + ū′ = s½, D * A * ȳ′ + v′ = 0, ⟨b, ȳ′ ⟩ = 1, A(C ᾱ + D β) = b, ½ T ᾱ = 1 t, 0 ⩽ ᾱ ⊥ ū′ ⩾ 0, and 0 ⩽ β ⊥ v′ ⩾ 0.
Now, observe that s ≠ 0, since by the optimality conditions:

1 = ⟨b, ȳ′ ⟩ = ⟨A(C ᾱ + D β), ȳ′ ⟩ = ⟨ᾱ, C * A * ȳ′ ⟩ + ⟨ β, D * A * ȳ′ ⟩ = ⟨ᾱ, s½ -ū′ ⟩ -⟨ β, v′ ⟩ = ⟨ᾱ, s½⟩ = s ᾱ 1 .
Therefore, one can set ȳ ∶= ȳ′ s, ū ∶= ū′ s, and v ∶= v′ s. The optimality conditions then become

C * A * ȳ + ū = ½, D * A * ȳ + v = 0, ⟨b, ȳ⟩ = 1 s, A(C ᾱ + D β) = b, ½ T ᾱ = 1 t, 0 ⩽ ᾱ ⊥ ū ⩾ 0, and 0 ⩽ β ⊥ v ⩾ 0. (4.38)
There are primal-dual path-following interior-point methods that can find a primaldual solution ((ᾱ, β, t), (ȳ, s, ū, v)) to the linear optimization problem (P ′ f ) with strict complementarity [START_REF] Roos | Theory and Algorithms for Linear Optimization -An Interior Point Approach[END_REF][START_REF] Wright | Primal-Dual Interior-Point Methods[END_REF]. In view of (4.38), this means that

∀ i ∈ I ∶ ᾱi = 0 ⇐⇒ ūi > 0 ⇐⇒ (C * A * ȳ) i < 1, ∀ j ∈ J ∶ βj = 0 ⇐⇒ vi > 0 ⇐⇒ (D * A * ȳ) j < 0.
Using the definitions (4.20) of C and D, this can equivalently be written

∀ i ∈ I ∶ ᾱi = 0 ⇐⇒ ⟨A * ȳ, c i ⟩ < 1, ∀ j ∈ J ∶ βj = 0 ⇐⇒ ⟨A * ȳ, d j ⟩ < 0.
Defining I + ∶= {i ∈ I ∶ ᾱi > 0}, J + ∶= {j ∈ J ∶ βj > 0}, and x ∶= C ᾱ + D β, we see that the quadruple (x, ȳ, ᾱI+ , βJ+ ) satisfies conditions (4.33a) and (4.33b) in proposition 4.10. By this proposition, x will be the unique solution to (P f ) if and only if (4.33c) holds, namely

N (A) ∩ R(C I+ D J+ ) = {0},
where (C I+ D J+ ) is the linear map defined by (4.21).

We can now make precise the uniqueness detection algorithm, which is based on the above discussion. Algorithm 4.14 (uniqueness detection) 1) Solve the linear optimization problem (P ′ f ) by a solver providing a strict complementarity solution, when a solution exists (cases 3 and 4 below).

2) If its optimal value val(P ′ f ) = +∞, then val(P f ) = 0 and r either J ≠ ∅, in which case Sol(P f ) = D(R J + ) (the solution is not unique), r or J = ∅, in which case Sol(P f ) = {0} (the solution is unique).

3) If its optimal value val(P ′ f ) = 0, then val(P f ) = +∞ (the problem is unbounded). 4) Otherwise 0 < val(P ′ f ) < +∞, in which case val(P f ) = 1 val(P ′ f ). Let ((ᾱ, β, t), (ȳ, s, ū, v)) be the strict complementarity primal-dual solution computed by the solver. Then x = (C ᾱ + D β) t is a solution to (P f ) and this one is unique if and only if

N (A) ∩ R(C I+ D J+ ) = {0},
where I + ∶= {i ∈ I ∶ ᾱi > 0} and J + ∶= {j ∈ J ∶ βj > 0}.

This algorithm has been implemented in a small piece of software, written in Matlab, called pgr. It is available on the author's site. The examples given in this paper have been implemented and can be solved by pgr.

It may look surprising that, in algorithm 4.14 and the discussion that precedes, the index sets I + ⊂ I and J + ⊂ J are determined by solving problem (P ′ f ), while throughout the proofs (see proposition 4.10 for instance), these index sets were supposed to be determined by solving the linear optimization in (4.25). The rest of this section provides results, which, in addition to their own interst, show that there are still other ways of determining the index sets I + and J + .

It is not difficult to show that the Lagrange dual of (P ′ f ) reads

(D ′ f ) ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ inf (y,s)∈F×R s ⟨A * y, c i ⟩ ⩽ s, ∀ i ∈ I ⟨A * y, d j ⟩ ⩽ 0, ∀ j ∈ J ⟨b, y⟩ = 1.
By weak duality, there holds val(D ′ f ) ⩾ val(P ′ f ). Proof. Problem (D ′ f ) is a feasible linear optimization problem with an optimal value val(D ′ f ) ⩾ val(P ′ f ) ⩾ 0 (by weak duality and by the nonnegativity of val(P ′ f ) proved in proposition 4.13). In linear optimization, there is a duality gap if only if both the primal and dual problems are infeasible, a situation that is prevented in (P ′ f ) by the nonnegativity of its optimal value, so that val(P ′ f ) = val(D ′ f ) (these optimal values can be +∞ though). Now, (D f ) is the Lagrange dual of (P f ), so that val(D f ) ⩽ val(P f ) and we only need to prove that val(D f ) ⩾ val(P f ). We consider three disjunctive cases.

r If val(P f ) = 0, the inequality val(D f ) ⩾ val(P f ) is clear since val(D f ) ⩾ 0 (y = 0 is feasible). r If val(P f ) = +∞, then b ∉ A(R + B
) by point 2 of proposition 4.13, so that one can write

b = b + + b -, with b + ∈ A(R + B) (a closed convex cone), b -∈ [A(R + B)] -∖ {0}
, and ⟨b + , b -⟩ = 0 (Moreau's decomposition [START_REF] Moreau | Proximité et dualité dans un espace hilbertien[END_REF]). Then observe that y t ∶= tb -, with t ⩾ 0, is feasible for (D f ) (because ⟨y t , A(Cα + Dβ)⟩ ⩽ 0 for all α ∈ ∆ I and β ⩾ 0, which follows from b -∈ [A(R + B)] -, implies that ⟨A * y t , c i ⟩ ⩽ 0 for all i ∈ I and ⟨A * y t , d j ⟩ ⩽ 0 for all j ∈ J, hence certainly A * y t ∈ B ▵ ) and that ⟨b, y t ⟩ = t b -2 → ∞ when t → ∞, so that val(D f ) = +∞. The next proposition makes precise the sense in which the vector ȳ appearing in (4.14) and (4.15) is a dual solution to (P f ), i.e., a solution to (D f ). We recall that for convex sets C, C 1 , C 2 in F, there hold [36; th. 6.5 and th. 6.6] (ri [(4.41c)] Just take the relative interior of the identity in (4.41b), using (4.39) and (4.40).

C 1 ) ∩ (ri C 2 ) ≠ ∅ ⇒ ri(C 1 ∩ C 2 ) = (ri C 1 ) ∩ (ri C 2 ), (4.39
[(4.41d) ⇒] By (4.15), the assumption of (4.41c) is satisfied, so that A * (ri Sol(D f )) = (ri S(x)) ∩ R(A * ), which implies that A * ȳ ∈ ri S(x) when ȳ ∈ ri Sol(D f ).

[(4.41d) ⇐] Suppose that A * ȳ ∈ ri S(x). Then x ∈ ri Sol(P f ) by (4.15). Since A * ȳ is in the relative interior of the solution set of the linear optimization problem in (4.25), there exist optimal multipliers (ᾱ, β) associated with the constraints of that problem that satisfy strict complementarity:

x = C ᾱ + D β, 0 ⩽ ᾱ ⊥ s (C * A * ȳ -½) ⩽ 0, 0 ⩽ β ⊥ s D * A * ȳ ⩽ 0,
where 0 ⩽ v ⊥ s w ⩽ 0 denotes strict complementarity: v ⩾ 0, w ⩽ 0, and (v i > 0 ⇔ w i = 0 for all index i). Multiplying the first equation by A and using Ax = b, the system becomes

b = AC ᾱ + AD β, 0 ⩽ ᾱ ⊥ s (C * A * ȳ -½) ⩽ 0, 0 ⩽ β ⊥ s D * A * ȳ ⩽ 0.
These are the optimality conditions ensuring that ȳ is a solution to the dual problem (D f ) and the strict complementarity implies that ȳ ∈ ri Sol(D f ). ◻ Remark 4.17 The proof of [(4.41d) ⇐] has also shown that the optimal multipliers ᾱ and β associated with the constraints of the problem in (4.25) can be taken as optimal multipliers associated with the constraints of (D f ) and that the primal solution can be recovered by x = C ᾱ + D β. ◻

Polyhedral constraints

The linearly constrained polyhedral gauge recovery problem (P f ) can take into account polyhedral constraints, instead of its affine constraint, by reformulating the problem. Suppose indeed that the problem of interest reads inf f 0 (x)

x ∈ P, (4.42a)

where f 0 ∶ E → R ∪ {+∞} is the Minkowski function associated with a convex polyhedron B 0 ⊂ E containing zero and P is another convex polyhedron of E. A problem of this form is considered in [START_REF] Zhao | Constructing new weighted ℓ 1 -algorithms for the sparsest points of polyhedral sets[END_REF], with f 0 being the ℓ 1 norm. The convex polyhedron P can always be written , where e i denotes here the ith canonical basis vector of R m . The equivalence between (4.43), hence the polyhedral constrained gauge recovery problem (4.42), and the affine constrained gauge recovery problem (4.44) rests on the fact that f (x, s) = f 0 (x) if s ⩾ 0, and f (x, s) = +∞ if s ⩾ 0.

P = {x ∈ E ∶ Ax ⩽ b}, (4.42b
Therefore the existence and uniqueness results of this paper and its uniqueness detection algorithm can also be applied to problem (4.42).

Conclusion

This paper has developed a series of tools, derived from convex analysis, that should be of interest in various recovery problems. This includes a characterization of the relative interior of the solution set of a polyhedral optimization problem and a relatively detailed presentation of the gauge recovery problem. The paper particularly stresses on the characterization of the uniqueness of the solution as well as on its numerical detection.

Proposition 3 . 1 (

 31 solution existence) Let x ∈ R n be a point satisfying Ax = b, I ∶= {i ∈ [1 ∶ n] ∶ xi ≠ 0}, and s ∶= sign(x I ). Then x ∈ Sol(P 1 ) if and only if

  9)] It is a consequence of the fact the f ▵▵ is the closure of f [36; th. 15.1]. [(4.10)] It is shown in [21; prop. 2.1(iv)] that f * is the indicator function of the set {x * ∶ f ▵ (x * ) ⩽ 1}, which is B ▵ by (4.7). [(4.11)] The identity follows directly from (4.10), since x * ∈ ∂f (x) if and only if f (x) + f * (x * ) = ⟨x * , x⟩ (by (2.6) since f ∈ Conv(E)). For the inclusion, observe that, for x * ∈ B ▵ , there holds ⟨x * , x⟩ ⩽ f (x) by (4.5) and (4.7). [(4.12)] If x * ∈ arg max{⟨x * , x⟩ ∶ x * ∈ B ▵ }, then ⟨x * , x⟩ = f ▵▵ (x) [by (4.8)] = f (x) [by (4.9) when f is closed]. Hence x * ∈ ∂f (x) by (4.11).◻

. 23 )

 23 By the definition (4.19a) of B and (4.3) of the polar, the polar of B readsB ▵ = {x * ∈ E ∶ ⟨x * , c i ⟩ ⩽ 1 for all i ∈ I, ⟨x * , d j ⟩ ⩽ 0 for all j ∈ J}. (4.24) Propositions 4.2 and 4.3 have highlighted the prominent role played by the set S(x) of maximizers of ⟨⋅, x⟩ on B ▵ (see (4.13)), which with the form (4.24) of B ▵ now reads S(x) = arg max x * such that ⟨x * ,c i ⟩⩽1, ∀ i∈I ⟨x * ,d j ⟩⩽0, ∀ j∈J ⟨x * , x⟩. (4.25)

Lemma 4 . 4 (I

 44 elements of S(x) and ri S(x)) Let x ∈ E, S(x) be the set defined by (4.25), and x * be a point in B ▵ . Then 1) x * ∈ S(x) if and only if there exists (ᾱ, β) ∈ R

( 4 .

 4 [START_REF] Harchaoui | Conditional gradient algorithms for normregularized smooth convex optimization[END_REF] holds with x * ∶= A * ȳ, which is exactly (4.29). 2) By proposition 4.2, x ∈ ri Sol(P f ) if and only if there is some ȳ ∈ F such that A * ȳ is in the relative interior of the set S(x) defined by(4.25). By lemma 4.4, this is equivalent to the existence of (ᾱ, β, ȳ) ∈ RI + × R J + × F such that (4.27) holds with x * ∶= A * ȳ, which is exactly (4.30). ◻ Examples 4.8 1) Conditions (4.29) are equivalent to conditions (3.1) when the spaces E = R n and F = R m , both equipped with the Euclidean scalar product (x, y) ↦ x T y, and f is the ℓ 1 norm. Indeed, in that case, the set in (4.19a) is B = co{c ±1 , . . . , c ±n }, where c ±i = ±e i (4.31) (we have denoted by e i the ith vector of the canonical basis of R n ). The indices of the vector c i are therefore the elements of I = {-n, . . . , -1, 1, . . . , n} and J = ∅. This makes B the unit ball for the ℓ 1 norm. Let us now show that conditions (4.29) are equivalent to conditions (3.1).

Lemma 4 . 9 (

 49 aff S(x)) Let x ∈ E, S(x) be given by (4.25), and x * ∈ ri S(x). Then aff S(x) = x * + {u * ∈ E ∶ ⟨u * , c i ⟩ = 0 for i ∈ I + , ⟨u * , d j ⟩ = 0 for j ∈ J + },(4.32)

1 4 c 2 + 1 2 c 3 + 1 4 c 4

 4 . Then I + = {2, 3, 4} and one can indeed find a ȳ ∈ R 2 satisfying (4.33b), which now reads ȳ1 + ȳ2 = 1, ȳ1 = 1, and ȳ1 -ȳ2 = 1 and accepts ȳ = (1, 0) as feasible point.

1 )

 1 [b ∈ AD(R J + ) ⇐⇒ Dβ ∈ Sol(P f ) for some β ⩾ 0] If b ∈ AD(R J + ), then b = ADβfor some β ⩾ 0. Now Dβ is clearly feasible for (P f ) and f (Dβ) = 0 by (4.23), so that Dβ ∈ Sol(P f ). The converse implication is clear.

Proposition 4 .

 4 [START_REF] Cohen | Compressed sensing and best k-term approximation[END_REF] (no duality gap) Let f be the polyhedral gauge determined by(4.19). Then val(P f ) = val(D f ) and val(P ′ f ) = val(D ′ f ).

r

  If 0 < val(P f ) < +∞, then b ∈ A(R + B) ∖ AD(R J + ) by points 1 and 2 of proposition 4.13. Therefore val(D ′ f ) = val(P ′ f ) [proven above] = 1 val(P f ) [by point 3 of proposition 4.13], which is positive and finite by the assumption of the case. As a linear optimization problem with finite optimal value, (D ′ f ) has then a solution, say (ȳ ′ , s′ ), where s′ = val(D ′ f ) > 0. Since ȳ′ s′ satisfies the constraints of (D f ), one gets val(D f ) ⩾ ⟨b, ȳ′ s′ ⟩ = 1 s′ = 1 val(D ′ f ) = 1 val(P ′ f ) = val(P f ) [by point 3 of proposition 4.13]. ◻

  ) ri(A * (C)) = A * (ri C). (4.40) Proposition 4.16 (on the properties A * ȳ ∈ S(x) and A * ȳ ∈ ri S(x)) Let f be the polyhedral gauge determined by (4.19), x ∈ X , ȳ ∈ F, and S(x) be defined by (4.13). Then x ∈ Sol(P f ) and ȳ∈ Sol(D f ) ⇐⇒ A * ȳ ∈ S(x), (4.41a) x ∈ Sol(P f ) ⇒ A * (Sol(D f )) = S(x) ∩ R(A * ),(4.41b)x ∈ Sol(P f ) and(ri S(x)) ∩ R(A * ) ≠ ∅ ⇒ A * (ri Sol(D f )) = (ri S(x)) ∩ R(A * ),(4.41c)x ∈ ri Sol(P f ) andȳ ∈ ri Sol(D f ) ⇐⇒ A * ȳ ∈ ri S(x). (4.41d) Proof. [(4.41a) ⇒] If ȳ solves (D f ), it satisfies A * ȳ ∈ B ▵ [feasibility] and ⟨A * ȳ, x⟩ = ⟨ȳ, Ax⟩ = ⟨ȳ, b⟩ [x ∈ X ] = val(D f ) = f (x) [x ∈Sol(P f ) and no duality gap]. Hence A * ȳ ∈ S(x) by (4.11). [(4.41a) ⇐] If A * ȳ ∈ S(x) then x ∈ Sol(P f ) [(4.14)] and ȳ is feasible for(D f ) [S(x) ⊂ B ▵ ]. Now the objective of (D f ) takes at ȳ the value ⟨b, ȳ⟩ = ⟨x, A * ȳ⟩ [x ∈ X ] = f (x) [A * ȳ ∈ S(x),(4.12) and (4.11)] = val(P f ) [x ∈ Sol(P f )] ⩾ val(D f ) [weak duality]. Hence ȳ ∈ Sol(D f ). [(4.41b)] If ȳ ∈ Sol(D f ), then A * ȳ ∈ S(x) ∩ R(A * ) by (4.41a). Conversely an element of S(x) ∩ R(A * ) is of the form A * ȳ with A * ȳ ∈ S(x), hence ȳ ∈ Sol(D f ) by (4.41a) and A * ȳ ∈ A * (Sol(D f )).

  )where A ∶ E → R m is a linear map, b ∈ R m , and the inequality acts componentwise. Therefore, problem (4.42) reads ⎧ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎩ inf (x,s)∈E×R m f 0 (x) Ax + s = b s ⩾ 0.

( 4 .

 4 43) Now, this last problem can be written as a polyhedral gauge recovery problem in the standard form (P f ) given in the introduction of section 4, namely inf (x,s)∈E×R m f (x, s) Ax + s = b, (4.44) provided f is the Minkowski function associated with the following convex polyhedron containg the origin B 0 × cone{e 1 , . . . , e m } = B 0 × R m + ⊂ E × R m

† INRIA Paris, 2 rue Simone Iff, CS 42112, 75589 Paris Cedex 12, France. E-mail: Jean-Charles.Gil bert@inria.fr.