Axel Flinth

Frédéric De Gournay

Pierre Weiss

Grid is Good: Adaptive Refinement Algorithms for Off-the-Grid Total Variation Minimization

We propose an adaptive refinement algorithm to solve total variation regularized measure optimization problems. The method iteratively constructs dyadic partitions of the unit cube based on i) the resolution of discretized dual problems and ii) on the detection of cells containing points that violate the dual constraints. The detection is based on upper-bounds on the dual certificate, in the spirit of branch-and-bound methods. The interest of this approach is that it avoids the use of heuristic approaches to find the maximizers of dual certificates. We prove the convergence of this approach under mild hypotheses and a linear convergence rate under additional non-degeneracy assumptions. These results are confirmed by simple numerical experiments. 1

Introduction

We develop and analyze an algorithm to solve the following problem: inf µ∈M(Ω)

J(µ)

def.

= µ M + f (Aµ), (P(Ω))

where Ω ⊂ R D is a compact domain, M(Ω) is the set of Radon measures on Ω, A : M(Ω) → R M is a continuous operator, • M is the total variation and f : R M → R ∪ {+∞} is a convex, proper function. A key property of this problem is that it admits sparse solutions (see e.g. [START_REF] Boyer | On Representer Theorems and Convex Regularization[END_REF]) of the form

µ = S s=1 α s δ x s ,
where α s ∈ R are weights, x s ∈ Ω are locations and where the number of sources S satisfies S ≤ M . This feature shows that a finite dimensional problem is somewhat hidden in (P(Ω)). It makes it possible to design specific and efficient numerical procedures, for the challenging measure optimization problem P(Ω).

Applications This problem and its variants appear in various fields. In inverse problems, it is used heavily for sparse source localization and super-resolution [START_REF] De | Exact reconstruction using Beurling minimal extrapolation[END_REF][START_REF] Bredies | Inverse problems in spaces of measures[END_REF][START_REF] Tang | Compressed sensing off the grid[END_REF][START_REF] Emmanuel | Towards a Mathematical Theory of Super-resolution[END_REF][START_REF] Duval | Exact support recovery for sparse spikes deconvolution[END_REF]. It is also used in optimal control with sparse controls [START_REF] Clason | A measure space approach to optimal source placement[END_REF][START_REF] Kunisch | Optimal control of the undamped linear wave equation with measure valued controls[END_REF]. In approximation theory, a "generalized" version of this problem was revisited recently in [START_REF] Unser | Splines Are Universal Solutions of Linear Inverse Problems with Generalized TV Regularization[END_REF]. Given a surjective Fredholm operator L : B(Ω) → M(Ω), where B(Ω) is a suitably defined Banach space, consider the following problem: inf u∈B(Ω)

Lu M + f (Au). (1)
The solutions of this problem are (generalized) splines with free knots [START_REF] Unser | Splines Are Universal Solutions of Linear Inverse Problems with Generalized TV Regularization[END_REF]. Following [START_REF] Flinth | Exact solutions of infinite dimensional total-variation regularized problems[END_REF] and letting L + denote a pseudo-inverse of L, this problem can be rephrased as inf µ∈M(Ω) u K ∈ker(L)

µ M + f (A(L + µ + u K )), (2)
which is an instance of (P(Ω)).

Exchange algorithms In this work, we will introduce and study a variant of an exchange algorithm. To explain its principle, let us introduce the dual problem (D(Ω)) to (P(Ω)):

sup q∈R M A * q L ∞ (Ω) ≤1 -f * (q), (D(Ω))
where A * q L ∞ (Ω)

def.

= sup x∈Ω |A * q|(x). This dual formulation will play a pivotal role in our analysis. It involves the optimization of a finite dimensional variable q ∈ R M , subject to an infinite number of linear constraints {|A * q(x)| ≤ 1, ∀x ∈ Ω}. It is therefore called a semi-infinite program [START_REF] Hettich | Semi-infinite programming: theory, methods, and applications[END_REF][START_REF] Reemtsen | Numerical methods for semi-infinite programming: A survey[END_REF][START_REF] Hettich | A review of numerical methods for semi-infinite optimization[END_REF]. The first algorithm proposed to tackle it is usually attributed to Remez and his exchange algorithm [START_REF] Remez | Sur la détermination des polynômes d'approximation de degré donnée[END_REF]. It dates back to the 1930's and was adapted to a specific problem of the form P(Ω). The general idea is to define a sequence of discretization sets (V k ) k∈N , where V k is a finite set of points (vertices) in Ω. We can then define the discretized primal and dual problems as follows inf

µ∈M(V k ) µ M + f (Aµ) (P(V k )) sup q∈R M A * q L ∞ (V k ) ≤1 -f * (q). (D(V k ))
Both problems are finite dimensional convex problem, and can be solved with off-the-shelf solvers. The simplest approach is to define V k as a Euclidean grid with edge-length 2 -k [START_REF] Tang | Sparse recovery over continuous dictionariesjust discretize[END_REF][START_REF] Debarre | TV-based Spline Reconstruction with Fourier Measurements: Uniqueness and Convergence of Grid-Based Methods[END_REF]. Proving the convergence of this approach is rather straightforward. A problem however is the numerical complexity which explodes rapidly while k increases.

A lighter adaptive method consists in using the dual variable q k to construct V k+1 . It satisfies |A * q k |(x) ≤ 1 for x ∈ V k by construction. However, there may exist locations x ∈ Ω \ V k with |A * q k |(x) > 1. Such points are candidates to be added to V k+1 . Perhaps the most popular approach in this class is the Frank-Wolfe [START_REF] Frank | An algorithm for quadratic programming[END_REF] approach. It consists in adding only the global maximizer of |A * q k | at each step. It is described precisely in Algorithm 1. It was revived in signal processing thanks to Bredies et al in [START_REF] Bredies | Inverse problems in spaces of measures[END_REF]. Its connection with the exchange Algorithm 1 The Frank-Wolfe Algorithm 1: Input:

• Initial discretization set V 0 , set k = 0 2: WHILE a stopping criterion is not satisfied

3:
1) Determine a solution q k of D(V k ) 4:

2) Determine x k def.

= argmax x∈Ω |A * q k |(x).

5:

3) Set V k+1 = V k ∪ {x k }. 6: Output:

• The dual solution q k of (D(V k )).

algorithms was recalled in [START_REF] Eftekhari | Sparse inverse problems over measures: Equivalence of the conditional gradient and exchange methods[END_REF]. A linear convergence theory was developed independently by Walter and Pieper in [START_REF] Pieper | Linear convergence of accelerated conditional gradient algorithms in spaces of measures[END_REF] and by the authors in [START_REF] Flinth | On the linear convergence rates of exchange and continuous methods for total variation minimization[END_REF]. Despite nice theoretical properties, this approach suffers from one major issue, which is the main motivation for the present paper:

How can we find the maximizer x k def.

= argmax x∈Ω |A * q k |(x)?

This problem has no reason to be simple: it is nonconvex and depends highly on the properties of the linear forms a m . As far as we could judge, it is usually tackled with heuristics, which are often swept under the carpet. For instance, multiple gradient or Newton ascents are launched in parallel starting from a set of points covering Ω sufficiently finely. At the end of the process, the point with the largest value is then kept as an approximation of x k . Our experience is that tuning the hyper-parameters in this quest for the global minimizer is time consuming and can represent a real headache for the optimizer. The main objective of this paper is to tackle this issue, by looking for approximate, easily detectable maximizers only.

Alternative solvers Finally, let us mention that alternative algorithms with a different flavor are available.

A possibility is to use the Lasserre hierarchies, which are designed to solve near generic measure optimization problems [START_REF] Bernard | An introduction to polynomial and semi-algebraic optimization[END_REF][START_REF] De Castro | Exact solutions to Super Resolution on semi-algebraic domains in higher dimensions[END_REF]. They however scale poorly for large M and will not be considered further in this work.

Another possibility is to use continuous optimization procedures. The idea is to parameterize the measure µ by the locations and weights of its masses. Given a number N ≥ M of particles, a set of locations X = (x 1 , . . . , x N ) in Ω N and a weight vector α ∈ R N , we can define the mapping µ(X, α)

def. = N n=1 α n δ xn .
Plugging it in the primal problem P(Ω), we obtain the following non-convex, finite dimensional problem inf

X∈Ω N α∈R N α 1 + f (Aµ(X, α)). (3)
It can be solved with continuous optimization routines such as proximal gradient descents. The difficulty with this type of approach is the initialization: how to set the number N of particles, their locations and weights? A possibility is to discretize the domain Ω finely. A nice global convergence theory has then been developed in [START_REF] Chizat | On the global convergence of gradient descent for over-parameterized models using optimal transport[END_REF][START_REF] Chizat | Sparse optimization on measures with over-parameterized gradient descent[END_REF]. The price to pay is a large number of variables N M . This is somewhat unsatisfactory since we know in advance that a solution supported on at most M points exists. A possibility to avoid this pitfall consists in using an exchange algorithm to find an approximate solution to P(Ω), and then fine-tune it with a continuous optimization routine on [START_REF] Borwein | Partially finite convex programming, Part I: Quasi relative interiors and duality theory[END_REF]. It now possesses a rich convergence theory [START_REF] Traonmilin | The basins of attraction of the global minimizers of the non-convex sparse spike estimation problem[END_REF][START_REF] Flinth | On the linear convergence rates of exchange and continuous methods for total variation minimization[END_REF]. It can be used in conjunction with the algorithm proposed in this work. A variant of this approach is to launch the continuous optimization technique after every step in the Frank-Wolfe algorithm, and not only use it to fine-tune in the end. This approach was introduced and coined the sliding Frank-Wolfe algorithm in [START_REF] Denoyelle | The sliding frank-wolfe algorithm and its application to super-resolution microscopy[END_REF].

Preliminaries

We will work on the domain Ω = [0, 1] D for simplicity. This is not a real restriction, since we can fit any compact domain of R D to Ω = [0, 1] d using a non-degenerate affine transformation. Using this map, we may push forward measurement functions and measures, in a bijective fashion. We let M(Ω) denote the space of Radon measures of bounded total variation on Ω and C 0 (Ω) the space of continuous functions on Ω vanishing on the boundary. Note that if we equip M(Ω) with the total variation norm • M and C 0 (Ω) with the supremum norm, M(Ω) can be identified with the dual of C 0 (Ω). For a subset ω of R D , we let vol(ω) denote its volume (or Lebesgue measure). The notation 1, N indicates the set of integers from 1 to N . The relation f g indicates that f is dominated by g up to positive multiplicative constant. The relation f g indicates that f and g are equivalent, i.e. that there exists two constants 0 < c 1 ≤ c 2 such that c 1 g ≤ f ≤ c 2 g.

Cells and cell partitions

The proposed algorithms rely on the use of 2 D -trees. We iteratively partition hypercubes in 2 D equal parts. For instance, we will use binary trees in 1D, quadtrees in 2D, and octrees in 3D. Let us define some objects. Definition 1 (Cells, vertices, edge-length). We call a subset ω ⊆ [0, 1] a dyadic cell (or simply a cell) if it is of the form

ω = x + 2 -J • [0, 1] d ,
where J is a non-negative integer and x ∈ (2 -J • 0, 1, . . . , 2 J -1 ) d . For a cell ω, we let vert(ω) denote its vertices and |ω| denote its edge-length.

Definition 2 (Cell partition). A cell partition Ω k is a collection of cells such that Ω = ∪ ω∈Ω k ω and vol(ω ∩ω) = 0 for all ω, ω ∈ Ω k with ω = ω . That is to say, two cells in Ω k can only have faces in common.

Measurement operator

Throughout the paper, we will work under the following assumption.

Assumption 1 (Continuous operator). The operator A : M(Ω) → R M is weak- * -continuous. Equivalently, the measurement functionals a * m defined by a * m , µ = (A(µ)) m are given for all µ ∈ M(Ω) by

a * m , µ = Ω a m dµ,
for functions a m ∈ C 0 (Ω).

Given q ∈ R M , A * q = M m=1 q m a m is a continuous function. Assuming than a m ∈ C r (Ω), we let (A * q) , (A * q) , (A * q) (r) denote its derivative, its Hessian and it r-th tensor derivative. We define the following constants κ r def.

= sup

q 2≤1 sup x∈Ω (A * q) (r) (x) 2→2 , (4)
where r indicates the derivative's order and where • 2→2 is the spectral norm.

Set distances

The "distance" between two sets X 1 and X 2 in R D is defined by dist(X 1 , X 2 )

def.

= inf

x1∈X1,x2∈X2

x 1 -x 2 2 .
Notice that dist is not a proper distance. In particular, it does not satisfy the triangle inequality. For a point x ∈ R D and a set X ⊂ R D , we will use the shorthand notation dist(x, X)

def.

= dist({x}, X).

The Hausdorff distance between X 1 and X 2 is defined by

dist H (X 1 |X 2 ) def. = sup x2∈X2 inf x1∈X1 x 1 -x 2 2 .
Notice that this distance is asymmetric: in general dist H (X

1 |X 2 ) = dist H (X 2 |X 1 )
. The following inequality will play an important role in the analysis.

Proposition 1 (Triangle inequality for set distances). For any triple of sets

X 1 , X 2 , X 3 in R D we have dist(X 1 , X 2 ) ≤ dist H (X 1 |X 3 ) + dist(X 3 , X 2 ). (5)

Primal, dual and existence

Our results will be established under the following assumptions on f and A.

Assumption 2 (A convexity assumption). The function f : R M → R ∪ {+∞} is a convex lower semi-continuous function with int(dom(f )) = ∅.

Assumption 3 (Coercivity). The functional J is coercive, meaning that J(µ) → ∞ when µ M(Ω) → ∞.

Notice that Assumption 3 is granted if f is lower-bounded. The following result relates the primal and the dual.

Proposition 2 (Existence and strong duality). Let V ⊆ Ω denote a subset of Ω. Assume that there exists µ ∈ M(Ω) supported on V with Aµ ∈ int(dom(f )). Then, under Assumptions 1, 2 and 3, the following statements hold true:

• The primal problem (P(V)) has a nonempty set of solutions, bounded in total variation norm.

• The dual (D(V)) has a nonempty set of solutions, which is also bounded.

• The following strong duality result holds

min µ∈M(V) µ M(V) + f (Aµ) = max q∈R M , A * q L ∞ (V) ≤1 -f * (q).
• Let (µ , q ) denote a primal-dual pair. They are related by the following primal-dual relationships:

A * q ∈ ∂ • M (µ ) and -q ∈ ∂f (Aµ ). (6)
The left inclusion in [START_REF] Emmanuel | Towards a Mathematical Theory of Super-resolution[END_REF] implies that the support of a solution µ satisfies: supp(µ ) ⊆ {x ∈ Ω, |A * q (x)| = 1}.

Remark 1. Strong duality may hold under different assumptions. For instance, if f is polyhedral (allowing the hard constraint Aµ = b), then strong duality holds [START_REF] Borwein | Partially finite convex programming, Part I: Quasi relative interiors and duality theory[END_REF], but the dual solution set may be unbounded. Similarly, the coercivity of J is not absolutely needed. If J has a finite dimensional constancy space, the primal solution set still exists, but may be unbounded as well. In both cases, the unboundedness of either the primal or dual problem requires extra technicalities and assumptions in the proofs that we decided to discard.

Main results

This section contains our main findings. All the proofs are post-poned to the appendix.

The algorithm

The algorithm we propose consists in designing a sequence of cell partitions (Ω k ) k∈N of Ω. At each step of the algorithm, Ω k+1 is constructed by dividing a few cells in Ω k . Let V k denote the set of vertices of the partition Ω k :

V k def. = {vert(ω) | ω ∈ Ω k }.
At step k, we solve (D(V k )), to obtain a solution q k of the discretized dual problem. It satisfies A * q k L ∞ (V k ) ≤ 1 by construction. However, it might be infeasible for the problem (D(Ω)), i.e. A * q k L ∞ (Ω) > 1. This suggests that we should detect the cells ω ∈ Ω k for which A * q k L ∞ (ω) > 1 and subdivide them. To this end, we suppose that we have access to a set of candidate cells Ω k ⊂ Ω k that are likely to satisfy A * q k L ∞ (Ω) > 1. To make it easier to control the growth of |V k | with the iteration number k, we propose to not refine all candidates in Ω k , but only the largest of them. The complete solver is described in Algorithm 2. One iteration of the algorithm is displayed in Figure 1.

Figure 1: The refinement . From left to right: i) a cell partition, ii) the partition with the candidate cells grayed out, iii) only the candidate cells with largest diameter are selected for refinement and iv) the new resulting cell partition.

Algorithm 2 Adaptive Refinement Algorithm

1: Input: • Operator A • Initial partition Ω 0 (e.g. Ω 0 = {Ω}) • Target precision J • Solver for the discretized primal (P(V k )) and dual (D(V k )) • Set k = 1 2: WHILE max ω∈Ω * k-1 |ω| ≥ 2 -J 3:
1) Determine a solution q k of (D(V k ))

4:
2) Determine the candidate cells Ω k .

5:

3) Subdivide the cells in Ω k with largest diameter 6:

4) k = k + 1 7: Output:
• The dual solution q k of (D(V k )).

• The primal solution µ k of (P(V k )).

Assumptions on the selection process

In this paragraph, we discuss how to construct the set of candidate cells Ω k . Following [START_REF] Flinth | On the linear convergence rates of exchange and continuous methods for total variation minimization[END_REF], we let X k denote the set of local maximizers of |A * q k | exceeding 1, i.e.

X k def. = {x ∈ Ω | x is a local maximizer of |A * q k | , |A * q k (x)| ≥ 1} .
To obtain convergence guarantees we will work under the following hypothesis.

Assumption 4 (Generic convergence assumption). For each x ∈ X k , at least one of the cells in Ω k containing x is a candidate for refinement. In other terms, Ω k satisfies

X k ⊂ ω∈Ω k ω.
The above condition is too weak to allow a control of the numerical complexity. For instance the choice Ω k = Ω k -which corresponds to refine uniformly at each iteration -obeys Assumption 4, but leads to an exponential growth of |Ω k |. Our complexity analysis will therefore rely upon the following extra hypothesis.

Assumption 5 (Second order approximation).

There exists a constant κ > 0 independent of the iteration k and the cell ω such that for every ω ∈ Ω k , we have

A q k L ∞ (ω) ≥ 1 -κ|ω| 2 ,
where |ω| is the edge-length of the cell ω.

Construction of selection processes

In this section, we discuss how to construct rules satisfying assumptions 4 and 5.

Ideal selection

An obvious refinement rule that obeys both assumptions (4) and ( 5) is to let

Ω * k,ideal = {ω ∈ Ω k | ω ∩ X k = ∅} .
Indeed, Assumption 4 can be reformulated as

{ω ∈ Ω k | ω ∩ X k = ∅} ⊆ Ω *
k , which certainly is true for the above choice. As for Assumption 5, note that for all ω with X k ∩ ω = ∅, we have

A * q k L ∞ ≥ 1 ≥ 1 -κ |ω| 2 , since ω contains a cell point where |A * q k | succeeds one.
In order to apply this rule, we however need to know which cells contain the elements of X k . As discussed in the introduction, this is in general infeasible.

Upper-bounds selections

To obtain resolvable but still powerful enough selection processes, we will instead rely on the design of simple to evaluate upper-bounds

|A * q k |(ω) ∈ R satisfying |A * q k |(ω) ≥ A * q k L ∞ (ω)
. Equipped with such an upper-bound, we can define the candidate cells as:

Ω k = ω ∈ Ω k | |A * q k |(ω) ≥ 1 .
By construction, this selection process guarantees Assumption 4. Indeed, a cell ω with ω ∩ X k obviously obeys

A * q k L ∞ (ω) ≥ 1, and therefore also |A * q k |(ω) ≥ A * q k L ∞ (ω) ≥ 1.
Notice that this principle is similar to a branch-and-bound approach [START_REF] Eugene | Branch-and-bound methods: A survey[END_REF]. We base our decisions on upperbounds, which secure that some regions of space can be safely neglected. An important difference lies in the fact that the objective function |A * q k | varies at each iteration, meaning that one region which might have been discarded at one iteration can be refined some iterations later. Let us describe two such upper bounds. Definition 3 (A first order selection process). Assume that a m ∈ C 1 (Ω) for all m. Let us define

|A * q k |(ω) = inf v∈vert(ω) |A * q k (v)| + κ 1 (q k , ω) diam(ω), (7)
with

κ 1 (q k , ω) = M m=1 |q k [m]| a m L ∞ (ω) . (8)
The first order selection process is defined as

Ω k,1 = ω ∈ Ω k | |A * q k |(ω) ≥ 1
Proposition 3. The first order selection process Ω k,1 satisfies Assumption 4. However it may not respect Assumption 5.

In order to satisfy both Assumption 4 and Assumption 5, we will use second order selection rules.

Definition 4 (A second order selection process). Assume that a m ∈ C 2 (Ω) for all m. For any cell ω, and all q k ∈ R M , define

|A * q k |(ω) def. = inf v∈vert(ω) sup x∈ω |A * q k (v) + (A * q k ) (v), x -v | + κ 2 (q k , ω) 2 x -v 2 , (9)
with

κ 2 (q k , ω) = M m=1 |q k [m]| sup x∈ω a m (x) 2→2 . (10)
The second order selection process is defined as

Ω k,2 = ω ∈ Ω k | |A * q k |(ω) ≥ 1 ( 11
)
Proposition 4. If the sequence (q k ) k∈N is uniformly bounded, then the second order selection process Ω k,2 satisfies both Assumption 4 and 5.

Importantly, notice that the problem

sup x∈ω |A * q k (v) + (A * q k ) (v), x -v | + κ 2 (q k , ω) 2 x -v 2 ,
consists in maximizing a convex function over a polyhedron. A solution is therefore attained on vert(ω), and can be evaluated in constant time per cell.

Remark 2. The values κ 1 (q k , ω) and κ 2 (q k , ω) can be replaced by any upper-bound on the Lipschitz constant of A * q k and the Lipshitz constant of (A * q k ) respectively. In particular, it is possible to use the global bounds κ 1 (q k , ω) = κ 1 q k 2 and κ 2 (q k , ω) = κ 2 q k 2 , where κ 1 and κ 2 are defined in equation (4).

Combining upper-bounds and lower-bounds on the gradient norm

The larger Ω k , the higher the chances of selecting unwanted cells for refinement. To reduce the cardinality of the candidate cells, it makes sense to only refine the cells where the function |A * q k | might surpass 1 and where the gradient's norm (A * q k ) (x) 2 might cancel. Indeed, Assumption 4 only requires the local maximizers of |A q k | that surpass 1 to be selected. In cells containing maximizers, the gradient of |A q k | vanishes. Consequently we can design a selection process based on lower bounds of the gradient.

Definition 5 (Second order selection process with first order gradient). Assume that a m ∈ C 2 (Ω) for all m. Define |A * q k |(ω) and κ 2 (q k , ω) as in ( 9) and (10) respectively. For any cell ω, and all q k ∈ R M , define

∇A * q k 2 (ω) = sup v∈vert(ω) (A * q k ) (v) 2 -κ 2 (q k , ω) diam(ω) (12)
The second order selection process with first order gradient is defined as

Ω k,2,1 = ω ∈ Ω k | |A * q k |(ω) ≥ 1 and ∇A * q k 2 (ω) ≤ 0 .
Proposition 5. If the sequence (q k ) k∈N is uniformly bounded, then the selection process Ω k,2,1 satisfies both Assumption 4 and 5. Incorporating gradient lower bounds reduces the cardinality of Ω k in the sense that the cardinality of Ω k in Definition 5 is non greater than the one of Ω k in Definition 4.

Remark 3. Following Remark 2, the definition of κ 2 (q k , ω) given in (10) can be replaced by any upper bound of the Lipschitz constant of the gradient of |A * q k |. Moreover, we use a first order Taylor expansion for ∇A * q k 2 . It is possible to replace or even combine this lower bound with bounds stemming from higher order Taylor expansions.

Generic convergence guarantees

To obtain a generic convergence result, we first need to prove that the algorithm is well defined. To this end, we introduce the following assumption.

Assumption 6 (Well-posedness of the algorithm ). The initial set of vertices V 0 is admissible in the sense that there exists µ ∈ M(V 0 ) with Aµ ∈ int(dom(f )).

Theorem 6. Under Assumptions 1, 2, 3, 4 and 6, the sequences (µ k ) k∈N and (q k ) k∈N defined in Algorithm (2) are well-defined. They contain subsequences that converge weakly to solutions µ and q of (P(Ω)) and (D(Ω)), as well as in optimal function value. If either the primal or dual solution is unique, the whole corresponding sequence converges.

Proof. The proof of this theorem is postponed to Section A.1.

Remark 4. In [START_REF] Flinth | On the linear convergence rates of exchange and continuous methods for total variation minimization[END_REF], additional assumptions were made (either smoothness of f or surjectivity of A restricted to M(V 0 )) to obtain generic convergence. The reason we can remove that assumption is based on a refined analysis.

Remark 5. The proof of this result relies on the fact that the sequence (V k ) k∈N is nested. In exchange algorithms, it is possible to not only add, but also discard points from V k to construct V k+1 . The obvious interest is to reduce the numerical complexity. We do not know if it possible to adapt the algorithm and the proof to allow for points suppression as well.

Linear convergence rates

Having established the generic convergence result, we move on to providing an eventual linear convergence rate under additional regularity conditions. We first need a couple of additional regularity conditions on f , A and the primal-dual solution pair, which are similar to those in [START_REF] Flinth | On the linear convergence rates of exchange and continuous methods for total variation minimization[END_REF] and [START_REF] Pieper | Linear convergence of accelerated conditional gradient algorithms in spaces of measures[END_REF].

Assumption 7 (Linear convergence conditions).

• The functionals a m are twice differentiable:

a m ∈ C 2 0 (Ω) for all 1 ≤ m ≤ M . • The function f is convex, differentiable with an L-Lipschitz gradient.
Following [START_REF] Duval | Exact support recovery for sparse spikes deconvolution[END_REF], we also require the following condition.

Assumption 8 (Non-degenerate source condition). We say that the non-degenerate source condition [START_REF] Duval | Exact support recovery for sparse spikes deconvolution[END_REF] holds if we have the following:

• The solution µ of (P(Ω)) is unique and supported on S ∈ N points µ = S s=1 α s δ x s for some α s ∈ R and x s ∈ Ω. In what follows, we let X def.

= {x 1 , . . . , x S }.

• The dual certificate |A * q | is only equal to 1 in the points x 1 , . . . , x S and is strictly concave around those points. This ensures the existence of a parameter γ > 0 and a radius R > 0 with

B(x s1 , R) ∩ B(x s2 , R) = ∅, ∀s 1 = s 2 (13) sign(A * q (x))(A * q ) -γ Id for x with dist(x, X ) ≤ R, |A * q (x)| ≤ 1 - γR 2 2 for x with dist(x, X ) ≥ R. ( 14
)
This last assumption is generic, given that the solution is unique. It is a condition that has appeared in the literature as a mean to prove recovery of sparse measures using problems of the form (P(Ω)) -see e.g. [START_REF] Poon | Support Localization and the Fisher Metric for offthe-grid Sparse Regularization[END_REF][START_REF] Emmanuel | Towards a Mathematical Theory of Super-resolution[END_REF]. We can now formulate our main result.

Theorem 7. Under Assumptions 3, 4, 5, 7 and 8, Algorithm 2 eventually converges linearly. That is, there exists constants k 0 ∈ N, c > 0 (depending on A, f and µ ) such that the algorithm terminates in no more than k = k 0 + cSJ iterations. For sufficiently large J, we further have

|V k | = O(J), controlled complexity dist H (X | vert(Ω k )) 2 -J , controlled localization q k -q 2 2 -J , certificate on the dual J(µ k ) -J(µ ) 2 -2J
, certificate on the primal.

Proof. The proof of this theorem is quite technical, and is therefore postponed to Section A.2. It relies on a few technical inequalities from the companion paper [START_REF] Flinth | On the linear convergence rates of exchange and continuous methods for total variation minimization[END_REF], but differs significantly to account for the discretization procedure.

Informally, it is built using the following arguments. First, appealing to the generic convergence result and the fact that only finitely many cells have an edge length larger than any fixed value δ > 0, we argue that after warming period of at most k 0 iterations, q k is close to q , and no cells with an edge-length larger than a critical value can be active. Once that happens, the algorithm will only be able to refine cells close to the maximizers X . This results in a multiscale refinement of local regions around the sought-for locations, see e.g. Figure 3. Remark 6. We did not keep track of the constants in the above inequalities to simplify the reading. While some of them are explicit, others, like the time k 0 to reach a linear convergence rate are not. Remark 7. We can replace µ k , the solution of (P(V k )), by the solution μk of P(vert(Ω k )) defined as

μk def. = inf µ∈M(vert(Ω k )) µ M + f (Aµ). ( 15
)
and still have J(μ k ) -J(µ ) 2 -2J . The interest of this alternative problem is that the cardinality of vert(Ω k ) is significantly smaller than that of V k , helping to reduce the numerical complexity.

Remark 8. Our algorithm relies on dyadic subdivision of cells. We therefore cannot expect the algorithm to converge faster than linearly. In that regard, Theorem 7 is optimal.

Numerical experiments

In this section, we aim at illustrating our main findings through some simple numerical experiments. We consider problems of sparse source recovery problem with filtered measurements. That is, given a ground truth μ, we set y = Aμ and let f (q) = 1 2 q -y 2 2 . This yields

f * (q )
def.

= sup

q∈R M q, q - 1 2 q -y 2 2 = 1 2 q 2 2 + q , y .
We consider Gaussian measurements functions of the form

a m (x) = 1 2πσ exp -x -z m 2 2 2σ 2
for some value σ > 0. To properly define our selection procedures in [START_REF] De | Exact reconstruction using Beurling minimal extrapolation[END_REF], we need an upper-bound on the second order derivatives.

Proposition 8. Define

κ 2,m (ω) = a m (dist(z m , ω)) σ 4 max σ 2 , (dist(z m , ω) + √ D|ω|) 2 then κ 2,m (ω) ≥ sup x∈ω a m (x) 2→2 . We can choose κ 2 (q k , ω) = M m=1 |q k |[m]κ 2,m (
ω), in Proposition 10 to define the second order candidates Ω k .

Implementation details

We implement our algorithm in Python using the numpy package. To solve the discretized dual (D(V k )), we rely on the SCS solver of the CVXPY package [START_REF] Diamond | CVXPY: A Python-embedded modeling language for convex optimization[END_REF][START_REF] Agrawal | A rewriting system for convex optimization problems[END_REF]. The selection procedures are defined and implemented as described in the main text. To assess the convergence rates, we compute the exact solutions of the primal problem by running a fixed step gradient descent in the parameter space, see equation [START_REF] Borwein | Partially finite convex programming, Part I: Quasi relative interiors and duality theory[END_REF], initialized in the 'ground truth measures' we specify. This is sound, since the true solution lies close to them (see e.g. [START_REF] Poon | Support Localization and the Fisher Metric for offthe-grid Sparse Regularization[END_REF]).

1D-experiments

The problem We set y = Aμ with μ def. = 8δ 1/3 -9δ 2/3 . We choose the Dirac mass locations to lie at 1/3 and 2/3, since these points are the hardest to reach with dyadic partitions. The sampling locations and σ-parameter are set to z m def.

= m/M and σ = 2/M , with M = 20.

Second-order upper bound The behavior of the second order selection process algorithm of Definition 4 is displayed in Table 1a and Figure 2. As can be seen in the figure, the algorithm starts by a burn-in period of 4 iterations. This transient behavior explains why the linear convergence rate only occurs after a finite number of iterations. Then, only cells in a neighborhood of {1/3, 2/3} are refined. The Table 1 clearly indicates that the distance dist H (V k , X ) decays exponentially fast, illustrating Theorem 7 and the linear convergence rate. Observe that less than 300 vertices are enough to obtain a precision 10 -6 , while a uniform refinement would require 10 6 vertices. This illustrates the huge computational/memory advantage of this adaptive method.

Second-order upper bound with first order gradient We turn our attention to the second order selection process with first order gradient, see Definition 5. The results are displayed in Table 1b and Figure 3. In comparison to the previous test, a lower bound on the gradient is used to reduce the cardinality of Ω k . Two measures of complexity can be used to compare the approaches: i) the cardinality |V k | needed to reach a given accuracy dist H (V k , X ), or ii) the number of iterations to reach the same accuracy. Reducing the cardinality of Ω k can be detrimental to the second notion of complexity. For example, compare Figure 3f and Figure 2f. The cells that are not flagged for refinement in Figure 3f are flagged in Figure 3g and refined at Iteration 7. Iteration 7 can be seen as a failed zwischenzug iteration that loses a tempo. However, for the first notion of complexity, the conclusion is different. We see that for this particular example, adding a gradient lower bounds allows reaching the target precision in Table 1b with less than half the number of vertices for the vanilla second order bound. A full complexity analysis would require a fine analysis of the quadratic programming solver, which is out of the scope of this paper.

2D experiments

The problem In this section, we assume that the sampling points z m lie on a Euclidean grid. More precisely, we suppose that

√ M ∈ N and that each index m ∈ 1, M can be decomposed as m = (m 1 , m 2 ) ∈ 0, √ M -1 2 and z m = 1 √ M (m 1 , m 2 ) with M = 15. μ is chosen as μ = -9δ (1/3,1/3) + 8δ (1/3,2/3) + 5δ (2/3,2/3) .
Results We begin by showcasing the behaviour of the algorithm when the second-order upper bound is used. Table 2a and Figure 4 summarize the algorithm's behavior. The conclusions are similar to the previous section and consistent with Theorem 7: after a burn-in period, the grid is refined in a multi-scale fashion, only around the support X of the solution µ . To control the complexity of our algorithm we refine only the cells with largest diameter. The effect of this strategy is striking in 2D, where the algorithm spends some iterations to refine larger cells only. See Figure 4, iterations 6, 8, 9, 10. At these iterations, it is not the cells containing the maximizers X k which are refined, but only the largest ones which were not refined in the previous iterations. Yet, the table indicates a clear advantage of this adaptive method: about 3000 vertices are sufficient to reach a precision 10 -4 , The behavior of the adaptive refinement algorithm with a second order selection process, on a 1D sparse recovery problem. The set Ω k is displayed in green, the function |A * q k | is displayed in dashed red, the upper-bound |A * q k | is the piecewise-constant function. Observe that it always dominates |A * q k |. The algorithm starts with a burn-in period of 4 iterations. There, it refines all cells uniformly since the upper-bound is highly inaccurate. After a while, only the cells around the locations X get refined in a multiscale fashion.

while the same guarantee would be obtained only with 10 8 vertices for a uniform refinement. The results when a lower bound of the gradient is added are displayed in Table 2b and Figure 5. For this example, there is no increase in the number of iterations, and only a slight decrease of the number of vertices is observed. Again, a more detailed analysis of the effects of gradient-including rules is beyond the scope of this paper.

Perspectives

In this work, we proposed an alternative to the Frank-Wolfe algorithm for infinite dimensional total variation regularization. This adaptive refinement approach has a significant advantage: it does not require to search for the maximizers of a non-convex function at each iteration. Instead, it progressively discards regions of the space, in a certified manner, resembling a branch-and-bound approach. The only prerequisite to implement it is the computation of upper bounds on the largest eigenvalues of the measurement functions Hessians. We proved that the method has great adaptivity properties. It converges generically under weak assumptions, and its rate of Figure 3: The adaptive refinement algorithm with a second order selection process and first order gradient. The setting is the same as the one of Figure 2. The cardinality of the set of candidates Ω k is smaller, as can be seen when comparing Figure 3f with Figure 2f.

convergence is linear under stronger regularity assumptions. To the best of our knowledge, this is as good as the best existing results for the Frank-Wolfe algorithm, and we cannot expect more from this dichotomic approach. Despite these assets, some parts of the algorithm still require some analysis. In particular, the solution of a finite dimensional convex problem needs to be computed at each iteration. In this work, we assumed that this could be achieved with an arbitrary accuracy. A complete theory should account for approximation errors and for the complexity of the sub-problems.

On a more positive side, the scope of this approach is possibly significantly wider than total variation regularization. Up to some adjustements, we believe that the method could be extended to more general sparse measure optimization problems. In particular, we think of other regularizers that promote sparse solutions, such as problems defined over the cone of nonnegative measures, or over the set probability measures.

A Proofs

Here, we include the proofs ommited in the main text. We begin by proving the main results, i.e. the generic (Theorem 6) and linear (Theorem 7) convergence results, and save the proofs of smaller, technical propositions to the end.

Iteration |V k | primal dist H (V k , X ) 0 2 3.

A.1 Proof of Theorem (6)

The proof of Theorem 6 builds on similar arguments as the ones in the companion paper [START_REF] Flinth | On the linear convergence rates of exchange and continuous methods for total variation minimization[END_REF]Thm 3.1], with some modifications related to the discretization and the fact that the assumptions have been slightly weakened.

Proof of Theorem 6. i) Well-posedness Under Assumptions 2, 1, 3 and 6, we can apply Proposition 2 to ensure the existence of the primal-dual pair (µ 0 , q 0 ). For the next iterates k ≥ 1, the measure µ in Assumption 6 still satisfies µ ∈ M(V k ) by nestedness of the sequence (V k ) k∈N . Hence we can apply Proposition 2 again. ii) Existence of the limit of the primal solutions. First remark that the sequence (J(µ k )) k∈N is non-increasing since the sets V k are nested. Since J is coercive, the sequence ( µ k M(Ω) ) k∈N is bounded. Hence there exists a subsequence (µ k ) k∈N , which we do not relabel, that weak- * converges towards a measure µ ∞ .

iii) Existence of the limit of the dual solutions.

Let C k def. = q ∈ R M , A * q L ∞ (V k ) ≤ 1 . The fact that V k+1 ⊇ V k implies that C k+1 ⊆ C k .
Therefore any solution q k of (D(V k )) belongs to C 0 . By Assumption 6, f * is coercive on C 0 (see the proof 2). Moreover, the sequence (f * (q k )) k∈N is nondecreasing, bounded above by f * (q ). Therefore all the vectors q k belong to Figure 4: Our algorithm's behavior on a 2D example for second-order selection rules. The set Ω k is displayed in green, the superlevelset 1 of |A * q k | is filled with red, the level-set 0.9 is represented with a dashed red line and levelset 0.75 with a dotted red line. The algorithm starts with a burn-in period of 3 iterations. There, it refines all cells uniformly since the upper-bound is highly inaccurate. Then, only the cells around the locations of X get refined in a multiscale fashion. Remember that only the cells in Ω * k with largest diameter are refined. This explains the behavior of the algorithm between, e.g. Figures 4f and4g Figure 5: The adaptive refinement algorithm's behavior on a 2D example for second-order selection rules with first order gradient. The behavior quadtrees are very similar to those in Figure 4.

the level set {q ∈ R M , f * (q) ≤ f * (q )}, which is by coercivity of f * . Up to a subsequence, (q k ) k∈N converges to a limit point q ∞ . iv) Equicontinuity of (A * q k ) k∈N . As another technical lemma, we prove that the set (A * q k ) k∈N is equicontinuous. Let > 0 be arbitrary. Since the functions a m ∈ C 0 (Ω) all are uniformly continuous, there exists a δ > 0 Table 2: The adaptive refinement Algorithm's behavior for the 2D super-resolution problem.

primal dist H (V k , X ) 0 4 1.35942e+03
with the property

x -y 2 < δ ⇒ |a m (x) -a m (y)| < sup k q k 1 for all m.
Consequently,

x -y 2 < δ ⇒ |(A * q k )(x) -(A * q k )(y)| = M m=1 (a m (x) -a m (y))q k (m) ≤ M m=1 |a m (x) -a m (y)| |q k (m)| < sup k q k 1 M m=1 |q k (m)| ≤ . (16)
v) Feasibility of q ∞ . Due to the convergence of (q k ) k∈N , the sequence (A * q k ) k∈N is converging strongly to A * q ∞ . We will now prove that

A * q ∞ L ∞ (Ω) ≤ 1. Towards a contradiction, assume that A * q ∞ L ∞ (Ω) = 1 + 2
for an > 0. By convergence of (A * q k ), we can conclude that there exists [START_REF] Eftekhari | Sparse inverse problems over measures: Equivalence of the conditional gradient and exchange methods[END_REF]. The set X k is not empty and there exists a cell ω that contains a point of X k and satisfies A * q k L ∞ (ω) ≥ 1 + . By Assumption 4 this cell belongs to Ω k . It must further satisfy diam(ω) ≥ 2δ. If not, all points in x have a distance to V k smaller than δ. Since we have |A * q k |(x) ≤ 1 for x ∈ vert(ω), the equicontinuity of the A * q k implie that |A * q k (x)| ≤ 1 + for all x ∈ ω, which is a contradiction. Hence, for all k ≥ k 0 , there exists ω ∈ Ω k such that diam(ω) ≥ 2δ. Let (ω k ) k∈N denote a sequence of refined cells in Ω k . Since we pick the active cells of largest diameter, we must have diam(ω k ) ≥ 2δ for all k ≥ k 0 . Since all the ω k 's belong to a compact set Ω, there is a finite number of cells with diameter larger than 2δ. Hence, we can extract a subsequence of (ω k ) which is constant. This is a contradiction, because the cells (ω k ) are refined and cannot appear twice.

k 0 ∈ N such that for k ≥ k 0 , A * q k L ∞ (Ω) ≥ 1 + . Set δ as in
vi) Convergence to a solution. Overall, we proved that the primal-dual pair (µ ∞ , q ∞ ) is feasible. It remains to prove that it is actually a solution. Here, we reproduce the argument of [START_REF] Flinth | On the linear convergence rates of exchange and continuous methods for total variation minimization[END_REF] for completeness. Let us first remark that µ ∞ M + f (Aµ ∞ ) ≥ -f * (q ∞ ) by weak duality. To prove the second inequality, first notice that the weak- * -continuity of A implies that Aµ k → Aµ ∞ . Assumption 2 furthermore implies that f is lower semi-continuous. As a supremum of linear functions, so is f * . Since also q k → q ∞ , we conclude

f * (q ∞ ) + f (Aµ ∞ ) ≤ lim inf k→∞ f * (q k ) + f (Aµ k ).
Assumptions 2, 1 together with Proposition 2 imply exact duality of the discretized problems. This means

f * (q k ) + f (Aµ k ) = -µ k M .
Since the norm is weak- * -l.s.c. , we thus obtain lim inf

k→∞ f * (q k ) + f (Aµ k ) = lim inf k→∞ -µ k M ≤ -lim inf k→∞ µ k M ≤ -µ ∞ M .
Reshuffling these inequalities yields µ ∞ M + f (Aµ ∞ ) ≤ -f * (q ∞ ), i.e., the reverse inequality. Thus, µ ∞ and q ∞ fulfill the duality conditions, and are solutions. The final claim follows from a standard subsequence argument.

A.2 Proof of Theorem [START_REF] Chizat | Sparse optimization on measures with over-parameterized gradient descent[END_REF] In this section, we prove the main theoretical result of the paper, which is Theorem [START_REF] Chizat | Sparse optimization on measures with over-parameterized gradient descent[END_REF]. To proceed to the final result, we begin by proving a set of intermediary results. The first one is a list of useful inequalities. Many of them are direct adaptions from [START_REF] Flinth | On the linear convergence rates of exchange and continuous methods for total variation minimization[END_REF].

Proposition 9. The following inequalities hold under Assumption 7:

q k -q 2 dist H (V k |X k ) (17)
q k -q 2 2 max (dist H (X k |X ), dist H (V k |X )) • dist H (V k |X ) (18)
Proof. All those inequalities come directly from [START_REF] Flinth | On the linear convergence rates of exchange and continuous methods for total variation minimization[END_REF]. The first inequality (17) comes from Lemma 3.5, the second (18) from Lemma 3.6.

Proposition 10 (A list of useful inequalities). Under Assumptions 7 and 8, there exists a k 0 ∈ N with the property that for k ≥ k 0 , the following inequalities are true:

dist H (X |X k ) q k -q 2 (19) dist H (X k |X ) = dist H (X |X k ) (20) dist H (X k |X ) dist H (V k |X k ) (21) dist H (V k |X k ) dist H (V k |X ) (22)
q k -q 2 dist H (V k |X ) (23)
f (µ k ) -f (µ ) dist H (V k |X ) 2 . ( 24
)
Proof. The first inequalities ( 20) and ( 19) are simple consequences of Proposition 3.7 in the companion paper [START_REF] Flinth | On the linear convergence rates of exchange and continuous methods for total variation minimization[END_REF], together with the fact that, by the generic convergence result, q k converges to q . Inequality ( 21) is a combination of ( 17), [START_REF] Hettich | A review of numerical methods for semi-infinite optimization[END_REF] and [START_REF] Frank | An algorithm for quadratic programming[END_REF].

To prove inequality [START_REF] Hiriart-Urruty | Convex analysis and minimization algorithms II: Advanced Theory and Bundle Methods[END_REF], let us start by proving that dist

H (V k |X k ) dist H (V k |X ).
We have by the triangular inequality

dist H (V k |X ) ≤ dist H (V k |X k ) + dist H (X k |X ) (21) dist H (V k |X k ).

Let us prove the converse inequality dist

H (V k |X k ) dist H (V k |X ).
To this end, first combine [START_REF] Flinth | Exact solutions of infinite dimensional total-variation regularized problems[END_REF], [START_REF] Hettich | A review of numerical methods for semi-infinite optimization[END_REF] and [START_REF] Frank | An algorithm for quadratic programming[END_REF] to get dist

H (X |X k ) 2 max (dist H (X |X k ), dist H (V k |X )) • dist H (V k |X ). ( 25
)
Regardless which of the expressions dist H (X |X k ) and dist

H (V k |X ) is larger, this inequality yields dist H (X |X k ) dist H (V k |X ).
Combining this and the triangular inequality, we get

dist H (V k |X k ) ≤ dist H (V k |X ) + dist H (X |X k ) dist H (V k |X ).
The inequality [START_REF] Hiriart-Urruty | Convex analysis and minimization algorithms II: Advanced Theory and Bundle Methods[END_REF] together with [START_REF] Hiriart-Urruty | Convex analysis and minimization algorithms II: Advanced Theory and Bundle Methods[END_REF] now implies [START_REF] Kunisch | Optimal control of the undamped linear wave equation with measure valued controls[END_REF]. Since the inequality ( 24) is a direct consequence of Proposition 3.12 in [START_REF] Flinth | On the linear convergence rates of exchange and continuous methods for total variation minimization[END_REF], we can conclude the proof.

Let us introduce the following shorthand notation to design a neighborhood of X of width r > 0:

B r def. = x∈X B(x, r).
Proposition 11 (Approximate nondegeneracy of |A * q k |). Under Assumptions 7 and 8, there exists k 1 ∈ N, which we can assume to be larger than k 0 , such that for all k ≥ k 1 , A * q k satisfies the approximate nondegenerate source condition:

i) The balls B(x s , R) contain exactly one local maximizer x k,s of |A * q k | for each 1 ≤ s ≤ S.

ii) Within these balls, |A * q k | is strongly concave:

|A * q k | (x) - γ 2 Id, ∀x ∈ B R . (26)
iii) Outside of these balls, we have:

|A * q k |(x) ≤ 1 - γR 2 4 , ∀x ∈ Ω \ B R . (27)
iv) Finally

sup x∈Ω |A * q k |(x) ≤ 1 + c 2 dist H (V k |X k ) 2 . ( 28
)
Proof. The convergence of (q k ) k∈N to q and the fact that the functions a m ∈ C 2 (Ω) imply

A * q k → A * q , (A * q k ) → (A * q ) and (A * q k ) → (A * q ) uniformly.

The conclusion of the three first points follows from the nondegeneracy of A * q in Assumption 8. To obtain the last, let ω s denote the cell containing the point x k,s in X k closest to x s . We have by definition (A * q k ) (x k,s ) = 0. Let v s denote a vertex of ω s closest to x k,s . To conclude, we can use a second-order Taylor expansion with the mean-value form of the remainder. It reads:

|A * q k |(v s ) = |A * q k |(x k,s ) + |A * q k | (x k,s ), v s -x k,s + 1 2 |A * q k | (ξ)(v s -x k,s ), (v s -x k,s ) for some point ξ in the segment [v, x k,s ]. By construction |A * q k |(v s ) ≤ 1, |A * q k | (x k,s ) = 0. Moreover (|A * q k | (ξ))
k∈N is uniformly bounded. This yields for all s:

1 ≥ |A * q k |(x k,s ) -c 2 v s -x k,s 2 2 ≥ |A * q k |(x k,s ) -c 2 dist H (V k |X k ) 2 .
Taking the maximum over the different 1 ≤ s ≤ S gives the result [START_REF] Poon | Support Localization and the Fisher Metric for offthe-grid Sparse Regularization[END_REF].

The above proposition translates to the following result for the upper-bound.

Proposition 12 (Finite time behavior of the upper-bound). Under Assumptions 7 and 8, there exists k 2 ≥ k 1 and some positive constants c 1 , c 2 , c 3 such that for all k ≥ k 2 and for all cell ω:

sup x∈ω |A * q k |(x) ≤ 1 -c 1 dist(ω, X k ) 2 + c 2 dist H (V k |X k ) 2 if dist(ω, X ) ≤ R, 1 -c 3 R 2 if dist(ω, X ) ≥ R. (29)
Proof. Take a cell ω with dist(ω, X ) ≥ R. For k ≥ k 1 , the upper-bound ( 27) is valid. Hence, we obtain the second bound in inequality [START_REF] Reemtsen | Numerical methods for semi-infinite programming: A survey[END_REF] for all k ≥ k 1 and c 3 = γ 4 . To obtain the first inequality, consider a cell ω with dist(ω, X ) ≤ R. Let s ∈ 1, S denote any index such that B(x s , R) ∩ ω = ∅. Point i) in Proposition 11 implies the existence of a unique point x k,s in X k ∩ B(x s , R). Proposition 11, point iv) implies that Proposition 11 states that |A * q k | is strongly concave in the balls B(x s , R). Therefore:

|A * q k (x k,s )| ≤ 1 + c 2 dist H (V k |X k ) 2 . Moreover, point ii) in
|A * q k |(x) ≤ 1 + c 2 dist H (V k |X k ) 2 -c 1 dist(x, X k ) 2 with c 1 = γ 4 , ∀x ∈ B(x s , R) ∩ ω.
Using the above inequality and point iii) in Proposition 11 gives:

sup x∈ω∩B R |A * q k |(x) ≤ 1 + c 2 dist H (V k |X k ) 2 -c 1 dist(ω, X k ) 2 , sup x∈ω∩B c R |A * q k |(x) ≤ 1 - γR 2 4 ( 30
)
We now need to show that (30) actually implies

|A * q k |(x) ≤ 1 + c 2 dist H (V k |X k ) 2 -c 1 dist(ω, X k ) 2 .
for x ∈ ω ∩ B c R . To this end, first notice that point i) in Proposition 11 shows that dist

H (X k |X ) ≤ R. Therefore, if dist(ω, X ) ≤ R, we get dist(ω, X k ) (5) ≤ dist(ω, X ) + dist H (X k |X ) ≤ 2R.
Hence, we get dist(ω, X k ) 2 R 2 , and by [START_REF] Remez | Sur la détermination des polynômes d'approximation de degré donnée[END_REF] we get sup

x∈ω∩B c R |A * q k |(x) ≤ 1 - γR 2 4 ≤ 1 -c 1 dist(ω, X k ) 2
for some other constant c 1 . In particular, we get

sup x∈ω |A * q k |(x) ≤ 1 + c 2 dist H (V k |X k ) 2 -c 1 dist(ω, X k ) 2 .
Proposition 13 (Structural properties of the partitions Ω k ). For k ≥ k 2 , let Ω k denote a partition generated by Algorithm 2. There exists a radius r > 0 such that any cell ω ∈ Ω k satisfies:

i) dist(ω, X ) ≥ R ⇒ |ω| ≥ r. ii) dist(ω, X ) ≤ R ⇒ |ω| dist(ω, X ). iii) For < 2 -k2 • min ω∈Ω0 |ω|, we have min ω∈Ω k |ω| < ⇒ dist H (V k |X ) .
Proof of Proposition 13. Let k 2 be the number of iterations referenced in Proposition 12. It is clear that after k 2 iterations, all the cells have a diameter larger than 2 -k2 • min ω∈Ω0 |ω|.

Let us establish point i) first. Let ω denote a cell in Ω k with dist(ω, X ) ≥ R. To be refined by the algorithm, this cell needs to verify the second order approximation Assumption 5:

A * q k L ∞ (ω) ≥ 1 -κ|ω| 2
On the other hand, Proposition 12 states that

A * q k L ∞ (ω) ≤ 1 -c 3 R 2
A necessary condition for refinement by Algorithm 2 is then |ω| ≥ cR for some c. Taking r = min c 2 R, 2 -k2 • min ω∈Ω0 |ω| proves i).

Point ii) is more technical. It follows from the following arguments.

1. Suppose that the partition Ω k contains a cell ω with an edge-length |ω| def.

= with < 2 -k2 • min ω∈Ω0 |ω|.

2. The parent cell ω p of ω must have been refined in some iteration k before k but after k 2 . For this k , the size of the parent cell is |ω p | = 2 .

3. Since we refine the largest cells in Ω k , it means that every cell in Ω k has an edge-length smaller or equal than 2 . By construction, every cell that contains an element of

X k is in Ω k , hence dist H (V k |X k ) .
4. By Proposition 10, equation ( 22), we have dist

H (V k |X k ) dist H (V k |X ). We get dist H (V k |X ) for k = k . By monotonicity of the sequence (dist H (V k |X )
) k∈N , we also get the inequality for all k ≥ k . 5. Noticing that dist(ω p , X * ) ≤ dist(ω, X * ) ≤ R, we apply Proposition 12 to ω p to get

A * q k L ∞ (ωp) ≤ 1 -c 1 dist(ω p , X k ) 2 + c 2 2 .
Since ω p is refined at iteration k , it belongs to Ω k and needs to verify the second order approximation Assumption 5:

A * q k L ∞ (ωp) ≥ 1 -κ|ω p | 2 ≥ 1 -4κ 2 .
From the two previous inequalities, we get dist(ω p , X k ) .

6. To conclude, remark that dist(ω p , X k )

≥

dist(ω, X k ) -dist H (ω|ω p ) ≥ dist(ω, X k ) - √ D (5) ≥ dist(ω, X ) -dist H (X k |X ) - √ D ≥ dist(ω, X ) -c 5 ,
for some c 5 > 0. This proves ii).

For point iii), repeat the first four arguments of point ii) to the cell that achieves min ω∈Ω k |ω|.

Now that we established the geometrical structure of Ω k , the remaining task is to count the number of cells in Ω k .

Proposition 14 (Counting cells).

Let Ω k denote a cell partition generated by Algorithm 2. Assume that

min ω∈Ω k |ω| = 2 -J
for some J ∈ N with J ≥ k 2 in Proposition 13. Then the number of cells in Ω k satisfies:

|Ω k | ≤ c 0 + c 1 SJ
for some constants c 0 , c 1 > 0 independent of J and S.

Proof. We decompose Ω k as

S s=0 Ω k,s with Ω k,0 def. = {ω ∈ Ω k , dist(ω, X ) > R}, Ω k,s def. = {ω ∈ Ω k , dist(ω, x s ) = dist(ω, X ), dist(ω, X ) ≤ R} s ∈ 1, S .
In words, Ω k,s is the set of cells in Ω k closest to x s , and at a distance smaller than R from X . We have

|Ω k | ≤ S s=0 |Ω k,s |. (31)
We first use point i = 2 -J . By assumption |ω(x)| ≥ for all x ∈ Ω. Moreover for all x ∈ Ω such that ω(x) ∈ Ω k,s we have by Proposition 13, point ii)

|ω(x)| ≥ c dist(ω(x), x s ). Therefore |ω(x)| dist(ω(x), x s ) (5) ≥ dist(x, x s ) -dist H (x|ω(x)) ≥ x -x s 2 - √ D|ω(x)|.
This gives |ω(x)| x -x s 2 for any x ∈ ω∈Ω k,s ω. Combining the two inequalities yields

|ω(x)| ≥ max( , c x -x s 2 ), ∀x ∈ ω∈Ω k,s ω.
for some c ≥ 0. For each cell ω, we have |ω| D = ω dx. We continue as follows

|Ω k,s | = ω∈Ω k,s 1 = ω∈Ω k,s ω |ω(x)| -d dx = ω∈Ω k,s ω |ω(x)| -D dx ≤ ω∈Ω k,s ω max( , c x -x s 2 ) -D dx ≤ Ω max( , c x -x s 2 ) -D dx ≤ B(x s , √ D) max( , c x -x s 2 ) -D dx = B(x s , /c) -d dx + B(x s , √ D)\B(x s , /c) (c x -x s 2 ) -D dx 1 + √ D ρ= /c ρ -D ρ D-1 dρ 1 + | log 2 ( )| 1 + J.
Summing up everything, we obtain |Ω k | c 0 + c 1 SJ for some constants c 0 , c 1 ≥ 0.

We now gathered all the necessary ingredient to prove the complexity result.

Proof of Theorem 7. Take J ≥ k 2 . The Algorithm terminates whenever a cell of size 2 -(J+1) has to be refined. When it stops, all the cells therefore have a size larger than 2 -(J+1) by construction and min ω∈Ω k |ω| = 2 -(J+1) . Proposition 14 therefore indicates that |Ω k | ≤ c 0 + c 1 SJ. Since at least one cell is refined per iteration, we reached the termination criterion for a number of iterations k ≤ c 0 + c 1 SJ. Point iii) in Proposition 13 allows us to conclude that dist H (V k |X ) 2 -J . The list of inequalities in Proposition 10 yield the conclusion.

A.3 Further proofs

Here, we collect proofs of the remaining, smaller and more technical propositions.

A.3.1 Proof of Proposition 1

Proof. For any

x 1 ∈ X 1 , x 2 ∈ X 2 , x 3 ∈ X 3 , we have x 1 -x 2 2 ≤ x 1 -x 3 2 + x 3 -x 2 2
. Taking the infimum over x 1 ∈ X 1 and the infimum over

x 2 ∈ X 2 yields dist(X 1 , X 2 ) ≤ inf x1∈X1 x 1 -x 3 2 + inf x2∈X2 x 3 -x 2 2 ≤ sup x3∈X3 inf x1∈X1 x 1 -x 3 2 + inf x2∈X2 x 3 -x 2 2 = dist H (X 1 |X 3 ) + inf x2∈X2 x 3 -x 2 2 .
Taking the infimum over x 3 ∈ X 3 , we obtain the claimed result.

A.3.2 Proof of Proposition 2

Proof. Under Assumptions 1 and 2, the function J is lower semi-continuous for the weak-* topology. The existence of a measure µ supported on V with J(µ) < +∞ and the coercivity of J therefore ensures the existence of a primal solution. We then invoke Theorem [2, 9.8.1] to conclude on the existence of a dual solution, the extremality relationships and on the fact that there is no duality gap.

For the boundedness of the primal solution set in total variation norm, it suffices to use the fact that J is coercive, ensuring boundedness of its sub-level sets. Now let us prove the boundedness of the dual solution set. To this end, notice that by convexity, f is continuous at any point in int(dom(f )). In particular, f is continuous at Aµ. Using Proposition 1.3.9 in [START_REF] Hiriart-Urruty | Convex analysis and minimization algorithms II: Advanced Theory and Bundle Methods[END_REF], we conclude that g * (q)

def.

= f * (q) -Aµ, q

is coercive. We have f * (q) ≥ g * (q) -µ M(V) A * q L ∞ (V) . Hence f * is coercive on the admissible set for which f * (q) ≥ g * (q) -µ M(V) . This ensures the boundedness of the dual solution set.

A.3.3 Proof of Proposition 3

Proof. Any choice of κ 1 (q k , ω) in [START_REF] Chizat | Sparse optimization on measures with over-parameterized gradient descent[END_REF] satisfying the Lipschitz inequality sup x1,x2∈ω

|A * q k (x 1 )| -|A * q k (x 2 )|

x 1 -x 2 2 ≤ κ 1 (q k , ω) also satisfies |A * q k |(ω) ≥ A * q k L ∞ (ω) , i.e. Assumption 4. We have sup x1,x2∈ω

|A * q k (x 1 )| -|A * q k (x 2 )|

x 1 -x 2 2 = sup x∈ω |A * q k | (x),
where we consider that |A * q k | (x) = 0 on the points of non differentiability of |A * q k |. To obtain the expression (8), we use a Hölder inequality:

sup x∈ω |A * q k | (x) = sup x∈ω M m=1 q k [m]a m (x) ≤ M m=1 |q k [m]| sup x∈ω |a m |(x). (33)
Showing that Assumption 5 is not always valid stems from the fact that we use a 0-th order Taylor expansion, with a remainder that is therefore of first order only.

f (x) -f (y) 2 ≤ κ 2 x -y 2 . ( 35
)
The value κ 2 (q k , ω) is an upper-bound on the Lipschitz constant of (A * q k ) restricted to ω. Indeed, Proof. Now, let us prove that

|A * q k |(ω) -κ 2 (q k , ω) diam(ω) 2 ≤ A * q k L ∞ (ω) ≤ |A * q k |(ω). (37)
By equation ( 34), we get

|A * q(x) -A * q(v) -(A * q) (v), x -v | ≤ κ 2 (q k , ω) x -v 2 2 2 .
It follows

|A * q(x)| ≤ |A * q(v) + (A * q) (v), x -v | + κ 2 (q k , ω) x -v 2 2 2 ,
Taking first the supremum in x and then the infimum over the vertices v yields the right-hand side of (37). We also have |A * q(x)| ≥ |A * q(v) + (A * q) (v), x -v | -κ 2 (q k , ω) diam(ω) 2 2

≥ |A * q(v) + (A * q) (v), x -v | + κ 2 (q k , ω)

x -v 2 2 2 -κ 2 (q k , ω) diam(ω) 2 .

Again, taking the supremum in x and then the infimum over the vertices v we obtain the left-hand side of (37). The right hand-side of (37) proves that the second order selection process satisfies Assumption 4, whereas the left hand-side proves that it obeys Assumption 5.

Proof of Proposition 5

Proof. We have for all v ∈ vert ω and x ∈ ω

(A * q k ) (x) -(A * q k ) (v) 2 ≤ κ 2 (q k , ω) x -v 2 ,
which implies

(A * q k ) (x) ≥ (A * q k ) (v) 2 -κ 2 (q k , ω) x -v 2 =⇒ inf x∈ω (A * q k ) (x) ≥ (A * q k ) (v) 2 -κ 2 (q k , ω) diam(ω).
Since this is true for every v ∈ vert(ω), we get

∇A * q k 2 (ω) ≤ inf x∈ω ∇A * q k (x) 2 ,
In other words, ∇A * q k 2 is a lower bound of (A * q k ) . Since κ 2 is an upper bound of the Lipschitz constant of (A * ) q k , ∇A * q k 2 (ω) is a lower bound of (A * q k ) . It follows that any cell ω that contains a point of For any u ∈ R D and any x ∈ Ω, we have

a m (x)u, u = a m (x) σ 4 -σ 2 u 2 2 + u, x -z m 2 ≤ a m (x) σ 4 max(σ 2 , x -z m 2
2 ) u 2 2 .

To conclude, it suffices to notice that for x ∈ ω a m (x) ≤ a m (dist(z m , ω))

x -z m 2 ≤ [dist(z m , ω) + diam(ω)] .

Figure 2 :

 2 Figure2: The behavior of the adaptive refinement algorithm with a second order selection process, on a 1D sparse recovery problem. The set Ω k is displayed in green, the function |A * q k | is displayed in dashed red, the upper-bound |A * q k | is the piecewise-constant function. Observe that it always dominates |A * q k |. The algorithm starts with a burn-in period of 4 iterations. There, it refines all cells uniformly since the upper-bound is highly inaccurate. After a while, only the cells around the locations X get refined in a multiscale fashion.

(a) |V1| = 9 (

 9 b) |V2| = 25 (c) |V3| = 81 (d) |V4| = 289 (e) |V5| = 951 (f) |V6| = 1210 (g) |V7| = 1246 (h) |V8| = 1512 (i) |V9| = 1529 (j) |V10| = 1545 (k) |V11| = 1770 (l) |V12| = 1773 (m) |V13| = 1776 (n) |V14| = 1787 (o) |V15| = 2042 (p) |V16| = 2045

  Figure4: Our algorithm's behavior on a 2D example for second-order selection rules. The set Ω k is displayed in green, the superlevelset 1 of |A * q k | is filled with red, the level-set 0.9 is represented with a dashed red line and levelset 0.75 with a dotted red line. The algorithm starts with a burn-in period of 3 iterations. There, it refines all cells uniformly since the upper-bound is highly inaccurate. Then, only the cells around the locations of X get refined in a multiscale fashion. Remember that only the cells in Ω * k with largest diameter are refined. This explains the behavior of the algorithm between, e.g. Figures4f and 4g.

(a) |V1| = 9 (

 9 b) |V2| = 25 (c) |V3| = 81 (d) |V4| = 289 (e) |V5| = 951 (f) |V6| = 1210 (g) |V7| = 1246 (h) |V8| = 1512 (i) |V9| = 1529 (j) |V10| = 1545 (k) |V11| = 1766 (l) |V12| = 1769 (m) |V13| = 1780 (n) |V14| = 2035 (o) |V15| = 2038 (p) |V16| = 2041

  ) in Proposition 13 to control |Ω k,0 |. It states that all cells in Ω k,0 have an edge-length larger than r. The volume of a cell of edge-length r is r D . Since all the cells are disjoint and contained in Ω, we get |Ω k,0 | ≤ vol(Ω)/r D = r -D . Now let us derive a bound for |Ω k,s |. Let ω(x) denote the cell in Ω k containing x and def.

A. 3 . 4

 34 Proofs of Proposition 4 and Proposition 5 Our proofs rely on the following well-known (see e.g. [26, Lemma 1.2.3, 1.2.4]) statements about Taylorexpansions. If f : C → R is a function on a convex domain C ⊆ R n with a κ 2 -Lipschitz continuous gradient, we have for x, y arbitrary |f (x) -f (y) -f (y), x -y | ≤ κ 2x -

XA. 3 . 5 -z m σ 2 a 2 σ 4

 35224 k will verify both |A * q k |(ω) ≥ 1 and ∇A * q k 2 (ω) ≤ 0. Hence Ω k verifies Assumption 4. It is clear that the Ω k of Definition 5 is included in the Ω k of Definition 4. Because the latter verifies Assumption 5, so does the former. Proof of Proposition 8Proof. We havea m (x) = -a m (x) x m (x) = a m (x) -σ Id + (x -z m )(x -z m ) T σ 4 .

Table 1 :

 1

Algorithm's behavior for the 1D super-resolution problem. Here, we set σ = 2/M , M = 20.

The title of this article is a reference to the seminal paper of J. Tropp on sparse approximation[START_REF] Tropp | Greed is good: Algorithmic results for sparse approximation[END_REF], which was itself a reference to the movie Wall Street of Oliver Stone.

Acknowledgement

AF acknowledges support from the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation. FdG and PW were supported by the ANR Micro-Blind (grant ANR-21-CE48-0008), by the ANR LabEx CIMI (grant ANR-11-LABX-0040) and the support of AI Interdisciplinary Institute ANITI funding, through the French "Investing for the Future PIA3" program under the Grant Agreement ANR-19-PI3A-0004.