Michel Chein

Michel Leclère

Entities and Surrogates in Knowledge Representation

Introduction

In a universe of discourse (or world), names are privileged accesses to information concerning entities in this universe of discourse. A name is generally a simple expression, e.g., for a person it can consist of a list of first names and family name(s), which is not necessarily sufficient to identify a person. Names, in outside world, are usually ambiguous references and additional information are needed in order to correctly identify a world entity.

The Unique Name Assumption (UNA) does not concern names in the usual meaning but identifiers within a computer system, and a name is simply an attribute of an identifier. UNA states that two different identifiers correspond to two different world entities. UNA is a fundamental property assumed in classical databases and also usually assumed in knowledge representation (e.g., in Description Logics [] or in Conceptual Graphs []). Assuming UNA implies that the designer of a base has to assign identifiers to elements of the world, in a way he has to solve identification problems before constructing its system.

UNA cannot be assumed in some situations, for instance for linking or merging databases independently built, and various identification problems have been considered in computer science since a long time (1959):

• Entity resolution, Reference reconciliation: which records represent the same entity, identifying multiple refs to the same object and distinguishing them from mentions of different objects

• de-duplication: duplicate data (object) is deleted (Classical problem: creation of mailing lists)

• merging records judged to represent the same world entity

• record linkage, linking records through refs to same world entities

• object identification is used as a generic term to single out, to distinguish, to recognize individual entities (objects) of the world in a computer system.

Most solutions of object identification problems, which are important for many kinds of databases (especially data warehouses) and also for (part of) the web, are based on classification techniques. In this approach, an entity is described by a list of attributes; attribute values are simple data types (e.g., strings or numbers) and approximate similarity measures are assigned for each kind of attributes vector; a similarity measure is built for lists of attributes (often it is a weighted combination of the attribute similarities); finally, a decision procedure allows to state when two lists of attributes represent the same entity. Recently, logical approaches have been developed (e.g., Fatiha Saïs, Nathalie Pernelle and M.-C.

Rousset consider data sources conforming to the same RDFS schema [START_REF] Saïs | L2r: A logical method for reference reconciliation[END_REF][START_REF] Saïs | Combining a logical and a numerical method for data reconciliation[END_REF]), our work also follows a logical approach.

A knowledge base (KB) is composed of logical constructs representing knowledge about a world. We assume that such a world can be modeled by using notions of (nave) set theory, e.g. elements, sets, relations, functions, and thus that knowledge about this set theoretical model are expressed by (a variant or a fragment) of first order logic. In this paper we are interested by identification problems concerning individual entities in world. These individual entities are represented by elements in the model and these elements are represented by special symbols called surrogates in the knowledge base. Surrogates should be in one-to-one correspondence with the set of world entities. Our aim is to define a KB faithful, or unambiguous, with respect to the identification of world entities and to propose mechanisms allowing a user to design, build, maintain such a KB, and also to repair an ambiguous KB. In this paper we consider individual entities, nevertheless similar identification problems occur for other notions such as classes of entities or relationships between entities.

We focus on digital libraries, which are specific knowledge bases, for several reasons. First, all the previous mentioned problems are important in the context of digital libraries. Some problems are induced by the evolution of digital libraries (e.g., adding notices to a base, merging bibliographic bases, maintenance of the different bases), other problems concern the quality of the notice bases (e.g., consistency inside and between bases, relevance of the subject). Secondly, a digital library is composed of several bases of notices: bibliographic notices and authority notices. A bibliographic notice gathers metadata concerning a document, an authority notice gathers metadata concerning an authority. An authority can be an author, a collectivity or a subject. International work is done to standardize these metadata (FRBR, ?) similar to light weight ontologies. Relationships between bibliographic notices and authority notices are represented by attributes in notices (e.g., authorOf, editorOf, ?). Thus, a digital library can be seen as a knowledge base having a graph structure. The problems expressed in our logical framework can be solved using graph techniques (rules, constraints, exact and approximate retrieval procedures cf. [CM09, ?, ?]?). Digital libraries allow to assess graph methods on large graphs (several dozen of millions of nodes) and to compare them to classification methods.

Logical Framework

In this section we present a first order logical framework aiming at representing object identification problems.

The language L

The KR language (L) used is a variant of FOL and more precisely a variant of the language L introduced by Levesque and Lakemeyer [START_REF] Levesque | The Logic of Knowledege Bases[END_REF]. Terms are used for representing entities in the application domain. We assume that there are no functional symbols in the KR language.

Definition 1 (Symbols and Vocabulary) The set of symbols is composed of a set of logical symbols and a set of non logical symbols also called vocabulary. The set of logical symbols consists of the following distinct sets:

• X a countably infinite set of variables,

• S a countably infinite set of surrogates, which is partitioned into an infinite set of literal surrogates and an infinite set of individual surrogates, S = L + E,

• the equality symbol =,

• the connectives ∃, ∀, ∧, →, ↔ and the brackets ( and )

The vocabulary or set of non-logical symbols consists of two distinct sets:

• C the (ordinary) constants (i.e., function symbols of arity 0).

• P the predicate symbols (of any arity > 0)

Definition 2 (Terms) A term is either a variable or a surrogate or a constant.

Literals surrogates (literal in short whenever there is no ambiguity) are used for representing entities such as integers, strings, dates and so on, e.g., int 3 represents the integer 3 and string abc represents the string "abc . We assume that there is a consensus about the meaning of a literal, i.e., a literal does not need a definition, its meaning is directly given by its syntax. This is not the case for individual surrogates (individual in short whenever there is no ambiguity). An individual has no meaning by itself, it is simply a symbol; individuals are noted by strings beginning by #, e.g., #12. The fundamental property of individuals is that they represent the elements of the universe of discourse. Thus, we only know that #12 and #25 represent different entities in the universe of discourse and if one wants to express what distinguish #12 from #25 one has to represent knowledge concerning the individuals #12 and #25. A constant corresponds to an alias for an individual, e.g., abc or Charles De Gaulle or Le General can be aliases for #121443 which is the individual representing in the system the French well-known personality. Constant are noted by strings disjoint from surrogates and variables. Please note that the Charles De Gaulle constant is a non-logical symbol different from the literal surrogate String Charles De Gaulle which might represent the name of the person represented into the system by the individual surrogate #121443.

Definition 3 (Formulas) An atom is either p(t 1 , ..., t k ), where p is a predicate and t i is a term, or t = t (equality atom), where t and t are terms. Formulas in L are defined from atoms and connectives in the same way as in classical FOL. We mainly use specific formulas defined as follows:

• A conjunct is a conjunction of atoms. A conjunct can be identified as a set of atoms.

• An ∃∧formula is the existential closure of a conjunct without equality atoms.

• An ∃∧ =formula is the existential closure of a conjunct.

• A range restricted rule (rr-rule) is a formula ∀X(H → A) where H is a conjunct without equality atoms, A is an atom and var(A) ⊆ var(H) ⊆ X. Two kinds of rr-rules are distinguished: P -rule where A is an atom built from a predicate in P and =rule where A is an equality atom.

• An individual definition for an individual e ∈ E, is a formula ∀X(H ↔ (x = e)) where H is a conjunct without equality atoms, x ∈ X.

In the examples, the conjuncts, ∃∧formula and ∃∧ =formula will be represented by their set of atoms.

A knowledge base (KB) is composed of three sets of formula. More precisely, Definition 4 (Knowledge Base) A knowledge base over L is a 3-tuple K = (F, R, C) composed of three finite sets:

• a set of ∃∧ =formulas F, representing facts,

• a set of rr-rules R without constants and individuals, representing knowledge which can be applied to facts,

• a set of ∃∧formulas C without constants and individuals, representing negative constraints that facts should fulfill.

Note that, using conjunction, F can be assumed to be a single ∃∧ =formula.

Notations The set of variables, literals, individuals, surrogates, constants, terms, atoms in a formula A are, respectively, denoted var(A), lit(A), ind(A), surr(A), const(A), term(A) and atom(A). These notations are also used for a set of formulas or for a knowledge base.

Definition 5 (A * ) For any set of terms T , T * is the set of all equality between terms in T , (i.e., T * = {t = t | t ∈ T, t ∈ T }.

Let A be an ∃∧ =formula. Let C 1 , C 2 , . . . , C n be the equivalence classes of term(A) (wrt the equality), and for any term t ∈ term(A), let C(t) be the equivalence class of t.

A

* = {p(t 1 , ..., t k ) | p(t 1 , ..., t k ) ∈ atom(A), ∀i = 1, . . . , k, t i ∈ C(t i )} ∪ {C * i | i = 1, . . . , n}
Definition 6 (Normal form of a formula) For any equivalence class of terms T , norm(T ) is the subset of T defined as follows:

• If T only contains variables, then let x be a variable in T , norm(T ) = {x} (one keeps one variable).

• If T contains (at least) a variable and (at least) a constant or surrogate, then norm(T ) = T \ X (all variables are removed).

• If T only contains constants or surrogates norm(T ) = T .

Let A be an ∃∧ =formula. Let C 1 , C 2 , . . . , C n be the equivalence classes of term(A) (wrt the equality), and for any term t ∈ term(A), let C(t) be the equivalence class of t. The normal form of A, noted norm(A) is defined by: norm

(A) = {p(t 1 , ..., t k ) | p(t 1 , ..., t k ) ∈ atom(A), ∀i = 1, . . . , k, t i ∈ norm(C(t i ))} \ {t = t | t ∈ term(A)}.
Note that there is no equality atoms containing variables nor valid atoms (t = t) in norm(A). Thus, if A is a set of valid atoms, norm(A) is the empty set of atoms. Furthermore, A ⊆ A * , norm(A) ⊆ A * and if A doesn't contain any equality atoms, then A = A * = norm(A). norm(A) is a canonical form of A up to a variable renaming.

Comment The last point should be clarified: let A and B be two ∃∧ =formula, if norm(A) = norm(B) then A ≡ B but the converse is not true! Example Let A = {p(x), q(y), q(w), p(z), q(c 2 ), r(s 3 , s 1 ), x = s 1 , c 1 = x, y = z, s 2 = c 2 } be a fact (where w, x, y, z are variables, c 1 , c 2 are constants and s 1 , s 2 , s 3 are surrogates), then A * = A ∪ {p(s 1 ), p(c 1 ), q(z), p(y), q(s 2 ), r(s 3 , c 1 ), r(s 3 , x),

s 1 = s 1 , c 1 = c 1 , x = x, s 1 = x, x = c 1 , c 1 = s 1 , s 1 = c 1 , y = y, z = z, z = y, s 2 = s 2 , c 2 = c 2 , c 2 =
s 2 , s 3 = s 3 , w = w} and norm(A) = {p(s 1 ), p(c 1 ), q(y), q(w), p(y), q(s 2 ), q(c 2 ), r(s 3 , s 1 ), r(s 3 , c 1 ),

c 1 = s 1 , s 1 = c 1 , c 2 = s 2 , s 2 = c 2 }

Interpretation and Model of a KB

The interpretation domain is the set of surrogates S = L + E.

Definition 7 (Interpretation) An interpretation of L is a mapping I from S + C + P to S * such that:

• for all surrogate s in S: I(s) = s,

• I(=) is the equality on S,

• for all constant c in C: I(c) ∈ E,

• for all k-ary predicate p in P : I(p) ⊆ S k .

Two interpretations may only differ by the interpretation of non logical symbols, i.e., elements in the vocabulary. Thus, one can speak of the interpretation of a language or of a vocabulary.

Definition 8 Let us consider a finite vocabulary V = (C, P ) (i.e., C and P are finite). An interpretation I is finite if for any p in P , I(p) is finite.

The semantics of the logical connectives are defined in the same way as in classical FOL. Thus, it is straightforward to define a model of a formula A as well as the logical consequence noted |= or the logical equivalence ≡.

Property 1 Let A be an ∃∧ =formula then A * ≡ A and norm(A) ≡ A.

Definition 9 (Model of a knowledge base)

An interpretation I is a model of a knowledge base K = (F, R, C) if • I is a model of (F, R),
• I is not a model of any C in C.

Grounded and Well-grounded KBs

A (satisfiable) KB is grounded if the interpretation of a constant is the same individual in all models of the knowledge base and this means that (in a grounded knowledge base) the constants are aliases of the individual surrogates.

Definition 10 (Grounded knowledge base) A satisfiable knowledge base K = (F, R, C) is grounded if: for each constant c in const(K), there is an individual surrogate e in ind(K) such that for any model

I of K I(c) = e.
As said in section 2.1, the two types of surrogates (i.e., literals and individuals) are semantically different. A literal directly refers to an element in the domain, while an individual surrogate means nothing. An identification formula give meaning to an individual, such a formula is a definition of an individual.

Definition 11 (Well-grounded) An individual surrogate e is well-grounded wrt a base K if there is an identification formula Id e = ∀X(N SC(x) ↔ (x = e)) such that K |= Id e . A grounded knowledge base K is well-grounded if each individual surrogate e in K is well-grounded.

Comment e is well-grounded means that any model of K is a model of N SC(e), and that in any model of N SC(x) the only possible value of x is e. Indeed, ∀X(N SC e (x) ↔ (x = e)) ≡ N SC e (e) ∧ ∀X(N SC e (x) → (x = e)).

In such a situation, K is said to be well-grounded with respect to the set ID K = {Id e | e ∈ ind(K)} of identification formulas associated with the individual surrogates of K.

Checking problems

In this framework, one can define several checking problems.

Problem 1 Let K be a knowledge base, check if K is satisfiable.

Problem 2 Let K be a satisfiable knowledge base, check if K is grounded.

Problem 3 Let K be a grounded knowledge base and a set of identification formulas Id, check if K is well-grounded with respect to Id.

Problem 4 Let K be a grounded knowledge base, check if K is well-grounded (and give an Id).

Reasoning with Homomorphism

In this section, the notions dealing with homomorphism introduced in [START_REF] Baget | On rules with existential variables: Walking the decidability line[END_REF] for classical FOL are adapted to the previous framework.

Homomorphism

Definition 12 (substitution) Given a set of variables X and a set of terms T , a substitution σ of X by T is a mapping from X to T . Given a conjunct C, σ(C) denotes the conjunct obtained from C by replacing each occurrence of x ∈ X ∩ var(C) by σ(x). If a fact A is the existential closure of a conjunct C, then σ(A) is the existential closure of σ(C).

Definition 13 (homomorphism) A homomorphism from a fact A to a (possibly infinite) fact B is a substitution σ of var(A) by term(B) such that σ(A) ⊆ B.

Note that there is a homomorphism from a fact A to its equivalent forms A * and norm(A).

Theorem 1 Let A and B be two facts. B |= A if and only if there is a homomorphism from norm(A) to norm(B).

Rule application

Remember that a rule hypothesis H (the same remark holds for the constraints) doesn't contain any equality atoms. Thus, we have H = H * = norm(H).

Definition 14 (Application of a rr-rule) Let F be a fact and R = (H, A) be a rr-rule. R is said applicable to F if there is a homomorphism, say π, from H to norm(F ). In that case, the application of R to F according to π produces a fact α(F, R, π) = F ∪ π(C). α(F, R, π) is said to be an immediate derivation from F . This rule application is said to be redundant if α(F, R, π) ≡ F .

To check whether α(F, R, σ) ≡ F , one can check that norm(α(F, R, σ)) maps to norm(F ).

Definition 15 (Derivation) Let F be a fact and R be a set of rr-rules. A fact F is called an R-derivation of F if there is a finite sequence (called the derivation sequence)

F = F 0 , F 1 , . . . , F k = F such that for all 1 ≤ i ≤ k, there is a rule R = (H, C) ∈ R and a homomorphism π from H to norm(F i-1 ) with F i = α(F i-1 , R, π), i.e., F i is an immediate derivation from F i-1 .
Definition 16 (Closure wrt R) Let R be a set of rr-rules, a fact F is said closed wrt R iff any application of a rule in R to F leads to a fact F equivalent to F. Given a fact F and a set of rules R, a closure of F wrt R is a closed fact (wrt to R) that is a R -derivation of F .

Property 2 Let F be a fact and R be a set of rr-rules: (i) there always exists a closure of F wrt R, (ii) all closures of F wrt R are logically equivalent, and (iii) the normal form of all closures of F wrt R are identical.

Definition 17 (R(F)) Let F be a fact and R be a set of rules, R(F) denotes the normal form of any closure of F wrt to R.

Theorem 2 (Saturation) Let F and F be two facts and R be a set of rr-rules. Then F, R |= F if and only if there is a homomorphism from norm(F ) to R(F ) 2.5.3 Satisfiability, Grounded and well-grounded properties Property 3 A knowledge base K = (F, R, C) is satisfiable iff: (i) there is at most one surrogate in any equivalence class of R(F) and (ii) for any C in C there is no homomorphism from C to R(F).

Definition 18 (Identity property) A knowledge base K = (F, R, C) has the identity property if each equivalence classe of terms in R(F) that contains a constant also contains an individual surrogate.

Property 4 A satisfiable knowledge base is grounded if and only if it fulfills the identity property. I is a model of K and since I (c) = I(c), K is not grounded.

Property 5 An individual surrogate e is well-grounded wrt a grounded knowledge base K = (F, R, C) iff there is an ∃∧formula F having a variable x such that:

• there is at least one homomorphism from F to R(F) and

• every homomorphism from F to R(F) maps x to e.

Graphical Framework

In order to solve these problems we use graph representation of formulas and graph homomorphisms.

Graph notions

Notions defined in this section are adapted from notions defined in [START_REF] Chein | Graph-based Knowledge Representation[END_REF].

Definition 19 (G-vocabulary) A G-vocabulary is a pair (T, P ) where T and P are two pairwise disjoint sets. T is a set of terms and P is a set of predicates of arity 1, ...k.

Definition 20 (Graph) A graph defined over a vocabulary (T, P ) is a 4-tuple G = (C, R, E, l) satisfying the following conditions:

• (C,R,E) is a bipartite multigraph. C is the concept node set, R is the relation node set and E is the family of edges.

• l is a labeling function of nodes and edges that satisfies:

1. A concept node is labeled by a set (possibly empty) of terms in T .

2. A relation node is labeled by a predicate in P .

3. The degree of a relation node is equal to the arity of its label.

4. Edges incident to a relation node labeled r are totally ordered and they are labeled from 1 to k (the arity of r).

Such a graph looks like a BG-graph on a flat vocabulary where the markers are sets of terms. A concept node labeled by the empty set is called a generic concept node Definition 21 A normal graph is a graph such all labels of concept nodes are pairwise disjoint and without twin relations. The normal form norm(G) of a graph G is the normal graph obtained by merging the concept nodes having a non empty intersection of their label (the label of a node resulting from a merging is the union of the labels of the merged nodes) and by deleting twin relations.

Other notions defined in [START_REF] Chein | Graph-based Knowledge Representation[END_REF] can be easily extended to the graphs defined in this section. The central notion of graph homomorphism can be defined as follows.

Definition 22 (Graph Homomorphism) Let G = (C G , R G , E G , l G ) and H = (C H , R H , E H , l H ) be two graphs defined over the same vocabulary. A homomorphism π from G to H is a mapping from C G to C H and from R G to R H such that:

• ∀(r, i, c) ∈ G, (π(r), i, π(c)) ∈ H,

• ∀r ∈ R G , l H (π(r)) = l G (r),

• ∀c ∈ C G , l H (π(c)) ⊇ l G (c)
If there is a homomorphism (say π) from G to H, we say that G maps or projects to H (by π). An atomic rule is an ordered pair R = ((c 1 , ...c n )H, p) where the c i are concept nodes (not necessarily distinct) in the graph H and p is a predicate of arity n.

Application of a rule graph can now be defined.

Definition 24 (Application of an equality rule) Let G be a graph and R = ((c, c ), H) be an equality rule. R is applicable to G if there is a homomorphism π from H to G. In this case, the result of the application of R to G according to π is the graph G = (R, π)G obtained from G by merging π(c) and π(c ).

Definition 25 (Application of an atomic rule) Let G be a graph and R = ((c 1 , ...c n )H, p) be an atomic rule. R is applicable to G if there is a homomorphism π from H to G. In this case, the result of the application of R to G according to π is the graph G = (R, π)G obtained from G by adding a new relation node labeled p whose i-th neighbor is π(c i ) for i = 1, . . . , n.

Proof:

  Let K = (F, R, C) be a satisfiable knowledge base. (⇐) Let I be any model of K. For any constant c in const(K), we note e c the single individual surrogate belonging to the equivalence class of c. Thus, I(c) = I(e c ) = e c , the interpretation of c is the same for any I. (⇒) Proof by contradiction. Let K be a satisfiable and grounded knowledge base. Let us assume that a constant c belongs to an equivalence class which does not contain an individual surrogate. Since K is grounded there is an individual surrogate e which is the interpretation of c in any model I of K. Let I be a model of K, a model I with I (c) = I(c) can be built as follows:• choose e in E -ind(K) different from e;• for each constant c equivalent to c, I (c ) = e , and for all other constant c", I (c") = I(c");• for all p in P , I (p) is the union of I(p) and the set of tuples obtained by substituting e to e in I(p).

  Let c and d be two concept nodes of a graph G. The merging operation of c and d consists of identifying the two nodes c and d into a new node having the label l(c) ∪ l(d). One now defines rules and rule applications and w.l.g. one only considers rules with at most one relation node in the conclusion. Definition 23 (G-rule) The two following kinds of graph rules are considered. An equality rule is an ordered pair R = ((c, c ), H) where c and c are distinct (generic) concept nodes in the graph H.

Relationships between formulas and graphs

Simple relationships between logical notions presented in Sect. 2 and graphical notions presented in Sect. 3 allow to solve problems concerning formulas by graph algorithms based on graph homomorphism.

Definition 26 (Graph of a Fact) The graph of a fact A is the normal graph graph(A) obtained as follows.

1. Create a concept node for each equivalence class of terms. Each concept node is labeled by the set of surrogates and constants belonging to the equivalence class and by the empty set if the equivalence class only contains variables.

2. From each atom p(t 1 , ...t k ), adds a relation node r labeled p with k edges labelled from 1 to k that link r to the k concept nodes resp. associated with the equivalence class of t 1 , ...t k .

3. Delete twin relation nodes.

Note that graph(A) = graph(norm(A)) and, more generally, for any fact B, such as norm(B) = norm(A), one has graph(B) = graph(A).

Theorem 3 There is a bijection between the set of normal facts (up to a renaming of the variables) on the vocabulary (C, P ) and the normal graphs on the vocabulary (C ∪ S, P ). The same result holds for rr-rules and G-rules. There is a homomorphism from a normal fact A to a normal fact B iff there is a homomorphism from graph(A) to graph(B). A rr-rule is applicable to a fact A iff the associated G-rule is applicable to graph(A). etc. Comment To finish...


Jean B Lasserre

THE K-MOMENT PROBLEM FOR CONTINUOUS LINEAR FUNCTIONALS

Keywords: 1991 Mathematics Subject Classification. 44A60 13B25 14P10 30C10 Moment problems, real algebraic geometry, positive polynomials, semi-algebraic sets. 1

Given a closed (and non necessarily compact) basic semialgebraic set K ⊆ R n , we solve the K-moment problem for continuous linear functionals. Namely, we introduce a weighted ℓ1-norm ℓw on R[x], and show that the ℓw-closures of the preordering P and quadratic module Q (associated with the generators of K) is the cone Psd(K) of polynomials nonnegative on K. We also prove that P and Q solve the K-moment problem for ℓw-continuous linear functionals and completely characterize those ℓw-continuous linear functionals nonnegative on P and Q (hence on Psd(K)). When K has a nonempty interior we also provide in explicit form a canonical ℓw-projection g w f for any polynomial f , on the (degree-truncated) preordering or quadratic module. Remarkably, the support of g w f is very sparse and does not depend on K! This enables us to provide an explicit Positivstellensatz on K. At last but not least, we provide a simple characterization of polynomials nonnegative on K, which is crucial in proving the above results.

Introduction

This paper is concerned with basic closed semi-algebraic sets K ⊆ R n and the preordering P (g) and quadratic module Q(g) associated with the finite family of polynomials (g j ), j ∈ J, that generate K. In particular, when K = R n then the latter two convex cones coincide with the cone Σ[x] of sums of squares (s.o.s.) of polynomials. The convex cones P (g) and Q(g) (which are subcones of the convex cone Psd(K) of polynomials nonnegative on K) are of practical importance because on the one hand nonnegative polynomials are ubiquitous but on the other hand, polynomials in P (g) or Q(g) are much easier to handle. For instance, and in contrast with nonnegative polynomials, checking whether a given polynomial is in P d (g) (⊂ P (g)) or Q d (g) (⊂ Q(g)) (i.e., with an a priori degree bound d on its representation) can be done efficiently by solving a semidefinite program, a powerful technique of convex optimization.

The celebrated K-moment problem is concerned with characterizing all real sequences y = (y α ), α ∈ N n , which can be realized as the moment sequence of some finite Borel measure on K. For such sequences y, the linear form L y associated with y is called a K-moment functional and Haviland's theorem states that L y is a K-moment functional if and only if L y (f ) ≥ 0 for all f ∈ Psd(K). And so one says that P (g) (resp. Q(g)) solves the K-moment problem if the K-moment functionals are those which satisfy L y (f ) ≥ 0 on P (g) (resp. Q(g)). However, this is true if and only if P (g) (resp. Q(g)) is dense in Psd(K) for the finest locally convex topology on R[x]. When K is compact, the K-moment problem was completely solved (with P (g) = Psd(K)) in Schmüdgen [START_REF] Schmüdgen | The K-moment problem for compact semi-algebraic sets[END_REF] and soon refined to Q(g) = Psd(K) in Putinar [START_REF] Putinar | Positive polynomials on compact sets[END_REF] for Archimedean quadratic modules Q(g).

Since then, recent contributions have tried to better understand (in even a more general framework) the links between Psd(K) and closures (and sequential closures) of preorderings and quadratic modules, one important goal being to extend (or provide analogues of) Schmüdgen and Putinar's Positivstellensatzë [START_REF] Schmüdgen | The K-moment problem for compact semi-algebraic sets[END_REF][START_REF] Putinar | Positive polynomials on compact sets[END_REF] to cases where K is not compact. In particular, Scheiderer [START_REF] Scheiderer | Positivity and sums of squares: A guide to recent results[END_REF] has shown rather negative results in this direction. For more details on those recent results, the interested is referred to e.g. Powers and Scheiderer [START_REF] Powers | The moment problem for non-compact semialgebraic sets[END_REF], Kuhlmann and Marshall [START_REF] Kuhlmann | Positivity sums of squares and the multidimensional moment problem[END_REF], Kuhlmann et al. [START_REF] Kuhlmann | Positivity sums of squares and the multidimensional moment problem II[END_REF], and Cimpric et al. [START_REF] Cimpric | Closures of quadratic modules[END_REF].

On the one hand, all linear functionals are continuous in the finest locally convex topology, on the other hand, the negative results of Scheiderer [START_REF] Scheiderer | Positivity and sums of squares: A guide to recent results[END_REF] suggest that solving the K-moment problem via preorderings or quadratic modules is possible only in specific cases, and so this topology is not the most appropriate in general. So why not rather consider other topologies on R[x] and the K-moment problem for linear functionals L y that are continuous for these topologies? This is the point of view taken in Ghasemi et al. [START_REF] Ghasemi | The moment problem for continuous positive semidefinite linear functionals[END_REF] where the authors consider certain (weighted) norm-topologies and show that the closure of the cone of sums of squares is Psd([-1, 1] n ) as did Berg [START_REF] Berg | The multidimensional moment problem and semigroups[END_REF] for the ℓ 1 -norm. Notice that this was also the point of view taken in Schmüdgen [START_REF] Schmüdgen | Positive cones in enveloping algebras[END_REF] for a class of non commutative (enveloping) * -algebra; in the latter context [START_REF] Schmüdgen | Positive cones in enveloping algebras[END_REF], the author proves that the cone of strongly positive elements is the closure of the (smallest) cone of sums of squares in certain topologies.

Contribution. In view of the negative results in Scheiderer [START_REF] Scheiderer | Positivity and sums of squares: A guide to recent results[END_REF], we also consider the above mentioned viewpoint and look at the K-moment problem by using a particular weighted ℓ 1 -norm on R[x] (denoted ℓ w for a certain sequence w : N n → R >0 ) rather than the usual finest locally convex topology. In this framework we solve the K-moment problem for basic closed semi-algebraic sets K ⊆ R n in the following sense. We prove that (a) the ℓ w -closure of P (g) and Q(g) is exactly Psd(K), and (b) P (g) and Q(g) solve the moment problem, i.e., the K-moment (ℓ w -continuous) functionals are those L y that are ℓ w -continuous and nonnegative on Q(g) (or P (g)). In fact, such linear functionals L y are characterized by: -L y (h 2 g j ) ≥ 0 for all h ∈ R[x], and every generator g j of K.

-∃M > 0 such that |y α | ≤ M w α for all α ∈ N n .

• Next, when K has a nonempty interior, there exist ℓ w -projections of a polynomial onto P d (g) and Q d (g), where P d (g) (resp. Q d (g)) denotes the subcone of elements of P (g) (resp. of Q(g)) which have a degree bound d in their representation. In general these projections are not unique but we provide a canonical ℓ w -projection g f for any polynomial f , which takes a remarkably simple and "sparse" form, and particularly when ℓ w is the usual ℓ 1 -norm, in which case (1.1)

g f = f + λ 0 + n i=1 λ i x 2d i ,
for some nonnegative vector λ ∈ R n+1 . In other words, the support g f 0 of g f does not depend on K and does not depend on d either! The dependence of g f on the g j 's that define K is only through the coefficients (λ * j ). In addition, the support is very sparse since g f 0 ≤ f 0 +n+1. This confirms the property of the ℓ 1 -norm with respect to sparsity, already observed in other contexts. Minimizing the ℓ 1 -norm aims at finding a solution with small support (where x 0 = #{i : x i = 0}). Finally, the vector λ in (1.1) is an optimal solution of an explicit semidefinite program, and so can be computed efficiently.

• We also provide a canonical ℓ 1 -projection of f onto P (g) ∩ R[x] 2d which is again of the form (1.1), and use this result to characterize the sequential closure P (g) ‡ of P (g) for the finest locally convex topology. Namely,

P (g) ‡ = f ∈ R[x] : ∃ d s.t. ∀ǫ > 0, f + ǫ 1 + n i=1 x 2d i ∈ P (g) ,
and the same statement is true for the quadratic module Q(g). This latter result exhibits the particularly simple form q := (1 + n i=1 x 2d i ) for the possible polynomials q in the characterization of P (g) ‡ (and Q(g) ‡ ) provided in e.g. [START_REF] Cimpric | Closures of quadratic modules[END_REF][START_REF] Kuhlmann | Positivity sums of squares and the multidimensional moment problem II[END_REF]; e.g., in [START_REF] Kuhlmann | Positivity sums of squares and the multidimensional moment problem II[END_REF] it is stated that one may take the polynomial (1 + x 2 ) s for some s.

• Thanks to the characterization of canonical ℓ w -projections, we finally obtain a Positivstellensatz on K of the following form: f ∈ Psd(K) if and only if for every ǫ > 0, there is some d ∈ N such that the polynomial

f + ǫ(1 + n i=1 d k=1 x 2k i /(2k)!) is in P (g) (or Q(g)).
• At last but not least, and crucial for the above results, we prove a result of independent interest, concerned with sequences y = (y α ), α ∈ N n , that have a finite representing Borel measure µ. Namely, we prove that a polynomial f is nonnegative on the support of µ if and only if

h 2 f dµ ≥ 0 for all h ∈ R[x].
The paper is organized as follows. In Section 2, and after introducing the notation and definitions, we present the intermediate result mentioned above. In Section 3 we show that P (g) and Q(g) solve the K-moment problem for ℓ w -continuous linear functionals. In section 4, we provide explicit expressions for the canonical ℓ w -projections onto P (g), Q(g) and their truncated versions. Moreover, we characterize the sequential closures Q(g) ‡ and P (g) ‡ and we end up with a Positivstellensatz for K. For every i ∈ N, let

Notation, definitions and preliminaries

N n d := {β ∈ N n : j β j ≤ d} whose cardinal is s(d) = n+d n . A polynomial f ∈ R[x] is written x → f (x) = α∈N n f α x α ,
and f can be identified with its vector of coefficients f

= (f α ) in the canonical basis (x α ), α ∈ N n . The support of f ∈ R[x] is the set {α ∈ N n : f α = 0} and let f 0 := card {α : f α = 0}. Denote by f 1 the ℓ 1 -norm α |f α | of the coefficient vector f .
Crucial in the sequel is the use of the following ℓ w -norm which is a weighted ℓ 1 -norm defined from the sequence w = (w α ), α ∈ N n , where w α := (2⌈|α|/2⌉)!. Namely, denote by f w the ℓ w -norm α w α |f α | of the coefficient vector f ; hence the ℓ 1 -norm corresponds to the case where w α = 1 for all α ∈ N n . Both ℓ 1 and ℓ w also define a norm on R[x] d .

Let S p ⊂ R p×p denote the space of real p × p symmetric matrices. For any two matrices A, B ∈ S p , the notation A 0 (resp. ≻ 0) stands for A is positive semidefinite (resp. positive definite), and the notation A, B stands for trace AB.

Let v d (x) = (x α ), α ∈ N n d , and let B 0 α ∈ R s(d)×s(d) be real symmetric matrices such that (2.1)

v d (x) v d (x) T = α∈N n 2d x α B 0 α .
Recall that a polynomial g ∈ R[x] 2d is a s.o.s. if and only if there exists a real positive semidefinite matrix X ∈ R s(d)×s(d) such that

g α = X, B 0 α , ∀α ∈ N n 2d . Let g j ∈ R[x]
, j = 0, 1, . . . , m, with g 0 being the constant polynomial g 0 (x) = 1 for all x, and let K ⊆ R n be the basic closed semi algebraic set:

(2.2)

K := {x ∈ R n : g j (x) ≥ 0, j = 1, . . . , m},
For every J ⊆ {1, . . . , m} let g J := k∈J g k , with the convention g ∅ := 1, and let v J := ⌈(deg g J )/2⌉ (with v j := v {j} ).

Definition 2.1. With K as in (2.2), let P (g), Q(g) ⊂ R[x] and P k (g), Q k (g) ⊂ R[x]
2k be the convex cones:

P (g) :=    J⊆{1,...,m} σ J g J : σ J ∈ Σ[x], J ⊆ {1, . . . , m}    , P k (g) :=    J⊆{1,...,m} σ J g J : σ J ∈ Σ[x] k-v J , J ⊆ {1, . . . , m}    , Q(g) :=    m j=0 σ j g j : σ j ∈ Σ[x], j = 1, . . . , m    , Q k (g) :=    m j=0 σ j g j : σ j ∈ Σ[x] k-v j , j = 1, . . . , m    .
The set P (g) (resp. Q(g)) is a convex cone called the preordering (resp. the quadratic module) associated with the g j 's. Obviously, if h ∈ P (g) (resp. h ∈ Q(g)), the associated s.o.s. weights σ J 's (resp. σ j 's) of its representation provide a certificate of nonnegativity of h on K. The convex cone

P k (g) (resp. Q k (g)) is the subset of elements h ∈ P (g) (resp. h ∈ Q(g)) with a degree bound 2k certificate. Observe that P k (g) ⊂ P (g) ∩ R[x] 2k and Q k (g) ⊂ Q(g) ∩ R[x] 2k . Moment matrix. With a sequence y = (y α ), α ∈ N n , let L y : R[x] → R be the linear functional f (= α f α x α ) → L y (f ) = α f α y α , f ∈ R[x].
With d ∈ N, the d-moment matrix associated with y is the real symmetric matrix M d (y) with rows and columns indexed in N n d , and defined by:

(2.3) M d (y)(α, β) := L y (x α+β ) = y α+β , ∀α, β ∈ N n d . Alternatively, M d (y) = α∈N n 2d y α B 0 α . It is straightforward to check that L y (g 2 ) ≥ 0 ∀g ∈ R[x] d ⇔ M d (y) 0, d = 0, 1, . . . .
A sequence y = (y α ) has a representing measure if there exists a finite Borel measure µ on R n , such that y α = x α dµ for every α ∈ N n . Moreover, the measure µ is said to be determinate if it is the unique such measure.

Notice that with the

ℓ w -norm on R[x] is associated a dual norm • * w on the dual space R[x] * of ℓ w -continuous linear functionals on R[x], by L y * w = sup{|y α |/w α : α ∈ N n }.
Localizing matrix. With y as above, J ⊆ {1, . . . , m}, and g J ∈ R[x] (with g J (x) = γ g Jγ x γ ), the localizing matrix of order d associated with y and g J is the real symmetric matrix M d (g J y) with rows and columns indexed by N n d , and whose entry (α, β) is just (2.4)

M d (y)(g J y)(α, β) := L y (g J (x)x α+β ) = γ g Jγ y α+β+γ , ∀α, β ∈ N n d . If B J α ∈ S s(d) is defined by: (2.5) g J (x) v d (x) v d (x) T = α∈N n 2d+deg g J B J α x α , ∀x ∈ R n , then M d (g J y) = α∈N n 2d+degg J y α B J α . Alternatively, M d (g J y) = M d (z) where z = (z α ), α ∈ N n , with z α = L y (g J x α ). Multivariate Carleman's condition. Let y = (y α ), α ∈ N n , be such that M d (y) 0 for all d ∈ N. If for every i = 1, . . . , n, (2.6) ∞ k=1 L y (x 2k i ) -1/2k = ∞,
then y has a finite representing Borel measure µ on R n , which in addition, is determinate; see e.g. Berg [START_REF] Berg | The multidimensional moment problem and semigroups[END_REF].

Closures. For a set A ⊂ R[x] we denote by A the closure of A for the finest locally convex topology on R[x] (treated as a real vector space). With this topology, every finite-dimensional subspace of R[x] inherits the euclidean topology, so that A also denotes the usual euclidean closure of a subset A ⊂ R[x] d . Following Cimpric et al. [START_REF] Cimpric | Closures of quadratic modules[END_REF] and Kuhlmann et al. [START_REF] Kuhlmann | Positivity sums of squares and the multidimensional moment problem II[END_REF], we also denote by A ‡ the set of all elements of R[x] which are expressible as the limit of some sequence of elements of A, and so A ‡ is called the sequential closure of A, and clearly

A ⊆ A ‡ ⊆ A. If A ⊂ R[x] is a convex cone A ‡ = {f ∈ R[x] : ∃ q ∈ R[x] s.t. f + ǫ q ∈ A, ∀ǫ > 0 },
and in fact, q can be chosen to be in A. Moreover, if A has nonempty interior (equivalently, has an algebraic interior) then A ‡ = A.

Semidefinite programming. A semidefinite program is a convex (more precisely convex conic) optimization problem of the form inf

X { C, X : A X = b; X 0 },
for some real symmetric matrices C, X ∈ S p , vector b ∈ R m , and some linear mapping A : S p → R m . Semidefinite programming is a powerful technique of convex optimization, ubiquitous in many areas. A semidefinite program can be solved efficiently and even in time polynomial in the input size of the problem, for fixed arbitrary precision. For more details the interested reader is referred to e.g. [START_REF] Vandenberghe | Semidefinite programming[END_REF].

2.2.

A preliminary result of independent interest. Recall that in a complete separable metric space X, the support of a finite Borel measure

µ (denoted supp µ) is the unique smallest closed set K ⊆ X such that µ(X \ K) = 0. Theorem 2.2. Let f ∈ R[x]
and µ be a finite Borel measure with all moments y = (y α ), α ∈ N n , finite and such that for some M > 0 and all k ∈ N and all i = 1, . . . , n, L y (x 2k i ) ≤ (2k)! M . Then:

f ≥ 0 on supp µ ⇐⇒ h 2 f dµ ≥ 0 ∀h ∈ R[x] (2.7) ⇐⇒ M d (f y) 0, ∀d = 0, 1, . . . Proof.
(f y) = M k (z) for every k ∈ N, h 2 f dµ ≥ 0 ∀h ∈ R[x] ⇐⇒ M k (z) 0, ∀ k ∈ N.
This combined with the fact that z satisfies Carleman's condition yields that z is the moment sequence of a finite Borel measure ψ on R n , which in addition, is determinate. Therefore, (2.8)

z α = x α f (x)dµ(x) dν(x) = x α dψ(x), ∀α ∈ N n . Let Γ+ := {x : f (x) ≥ 0}, Γ -:= {x : f (x) < 0} and let µ = µ + + µ - with µ + (B) = µ(B ∩ Γ + ), µ -(B) = µ(B ∩ Γ -), for all B ∈ B.
Similarly, let ν = ν +ν -with ν + and ν -being the positive measures defined by ν + (B) = B f dµ + and ν -(B) = -B f dµ -, for all B ∈ B. Since µ + , µ -≤ µ, one has

x 2k i dµ + (x) ≤ x 2k i dµ(x) and x 2k i dµ -(x) ≤ x 2k i dµ(x),
for all i = 1, . . . , n and all k ∈ N. Therefore, again by Lemma 5.1, both ν + and ν -satisfy Carleman's condition (2.6) so that both are determinate. On the other hand, (2.8) can be rewritten,

x α dν + (x) = x α dν -(x) + x α dψ(x), ∀α ∈ N n ,
and so ν + = ν -+ ψ because ν + and ν -+ ψ are determinate. But then 0 = ν + (Γ -) ≥ ν -(Γ -) implies that ν -= 0, i.e., ν = ν + = ψ, and so the signed Borel measure ν is in fact a positive measure. This in turn implies that f ≥ 0 for all x ∈ supp µ \ G, where G ⊂ supp µ and µ(G) = 0. Notice that by minimality of the support , supp µ \ G = supp µ. Hence let x ∈ supp µ be fixed, arbitrary. As supp µ \ G = supp µ, there is sequence (x ℓ ) ⊂ supp µ \ G such that x ℓ → x as ℓ → ∞, and f (x ℓ ) ≥ 0 for all ℓ. But then continuity of f yields that f (x) ≥ 0.

Interestingly, as we next see, Theorem 2.2 yields alternative characterizations of the cone Psd(S) for an arbitrary closed set S ⊂ R n .

For a finite Borel measure µ (with all moments finite) and a polynomial f ∈ R[x], let µ f be the finite signed Borel measure defined by µ f (B) :=

→ exp(|x i |) is µ-integrable for all i = 1, . . . , n. Then with f ∈ R[x], f ∈ Psd(S) ⇐⇒ µ f ∈ Σ[x] * (2.9) Psd(S) = Θ * µ . (2.10)
Proof. Let y = (y α ), α ∈ N n , be the moment sequence of µ. Observe that for every i = 1, . . . , n, and all k ∈ N,

L y x 2k i (2k)! ≤ S exp (|x i |)dµ(x) ≤ M,
for some M > 0. Moreover, supp µ = S and so by Theorem 2.2, f ≥ 0 on S if and only if S h 2 f dµ ≥ 0 for all h ∈ R[x]. Equivalently, if and only if S σdµ f ≥ 0 for all σ ∈ Σ[x] (which yields (2.9)), or if and only if S f dµ σ ≥ 0 for all σ ∈ Σ[x], which yields (2.10).

The K-moment problem for ℓ w -continuous linear functionals

We first show that Q(g) (and P (g)) solve the K-moment problem for ℓ w -continuous linear functionals.

When equipped with the ℓ w -norm, we may and will identify R[x] as the subspace of sequences with finite support, in the Banach space of real infinite sequences f = (f α ), α ∈ N n , that are w-summable, i.e., such that

α w α |f α | < +∞. Proposition 3.1. The dual of (R[x], • w ) is the space (R[x] * , • * w ) of linear functionals L y associated with the sequence y = (y α ), α ∈ N n , which satisfy L y * w < ∞, where L y * w := sup{|y α |/w α : α ∈ N n }. Proof. If L y ∈ R[x] * satisfies L y * w < ∞, then |L y (f )| ≤ α |f α | w α y α w α ≤ f w L y * w ,
and so L y is bounded, hence ℓ w -continuous. Conversely, if L y is ℓ w -continuous, then consider the sequence of polynomials (f α ) ⊂ R[x] with x → f α (x) := x α /w α for every α ∈ N n . Then f α w = 1 for every α ∈ N n , and L y (f α ) = y α /w α for all α ∈ N n . And so, if L y is ℓ w -continuous then sup{|y α |/w α :

α ∈ N n } < +∞. Theorem 3.2. Let K ⊆ R n be
L y (h 2 g j ) ≥ 0 ∀ h ∈ R[x], j = 0, . . . , m; sup α∈N n |y α | w α ≤ M for some M .
Proof. The necessity is clear. Indeed, if y has a representing measure µ on K then L y (h 2 g j ) = K h 2 g j dµ ≥ 0 for all h ∈ R[x] and all j = 0, 1, . . . , m; and so L y (f ) ≥ 0 for all f ∈ Q(g). Moreover, L y * w < ∞ because L y is ℓ w -continuous; hence (3.1) holds.

Sufficiency. Suppose that L y is a non trivial ℓ w -continuous linear functional, nonnegative on Q(g), i.e., suppose that (3.1) holds. In particular, L y (x 2k i ) ≤ M (2k)! for every k ∈ N and every i = 1, . . . , n. Therefore, y satisfies Carleman's condition (2.6) and since M k (y) 0 for all k ∈ N, y has a representing finite Borel measure µ on R n , which in addition, is determinate. Next, using L y (h 2 g j ) ≥ 0 for all h ∈ R[x], and invoking Theorem 2.2, one may conclude that g j ≥ 0 on supp µ, for every j = 1, . . . , m. Hence supp µ ⊆ K. Theorem 3.2 states that Q(g) solves the K-moment problem for ℓ wcontinuous functionals. Of course, Theorem 3.2 is also true if one replaces the quadratic module Q(g) with the preordering P (g).

The ℓ w -closure of Q(g) and P (g). Observe that Psd(K) is ℓ w -closed. To see this, notice that with every every x ∈ K is associated the Dirac measure δ x , whose associated sequence y = (x α ), α ∈ N n , is such that L y is ℓ w -continuous. Indeed, let a := max i |x i | so that |x α | ≤ a |α| , and let M := exp(a).

M -1 |y α | = exp(a) -1 |x α | ≤ exp(a) -1 a |α| < α! ≤ (2⌈|α|/2⌉)! = w α , and so L y * w < M , i..e., L y is ℓ w -continuous. Therefore, let (f n ) ⊂ Psd(K) be such that f n -f w → 0 as n → ∞. As L y is ℓ w -continuous one must have 0 ≤ lim n→∞ L y (f n ) = L y (f ) = f (x). As x ∈ K was arbitrary, f ∈ Psd(K). Theorem 3.3. Let K ⊆ R n be as in (2.2) and recall that Psd(K) := {f ∈ R[x] : f ≥ 0 on K}. Then cl w (P (g)) = cl w (Q(g)) = Psd(K).
Proof. As Psd(K) is ℓ w -closed and Q(g) ⊂ Psd(K), cl w (Q(g)) ⊆ Psd(K), and so we only have to prove the reverse inclusion. Let f ∈ cl w (Q(g)). Since Q(g) is a convex cone, by the Hahn-Banach separation theorem there exists an ℓ w -continuous linear functional L y that strictly separates f from cl w (Q(g)). That is, there exists y ∈ N n such that L y is ℓ w -continuous, L y (f ) < 0 and L y (h) ≥ 0 for all h ∈ cl w (Q(g)). By Theorem 3.2, such a y has a representing finite Borel measure µ on K, and so L y (f ) = K f dµ < 0 yields that necessarily f (x 0 ) < 0 for some x 0 ∈ K. Hence Psd(K) ⊆ cl w (Q(g)), which in turn yields the desired result.

For instance, from Berg [START_REF] Berg | The multidimensional moment problem and semigroups[END_REF], the ℓ 1 -closure of Σ[x] is Psd([-1, 1] n ). On the other hand, its ℓ w -closure is now Psd(R n ), which is what we really want.

It is worth mentioning that Theorem 3.2 and 3.3 can be extended to any preordering or quadratic module (finitely generated or not). The proof is the same. Any closed set K ⊂ R n may be represented as the non-negativity set of such a quadratic module (taking generators of the form x → g(x) := n i=1 (x ia i )r 2 , for suitable a ∈ R n and r > 0). However, for reasons that become obvious in the next section, the focus of the present paper is on the finitely generated case.

4. Canonical ℓ w -projections onto P d (g) and Q d (g) As we next see, the ℓ w -and ℓ 1 -norm have the nice feature that one may find particular (canonical) projections onto various truncations of P (g) and Q(g) with a particularly simple expression. For ℓ w -and ℓ 1 -projections to be well-defined we assume that K has a nonempty interior.

We first provide an explicit form of canonical ℓ 1 -and ℓ w -projection of any given polynomial f onto P d (g) and Q d (g) respectively, and analyze their limit as d → ∞. Then we will consider the projections onto P d (g) ∩ R[x] s for fixed s, d ∈ N, which, letting s → ∞, will permit to obtain the projection of f onto P (g) ∩ R[x] d , and so to also characterize the sequential closure P (g) ‡ .

As in the previous section, for a polynomial in R[x] t we use indifferently the notation h for both the polynomial and its vector of coefficients h ∈ R s(t) . The context will make clear which one of the two is concerned.

Let K ⊆ R n be as in (2.2) and consider the following optimization problem: (4.1)

p dw := inf h { f -h w : h ∈ P d (g) }.
That is, one searches for the best ℓ w -approximation of f by an element h * of P d (g), or equivalently, an ℓ w -projection of f onto P d (g). In general, such a best approximation h * ∈ P d (g) is not unique 1 but we provide a canonical solution with a very simple expression. Of course, and even though (4.1) is well defined for an arbitrary f ∈ R[x], such a problem is of particular interest when f is nonnegative on K but not necessarily an element of P (g).

p dw := inf λ,X J ,h α∈N n 2d w α λ α s.t. λ α + h α ≥ f α , ∀α ∈ N n 2d λ α -h α ≥ -f α , ∀α ∈ N n 2d h α - m J⊆{1,...,m} X J , B J α = 0, ∀α ∈ N n 2d λ ≥ 0; h ∈ R[x] 2d ; X J 0, ∀J ⊆ {1, . . . , m}.
The dual semidefinite program of (4.4) reads:

(4.5)            sup u,v≥0,y α∈N n d f α (u α -v α ) s.t. u α + v α ≤ w α ∀α ∈ N n 2d u α -v α + y α = 0 ∀α ∈ N n 2d , M d (g J y)
0, ∀J ⊆ {1, . . . , m}, or, equivalently, (4.6)

     sup y -L y (f ) s.t. M d (g J y) 0, ∀J ⊆ {1, . . . , m} |y α | ≤ w α , ∀α ∈ N n
2d . The semidefinite program (4.6) has an optimal solution y * because the feasible set is nonempty and compact. In addition, let y = (y α ) be the moment sequence of the finite Borel measure µ(B) = K∩B e -x 2 dx, for all B ∈ B, scaled so that |y α | < w α for all α ∈ N n 2d . Then (y, u, v) with u =min[y, 0] and v = max[y, 0], is strictly feasible in (4.5). Indeed, as K has nonempty interior, then necessarily M d (g J y) ≻ 0 for all J ⊆ {1, . . . , m}, and so Slater's condition 2 holds for (4.5). Therefore, by a standard duality result in convex optimization, there is no duality gap between (4.4) and (4.5) (or (4.6)), and (4.4) has an optimal solution (λ * , (X * j ), g P f ). Hence p dw = -L y * (f ) for any optimal solution y * of (4.6).

Next, recall that with

J := ∅, M d (g ∅ y) = M d (y). Moreover, M d (y) 0 implies M k (y) 0 for all k ≤ d. By [11, Lemma 1], M k (y) 0 implies that |y α | ≤ max[L y (1), max i L y (x 2k i )],
for every α ∈ N n 2k , and all k ≤ d. Therefore, (4.6) has the equivalent formulation (4.7)

         p d = -inf y L y (f )) s.t. M d (g J y) 0, ∀J ⊆ {1, . . . , m} L y (1) ≤ 1 L y (x 2k i ) ≤ (2k)!, k = 1, . . . , d; i = 1, .
. . , n. Indeed, any feasible solution of (4.7) satisfies

|y α | ≤ max[L y (1), max i L y (x 2k i )] ≤ (2k)! = w α ,
for every α with |α| = 2k and 2k -1, k = 1, . . . , d. The dual of (4.7) is exactly the semidefinite program (4.3). Again Slater's condition holds for (4.7) and it has an optimal solution y * . Therefore (4.3) also has an optimal solution λ P w ∈ R nd+1 Of course, all statements in Theorem 4.1 remain true if one replaces P d (g) with Q d (g). Moreover, if w α = 1 for all α (and so ℓ w is now the usual ℓ 1norm) the polynomial g P w f in (4.2) simplifies and is of the form:

(4.8) x → g P f (x) := f (x) + (λ P 0 + n i=1 λ P i x 2d i ),
for some nonnegative vector λ P ∈ R n+1 . If K = R n then g P f is the canonical ℓ 1 -projection of f onto the cone of s.o.s. polynomials., as illustrated in the following example.

Example 1. Let n = 2 and K = R 2 , in which case P d (g) = Q d (g) = Σ[x] d for all d ∈ N. Consider the Motzkin-like polynomial 3 x → f (x) =
2 Slater's condition holds for the conic optimization problem P : infx{c ′ x : Ax = b; x ∈ K}, where K ⊂ R n is a convex cone and A ∈ R p×n , if there exists a feasible solution x0 ∈ int K. In this case, there is no duality gap between P and its dual P * : sup z {b ′ z : c -A ′ z ∈ K * }. In addition, if the optimal value is bounded then P * has an optimal solution.

3 Computation was made by running the GloptiPoly software [START_REF] Henrion | Gloptipoly 3: moments, optimization and semidefinite programming[END_REF] dedicated to solving the generalized problem of moments.

x 2 1 x 2 2 (x 2 1 + x 2 2 -1) + 1/27 of degree 6, which is nonnegative but not a s.o.s., and with a global minimum f * = 0 attained at 4 global minimizers x * = (±(1/3) 1/2 , ±(1/3) 1/2 ). The results are displayed in Table 1

(g) t ∩ R[x] 2d and Q(g) t ∩ R[x] 2d . We now consider ℓ w -projection of f onto P t (g) ∩ R[x] 2d for given integers d, t ∈ N, i.e., (4.9) p dw t
:= inf g { f -g w : g ∈ P t (g) ∩ R[x] 2d }.
In other words, we are interested in searching for a polynomial of degree 2d in P t (g) which is the closest to f for the ℓ w -norm. For instance, if 2d = deg f , one wishes to find an ℓ w -projection onto P t (g) of same degree as f . One may also consider the analogue problem with the quadratic module, i.e., an ℓ w -projection onto Q t (g) ∩ R[x] 2d . We also analyze the limit as t → ∞. Proof. The proof is almost a verbatim copy of that of Theorem 4.1 with a slight difference. For instance, (4.4) is now replaced with (4.12)

p dw t := inf λ,X J ,h α∈N n 2d w α λ α s.t. λ α + h α ≥ f α , ∀α ∈ N n 2d λ α -h α ≥ -f α , ∀α ∈ N n 2d h α - m J⊆{1,...,m} X J , B J α = 0, ∀α ∈ N n 2t λ ≥ 0; h ∈ R[x] 2d ; X J 0, ∀J ⊆ {1, . . . , m}.
(where h α = 0 whenever |α| > 2d) and the dual (4.6) now reads (4.13)

     sup y -L y (f ) s.t. M t (g J y) 0, ∀J ⊆ {1, . . . , m} |y α | ≤ w α , ∀α ∈ N n 2d .
Again with exactly the same arguments, (4.12) has a feasible solution and (4.13) has a strictly feasible solution y, and so Slater's condition holds for (4.13), which in turn implies that there is no duality gap between (4.12) and (4.13), and (4.12) has an optimal solution (λ, (X J ), g P w f ). However (and this is the only difference with the proof of Theorem 4.1) now one cannot guarantee any more that (4.13) has an optimal solution because |y α | ≤ w α only for α ∈ N n 2d and not for all α ∈ N n 2t . As before, we call g P w f in (4.10) the canonical ℓ w -projection of f onto P t (g) ∩ R[x] 2d . Of course, an analogue of Theorem 4.2 (with obvious ad hoc adjustments) holds for the canonical ℓ w -projection g Qw f onto Q t (g) ∩ R[x] 2d . Also and again, if w α = 1 for all α ∈ N n 2d , then the polynomial g P w f in (4.10) simplifies to the form in (4.8).

We next analyze the behavior of g P w f as t → ∞ to obtain the canonical ℓ w -projection of f onto P (g) ∩ R[x] 2d . Recall that

P (g) ∩ R[x] 2d =   t≥0 P t (g)   ∩ R[x] 2d = t≥0 P d t (g).
Corollary 4.3. Let K ⊆ R n be as in (2.2) and with nonempty interior, f ∈ R[x] 2d , and let g P w f (t) ∈ P t (g) ∩ R[x] 2d be an optimal solution of (4.9). Then there is an ℓ w -projection of

f onto P (g) ∩ R[x] 2d which is a polynomial g w f ∈ R[x] 2d of the form (4.14) x → g w f (x) = f (x) + λ * 0 + n i=1 d k=1 λ * ik x 2d i ,
for some nonnegative vector λ * ∈ R dn+1 . In particular, if K is compact and f ≥ 0 on K then λ * = 0 and g w f = f . Proof. Let (p dw t ), t ∈ N, be the sequence of optimal values of (4.9), which is nonnegative and monotone non increasing. Therefore it converges to some nonnegative value p dw ≥ 0. For every t ∈ N, (4.9) has an optimal solution g P w f (t) of the form

(4.15) x → g P w f (t)(x) = f (x)+λ P w 0 (t)+ n i=1 d k=1 λ P w ik (t) x 2k i 2k! , ∀x ∈ R n ,
with λ P w (t) ≥ 0 and i,k λ P w ik (t) = p dw t ≤ p dw t 0 . Hence there is a subsequence (t j ), j ∈ N, and some nonnegative vector λ * ∈ R nd+1 + such that λ P w (t j ) → λ * as j → ∞. In addition,

p dw = lim j→∞ p dw t j = lim j→∞ λ P w 0 (t j ) + n i=1 d k=1 λ P w ik (t j ) = λ * 0 + n i=1 d k=1 λ * ik .
Hence g P w f (t j ) → g w f ∈ R[x] 2d as j → ∞ where g w f is as in (4.14). And of course, as

g P w f (t) -g w f w → 0, g w f is in the closure P (g) ∩ R[x] 2d of P (g) ∩ R[x] 2d .
Next, suppose that there exists h

∈ P (g) ∩ R[x] 2d with f -h w < f - g w f w . Then there exists a sequence (h t ) ⊂ R[x] 2d , t ∈ N, with h t ∈ P d t (g) such that h t -h w → 0 as t → ∞. But then f -h w = f -h t + h t -h w ≥ f -h t w ≥ f -g P w f (t) w -h t -h w →0 as t→∞ , ∀ t,
and so taking limit as t → ∞ yields the contradiction

f -g w f w > f -h w ≥ lim t→∞ f -g P w f (t) w = f -g w f w . Therefore f -g w f w = min h { f -h w : h ∈ P (g) ∩ R[x] 2d }.
The last statement (when K is compact) follows from Schmüdgen's Positivstellensatz [START_REF] Schmüdgen | The K-moment problem for compact semi-algebraic sets[END_REF] which implies that if f is nonnegative on K then f + ǫ ∈ P (g) for every ǫ > 0.

Of course there is an analogue of Corollary 4.3 with Q(g) in lieu of P (g). The only change is concerned with the last statement where one needs that Q(g) is Archimedean. And also, if w α = 1 for every α ∈ N n , then g w f in (4.14) simplifies to the form (4.8).

The sequential closures of P (g) and Q(g). Recall that for any convex cone

A ⊂ R[x] (4.16) A ‡ = {f ∈ R[x] : ∃ q ∈ R[x] s.t. f + ǫ q ∈ A, ∀ǫ > 0 }.
We have seen that P (g) ⊂ P (g) ‡ ⊆ P (g), where A denotes the closure of A for the finest locally convex topology. Therefore, it is of particular interest to describe P (g) ‡ , which the goal of this section. We know that (4.17

.3].) Notice that Q(g) ‡ = d∈N Q(g) ∩ R[x] d ([9]
) and by [5, Prop. 1.3], we also have Q

(g) = Q(g) ‡ if Q(g) is archimedean. Theorem 4.4. Assume that K ⊆ R n in (2.

2) has a nonempty interior and let f ∈ R[x]. Then:

(a) f ∈ P (g) ‡ if and only if there is some d ∈ N such that for every ǫ > 0, the polynomial

(4.18) x → f (x) + ǫ 1 + n i=1 x 2d i is in P (g).
(b) The same statement as (a) also holds with Q(g) instead of P (g).

In other words, q ∈ R[x] in (4.16) for A = P (g) can be taken as x → (1 + n i=1 x 2d i ) independently of K. The dependence of q on f is through the power d only.

Proof. (a) From (4.17) f ∈ P (g) ‡ if and only if f ∈ P (g) ∩ R[x] 2d for some d ∈ N. Next, by Corollary 4.3, f ∈ P (g) ∩ R[x] 2d if and only if the polynomial g w f ∈ R[x] 2d defined in (4.14) (and which simplifies to (4.8) when w α = 1 for all α ∈ N n ) is identical to f . But then this implies that the polynomial g P w f (t) ∈ P t (g) ∩ R[x] 2d in (4.15) is such that n i=0 λ P w i (t) → 0 as t → ∞ (recall that w α = 1 for all α ∈ N n ). Let λ(t) := max i [λ P w i (t)] so that λ(t) → 0 as t → ∞, and the polynomial x → f (x) + λ(t) 1 + (λ(t)λ P f (t)) ≥0

x 2d i .

Therefore, for every ǫ > 0, choosing t ǫ such that λ(t ǫ ) ≤ ǫ ensures that the polynomial f +ǫ(1+ n i=1 x 2d i ) is in P tǫ (g)∩R[x] 2d , which implies the desired result in (a).

The proof of (b) is omitted as it follows similar arguments. Indeed, it was already mentioned that Theorem 4. ,

and so f + ǫ(1 + n i=1 d k=1

x 2k i (2k)! ) ∈ P (g). The if part. Let q d ∈ R[x] be the polynomial in (4.19), and let x ∈ K be fixed, arbitrary. Then 0 ≤ q d (x) ≤ f (x) + ǫ n i=1 exp |x i |. Therefore, letting ǫ → 0 yields f (x) ≥ 0.

Appendix

Lemma 5.1. Let µ a finite Borel measure whose sequence of moments y = (y α ), α ∈ N n , is such that for all i = 1, . . . , n, and all k ∈ N, L y (x 2k i ) ≤ (2k!)M for some M . Let f ∈ R[x] be such that L y (x 2t i f ) ≥ 0 for all i = 1, . . . , n, and all t ∈ N. Then the sequence z f = (z f α ), α ∈ N n , where z f α = L z f (x α ) := L y (x α f ) for all α ∈ N n , satisfies Carleman's condition (2.6). Proof. Let 1 ≤ i ≤ n be fixed arbitrary, and let 2s ≥ degf . Observe that whenever |α| ≤ k, |x| α ≤ |x j | k on the subset W j := {x ∈ R n \ [-1, 1] n :

2. 1 .

 1 Notation and definitions. The notation B stands for the Borel σfield of R n . Let R[x] (resp. R[x] d ) denote the ring of real polynomials in the variables x = (x 1 , . . . , x n ) (resp. polynomials of degree at most d), whereas Σ[x] (resp. Σ[x] d ) denotes its subset of sums of squares (s.o.s.) polynomials (resp. of s.o.s. of degree at most 2d). For every α ∈ N n the notation x α stands for the monomial x α 1 1 • • • x αn n , |α| stands for the integer a := α 1 + • • • + α n , and α! stands for the integer a! For an arbitrary set S ⊆ R n , let Psd(S) denote the convex cone of polynomials that are nonnegative on S.

B

  f dµ for all B ∈ B. Let Θ µ := {µ σ : σ ∈ Σ[x]}, i.e., Θ µ is the set of finite Borel measures absolutely continuous with respect to µ, and whose density (or Radon Nikodym derivative) is a sum of squares of polynomials. Let Σ[x] * ⊂ R[x] * be the dual cone of the cone of Σ[x], i.e., the set of linear forms L y on R[x] such that L y (h 2 ) ≥ 0 for all h ∈ R[x], and similarly, let Θ * µ ⊂ R[x] be the dual cone of Θ µ , i.e., Θ * µ := {h ∈ R[x] : hdν ≥ 0, ∀ν ∈ Θ µ }. Corollary 2.3. Let S ⊆ R n be an arbitrary closed set and let µ be any finite Borel measure such that supp µ = S and x

1Theorem 4 . 1 .

 41 The following example was kindly provided by an anonymous referee: Let n = 2, d = 1,x → f (x) := -2x1x2, and let C ⊂ R[x] 2d be the cone of sums of squares of linear polynomials. Then any polynomial x → p λ (x) := λ(x1 -x2) 2 with λ ∈ [0, 1], is an ℓw-projection (and an ℓ1-projection) of f onto C and fp λ w = 2. Let K ⊆ R n in (2.2) be with nonempty interior. Let f ∈ R[x]and let 2d ≥ deg f . There is an ℓ w -projection of f onto P d (g) which is a polynomial g P w f ∈ R[x] 2d of the form:(4.2)x → g P w f (x) := f (x) + λ P w vector λ P w ∈ R nd+1 is an optimal solution of the semidefinite program: ∈ P d (g) , and p dw = fg P w f w = λ P w Consider f as an element of R[x] 2d by setting f α = 0 whenever |α| > deg f (where |α| = α i ), and rewrite (4.1) as the semidefinite program: (4.4)

+ with p dw = λ Pw 0

 0 w ik , which is the desired result. The polynomial g P w f ∈ P d (g) in (4.2) is what we call the canonical ℓ wprojection of f onto P d (g).

Theorem 4 . 2 .=

 42 Let K ⊆ R n in (2.2) be with nonempty interior and letd ∈ N. Let f ∈ R[x] and let 2t ≥ max[2d, deg f ]. There is an ℓ w -projection of f onto P t (g) ∩ R[x] 2d which is a polynomial g P w f ∈ R[x] 2d of the form: (4.10)x → g P w f (x) = f (x) + λ P w vector λ P w ∈ R nd+1 is an optimal solution of the semidefinite program: fg P P w f w = λ P w

  ) P (g) ‡ = d∈N P (g) ∩ R[x] d , and if for instance P (g) has an algebraic interior then P (g) = P (g) ‡ . (See e.g. Kuhlmann and Marshall [9, Prop. 1.4] and Cimpric et al. [5, Prop. 1

i

  belongs to P t (g) ∩ R[x] 2d because f + λ(t)

  2 and Corollary 4.3 have obvious analogues for the quadratic module Q(g).Of course in (4.18) one may replace 1+ n i=1 x 2d i ! . In fact, and as pointed out by an anonymous referee, in (a) one may also replace 1 + n i=1 x 2d i with any point in the interior of P d (g) in R[x] 2d and in (b) with any point in the interior ofQ d (g) in R[x] 2d . The fact that 1 + n i=1 x 2d i is an interior point of Σ[x] d in R[x]2d (and hence also an interior point of P d (g) and Q d (g) in R[x] 2d ) seems to be well-known. For instance, it can be deduced from[START_REF] Lasserre | Sufficient conditions for a real polynomial to be a sum of squares[END_REF] Theorem 3].4.3.A Positivstellensatz for non compact K. As we know how to project with the ℓ -norm, we are now able to obtain the following Positivstellensatz on K. Corollary 4.5. Let K ⊆ R n in (2.2) be nonempty interior. Then f ≥ 0 on K if and only if for every ǫ > 0 there exists d ∈ N such that(4.19) x → f (x) + ǫ 1 + ∈ P (g).Proof. The only if part: Recall that P (g) = d≥0 P d (g), and from Theorem 3.3, Psd(K) = cl w (P (g)). Let g P w f (d) ∈ R[x] 2d be the canonical ℓ wprojection of f onto P d (g) given in (4.2), where p dw = λ P w 0 + n i=1 d k=1 λ P w ik . As f ∈ cl w (P (g)), we necessarily have lim d→∞ p dw = 0, because fg P w f (d) w → 0. Hence given ǫ > 0, let d be such that max i,k λ P w ik

  The implication ⇒ is clear. For the reverse implication, consider the signed Borel measure ν(B) := B f dµ, for all Borel sets B ∈ B, and let z = (z

α ), α ∈ N n , be its sequence of moments. By Lemma 5.1, the sequence z satisfies Carleman's condition

(2.6)

. Next, recalling that M k

  as in(2.2) and let y = (y α ), α ∈ N, be a given real sequence such that L y is ℓ w -continuous. Then y has a finite representing Borel measure µ on K if and only if L y is nonnegative on Q(g).

	Equivalently if and only if:
	(3.1)

Table 1 .

 1 for d = 3, 4, 5. Best ℓ 1 -approximation for the Motzkin polynomial. 4.1. Canonical ℓ w -projection onto P

	d λ *	p d
	3 ≈ 10 -3 (5.445, 5.367, 5.367) ≈ 1.6 10 -2
	4 ≈ 10 -4 (2.4, 9.36, 9.36)	≈ 2. 10 -3
	5 ≈ 10 -5 (0.04, 4.34, 4.34)	≈ 8. 10 -5

Acknowledgement. The author wishes to thank an anonymous referee for several comments and suggestions that helped writing the final version.

|x j | = max i |x i |}. And so, |f (x)| ≤ f 1 |x j | 2s for all x ∈ W j . Hence,

and so we have

where the last equality follows from ( 12(k+s) ) (k+s)/k = ( 1 2(k+s) )( 1 2(k+s) ) s/k and ( 12(k+s) ) s/k ≥ 1/2 whenever k is sufficiently large, say k ≥ k 1 . Hence the sequence z f satisfies Carleman's condition (2.6).


Karim Belharet
email: karim.belharet@ensi-bourges.fr

David Folio
email: david.folio@ensi-bourges.fr

Antoine Ferreira
email: antoine.ferreira@ensi-bourges.fr

3D Controlled Motion of a Microrobot using Magnetic Gradients

Keywords: Microrobot, gradient controlled motion, endovascular navigation

This paper presents an endovascular navigation of a ferromagnetic microdevice using MRI-based predictive control. The concept was studied for future development of microrobot designed to perform minimally invasive interventions in remote sites accessible through the human cardiovascular system. A system software architecture is presented illustrating the different software modules to allow 3D navigation of a microdevice in blood vessels, namely: (i) vessel path extraction, (ii) magnetic gradient steering, (iii) tracking and (iv) closed-loop navigation control. First, the navigation path of the microrobot into the blood vessel is extracted using Fast Marching Method from the pre-operation images (3D MRI imaging) to guide the microrobot from the injection point to the tumor area through the anarchic vessel network. Based on the pre-computed path, a Model Predictive Controller is proposed for robust time-multiplexed navigation along a 3D path in presence of pulsative flow.

The simulation results suggest the validation of the proposed image processing and control algorithms.

INTRODUCTION

Microrobots designed to perform targeted therapy by navigating in the cardiovascular system are a prolific research area for minimally invasive surgeries [START_REF] Ishiyama | Magnetic micromachines for medical applications[END_REF][2] and treatments efficiency through early diagnosis of diseases [START_REF] Cavalcanti | Nanorobot for Brain Aneurysm[END_REF]. When microrobots are propelled in the body fluids, especially in the blood circulatory system, a very large number of remote locations in the human body become accessible. Because the method of propulsion should allow such a microrobot to navigate through the cardiovascular system, the use of the normal blood flow itself must be considered only as a complementary means of propulsion when the travel path is along the direction of the blood flow. These untethered microrobots have been mainly developed according to three different designs: magnetic bead pulling [START_REF] Abbott | Robotics in the Small[END_REF], biomimetic flagellated robot [START_REF] Behkam | Design methodology for biomimetic propulsion of miniature swimming robots[END_REF] and magnetotactic bacteria [START_REF] Martel | Flagellated magnetotactic bacteria as controlled MRItrackable propulsion and steering systems for medical nanorobots operating in the human microvasculature[END_REF]. Furthermore, navigation requires observation of the scene in order either to plan the trajectory by off-line mapping, or to correct on-line the microrobot's pose error between the planned and the observed trajectory. Recently, magnetic resonance imaging (MRI)-based medical microrobotic platforms are investigated to reach locations deep in the human body while enhancing targeting efficacy using real-time navigational and trajectory control [START_REF] Felfoul | In vivo MR-tracking based on magnetic signature selective excitation[END_REF]. For the position recognition of the microrobot in the blood vessels, from the pre-operation images, 3D path planning and route optimization solutions have been proposed. The authors in [START_REF] Sabra | Use of 3D potential field and an enhanced breath-first search algorithms for path-planning of microdevices propelled in the cardiovascular system[END_REF] proposed an endovascular path-planning method based on 3D potential fields and enhanced breath-first search algorithms based on MR-imaging. Based on these path-planning techniques, only explorative 2D control strategies have been adopted so far using simple proportional-integralderivative (PID) controller [START_REF] Tamaz | Real-time mri-based control of a ferromagnetic core for endovascular navigation[END_REF]. However, stability and robustness are not ensured against important perturbations. First, pulsatile flow should be taken into account since variations in waveform, amplitude, and frequency exists from vessels. Second, variation of time-multiplexed sequence parameters (duty cycle of the propulsion gradients, and repetition time of the tracking sequence) produce important trajectory errors during real-time navigation.

Finally, random imaging signal noise degrades the localization of the microrobot during tracking.

The main objective of this paper is to propose an automated technique based on image processing and control algorithms for path finding, reconstruction and navigation control of a ferromagnetic microrobot using the MRI system. The MRI-based control of a ferromagnetic microcapsule presented here is dedicated to macroscale navigation, which focuses in conveying a microsphere radius of 300 µm in vessels, such as arteries and arterioles (eg, around 10 to 0.5 mm), as close as possible to the tumor area. Based on slice images provided by an MRI system, relevant information related to detection of blood vessels is extracted using robust Frangi vesselness filtering from the pre-operation images. Then, a set of minimal path is predefined, using Fast Marching Method (FMM), to guide the ferromagnetic microrobot from the injection point to a targeted area through the anarchic vessel network. Based on the precomputed path, a Model Predictive Controller (MPC) is designed. Hence, we proposed a control strategy for robust time-multiplexed navigation along a 3D path even in presence of pulsative flow. The simulation results suggest the validation of the proposed image processing and control algorithms against perturbations.

MRI-based NAVIGATION SYSTEM

System Overview

The Magnetic Resonant Imaging (MRI)-based microrobotic system is used here for propulsion and navigation of the microdevice. The propulsion of the ferromagnetic microcapsule in the cardiovascular system is realized through the induction of force from magnetic gradients provided by the MRI. This MRI system will guide the microcapsule in vivo through vascular networks to a targeted area. The overview of the software system architecture is given in Fig. 1.

(i) The graphical user interface module, which comprises input command prompt, 3D-visualization, and process supervision tools. (ii) The control module, which comprises (a) the high-level controller responsible for the microcapsule navigation tasks and for the generation of the magnetic field gradients and (b) the low-level controller (manufacturer MRI controller) responsible for the generation of the desired field gradients and for the image acquisition tasks. Then, (iii) the controlled hardware, which comprises (a) the MRI hardware and software systems and (b) the microcapsules that have been injected within the vasculature and are steered by the magnetic gradients. Finally, (iv) the image processing module, which comprises the MRI data rendering, the navigation path extraction, and the microdevice recognition/tracking algorithm. In particular, the tracking procedure, presented in [START_REF] Wortmann | Study of MRI susceptibility artifacts for nanomedical applications[END_REF], allows to estimate the position and accumulation of the microdevices within the vasculature, the tissues, and the organs of the human. However as MR-imaging is too slow to gather position of the microrobot and special MR-tracking algorithm, such as MR-SET, must considered to ensure real time control.

Navigation in blood vessels

In our context, the problem of navigation in blood vessels within the MRI data can be formulated as finding the correct way through the data that follows the vessel of interest between its start and end points. Finding a navigation path within the endovascular network is then an essential, primary, and important step that must be addressed prior to the control procedure. The problem of vessels extraction has received considerable attention in the computer vision and medical imaging communities [START_REF] Kirbas | A review of vessel extraction techniques and algorithms[END_REF]. Hence, several class of methods have been proposed to find a path from a set of medical imaging, such as using tracking methods [START_REF] Reuzé | A 3D moment based approach for blood vessel detection and quantification in MRA[END_REF] [6] [START_REF] Tokuda | Integrated navigation and control software system for mri-guided robotic prostate interventions[END_REF], path extraction methods [START_REF] Deschamps | Curve and shape extraction with minimal path and level-sets techniques: Applications to 3d medical imaging[END_REF][14] [START_REF] Wink | Vessel axis determination using wave front propagation analysis[END_REF], and so on. Most works based on in vivo MR-tracking methods usually need many user-defined way points as the input of a controller module for the navigation computation. A major drawback in general remains when the user must define many points (e.g. way or fiducial points) manually. Hence, for a complex structure (e.g. colon, small vessels. . . ) the required interactivity can be very tedious. The path extraction is useful for a range of application domains including medical image analysis, robot navigation, and artificial intelligence. The path extraction technique needs a very simple initialisation and leads to global minimum of a snake-like energy, thus avoiding local minima. Moreover, it is fast and accurate. This path finding problem has been studied for ages by mathematicians, and has been solved numerically using graph theory or dynamic programming. Cohen and Kimmel [START_REF] Cohen | Global minimum for active contour models: A minimal path approach[END_REF] solved the minimal path problem in 2D with a front propagation equation between the two fixed end points, using the Eikonal equation (that physically models wave-light propagation), with a given initial front. Wink et al. [START_REF] Wink | Minimum cost path determination using a simple heuristic function[END_REF] explored different methods to determine the minimum cost path through a pre-defined cost image, for extraction of vessel centrelines from medical image data. Among them are Dijikstra's algorithm, the A ⋆ algorithm, which makes use of additional heuristics to steer the search process, and wave front propagation analysis [START_REF] Wink | Vessel axis determination using wave front propagation analysis[END_REF]. Early, Sethian [START_REF] Sethian | Level set methods and fast marching methods[END_REF] explored the use of Fast Marching Method (FMM) to extract minimal paths. This method relies on the fact that the gradient of the FMM arrival function has only one local minimum, which is guaranteed to be global minimum [START_REF] Deschamps | Curve and shape extraction with minimal path and level-sets techniques: Applications to 3d medical imaging[END_REF]. Therefore, the minimal path can be extracted by back-propagating from given seeds (e.g. the end point of the desired path) to the starting point implicitly embedded in the arrival function.

In this work the FMM is adopted to design a set of paths to guide the microdevice from the injection point to the tumor area through the vessel network. Our aim is to focus on the automation of the path construction, reducing the need of interaction and improving performance, in a robust way.

Problem formulation

Navigation in blood vessel requires observation of the scene in order either to plan the path by offline mapping, or to correct online the microrobot pose error between the planned and the observed path. To insure a smooth conveyance of the microcapsule to destination, collisions and the risk to be trapped by the endothelium, optimal navigation performance will be affected by external perturbations and MRI technological constraints:

• Nonnegligible pulsatile flow, whose variations in waveform, amplitude, and frequency exist from one vessel to another (such as arteries and arterioles).

• Magnetic gradients are used both for observation and control purposes in a time-multiplexed sequence. It requires different trade-offs in terms of refresh rate, duty cycle of the propulsion gradients, and repetition time of the tracking sequence.

• MRI overheating avoidance leading to limitations on the MRI duty cycle, tends to increase the disproportional scaling between magnetic forces used for control purpose and perturbation forces (drag forces and net buoyancy forces).

• Limitations on the magnetic gradient amplitude in available MRI devices.

• Proper delay in the image processing algorithms that renders the navigation control unstable.

Real-Time Sequence Design

The overall concept of the in-vivo MRI-tracking system is based on the fact that both tracking and propulsion is possible with the gradient coils of the MRI system. Software based upgrading of a clinical MRI system is the least expensive approach to convert a platform that is used for imaging to an effective interventional platform. At any instant only one of the functions could be applied (i.e. either tracking or propulsion), but both will be executed over the same MRI interface. The MRI interface has therefore to be shared and a time-division-multiple-access scheme for it has to be developed. Fig. 2 shows an overview of the real-time sequence with time-multiplexed positioning and propulsion phases introduced by Martel et al. [START_REF] Felfoul | In vivo MR-tracking based on magnetic signature selective excitation[END_REF]. The main aspect relevant to the controller's performance is (i) the duty cycle T Prop /T s that stands for the ratio between the propulsion time and the time between two successive position requests, and (ii) the synchronization event delay T Sync that stands for the minimum time allowed for image processing and real-time control feedback. First, the duty cycle should be adapted to apply sufficient magnetic propulsion gradients during a predefined propulsion time T Prop to prevent the microrobot from drifting away from the path. Second, a large time delay T Sync produces oscillations as the microrobot approaches the reference path w leading to position instabilities. Such limitations have been pointed out by Mathieu et al. [START_REF] Tamaz | Real-time mri-based control of a ferromagnetic core for endovascular navigation[END_REF] when implementing simple proportional-integral-derivative (PID) controller. We proposed a Model Predictive Controller (MPC) including microrobot's motion and dynamics with estimation of the pulsative blood flow and time-multiplexed positioning. A predictive path-tracking control consider a prediction window (cf. Fig. 2). The propulsion phase starts during T Prop seconds at the same initial condition as the prediction phase, recording the performance of the system according to a prediction horizon. After this phase the system ends after a imagingpropulsion sequence at a final position Y which is set as the new initial condition of the next prediction output Y .

The proposed navigation based predictive controller offers stability by design and allows the designer to tradeoff performance for (computation) speed, stability margins according to the MRI application and technological requirements outlined in section 3.1.

Model description

The linear model used in this work is derived from the nonlinear model developed in a previous study [START_REF] Arcèse | Nonlinear modeling and robust controller-observer for a magnetic microrobot in a fluidic environment using MRI gradients[END_REF]. The authors used this model to combine the backstepping controller and high-gain observer in order to control the path of the microrobot inside a vessel using the MRI gradients.

The different forces acting on the microrobot are (see Fig. 3): drag force

- → F d , apparent weight - → W a and mag- netic force - → F m .
The application of Newton's third law and the projection on the ( -→ x , -→ y , -→ z ) axes leads to:

         m ẍ = - → F dx + - → F mx m ÿ = - → F dy + - → F my mz = - → F dz + - → F mz + - → W a (1)
where m is the mass of the microrobot modeled by a ferromagnetic sphere with a high saturation magnetization.

Let - → v = (v f x , v f y , v f z )
denotes the blood flow velocity, and (x, y, z) the robot location in the blood vessel wrt.

to a given frame

F (O, - → x , - → y , - → z ). Taking the drag coefficient C d = 24
Re , the linear model can be written as follow:

         ẍ = α 1 ẋ -v f x + α 2 u x ÿ = β 1 ẏ -v f y + β 2 u y z = γ 1 ż -v f z + γ 2 u z (2)
with the following parameters α i , β i and γ i , and the magnetic gradients considered as control inputs u x , u y and u z , that is:

                 α 1 = -4.5 η cos ϕ cos θ r 2 ρ , u x = - → ∇ B x β 1 = -4.5 η cos ϕ sin θ r 2 ρ , u y = - → ∇ B y γ 1 = -4.5 η sin ϕ r 2 ρ , u z = - → ∇ B z α 1 = β 2 = γ 2 = m ρ ( 3
)
where ρ is the density of the fluid; η is the fluid viscosity; r is the spherical radius of the microrobot; and B = (B x , B y , B z ) T is the magnetic field generated by the MRI system.

Finally, the state-space representation is deduced from (2):

(S)                            ẋ = v x vx = α 1 v x -α 1 v f x + α 2 u x    (S x ) ẏ = v y vy = β 1 v y -β 1 v f y + β 2 u y    (S y ) ż = v z vz = γ 1 v z -β 1 v f z + γ 2 u z    (S z ) (4)
where (v x , v y , v z ) T denotes the robot velocity along -→ x -axis, -→ y -axis and -→ z -axis. Assuming that the microrobot location (x, y, z) can be measured thanks to the MRI system, we denote by Y = (x, y, z) T the process measure. We can notice that system (S) can be divided into three subsystems (S x ), (S y ) and (S z ), which allow us to define three independents MPC schemes to track the reference path w in 3D MRI data.

In this paper, we aim to use the system model defined in (4) in a high level MPC scheme in order to follow efficiently a pre-planed path extracted with the method proposed in section 2.2. The proposed MPC controller is intended to embed the low level robust controller designed in [START_REF] Arcèse | Nonlinear modeling and robust controller-observer for a magnetic microrobot in a fluidic environment using MRI gradients[END_REF][19] (see Fig. 4). Let us notice that the low level controller provides1 robustness performances against MRI system constraints (as pulsatile flow, limited gradient amplitude, and image noise) while the MPC controller is designed to tradeoff time-multiplexed sequence constraints in terms of refresh-rate, duty cycle of the propulsion gradients, and repetition time of the tracking sequence.

Predictive Control

Model Predictive Control (MPC) has become an area of significant research interest over the last past twenty years. This interest has been powered by a stream of successful industrial applications [START_REF] Qin | A survey of industrial model predictive control technology[END_REF]. When focusing on linear (and unconstrained) discrete time transfer function models and quadratic cost functions, some of the best known approaches include the Generalized Predictive Control (GPC) introduced by Clarck et al. [START_REF] Clarke | Generalized predictive control -Part I & II[END_REF], and the inner loop stabilizing Stable Predictive Control [START_REF] Kouvaritakis | Stable generalised predictive control: an algorithm with guaranteed stability[END_REF].

MPC refers to a class of computer control algorithms which use an explicit process model to predict the future response of the system. One way to design MPC is to use an extended state-space representation, which is given by:

   Ẋk+1 = AX k + B∆u k Y k = CX k (5)
where ∆u k = u ku k-1 is the discrete difference operator. The predicted state vector at time k + i is then computed from [START_REF] Camacho | Model predictive control[END_REF]:

X k+i|k = A i X k|k-1 + i-1 ∑ j=0 A j Bu k-j-1 (6)
Then, the future outputs Y k+ j|k can be computed based on the plant for future times starting at time k using a recursion procedure, defined by:

Y k+i|k = C A i X k + i ∑ j=1 A i-j-1 Bu k+i-j|k (7)
Design criterion is defined for certain interval of predictions (several steps to future). It includes the part of control error, in which the model of system is covered (insertion of equations of prediction ( 7)) and the part of control actions, where the input energy (control actions) is weighted. This part redistributes control errors to individual steps of predictions and provides coupling within intervals of predictions. Usual form of the criterion for predictive design is written as follows:

J k = N 2 ∑ j=N 1 +1 Y k+ j W T k+ j Q Y Y k+ j W k+ j + N u ∑ j=1 u T k+ j-1 Q u u k+ j-1 ( 8
)
The criterion is expressed in step k. N = N 2 -N 1 is a horizon of prediction, N u is the control horizon. Q Y and Q u are output and input penalizations. Y k+ j and u k+ j-1 are output and input (full or incremental) values.

Finally, let us note how to construct real control actions at incremental algorithm: after computing a vector for whole horizon, only first control u k is used; then to obtain the full control actions the second line of equation ( 5) is applied.

When using MPC in the state-space formulation, and generally at the use of whichever stat-space control, it is necessary to solve the question of availability of the state of the system (state vector). If it is not available, and only system output from the measurement are known, then some state-space estimation has to be considered.

Suitable well-known solution of such estimation is the state-space observer based on Kalman filter.

Results

Navigation Path Extraction

The FMM algorithm, introduced by Sethian [START_REF] Sethian | Level set methods and fast marching methods[END_REF] is applied here to extract a targeted navigation path within the vessel network. From the set of 3D MRI data, a speed map is computed (ie. a weighting image map) in order to enhance the relevant intravascular network. Choosing an appropriate and efficient image cost function is the most difficult part of the entire process.

We describe in the sequel presented in Fig. 5, the process used to extract the navigation path. First, we need a relevant cost function which allow to enhance vessel in the image. To this aim, we used some a priori knowledge about vessel shape and intensity in MRI data (cf. Fig. 5). Vessels are expected to appear as bright tubular structures in a darker environment. One way to account for the varying size of vessels is by multiscale analysis. It allows us to detect structures of different sizes according to the scale at which they give maximal response. In this context, a typical speed image is produced by using a Frangi vesselness filter [START_REF] Frangi | Multiscale vessel enhancement filtering[END_REF] which uses the eigenvectors of the Hessian matrix at each voxel of the image to compute the likeliness of an image region to vessels. This mapping is selected in such a way that vessels regions will have higher speed (high level in speed image, see Fig. 5). Once the speed map is generated, the user has to select a start and end points (ie. seed points) in the viewer of the input original image. The FFM will then propagate a front from the start seed and traveling to the targeted area, thanks to the speed map. Thus, this approach allow to find a minimal navigation path between the start and targeted seed (cf. Fig. 5).

Microdevice Navigation using Predictive Control

Simulations conducted here are performed within the scope of actual commonly spread MRI system abilities.

Actually, MRI systems are able to generate magnetic gradients with an intensity of some tens of mT.m -1 . Let us note that this limitation is additionally affected by the gradient coils duty-cycle and by the time-multiplexing sequence (T Prop /T s ) needed both for controlling and observing sequences. In order to make sure that the amplitude of the control inputs remains bounded by physical actuators limits u i,max , and to protect the system, we applied a simple time-scaling factor defined by u i k(t) , with k(t) =max 1, u i u i,max . The following set of simulations corresponds to a microcapsule radius of r = 300 µm and a time scaling settled at k(t) = 0.55. Different situations are considered to illustrate and to validate the performance of the proposed MRI-based predictive controller.

We validated the proposed control strategy on a 3D endovascular navigation path w extracted from MRI-data with the previously presented method without any disturbance. Then, to evaluate the efficiency of the proposed MRI-based predictive controller, we performed some tests with a white Gaussian noise on the system output measure Y . The noise is about 10 % of the measured signal which is motivated by the common precision of clinical MRI devices. Fig. 6 describes the navigation path followed by the microrobot, and Fig. 7 presents the relative error norm between the current position Y and the reference w, for a time horizon N = 5. As shown, the system output Y follows perfectly the reference path w. In particular, the microdevice is able to reach quickly the navigation path, in spite of a gap between the initial position Y and the reference w. Let us notice that the 3D tracking is not too much affected by the Gaussian noise since position standard deviation (STD) and root mean square (RMS) error are quite satisfactory. Fig. 8 simulates the impact of the time horizon N on the system tracking error for optimized time horizon values between 3 ≤N≤ 10. Comparing the error statistics, the nature of anticipation of the MPC scheme is well illustrated -important values of N improve greatly the anticipation nature of the path behavior but increases at the same time the path tracking error-. Hence, a great value of N does not necessarily guarantee good performances, and classically increase the complexity of the scheme.

To evaluate the robustness of our control strategies, we have also applied an external disturbance which represent the pulsatile blood flow behavior.

Hence, we have modeled the blow flow as a time-sinusoidal profile with spatial parabolic form σ flow (t). In case of an artery, to model the action of flow (positive) and reflux of blood (negative) σ flow (t) were shifted up, leading to:

σ flow (t) = 0.025 1 + 1.15 sin 2πt + π 8 (9)
where amplitude of 0.025 is representative of maximum blood flow speed. In the following, the performance and stability of the predictive controller with respect to physiological parameters variations are demonstrated in Fig. 9. It appears that the system is robust to uncertain physiological parameters (disturbance applied at t = 13 seconds) since the 3D position tracking error norm is bounded to 0.2 %.

Finally, we have evaluated the robustness of our controller for different duty cycle values: 25 %, 50 % and 75 %, respectively. The error curves and statistics for the three scenario are illustrated on Fig. 10. As one can see for a duty cycle of 50 %, that is the MRI system propels during the first half-period, and acquires 3D images on the other half-period, the path tracking is quite satisfactory. It corresponds to the real-time navigational and trajectory control constraints reported in [START_REF] Tamaz | Real-time mri-based control of a ferromagnetic core for endovascular navigation[END_REF]. Nevertheless for a duty cycle of 25 % (ie. the MRI propels during 1/4 period, and image during 3/4 period) the microrobot can not properly track the reference path w leading to great tracking error. The time-multiplexing duty cycle is optimized for a value around 40 %. In the optimal case, the simulated predictive behavior of the MPC controller suggests better tracking results compared to those obtained by [START_REF] Tamaz | Real-time mri-based control of a ferromagnetic core for endovascular navigation[END_REF] that should be confirmed by experimentation.

CONCLUSIONS

The proposed MRI-based ferromagnetic microcapsule steering and navigation strategy has been developed at milli and microscale, where endovascular navigation path extraction and predictive controller have been designed. The main drawback of MRI-based navigation stems from the strong limitations on the magnetic gradient amplitude of available MRI devices. As magnetic forces used for propelling are volumetric, whereas the drag force is at best dependent on the microcapsule's area, the smaller the capsule, the higher the required control forces with respect to hydrodynamic perturbations. Consequently, this approach is well conditioned for beads whose radius is up to a few dozen micrometers with actual MRI devices. Targeting aims at focusing these microcarriers and stopping them through embolization at the arterioles entry close to the occluded blood vessels. Possible releasing mechanisms could rely on biodegradable polymer and techniques used in hyperthermia where aggregates of nanocapsules can be heated to melt polymer. Such a solution is actually under experimentation for validation of the proposed minimally invasive MRI-based microrobotic system.

Figure 1 :

 1 Figure 1: Overall system overview.

Figure 2 :

 2 Figure 2: Timeline of acquisition and control prediction.

Figure 3 :

 3 Figure 3: Forces applied on microrobot navigating in blood vessel.

Figure 4 :

 4 Figure 4: MRI-based Predictive Control strategy.

Figure 5 :

 5 Figure 5: 3D Navigation path extraction processing: a) Original MRI data; b) Computed cost function usingFrangi filter (here displayed in red volume); c) Extracted navigation path between the start and end seeds using FFM.

Figure 6 :

 6 Figure 6: 3D MRI-based microrobot endovascular navigation (N = 5, in mm).

Figure 7 :

 7 Figure 7: 3D tracking error: Yw for N = 5.

Figure 8 :

 8 Figure 8: Tracking error statistics for different time horizons N.

( a )

 a Blood flow disturbance σ flow (t).

Figure 9 :

 9 Figure 9: MRI-based navigation with blood flow disturbance.

Figure 10 :

 10 Figure 10: Tracking error with different values of duty cycle.

The interested reader is invited to refer to[START_REF] Arcèse | Nonlinear modeling and robust controller-observer for a magnetic microrobot in a fluidic environment using MRI gradients[END_REF][19][START_REF] Arcese | Dynamic behavior investigation for trajectory control of a microrobot in blood vessels[END_REF].

ACKNOWLEDGMENTS

This work was supported by European Union's 7th Framework Program and its research area ICT-2007.3.6 Micro/nanosystems under the project NANOMA (Nano-Actuactors and Nano-Sensors for Medical Applications). The PhD student K. Belharet is supported by the Nano-IRM project, funded by Conseil Gnral du Cher and Agglomeration de Bourges.