Agostino Martinelli

Extension of the Observability Rank Condition to Nonlinear systems driven by Unknown Inputs*

Keywords: Nonlinear Observability, Unknown Input, Nonlinear Systems

This paper investigates the unknown input observability problem in the nonlinear case under the assumption that the unknown inputs are differentiable functions of time (up to a given order). The goal is not to design new observers but to provide simple analytic conditions in order to check the weak local observability of the state. The analysis starts by providing a new definition of indistinguishable states in the case of unknown inputs. Then, in order to separate the effect of the known inputs from the effect of the unknown inputs on the system outputs, the state is augmented. This allows us to obtain the extension of basic properties, which hold in the case of known inputs. Starting from these properties, the paper provides a sufficient analytic condition for the state observability, which is called the extended observability rank condition. The proposed approach is used to derive the observability properties of two systems. The former is very simple while the latter is very complex and describes the fusion of visual and inertial measurements.

I. INTRODUCTION

The problem of state observability for systems driven by unknown inputs (UI) is a fundamental problem in control theory. This problem was introduced and firstly investigated in the seventies [START_REF] Basile | On the observability of linear, time invariant systems with unknown inputs[END_REF], [START_REF] Bhattacharyya | Observer design for linear systems with unknown inputs[END_REF], [START_REF] Guidorzi | On Wonham stabilizability condition in the synthesis of observers for unknown-input systems[END_REF], [START_REF] Wang | Observing the states of systems with unmeasurable disturbance[END_REF]. A huge effort has then been devoted to design observers for both linear and nonlinear systems in presence of UI, e.g., [START_REF] Barbot | An algebraic framework for the design of nonlinear observers with unknown inputs[END_REF], [START_REF] Barbot | An observation algorithm for nonlinear systems with unknown inputs[END_REF], [START_REF] Chen | Unknown input observer design for a class of nonlinear systems: an LMI approach[END_REF], [START_REF] Darouach | Full-order observers for linear systems with unknown inputs[END_REF], [START_REF] Floquet | A sliding mode approach of unknown input observers for linear systems[END_REF], [START_REF] Floquet | On sliding mode observers for systems with unknown inputs[END_REF], [START_REF] Guan | A novel approach to the design of unknown input observers[END_REF], [START_REF] Ha | Trinh State and input simultaneous estimation for a class of nonlinear systems[END_REF], [START_REF] Hammouri | Unknown input observer for state affine systems: A necessary and sufficient condition[END_REF], [START_REF] Hou | Design of observers for linear systems with unknown inputs[END_REF], [START_REF] Koenig | Design of a class of reduced order unknown inputs nonlinear observer for fault diagnosis[END_REF], [START_REF] Koening | Unknown input observers for switched nonlinear discrete time descriptor system[END_REF], [START_REF] Yang | Observer for linear systems with unknown inputs[END_REF].

The goal of this paper is not to design new observers for systems driven by UI but to provide simple analytic conditions in order to check the weak local observability of the state. The obtained results hold for systems whose dynamics are nonlinear in the state and affine in both the known and the unknown inputs. Additionally, the unknown inputs are supposed to be smooth functions of time (specifically, they are supposed to be C k , for a suitable integer k).

In [START_REF] Hermann | Nonlinear Controllability and Observability[END_REF] the observability properties of a nonlinear system are derived starting from the definition of indistinguishable states. According to this definition, the Lie derivatives of any output computed along any direction allowed by the system dynamics take the same values at the states which are indistinguishable. Hence, if a given state x belongs to the indistinguishable set of a state x 0 (i.e., to I x0 ) all the Lie derivatives computed at x and at x 0 take the same values. This is a fundamental property. In particular, based on this *This work was supported by the French National Research Agency ANR through the project VIMAD A. Martinelli is with INRIA Rhone Alpes, Montbonnot, France e-mail: agostino.martinelli@ieee.org property, the observability rank condition was introduced in [START_REF] Hermann | Nonlinear Controllability and Observability[END_REF].

Our objective is to extend the observability rank condition to systems characterized by dynamics that are also driven by UI. For, we introduce a new definition of indistinguishable states for the case UI (section II). Then, in section III we introduce a new system by a suitable state extension. For this extended system, we show that, the Lie derivatives of the outputs up to a given order, take the same values at the states which are indistinguishable. In other words, the new system satisfies the same property derived in [START_REF] Hermann | Nonlinear Controllability and Observability[END_REF] mentioned above and this allows us to extend the observability rank condition (section IV). We will refer to this extension as to the Extended Observability Rank Condition (EORC).

The new system is obtained by a state augmentation. In particular, the augmented state is obtained by including the unknown inputs together with their time-derivatives up to given order. This augmented state has already been considered in the past. Specifically, in [START_REF] Belo | 3 Known Landmarks are Enough for Solving Planar Bearing SLAM and Fully Reconstruct Unknown Inputs[END_REF] the authors adopted this augmented state to investigate the observability properties of a fundamental problem in the framework of mobile robotics (the bearing SLAM). In particular, starting from the idea of including the time-derivatives of the unknown input in the state, in [START_REF] Belo | 3 Known Landmarks are Enough for Solving Planar Bearing SLAM and Fully Reconstruct Unknown Inputs[END_REF] a sufficient condition for the state observability has been provided.

All the theoretical results are illustrated in section V by deriving the observability properties of two nonlinear systems driven by unknown inputs. Finally, in section VI we provide conclusion together with some discussion with special emphasis on future research outlooks.

II. BASIC DEFINITIONS

In the sequel we will refer to a nonlinear control system with m u known inputs (u

≡ [u 1 , • • • , u mu ] T ) and m w unknown inputs or disturbances (w ≡ [w 1 , • • • , w mw ] T
). The state is the vector x ∈ M , with M an open set of R n . We assume that the dynamics are nonlinear with respect to the state and affine with respect to the inputs (both known and unknown). Finally, for the sake of simplicity, we will refer to the case of a single output y (the extension to multiple outputs is straightforward). Our system is characterized by the following equations:

     ẋ = f 0 (x) + mu i=1 f i (x)u i + mw j=1 g j (x)w j y = h(x) (1)
where f i (x), i = 0, 1, • • • , m u , and g j (x), j = 1, • • • , m w , are vector fields in M and the function h(x) is a scalar function defined on the open set M . For the sake of simplicity, we will assume that all these functions are analytic functions in M .

Let us consider the time interval I ≡ [0, T ]. Note that, since the equations in (1) do not depend explicitly on time, this can be considered as a general time interval of length T . In the sequel, we will assume that the solution of (1) exists in I and we will denote by x(t; x 0 ; u; w) the state at a given time t ∈ I, when x(0) = x 0 and the known input and the disturbance are u(t) and w(t), respectively, ∀t ∈ I.

We introduce the following definition:

Definition 1 (Indistinguishable states in presence of UI) Two states x a and x b are indistinguishable if, for any u(t) (the known input vector function), there exist w a (t) and w b (t) (i.e., two unknown input vector functions in general, but not necessarily, different from each other) such that h(x(t; x a ; u; w a )) = h(x(t; x b ; u; w b )) ∀t ∈ I.

This definition states that, if x a and x b are indistinguishable, then, for any known input, by looking at the output during the time interval I, we cannot conclude if the initial state was x a and the disturbance w a or if the initial state was x b and the disturbance w b . We remark that, contrary to the definition of indistinguishable states in the case without disturbances, the new definition does not establish an equivalence relation. Indeed, we can have x a and x b indistinguishable, x b and x c indistinguishable but x a and x c are not indistinguishable. As in the case of known inputs, given x 0 , the indistinguishable set I x0 is the set of all the states x such that x and x 0 are indistinguishable. Starting from this definition, we can use exactly the same definitions of observability and weak local observability adopted in the case without disturbances.

III. EXTENDED SYSTEM AND BASIC PROPERTIES

In order to extend the observability rank condition to the case of unknown inputs we introduce a new system (the extended system) such that its Lie derivatives are constant on the indistinguishable sets. The new system will be denoted by Σ (k) . It is simply obtained by extending the original state by including the unknown inputs together with their time derivatives. Specifically, we denote by k x the extended state that includes the time derivatives up to the (k -1)-order:

k x ≡ [x T , w T , w (1) T , • • • , w (k-1) T ] T (2)
where

w (k) ≡ d k w dt k and k x ∈ M (k) , with M (k)
an open set of R n+kmw . From (1) it is immediate to obtain the dynamics for the extended state:

k ẋ = f (k) 0 ( k x) + mu i=1 f (k) i (x)u i + mw j=1 1 n+(k-1)mw+j n+kmw w (k) j
(3) where:

f (k) 0 ( k x) ≡         f 0 (x) + mw i=1 g i (x)w i w (1) w (2) • • • w (k-1) 0 mw         (4) f (k) i (x) ≡ f i (x) 0 kmw (5)
and we denoted by 0 m the m-dimensional zero column vector and by 1 l m the m-dimensional unit column vector, with 1 in the l th position and 0 elsewhere. We remark that the resulting system has still m u known inputs and m w disturbances. However, while the m u known inputs coincide with the original ones, the m w unknown inputs are now the k-order time derivatives of the original disturbances. The state evolution depends on the known inputs via the vector fields f

(k) i , (i = 1, • • • , m u )
and it depends on the disturbances via the unit vectors 1 n+(k-1)mw+j n+kmw , (j = 1, • • • , m w ). Finally, we remark that only the vector field f (k) 0 depends on the new state elements. In the rest of this section we derive several properties satisfied by Σ (k) .

Lemma 1 Let us consider the system Σ (k) . The Lie derivatives of the output up to the m th order (m ≤ k) are independent of w

(f ) j , j = 1, • • • , m w , ∀f ≥ m.
Proof: We proceed by induction on m for any k. When m = 0 we only have one zero-order Lie derivative (i.e., h(x)), which only depends on x, namely it is independent of w (f ) , ∀f ≥ 0. Let us assume that the previous assert is true for m and let us prove that it holds for m+1. If it is true for m, any Lie derivative up to the m th order is independent of w (f ) , for any f ≥ m. In other words, the analytical expression of any Lie derivative up to the m-order is represented by a function g(x, w, w (1)

, • • • , w (m-1) ). Hence, ∇g = [ ∂g ∂x , ∂g ∂w , ∂g ∂w (1) , • • • , ∂g ∂w (m-1) , 0 (k-m)mw ].
It is immediate to realize that the product of this gradient by any vector filed in (3) depends at most on w (m) , i.e., it is independent of w (f ) , ∀f ≥ m + 1

A simple consequence of this lemma are the following two properties:

Proposition 1 Let us consider the system Σ (k) . The Lie derivatives of the output up to the k th order along at least one vector among 1

n+(k-1)mw+j n+kmw (j = 1, • • • , m w ) are identically zero.
Proof: From the previous lemma it follows that all the Lie derivatives, up to the (k -1)-order are independent of w (k-1) , which are the last m w components of the extended state in [START_REF] Barbot | An observation algorithm for nonlinear systems with unknown inputs[END_REF]. Then, the proof follows from the fact that any vector among 1

n+(k-1)mw+j n+kmw (j = 1, • • • , m w ) has the first n + (k -1)m w components equal to zero Proposition 2
The Lie derivatives of the output up to the k th order along any vector field f

(k) 0 , f (k) 1 , • • • , f (k)
mu for the system Σ (k) coincide with the same Lie derivatives for the system Σ (k+1) Proof: We proceed by induction on m for any k. When m = 0 we only have one zero-order Lie derivative (i.e., h(x)), which is obviously the same for the two systems, Σ (k) and Σ (k+1) . Let us assume that the previous assert is true for m and let us prove that it holds for m + 1 ≤ k. If it is true for m, any Lie derivative up to the m th order is the same for the two systems. Additionally, from lemma 1, we know that these Lie derivatives are independent of w (f ) , ∀f ≥ m. The proof follows from the fact that the first n + mm w components of f

(k) 0 , f (k) 1 , • • • , f (k) mu coincide with the first n+mm w components of f (k+1) 0 , f (k+1) 1 , • • • , f (k+1) mu when m < k
In the sequel we will use the notation: ξ ≡ [w T , w (1) T , • • • , w (k-1) T ] T . In this notation we have k x = [x T , ξ T ] T . We also denote by Σ (0) the original system, i.e., the one characterized by the state x and the equations in [START_REF] Barbot | An algebraic framework for the design of nonlinear observers with unknown inputs[END_REF]. The definition 1, given for Σ (0) , can be applied to Σ (k) . Specifically, in Σ (k) , two states [x a , ξ a ] and [x b , ξ b ] are indistinguishable if, for any u(t) (the known inputs), there exist two vector functions w

k) b (t) (the k th time derivative of two disturbance vectors) such that, h(x(t; [x a , ξ a ]; u; w (k) a )) = h(x(t; [x b , ξ b ]; u; w (k) b )) ∀t ∈ I.
It holds the following fundamental result:

Proposition 3 If [x a , ξ a ] and [x b , ξ b ] are indistinguishable in Σ (k)
then the Lie derivatives of the output up to the k thorder computed on these points take the same values.

Proof: We consider a piecewise-constant input ũ as follows

(i = 1, • • • , m u ): ũi (t) = (6)          u 1 i t ∈ [0, t 1 )
u 2 i t ∈ [t 1 , t 1 + t 2 ) • • • u g i t ∈ [t 1 + t 2 + • • • + t g-1 , t 1 + t 2 + • • • + t g-1 + t g ) Since [x a , ξ a ] and [x b , ξ b ] are indistinguishable in Σ (k) , there exist two disturbance functions w (k) a (t) and w (k) b (t) such that: h(x(t; [x a , ξ a ]; ũ; w (k) a )) = h(x(t; [x b , ξ b ]; ũ; w (k) b )) (7) ∀t ∈ [0, t 1 +t 2 +• • •+t g-1 +t g ) ⊂ I.
On the other hand, by taking the two quantities in [START_REF] Bryson | Observability Analysis and Active Control for Airbone SLAM[END_REF]

at t = t 1 + t 2 + • • • + t g-1 +
t g , we can consider them as functions of the g arguments t 1 , t 2 , • • • , t g . Hence, by differentiating with respect to all these variables, we also have:

∂ g h(x(t 1 + • • • + t g ; [x a , ξ a ]; ũ; w (k) a )) ∂t 1 ∂t 2 • • • ∂t g = (8) = ∂ g h(x(t 1 + • • • + t g ; [x b , ξ b ]; ũ; w (k) b )) ∂t 1 ∂t 2 • • • ∂t g
By computing the previous derivatives at t 1 = t 2 = • • • = t g = 0 and by using proposition 1 we obtain, if g ≤ k:

L g θ1θ2•••θg h x = x a ξ = ξ a = L g θ1θ2•••θg h x = x b ξ = ξ b (9)
where

θ h = f (k) 0 + mu i=1 f (k) i u h i , h = 1, • • • , g. The equality in (9) must hold for all possible choices of u h 1 , • • • , u h mu . By appropriately selecting these u h 1 , • • • , u h mu ,
we finally obtain:

L g v1v2•••vg h x = x a ξ = ξ a = L g v1v2•••vg h x = x b ξ = ξ b (10)
where

v 1 v 2 • • • v g are vector fields belonging to the set {f (k) 0 , f (k) 1 , • • • , f (k)
mu } In [START_REF] Hermann | Nonlinear Controllability and Observability[END_REF] it was also defined the concept of V -indistinguishable states, with V a subset of the definition set (in the specific case V ⊆ M (k) ) that includes the two considered states. From this definition and the previous proof we can alleviate the assumptions in the previous proposition. Specifically, we have the following:

Remark 1 The statement of proposition 3 also holds if [x a , ξ a ] and [x b , ξ b ] are V -indistinguishable, being V any open subset of M (k) and [x a , ξ a ], [x b , ξ b ] ∈ V .
Thanks to the results stated by propositions 2 and 3 we will introduce the extension of the observability rank condition in the next section.

IV. EXTENSION OF THE OBSERVABILITY RANK

CONDITION

According to the observability rank condition, the weak local observability of the system in (1) with m w = 0 at a given point x 0 can be investigated by analyzing the codistribution generated by the gradients of the Lie derivatives of its output. Specifically, if the dimension of this codistribution is equal to the dimension of the state on a given neighbourhood of x 0 , we conclude that the state is weakly locally observable at x 0 (theorem 3.1 in [START_REF] Hermann | Nonlinear Controllability and Observability[END_REF]). We can also check the weak local observability of a subset of the state components. Specifically, a given component of the state is weakly locally observable at x 0 , if its gradient belongs to the aforementioned codistribution 1 . The proof of theorem 3.1 in [START_REF] Hermann | Nonlinear Controllability and Observability[END_REF] is based on the fact that all the Lie derivatives (up to any order) of the output computed along any direction allowed by the system dynamics take the same values at the states which are indistinguishable.

Let us consider now the general case, i.e., when m w = 0. In the extended system (Σ (k) ) we know that the Lie derivatives up to the k-order satisfy the same property (see proposition 3). Therefore, we can extend the validity of theorem 3.1 in [START_REF] Hermann | Nonlinear Controllability and Observability[END_REF] to our case, provided that we suitably augment the state and that we only include the Lie derivatives up to the k-order to build the observable codistribution.

In the sequel, we will introduce the following notation:

• Ωm will denote the observable codistribution for Σ (k) that includes all the Lie derivatives of the output along f

(k) 0 , f (k) 1 , • • • , f (k)
mu up to the order m ≤ k; • The symbol d will denote the gradient with respect to the extended state in (2); • For a given codistribution Λ and a given vector field η, we will denote by L η Λ the codistribution whose covectors are the Lie derivatives along η of the covectors in Λ (we are obviously assuming that the dimension of these covectors coincides with the dimension of η). • Given two vector spaces V 1 and V 2 , we will denote with V 1 + V 2 their sum, i.e., the span of all the generators of both V 1 and V 2 . • For a given V ⊆ M (k) and a given [x 0 , ξ 0 ] ∈ V , we will denote with

I V [x0,ξ0] the set of all the states V -indistinguishable from [x 0 , ξ 0 ].
The codistribution Ωm can be computed recursively by the following algorithm:

Algorithm 1 (Computation of Ωm , m ≤ k) Set Ω0 = span{dh}; Set i = 0 while i < m do Set i = i + 1 Set Ωi = Ωi-1 + mu i =0 L f (k) i Ωi-1 end while
Let us denote by x j the j th component of the state (j = 1, • • • , n). We introduce the following definition:

Definition 2 (EORC) For the system Σ (k) , the j th component of the state (i.e.,

x j , j = 1, • • • , n) satisfies the extended observability rank condition at [x 0 , ξ 0 ] if dx j ∈ Ωk at [x 0 , ξ 0 ]. If this holds ∀j = 1, • • • , n,
we say that the state x satisfies the extended observability rank condition at [x 0 , ξ 0 ] in Σ (k) .

We have the following result, which is the extension of the result stated by theorem 3.1 in [START_REF] Hermann | Nonlinear Controllability and Observability[END_REF]:

Proposition 4 For Σ (k) , if x j (j = 1, • • • n)
satisfies the extended observability rank condition at [x 0 , ξ 0 ], then x j is weakly locally observable at [x 0 , ξ 0 ]. Additionally, x j remains weakly locally observable by further extending the state (i.e., in every system Σ (f ) (f > k)).

Proof: We prove that it exists an open neighbourhood U of [x 0 , ξ 0 ] such that, for every open neighbourhood V ⊆ U of [x 0 , ξ 0 ], x j is constant on the set I V [x0,ξ0] . Since dx j ∈ Ωk at [x 0 , ξ 0 ], it exists some open neighborhood U of [x 0 , ξ 0 ], such that x j can be expressed in terms of the Lie derivatives of h along the directions f

(k) i (i = 0, 1, • • • , m u ) up to the k order. If V ⊆ U is an open neighborhood of [x 0 , ξ 0 ],
then proposition 3 and remark 1 imply that all the Lie derivatives up to the k order are constant on the set

I V [x0,ξ0]
and, consequently, also x j is constant on this set. Finally, the fact that x j is weakly locally observable in every system Σ (f ) (f > k) directly follows from proposition 2

In accordance with the previous result, the EORC is a tool to analyze the observability properties of a nonlinear system driven by known and unknown inputs. However, we remark two important limitations of the EORC. The former consists in the fact that the state augmentation can be continued indefinitely. As a result, the EORC only provides sufficient conditions for the weak local observability of the state components. The latter regards the computational cost demanded to check if it is satisfied. Specifically, the computation demanded to check if dx j belongs to Ωk can be very complex because by increasing k we also increase the dimension of the extended state.

V. APPLICATIONS

We apply the EORC described in section IV in order to investigate the observability properties of two nonlinear systems driven by unknown inputs. We also consider the case of multiple outputs. The first system characterizes a localization problem in two dimensions in the framework of mobile robotics. For this simple example, the use of the EORC is not required to derive the observability properties, which can be obtained by using intuitive reasoning.

The second system is much more complex and describes one of the most important sensor fusion problem, which is the problem of fusing visual and inertial measurements. We will refer to this problem as to the visual-inertial structure from motion problem (the Vi-SfM problem). This problem has been investigated by many disciplines, both in the framework of computer science [START_REF] Bryson | Observability Analysis and Active Control for Airbone SLAM[END_REF], [START_REF] Jones | Visual-inertial navigation, mapping and localization: A scalable real-time causal approach[END_REF], [START_REF] Kelly | Visual-inertial simultaneous localization, mapping and sensor-to-sensor self-calibration[END_REF], [START_REF] Martinelli | Vision and IMU data fusion: closed-form solutions for attitude, speed, absolute scale and bias determination[END_REF], [START_REF] Strelow | Motion estimation from image and inertial measurements[END_REF] and in the framework of neuroscience (e.g., [START_REF] Berthoz | Perception of Linear Horizontal Self-Motion Induced by Peripheral Vision Basic Characteristics and Visual-Vestibular Interactions[END_REF], [START_REF] Dokka | Estimating distance during self-motion: a role for visual-vestibular interactions[END_REF], [START_REF] Fetsch | Visual-vestibular cue integration for heading perception: Applications of optimal cue integration theory[END_REF]). Inertial sensors usually consist of three orthogonal accelerometers and three orthogonal gyroscopes. All together, they constitute the Inertial Measurement Unit (IMU). We will refer to the fusion of monocular vision with the measurements from an IMU as to the standard Vi-SfM problem. In [START_REF] Hesch | Towards consistent vision-aided inertial navigation[END_REF], [START_REF] Jones | Visual-inertial navigation, mapping and localization: A scalable real-time causal approach[END_REF], [START_REF] Kelly | Visual-inertial simultaneous localization, mapping and sensor-to-sensor self-calibration[END_REF], [START_REF] Kottas | On the consistency of vision-aided inertial navigation[END_REF], [START_REF] Li | Improving the accuracy of EKF-based visualinertial odometry[END_REF], [START_REF] Martinelli | Vision and IMU data fusion: closed-form solutions for attitude, speed, absolute scale and bias determination[END_REF], [START_REF] Mirzaei | A Kalman filter-based algorithm for IMU-camera calibration: Observability analysis and performance evaluation[END_REF] and [START_REF] Weiss | Vision Based Navigation for Micro Helicopters[END_REF] the observability properties of the standard Vi-SfM have been investigated in several different scenarios. Very recently, following two independent procedures, the most general result for the standard Vi-SfM problem has been provided in [START_REF] Chao | IMU-RGBD Camera 3D Pose Estimation and Extrinsic Calibration: Observability Analysis and Consistency Improvement[END_REF] and [START_REF] Martinelli | Observability Properties and Deterministic Algorithms in Visual-Inertial Structure from Motion[END_REF]. This result can be summarized as follows. In the standard Vi-SfM problem all the independent observable states are: the positions in the local frame of all the observed features, the three components of the speed in the local frame, the biases affecting the inertial measurements, the roll and the pitch angles, the magnitude of the gravity and the transformation between the camera and IMU frames. The fact that the yaw angle is not observable is an obvious consequence of the system invariance under rotation about the gravity vector. We want to use here the theory developed in the previous sections in order to investigate the observability properties of the Vi-SfM problem when the number of inertial sensors is reduced, i.e., when the system is driven by unknown inputs.

A. Simple 2D localization problem

We consider a vehicle that moves on a 2D-environment. The configuration of the vehicle in a global reference frame, can be characterized through the vector [x v , y v , θ v ] T where x v and y v are the cartesian vehicle coordinates, and θ v is the vehicle orientation. We assume that the dynamics of this vector satisfy the unicycle differential equations:

   ẋv = v cos θ v ẏv = v sin θ v θv = ω (11)
where v and ω are the linear and the rotational vehicle speed, respectively, and they are the system inputs. Additionally, we assume that the vehicle is equipped with a GPS able to provide its position. Hence, the system output is the following two-components vector:

y = [x v , y v ] T (12)
Let us start by considering the case when both the system inputs, i.e., the two functions v(t) and ω(t), are available. By comparing [START_REF] Barbot | An algebraic framework for the design of nonlinear observers with unknown inputs[END_REF] with [START_REF] Fetsch | Visual-vestibular cue integration for heading perception: Applications of optimal cue integration theory[END_REF] we obtain

x = [x v , y v , θ v ] T , m u = 2, m w = 0, u 1 = v, u 2 = ω, f 0 (x) = [0, 0, 0] T , f 1 (x) = [cos θ v , sin θ v , 0] T and f 2 (x) = [0, 0, 1] T .
In order to investigate the observability properties, we apply the observability rank crondition introduced in [START_REF] Hermann | Nonlinear Controllability and Observability[END_REF].

The system has two outputs: h x ≡ x v and h y ≡ y v . By definition, they coincide with their zero-order Lie derivatives. Their gradients with respect to the state are, respectively: [1, 0, 0] and [0, 1, 0]. Hence, the space spanned by the zero-order Lie derivatives has dimension two. Let us compute the first order Lie derivatives. We obtain:

L 1 1 h x = cos θ v , L 1 1 h y = sin θ v , L 1 2 h x = L 1 2 h y = 0.
Hence, the space spanned by the Lie derivatives up to the first order span the entire configuration space and we conclude that the state is weakly locally observable.

We now consider the case when both the system inputs are unknown. In this case, by comparing (1) with [START_REF] Fetsch | Visual-vestibular cue integration for heading perception: Applications of optimal cue integration theory[END_REF] we obtain

m u = 0, m w = 2, w 1 = v, w 2 = ω, f 0 (x) = [0, 0, 0] T , g 1 (x) = [cos θ v , sin θ v , 0] T and g 2 (x) = [0, 0, 1] T .
Intuitively, we know that the knowledge of both the inputs is unnecessary in order to have the full observability of the entire state. Indeed, the first two state components can be directly obtained from the GPS. By knowing these two components during a given time interval, we also know their time derivatives. In particular, we know ẋv (0) and ẏv (0).

From [START_REF] Fetsch | Visual-vestibular cue integration for heading perception: Applications of optimal cue integration theory[END_REF] we easily obtain: θ v (0) = atan ẏv(0) ẋv(0) . Hence, also the initial orientation is observable, by only using the GPS measurements.

Let us proceed by applying the EORC, discussed in section IV. We start by computing the codistribution Ω0 in Σ (0) . We easily obtain:

Ω0 = span{[1, 0, 0], [0, 1, 0]}
From this we know that x v and y v are weakly locally observable. We want to know if also θ v is weakly locally observable (in which case the entire state would be weakly locally observable). We have to compute Ω1 in Σ (1) . For, we build the system Σ (1) . We have:

1 x = [x v , y v , θ v , v
, ω] T . We can easily obtain the analytical expression for the quantities appearing in [START_REF] Basile | On the observability of linear, time invariant systems with unknown inputs[END_REF]. We have: f

(1) 0 (x) = [cos θ v v, sin θ v v, ω, 0, 0] T . We compute the analytical expression of the first-order Lie derivatives along this vector filed. We have:

L 1 0 h x = ∇h x • f (1) 0 (x) = [1, 0, 0, 0, 0] • [cos θ v v, sin θ v v, ω, 0, 0] = cos θ v v (similarly, we obtain L 1 0 h y = sin θ v v).
We obtain:

Ω1 = span{[1, 0, 0, 0, 0], [0, 1, 0, 0, 0], [0, 0, -sin θ v v, cos θ v , 0], [0, 0, cos θ v v, sin θ v , 0]}
from which we obtain that the gradient of θ v belongs to Ω1 . Therefore, also θ v is weakly locally observable and so the entire original state.

B. The Vi-SfM with partial input knowledge

For the brevity sake, we do not provide here the computation necessary to deal with this problem. All the details are available in [START_REF] Martinelli | Observability Properties and Deterministic Algorithms in Visual-Inertial Structure from Motion[END_REF] (see also the work in [START_REF] Martinelli | State Estimation Based on the Concept of Continuous Symmetry and Observability Analysis: the Case of Calibration[END_REF] for the definition of continuous symmetries). Here we provide a summary of these results. First of all, we remark that the Vi-SfM problem can be described by a nonlinear system with six inputs (3 are the accelerations along the three axes, provided by the accelerometers, and 3 are the angular speeds provided by the gyroscopes). The outputs are the ones provided by the vision. In the simplest case of a single point feature, they consist of the two bearing angles of this point feature in the camera frame.

We analyzed the following three cases: 1) camera extrinsically calibrated, only one input known (corresponding to the acceleration along a single axis); 2) camera extrinsically uncalibrated, only one input known (corresponding to the acceleration along a single axis); 3) camera extrinsically uncalibrated, two inputs known (corresponding to the acceleration along two orthogonal axes). The dimension of the original state is 12 in the first case and 23 in the other two cases. Additionally m u = 1 and m w = 5 in the first two cases while m u = 2 and m w = 4 in the last case.

In [START_REF] Martinelli | Observability Properties and Deterministic Algorithms in Visual-Inertial Structure from Motion[END_REF] we prove that the observability properties of Vi-SfM do not change by removing all the three gyroscopes and one of the accelerometers. In other words, exactly the same properties hold when the sensor system only consists of a monocular camera and two accelerometers. To achieve this result, we computed the Lie derivatives up to the second order for the third case mentioned above. By removing a further accelerometer (i.e., by considering the case of a monocular camera and a single accelerometer) the system loses part of its observability properties. In particular, the distribution ∆ k (≡ Ω⊥ k ), ∀k ≥ 2, contains a single vector. This vector describes a continuous symmetry that is the invariance under the rotation around the accelerometer axis. This means that some of the internal parameters that define the extrinsic camera calibration, are no longer identifiable. Although this symmetry does not affect the observability of the absolute scale and the magnitude of the velocity, it reflects in an indistinguishability of all the initial speeds that differ for a rotation around the accelerometer axis. On the other hand, if the camera is extrinsically calibrated (i.e., if the relative transformation between the camera frame and the accelerometer frame is known (first case mentioned above)) this invariance disappears and the system still maintains full observability, as in the case of three orthogonal accelerometers and gyroscopes. The analysis of this system (the first case mentioned above) has been done in the extreme case when only a single point feature is available. This required to significantly augment the original state. In particular, in [START_REF] Martinelli | Observability Properties and Deterministic Algorithms in Visual-Inertial Structure from Motion[END_REF] we compute all the Lie derivatives up to the 7 th order, i.e., we included in the original state the 5 unknown inputs together with their time-derivatives up to the six order. We prove that the gradient of any component of the original state, with the exception of the yaw angle, is orthogonal to the distribution ∆ k , ∀k ≥ 7 (see the computational details in [START_REF] Martinelli | Observability Properties and Deterministic Algorithms in Visual-Inertial Structure from Motion[END_REF]) 2 .

VI. CONCLUSION

In this paper we investigated the problem of nonlinear observability when part (or even all) of the system inputs is unknown. We made the assumption that the unknown inputs are differentiable functions of time (up to a given order). The goal was not to design new observers but to provide simple analytic conditions in order to check the weak local observability of the state. An unknown input was also called disturbance.

We started the analysis by providing a new definition of indistinguishable states. Then, in order to separate the effect of the known inputs from the effect of the unknown inputs on the system outputs, the original state was augmented by including the unknown inputs together with their time derivatives up to a given order. This allowed us to obtain the extension of basic properties, which hold in the standard case (i.e., when all the inputs are known). Starting from these properties, the paper provided an analytic condition which guarantees the weak observability of the state. This condition was called the extended observability rank condition.

The extended observability rank condition has been illustrated by deriving the observability properties of several nonlinear systems driven by unknown inputs.

We remark two important limitations of the EORC. The former consists in the fact that the state augmentation can be continued indefinitely. As a result, the EORC only provides sufficient conditions for the weak local observability of the state components. The latter regards the computational cost demanded to check if it is satisfied. Specifically, the computation demanded to check if dx j belongs to Ωk can be very complex because by increasing k we also increase the dimension of the extended state.

In [START_REF] Martinelli | Nonlinear Unknown Input Observability: Analytical expression of the observable codistribution in the case of a single unknown input[END_REF], [START_REF] Martinelli | Non linear Unknown Input Observability: Extension of the observability rank condition and the case of a single unknown input[END_REF], we focused our attention on these fundamental issues:

• understanding if there exists a given k such that, if dx j / ∈ Ωk , then dx j / ∈ Ωk ∀k > k.

• obtaining a new codistibution (Ω k ) that is the span of covectors whose dimension is n (i.e., independent of the state extension) such that d x x j ∈ Ω k if and only if dx j ∈ Ωk (where d x denotes the gradient with respect to the original state x); In [START_REF] Martinelli | Nonlinear Unknown Input Observability: Analytical expression of the observable codistribution in the case of a single unknown input[END_REF], [START_REF] Martinelli | Non linear Unknown Input Observability: Extension of the observability rank condition and the case of a single unknown input[END_REF] we fully addressed both these issues in the case m w = 1. Specifically, we proved that the observable codistribution can be splitted into two codistributions. The former is generated by the gradients of scalar functions that only depend on the original state. The latter is generated by the gradients of scalar functions that depend on the entire augmented state. However, this latter codistribution can be ignored when deriving the observability properties of the original state. The former codistribution, namely the one generated by the gradients of scalar functions that only depend on the original state, is defined by a simple recursive algorithm. In [START_REF] Martinelli | Nonlinear Unknown Input Observability: Analytical expression of the observable codistribution in the case of a single unknown input[END_REF], [START_REF] Martinelli | Non linear Unknown Input Observability: Extension of the observability rank condition and the case of a single unknown input[END_REF] we also provided a complete answer to the first issue by proving that this algorithm converges in a finite number of steps and by also providing the criterion to establish that the convergence of the algorithm has been reached (theorem 2 in [START_REF] Martinelli | Non linear Unknown Input Observability: Extension of the observability rank condition and the case of a single unknown input[END_REF]). Also this proof is based on several tricky analytic steps. Our current investigation is focused on extending the results in [START_REF] Martinelli | Nonlinear Unknown Input Observability: Analytical expression of the observable codistribution in the case of a single unknown input[END_REF], [START_REF] Martinelli | Non linear Unknown Input Observability: Extension of the observability rank condition and the case of a single unknown input[END_REF] to the case of multiple unknown inputs (m w > 1).

  (k) a (t) and w

(

A component of the state is observable at x 0 if it is constant on the indistinguishable set of x 0 (Ix 0 ).

Note that, the yaw angle is not observable even in the case when all the 6 inputs are known. The fact that the yaw is unobservable is a consequence of a symmetry in the considered system, which is the system invariance under rotations about the gravity axis.


Agostino Martinelli
email: agostino.martinelli@ieee.org

Minimalistic sensor design in visual-inertial structure from motion*

.

The paper also provides a general discussion on UIO and in particular on the proposed solution.

I. INTRODUCTION

Visual and inertial sensing have received great attention by the mobile robotics community since they require no external infrastructure and this is a key advantage for robots operating in unknown environments where GPS signals are shadowed. Recent works have shown that through these sensors it is possible to perform metric structure from motion (e.g., [START_REF] Bryson | Observability Analysis and Active Control for Airbone SLAM[END_REF], [START_REF] Jones | Visual-inertial navigation, mapping and localization: A scalable real-time causal approach[END_REF], [START_REF] Kelly | Visual-inertial simultaneous localization, mapping and sensor-to-sensor self-calibration[END_REF], [START_REF] Martinelli | Vision and IMU data fusion: closed-form solutions for attitude, speed, absolute scale and bias determination[END_REF], [START_REF] Strelow | Motion estimation from image and inertial measurements[END_REF]). In the sequel we will refer to the problem of building the 3D-structure of the environment starting from visual and inertial measurements obtained during navigation as to the visual-inertial structure from motion problem (the Vi-SfM ). Inertial sensors usually consist of three orthogonal accelerometers and three orthogonal gyroscopes. All together, they constitute the Inertial Measurement Unit (IMU). We will refer to the fusion of monocular vision with the measurements from an IMU as to the standard Vi-SfM problem. In [START_REF] Hesch | Towards consistent vision-aided inertial navigation[END_REF], [START_REF] Jones | Visual-inertial navigation, mapping and localization: A scalable real-time causal approach[END_REF], [START_REF] Kelly | Visual-inertial simultaneous localization, mapping and sensor-to-sensor self-calibration[END_REF], [START_REF] Kottas | On the consistency of vision-aided inertial navigation[END_REF], [START_REF] Li | Improving the accuracy of EKF-based visualinertial odometry[END_REF], [START_REF] Martinelli | Vision and IMU data fusion: closed-form solutions for attitude, speed, absolute scale and bias determination[END_REF], [START_REF] Mirzaei | A Kalman filter-based algorithm for IMU-camera calibration: Observability analysis and performance evaluation[END_REF] and [START_REF] Weiss | Vision Based Navigation for Micro Helicopters[END_REF] the observability properties of the standard Vi-SfM have been investigated in several different scenarios. Recently, following two independent procedures, the most general result on the observability of the standard Vi-SfM problem has been provided in [START_REF] Chao | IMU-RGBD Camera 3D Pose Estimation and Extrinsic Calibration: Observability Analysis and Consistency Improvement[END_REF] and [START_REF] Martinelli | Observability Properties and Deterministic Algorithms in Visual-Inertial Structure from Motion[END_REF]. This result can be summarized as follows. In the standard Vi-SfM problem all the independent observable modes are: the positions in the local frame of all the observed features, the three components of the speed in the local frame, the biases affecting the inertial measurements, the roll and the pitch angle, the magnitude of the gravity and the transformation between the camera and IMU frames. The fact that the yaw angle is not observable is an obvious consequence of the system invariance under rotation about the gravity vector.

In [START_REF] Martinelli | Visual-inertial structure from motion: observability vs minimum number of sensors[END_REF], [START_REF] Martinelli | Observability Properties and Deterministic Algorithms in Visual-Inertial Structure from Motion[END_REF] we investigated the observability properties of the Vi-SfM when the number of inertial sensors is reduced. We considered separately the cases of camera extrinsically calibrated and not calibrated. In the second case, we assumed that at least five point features were available. This allowed us to consider the camera as a sensor able to provide the position and the speed up to a scale. Only in the first case we also considered the case of less than five point features (specifically, in that case we dealt with a single point feature). Under these premises, we proved that the observability properties of Vi-SfM do not change by removing all the three gyroscopes and one of the accelerometers. In other words, exactly the same properties hold when the sensor system only consists of a monocular camera and two accelerometers. By removing a further accelerometer (i.e., by considering the case of a monocular camera and a single accelerometer) the system loses part of its observability properties. In particular, a new symmetry arises. This symmetry corresponds to an internal rotation around the accelerometer axis. This means that some of the internal parameters that define the extrinsic camera calibration, are no longer observable. Although this symmetry does not affect the observability of the absolute scale and the magnitude of the velocity, it reflects in an indistinguishability of all the initial speeds that differ for a rotation around the accelerometer axis. On the other hand, if the camera is extrinsically calibrated (i.e., if the relative transformation between the camera frame and the accelerometer frame is known) this symmetry disappears and the system still maintains full observability.

The goal of this paper is to extend the analysis in [START_REF] Martinelli | Visual-inertial structure from motion: observability vs minimum number of sensors[END_REF], [START_REF] Martinelli | Observability Properties and Deterministic Algorithms in Visual-Inertial Structure from Motion[END_REF] by also including the extreme case of a single point feature when the camera is not extrinsically calibrated. The system is described in section II. Even if this extension seems to be simple, the analytic computation must be totally changed. Indeed, by including in the state the camera extrinsic parameters, the computation, as carried out in [START_REF] Martinelli | Visual-inertial structure from motion: observability vs minimum number of sensors[END_REF], [START_REF] Martinelli | Observability Properties and Deterministic Algorithms in Visual-Inertial Structure from Motion[END_REF] in the case when the camera is calibrated, becomes prohibitive.

The problem of deriving the observability properties of Vi-SfM when the number of inertial sensors is reduced corresponds to solve a problem that in control theory is known as Unknown Input Observability (UIO). This problem is still unsolved in the nonlinear case. In [START_REF] Martinelli | Visual-inertial structure from motion: observability vs minimum number of sensors[END_REF], [START_REF] Martinelli | Observability Properties and Deterministic Algorithms in Visual-Inertial Structure from Motion[END_REF] we introduced a new method able to provide sufficient conditions for the state observability. On the other hand, this method is based on a state augmentation. Specifically, the new extended state includes the original state together with the unknown inputs and their time-derivatives up to a given order. Then, the method introduced in [10], [START_REF] Martinelli | Observability Properties and Deterministic Algorithms in Visual-Inertial Structure from Motion[END_REF] (which is summarized in section IV-A and IV-B) is based on the computation of a codistribution defined in the augmented space. This makes the computation necessary to derive the observability properties dependent on the dimension of the augmented state and consequently prohibitive in our case. Our effort to deal with this fundamental issue, is devoted to separate the information on the original state from the information on its extension. We fully solve this problem only in the case of a single unknown input [START_REF] Martinelli | Nonlinear Unknown Input Observability: Extension of the Observability Rank Condition and the case of a single unknown input[END_REF]. For the general case, we partially solve this problem and we suggest a technique able to partially perform this separation (section IV-C). In section V we derive the observability properties for our systems. We obtain the extension of the results derived in [START_REF] Martinelli | Visual-inertial structure from motion: observability vs minimum number of sensors[END_REF], [START_REF] Martinelli | Observability Properties and Deterministic Algorithms in Visual-Inertial Structure from Motion[END_REF], i.e., in the case of a single point feature available and when the transformation between the camera frame and the frame attached to the inertial sensors is unknown. Finally, in section VI we provide a discussion of the results and our conclusion.

II. THE CONSIDERED SYSTEM

We consider a system which consists of a monocular camera and a single-axis accelerometer. All the results provided in this paper are obtained starting by the analysis of this system, even if they also regard the case of an additional inertial sensor, that can be both an accelerometer or a gyroscope. We assume that the local frame coincides with the frame attached to the single-axis accelerometer and, without loss of generality, we assume that this local frame has its z-axis coincident with the axis of the accelerometer. The position of the camera optical center in the local frame will be denoted by R c and the camera orientation will be characterized through the three Euler angles α, β, γ. Specifically, a vector with orientation τ in the local frame, will have the orientation Rτ in the camera frame, where R x η rotates the unit vector τ clockwise through the angle η about the z-axis and the x-axis, respectively. The vector R c and the three angles α, β, γ, characterize the extrinsic camera calibration and are assumed to be unknown. We consider the extreme case when a single point feature is available and we denote its position in the camera frame with c F ≡ [ c F x c F y c F z ] T . We also introduce a global frame whose z-axis is along the gravity vector but pointing upward. In other words, in this frame the gravity vector will be g = [0, 0, -g] T , where g is the magnitude of the gravity which is assumed to be unknown. We characterize our system through the following state:

R = R(α, β, γ) = R z α R x β R z γ and R z η and
S ≡ c F T , V T , q t , q x , q y , q z , A b z , g, R cT , α, β, γ T ( 1
)
where V is the speed in the local frame, q t , q x , q y , q z are the four components of the unit quaternion q ≡ q t + q x i + q y j + q z k, which characterizes the orientation of the local frame in the global frame and A b z is the accelerometer bias. This state is a vector with 18 components, which are not independent since the quaternion must be unit (qq * = 1). The dynamics of this state are the following:

    c Ḟ = -c Ω ∧ c F -R(V + Ω ∧ R c ) V = -Ω ∧ V + A + G q = 1 2 qΩ q ġ = Ȧb z = α = β = γ = 0 (2)
where

Ω ≡ [Ω x Ω y Ω z ]
T is the unknown angular speed in the local frame, c Ω = RΩ is the angular speed in the camera frame, Ω q is the imaginary quaternion associated with Ω, i.e., Ω q ≡ 0 + Ω x i + Ω y j + Ω z k, A is the acceleration that would be perceived by an ideal (i.e., noiseless and unbiased) three-axis accelerometer attached to the local frame and G ≡ [G x , G y , G z ] T is the gravity vector in the local frame, i.e., by denoting with G q the corresponding imaginary quaternion (G q = 0 + G x i + G y j + G z k), we have the following quaternion equality G q = -gq * kq. Note that the first two components of A are unknown while the third is available up to the bias A b z thanks to the single axis accelerometer. The monocular camera provides the position of the feature in the camera frame ( c F ) up to a scale. Hence, it provides the ratios of the components of c F :

h cam (S) ≡ [h u , h v ] T = c F x c F z , c F y c F z T (3)
We have also to consider the constraint q * q = 1. This provides the further observation:

h const (S) ≡ h q = q * q (4)
III. OBSERVABILITY ANALYSIS

The system described in the previous section is characterized by the state in (1), the dynamics in (2) and the observations in (3) and ( 4). This can be regarded as an input-output non linear system, where, part of the inputs is unknown. Specifically, the dynamics in (2) have the following structure:

ẋ = f 0 (x) + mu i=1 f i (x)u i + mw j=1 g j (x)w j (5)
where:

• m u = 1, m w = 5, u 1 = A z , w 1 = A x , w 2 = A y , w 3 = Ω x , w 4 = Ω y , w 5 = Ω z ; • f 0 is
obtained by setting to zero all the components of both A and Ω in (2), with the exception of the third component of A, which is set equal to -A b z ; • f 1 is obtained by removing f 0 from (2) and then by setting

A x = A y = Ω x = Ω y = Ω z = 0 and A z = 1; • g j (for j = 1, • • • , 5
) are obtained by removing f 0 from (2) and then by setting to zero all the components of both A and Ω with the exception of one of them depending on j (e.g., to obtain g 1 we set A y = A z = Ω x = Ω y = Ω z = 0 and A x = 1). The observability properties of systems with the dynamics given in ( 5) cannot be obtained by applying standard methods in control theory (e.g., the observability rank condition in [START_REF] Hermann | Nonlinear Controllability and Observability[END_REF]) because part of the inputs is unknown. We apply the same method introduced in [10], [START_REF] Martinelli | Observability Properties and Deterministic Algorithms in Visual-Inertial Structure from Motion[END_REF], which has been better formalized in [START_REF] Martinelli | Nonlinear Unknown Input Observability: Extension of the Observability Rank Condition and the case of a single unknown input[END_REF]. On the other hand, the system defined by the dynamics in ( 2) is more complex than the systems analyzed in [START_REF] Martinelli | Visual-inertial structure from motion: observability vs minimum number of sensors[END_REF], [START_REF] Martinelli | Observability Properties and Deterministic Algorithms in Visual-Inertial Structure from Motion[END_REF]. Note that in [START_REF] Martinelli | Visual-inertial structure from motion: observability vs minimum number of sensors[END_REF], [START_REF] Martinelli | Observability Properties and Deterministic Algorithms in Visual-Inertial Structure from Motion[END_REF] the case of a single feature was considered only when the camera was extrinsically calibrated, which means that the state had 12 entries instead of 18. It results that the analytical computation becomes prohibitive when we use the Lie derivatives whose order is equal or larger than 3. Note that to deal with the simpler case of camera calibrated, we had to use the Lie derivatives up to the 7 th order.

For these reasons, from one side we introduce some general properties, which allow us to reduce the analytic computation demanded to solve any UIO problem (section IV). From another side, we will proceed in three distinct phases, as illustrated in section V.

IV. COMPUTATION OF THE OBSERVABLE CODISTRIBUTION: KEY PROPERTIES

In this section we summarize the method introduced in [START_REF] Martinelli | Visual-inertial structure from motion: observability vs minimum number of sensors[END_REF], [START_REF] Martinelli | Observability Properties and Deterministic Algorithms in Visual-Inertial Structure from Motion[END_REF] to solve an UIO problem and we add new properties that allow us to significantly reduce the analytic computational burden.

A. Extended system

According to the observability rank condition [START_REF] Hermann | Nonlinear Controllability and Observability[END_REF], the observability properties of a nonlinear system with only known inputs, can be investigated by analyzing the codistribution generated by the gradients of its Lie derivatives. Specifically, if the dimension of this codistribution is equal to the dimension of the state, we conclude that the state is observable 1 . The observability rank condition has been introduced and proved that it is a sufficient condition for a system to be observable (theorem 3.1 in [START_REF] Hermann | Nonlinear Controllability and Observability[END_REF]). The proof of this theorem is based on the fact that the Lie derivatives of the outputs are constant on the indistinguishable sets.

In [START_REF] Martinelli | Visual-inertial structure from motion: observability vs minimum number of sensors[END_REF], [START_REF] Martinelli | Observability Properties and Deterministic Algorithms in Visual-Inertial Structure from Motion[END_REF] and [START_REF] Martinelli | Nonlinear Unknown Input Observability: Extension of the Observability Rank Condition and the case of a single unknown input[END_REF], we proposed an extension of this method in order to deal with systems driven by unknown inputs. Specifically, our approach can be used to investigate the observability properties of systems that satisfy the dynamics in [START_REF] Jones | Visual-inertial navigation, mapping and localization: A scalable real-time causal approach[END_REF], namely where part of the inputs is unknown. We defined a new system, denoted by Σ (k) . It is simply obtained by extending the original state by including the unknown inputs together with their time derivatives up to the (k -1)-order. The extended state is:

x (k) ≡ [x T , w T , w (1) T , • • • , w (k-1) T ] T (6)
1 Actually, it is weakly locally observable (see [START_REF] Hermann | Nonlinear Controllability and Observability[END_REF] for the definition of weak local observability).

where

w (i) ≡ d i w dt i t=0 , i = 0, 1, • • • , k -1.
The dimension of the extended state is n + km w . Its basic equations can be obtained starting from [START_REF] Jones | Visual-inertial navigation, mapping and localization: A scalable real-time causal approach[END_REF] and are available in [START_REF] Martinelli | Nonlinear Unknown Input Observability: Extension of the Observability Rank Condition and the case of a single unknown input[END_REF] together with the main properties satisfied by Σ (k) . One fundamental property is that the Lie derivatives up to the k-order are constant on the indistinguishable sets (see property 4 in [START_REF] Martinelli | Nonlinear Unknown Input Observability: Extension of the Observability Rank Condition and the case of a single unknown input[END_REF]). In other words, the Lie derivatives up to the k-order satisfy exactly the same property satisfied by all the Lie derivatives in the standard case of known inputs. As mentioned above, this property allows us to prove the theorem 3.1 in [START_REF] Hermann | Nonlinear Controllability and Observability[END_REF]. As a result, we can adopt the observability rank condition to investigate the observability properties of a system driven by also unknown inputs, provided that we suitably augment the state.

B. Extension of the Observability Rank Condition

On the basis of the previous discussion, the observability properties of a general nonlinear system, where part of the inputs is unknown, can be obtained by extending the state and by computing the codistribution that is the span of the gradients of all the Lie derivatives, up to the k-order, in the extended system Σ (k) . In the sequel we denote this codistribution by Ωk . Additionally, let us denote by f

(k) 0 , f (k) 1 , • • • , f (k)
mu the vector fields that characterize the dynamics of Σ (k) (their expression is provided in [START_REF] Martinelli | Nonlinear Unknown Input Observability: Extension of the Observability Rank Condition and the case of a single unknown input[END_REF] and it is easily obtained starting from ( 5)). The first step to do is to compute the codistribution Ωk . This is carried out recursively, by using the following algorithm:

(k) 0 , f (k) 1 , • • • , f (k) mu
Set Ωm the span of the gradients of the previous Lie derivatives and the generators of Ωm-1 end while

We are interested in deriving the observability properties of the original state x and not in the observability of the entire extended state. We can check the observability of the original state component by component, i.e., by proceeding as follows. Let us consider the i th component of the original state, i.e., x i (i = 1, • • • , n). We check if the gradient of x i with respect to the extended state belongs to Ωk . In other words, we check if the row vector of dimension n + km w , with all the entries equal to zero with the exception of the i th entry equal to 1, is in the span of the gradients of the Lie derivatives up to the k-order. If there exists a k such that this is true, we conclude that x i is observable. If this holds for i = 1, • • • , n, we conclude that the original state is observable.

C. Properties of Ωk

The method described in the previous subsection requires to compute the codistribution Ωk . Then, the computation demanded to check if a given covector belongs to Ωk can be very complex because by increasing k we also increase the dimension of the extended state. In the sequel, we will focus our attention on this fundamental issue. Specifically, we want to solve the following problem: separate the information on the original state from the information on its extension. We fully solve this problem only in the special case of a single unknown input and when the vector f 0 (x) in ( 5) vanishes. For this case we found the following fundamental result: Theorem 1 (Information Separation when m u = m w = 1) For every integer m, the codistribution Ωm is the span of two sets of covectors. The first set consists of gradients of scalar functions that only depend on the original state. The second set consists of gradients of scalar functions that depend on the entire augmented state but that do not contain additional information on the original state.

The proof of this theorem is complex and is based on several tricky steps (see theorem 1 in [START_REF] Martinelli | Nonlinear Unknown Input Observability: Extension of the Observability Rank Condition and the case of a single unknown input[END_REF] for a complete proof). On the basis of the previous theorem, we can investigate the observability properties of the original state by only considering the first set of functions. This makes the computation independent of the dimension of the extended state 2 .

Unfortunately, so far, we have not derived a similar result for the case of multiple inputs. On the other hand, we have proved the following weaker property, which still significantly simplifies the computation and which has been fundamental in deriving the observability properties of our system in (2).

Property 1 Let us suppose that, for a given integer m ≤ k, the gradient of a scalar function of the original state (i.e., m(x)) belongs to Ωm-1 . Then, the gradients of all the Lie derivatives of m(x) along the directions f

(k) 0 , f (k) 1 , • • • , f (k)
mu belong to Ωm .

Proof: Let us denote with ∇ the gradient with respect to the extended state and by L f

(k) i
the Lie derivative operator along the direction f

(k) i , i = 0, • • • , m u .
Additionally, we assume that the dimension of Ωm-1 is d and we denote with γ i (i = 1, • • • , d) d independent Lie derivatives (whose order is less or equal to m). In other words, we have:

Ωm-1 = span{∇γ 1 , • • • , ∇γ d }.
By assumption we have ∇m ∈ Ωm-1 , namely: ∇m = d j=1 c j ∇γ i , where the coefficients c j depend on the entire extended state. We have, for every i = 0, 1,

• • • , m u : ∇L f (k) i m = L f (k) i ∇m = d j=1 L f (k) i (c j ∇γ i ) = d j=1 (L f (k) i c j )∇γ i + d j=1 c j (L f (k) i ∇γ i
) and the statement follows by remarking that L f

(k) i ∇γ i ∈ Ωm
The advantage of this property is that, if we are able to detect such a scalar function m(x), we are allowed to use in the algorithm 1 ∇m as one of the generators of the codistribution Ωm-1 and its Lie derivatives along f

(k) 0 , f (k) 1 , • • • , f (k)
mu as a part of the generators of Ωm (provided that they are independent). This partially separates the information on the original state from its extension.

V. OBSERVABILITY PROPERTIES

We extend the results stated by theorems 2 and 3 in [START_REF] Martinelli | Visual-inertial structure from motion: observability vs minimum number of sensors[END_REF] to the case of a single feature. Because of the huge computational burden, we proceed into three separate steps. In V-A we prove that the parameters α and β are identifiable. We know, from the analysis carried out in [START_REF] Martinelli | Visual-inertial structure from motion: observability vs minimum number of sensors[END_REF], that the parameter γ is unobservable when 5 or more features are available. Therefore, also in the case of a single feature it remains unobservable. In section V-B we consider the case when γ is known (since α and β are identifiable, the entire rotation matrix R is known). For the resulting system we prove that all the remaining states are observable, with the exception of the absolute yaw (which is unobservable even in the standard case, i.e., when a complete IMU is available and for every number of features). Finally, in V-C we perform a system decomposition and we provide the final results.

A. Identifiability of the parameters α and β

We apply the algorithm 1 to compute the codistribution Ωm for m = 0, 1, 2, 3 for the system characterized by the state in (1), the dynamics in ( 2) and the observations in (3) and (4). At each step of the algorithm, we check the observability of α and β, respectively. By a direct computation, it is possible to verify that the gradients of both α and β belong to Ω3 . More precisely, we do not need to fully compute Ω3 since the gradients of both α and β belong to the span of all the Lie derivatives up to the third order with the exception of the ones along the direction f

(3) 0 all the three times (note that the expression of these Lie derivatives is the most complex). We proved the following property: Property 2 In the Vi-SfM problem with a single accelerometer, no gyroscope, unknown transformation between the camera and the accelerometer frames, the relative roll and pitch of the camera frame in the accelerometer frame are identifiable. This holds even in the case of one point feature.

B. Observability properties when the matrix R is known

We investigate the observability properties of the system characterized by the state in [START_REF] Bryson | Observability Analysis and Active Control for Airbone SLAM[END_REF] where we removed the last three entries, the dynamics given in [START_REF] Chao | IMU-RGBD Camera 3D Pose Estimation and Extrinsic Calibration: Observability Analysis and Consistency Improvement[END_REF] with R equal to the identity matrix and the observations in (3) and (4). We apply the algorithm 1 and, at each step, we check the observability of all the state entries. We obtain that the gradients of the three components of c F belong to Ω3 . Hence, we apply three times the property 1 with the scalar function equal to the these three components. This significantly reduce the computation and allows us to manage with higher order Lie derivatives (specifically, up to the six order). By a direct computation it is possible to verify that the gradients of six scalar functions belong to Ω6 . These functions are the three components of the angular speed Ω and the three components of the vector V + Ω ∧ R c . We apply again property 1. We compute the codistribution that is the span of the following scalar functions:

• the three components of c F ; • the constraint in (4);

• the three components of the angular speed Ω, together with their Lie derivatives up to the 7 th order; • the three components of the vector V +Ω∧R c , together with their Lie derivatives up to the 6 th order. We obtain that the gradients of the following scalar functions belong to the previous codistribution: the first six components and the last five components of the state; the three functions of the quaternion components that correspond to the roll and the pitch angles and its norm (i.e., Q r ≡ qtqx+qyqz 1-2(q 2

x +q 2 y ) , Q p ≡ q t q y -q z q x and qt 2 + q 2 x + q 2 y + q 2 z ; actually, the roll and pitch are arctan(2Q r )and arcsin(2Q p ), respectively). Hence, we proved the following property: Property 3 (Known camera-accelerometer rotation) In the Vi-SfM problem with a single accelerometer, no gyroscope, known rotation between the camera and the accelerometer frames and unknown shift between these frames, all the independent observable modes are the same as in the standard Vi-SfM problem. This holds even in the extreme case of a single point feature.

C. Results in the general case

We are now ready to investigate the observability properties of the system characterized by the state in (1), the dynamics given in (2) and the observations in (3) and (4). From the analysis described in section V-A we know that the two parameters α and β are observable. Hence, we are allowed to simplify the system by eliminating from the state these two parameters. Additionally, we rotate the camera frame, i.e., we rotate all the images provided by the camera by pre-multiplying c F by the rotation matrix (R z α R x β ) -1 . By introducing the vector n F ≡ (R z α R x β ) -1c F , we obtain the new state: S ≡ n F T , V T , q t , q x , q y , q z , A b z , g, R cT , γ T . From (2), we obtain its dynamics as follows:

    n Ḟ = -n Ω ∧ n F -R z γ (V + Ω ∧ R c ) V = -Ω ∧ V + A + G q = 1 2 qΩ q ġ = Ȧb z = γ = 0 (7)
where n Ω ≡ (R z α R x β ) -1c Ω is the angular speed in the new camera frame. Now, we perform the following coordinates change: S → S ≡ n F T , V T , q t , q x , q y , q z , A b z , g, R c T , γ

T , with V = R z γ V , R c = R z γ R c
, q ≡ q t + q x i + q y j + q z k = qp, and p is the unit quaternion associated to the rotation matrix R z γ (p = cos γ 2 + sin γ 2 k). Starting from [START_REF] Kottas | On the consistency of vision-aided inertial navigation[END_REF], we obtain the following dynamics in the new coordinates:

    n Ḟ = -n Ω ∧ n F -(V + n Ω ∧ R c ) V = -n Ω ∧ V + A + G q = 1 2 q n Ω q ġ = Ȧb z = γ = 0 (8)
where G is obtained from the quaternion product -gq * kq and A = R z γ A (note that the rotation implemented by the matrix R z γ leaves unvaried the acceleration along the z-axis. We remark the following two properties:

1) In the new coordinates the dynamics of the first 15 state entries are independent of γ and also the observations are independent of γ; 2) The system characterized by the first 15 entries of S is precisely the system analyzed in section V-B. The first remark allows us to decompose the state into two parts. Specifically, the state that defines the former consists of the first 15 state entries while the latter only consists of γ. The first consequence of this decomposition is that the parameter γ is unobservable. This is not a new result since we already know from theorem 3 in [START_REF] Martinelli | Visual-inertial structure from motion: observability vs minimum number of sensors[END_REF] that, in the case of at least 5 features, the system is characterized by a rotation symmetry that corresponds to a rotation around the accelerometer axis. The second remark allows us to conclude that the remaining states are observable up to the yaw (property 3). By adding to the system an additional inertial sensor along an axis that does not coincide with the axis of the accelerometer, the symmetry that corresponds to a rotation around the z-axis is broken and also the parameter γ becomes observable. On the other hand, if the new inertial sensor shares the same axis of the first one, the symmetry is not broken and the parameter γ remains unobservable. We summarize this new result with the following theorem:

Theorem 2 In the Vi-SfM problem with only two inertial sensors, the observability properties are the same as in the standard case provided that the two inertial sensors are along two distinct axes and with at least one of them that is an accelerometer. This holds even in the most challenging scenario, i.e., in the case of unknown camera-inertial sensor transformation, unknown magnitude of the gravity, unknown biases and single point feature available. In the case when the inertial sensors only consist of a single accelerometer, a new internal symmetry arises. As a consequence, the initial speed and orientation and the camera-inertial sensor transformation are not fully observable: all these quantities cannot be distinguished from the same quantities rotated around the accelerometer axis. All the remaining states are observable as in the standard Vi-SfM problem.

VI. DISCUSSION AND CONCLUSION

This paper provided new theoretical results on the Vi-SfM problem. Specifically, the investigation aimed to discover how the observability properties change when the number of inertial sensors is reduced and the new results here provided extended our previous results presented in [START_REF] Martinelli | Visual-inertial structure from motion: observability vs minimum number of sensors[END_REF], [START_REF] Martinelli | Observability Properties and Deterministic Algorithms in Visual-Inertial Structure from Motion[END_REF]. With respect to the contributions in [START_REF] Martinelli | Visual-inertial structure from motion: observability vs minimum number of sensors[END_REF], [START_REF] Martinelli | Observability Properties and Deterministic Algorithms in Visual-Inertial Structure from Motion[END_REF], here we considered simultaneously the case when the transformation between the camera frame and the frame attached to the inertial sensors is unknown and only a single point feature is available. To deal with this case we had to derive new general results on a theoretical problem that, in the framework of control theory, is known as Unknown Input Observability (UIO). Thanks to these results, we could derive the observability properties of the Vi-SfM in the case of a single feature available and unknown camera extrinsic calibration. Our results are summarized by theorem 2, which basically states that by using two inertial sensors along two independent axes and where at least one of them is an accelerometer, the observability properties do not change with respect to the standard Vi-SfM . In the case of a single accelerometer, exactly as in the case considered in [START_REF] Martinelli | Visual-inertial structure from motion: observability vs minimum number of sensors[END_REF], [START_REF] Martinelli | Observability Properties and Deterministic Algorithms in Visual-Inertial Structure from Motion[END_REF] (i.e., with at least 5 point features), it is not possible to distinguish all the physical quantities rotated around the accelerometer axis, independently of the accomplished trajectory. This means that, in this setting, it is not possible to fully perceive selfmotion. Note that the case of a single point features is much more complex than the case when the number of features is at least five. In this latter case, the monocular vision alone allows us to build the structure of the environment up to a scale. This means that the angular speed is provided by the visual measurements and consequently, the fact that the gyroscopes can be removed without altering the observability properties is an obvious result. In the case of a single point feature, the monocular vision does not allow us to observe the angular speed and the fact that the gyroscopes can be removed without altering the observability properties is not obvious. We remark that all the results obtained so far, clearly show that the observability properties are independent of the number of features, provided that the inertial sensors include at least one accelerometer (see table I). From our derivations, it is also possible to conclude that they are independent of the knowledge of the bias and the magnitude of the gravity. In order to complete our investigation, we need to consider the case without accelerometers. Obviously, in this case we loose the absolute scale and the roll and pitch angles. On the other hand, it must be investigated how the number of features impacts the observability properties, depending on the gyroscopes that are available. We are currently investigating these cases.

Finally, we wish to emphasize that, this research on visualinertial structure from motion with missing inertial inputs, pushed us to investigate the UIO problem. Currently, our results on UIO (available in [START_REF] Martinelli | Nonlinear Unknown Input Observability: Extension of the Observability Rank Condition and the case of a single unknown input[END_REF]) provide an exhaustive answer to the case of a single unknown input. In this case, we introduced a simple algorithm to directly obtain the entire observable codistribution. As in the standard case of only known inputs (i.e., without unknown inputs), the observable codistribution is obtained by recursively computing the Lie derivatives along the vector fields that characterize the dynamics. However, in correspondence of the unknown input, the corresponding vector field must be suitably rescaled. Additionally, the Lie derivatives must be computed also along a new set of vector fields that are obtained by recursively performing suitable Lie bracketing of the vector fields that define the dynamics. In practice, the entire observable codistribution is obtained by a very simple recursive algorithm. However, the analytic derivations required to prove that this codistribution fully characterizes the weak local observability of the state are very complex (theorem 1 in [START_REF] Martinelli | Nonlinear Unknown Input Observability: Extension of the Observability Rank Condition and the case of a single unknown input[END_REF]). Finally, in [START_REF] Martinelli | Nonlinear Unknown Input Observability: Extension of the Observability Rank Condition and the case of a single unknown input[END_REF] we showed that the recursive algorithm converges in a finite number of steps and we also provided the criterion to establish that the convergence has been reached. Also this proof is based on several tricky analytical steps (theorem 2 in [START_REF] Martinelli | Nonlinear Unknown Input Observability: Extension of the Observability Rank Condition and the case of a single unknown input[END_REF]). We are currently extending these results to the case of multiple unknown inputs.

Algorithm 1 (

 1 Computation of Ωk ) Set Ω0 the span of the gradient of the output Set m = 0 while m < k do Set m = m + 1 Compute all the m-order Lie derivatives of the output along the directions f

Note that in[START_REF] Martinelli | Nonlinear Unknown Input Observability: Extension of the Observability Rank Condition and the case of a single unknown input[END_REF] we provide a simple automatic method to directly generate these functions, starting from the dynamics in[START_REF] Jones | Visual-inertial navigation, mapping and localization: A scalable real-time causal approach[END_REF]. Note also that in[START_REF] Martinelli | Nonlinear Unknown Input Observability: Extension of the Observability Rank Condition and the case of a single unknown input[END_REF] we proved a further fundamental result that allows us to detect the largest integer m to be considered in the algorithm 1 to obtain all the observability properties (see theorem 2 in[START_REF] Martinelli | Nonlinear Unknown Input Observability: Extension of the Observability Rank Condition and the case of a single unknown input[END_REF]).

*This work has been supported by the French National Research Agency ANR 2014 through the project VIMAD

A. Martinelli is with


Alain Sarlette

A common symmetrization framework for iterative (linear) maps

This paper highlights some more examples of maps that follow a recently introduced "symmetrization" structure behind the average consensus algorithm. We review among others some generalized consensus settings and coordinate descent optimization.

Introduction

The linear consensus algorithm [START_REF] Tsitsiklis | Problems in decentralized decision making and computation[END_REF] x k (t + 1) = x k (t) + N j=1 a jk (x j (t) -x k (t)) , k = 1, 2, ..., N,

with a j k ≥ 0, or equivalently for x k ∈ R, x(t + 1) = A(t) x(t) where the matrix A has off-diagonal components A jk = a jk and diagonal component A kk = 1 -N j=1 a jk , features several geometric structures that could serve as a basis for generalization. In previous work we have considered the structure of (1) on a cone space, associated to the Hilbert metric, which generalizes (1) e.g. towards "non-commutative consensus" and the Kraus maps of quantum dynamics [START_REF] Sepulchre | Consensus in non-commutative spaces[END_REF]. More recently [START_REF] Mazzarella | Extending robustness and randomization from consensus to symmetrization algorithms[END_REF], we have explored a structure related to the network interaction and generalized (1) into a "symmetrization" class of iterative maps, which is restricted to linear procedures but allows to cover consensus on (quantum) probability spaces and some geometric control design algorithms.

In the present paper, we want to give a few more examples of applications covered by the former approach. In particular:

-In Section 3 we show how symmetrization readily applies to the modeling of some direct variants of (1). -In Section 4 we slightly relax the symmetrization assumptions to model gradient and coordinate descent (for a quadratic cost function to stay in the linear context).

The intended message of this paper is in showing the possibility to model a set of a priori different maps as one class of dynamics. We denote by I the identity matrix and by e the identity element of a group; when numbering group elements we use the convention g 1 = e.

Let us first recall the symmetrization framework developed in [START_REF] Mazzarella | Extending robustness and randomization from consensus to symmetrization algorithms[END_REF]. The main point is to write an iterative map

x(t + 1) = Φ(x(t), t) (2)
as a stochastic combination of actions of a discrete group G, i.e.

Φ(•, t) = |G| i=1 w i (t)a(g i , •) (3)
where g i ∈ G are the elements of the group, a(g i , •) is a linear action associated to g i on the space X ∋ x, and the w i satisfy:

w i (t) ≥ 0 for all i, |G| i=1 w i (t) = 1.
The iterative map (2) can then be lifted, possibly non-uniquely, to dynamics on the stochastic weights of group elements. I.e. we can write

x(t) = |G| i=1 p i (t) a(g i , x(0))
and describe the evolution of the p i (t). Explicitly, defining π i (k) such that g πi(k) = g -1 i g k in the group sense, we have

p k (t + 1) = |G| i=1 w i (t) p πi(k) (t) , k = 1, 2, ..., |G| , (4)
starting with p 1 (0) = 1 for g 1 = e and p k (0) = 0 for k = 1. In general, |G| can be much larger than the dimension of X . Yet the interesting point is that (4) is completely independent of X and of the particular action a(g i , •). This has allowed us to cover with one single model, consensus on variables belonging to vector spaces, so-called "symmetric consensus" on probabilities over a discrete set and similarly "symmetric quantum consensus". In the two latter applications, not only marginal probabilities but also all multi-partite correlation probabilities converge to the same values for all agents. It is not difficult to see that the |G| × |G| state matrix describing (4) is doubly stochastic. It is hence stable and features as a particular stationary point the uniform weight distribution p = p where pk = 1/|G| for all k. For this stationary point, in the X space, we have

x = 1 |G| |G| i=1 a(g i , x(0)) .
We hence call x the symmetrization of x 0 with respect to ( G, a(•, •) ), and a fortiori if Φ can be written as (3) then x is a stationary point of Φ.

In general the goal of Φ is to make x converge to x. A sufficient condition for this is that the associated lift (4) makes p converge to p. In some situations, especially with time-varying Φ, the lift might provide more insights, e.g.: Proposition 1: Given δ > 0, T > 0, denote S(t) ⊆ G the set of g i for which t+T t ′ =t w i (t ′ ) > δ. If there exist δ > 0, T > 0 and H ⊆ G generating G such that • g 1 = e ∈ S(t) for each t and

• H ⊆ S(t) for each t, then the dynamics (4) makes p converge to p.

With different choices of the lift, Proposition 1 can prove convergence of several different linear iterative maps at once, instead of having to repeat a "similar" proof argument for each specific map separately. In [START_REF] Mazzarella | Extending robustness and randomization from consensus to symmetrization algorithms[END_REF] a few examples are given. In the following we present a few others. Note that each of these examples has been efficiently solved on its own in the respective literature; our point here is that a common framework is established for all of them.

Variations on consensus

Let us first review how (1) can be cast into the symmetrization framework, at least for the usual case where A is doubly stochastic, implying a.o. j a jk ≤ 1 for all k. Take Ḡ = Perm N the group of permutations on N elements. The easiest case is "gossip", where at each t a single pair (m, n) of agents interacts with a mn = a nm = 0: we can then write w 1 = 1 -a m,n for g 1 = e and w i = a m,n for g i the pairwise permutation of (m, n), all other w i zero. Several variations that allow several interactions at once, admit a similarly direct treatment.

For a general situation with A doubly stochastic, we use a result by Birkhoff [START_REF] Birkhoff | Three observations on linear algebra[END_REF] to decompose Φ into a convex sum of permutations. If there exists α > 0 such that a kk > α for all k, then à = 1 1-α (A -αI) is also doubly stochastic and by applying the Birkhoff result to Ã, we obtain a decomposition of A = αI +(1-α) à into permutation matrices weighted by w i and where w 1 ≥ α. Except for special time dependencies of the a jk (t), generally an element for which w i > δ at some t satisfies t+T t ′ =t w i (t ′ ) > δ for all t, for T large enough. We then say that all elements are recurrent. In this case, Proposition 1 ensures that p(t) converges to the uniform distribution p over all elements of the group G ⊆ Ḡ generated by the elements that appear in the decomposition. Concretely, for instance:

-For pairwise gossip, if the interaction graph corresponding to the ājk = t+T t ′ =t a jk (t ′ ) is connected, then the associated pairwise permutations generate all of Ḡ = Perm N . A generalization to the case where the interaction graph is composed of several connected components is immediate.

-When a jk = β/N for all j = k and some β ∈ (0, 1), an associated lift would be w 1 = 1 -β and w i = β/N for all g i which are a power 1 to N -1 of the circular permutation g c : (1, 2, 3, ..., N ) → (N, 1, 2, ..., N -1). These form a closed subgroup G ⊂ Perm N . But still, having p converge to the uniform distribution over these N elements is sufficient to have the x k converge to 1/N N k=1 x k (0) for each k. Problems with the lift could arise if an element of Perm N \G appears rarely, i.e. without belonging to the set S(t) of Proposition 1 for any large T . This seems unlikely in practical situations.

In this setting, whether x k is a scalar, vector or other object of a linear space X does not matter, it just affects the group actions. Another action allows to apply the same group dynamics to the symmetrization of joint probability distributions, both classical and quantum, over a finite set [START_REF] Mazzarella | Extending robustness and randomization from consensus to symmetrization algorithms[END_REF]. We now turn to different variants of (1) for x k ∈ R.

Consensus with antagonistic interactions

A variant of consensus proposed e.g. in [START_REF] Meng | Modulus consensus over networks with antagonistic interactions and switching topologies[END_REF] considers that agents might be attracted to the opposite of the values of some neighbors, i.e. the dynamics become

x k (t + 1) = a kk x k (t) + a jk x j (t) (5)
with a kk = 1j =k |a jk | > 0, but possibly some negative a jk for j = k.

To cover this possibility, we take G the group corresponding to all permutation matrices with arbitrary sign ±1 on each component; we call this "generalized" permutations. This can be viewed as a particular product of the group of permutations with the group {-1, 1} N . We then lift (5) as follows.

-Take the Birkhoff decomposition associated to the corresponding standard consensus algorithm, where each a jk in ( 5) is replaced by |a jk |. This gives nonzero weights wi on the g i ∈ G corresponding to permutation matrices. -Then sequentially consider each pair (j, k) for which a jk < 0 and swap the weights attributed to the generalized permutation matrices which are equal up to the sign of their element (j, k).

Convergence of ( 5) is efficiently characterized a.o. in [START_REF] Hendrickx | A Lifting Approach to Models of Opinion Dynamics with Antagonisms[END_REF].We just provide an informal summary on the basis of G. As for standard consensus, we may generally assume that all the elements appearing in the lift are recurrent. The generated group G over which we get p = p at convergence then depends (only) on the group generated by the appearing elements. Three main situations can occur:

-The interaction graph is not connected.

-The component (k, k) takes the same sign in the matrices associated to all the generated group elements. By group properties, this implies that all components (j, j) have the same sign in all the generated group elements, provided the interaction graph is connected. Then in terms of x k , the agents split into two communities with opposite component values as t → ∞. -The component (k, k) can take opposite signs in the generated group elements. Then, thanks to group properties, for each j, k there should be an equal number of elements with negative component (j, k) as with positive component (j, k) in the generated group G. This implies that when p converges to p uniform over G, the corresponding x k converge to 0.

Our lift can involve many elements but still a finite number, i.e. it abstracts away the exact values of the a j,k (t) in [START_REF] Meng | Modulus consensus over networks with antagonistic interactions and switching topologies[END_REF]. While our framework may appear more cumbersome than the graph analysis of [START_REF] Hendrickx | A Lifting Approach to Models of Opinion Dynamics with Antagonisms[END_REF], it can also yield more precise results in some cases. Indeed, we can exactly cover the following example which [START_REF] Hendrickx | A Lifting Approach to Models of Opinion Dynamics with Antagonisms[END_REF] provides as an inconclusive case of their graph-conditions-based theorem:

x k (t + 1) = 1/2 (x 1 (t) + x 2 (t)) , k = 1, 2; t even x k (t + 1) = (-1) k /2 (x 2 (t) -x 1 (t)) , k = 1, 2; t uneven .
The dynamics can be explicitly solved and converges to x 1 = x 2 = 0 after iterations t = 0, t = 1, yet the theorem of [START_REF] Hendrickx | A Lifting Approach to Models of Opinion Dynamics with Antagonisms[END_REF] cannot tell this. In terms of our lift, we have three recurrent elements

g 1 = 1 0 0 1 ; g 2 = 0 1 1 0 ; g 3 = 0 -1 -1 0
with weights w 1 = 1/2, w 2 (t) = 1/4 + (-1/4) t , w 3 (t) = 1/4 -(-1/4) t . These weights are in fact irrelevant, we only need to compute that g 1 , g 2 , g 3 generates a 4-group element, together with g 4 = -g 1 . We then readily conclude that the system converges to x = 1 4 4 i=1 g i x = 0. At this stage we do not claim that the group lift approach is efficiently scalable to larger problems. Yet it might suggest e.g. how to adapt the graph analysis argument of [6] towards covering the above example.

Doubly sub-stochastic matrices

Consensus is a particular linear dynamics which features a one-dimensional invariant space. In iterative maps, the most common situation is when there is only one target invariant point. This happens with "smaller than stochastic" A. Shifting the invariant point to x = 0, we define the following class of systems:

x k (t + 1) = N j=1 a jk (t) x j (t) with 1 ≥ j |a jk (t)| for all k, t (6) 1 ≥ k |a jk (t)| for all j, t .
Such system can be straightforwardly rewritten as consensus with (possibly antagonistic interactions and) a virtual leader x 0 (t) = 0, hence proving convergence is not a big issue. Again our intended contribution is more to show that this dynamics, as well, can be cast into the class of symmetrization algorithms. For simplicity of notations we describe the following assuming a jk ≥ 0 for all j, k.

Take the same group G as in Section 3.1. We first define b jk = a jk + c jk with c jk ≥ 0 and such that N j=1 b jk = N j=1 b kj = 1 for all k, i.e. the state matrix associated to the b jk is doubly stochastic. Such a construction is always possible for a sub-stochastic matrix, e.g. as follows:

0. Let a ′ jk := a jk for all j, k.

1. Compute a c k = N j=1 a ′ jk and a r k = N j=1 a ′ kj for all k. 2. Since k a c k = j,k a ′ jk = k a r k : if a c
k < 1 for some k then there exists k ′ such that a r k ′ < 1, and vice versa. Else a c k = a r k = 1 for all k, i.e. the a ′ jk matrix is already doubly stochastic and we can stop. 3. Find a r m = max(a r k : a r k < 1) and a c n = max(a c k : a c k < 1). Then let b mn = a ′ mn + c mn with c mn = 1 -max(a r m , a c n ), and b jk = a ′ jk for all (j, k) = (m, n).

Define a ′

jk := b jk for all j, k and iterate the procedure starting again from 1. This procedure converges to a doubly stochastic matrix. Indeed, at each iteration: if the a ′ jk are doubly sub-stochastic then also the b jk are; and the b jk matrix has at least one more row or column whose elements sum to 1 than the a ′ jk matrix. Define by { wi } a lift of the dynamics associated to the standard consensus x k (t + 1) = N j=1 b jk (t) x j (t) . We then sequentially go through all (j, k) for which c jk > 0 and transform the weights as follows. 0. Let w ′ i = wi for all i and choose some (j, k) for which c jk > 0. 1. Denote f - jk (m) = n such that g n is identical to g m except that the matrix element (j, k) associated to g m has an opposite sign in g n . Then for all i for which g i has a positive element (j, k), apply

w i = (1 - c jk 2b jk ) w ′ i , w f - jk (i) = c jk 2b jk w ′ i .
2. Let w ′ i = w i , choose a different (j, k) with c jk > 0 and iterate from point 1.

The weight modification in point 1 above preserves the total weight, i w i = i w ′ i . The w i remain non-negative, since c jk ≥ 0, b jk ≥ 0, a jk ≥ 0 and 1-

c jk 2b jk = 1- c jk
2c jk +2a jk > 0. Summing up the effect on i w i a(g i , •), we see that when point 1 treats (j, k), the matrix components different from (j, k) undergo no change while the component on (j, k) is modified:

from i∈F j,k w ′ i =: B 1 to i∈F j,k w ′ i (1 - c jk 2b jk ) - c jk 2b jk =: B 2 ,
where F j,k ⊂ G is the subset of group elements whose associated matrix have a coefficient +1 at position (j, k). By definition of the lift, we have

B 1 = b jk . We then get B 2 = B 1 (1 - c jk
b jk ) = a jk , thus indeed the matrix that we had to model. From there, we can go on and analyze convergence of the resulting group dynamics. By construction, if G contains g i then also contains g f - jk (i) for each (j, k) for which c jk > 0. Hence if p(t) converges to p uniform over G, then the corresponding (j, k) elements will be zero in the matrix associated to

1 |G| |G| i=1 a(g i , •).

Gradient Descent and Coordinate Descent

In optimization, the gradient descent method consists in iteratively searching for min f (x) by applying

x(t + 1) = x(t) -α grad x f (x(t)) , α > 0 , x ∈ R N . (7)
For a local quadratic expansion f = 1 2 x T Ax around the minimum, A symmetric positive definite, approximating (7) by a linear map, there is a trivial symmetrization viewpoint on the resulting x(t + 1) = x(t) -αAx(t).

In the eigenbasis of A, (7) becomes x k (t + 1) = (1 -α a k ) x k (t) with a k the associated eigenvalues. For stable algorithms, (1 -α a k ) ∈ (-1, 1) such that the associated state transition matrix is (diagonal and) doubly substochastic. A simplified version of section 3.2 then rewrites this iteration as symmetrization over the group G represented by diagonal N × N matrices with elements ±1. This abstract definition does not require to actually compute the eigenbasisonly assume it exists and the a k are small enough. Yet this viewpoint must be adapted to address the following.

Coordinate Descent

Coordinate descent selects some k ∈ { 1, 2, ..., N } at each step and applies gradient descent to minimize f (x) along a line where only x k varies, assuming fixed all x j with j = k. This comes closer to a (possibly stochastically) time-varying map as in consensus. It links to symmetrization as follows, e.g. for N = 2: define

y = √ a 1 0 0 √ a 2 cos θ sin θ -sin θ cos θ x such that f (x) = 1 2 x T Ax = 1 2 y T y.
This simplifies the cost function, but coordinate descent now implies iterative optimization along two arbitrary lines, of slopes tan φ 1 = tanθ a 2 /a 1 and tan φ 2 = -cotanθ a 2 /a 1 . In general those lines are not orthogonal, but f will still be quadratic along each of them. It is not difficult to see that we can then write, if k ∈ {1, 2} is chosen at time t:

y(t + 1) = (1 -λ) y(t) + λ (reflection of y(t) around axis of slope cotan φ k ) = (1 -λ) y(t) + λ -cos 2φ k sin 2φ k sin 2φ k cos 2φ k y(t) ,
for some λ ∈ (0, 1). In general, (1 -λ) + λ(cos + sin) > 1 and the associated transition matrix is not sub-stochastic. Nevertheless, we were able to write this as symmetrization with respect to the 8-element group G =

g ± 1 = ± 1 0 0 1 , g ± 2 = ± 1 0 0 -1 , g ± 3 = ± 0 1 1 0 , g ± 4 = ± 0 1 -1 0 . Explicitly, y(t + 1) = (w 1+ g + 1 + w 2-g - 2 + w 2+ g + 2 + w 3-g - 3 + w 3+ g + 3 ) y(t) with w 1+ = 1 -λ ; w 2-= λ ( 1 4 + cos φ k 2 ) ; w 3+ = λ ( 1 4 + sin φ k 2 ) w 2+ = λ ( 1 4 -cos φ k 2 ) ; w 3-= λ ( 1 4 -sin φ k 2 )
. By construction gi∈G w i = 1. However we do not have w i > 0 for all i. This requires to slightly generalize the class of dynamics accepted on the group. In the present case:

The state transition matrix for the weights p i (t) on the group G is symmetric and doubly stochastic, up to having possibly negative off-diagonal components. Hence it still features p as a stationary point. Its convergence is not as straightforward to analyze as standard consensus. However thanks to symmetry, in a time-varying context it suffices for convergence to examine the common Lyapunov function V (t) = i (p i (t)) 2 . For this particular example, i.e. a two-dimensional x, the state transition matrices for the p i (t) further admit an efficient tensor product decomposition such that convergence conditions can be easily formalized. At this point we cannot claim that the symmetrization framework is efficient to study convergence for high-dimensional x. Yet, the possibility to model the system as symmetrization, with generalized (possibly negative) weights, could suggest a way to include coordinate descent in versatile theoretical formalizations that exploit the symmetrization structure.

Conclusion

We have abstractly defined a "symmetrization" class of linear iterative maps. This class comprises a great variety of algorithms, as illustrated in [START_REF] Mazzarella | Extending robustness and randomization from consensus to symmetrization algorithms[END_REF]. The present paper highlights some further elements of the class. Although each instance encountered so far, admits a relatively easy specific convergence proof, the common symmetrization framework allows to treat them all at once, modulo a finite group analysis step. In the future we hope that further properties of this symmetrization class can be exploited in general analyzes.

Acknowledgments

I thank F.Ticozzi and L.Mazzarella for sharing ideas on the symmetrization approach and R.Sepulchre for encouraging to address these particular applications.