(1)

Theorem 1 For k 1, D k is not a closed set, and D k = {x ∈ Ê n , x 0 k} (denoting by the closure operator).

Proof 1

• D k is not a closed set: it is easy to find a sequence x j ∈ D k (j ∈ AE) whose limit is not in D k .

For instance, x j = (1/j) e, where e is a given vector in D k . x j tends towards 0 / ∈ D k .

• D k ⊆ {x ∈ Ê n , x 0 k}. If x ∈ D k , then there exists a sequence x j ∈ D k (j ∈ AE) whose limit is equal to x. Then, ∀ε > 0, ∃J, j J ⇒ ∀i, |x(i)x j (i)| < ε.

Applying this property with ε = min

x(i) =0
|x(i)|, we deduce that there exists an iteration J, such that ∀j J, ∀i, x(i) = 0 ⇒ x j (i) = 0. In other words, x 0 x j 0 = k.

• {x ∈ Ê n , x 0 k} ⊆ D k . Let us show that if x is such that x 0 k, then there exists a sequence

x j ∈ D k whose limit is equal to x. Given x, we define x j by setting x j (i) = x(i) if i ∈ A(x) (support of x), and by replacing the kx 0 first zero valued entries of x by 1/j in x j , and setting to 0 the remaining nk entries x j (i). Obviously, x j ∈ D k and this sequence tends towards x.

The consequence of theorem 1 is that arg min

x∈D k {E(x) = y -Ax 2 }
is not always defined, although the minimal value min x∈D k E(x) is defined. On the contrary, the set of minimizers

X c (k) = arg min x∈D k E(x) = arg min x 0 k E(x)
is properly defined because D k is a closed set and E is quadratic and convex (to be completed).

Example 1 Let us consider the minimization of x 2 over the domain D k . For k 1, there is no minimizer over D k , but the minimal cost min x∈D k

x 2 is equal to 0. The set of minimizers over D k is reduced to one vector:

X c (k) = {0}.
Example 2 The set X c (k) is not always a singleton. Let us consider the minimization of the 2D cost function 2 . It is easy to see that X c (0) = {0}, X c (1) = {[0, x(2)] T , x(2) ∈ Ê} and X c (2) = X c [START_REF] Gorodnitsky | Sparse signal reconstruction from limited data using FOCUSS: A reweighted minimum norm algorithm[END_REF].

E(x) = x(1)
Example 3 Let us consider the minimization of the 2D cost function E(x) = (x(1)α) 2 for a given α = 0. It is easy to see that X c (0

) = {0}, X c (1) = {[α, 0] T } and X c (2) = {[α, x(2)] T , x(2) ∈ Ê}.
Remark 1 Obviously, the sets D k have a nesting property (D k ⊂ D k+1 ), therefore, for all k, we have

∀x k ∈ X c (k), ∀x k+1 ∈ X c (k + 1), E(x k+1 ) E(x k ). Theorem 2 X c (k + 1) ∩ D k ⊆ X c (k). Proof 2 Let us consider x k+1 ∈ X c (k + 1) ∩ D k . Since D k ⊂ D k+1 and x k+1 is a minimizer of E over D k+1 , we have ∀x ∈ D k , E(x k+1 ) E(x). As x k+1 ∈ D k , x k+1 is a minimizer of E over D k .
2 Working assumptions and notion of constrained solution path

Unique representation property

We recall the definition of the unique representation property (URP), introduced in [START_REF] Gorodnitsky | Sparse signal reconstruction from limited data using FOCUSS: A reweighted minimum norm algorithm[END_REF] in the underdetermined case (when m n):

Definition 1 A matrix A of size m × n (m n)
satisfies the URP if and only if any selection of m columns of A forms a family of linearly independent vectors.

Under the URP assumption, we can solve y = Ax by imposing that x ∈ D m . The system is then equivalent to y = Bz where B is a matrix of size m × m extracted from A, and z is the corresponding vector extracted from x, of size m × 1. According to the URP definition, B is always invertible, and we can find sparse solutions to y = Ax with at most m non-zero entries (z = B -1 y and then x = {z, 0} for all the possible extractions B from A).

When m > n, we adopt the following definition:

Definition 2 A matrix A of size m × n (m > n) satisfies the URP if and only if it is full rank.
When m > n, there is generally no solution to y = Ax but the minimizer of E(x) over Ê n is unique (although not necessarily sparse):

X c (n) = {(A T A) -1 A T y}.
In the following, we will assume that y = 0 and that A satisfies the URP.

Cardinality of the set X c (k)

Theorem 3 For k min(m, n), the set X c (k) is finite under the URP assumption.

Proof 3 Because of the URP assumption, any selection of k min(m, n) columns of A yields a matrix B of size m × k whose rank is equal to k. Then, the energy reduces to E(x) = E(z; 0) = y -Bz 2 (where z ∈ Ê k ), and there is only one minimizer of z → E(z; 0) over Ê k . Since the number of possible selections of k columns of A is finite, the set X c (k) is finite.

Remark 2

The minimal value of E(x) (for x ∈ Ê n ) can be reached when minimizing E over D min(m,n) . Thus, when m n, it is not necessary to compute X c (k) for k > m. According to theorem 3, when m > n, all the sets X c (k), k = 0, . . . , n are finite.

Theorem 4 When m n and k is such that m < k n, the set X c (k) is of infinite cardinality.

Proof 4 Given a solution x m ∈ X c (m), let A(x m ) be the support of x m . We consider a support B of cardinality k such that A(x m ) ⊂ B ⊆ {1, . . . , n}, and we extract from A the matrix B of size m × k formed of the columns a i of A (i ∈ B). Then, let us add to x m a vector n belonging to the null space of B. Clearly,

x m + n ∈ X c (k) because x m + n 0 k and E(x m + n) = E(x m ) = min x∈Ê n E(x). Since the null space of B is of dimension k -m > 0, X c (k) is of infinite cardinality.
As a conclusion, the constrained solution path is defined in the following way, for any case (m n or m > n).

Definition 3

The constrained solution path is the (finite) set

X c = min(m,n) k=0 X c (k).
3 Properties of the penalized solution path

Penalized solution path

For a given λ 0, we define the set of minimizers of J (x; λ) = E(x) + λ x 0 :

X p (λ) = arg min x∈Ê n {J (x; λ)}.
By extension, we define X p (+∞) = {0}.

Definition 4 We denote the cardinality of a set A ⊆ {1, . . . , n} by

A 0 Card(A).
Definition 5 We denote by A(x) ⊆ {1, . . . , n} the support of a vector x ∈ Ê n .

Definition 6 For a given active set A such that A 0 min(m, n), the corresponding least-square solution is unique (due to the URP assumption). We denote this solution by

x A arg min A(x)⊆A E(x) (2)
and the corresponding least-square cost by

E A E(x A ) = min A(x)⊆A E(x). (3)
Finally, we define the corresponding value of J by

J A (λ) J (x A ; λ) = E A + λ x A 0 (4)
which is generally different from min A(x)⊆A J (x; λ).

Theorem 5 If λ > 0 and x p (λ) ∈ X p (λ), then the support of x p (λ), denoted by A A(x p (λ)) for convenience, is such that A 0 min(m, n), and x p (λ) = x A .

Proof 5 -First, we show that x p (λ) ∈ arg min

{x∈Ê n , A(x)⊆A} E(x).
Since x p (λ) is a minimizer of J (x; λ), the following equivalent inequalities hold for all x such that A(x) ⊆ A:

J (x; λ) J (x p (λ); λ) E(x) + λ x 0 E(x p (λ)) + λ A 0 E(x) -E(x p (λ)) λ A 0 -x 0 0.
We finally deduce that x p (λ) is a minimizer of E over the set {x ∈ Ê n , A(x) ⊆ A}.

-The case where A 0 > min(m, n) never occurs. If it does, remark 2 shows that there exists x ∈ D min(m,n) such that E(x) = E(x p (λ)). Since x 0 min(m, n) < x p (λ) 0 = A 0 , J (x; λ) < J (x p (λ); λ), which is in contradiction with x p (λ) ∈ X p (λ).

Finally, A 0 min(m, n) and there is only one minimizer of E over the set {x ∈ Ê n , A(x) ⊆ A} (URP assumption), which is x A .

Corrolary 1 If λ > 0, the set X p (λ) is finite and X p (λ) ⊆ D min(m,n) .
Proof 6 There are at most

min(m,n) k=0 C k n distinct values x p (λ) (i.e., min(m,n) k=0
C k n sets which are candidate to be a set A and one optimal x-value x A per set), which shows that X p (λ) is a finite set. Additionally, we have seen in theorem 5 that for each solution x p (λ), x p (λ) 0 = A 0 min(m, n).

Definition 7

The penalized solution path is defined as the union of sets

X p = λ>0 X p (λ).
Imposing λ > 0 (rather than λ 0) guarantees that X p (λ) is of finite cardinality for all λ. Moreover, it is easy to see (from theorem 5) that the solution path is of finite cardinality, since all the sets X p (λ) are included in a common set of cardinality

min(m,n) k=0 C k n : x ∈ Ê n , ∃A ⊆ {1, . . . , n}, A 0 min(m, n) and x = x A .

Piecewise constant property

Theorem 6 The dependence of the set

X p (λ) w.r.t. λ (λ > 0) is piecewise constant, with a finite number of intervals (λ ⋆ i , λ ⋆ i+1 ): for all i, X p (λ) is constant for λ ∈ (λ ⋆ i , λ ⋆ i+1 ) and if λ ∈ (λ ⋆ i , λ ⋆ i+1 ), then X p (λ) ⊆ X p (λ ⋆ i ) ∩ X p (λ ⋆ i+1
). The minimal cost value J (λ) min x∈Ê n J (x; λ) is a continuous and piecewise linear function of λ, and

∀λ, J (λ) = min {A⊆{1,...,n}, A 0 min(m,n)} J A (λ). ( 5
)
Definition 8 In the following, we will define the values λ = λ ⋆ i (i = 1, . . . , I) as the critical values. These values, together with λ ⋆ 0 = 0 and λ ⋆ I+1 = +∞, define the piecewise constant domain X p (λ):

0 = λ ⋆ 0 < λ ⋆ 1 < . . . < λ ⋆ I < λ ⋆ I+1 = +∞. (6)
λ ⋆ i are also the λ-values at which the derivative of J is changing: at λ = λ ⋆ i , λ → J (λ) is not differentiable, and J is linear on each interval [λ ⋆ i , λ ⋆ i+1 ] (see Fig. 1).

Proof 7 -The result (5) can be illustrated geometrically, by considering the affine curves λ → J A (λ) for all the possible supports A such that A 0 min(m, n) (see Fig. 1). Let us prove that (5) holds. When λ is fixed, let x p (λ) ∈ X p (λ), and let A A(x p (λ)).

• According to theorem 5,

x p (λ) 0 = A 0 min(m, n) and x p (λ) = x A . Thus, E(x p (λ)) = E A and J (x p (λ); λ) = J A (λ). • x p (λ) ∈ X p (λ) implies that for all A ′ ⊆ {1, . . . , n} such that A ′ 0 min(m, n), J (x p (λ); λ) J A ′ (λ) = J (x A ′ ; λ).
Here, we have shown that (5) holds since J (λ) = J (x p (λ); λ).

-λ → J (λ) is a continuous and piecewise linear function of λ because of (5). Since the number of affine curves λ

→ J A (λ) is finite, λ → J (λ) is described by a finite set of values {(λ ⋆ i , E Ai , x Ai 0 ), i = 0, . . . , I}, where λ ⋆ 0 = 0 < λ ⋆ 1 < . . . < λ ⋆ I < λ ⋆ I+1 = +∞. Each value λ ⋆ i (i = 1, .
. . , I) corresponds to the intersection between a pair of affine curves (see Fig. 1), and the restriction of J to a given interval

[λ ⋆ i , λ ⋆ i+1 ] is linear: ∀λ ∈ [λ ⋆ i , λ ⋆ i+1 ], J (λ) = E Ai + λ x Ai 0 . (7)
In particular, for i = 0, we have

∀λ ∈ [0, λ 1 ], J (λ) = E A0 + λ x A0 0 , (8)
where E A0 = min x∈Ê n E(x) is the minimal least-square error, and x A0 0 is the minimal L0-norm of the minimizers of E over Ê n . For i = I, we have necessarily x AI = 0 and

E AI = y 2 , thus ∀λ ∈ [λ ⋆ I , +∞), J (λ) = y 2 . (9) -For a given interval [λ ⋆ i , λ ⋆ i+1 ], let us show that when λ ∈ (λ ⋆ i , λ ⋆ i+1 ), X p (λ) is a constant set.
For some given λ-value ∈ (λ ⋆ i , λ ⋆ i+1 ), we consider x ∈ X p (λ), then necessarily, the following equivalent equations hold:

J (λ) = J (x; λ) E Ai + λ x Ai 0 = E(x) + λ x 0 .
Imagine that E Ai = E(x), then, necessarily, the two functions

J (λ ′ ) = E Ai + λ ′ x Ai 0 and J (x; λ ′ ) = E(x) + λ ′ x 0 do not coincide for λ ′ ∈ [λ ⋆ i , λ ⋆ i+1 ]\{λ}. Moreover, J (x; λ ′ ) is strictly lower than J (λ ′ ) either for λ ′ ∈ [λ ⋆ i , λ) or for λ ′ ∈ (λ, λ ⋆ i+1 ]
. This is in contradiction with (7) and the definition of J (λ ′ ) in theorem 6. We have shown that E Ai = E(x). Since J (λ) = J (x; λ) and λ > 0, we deduce that x Ai 0 = x 0 , and

that ∀λ ′ ∈ [λ ⋆ i , λ ⋆ i+1 ], J (λ ′ ) = J (x; λ ′ ). Finally, if λ ∈ (λ ⋆ i , λ ⋆ i+1 ) and x ∈ X p (λ), then x ∈ X p (λ ′ ) for all λ ′ ∈ [λ ⋆ i , λ ⋆ i+1 ]. X p (λ) is then a constant set when λ ∈ (λ ⋆ i , λ ⋆ i+1 ), and X p (λ) ⊆ X p (λ ⋆ i ) ∩ X p (λ ⋆ i+1 ).
Lemma 1 The function λ → J (λ) is increasing and concave.

Proof 8 J is an increasing and concave function as the minimum of a finite set of increasing and concave functions.

Lemma 2 X p (0) ∩ X p = ∅, and if m n, then X p (0) ⊂ X p .

Proof 9 The application of the result of theorem 6: "for all i,

if λ ∈ (λ ⋆ i , λ ⋆ i+1 ), then X p (λ) ⊆ X p (λ ⋆ i )" with i = 0 yields ∀λ ∈ (0, λ ⋆ 1 ), X p (λ) ⊆ X p (0)
. Thus, we always have X p (0)∩X p = ∅. For m n, X p (0) is formed of only one vector, thus ∀λ ∈ (0, λ ⋆ 1 ), X p (λ) = X p (0), and X p (0) ⊆ X p . Since y = 0 and A is full rank, the domain (6) is formed of at least two intervals (I 1), thus X p (0) ⊂ X p .

Theorem 7 For a given λ-value which is distinct from λ ⋆ 0 , λ ⋆ 1 , . . . , λ ⋆ I , all the elements of X p (λ) are of same L0-norm, which is equal to the derivative of J (λ), and yield the same least-square cost.

Proof 10 Because of theorem 6, for a given value of i, there exists A i ⊆ {1, . . . , n} such that

∀λ ′ ∈ [λ ⋆ i , λ ⋆ i+1 ], J (λ ′ ) = J Ai (λ ′ ). ( 10
)
Now, let us fix the value of λ ∈ (λ ⋆ i , λ ⋆ i+1 ) and let x p (λ) ∈ X p (λ). Because of theorem 6, X p (λ ′ ) is constant for

λ ′ ∈ (λ ⋆ i , λ ⋆ i+1 ), and x p (λ) ∈ X p (λ ′ ) for all λ ′ ∈ [λ ⋆ i , λ ⋆ i+1 ]. (10) implies that ∀λ ′ ∈ [λ ⋆ i , λ ⋆ i+1 ], J (x p (λ); λ ′ ) = J Ai (λ ′ ) ∀λ ′ ∈ [λ ⋆ i , λ ⋆ i+1 ], E(x p (λ)) + λ ′ x p (λ) 0 = E Ai + λ ′ x Ai 0 . (11)
Taking the derivative of (11) yields x p (λ) 0 = x Ai 0 = J ′ (λ), and then, due to (11), E(x p (λ)) = E Ai .

Theorem 8 Let x p (λ) be a sequence such that ∀λ, x p (λ) ∈ X p (λ). Then, necessarily, x p (λ) 0 is a decreasing function of λ, and E(x p (λ)) is an increasing function of λ.

Proof 11

• Recall that for i ∈ {0, . . . , I}, there exists a set

A i such that if λ ∈ (λ ⋆ i , λ ⋆ i+1 ) and x p (λ) ∈ X p (λ), then x p (λ) 0 = x Ai 0 (see theorem 7);
• The first result is a direct consequence of theorem 7: ∀λ / ∈ {λ ⋆ 0 , . . . , λ ⋆ I }, x p (λ) 0 = J ′ (λ), and of lemma 1: J is a concave function, thus its derivative (when it is defined) is a decreasing function of λ. At this point, we know that λ → x p (λ) 0 is piecewise constant on Ê + , and that its restriction to Ê + \{λ ⋆ 0 , . . . , λ ⋆ I } is decreasing: ∀i ∈ {1, . . . , I}, x Ai-1 0

x Ai 0 . The remaining part is to study the behavior of x p (λ) 0 at λ = λ ⋆ i , i = 0, . . . , I. For i ∈ {1, . . . , I}, let us show that

x p (λ ⋆ i ) is such that x Ai-1 0 x p (λ ⋆ i ) 0 x Ai 0 : -λ → J (x p (λ ⋆ i ); λ) and λ → J (λ) coincide at λ = λ ⋆ i ; -J ′ (λ) is equal to x Ai-1 0 when λ ∈ (λ ⋆ i-1 , λ ⋆ i ), and to x Ai 0 when λ ∈ (λ ⋆ i , λ ⋆ i+1 ). -the derivative of λ → J (x p (λ ⋆ i ); λ) is equal to x p (λ ⋆ i ) 0 .
Due to the definition of λ → J (λ) in theorem 6, the affine function λ → J (x p (λ ⋆ i ); λ) is necessarily greater or equal to λ → J (λ) for λ ∈ (λ ⋆ i-1 , λ ⋆ i ) and for λ ∈ (λ ⋆ i , λ ⋆ i+1 ). This implies that x Ai-1 0 x p (λ ⋆ i ) 0 x Ai 0 .

A similar argument can be given to show that x p (λ ⋆ 0 ) 0 x A0 0 .

Finally, we have shown that λ → x p (λ) 0 is decreasing on Ê + .

• Second result: for a given i ∈ {1, . . . , I}, the continuity of

J at λ = λ ⋆ i reads E Ai-1 + λ ⋆ i x Ai-1 0 = E Ai + λ ⋆ i x Ai 0 . Because x Ai-1 0 x Ai 0 , E Ai-1 E Ai .
When λ varies from 0 to +∞ and λ / ∈ {λ ⋆ 1 , . . . , λ ⋆ I }, E(x p (λ)) takes sequentially the values E Ai , i = 0, . . . , I.

Thus, the restriction of λ → E(x p (λ)) to Ê + \{λ ⋆ 1 , . . . , λ ⋆ I } is increasing. With similar arguments than in the first result, we can show that for i ∈ {1, . . . , I},

E Ai-1 E(x p (λ ⋆ i )) E Ai . Finally, λ → E(x p (λ)) is increasing on Ê + .

Cardinality of X p (λ)

It is easy to see that:

• For all i ∈ {1, . . . , I}, the cardinality of X p (λ ⋆ i ) is larger than 2, because at λ = λ ⋆ i , at least two distinct affine curves λ → J A (λ) = E A + λ x A 0 intersect (see Fig. 2).

• X p (λ) is reduced to the unique vector 0 for the largest λ-values (λ > λ ⋆ I ⇒ X p (λ) = {0}). • For λ = 0 (the least-square error E(x) is minimized with no penalty), X p (0) is either reduced to the unique vector (A T A) -1 A T y when m n, or is of infinite cardinality otherwise.

We conclude that at least for m n, the cardinality of X p (λ) is not monotonic w.r.t. λ.

Relationship between the constrained and the penalized solution paths

Generally, the solution paths X c and X p do not coincide. This is a consequence of the non-convexity of the L0-norm [START_REF] Das | A closer look at drawbacks of minimizing weighted sums of objectives for Pareto set generation in multicriteria optimization problems[END_REF]. However, X p ⊆ X c is always true (a well-known result in the literature of multi-objective optimization?). In general, the proposition "∀k, ∃λ, X c (k) ⊆ X p (λ)" is false (see Fig. 1).

Theorem 9 If λ = {λ ⋆ 0 , . . . , λ ⋆ I }, then there exists k such that X p (λ) = X c (k).

Proof 12 For a given λ-value, let x ∈ X p (λ), let A A(x) denote the support of x and k x x 0 = A 0 . According to theorem 5, A 0 min(m, n) and x

= x A . -Let us show that x ∈ X c (k x ). If x / ∈ X c (k x ), there exists a (minimal) support B such that B 0 k x and E B < E(x) = E A , then J (x B ; λ) < J (x A ; λ). This is in contradiction with x ∈ X p (λ).
At this point, we have shown that

∀λ, ∀x ∈ X p (λ), ∃k x , x ∈ X c (k x ), or equivalently, X p ⊆ X c .
-The following of the proof requires the assumption λ = {λ ⋆ 0 , . . . , λ ⋆ I }. We have seen that if x and y ∈ X p (λ), then x ∈ X c (k x ) and y ∈ X c (k y ). According to theorem 7, all the elements of X p (λ) are of same L0-norm. Therefore, k y = k x . At this point, we have shown that

∀λ = {λ ⋆ 0 , . . . , λ ⋆ I }, ∃k λ , X p (λ) ⊆ X c (k λ ).
λ * 2 λ * 1 E A2 E B E A1 E A0 λ A 2 A 0 B A 1 J A (λ) A ′ 1 E A ′ 1
Figure 1: Representation of the affine curves λ → J A (λ) = E A + λ x A 0 for all the possible supports A such that A 0 min(m, n). Note that a given affine curve may correspond to several supports A and B for which ∀λ, J A (λ) = J B (λ). The piecewise linear function λ → J (λ) is defined according to (5) and is represented in bold lines. From this illustration, let us comment on the nonequivalence of both solution paths X c and X p . By following the bold curve representing λ → J (λ), we see that the penalized solution path is described by the active sets A 0 , A 1 and A 2 (and the possible other sets yielding the same three curves λ → J Ai (λ)) for which x A 0 is equal to 3, 2 and 0, respectively. A ′ 1 is an active set such that

x A ′ 1 0 = 2 but E A ′ 1 > E A1 .
No active set such that x A 0 = 1 is present in X p . B is the active set such that x B 0 = 1 whose energy E B is the lowest among all the active sets such that x A 0 1, however, ∀λ, J B (λ) > J (λ). Thus, X c (1) = {x B } ⊂ X p . On the contrary, for all λ = {λ ⋆ 0 , . . . , λ ⋆ I }, X p (λ) = X c (k λ ), with k λ = J ′ (λ) = 3, 2 or 0.

λ * 2 λ * 1 E A2 E B E A1 E A0 λ A 2 A 0 B J A (λ) A 1 Figure 2: Content of X p (λ) at a critical λ-value λ = λ ⋆ i , i 1: X p (λ ⋆ i ) ⊂ X c , and Card(X p (λ ⋆ i )) 2. On this example, X p (λ ⋆ 2 ) = X c (0) ∪ X c (1) ∪ X c (2) and Card(X p (λ ⋆ 2 )) 3 since x A1 , x A2 and x B ∈ X p (λ ⋆ 2 ).
-Now, let us prove the reverse inclusion. Given λ, there exists at least one x such that x ∈ X p (λ), k λ = x 0 and x ∈ X c (k λ ). For all y ∈ X c (k λ ), we have necessarily E(y) = E(x) and y 0 x 0 , thus J (y; λ) J (x; λ). Since x ∈ X p (λ), we deduce that J (y; λ) = J (x; λ) and that y ∈ X p (λ). This completes the proof, since we have shown that ∀λ = {λ ⋆ 0 , . . . , λ ⋆ I }, X c (k λ ) ⊆ X p (λ). Actually, k λ = J ′ (λ) according to theorem 7.

Content of X p (λ) at critical λ-values

Lemma 3 If λ ⋆ i-1 < λ < λ ⋆ i < λ ′ < λ ⋆ i+1 , then X p (λ) ∩ X p (λ ′ ) = ∅.
Proof 13 According to theorem 7, all the vectors of X p (λ) (respectively of X p (λ ′ )) are of same L0-norm, which is the derivative of J at λ (resp. λ ′ ). Thus, if

X p (λ) ∩ X p (λ ′ ) = ∅, the derivative of J is constant on (λ ⋆ i-1 , λ ⋆ i+1 )\{λ ⋆ i },
which is in contradiction with the definition of λ ⋆ i (critical point, at which the derivative of J is changing).

Theorem 10 If λ ⋆ i-1 < λ < λ ⋆ i < λ ′ < λ ⋆ i+1 , then X p (λ)∪X p (λ ′ ) ⊆ X p (λ ⋆ i ), thus Card(X p (λ))+Card(X p (λ ′ )) Card(X p (λ ⋆ i )) (Card denotes the cardinality). If λ ∈ (λ ⋆ i-1 , λ ⋆ i+1 )\{λ ⋆ i }, then Card(X p (λ)) < Card(X p (λ ⋆ i )).
See illustration in Fig. 2.

Proof 14

• First result: according to theorem 6, if λ ∈ (λ ⋆ i , λ ⋆ i+1 ), then X p (λ) ⊆ X p (λ ⋆ i ) ∩ X p (λ ⋆ i+1 ). According to lemma 3, if λ ⋆ i-1 < λ < λ ⋆ i < λ ′ < λ ⋆ i+1 , then X p (λ) ∩ X p (λ ′ ) = ∅. Thus, X p (λ) ∪ X p (λ ′ ) ⊆ X p (λ ⋆ i ) and Card(X p (λ)) + Card(X p (λ ′ )) Card(X p (λ ⋆ i )). • Second result: since neither X p (λ) nor X p (λ ′ ) is empty, their cardinality is larger or equal to 1, then, applying Card(X p (λ)) + Card(X p (λ ′ )) Card(X p (λ ⋆ i )), we deduce that Card(X p (λ)) < Card(X p (λ ⋆ i )) and Card(X p (λ ′ )) < Card(X p (λ ⋆ i )).

SBR and CSBR algorithms 4.1 SBR iterates and output

Let us consider the SBR algorithm for a given λ-value. An SBR iterate takes the form of:

• an active set A (for simplicity, we omit the dependence w.r.t. λ);

• the corresponding least-square minimizer x A = arg min

{x∈Ê n , A(x)⊆A} E(x).
x(λ) x A is chosen as the estimator of a minimizer (there may be several) of

J (x; λ) = E(x) + λ x 0 over Ê n .
First, recall that for the SBR iterates (and in particular when SBR terminates), x A 0 = A 0 . This property can be guaranteed by including in the SBR loops a small procedure which removes from the active set A all the indices i ∈ A such that x A (i) = 0 (however, these removals rarely occur in practice). The following remark follows from this property.

Remark 3 For a given λ-value, the cost of an SBR iterate x A is J A (λ) = E A + λ A 0 . Because the cost of SBR iterates only depend on their support and for convenience, we will omit their dependence w.r.t. x.

Remark 4 SBR terminates after a finite number of iterations. Moreover, a set A cannot be explored twice while running SBR.

Proof 15 SBR is a descent algorithm and the number of sets A which are reachable is finite (i.e., the number of subsets of {1, . . . , n}).

Remark 5 When SBR terminates, the estimate x(λ) = x A is generally not included in X p (λ) because SBR is a sub-optimal algorithm. Remark 6 At the SBR output A, J is "locally minimum w.r.t. A": any replacement of A by A • i (where • ∪ or \) does not yield a decrease of the cost J A (λ)). Formally, this property reads: ∀i, J A (λ)

J A•i (λ), (12)
or equivalently,

∀i, E A + λ A 0 E A•i + λ x A•i 0 ∀i, E A -E A•i λ x A•i 0 -A 0 . (13)
Here, we do not consider the small removal procedure described above for A • i (update of A • i by removing the indices corresponding to the zero valued entries of x A•i ), therefore we use x A•i 0 , which may be lower than A • i 0 .

Iterative computation of λ in the CSBR algorithm

When λ = λ q > 0 (q-th call to SBR), let A = A q be the support of the output of SBR(λ q ). Then, (13) holds.

For simplicity, we will omit, when possible, the dependence of A w.r.t. q. When λ q is replaced by another value λ λ q and A = A q is kept fixed, for which λ-values does (13) remain valid? When • = \, both terms on the left-and right-hand sides of the inequality are strictly negative ( x A\i 0 A 0 -1), while when • = ∪, both terms are positive since E A -E A∪i 0 and (13) holds for λ = λ q (this implies that x A∪i 0 = A 0 or A 0 + 1). Therefore, (13) remains valid for λ = λ q if and only if

(0 ) max i / ∈A and xA∪i 0 = A 0+1 (E A -E A∪i ) λ min i∈A E A -E A\i x A\i 0 -A 0 . ( 14
)
The lower bound of ( 14) can be simplified to max

i / ∈A (E A -E A∪i ) because if i / ∈ A is such that x A∪i 0 = A 0 ,
then (13) implies that E A -E A∪i = 0. Thus, including these indices i in the computation of the lower bound of (14) does not change its value, and (14) simplifies to

max i / ∈A (E A -E A∪i ) λ min i∈A E A -E A\i x A\i 0 -A 0 . ( 15
)
Given λ q , the next λ-value λ q+1 < λ q is found by computing the lower bound of (15). How to choose λ q+1 ? Setting λ q+1 to the lower bound of (15) is not judicious, since for this λ-value, J is still "locally minimum w.r.t. A" in the sense of (12). One possibility is to set λ q+1 to the lower bound of (15) minus some ε > 0, without guarantee that this value is larger than the "next lower bound" of (15). Another possibility is to sort the of

λ i E A -E A∪i 0 ( 16
)
for all indices i / ∈ A, and then to set λ q+1 to the mean of the two largest values. This setting ensures that the inequality λ i λ q+1 does not hold for one value of λ i only.

• If the number of indices i / ∈ A such that λ i > 0 is equal to 1, then we set λ q+1 to half of the value of λ i .

• If all indices i / ∈ A are such that λ i = 0, then we terminate CSBR.

• If A is the complete set {1, . . . , n}, the lower bound of ( 15) is undefined, and we terminate CSBR.

Remark 7 For a given i / ∈ A for which x A∪i 0 = A 0 + 1, λ i is the λ-value for which both affine curves λ → J A (λ) and λ → J A∪i (λ) intersect. Similarly, for i ∈ A, the value

λ i E A -E A\i x A\i 0 -A 0 (17)
is the λ-value for which both affine curves λ → J A (λ) and λ → J A\i (λ) intersect.

Proof 16 For i / ∈ A and for the λ-value λ i , (13) is an equality, then J A (λ i ) = J A∪i (λ i ). Since x A∪i 0 is supposed to be different from A 0 , both affine curves λ → J A (λ) and λ → J A∪i (λ) are not parallel (their slopes are equal to A 0 and x A∪i 0 = A 0 + 1 respectively), and they intersect at λ = λ i . A similar proof holds in the case where i ∈ A and ∪ is replaced by \.

Remark 8 A set A of cardinality larger than min(m, n) cannot be explored.

Proof 17 -SBR: if a set A of cardinality larger than min(m, n) is explored, then SBR has earlier explored at least one set B of cardinality min(m, n) (recall that the initial solution is A = ∅). Due to the URP assumption, E B = E A = min x∈Ê n E(x) is the optimal least-square cost. Therefore, A 0 > B 0 ⇒ ∀λ > 0, J A (λ) > J B (λ). This cannot occur because SBR is a descent algorithm.

-CSBR. Recursively, for each λ = λ q , if the initial set A q-1 (input of SBR(λ q )) is of cardinality lower than min(m, n), then the output A q of SBR(λ q ) is also of cardinality lower than min(m, n).

Termination of CSBR

Remark 9 When CSBR terminates, E A = J A (0) is locally minimum w.r.t. A, then ∀i / ∈ A, E A∪i = E A .
Remark 10 CSBR terminates after a finite number of SBR iterations.

Proof 18

• According to remark 4, for a given λ-value λ q , SBR(λ q ) terminates after a finite number of iterations.

• According to remark 7, each value of λ q is such that there exists µ q and µ q such that A λ q ′ λ q λ J A (λ) Here, each vertical line corresponds to one call to SBR (A and A' are two SBR iterates at λ q and λ ′ q ), i.e., to a fixed λ-value while the plain lines are the affine curves λ → J A (λ) and λ → J A ′ (λ).

E A E A ′
-0 µ q λ q µ q ; -λ q = (µ q + µ q )/2; -µ q and µ q are critical values for which two affine curves λ → J A (λ) and λ → J A (λ ∪ i) intersect.

From the recursive construction of the sequence (λ q , q 0), it is clear that ∀q, µ q < λ q-1 , thus ∀q, µ q < µ q-1 . Since each value of µ q can be associated to a given intersection between two affine curves λ → J A (λ) and λ → J B (λ) and the number of possible subsets A and B of {1, . . . , n} whose cardinality is lower than min(m, n) is finite, the number of possible values taken by µ q is also finite. Since the sequence (µ q , q 0) satisfies ∀q, µ q < µ q-1 , we conclude that the number of iterations q at which SBR(λ q ) is run is finite.

Despite remark 10, we cannot claim that a given set A is never explored twice during the CSBR procedure. In remark 4, we have seen that a given set A can never be explored twice while running SBR for a given λ-value. However, A may be explored several times while running CSBR, i.e., once while running SBR at some λ-value λ q , and another time while running SBR at another λ-value λ q ′ λ q (for q ′ > q). See Fig. 3 for a simple illustration.

Remark 11 When CSBR terminates, the solution x A is an unconstrained least-square estimate.

Proof 19 Let us define the residual r = y -Ax A and the unit vectors e i ∈ Ê n in which all entries are equal to 0 except the i-th entry, equal to 1. Then, Ae i = a i , where a i stands for the i-th column of A.

Firstly, we prove that ∀i ∈ A, a T i r = 0. According to remark 9, A is such that ∀i / ∈ A, E A∪i = E A . Then, the following inequalities hold: ∀i / ∈ A, ∀ε ∈ Ê, E(x A + εe i ) -E(x A ) 0 ∀i / ∈ A, ∀ε ∈ Ê, rεa i 2r 2 0 ∀i / ∈ A, ∀ε ∈ Ê, ε 2 a i 2 -2εa T i r 0 ∀i / ∈ A, a T i r = 0.

  On the properties of the solution path of the constrained and penalized L2-L0 problems Junbo Duan * , Charles Soussen * , David Brie * , Jérôme Idier † * Centre de Recherche en Automatique de Nancy † Institut de Recherche en Communication et Cybernétique de Nantes February 23, 2009 1 Domain of optimization For k n, we define the domain D k ⊂ Ê n : D k = {x ∈ Ê n , x 0 = k}.

3. 4

 4 Relationship between the constrained and the penalized solution paths 3 PROPERTIES OF THE PENALIZED SOLUTION PATH 6 -. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3. 5

 5 Content of X p (λ) at critical λ-values 3 PROPERTIES OF THE PENALIZED SOLUTION PATH 6 -. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A A ′

Figure 3 :

 3 Figure3: A given set A may be explored twice during the CSBR procedure, at different λ-values. Here, each vertical line corresponds to one call to SBR (A and A' are two SBR iterates at λ q and λ ′ q ), i.e., to a fixed λ-value while the plain lines are the affine curves λ → J A (λ) and λ → J A ′ (λ).

Secondly, because x A is a solution to the constrained problem (2):

Finally, we deduce that ∀i ∈ {1, . . . , n}, a T i r = 0

Since E is quadratic, we have shown that x A is an unconstrained least-square estimate.