Codrut ¸a Stoica
email: cstoicad@yahoo.com

Dichotomies for evolution equations in Banach spaces

Keywords: 34D05, 34D09, 93D20 evolution semiflow, evolution cocycle, skew-evolution semiflow, uniform exponential dichotomy, Barreira -Valls exponential dichotomy, exponential dichotomy, uniform polynomial dichotomy, Barreira -Valls polynomial dichotomy, polynomial dichotomy

come

Preliminaries

Recently, the important progress made in the study of evolution equations had a master role in the developing of a vast literature, concerning mostly the asymptotic properties of linear operators semigroups, evolution operators or skew-product semiflows.

In this paper, the study is led throughout the notion of skew-evolution semiflow on Banach spaces, defined by means of an evolution semiflow and an evolution cocycle. As the skew-evolutions semiflows reveal themselves to be generalizations of evolution operators and skew-product semiflows, they are appropriate to study the asymptotic properties of the solutions of evolution equations having the form u(t) = A(t)u(t), t > t 0 ≥ 0 u(t 0 ) = u 0 , where A : R → B(V ) is an operator, DomA(t) ⊂ V , u 0 ∈ DomA(t 0 ).

The fact that a skew-evolution semiflow depends on three variables t, t 0 and x, while the classic concept of cocycle depends only on t and x, justifies the study of asymptotic behaviors in a nonuniform setting (relative to the third variable t 0 ) for skew-evolution semiflows.

The basic concepts of asymptotic properties, such as stability, instability and dichotomy, that appear in the theory of dynamical systems, play an important role in the study of stable, instable and central manifolds. We intend to define and exemplify various concepts of dichotomies, as uniform exponential dichotomy, Barreira-Valls exponential dichotomy, exponential dichotomy, uniform polynomial dichotomy, Barreira-Valls polynomial dichotomy, polynomial dichotomy and to emphasize connections between them. We have thus considered generalizations of some asymptotic properties for evolution equations, defined by L. Barreira and C. Valls in [START_REF] Barreira | Stability of Nonautonomous Differential Equations[END_REF]. Characterizations for the asymptotic properties in a nonuniform setting are also proved. Some of the original results concerning the properties of stability and instability for skew-evolution semiflows were published in [START_REF] Stoica | On uniform exponential stability for skew-evolution semiflows on Banach spaces[END_REF] and [START_REF] Megan | Exponential instability of skew-evolution semiflows in Banach spaces[END_REF].

The exponential dichotomy for evolution equations is one of the mathematical domains with an impressive development due to its role in describing several types of differential equations. Its study led to an extended literature, which begins with the interesting results due to O. Perron in [START_REF] Perron | Die Stabitätsfrage bei Differentialgleichungen[END_REF]. The ideas were continued by J.L. Massera and J.J. Schäffer in [START_REF] Massera | Linear Differential Equations and Function Spaces[END_REF], with extensions in the infinite dimensional case accomplished by J.L. Dalecki ȋ and M.G. Kre ȋn in [START_REF] Dalecki | Stability of solutions of differential equations in Banach space[END_REF] and A. Pazy in [START_REF] Pazy | Semigroups of Linear Operators and Applications to Partial Differential Equations[END_REF], respectively R.J. Sacker and G.R. Sell in [START_REF] Sacker | Existence of dichotomies and invariant splittings for linear differential systems III[END_REF]. Diverse and important concepts of dichotomy were introduced and studied by S.N. Chow and H. Leiva in [START_REF] Chow | Existence and roughness of the exponential dichotomy for linear skew-product semiflows in Banach spaces[END_REF] and by W.A. Coppel in [START_REF] Coppel | Dichotomies in stability theory[END_REF].

Some asymptotic behaviors for evolution families were given in the nonuniform case in [START_REF] Megan | Asymptotic Behaviour of Evolution Families[END_REF] by M. Megan, A.L. Sasu and B. Sasu. The study of the nonuniform exponential dichotomy for evolution families was considered by P. Preda and M. Megan in [START_REF] Preda | Nonuniform dichotomy of evolutionary processes in Banach spaces[END_REF].

The property of exponential dichotomy for the case of skew-evolution semiflows is treated in [START_REF] Megan | Exponential dichotomy for skew-evolution semiflows on Banach spaces[END_REF] and [START_REF] Stoica | Nonuniform behaviors for skew-evolution semiflows in Banach spaces[END_REF].

Notations. Definitions. Examples

Let us consider a metric space (X, d), a Banach space V , V * its topological dual and B(V ) the space of all bounded linear operators from V into itself. I is the identity operator on V . We denote

T = (t, t 0 ) ∈ R 2 , t ≥ t 0 ≥ 0 and Y = X × V . Definition 1 A mapping ϕ : T × X → X is called evolution semiflow on X if following relations hold: (s 1 ) ϕ(t, t, x) = x, ∀(t, x) ∈ R + × X; (s 2 ) ϕ(t, s, ϕ(s, t 0 , x)) = ϕ(t, t 0 , x), ∀(t, s), (s, t 0 ) ∈ T, x ∈ X. Definition 2 A mapping Φ : T × X → B(V ) is called evolution cocycle over an evolution semiflow ϕ if: (c 1 ) Φ(t, t, x) = I, ∀(t, x) ∈ R + × X; (c 2 ) Φ(t, s, ϕ(s, t 0 , x))Φ(s, t 0 , x) = Φ(t, t 0 , x), ∀(t, s), (s, t 0 ) ∈ T, x ∈ X.
Definition 3 The mapping C : T × Y → Y defined by the relation

C(t, s, x, v) = (ϕ(t, s, x), Φ(t, s, x)v),
where Φ is an evolution cocycle over an evolution semiflow ϕ, is called skewevolution semiflow on Y .

Example 1 We denote by C = C(R + , R + ) the set of all continuous functions x : R + → R + , endowed with the topology of uniform convergence on compact subsets of R + , metrizable by means of the distance

d(x, y) = ∞ n=1 1 2 n d n (x, y) 1 + d n (x, y)
, where

d n (x, y) = sup t∈[0,n] |x(t) -y(t)|.
If x ∈ C, then, for all t ∈ R + , we denote x t (s) = x(t + s), x t ∈ C. Let X be the closure in C of the set {f t , t ∈ R + }, where f : R + → R * + is a decreasing function. It follows that (X, d) is a metric space. The mapping ϕ : T × X → X, ϕ(t, s, x) = x t-s is an evolution semiflow on X.

We consider

V = R 2 , with the norm v = |v 1 | + |v 2 |, v = (v 1 , v 2 ) ∈ V . The mapping Φ : T × X → B(V ) given by Φ(t, s, x)v = e α 1 t s x(τ -s)dτ v 1 , e α 2 t s x(τ -s)dτ v 2 , (α 1 , α 2 ) ∈ R 2 ,
is an evolution cocycle over ϕ and C = (ϕ, Φ) is a skew-evolution semiflow.

Remark 1 A connection between the solutions of a differential equation

u(t) = A(t)u(t), t ∈ R + (1)
and a skew-evolution semiflow is given by the definition of the evolution cocycle Φ, by the relation Φ(t, s, x)v = U (t, s)v, where U (t, s) = u(t)u -1 (s), (t, s) ∈ T , (x, v) ∈ Y , and where u(t), t ∈ R + , is a solution of the differential equation [START_REF] Barreira | Stability of Nonautonomous Differential Equations[END_REF].

The fact that the skew-evolution semiflows are generalizations for skewproduct semiflows is emphasized by Example 2 Let X be the metric space defined as in Example 1. The mapping ϕ 0 : R + × X → X, ϕ 0 (t, x) = x t , where x t (τ ) = x(t + τ ), ∀τ ≥ 0, is a semiflow on X. Let us consider for every x ∈ X the parabolic system with Neumann's boundary conditions:

           ∂v ∂t (t, y) = x(t) ∂ 2 v ∂y 2 (t, y), t > 0, y ∈ (0, 1) v(0, y) = v 0 (y), y ∈ (0, 1) ∂v ∂y (t, 0) = ∂v ∂y (t, 1) = 0, t > 0.
(

) 2
Let V = L 2 (0, 1) be a separable Hilbert space with the orthonormal basis {e n } n∈N , e 0 = 1, e n (y) = √ 2 cos nπy, where y ∈ (0, 1), n ∈ N. We denote D(A) = {v ∈ L 2 (0, 1), v(0) = v(1) = 0} and we define the operator

A : D(A) ⊂ V → V, Av = d 2 v dy 2 ,
which generates a C 0 -semigroup S, defined by

S(t)v = ∞ n=0 e -n 2 π 2 t v, e n e n ,
where •, • denotes the scalar product in V . We define for every x ∈ X, A(x) : D(A) ⊂ V → V , A(x) = x(0)A, which allows us to rewrite system (2

) in V as v(t) = A(ϕ 0 (t, x))v(t), t > 0 v(0) = v 0 . (3)
The mapping

Φ 0 : R + × X → B(V ), Φ 0 (t, x)v = S t 0 x(s)ds v
is a cocycle over the semiflow ϕ 0 and C 0 = (ϕ 0 , Φ 0 ) is a linear skew-product semiflow strongly continuous on Y . Also, for all v 0 ∈ D(A), we have obtained that v(t) = Φ(t, x)x 0 , t ≥ 0, is a strongly solution of system (3).

As C 0 = (ϕ 0 , Φ 0 ) is a skew-product semiflow on Y , then the mapping

C : T × Y → Y , C(t, s, x, v) = (ϕ(t, s, x), Φ(t, s, x)v), where ϕ(t, s, x) = ϕ 0 (t -s, x) and Φ(t, s, x) = Φ 0 (t -s, x), ∀(t, s, x) ∈ T × X
is a skew-evolution semiflow on Y . Hence, the skew-evolution semiflows generalize the notion of skew-evolution semiflows.

An interesting class of skew-evolution semiflows, useful to describe some asymptotic properties, is given by Example 3 Let us consider a skew-evolution semiflow C = (ϕ, Φ) and a parameter λ ∈ R. We define the mapping Φ λ : T × X → B(V ), Φ λ (t, t 0 , x) = e λ(t-t 0 ) Φ(t, t 0 , x).

(

) 4
One can remark that C λ = (ϕ, Φ λ ) also satisfies the conditions of Definition

λ : T × X → B(V ), Φ λ (t, s, x)v = S λ (t -s)v
, where S λ = {S λ (t)} t≥0 is generated by the operator A -λI, is also an evolution cocycle.

Definition 4 A skew-evolution semiflow C = (ϕ, Φ) is said to be strongly measurable if, for all (t 0 , x, v) ∈ T × Y , the mapping s → Φ(s, t 0 , x)v is measurable on [t 0 , ∞).

Definition 5

The skew-evolution semiflow C = (ϕ, Φ) is said to have exponential growth if there exist M, ω : R + → R * + such that:

Φ(t, t 0 , x)v ≤ M (s)e ω(t-s) Φ(s, t 0 , x)v , ∀(t, s), (s, t 0 ) ∈ T, ∀(x, v) ∈ Y. Remark 2 If C = (ϕ, Φ
) is a skew-evolution semiflow with exponential growth, as following relations

Φ λ (t, t 0 , x)v = e λ(t-t 0 ) Φ(t, t 0 , x)v ≤ M (t 0 )e [ω(t 0 )+λ](t-t 0 ) v , hold for all (t 0 , x, v) ∈ R + × Y , then C λ = (ϕ, Φ λ ), λ > 0, has also expo- nential growth.
Remark 3 (i) If we consider in Definition 5 the constants M ≥ 1 and ω > 0, the skew-evolution semiflow C is said to have uniform exponential growth;

(ii) If in Definition 5 we consider M ≥ 1 to be a constant such that the relation Φ(t, s, x) ≤ M e ω(t-s) holds for all (t, s) ∈ T and all x ∈ X, the skew-evolution semiflow C is said to have bounded exponential growth.

Definition 6

The skew-evolution semiflow C = (ϕ, Φ) is said to have exponential decay if there exist M, ω : R + → R * + such that:

Φ(s, t 0 , x)v ≤ M (t)e ω(t-s) Φ(t, t 0 , x)v , ∀(t, s), (s, t 0 ) ∈ T, ∀(x, v) ∈ Y.
Remark 4 If C = (ϕ, Φ) be a skew-evolution semiflow with exponential decay, as following relations

Φ -λ (s, t 0 , x)v = e -λ(s-t 0 ) Φ(s, t 0 , x)v ≤ M (t)e [ω(t)+λ](t-s) Φ -λ (t, t 0 , x)v ,
hold for all (t, s), (s, t 0 ) ∈ T and all (x, v) ∈ Y , then C -λ = (ϕ, Φ -λ ), λ > 0, has also exponential decay.

Remark 5 If in Definition 6 we consider M ≥ 1 and ω > 0 to be constants, the skew-evolution semiflow C is said to have uniform exponential decay.

3 On various classes of dichotomy

Let C : T ×Y → Y , C(t, s, x, v) = (ϕ(t, s, x), Φ(t, s, x)v) be a skew-evolution semiflow on Y .
Definition 7 A continuous mapping P : Y → Y defined by:

P (x, v) = (x, P (x)v), ∀(x, v) ∈ Y, (5)
where P (x) is a linear projection on Y x , is called projector on Y .

Remark 6 The mapping P (x) : Y x → Y x is linear and bounded and satisfies the relation P (x)P (x) = P 2 (x) = P (x) for all x ∈ X.

For all projectors P : Y → Y we define the sets

ImP = {(x, v) ∈ Y, P (x)v = v} and KerP = {(x, v) ∈ Y, P (x)v = 0}.
Remark 7 Let P be a projector on Y . Then ImP and KerP are closed subsets of Y and for all x ∈ X we have

ImP (x) + KerP (x) = Y x and ImP (x) ∩ KerP (x) = {0}.
Remark 8 If P is a projector on Y , then the mapping

Q : Y → Y, Q(x, v) = (x, v -P (x)v) (6)
is also a projector on Y , called the complementary projector of P .

Definition 8 A projector P on Y is called invariant relative to a skewevolution semiflow C = (ϕ, Φ) if following relation holds:

P (ϕ(t, s, x))Φ(t, s, x) = Φ(t, s, x)P (x), (7)
for all (t, s) ∈ T and all x ∈ X.

Remark 9 If the projector P is invariant relative to a skew-evolution semiflow C, then its complementary projector Q is also invariant relative to C.

Definition 9 A projector P 1 and its complementary projector P 2 are said to be compatible with a skew-evolution semiflow C = (ϕ, Φ) if (d 1 ) the projectors P 1 and P 2 are invariant on Y ; (d 2 ) for all x ∈ X, the projections P 1 (x) and P 2 (x) commute and the relation

P 1 (x)P 2 (x) = 0 holds.
In what follows we will denote

Φ k (t, t 0 , x) = Φ(t, t 0 , x)P k (x), ∀(t, t 0 ) ∈ T, ∀x ∈ X, ∀k ∈ {1, 2}.
We remark that Φ k , k ∈ {1, 2} are evolution cocycles and

C k (t, s, x, v) = (ϕ(t, s, x), Φ k (t, s, x)v), ∀(t, t 0 , x, v) ∈ T × Y, ∀k ∈ {1, 2},
are skew-evolution semiflows, over all evolution semiflows ϕ on X.

Definition 10

The skew-evolution semiflow C = (ϕ, Φ) is called uniformly exponentially dichotomic if there exist two projectors P 1 and P 2 compatible with C, some constants N 1 ≥ 1, N 2 ≥ 1 and ν 1 , ν 2 > 0 such that:

e ν 1 (t-s) Φ 1 (t, t 0 , x)v ≤ N 1 Φ 1 (s, t 0 , x)v ; (8) e ν 2 (t-s) Φ 2 (s, t 0 , x)(x)v ≤ N 2 Φ 2 (t, t 0 , x)(x)v , (9)
for all (t, s), (s, t 0 ) ∈ T and all (x, v) ∈ Y .

Remark 10 Without any loss of generality we can consider

N = max{N 1 , N 2 } and ν = min{ν 1 , ν 2 }. We will call N 1 , N 2 , ν 1 , ν 2 , respectively N , ν dichotomic characteristics.
In what follows we will define generalizations for skew-evolution semiflows of some asymptotic properties given by L. Barreira and C. Valls for evolution equations in [START_REF] Barreira | Stability of Nonautonomous Differential Equations[END_REF].

Definition 11

The skew-evolution semiflow C = (ϕ, Φ) is called Barreira-Valls exponentially dichotomic if there exist two projectors P 1 and P 2 compatible with C, some constants N ≥ 1, α 1 , α 2 > 0 and

β 1 , β 2 > 0 such that: Φ 1 (t, t 0 , x)v ≤ N e -α 1 t e β 1 s Φ 1 (s, t 0 , x)v ; (10) Φ 2 (s, t 0 , x)v ≤ N e -α 2 t e β 2 s Φ 2 (t, t 0 , x)v , (11)
for all (t, s), (s, t 0 ) ∈ T and all (x, v) ∈ Y .

Definition 12

The skew-evolution semiflow C = (ϕ, Φ) is called exponentially dichotomic if there exist two projectors P 1 and P 2 compatible with C, some mappings N 1 , N 2 : R + → R * + and some constants ν 1 , ν 2 > 0 such that:

Φ 1 (t, t 0 , x)v ≤ N 1 (s)e -ν 1 t Φ 1 (s, t 0 , x)v ; (12) Φ 2 (s, t 0 , x)v ≤ N 2 (s)e -ν 2 t Φ 2 (t, t 0 , x)v , (13)
for all (t, s), (s, t 0 ) ∈ T and all (x, v) ∈ Y .

Some immediate connections concerning the previously defined asymptotic properties for skew-evolution semiflows are given by Remark 11 (i) A uniformly exponentially dichotomic skew-evolution semiflow is Barreira-Valls exponentially dichotomic;

(ii) Barreira-Valls exponentially dichotomic skew-evolution semiflow is exponentially dichotomic.

The reciprocal statements are not true, as shown in what follows. Hence, the next example emphasizes a skew-evolution semiflow which is Barreira-Valls exponentially dichotomic, but is not uniformly exponentially dichotomic.

Example 4 Let f : R + → (0, ∞) be a decreasing function with the property that there exists lim t→∞ f (t) = l > 0. We will consider λ > f (0). Let C = C(R, R) be the metric space of all continuous functions x : R → R, with the topology of uniform convergence on compact subsets of R. C is metrizable relative to the metric given in Example 1. We denote X the closure in C of the set {f t , t ∈ R + }, where

f t (τ ) = f (t + τ ), ∀τ ∈ R + . Then (X, d) is a metric space. The mapping ϕ : T × X → X, ϕ(t, s, x)(τ ) = x t-s (τ ) = x(t -s + τ ) is an evolution semiflow on X. Let us consider the Banach space V = R 2 with the norm v = |v 1 | + |v 2 |, v = (v 1 , v 2 ) ∈ V . The mapping Φ : T × X → B(V ), Φ(t, s, x)v = = e t sin t-s sin s-2(t-s)-t s x(τ -s)dτ v 1 , e 3(t-s)-2t cos t+2s cos s+ t s x(τ -s)dτ v 2 ,
where t ≥ s ≥ 0, (x, v) ∈ Y , is an evolution cocycle over the evolution semiflow ϕ. We consider the projectors Let us suppose now that C = (ϕ, Φ) is uniformly exponentially dichotomic. According to Definition 10, there exist N ≥ 1 and ν 1 > 0, ν 2 > 0 such that e t sin t-s sin s+2s-2t e -t s x(τ -s)dτ

P 1 , P 2 : Y → Y , P 1 (x, v) = (v 1 , 0), P 2 (x, v) = (0, v 2 ), for all x ∈ X and all v = (v 1 , v 2 ) ∈ V ,
|v 1 | ≤ N e -ν 1 (t-s) |v 1 |, ∀t ≥ s ≥ 0
and

N e 3t-3s-2t cos t+2s cos s e t s x(τ -s)dτ |v 2 | ≥ e ν 2 (t-s) |v 2 |, ∀t ≥ s ≥ 0.
If we consider t = 2nπ + π 2 and s = 2nπ, we have in the first inequality

e 2nπ-π 2 ≤ N e -ν π 2 e 2nπ+ π 2 2nπ x(τ -2nπ)dτ ≤ N e (-ν 1 +λ) π 2 ,
which, for n → ∞, leads to a contradiction. In the second inequality, if we consider t = 2nπ and s = 2nππ, we obtain

N e -4nπ+3π ≥ e ν 2 π e 2nπ 2nπ-π x(τ -2nπ+π)dτ ≥ e (ν 2 -λ)π .
For n → ∞, a contradiction is obtained.

We obtain that C is not uniformly exponentially dichotomic.

There exist exponentially dichotomic skew-evolution semiflows that are not Barreira-Valls exponentially dichotomic, as in the next Example 5 We consider the metric space (X, d), the Banach space V , the evolution semiflow ϕ and the projectors P 1 and P 2 defined as in Example 4. Let us consider a continuous function

g : R + → [1, ∞) with g(n) = e n•2 2n and g n + 1 2 2n = 1.
The mapping Φ : T × X → B(V ), defined by .

Φ(t, s, x)v = g(s) g(t) e -(t-s)-t s x(τ -s)dτ v 1 , g (t) g(s
As, for n → ∞, two contradictions are obtained, it follows that C is not Barreira-Valls exponentially dichotomic.

Let us present some particular classes of dichotomy, given by Definition 13 A skew-evolution semiflow C = (ϕ, Φ) is uniformly polynomially dichotomic if there exist two projectors P 1 and P 2 compatible with C and some constants N ≥ 1 and α 1 > 0, α 2 > 0 such that:

Φ 1 (t, s, x)v ≤ N t -α 1 s α 1 P 1 (x)v ; (14)
P 2 (x)v ≤ N t -α 2 s α 2 Φ 2 (t, s, x)v ; (15)
for all (t, s) ∈ T and all (x, v) ∈ Y .

Definition 14 A skew-evolution semiflow C = (ϕ, Φ) is Barreira-Valls polynomially dichotomic if there exist some constants N ≥ 1, α 1 > 0, α 2 > 0 and β 1 > 0, β 2 > 0 such that:

Φ 1 (t, s, x)v ≤ N t -α 1 s β 1 P 1 (x)v ; (16)
P 2 (x)v ≤ N t -α 2 s β 2 Φ 2 (t, s, x)v , (17)
for all (t, s) ∈ T and all (x, v) ∈ Y .

Definition 15 A skew-evolution semiflow C = (ϕ, Φ) is polynomially dichotomic if there exist a function N : R + → [1, ∞), some constants α 1 > 0 and α 2 > 0 such that:

Φ 1 (t, s, x)v ≤ N (s)t -α 1 P 1 (x)v ; (18)
P 2 (x)v ≤ N (s)t -α 2 Φ 2 (t, s, x)v , (19)
for all (t, s) ∈ T and all (x, v) ∈ Y .

Relations between the defined classes of dichotomy are described by Remark 12 (i) A uniformly polynomially dichotomic skew-evolution semiflow is Barreira-Valls polynomially dichotomic;

(ii) A Barreira-Valls polynomially dichotomic is polynomially dichotomic.

The next example shows a skew-evolution semiflow which is Barreira-Valls polynomially dichotomic but is not uniformly polynomially dichotomic.

Example 6

We consider the metric space (X, d), the Banach space V , the evolution semiflow ϕ and the projectors P 1 and P 2 defined as in Example 4. We will consider the mapping g : R + → R, g(t) = (t + 1) 3-sin ln(t+1) .

We define

Φ(t, s, x)v = g(s) g(t) e -t s x(τ -s)dτ v 1 , g(t) g(s) e t s x(τ -s)dτ v 2 , (t, s) ∈ T, (x, v) ∈ Y.
Φ is an evolution cocycle over ϕ. Due to the properties of function x and of We suppose now that C is uniformly polynomially dichotomic. According to Definition 13, there exist N ≥ 1 and α 1 > 0 such that (s + 1) 3 (t + 1) 3 (t + 1) sin ln(t+1) (s + 1) sin ln(s+1) ≤ N t -α 1 s α 1 e t s x(τ -s)dτ for all t ≥ s ≥ t 0 . Let us consider t = e 2nπ+ π 2 -1 and s = e 2nπ-π 2 -1.

function f : (0, ∞) → (0, ∞), f (u) = e u u , we have |Φ 1 (t, s, x)v| ≤ (s + 1) 4 (t + 1) 2 e -l(t-s) |v 1 | ≤ (s + 1) 2 s + 1 t + 1 2 e -lt e ls |v 1 | ≤ ≤ s(s + 1) 2 t t -l s l |v 1 | ≤ 4t -(1+l) s 3+l |v 1 |, for all t ≥ s ≥ t 0 = 1 and all (x, v) ∈ Y . Also,
We have, if we consider the properties of function x, that e (2n-λ-1)π ≤ N e 2α 1 , which, if n → ∞, leads to a contradiction. Also, as in Definition 13, there exist N ≥ 1 and α 1 > 0 such that N (t + 1) 3 (s + 1) 3

(s + 1) sin ln(s+1) (t + 1) sin ln(t+1) ≥ t α 2 s -α 2 e -t s x(τ -s)dτ for all t ≥ s ≥ t 0 , which implies, for t = e 2nπ+ π 2 -1 and s = e 2nπ-π 2 -1,

N e (-2n+λ-1)π ≥ e -2α 2 ,
which, for n → ∞, is a contradiction. We obtain thus that C is not uniformly polynomially dichotomic.

There exist skew-evolution semiflows that are polynomially dichotomic but are not Barreira-Valls polynomially dichotomic.

Example 7 Let us consider the data given in Example 5. We obtain

|Φ(t, s, x)P 1 (x)v| ≤ g(s)e -(1+l)(t-s) |v 1 | ≤ g(s)e (1+l)s t -(1+l)
and g(s)e (1+l)s |Φ(t, s, x)P 2 (x)v| ≥ e (1+l)t |v 2 | ≥ t (1+l) |v 2 |, for all (t, s, x, v) ∈ T × Y , which proves that the skew-evolution semiflow C = (ϕ, Φ) is polynomially dichotomic.

If we suppose that C is Barreira-Valls polynomially dichotomic, there exist N ≥ 1, α 1 > 0, α 2 > 0 and β 1 > 0, β 2 > 0 such that g(s) g(t)

≤ N t -α 1 s β 1 e t-s+ t s x(τ -s)dτ and t α 2 ≤ N g(t) g(s) s β 2 e t-s+ t s x(τ -s)dτ .

If we consider t = n + 1 2 2n and s = n, we obtain

e n•2 2n ≤ N • n -α 1 • n β 1 • e 1+λ 2 2n and e n•2 2n ≤ N n + 1 2 2n -α 2 • n β 2 • e 1+λ 2 2n
.

For n → ∞, two contradictions are obtained, which proves that C is not Barreira-Valls polynomially dichotomic.

Main results

The first results will prove some relations between all the classes of dichotomies.

Proposition 1 A uniformly exponentially dichotomic skew-evolution semiflow C = (ϕ, Φ) is uniformly polynomially dichotomic.

Proof. Let us consider in Definition 10, without any loss of generality, t 0 = 1. It also assures the existence of constants N ≥ 1 and

ν 1 > 0 such that Φ 1 (t, s, x)v ≤ N e -ν 1 (t-s) P 1 (x)v . As e -u ≤ 1 u + 1 , ∀u ≥ 0 and t s ≤ t -s + 1, ∀t ≥ s ≥ 1, it follows that Φ 1 (t, s, x)v ≤ N (t -s + 1) -ν 1 P 1 (x)v ≤ N t -ν 1 s ν 1 P 1 (x)v ,
for all t ≥ s ≥ 1 and all (x, v) ∈ Y . We also have the property of function

f : (0, ∞) → (0, ∞), f (u) = e u u
of being nondecreasing, which assures the inequality e s e t ≤ s t , ∀t ≥ s > 0 and, further, for all t ≥ s ≥ 1 and all (x, v) ∈ Y , we have

P 2 (x)v ≤ N e -ν 2 t e ν 2 s Φ 2 (t, s, x)v ≤ N t -ν 2 s ν 2 Φ 2 (t, s, x)v ,
where constants N ≥ 1 and ν 2 > 0 are also given by Definition 10. Thus, according to Definition 13, C is uniformly polynomially dichotomic.

We give an example of a skew-evolution semiflow which is uniformly polynomially dichotomic, but is not uniformly exponentially dichotomic.

Example 8 Let (X, d) be the metric space, V the Banach space, ϕ the evolution semiflow, P 1 and P 2 the projectors given as in Example 4.

Let us consider the function g : R + → R, given by g(t) = t 2 + 1 and let us define

Φ(t, s, x)v = g(s) g(t) e -t s x(τ -s)dτ v 1 , g(t) g(s) e t s x(τ -s)dτ v 2 , (t, s) ∈ T, (x, v) ∈ Y.
We can consider t 0 = 1 in Definition 13. As,

s 2 + 1 t 2 + 1 ≤ s t , for t ≥ s ≥ 1 and
according to the properties of function x, we have

s 2 + 1 t 2 + 1 e -t s x(τ -s)dτ |v 1 | ≤ t -(1+l) s 1+l |v 1 | and t 2 + 1 s 2 + 1 e t s x(τ -s)dτ |v 2 | ≥ t (2+l) s -(4+l) |v 2 |,
for all t ≥ s ≥ 1 and all v ∈ V . It follows that C = (ϕ, Φ) is uniformly polynomially dichotomic.

If the skew-evolution semiflow C = (ϕ, Φ) is also uniformly exponentially according to Definition 10, there exist N ≥ 1 ν 1 > 0 and ν 2 > 0 such that

s 2 + 1 t 2 + 1 |v 1 | ≤ N e -ν 1 (t-s) e -l(t-s) |v 1 | and N t 2 + 1 s 2 + 1 |v 2 | ≥ e ν 2 (t-s) e l(t-s) |v 2 |,
for all t ≥ s ≥ t 0 and all v ∈ V. If we consider s = t 0 and t → ∞, two contradictions are obtained, which proves that C is not uniformly exponentially dichotomic.

Proposition 2 A Barreira-Valls exponentially dichotomic skew-evolution semiflow C = (ϕ, Φ) with α i ≥ β i > 0, i ∈ {1, 2}, is Barreira-Valls polynomially dichotomic.

Proof. According to Definition 11, there exist some constants N ≥ 1, α 1 > 0 and

β 1 > 0 such that Φ 1 (t, s, x)v ≤ N e -α 1 t e β 1 s P 1 (x)v , ∀(t, s) ∈ T, ∀(x, v) ∈ Y.
As the mapping f : (0, ∞) → (0, ∞), defined by f (u) = e u u is nondecreasing, and as, by hypothesis, we can chose α 1 ≥ β 1 , we obtain that

Φ 1 (t, s, x)v ≤ N t -α 1 e -β 1 s s β 1 e β 1 s P 1 (x)v = N t -α 1 s β 1 P 1 (x)v ,
for all t ≥ s > 0 and all (x, v) ∈ Y .

Analogously, we obtain

P 2 (x)v ≤ N e -α 2 t e β 2 s Φ 2 (t, s, x)v ≤ N t -α 2 s β 2 Φ 2 (t, s, x)v ,
for all t ≥ s > 0 and all (x, v) ∈ Y , where the constants N ≥ 1, α 2 > 0 and β 2 > 0 are also assured by Definition 10, with the property α 2 ≥ β 2 .

Hence, according to Definition 13, C is Barreira-Valls polynomially dichotomic.

There exist skew-evolution semiflows that are Barreira-Valls polynomially dichotomic, but are not Barreira-Valls exponentially dichotomic.

Example 9

We consider the metric space (X, d), the Banach space V , the evolution semiflow ϕ and the projectors P 1 and P 2 defined as in 4.

Let us consider the function g : R + → R, given by g(t) = t + 1 and let us define an evolution cocycle Φ as in Example 8. We obtain

s + 1 t + 1 e -t s x(τ -s)dτ |v 1 | ≤ s 2 t e -l(t-s) |v 1 | ≤ t -1-l s
≤ N t 0 + 1 , ∀t ≥ t 0 .
For t → ∞, we obtain two contradictions, and, hence, C is not Barreira-Valls exponentially dichotomic.

Proposition 3 An exponentially dichotomic skew-evolution semiflow C = (ϕ, Φ) is polynomially dichotomic.

Proof. Definition 12 assures the existence of a function

N 1 : R + → [1, ∞) and a constant ν 1 > 0 such that Φ 1 (t, s, x)v ≤ N 1 (s)e -ν 1 t P 1 (x)v , ∀(t, s) ∈ T, ∀(x, v) ∈ Y.
As following inequalities e t ≥ t + 1 > t hold for all t ≥ 0, we obtain

Φ 1 (t, s, x)v ≤ N 1 (s)t -ν 1 P 1 (x)v ,
for all t ≥ s > 0 and all (x, v) ∈ Y . As, by Definition 12 there a function N 2 : R + → [1, ∞) and a constant ν 2 > 0 such that

P 2 (x)v ≤ N 2 (s)e -ν 2 t Φ 2 (t, s, x)v , ∀(t, s) ∈ T, ∀(x, v) ∈ Y.
Analogously, as previously, we have

P 2 (x)v ≤ N 2 (s)t -ν 2 Φ 2 (t, s, x)v ,
for all t ≥ s > 0 and all (x, v) ∈ Y .

Hence, according to Definition 15, C is polynomially dichotomic.

We present an example of a skew-evolution semiflow which is polynomially dichotomic, but is not exponentially dichotomic.

Example 10 We consider the metric space (X, d), the Banach space V , the evolution semiflow ϕ, the projectors P A characterization for the classic and mostly encountered property of exponential dichotomy is given by the next Theorem 1 Let C = (ϕ, Φ) be a strongly measurable skew-evolution semiflow. C is exponentially dichotomic if and only if there exist two projectors P 1 and P 2 compatible with C with the properties that C 1 has bounded exponential growth and C 2 has exponential decay such that (i) there exist a constant γ > 0 and a mapping D : R + → [1, ∞) with the property:

∞ s e (τ -s)γ Φ 1 (τ, s, x)v dτ ≤ D(s) P 1 (x)v ,
for all s ≥ 0 and all (x, v) ∈ Y ;

(ii) there exist a constant ρ > 0 and a nondecreasing mapping D : R + → [1, ∞) with the property:

t t 0 e (t-τ )ρ Φ 2 (τ, t 0 , x)v dτ ≤ D(t 0 ) Φ 2 (t, t 0 , x)v , for all t ≥ t 0 ≥ 0 and all (x, v) ∈ Y . Proof. Necessity. As C is exponentially dichotomic, according to Definition 12, there exist N 1 , N 2 : R + → R * + and ν 1 , ν 2 > 0 such that Φ 1 (t, t 0 , x)v ≤ N 1 (s)e -ν 1 t Φ 1 (s, t 0 , x)v and Φ 2 (s, t 0 , x)v ≤ N 2 (s)e -ν 2 t Φ 2 (t, t 0 , x)v ,
for all (t, s), (s, t 0 ) ∈ T and all (x, v) ∈ Y . In order to prove (i), let us define γ = -ν 1 2 . We obtain successively

∞ s e (τ -s)γ Φ 1 (τ, s, x)v dτ ≤ N 1 (s) Φ 1 (s, s, x)v ∞ s e -ν 1 2 (τ -s) e -ν 1 (s-τ ) dτ = = N (s) P 1 (x)v ∞ s e -ν 1 2 (s-τ ) dτ = D(s) P 1 (x)v ,
for all s ≥ 0 and all (x, v) ∈ Y , where we have denoted

D(u) = N 1 (u) γ , u ≥ 0.
To prove (ii), we define ρ = ν 2 2 . Following relations

t t 0 e (t-τ )ρ Φ 2 (τ, t 0 , x)v dτ ≤ N 2 (t 0 ) Φ 2 (t, t 0 , x)v t t 0 e ν 2 2 (t-τ ) e -ν 2 (t-τ ) dτ ≤ ≤ D(t 0 ) Φ 2 (t, t 0 , x)v
hold for all s ≥ 0 and all (x, v) ∈ Y , where we have denoted

D(u) = 2N 2 (u) ρ , u ≥ 0.
Sufficiency. According to relation (i), the γ-shifted skew-evolution semiflow C 1 γ = (ϕ, Φ 1 γ ), defined as in Example 3, has bounded exponential growth and there exists D :

R + → [1, ∞) such that ∞ s Φ 1 γ (τ, s, x)v dτ ≤ D(s) P 1 (x)v ,
for all s ≥ 0 and all (x, v) ∈ Y . First of all, we will prove that there exists D 1 : R + → [1, ∞) such that Φ 1 γ (t, s, x)v ≤ D 1 (s) P 1 (x)v , for all t ≥ s ≥ 0 and all (x, v) ∈ Y . Let us consider, for t ≥ s + 1, c = Further, it follows that Φ 1 (t, s, x)v ≤ D 1 (s)e -(t-s)γ v , ∀t ≥ s ≥ 0.

According to (ii), there exist a constant ρ > 0 and a nondecreasing mapping D : R + → [1, ∞) such that t t 0 e -(τ -t 0 )ρ Φ 2 (τ, t 0 , x)v dτ ≤ D(t 0 )e -(t-t 0 )ρ Φ 2 (t, t 0 , x)v , for all t ≥ t 0 ≥ 0 and all (x, v) ∈ Y . Thus, M (t 0 )e -ω(u-s) e ω(u-s) Φ 2 -ρ (u, t 0 , x)v du ≤ ≤ M (t 0 ) t t 0 Φ 2 -ρ (u, t 0 , x)v du ≤ M (t 0 ) D(t 0 ) Φ 2 -ρ (t, t 0 , x)v .

We obtain

Φ 2 -ρ (s, t 0 , x)v ≤ M (t 0 ) D(t 0 ) c Φ 2 -ρ (t, t 0 , x)v ,
for all t ≥ s ≥ t 0 ≥ 0 with t ≥ s + 1 and all (x, v) ∈ Y. Now, for t ∈ [s, s + 1) and s ≥ t 0 ≥ 0, we have Φ 2 -ρ (s, t 0 , x)v ≤ M (t 0 )e ω(1) Φ 2 -ρ (t, t 0 , x)v , for all (x, v) ∈ Y. Finally, we obtain Φ 2 -ρ (s, t 0 , x)v ≤ D 2 (t 0 ) Φ 2 -ρ (t, t 0 , x)v , for all t ≥ s ≥ t 0 ≥ 0 and all (x, v) ∈ Y , where we have denoted 1) , u ≥ 0.

D 2 (u) = M (u) D(u) c + e ω(
Thus, it follows that e -(s-t 0 )ρ Φ 2 (s, t 0 , x)v ≤ D 2 (t 0 )e -(t-t 0 )ρ Φ 2 (t, t 0 , x)v , which implies Φ 2 (s, t 0 , x)v ≤ D 2 (t 0 )e -(t-s)ρ Φ 2 (t, t 0 , x)v , for all t ≥ s ≥ t 0 ≥ 0 and all (x, v) ∈ Y , or

P 2 (x)v ≤ D 2 (s)e -(t-s)ρ Φ 2 (t, s, x)v ,
for all t ≥ s ≥ 0 and all (x, v) ∈ Y . Hence, the skew-evolution semiflow is exponentially dichotomic, which ends the proof.

  compatible with the skew-evolution semiflow C = (ϕ, Φ).We have, according to the properties of function x,|Φ(t, s, x)P 1 (x)v| = e t sin t-s sin s+2s-2t e -t s x(τ -s)dτ |v 1 | ≤ ≤ e -t+3s e -l(t-s) |v 1 | = e -(1+l)t e (3+l)s |v 1 |, for all (t, s, x, v) ∈ T × Y . Also, following relations |Φ(t, s, x)P 2 (x)v| = e 3t-3s-2t cos t+2s cos s+ t s x(τ -s)dτ |v 2 | ≥ ≥ e t-s e l(t-s) |v 2 | = e (1+l)t e -(1+l)s |v 2 |, hold for all (t, s, x, v) ∈ T × Y . Hence, the skew-evolution semiflow C = (ϕ, Φ) is Barreira-Valls exponentially dichotomic with N = 1, α 1 = α 2 = β 2 = 1 + l, β 1 = 3 + l.

1 0e

 1 -ω(u) du ≤ t-s 0 e -ω(u) du = t s e -ω(t-τ ) dτ.Hence, for t ≥ s + 1, we obtainc| < v * , Φ 1 γ (t, s, x)v > | ≤ t s e -ω(t-τ ) | < v * , Φ 1 γ (t, s, x)v > |dτ = = t s e -ω(t-τ ) Φ 1 γ (t, τ, ϕ(τ, s, x)) * v * Φ 1 γ (τ, s, x)v dτ ≤ ≤ M P 1 (x)v * t s Φ 1 γ (τ, s, x)v dτ ≤ M D(s) P 1 (x)v P 1 (x)v * ,where v ∈ V , v * ∈ V * and M , ω are given by Definition 5 and Remark 3. Hence,Φ 1 (t, s, x)v ≤ M D(s) c , ∀t ≥ s + 1, ∀(x, v) ∈ Y. Now, for t ∈ [s, s + 1), we have Φ 1 (t, s, x)v ≤ M e ω(1) P 1 (x)v , ∀(x, v) ∈ Y.Thus, we obtainΦ 1 γ (t, s, x)v ≤ D 1 (s) P 1 (x)v ,for all t ≥ s ≥ 0 and all (x, v) ∈ Y , where we have denoted D 1 (u) = M e ω(1) + D(u) c , u ≥ 0.

2 1 0e

 21 -ρ (τ, t 0 , x)v dτ ≤ D(t 0 ) Φ 2 -ρ (t, t 0 , x)v ,for all t ≥ t 0 ≥ 0 and all (x, v) ∈ Y , where Φ 2 -ρ is defined as in Example 3. Let functions M and ω be given by Definition 6. Let us denote c = -ω(τ ) dτ = s+1 s e -ω(u-s) du.Further, for t ≥ s + 1 and s ≥ t 0 ≥ 0, we obtainc Φ 2 -ρ (s, t 0 , x)v = s+1 s e -ω(u-s) Φ 2 -ρ (s, t 0 , x)v du ≤ ≤ s+1 s

  Let us suppose that C is Barreira-Valls exponentially dichotomic. There exist N ≥ 1 and α 1 , α 2 , β 1 , β 2 > 0 such that

	Further, if we consider t = n +	1 2 2n and s = n, it follows that
	e n(2 2n +1+α 1 -β 1 ) ≤ N e	λ-α 1 2 2n	and e n(2 n +α 2 -β 2 ) ≤ N e	1+λ-α 2 2 2n
			g(s) g(t)	e t s x(τ -s)dτ
	and	e α 2 t e -t ≤ N	g(t) g(s)	e β 2 s e -s e	t s x(τ -s)dτ .

) e t-s+ t s x(τ -s)dτ v 2 is an evolution cocycle over the evolution semiflow ϕ. As

|Φ(t, s, x)P 1 (x)v| ≤ g(s)e -(1+l)(t-s) |v 1 |, ∀(t, s, x, v) ∈ T × Y and g(s) |Φ(t, s, x)P 2 (x)v| ≥ e (1+l)(t-s) |v 2 |, ∀(t, s, x, v) ∈ T × Y, the skew-evolution semiflow C = (ϕ, Φ) is exponentially dichotomic, with N 1 (u) = N 2 (u) = g(u)

• e (1+l)u , u ≥ 0, and ν 1 = ν 2 = 1 + l. s ≤ N e t e -α 1 t e β 1 s e

  2+l |v 1 | -s)dτ |v 2 | ≥ t 1+l s -2-l |v 2 |, for all t ≥ s ≥ 1 and all v ∈ V . It follows that the skew-evolution semiflow C = (ϕ, Φ) is Barreira-Valls polynomially dichotomic.Let us suppose that C is also Barreira-Valls exponentially dichotomic. According to Definition 11, there exist some constantsN ≥ 1, α 1 , β 1 > 0 and α 2 , β 2 > 0 such that -s)dτ |v 1 | ≤ N e -α 1 t e β 1 s |v 1 | -s)dτ |v 2 | ≥ e α 2 t e -β 2 s |v 2 |,for all (t, s), (s, t 0 ) ∈ T and all (x, v) ∈ Y . We consider s = t 0 . We have

	and s x(τ and t + 1 s + 1 e t s x(τ s + 1 t + 1 e -t N t + 1 s + 1 e t s x(τ e α 1 t t + 1 ≤ N t 0 + 1 and	e α 2 t t + 1

  1 , P 2 and function g as in Example 9.

	Let	Φ(t, s, x)v =	g(s) g(t)	e	t s x(τ -s)dτ |v 1 |,	g(t) g(s)	e -t

s x(τ -s)dτ |v 2 | be an evolution cocycle. Analogously as in the mentioned Example, the skew-evolution semiflow C is Barreira-Valls polynomially dichotomic, and, according to Remark 12 (ii), it is also polynomially dichotomic. On the other hand, if we suppose that C is exponentially dichotomic, there exist N 1 , N 2 : R + → R * + and ν 1 , ν 2 > 0 such that

s + 1 t + 1 |v 1 | ≤ N 1 (s)e -(ν 1 +l)t e ls |v 1 | and |v 2 | ≤ N 2 (s)e -(ν 2 +l)t t + 1 s + 1 |v 2 |,

for all (t, s) ∈ T and all (x, v) ∈ Y . If we consider s = t 0 and t → ∞, we obtain two contradictions, which shows that C is not exponentially dichotomic.

Acknowledgments. This work is financially supported from the Exploratory Research Grant CNCSIS PN II ID 1080 No. 508/2009 of the Romanian Ministry of Education, Research and Innovation.


Masaru Kamada
email: kamada@mx.ibaraki.ac.jp

Rentsen Enkhbat
email: renkhbat46@ses.edu.mn

Spline Interpolation in Piecewise Constant Tension

Locally supported splines in tension are constructed where the tension, which has ever been constant over the entire domain, is allowed to change at sampling points.

Introduction

A cubic spline gives the interpolation of data that minimizes the square integral of its second derivative [START_REF] De Boor | Best approximation properties of spline functions of odd degree[END_REF][START_REF] Holladay | Smoothest curve approximation[END_REF][START_REF] Schoenberg | On interpolation by spline functions and its minimal properties[END_REF] and is crowned as the smoothest interpolation in this sense. A linear spline gives the piecewise linear interpolation that is most straight but nonsmooth. The linear spline is characterized as minimizing the square integral of its first derivative [START_REF] De Boor | Best approximation properties of spline functions of odd degree[END_REF][START_REF] Schoenberg | On interpolation by spline functions and its minimal properties[END_REF]. A spline in tension [START_REF] Ahlberg | The Theory of Splines and Their Applications[END_REF][START_REF] Schweikert | An interpolation curve using a spline in tension[END_REF] was devised as a generalization of those two splines. It minimizes the integral of a weighted sum of the squared second derivative and the squared first derivative. By increasing the weight called tension, we can make a spline in tension approach the most straight linear spline while retaining smoothness similar to that of the cubic spline.

The spline in tension has been known for more than 40 years. It has been extended even to the multidimensional cases [START_REF] Benbourhim | Approximation of vector fields by thin plate splines with tension[END_REF][START_REF] Mitasova | Interpolation by regularized spline with tension: I. theory and implementation[END_REF] and is now supported by a standard software library [START_REF] Polyakov | Graphics Programming with GDI+ & DirectX[END_REF]. But the tension has ever been a single constant over the entire domain.

In this paper, we look at the splines as the output of a linear dynamical system with a series of delta functions input. That is the same way as how the exponential splines and their locally supported basis were successfully constructed in [START_REF] Unser | Cardinal exponential splines: Part I-Theory and filtering algorithms[END_REF][START_REF] Unser | Cardinal exponential splines: Part II-Think analog, act digital[END_REF]. In addition, attending to that the linear dynamical system theory [START_REF] Kalman | A new approach to linear filtering and prediction problems[END_REF] allows for time-varying dynamical parameters, we shall place different tension in each sampling interval. Then we will obtain locally supported splines in piecewise constant tension that can change the interpolation characteristics from a sampling interval to another.

Preliminaries

A spline f in tension interpolating the data

{(t k , f k )} ∞ k=-∞ given at strictly increasing sampling points (• • • < t -2 < t -1 < t 0 < t 1 < t 2 < • • • )
on the real line is defined as the twice-differentiable function that minimizes the integral of a weighted sum

∫ ∞ -∞ (f (2) (t)) 2 + p(t) 2 (f (1) (t)) 2 dt (1)
of its squared second derivative f (2) and squared first derivative f (1) subject to the constraints

f (t k ) = f k , k = 0, ±1, ±2, • • • . ( 2
)
In the case p = 0, f is identical with the cubic spline [START_REF] De Boor | Best approximation properties of spline functions of odd degree[END_REF][START_REF] Holladay | Smoothest curve approximation[END_REF][START_REF] Schoenberg | On interpolation by spline functions and its minimal properties[END_REF]. By increasing p, f approaches the most straight linear spline as if the curve were pulled from both ends. That is why p is called tension [START_REF] Ahlberg | The Theory of Splines and Their Applications[END_REF][START_REF] Schweikert | An interpolation curve using a spline in tension[END_REF].

The tension p has originally been a single constant over the entire domain [START_REF] Schweikert | An interpolation curve using a spline in tension[END_REF]. We shall now relax the tension to be a non-negative constant in each sampling interval, i.e.,

p(t) = p k ≥ 0, for t ∈ [t k , t k+1 ), (3)
which can change at the sampling points.

By the calculus of variation, the minimization problem is reduced to solution of the Euler-Lagrange differential equation

f (4) (t) -2p(t)p (1) (t)f (1) (t) -p(t) 2 f (2) (t) = w(t), ( 4
)
where w is a series of the Dirac delta functions

w(t) = ∞ ∑ n=-∞ w n δ(t -t n )
to be determined so that (2) holds good. We do not have, however, a practical means to decide the coefficients {w n } for given

{(t k , f k )}.
In practice, it is convenient to have locally supported functions {y n } satisfying

y n (t) = 0, for t / ∈ [t n , t n+4 ] (5)
of which linear combination

f (t) = ∞ ∑ n=-∞ c n y n (t) (6)
represents any possible f . This y n can be constructed by

y (4) n (t) -2p(t)p (1) (t)y (1) n (t) -p(t) 2 y (2) n (t) = u n (t) (7)
for some appropriately chosen

u n (t) = 4 ∑ l=0 u l,n δ(t -t n+l ) (8)
as long as the sampled data system [START_REF] Mitasova | Interpolation by regularized spline with tension: I. theory and implementation[END_REF] with the impulse input ( 8) is completely controllable [START_REF] Ho | Controllability of linear dynamical systems[END_REF]. Once we obtain y n (t), we have only to determine the coefficients {c n } by the linear equations

f k = ∞ ∑ n=-∞ c n y n (t k ), k = 0, ±1, ±2, • • • from {(t k , f k )}.
Although infinitely many coefficients and data are involved in the equations, we can solve the linear equations for finitely many {c n } from finitely many {(t k , f k )} in practice because {y n } are locally supported.

Construction of locally supported splines in piecewise constant tension

A state-space representation of the differential equation ( 7) is

x (1)

n (t) = F (t)x n (t) + gu n (t), y n (t) = hx n (t), (9)
where

F (t) =     0 1 0 0 0 0 1 0 0 0 0 1 0 2p(t)p (1) (t) p(t) 2 0     , x n (t) =      y n y (1) n y (2) n y (3) n      , g =     0 0 0 1     , h = [1 0 0 0] . ( 10
)
The state x n can be expressed by [START_REF] Sontag | Mathematical Control Theory[END_REF] for any real numbers t and v, in terms of the statetransition matrix function Φ and the input u n [START_REF] Sontag | Mathematical Control Theory[END_REF].

x n (t) = Φ(t, v)x n (v) + ∫ t v Φ(t, τ )gu n (τ ) dτ,
Since u n (t) = 0 for t / ∈ {t n , t n+1 , t n+2 , t n+3 , t n+4 }, it follows from (11) that

x n (t) =        0, t < t n Φ(t, t n+l +0)x n (t n+l +0), t n+l < t < t n+l+1 , (l = 0, 1, 2, 3) Φ(t, t n+4 +0)x n (t n+4 +0), t n+4 < t. ( 12
)
Because of the top and bottom lines of [START_REF] Unser | Cardinal exponential splines: Part I-Theory and filtering algorithms[END_REF], y n = hx n is locally supported as (5) if x n (t n+4 +0) = 0. In order to avoid the trivial case u 0,n = u 1,n = u 2,n = u 3,n = u 4,n = 0 that would result in u n ≡ y n ≡ 0, let us fix one of them as u 0,n = 1. Then the problem of constructing a locally supported y n becomes a dead-beat control problem of finding u 1,n , u 2,n , u 3,n , and u 4,n that make the terminal state dead as

x n (t n+4 +0) = 0. ( 13
)
Once the terminal state is controlled to 0, it will stay at 0 forever for t > t n+4 without any beats.

We shall consider two types of state transitions: (i) Those within each sampling interval (t n+l , t n+l+1 ), and (ii) one across each sampling point t n+l .

(i) In the open interval (t n+l , t n+l+1 ), [START_REF] Sontag | Mathematical Control Theory[END_REF] with v = t n+l +0 is reduced to

x n (t) = Φ(t, t n+l +0)x n (t n+l +0), l = 0, 1, 2, 3 (14)
because u n (t) = 0 for t ∈ (t n+l , t n+l+1 ). Besides, F (t) in ( 10) is a constant matrix

F (t) =     0 1 0 0 0 0 1 0 0 0 0 1 0 0 p 2 n+l 0     (15)
because of (3) so that we can calculate the state-transition matrix by the matrix exponential function [START_REF] Sontag | Mathematical Control Theory[END_REF] as follows:

Φ(t, t n+l +0) = e R t t n+l +0 F (υ) dυ =                                                                 1 t -t n+l (t-t n+l ) 2 2 (t-t n+l ) 3 6 0 1 t -t n+l (t-t n+l ) 2 2 0 0 1 t -t n+l 0 0 0 1      if p n+l = 0      1 t -t n+l cosh(p n+l (t-t n+l ))-2 p 2 n+l 0 1 sinh(p n+l (t-t n+l )) p n+l 0 0 cosh(p n+l (t -t n+l )) 0 0 p n+l sinh(p n+l (t -t n+l )) sinh(p n+l (t-t n+l ))-2p n+l (t-t n+l ) p 3 n+l cosh(p n+l (t-t n+l ))-2 p 2 n+l sinh(p n+l (t-t n+l )) p n+l cosh(p n+l (t -t n+l ))       if p n+l > 0. (16)
In the special case that t = t n+l+1 -0, we have the state transition from x n (t n+l +0) to x n (t n+l+1 -0) as follows:

x n (t n+l+1 -0) = Φ(t n+l+1 -0, t n+l +0)x n (t n+l +0), l = 0, 1, 2, 3. (17)
The matrix Φ(t n+l+1 -0, t n+l +0) can be evaluated by the right hand side of (16) with t replaced by t n+l+1 .

(ii) The state transition from x n (t n+l -0) to x n (t n+l +0) across the sampling point t n+l , (l = 0, 1, 2, 3, 4) finds a trouble that F (t) in ( 10) contains a derivative of the function p being discontinuous at t n+l as defined by (3). We had better consider this transition by way of the original differential equation ( 7). An equivalent form of ( 7) is

y (4) n (t) - d dt ( p(t) 2 y (1) n (t) ) = u n (t) (18)
and its integration gives

y (3) n (t) = p(t) 2 y (1) n (t) + ∫ t tn-0 u n (τ )dτ + c, ( 19
)
where c is an integral constant. Substituting t n+l +0 and t n+l -0 for t of (19), we have

y (3) n (t n+l +0) = p(t n+l +0) 2 y (1) n (t n+l +0) +u 0,n + • • • + u n+l,n + c ( 20
)
and

y (3) n (t n+l -0) = p(t n+l -0) 2 y (1) n (t n+l -0) +u 0,n + • • • + u n+l-1,n + c, (21)
respectively. Recall that the spline in tension is sought among the twice-differentiable functions and attend to the definition (3) of p. Then we can reduce (20) and (21) to

y (3) n (t n+l +0) = p 2 n+l y (1) n (t n+l ) +u 0,n + • • • + u n+l,n + c (22) and y (3) n (t n+l -0) = p 2 n+l-1 y (1) n (t n+l ) +u 0,n + • • • + u n+l-1,n + c, (23)
respectively. Subtracting (23) from ( 22), we have

y (3) (t n+l +0) -y (3) (t n+l -0) = (p 2 n+l -p 2 n+l-1 )y (1) (t n+l ) + u l,n , ( 24
)
which tells how to update the state variable y (3) at t n+l and implies that the other state variables y (2) , y (1) , and y are continuous at t n+l . So we can write the state transition across the sampling point t n+l as follows:

x n (t n+l +0) = Φ(t n+l +0, t n+l -0)x n (t n+l -0) + gu l,n , l = 0, 1, 2, 3, 4, (25)
where

Φ(t n+l +0, t n+l -0) =     1 0 0 0 0 1 0 0 0 0 1 0 0 p 2 n+l -p 2 n+l-1 0 1     . (26)
The two types of state transitions (17) and (25) can be combined into the recurrence formulae

x n (t n +0) = gu 0,n = g, x n (t n+l +0) = Ψ n+l x n (t n+l-1 +0) + gu l,n , l = 1, 2, 3, 4, (27)
where we have set

Ψ n+l = Φ(t n+l +0, t n+l -0)Φ(t n+l -0, t n+l-1 +0), l = 1, 2, 3, 4, (28)
and used our choice u 0,n = 1 and the initial state x(t n -0) = 0. By these recurrence formulae, we can write the terminal state as follows:

x n (t n+4 +0) = Ψ n+4 Ψ n+3 Ψ n+2 Ψ n+1 g +Ψ n+4 Ψ n+3 Ψ n+2 gu 1,n +Ψ n+4 Ψ n+3 gu 2,n +Ψ n+4 gu 3,n +gu 4,n .
(

Then we can determine u 1 , u 2 , u 3 , and u 4 that makes the terminal state x n (t n+4 +0) be zero by

    u 1,n u 2,n u 3,n u 4,n     = -[Ψ n+4 Ψ n+3 Ψ n+2 g Ψ n+4 Ψ n+3 g Ψ n+4 g g] -1 Ψ n+4 Ψ n+3 Ψ n+2 Ψ n+1 g. ( 30
)
Existence of the inverse matrix is equivalent to the complete controllability of the sampled-data system with the impulse control u n input. We do not have the condition in a simpler form due to the complication caused by timevarying dynamics and non-uniform sampling. Even the uniform sampling case is yet to be investigated.

For the numerical evaluation of y n , we first compute the states {x n (t n+l +0)}

=            [ 1 t -t n+l (t-t n+l ) 2 2 (t-t n+l ) 3 6 ] if p n+l = 0 [ 1 t -t n+l cosh(p n+l (t-t n+l ))-2 p 2 n+l sinh(p n+l (t-t n+l ))-2p n+l (t-t n+l ) p 3 n+l ] if p n+l > 0 (32)
which follow from ( 12), ( 16), and the continuity of y n over the entire domain.

Numerical examples

Test data were prepared by concatenating a sampled smooth curve and a sampled polygonal line. Their interpolation was computed as a linear combination of the locally supported splines in tension.

The cubic spline interpolation (equivalent to the case p(t) ≡ 0) is shown in Fig. 1. The cursive part is reproduced in a good shape but the polygonal part suffers from inter-sample vibration. The linear spline interpolation (equivalent to the case p(t) → ∞) in Fig. 2 behaves in the opposite way. Reproduction of the polygonal part is perfect but there is no smootheness. Interpolation by a spline in constant tension (p(t) ≡ 10) in Fig. 3 provides a good compromise between the cubic and linear spline interpolation. It is fairly smooth and has less vibration. Some may say that the cursive part is not smooth enough and rather polygonal in Fig. 3. In this case, we can obtain a better interpolation by varying the tension in time. Figure 4 is an interpolation by a spline in piecewise constant tension. Higher tensions are imposed on the polygonal part to suppress the vibration. The interpolation is kept smooth elsewhere. The locally supported splines used to construct this curve are plotted in Fig. 5 where the plots are vertically scaled to have a common peak value.

Conclusions

Locally supported splines in tension were constructed where the tension is constant within each sampling interval and variable at the sampling points. They will hopefully contribute to the variety of curve drawing modules in the graphical design tools. Another application may be image enlargement tools which allow users to put higher tension manually at the portions where they want to suppress ringing effects.

  t

Figure 1 :

 1 Figure 1: Interpolation by a cubic spline (p(t) ≡ 0).

  t

Figure 2 :

 2 Figure 2: Interpolation by a linear spline (p(t) → ∞).

  t

Figure 3 :

 3 Figure 3: Interpolation by a spline in constant tension (p(t) ≡ 10).

  t

Figure 5 :

 5 Figure 5: Locally supported splines used to construct the curve in Fig. 4.

  Figure 4: Interpolation by a spline in piecewise constant tension (p(t) = 0 for the cursive part (t < t 4 ), p(t) = 10for the straight parts (t 4 ≤ t < t 6 and t 7 ≤ t), and p(t) = 30 for the breaking part (t 6 ≤ t < t 7 ) ).

	f(t)
	t 0	t 1	t 2	t 3	t 4	t 5	t 6	t 7	t 8	t 9	t 10
	y (t) n
	t 0	t 1	t 2	t 3	t 4	t 5	t 6	t 7	t 8	t 9	t 10	t


Françoise Rose
email: francoise.rose@etu.univ-lyon2.fr

MY HAMMOCK = I HAVE A HAMMOCK Possessed nouns constituting possessive clauses in Emérillon (Tupi-Guarani)

This paper concerns Emérillon, a language spoken only in French Guyana by about 400 speakers who call it Teko. It belongs to the 8

This paper deals with a particular construction of Emérillon: the predicative use of a possessed noun 2 (person prefix plus a noun stem) to constitute a possessive clause. The fact is that, in Emérillon, there is no morphological distinction between possessed nouns in argument function in "ordinary" sentences and possessed nouns that constitute by themselves possessive clauses.

(1) e-kija (Couchili et al.) 1sg/II 3 -hammock "my hammock" or "I have a hammock" This topic is linked to the new analysis of so-called "descriptive verbs" as a subcategory of nouns (called nominoids, Cf. Couchili, Maurel & Queixalós), which implies analyzing the person marker as a possessive prefix. The structure in (2) is therefore exactly parallel to the one in (1).

(2) e-kaneo (nominoid) (Couchili et al.) 1sg/II-fatigue "my fatigue" or "I am tired" (i.e. I have fatigue).

Possessive sentences in general linguistics and in Emérillon:

Payne 1997 draws a quick typology of possessive clauses in the languages of the world: "Languages usually employ existential and/or locational structures to express the notion of possession. Occasionally possessive clauses use a special verb like "have". " The following examples show that the same copula in Estonian is used for existence (3), location (4) and possession (5).

(3) laua-l on klaas piima (Estonian, Payne 1997) (5) lapsel on piima (Estonian, Payne 1997) child:LOC be:3sg milk The child has milk. (lit: Milk is at the child) (In this last sentence, the possessor is expressed as a location, but the word order differentiates it from (4).) [START_REF] Heine | Possession. Cognitive sources, forces and grammaticalization[END_REF] gives 8 different Event Schemas as sources for predicative possession. Three of them are exemplified in Emérillon constructions.

• The first construction contains a verbal predicate, and would fit under the Companion Schema, whose Formula is "X is with Y", with the meaning of "X has, owns Y". (6) a-leko kasulu 1sg/I-have (?) necklace I have some necklaces.

Though in synchrony -leko can be translated with "have", [START_REF] Cabral | Observações sobre a história do morfema -a da família Tupí-Guaraní[END_REF] gives a nice analysis of the cognates of this form in Tenetehára-Tembé and in Jo'é. She analyses it as the causative-comitative form of the verb "to be in movement". (7) a-r-eká e r-ú-Ø [START_REF] Cabral | Observações sobre a história do morfema -a da família Tupí-Guaraní[END_REF], Jo'é) 1-C.COM-be.in.movement 1 CONT-father-ARG I have my father. So the -leko in Emérillon could be analysed the same way (eko being a stem), with the meaning "to be with something", except that in a synchronic analysis, the causative-comitative morpheme seems to be -elo-.

• We also found one sentence that embodies Heine's Goal Schema "Y exists for/to X", a sub-type of the Existence Schema. This sentence with the existential kob conveys a possessive meaning, the possessor being expressed by the object of a postposition. (8) kob-a-zepe idu-pe kalakuli... EXIST-a-but 3sg-POST money despite the money he has… (Litt: despite that there is money to him…)

• The third kind of Emérillon predicative possessive constructions consists of a possessed noun (person marker + noun) by itself, as in (1) and (2). Since this is the most frequent possessive construction in Emérillon and typologically the most interesting, we will now focus on it.

The most obvious hypothesis on the semantic type of predication in these possessive clauses is to consider it as an existential predication. This analysis was proposed by Rodrigues for Tupinamba (2001) and Dietrich for Tupi-Guarani languages in general (2001). A strong argument in favour of this existential interpretation is an interesting fact about Jo'é, another Tupi-Guarani language. In Jo'é, a possessive sentence consists most of the time of a possessed noun followed by an existential copula [START_REF] Cabral | Observações sobre a história do morfema -a da família Tupí-Guaraní[END_REF]. ( 9 The difference between the Jo'é construction and the Emérillon one is that the existential meaning that we presume in these sentences is expressed overtly by a copula in Jo'é, which is not the case in Emérillon (although we will actually see a case where it appears).

In line with Heine's typology, my hypothesis would be that it is either the Genitive Schema "X's Y exists" or the Topic Schema "As for X, Y exists.", both being sub-types of the Existence Schema.

The important point is that, as far as I know, it is typologically really uncommon to have an existential predication without any existential verb or copula (that is to say to have just "N" as a sentence for "there is N"), especially without a locative constituent. Tupi-Guarani languages display this rarity. Before dealing with the absence of a copula in this structure, let us look at this construction in more detail.

Predicate nominals:

An article by Couchili, Maurel and Queixalós on the lexical categories in Emérillon has established that there is a clear distinction between nouns and verbs. The main difference is that nouns have the vocation to be used as arguments (i.e. they can be used as such without any modification), whereas verbs have the vocation to be used as predicates. In the following example, -kûlûg and -iñuÑ are verbs, zetûg and kuku are nouns.

(11) zetûg o-kûlûg o-iñuÑ kuku-pope sweet.potato 3/I-grate 3/I-put manioc.beer-POST She grates the sweet potatoes and puts them in the beer.

For Tupi-Guarani specialists: note that nouns in Emérillon do not take the -a suffix when used as core arguments. The use of this -a varies among Tupi-Guarani languages, and in some, it would make a difference between a possessed noun used as an argument (marked with -a) and a possessive predicate (unmarked), see for example Rodrigues 96.

And yet verbs can be used as arguments once they have been nominalized through relativization: (12) o-kuwa-pa o-manõ ma¿Ã. 3/I-know-TAM 3/I-die REL He knows the dead. (i.e. those who have died) and nouns may be used as predicates when possessed:

(13) i-•alû•-a-nam, i-•alû•-ate o-mã¿Ã Ø-ehe.
3/II-grandmother-a-SUB 3/II-grandmother-FOC 3/I-watch 3-POST If she has a grandmother, her grandmother watches her. (Here, the -a is made necessary by the subordination: i-•alû• by itself means "she has a grandmother".)

These nominal predicates share the same TAM (Tense Aspect and Mood) (14&15) and negation (16&17) as the verbs:

(14) wane ma¿Ã za-ûkû•-tal apam-a-wi. good REL indet/I-take-FUT foreigner-a-POST We are going to take the good things from the foreigners. [START_REF] Vieira | A natureza transitiva das sentenças possessivas em Mbyá-Guarani[END_REF] indicates that the predicate nominal in Mbya Guarani keeps some nominal syntactic properties: this means that the noun has not been verbalized. Here is an example of a nominal predicate modified by a numeral in Emérillon: (18) ede moko de-l-apd 2sg/PRO two 2sg/II-LK-house You have two houses. I will assume for the time being that predicate nominals have both nominal and verbal properties because their lexical category (noun) allows them to be modified, whereas their function (predicate) makes them have the same properties as verbs in a predicative function.

We must specify here that only possessed nouns consisting of a person marker plus a noun can make a possessive clause, and that genitival constructions (a noun modified by another noun) do not share this property (since the possessed noun and the genitival construction do not have the same structure). This description raises two questions: the first one is the analysis of the possessor NP's function (linked to the question of the predicate type). Various analysis have been made in Tupi-Guarani linguistics: subject of an intransitive predicate, subject of a transitive predicate, Head of a nominal determination, adposition of a pronominal argument…) Given lack of time and data, I will not develop this question here.

The second question is the question of an existential predication without copula. We can now return to it.

3.

Existential predications: In order to focus on the absence/presence of an existential copula, let us compare Emérillon with Turkish (as already done in Couchili, Maurel & Queixalós). In both languages, the distinction between verbs and nouns is blurred by the fact that both classes use the same person markers and that possessed nouns as arguments ( 21) or in a possessive predication ( 22) share the same inflectional affixes. Var is an existential copula, as shown in ( 23). In Turkish, a possessed noun needs this existential copula (var) to make a possessive clause, whereas in Emérillon, the surface forms of possessed nouns and possessive clauses look exactly the same. Within our existential hypothesis, this would result from the fact that no copula is needed to express existence with possessed nouns, a fact that is typologically rare. In Payne 1997, there is no mention about any existential clauses without a verb or a copula. (Even though uncommon, the absence of existential copula has been attested for Australian languages.)

It is true that a zero copula is nothing exceptional, but in most cases, this zero copula will occur in predications expressing the identity between two arguments (equation, attribution or inclusion), rather than in existential predications. The following examples show that in Russian the identity copula is zero with proper inclusion (24) and attribution (25): (24) Ivan professor.

(Russian) I.

teacher. I. is a teacher (25) Ona krasiva.

(Russian) 3sg/FEM beautiful She is beautiful.

We must insist than in Emérillon possessive clauses (and probably in the other Tupi-Guarani languages), the predication is not attributive: in (26), the relation between "me" and "fatigue" is not a relation of identity "be" (even though it is between "me" and "tired" in English, Portuguese or French). Semantically, the relation is one of possession "have", which is more obvious in (27) where there is no possible attributive interpretation even in European languages. (27) e-kija (Couchili et al.) 1sg/II-hammock "I have a hammock" Our hypothesis is that there is a covert existential meaning in possessive clauses in Emérillon, but is there any overt existential verb or copula in non-possessive clauses? 4. Existential predications in non-possessive clauses. In our corpus, existence is expressed by the use of kob (28), the basic meaning of which is a distant location like the English there (29). (28) kob petum.

EXIST cigarette

There are cigarettes. (The location is backgrounded in this text: the speaker describes the influence of "foreigners" on the community life. If a location were expressed, it would be "here" or "in our village").

(29) kob amonam olo-wûg-tal-e¿e.

there maybe 1excl/I-arrive-FUT-REP We will maybe go back there.

Up to this point, we have seen possessive clauses consisting of a simple possessed noun with what we assume to be an existential meaning. However, the Emérillon existential copula was not used in these sentences.

A possessive clause with the existential morpheme?

In fact, the corpus shows some examples of the existential kob plus a possessed noun, with a possessive meaning. This is another strong argument for the hypothesis that there is a covert existential copula in possessive clauses consisting simply of a person marker plus a noun. This copula may reappear under certain circumstances.

(30) κοβ-α-ιτε ε-βοτε-ναµ, wil-a-kuwa e-al o-ho.

there-a-IRR 1sg/II-motor-if quick-a-IRR 1sg/II-canoe 3/I-go If I had a motor, my canoe would go fast.

This reminds us of the fact that in some languages copulas may be zero or optional in present or incompletive tense and then become obligatory in past tense. In fact, when sentences 24 (proper inclusion) and 25 (attribution) are put in the past or the future tense, they indeed display then a copula (31-32). (31) Ivan budet professor. I.

be:FUT professor I. will be a teacher.

(32) Ona byla krasiva. She be:PAST:FEM beautiful She was beautiful.

In (30), kob could be sensitive to the irrealis TAM and/or the subordination. Further data should be collected to confirm this hypothesis and specify the contexts in which the copula can occur or must occur.

Summary:

Only possessed nouns (person marker plus noun) can function as predicate with a possessive meaning.

We made the hypothesis that these nominal predicates are in fact existential constructions.

With unpossessed nouns, the existential meaning is expressed by the copula κοβ .

The existential copula kob may be overt also in possessive clauses. What is still to be investigated is if the possessed noun keeps some verbal properties when kob is present, or if negation and TAM are taken over by the copula. Similarly, the question is raised of whether we should posit a zero copula in sentences like (1) and (2), or still think of them in terms of "nominal predicate"? Further remark: Queixalós (2001) notes that in Tupi-Guarani languages nouns have a general propensity to function as predicate in semantically possessive predications, a fact we have illustrated here with Emérillon examples.

On the other hand, we said earlier that "descriptive" words (words with adjectival meaning) were analyzed as nouns (nominoids) in Emérillon. They share most of the properties of nouns, and precisely can easily constitute a possessive clause when possessed (2). These last two remarks make understandable how some propertyconcept words (adjectival meaning words) can be expressed by nouns in Emérillon (we refer here to nominoids): they can easily constitute a possessive clause, that is to say be used in a predication, one frequent use of property-concept words.

ABBREVIATIONS:

  father. (lit. My father exists.)

(

  15) e-l-apû•-tal 1sg/I-LK 4 -house-FUT I will have a house. (16) d-o-¿u-•i sautu NEG-3/I-eat-NEG salt (S)he does not eat any salt. (17) d-i-kiya-•i (Couchili et al.) NEG-3/II-hammock-NEG He does not have any hammock.

  (19) tiiwan-a-kija(Couchili et al.) T.-a-hammock T's hammock / * T has a hammock. If one wants to introduce a full NP for the possessor, the possessive clause will look like (20): (20) i-kija tiiwan (Couchili et al.) 3/II-hammock T. T. has a hammock.

  tired" (i.e. I have fatigue).

  table:LOC be glass milk There is a glass of milk on the table.

	(4) raamat	on	laua-l	(Estonian, Payne 1997)
	book	be:3sg table:LOC
	The book is on the table.

This linking morpheme is used in front of some postpositions and nouns when they are preceded by another noun or a prefix of set II (1st or 2 nd person) in the same constituent.


Muhammad Usman
email: muhammad.3.usman@kcl.ac.uk

Philip G Batchelor
email: philip.batchelor@kcl.ac.uk

Optimized Sampling Patterns for Practical Compressed MRI

The performance of compressed sensing (CS) algorithms is dependent on the sparsity level of the underlying signal, the type of sampling pattern used and the reconstruction method applied. The higher the incoherence of the sampling pattern used for undersampling, less aliasing will be noticeable in the aliased signal space, resulting in better CS reconstruction. In this work, based on point spread function (PSF) properties, we compare random, Poisson disc and constrained random sampling patterns and show their usefulness in practical compressed sensing applied to dynamic cardiac magnetic resonance imaging (MRI).

Introduction

One of the main questions that arise in compressed sensing magnetic resonance imaging (CS-MRI) is: which type of sampling is optimal? The basic theory of compressed sensing as proposed by Donoho [START_REF] Donoho | Compressed Sensing[END_REF] and Candes [START_REF] Candes | Compressive sampling[END_REF] requires acquisition of randomized set of measurements. For MRI, this corresponds to the random sampling in Fourier domain (k-space) which results in incoherent aliasing artefacts in image space. However, random sampling requires bigger changes in amplitudes and polarity of MR system gradients, making it infeasible practically in an MR system. Figure 1 shows one dimensional gradient variations for 2D random and uniform lattice sampling patterns. From the figure, it is evident that we have bigger changes in amplitude and polarity of gradients in case of random sampling pattern than uniform lattice. The solution to this problem is to use deterministic sampling patterns. The uniform lattice pattern is a deterministic pattern but yields coherent artefacts in its PSF and hence, it does not satisfy the basic requirements of compressed sensing theory. Our goal is to find deterministic sampling patterns that have incoherent artefacts in the PSF and can yield better CS reconstruction.

Candidate Sampling Patterns in CS

To have minimum aliasing due to sampling below the Nyquist rate, Nayak [START_REF] Ks Nayak | Randomized trajectories for reduced aliasing artifact[END_REF] defined the following properties of PSF of the ideal sampling pattern: The near zero region around the main lobe of the PSF should be as large as possible and outside that region, PSF should resemble white noise. The samples should be placed randomly but with a restricted maximum distance between samples. These two conditions are met by Poisson disc sampling [START_REF] Yellot | Spectral consequences of photoreceptor sampling in the rhesus retina[END_REF]. Recently, Poisson disc sampling has been shown to give good results in parallel MRI due to better reconstruction conditioning [START_REF] Lustig | Autocalibrating Parallel Imaging Compressed Sensing using L1 SPIR-iT with Poisson-Disc Sampling and Joint Sparsity Constraints ISMRM Workshop on Data Sampling and Image Reconstruction[END_REF]. However, it also has impractical gradient requirements. Gamper [START_REF] Gamper | Compressed sensing in dynamic MRI[END_REF] defined constrained random pattern with incoherent artefacts in its PSF. Constrained random pattern is a normal lattice pattern with samples shifted along one dimension randomly by -1, 0 and +1. Hence, it is a normal lattice with constrained randomization added along one direction and has moderate gradient requirements. Figure 2 shows the three candidate sampling patterns (random, Poisson disc and constrained random) with the corresponding PSFs. Like Poisson disc sampling, the constrained random sampling has a nearzero region around the main lobe in its PSF and it also possesses the uniform density of sampling both locally and globally. Additionally, due to added constrained randomization, the amplitudes of coherent side lobes in the PSF of constrained random pattern are also suppressed. In CS recovery algorithms like OMP [START_REF] Gamper | Compressed sensing in dynamic MRI[END_REF] which are based on picking the most significant component from the aliased space iteratively, the suppression of coherent artefacts ensures that only the right candidates are picked up in successive iterations.

Experimental Setup

To test the performance of three sampling patterns in dynamic cardiac MRI, two sets of dynamic cardiac data of size (n f x n p x n t , n f: number of frequency encoding indices, n p: number of phase encoding indices, n t : number of time frames) (224x155x50) and (336x178x48) were acquired with a Philips MRI scanner 1.5 T, SSFP sequence, FOV 350x350 mm 2 . We used the jittered grid approximation of the Poisson disc sampling as proposed by Cook [START_REF] Cook | Stochastic sampling in computer graphics[END_REF]. For CS based reconstruction, the x-f space (x: spatial location, f: temporal frequency) is chosen to be the sparse representation [START_REF] Malik | x-f Choice: reconstruction of undersampled dynamic MRI by data-driven alias rejection applied to contrast-enhanced angiography. Stochastic sampling in computer graphics[END_REF]. The x-f space representation of the dynamic cardiac data is obtained by taking the Fourier transform of dynamic MR data along the temporal dimension. Figure 3 shows the dynamic cardiac MR data and its sparse representation. For each frequency encoding index, the under-sampled data was simulated by applying the three sampling patterns to the fully sampled dynamic cardiac data in k x -t space (k x : phase encoding index, t: time) with varying acceleration factors/sampling factors (SF) from 3 to 7. The x-f space corresponding to each frequency encoding index was independently reconstructed by our modified OMP method with adaptive thresholding scheme [START_REF] Usman | Adaptive thresholding scheme for OMP method applied to dynamic MRI[END_REF]. The OMP algorithm stops when maximum residual aliasing intensity in x-f space reaches the intensity level of noise.

Performance Results

The CS reconstruction results for candidate sampling patterns are shown in Figure 4 to Figure 9 with different acceleration factors. For the original cardiac frame shown in Figure 4 (a), the CS reconstruction results by OMP method with under-sampling factor (SF) of 3 are shown in Figure 4 (b),(c) and (d) for random, Poisson disc and constrained random sampling patterns. The corresponding temporal profiles are shown in Figure 5. The CS reconstruction results for acceleration factors of 5 and 7 are shown in Figure 6 to Figure 9. Up to the acceleration factor of 5, the CS reconstructed data has same spatial and temporal resolution for all three sampling patterns with nearly exact signal reconstruction achieved up to SF=3 (Figure 4 and Figure 5). Below SF=5, the temporal resolution of CS reconstructed data with constrained random sampling gets worse than that for the other sampling patterns (Figure 9 d). This is due to the fact that with very high acceleration factors, many locations within the constrained random pattern will have zero probability of being picked up, as the sampling locations are constrained to only one sample shift from the uniform lattice grid.

Conclusion

We showed that the PSF properties of constrained random sampling are similar to the optimal sampling pattern (Poisson disc sampling). Up to the acceleration factor of 5, the quality of the reconstructed images and the temporal resolution of the CS reconstructed data are nearly the same for random, Poisson and constrained random sampling patterns. Since the constrained random sampling has moderate gradient requirements when compared with other optimal sampling schemes, it is an excellent choice to be used as an optimal sampling pattern in practical compressed MRI.

Figure 1 :

 1 Figure 1: Gradient variation along one dimension in MR system for (a) random sampling (top) (b) uniform lattice sampling (bottom)

Figure 2 :

 2 Figure 2: Three candidate sampling patterns and their corresponding PSFs: top to bottom: random, Poisson disc and constrained random

Figure 3 :

 3 Figure 3: Dynamic cardiac MR data (a) and its x-f space representation (b), the frequency axis 'f' is centered around dc frequency (f=0)

Figure 4 :

 4 Figure 4: CS reconstruction results with SF=3: (a) original cardiac frame, CS reconstructed data with (b) random sampling (c) Poisson disc sampling (d) constrained random sampling

Figure 5 Figure 6 :

 56 Figure 5: CS reconstruction results with SF=3: (a)original temporal profile, CS Reconstructed temporal profile with (b) random sampling (c) Poisson disc sampling (d) constrained random sampling

Figure 8 :

 8 Figure 8: CS reconstruction results with SF=7: (a) original cardiac frame, CS reconstructed data with (b) random sampling (c) Poisson disc sampling (d) constrained random sampling

Figure 7

 7 Figure 7: CS reconstruction results with SF=5: (a)original temporal profile, CS Reconstructed temporal profile with (b) random sampling (c) Poisson disc sampling (d) constrained random sampling


Akira Hirabayashi
email: hira@yamaguchi-u.ac.jp

A Study on Sparse Signal Reconstruction from Interlaced Samples by l1-Norm Minimization

We propose a sparse signal reconstruction algorithm from interlaced samples with unknown offset parameters based on the l 1 -norm minimization principle. A typical application of the problem is superresolution from multiple lowresolution images. The algorithm first minimizes the l 1norm of a vector that satisfies data constraint with the offset parameters fixed. Second, the minimum value is further minimized with respect to the parameters. Even though this is a heuristic approach, the computer simulations show that the proposed algorithm perfectly reconstructs sparse signals without failure when the reconstruction functions are polynomials and with more than 99% probability for large dimensional signals when the reconstruction functions are Fourier cosine basis functions.

Introduction

Sampling theory is at the interface of analog/digital conversion, and sampling theorems provide bridges between the continuous and the discrete-time worlds. A fundamental framework of the sampling theorems consists of data acquisition (sampling) process of a target signal and reconstruction process from the data. Classical studies assumed that both processes are fixed and known. Then, sampling theorems yield in linear formulations [START_REF] Unser | Sampling-50 Years after Shannon[END_REF]. On the other hand, recent studies assume that sampling or reconstruction processes contain unknown factors. Then, sampling theorems become nonlinear. For example, Vetterli et al. discussed problems in which locations of reconstruction functions are unknown [START_REF] Vetterli | Sampling signals with finite rate of innovation[END_REF], [START_REF] Dragotti | Sampling moments and reconstructing signals of finite rate of innovation: Shannon meets Strang-Fix[END_REF]. They introduced the notion of rate of innovation, and provided perfect reconstruction procedures for signals with finite rate of innovation. The recent hot topic, compressive sampling, assumes that signals are sparse in the sense that signals are expressed by a small subset of reconstruction functions, but the subset is unknown [START_REF] Candes | Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information[END_REF], [START_REF] Baraniuk | Compressive sensing [lecture notes[END_REF], [START_REF] Candes | An introduction to compressive sampling [a sensing/sampling paradigm that goes against the common knowledge in data acquisition[END_REF]. It is interesting that the solution is obtained by the l 1 -norm minimization. In contrast to the above studies, problems with unknown factors in the sampling process have also been discussed. For example, sampling locations are assumed to be unknown and completely arbitrary in [START_REF] Marziliano | Reconstruction of irregularly sampled discrete-time bandlimited signals with unknown sampling locations[END_REF] and [START_REF] Browning | Approximating signals from nonuniform continuous time samples at unknown locations[END_REF]. A more restricted sampling process is interlaced sampling [START_REF] Marks | Introduction to Shannon Sampling and Interpolation Theory[END_REF], in which a signal is sampled by a sampling device several times with slightly shifted locations. If the offset parame-ters are unknown, the sampling theorem becomes nonlinear. A typical application is superresolution from a set of multiple low-resolution images. A replacement of a single high-rate A/D converter by multiple lower rate converters also yields within this formulation. To this problem, Vandewalle et al. proposed perfect reconstruction algorithms under a condition that the total number of unknown parameters is less than or equal to the number of samples [START_REF] Vandewalle | Super-resolution from unregistered and totally aliased signals using subspace methods[END_REF]. We can find, however, practical situations in which the condition is not true. The method proposed in [START_REF] Browning | Approximating signals from nonuniform continuous time samples at unknown locations[END_REF] can be applied to such situations. However, it hardly provides a high quality stable result. In order to solve these difficulties, the present author proposed an algorithm that reconstructs the closest function to a mean signal under data constraint assuming that signals are generated from a probability distribution [START_REF] Hirabayashi | A study on interlaced sampling with unknown offsets[END_REF]. The mean signal is, however, not always available. Hence, in this paper we propose a signal reconstruction algorithm from interlaced samples with unknown offsets using a relatively weak a priori knowledge, sparsity. The algorithm first minimizes the l 1 -norm of a vector that satisfies data constraint with the offset parameters fixed. Then, the minimum value is further minimized with respect to the parameters. Even though this is a heuristic approach, the computer simulations show that the proposed algorithm perfectly reconstructs sparse signals without failure when the reconstruction functions are polynomials and with more than 99% probability for large dimensional signals when the reconstruction functions are Fourier cosine basis functions. This paper is organized as follows. Section 2 formulates the fundamental framework and defines the notion of sparsity. Section 3 introduces interlaced sampling and summarizes the conventional studies. In Section 4, we propose the l 1 -norm minimization algorithm. Section 5 evaluates the algorithm through simulations, and shows that the algorithm perfectly reconstruct sparse signals with high probability. Section 6 concludes the paper.

Sparse Signals

A signal f to be reconstructed is defined on a continuous domain D. We assume that f belongs to a Hilbert space H = H(D) of a finite dimension K. The inner product for f and g in H is denoted by f, g , and the norm is induced as f = √ f, f . By using an arbitrarily fixed basis {ϕ k } K-1 k=0 , any f in H is expressed as

f = K-1 ∑ k=0 a k ϕ k . ( 1
)
A K-dimensional vector with k-th element a k is denoted by a. 1) are non-zero and the rest are zero.

Definition 1 A signal f is J-sparse if at most J coeffi- cients of {a k } K-1 k=0 in Eq. (
It should be noted that unknown factors in J-sparse signals are not only values of non-zero coefficients but also their locations. Hence, there are 2J unknown factors in a Jsparse signal. If 2J ≥ K, then the number of unknown factors is more than K, which is the number of the original unknown coefficients {a k } K-1 k=0 without sparsity. Hence, in order for sparsity to be meaningful, we assume that

J < K/2.
In real applications, J is supposed to be much smaller than K/2.

Interlaced Sampling

Interlaced sampling means that a signal f is sampled M times by an identical observation device with offsets {δ (m) } M -1 m=0 , where δ (0) = 0. An M -dimensional vector with m-th element δ (m) is denoted by δ. The observation device is characterized by sampling functions {ψ n } N -1 n=0 , which are given a priori. Then, the sampling function for the n-th sample in the m-th sequence is given by

ψ (m) n (x) = ψ n (x -δ (m) ),
and the sample is expressed as

d (m) n = f, ψ (m) n . ( 2
)
Let d be an M N -dimensional vector in which d

(m) n is the n+mN -th element. An M N ×K matrix with the n+mN , k-th element ϕ k , ψ (m) n is denoted by B δ . Substituting Eq. (1) into Eq. (2) yields B δ a = d. ( 3
)
For simplicity, we assume that the column vectors of B δ are linearly independent. Figure 1 illustrates the formulation of interlaced sampling.

In order to reconstruct the signal f from interlaced samples with unknown offsets, we have to determine both {a k } K-1 k=0 and {δ (m) } M -1 m=1 . To this problem, Vandewalle et al. proposed perfect reconstruction algorithms under a condition that the number of unknown parameters is less than or equal to the number of samples {{d

(m) n } N -1 n=0 } M -1 m=0 , or K + M -1 ≤ M N. ( 4
)
We can find, however, practical situations in which the condition is not true. The method in [START_REF] Browning | Approximating signals from nonuniform continuous time samples at unknown locations[END_REF] can be applied to the situation without Eq. ( 4). However, the results obtained by the method tend to be unstable. The present author proposed an algorithm which uses a mean signal as a prior [START_REF] Hirabayashi | A study on interlaced sampling with unknown offsets[END_REF]. However, the mean signal is not always available. Hence, in this paper, we propose perfect reconstruction algorithms using a relatively weak prior, sparsity.

H f = K-1 ∑ k=0 a k ϕ k Reconstruction Sampling C K a =    a 0 . . . a K-1    C M N d =    d 0 . . . d (M -1) N -1    B δ

l 1 -Norm Minimization Algorithm

The problem which we are going to solve in this paper is stated as follows.

Problem 1 Determine J-sparse vector a and δ which satisfy Eq. ( 3) under the condition that the column vectors of B δ are linearly independent.

Because of the linear independentness, a vector a that satisfies B δ a = d is uniquely determined as

a = B † δ d,
where B † δ is the Moore-Penrose generalized inverse of B δ . Let us define a matrix B ε by setting an arbitrarily fixed parameter ε instead of δ. By using this matrix, a vector c ε is defined as

c ε = B † ε d. ( 5
)
Then, our problem becomes a problem of finding a parameter ε such that the vector c ε is J-sparse.

It is well-known that l 1 -norm minimization is effective to promote sparsity as is used in the compressed sensing [START_REF] Candes | Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information[END_REF], [START_REF] Baraniuk | Compressive sensing [lecture notes[END_REF], [START_REF] Candes | An introduction to compressive sampling [a sensing/sampling paradigm that goes against the common knowledge in data acquisition[END_REF]. Hence, we also employ this principle to find Jsparse vector c ε . Now, our problem becomes the following problem.

Problem 2 Determine ε that makes column vectors of the matrix B ε linearly independent, and minimizes l 1 -norm of c ε in Eq. ( 5):

ε = argmin ε c ε l1 = argmin ε B † ε d l1 . ( 6
)
Table 1: Parameters K, J, N and M used in simulations.

K 4 6 8 10 12 J 1 2 3 4 5 N 2 3 4 5 6 M 2 2 2 2 2
The solution to Problem 2 is different from that to Problem 1 in general. Similar to the compressed sensing, the former agrees with the latter in some cases. Theoretical analyses for the agreement are still under consideration. Instead, we show simulation results in this paper.

Simulations

We show computer simulations which demonstrate that the proposed algorithm perfectly reconstructs sparse signals under certain conditions. We consider two reconstruction functions, polynomial and Fourier cosine basis.

Polynomial reconstruction

Let H be a space spanned by functions

ϕ k (x) = x k (0 ≤ k < K) for [0, l]
where l is a positive real number. The inner product is defined by

f, g = 1 l ∫ l 0 f (x)g(x)dx.
Sampling is assumed to be ideal, i.e., d

(m) n = f (x n + δ (m)
). The sample point x n is given by

x n = (2n + 1)l 2N (n = 0, 1, . . . , N -1),
which we call the base sequence. Let l = N so that the sampling interval becomes one. Figure 2 (a) shows a simulation result, in which the dimension of H is K = 8, sparsity parameter is J = 3, the number of samples in each sequence is N = 4, and the sequence was used M = 2 times. The offset parameter is δ (1) = -0.4. The black line shows the target signal f , and 'o' and 'x' respectively show the base and the first sequences. The red line shows the reconstructed signal, from which we can see the target signal is perfectly recovered. Figure 2 (b) shows that the l 1 -norm of c ε is indeed minimized at ε = -0.4. We repeated the simulation for one thousand target signals with the values shown in Table 1. Then, all of the signals are perfectly recovered as well as the offset parameters.

Fourier cosine basis reconstruction

We used the same setup except that the reconstruction functions are

ϕ k (x) = { 1 (k = 0), √ 2 cos kπx l (0 < k < K).
Under the above defined inner product, {ϕ k } K-1 k=0 is an orthonormal basis. Unfortunately, perfect reconstruction is not always achieved. Figure 4 shows failure rates [%] of perfect reconstruction with respect to K. The dotted red and the solid blue lines show the rates when J = K/4 and J = K/6, respectively. The failure rate for J = K/4 arrives at less than or equal to 1% when K > 32, while that for J = K/6 does so when K > 30.

¡ ¢ £ £ ¡ ¢ ¤ ¤ ¡ ¢ ¥ ¥ ¡ ¢ ¦ § ¡ ¢ § ¡ ¦ § ¡ ¥ § ¡ ¤ § ¡ £ ¡ £ ¡ ¤ ¡ ¥ (a) Reconstruction result ¡ ¢ £ ¡ ¢ ¤ ¡ ¢ ¥ ¡ ¢ ¦ ¡ ¡ ¢ ¦ ¡ ¢ ¥ ¡ ¢ ¤ ¡ ¢ £ ¡ § ¡ ¦ ¡ ¡ ¦ § ¡ ¥ ¡ ¡ ¥ § ¡ ¤ ¡ ¡ ¤ § ¡ £ ¡ ¡ £ § ¡ § ¡ ¡ (b) l 1 -norm of c ε
Even though these results are only verified through simu-

Conclusion

We proposed a sparse signal reconstruction algorithm from interlaced samples with unknown offset parameters. The algorithm is based on the l 1 -norm minimization principle: First, it minimizes the l 1 -norm with the offset parameters fixed. Second, the minimum value is further minimized with respect to the parameters. Even though this is a heuristic approach, the computer simulations showed that the proposed algorithm perfectly reconstructs sparse signals without failure when the reconstruction functions are polynomials and with more than 99% probability for large dimensional signals when the reconstruction func-tions are Fourier cosine basis functions. Because of the computational efficiency, the proposed algorithm is very attractive. Theoretical analyses of these results are our most important future task.

Figure 1 :

 1 Figure 1: Formulation of sampling and reconstruction. The vector a is to be estimated from the vector d. Note that there are unknown offset parameters δ in B δ .

Figure 2 :

 2 Figure 2: Simulation result. The black line shows the target signal f , and 'o', 'x', and '+' respectively show the base, the first, and the second sequences. The red line shows the reconstructed signal which perfectly matches to the target signal.

Figure 3 (

 3 Figure3(a) shows a simulation result, in which the dimension of H is K = 60, sparsity parameter is J = 15, the number of samples in each sequence is N = 20, and the sequence was used M = 3 times. The offset parameters are δ(1) = -0.2 and δ(2) = 0.3. The black line shows the target signal f , and 'o', 'x', and '+' respectively show the base, the first, and the second sequences. The red line shows the reconstructed signal, from which we can see the target signal is perfectly recovered. Unfortunately, perfect reconstruction is not always achieved. Figure4shows failure rates [%] of perfect reconstruction with respect to K. The dotted red and the solid blue lines show the rates when J = K/4 and J = K/6, respectively. The failure rate for J = K/4 arrives at less than or equal to 1% when K > 32, while that for J = K/6 does so when K > 30.Even though these results are only verified through simu-

Figure 3 :J = K/ 4 J = K/ 6 Figure 4 :

 3464 Figure 3: Simulation result for Fourier cosine basis functions. The black line shows the target signal f , and 'o', 'x', and '+' respectively show the base, the first, and the second sequences. The red line shows the reconstructed signal which perfectly matches to the target signal.

Acknowledgment

This work was partially supported by the Ministry of Education, Science, Sports and Culture, Grant-in-Aid for Young Scientists (B), 20700164, 2008.