Yougourthen Boumekla

Fengjie Xia

Lucas Vidal

Cédric Totée

Christophe Raynaud

Armelle Ouali

Calcium-catalysed synthesis of amines through imines hydrosilylation: an experimental and theoretical study

A method to reduce aldimines through hydrosilylation is reported. The catalytic system involves calcium triflimide (Ca(NTf2)2) and potassium hexafluorophosphate (KPF6) shown to act in a synergistic manner. The expected amines are obtained in fair to very high yields (40-99%) under mild conditions (room temperature in most cases). To illustrate the potential of the method, a bioactive molecule with antifungal properties was prepared in gram scale and high yield in environmentally friendly 2-methyltetrahydrofuran. Moreover, it was shown on this example that the imine can be prepared in situ from the aldehyde and the amine without isolating the imine. The mechanism involved has been explored experimentally and through DFT calculation, and the results are in accordance with an electrophilic activation of the silane by the calcium catalyst.

2

Introduction

Amines constitute highly important building blocks in organic synthesis due to their omnipresence in natural products, polymers, 1 pharmaceuticals 2 or agrochemicals. [START_REF] Lawrence | Amines: Synthesis, Properties and Applications[END_REF][START_REF] Vogt | Ullmann's Encyclopedia of Industrial Chemistry[END_REF] Among the synthetic strategies towards these key compounds, catalytic reduction of imines including hydrogenation, hydrogen transfer or hydrosilylation, appear as efficient methodologies. Within the last few years, hydrosilylation processes involving silanes as the H source, significantly contributed to the preparation of amines. [START_REF] Li | Amine synthesis via transition metal homogeneous catalysed hydrosilylation[END_REF][START_REF] Shaikh | Sustainable Amine Synthesis: Iron Catalyzed Reactions of Hydrosilanes with Imines, Amides, Nitroarenes and Nitriles[END_REF] Hydrosilanes, readily produced on an industrial scale, indeed constitute useful reducing agents due to their air-and water stability, ease of handling and ability to be activated in mild conditions. They thus appear as an attractive alternative to molecular hydrogen often requiring high temperature and pressure conditions as well as specific set-up. Although ytterbium-, aluminium-, boron [START_REF] Zhu | A Chiral Borane Catalyzed Asymmetric Hydrosilylation of Imines[END_REF][START_REF] Mewald | Illuminating the Mechanism of the Borane-Catalyzed Hydrosilylation of Imines with Both an Axially Chiral Borane and Silane[END_REF] -even ionic liquid [START_REF] Li | Imidazolium-based ionic liquid-catalyzed hydrosilylation of imines and reductive amination of aldehydes using hydrosilane as the reductant[END_REF] -based or organic [START_REF] Malkov | Catalyst development for organocatalytic hydrosilylation of aromatic ketones and ketimines[END_REF] catalysts have been shown to promote imine hydrosilylations, the most ubiquitous catalysts for these transformations involve transition metals. Historically, the first systems reported involved noble ones (ruthenium, rhodium, iridium, palladium) and later on, some catalysts based on more earth abundant metals such as copper, [START_REF] Lipshutz | Copper(I)-Catalyzed Asymmetric Hydrosilylations of Imines at Ambient Temperatures[END_REF] zinc, [START_REF] Swewczyk | Zinc-Catalyzed Enantioselective Hydrosilylation of Ketones and Imines under Solvent-Free Conditions[END_REF] nickel, [START_REF] Zheng | Nickel-Catalysed Reductive Amination with Hydrosilanes[END_REF] or iron [START_REF] Jaafar | Phosphane-Pyridine Iron Complexes: Synthesis, Characterization and Application in Reductive Amination through the Hydrosilylation Reaction[END_REF][START_REF] Castro | NHC-carbene cyclopentadienyl iron based catalyst for a general and efficient hydrosilylation of imines[END_REF][START_REF] Bhunia | A Highly Efficient Base-Metal Catalyst: Chemoselective Reduction of Imines to Amines Using An Abnormal-NHC-Fe(0) Complex[END_REF][START_REF] Saini | Conversion of aldimines to secondary amines using ironcatalysed hydrosilylation[END_REF] have been developed. [START_REF] Li | Amine synthesis via transition metal homogeneous catalysed hydrosilylation[END_REF] Some of the complexes required multi-step ligand synthesis and/or are air-or moisture sensitive. Our objective consisted in providing the actual toolbox for imine hydrosilylation with a catalytic system involving a benign metal and attractive for the organic chemist namely readily available and easy to handle (air-and moisture stable). We then turned our attention to calcium. Generally, alkaline earth metals (Ae = Mg, Ca, Sr, Ba) attracted much attention over the last decade and catalytic systems have been reported to promote a wide range of processes including ring-opening polymerizations, [START_REF] Sarazin | Discrete Cationic Complexes for Ring-Opening Polymerization Catalysis of Cyclic Esters and Epoxides[END_REF] C-C or C-heteroatom bond-forming transformations, [START_REF] Kobayashi | Alkaline Earth Metal Catalysts for Asymmetric Reactions[END_REF][START_REF] Leboeuf | Carbon-Carbon and Carbon-Heteroatom Bond-Forming Transformations Catalyzed by Calcium(II) triflimide[END_REF] dehydrocouplings [START_REF] Li | A Dialkyl Calcium Carbene Adduct: Synthesis, Structure, and Catalytic Cross-Dehydrocoupling of Silanes with Amines[END_REF][START_REF] Rauch | Reactivity of [Tism PriBenz ]MgMe towards Secundary Amines and Terminal Alkynes : catalytic Dehydrocoupling with Hydrosilanes to Afford Si-N and Si-C Bonds[END_REF][START_REF] Forosenko | Amido Ca(II) Complexes Supported by Schiff Base Ligands for Catalytic Cross-Dehydrogenative Coupling of Amines with Silanes[END_REF][START_REF] Zhao | Calcium-Catalyzed Dehydrogenative Silylation of Aromatic Ethers with Hydrosilanes[END_REF] or hydroelementations of C=C, C=O or C=N bonds. [START_REF] Harder | From Limestone to Catalysis: Application of Calcium Compounds as Homogeneous Catalysts[END_REF][START_REF] Harder | Molecular early main group metal hydrides: synthetic challenge, structures and applications[END_REF][START_REF] Hill | Alkaline earths as main group reagents in molecular catalysis[END_REF][28] Along these lines, alkaline earth complexes were shown to promote hydrosilylation of olefins [START_REF] Garcia | Magnesium Hydride Alkene Insertion and catalytic Hydrosilylation[END_REF][START_REF] Schuhknecht | Regioselective Hydrosilylation of Olefins Catalyzed by a Molecular Calcium Hydride Cation[END_REF][START_REF] Rauch | Synthesis, Structure, and Reactivity of a Terminal Magnesium Hydride Compound with a Carbatrane Motif, [Tism PriBenz ]MgH : A Multifunctional Catalyst for Hydrosilylation and Hydroboration[END_REF] or pyridines. 32- 35 Interestingly, concerning non-activated C=N bonds, Sarazin et al reported stoichiometric hydrosilylation of imine ligands in barium complexes. [START_REF] Chapple | A versatile nitrogen ligand for alkalineearth Chemistry[END_REF] In addition, a recent breakthrough by Harder et al demonstrated for the first time the ability of calcium, strontium and barium complexes involving amide and/or benzyl ligands to catalyse the hydrosilylation of aldimines and one ketimine with phenylsilane. [START_REF] Elsen | Early Main Group Metal Catalysts for Imine Hydrosilylation[END_REF][START_REF] Bauer | Similar complexes are able to promote the related imine hydrogenation[END_REF] In this report, a commercial and moisture stable calcium salt Ca(NTf2)2 is shown to act in a synergistic manner with KPF6 and in the absence of any additional ligands to catalyse hydrosilylation of aldimines under mild conditions. DFT studies have been carried out to get insight into the involved mechanism. To the best of our knowledge, if calcium-based Lewis acids emerged as important catalysts in green chemistry, Ca(NTf2)2 has not been used yet to promote imines hydrosilylation. [START_REF] Leboeuf | Carbon-Carbon and Carbon-Heteroatom Bond-Forming Transformations Catalyzed by Calcium(II) triflimide[END_REF]28 In addition, it is the first time that calcium triflimide is shown to activate Si-H bonds which opens new prospects in the fields of hydrosilylation reactions as well.

Results and Discussion

Imine 1a, which results from the condensation of 4bromobenzaldehyde and 4-iodoaniline, was chosen as the model substrate. The performance of several commercial calcium salts was evaluated in the hydrosilylation of 1 with phenylsilane at room temperature. Although calcium hydroxide and alkoxides revealed inefficient (no 1a conversion), Ca(NTf2)2, a calcium precursor that carries a strong electron-withdrawing and weakly coordinating counter anion, allowed the formation of expected amine 2a, with low yield (10%) however (Table 1, entry 1). The addition of catalytic amounts of KPF6 (20 mol%) enabled to significantly increase the performances (entry 2), 2a being quantitatively obtained. It is noteworthy that Ca(NTf2)2 and KPF6 acted in a synergistic manner, KPF6 being inefficient when used alone (entry 3). It has previously been shown that Ca(NTf2)2 and PF6 salts underwent anion metathesis to form KNTf2 and Ca(NTf2)PF6. [START_REF] Leboeuf | Carbon-Carbon and Carbon-Heteroatom Bond-Forming Transformations Catalyzed by Calcium(II) triflimide[END_REF] The latter salt, more Lewis acidic than Ca(NTf2)2 and displaying two binding sites available on the calcium center, was reported to activate a wide range of substrates such as cyclopropanes, [START_REF] Maloney | Friedel-Crafts Alkylation of Benzo[b]furan with Activated Please do not adjust margins Cyclopropanes by a Calcium(II) Complex[END_REF][START_REF] Dulin | Calcium-Catalyzed Friedel-Crafts Addition of 1-methylindole to Activated Cyclopropanes[END_REF] carbonyl compounds, [START_REF] Davies | The First Calcium-Catalyzed Nazarov Cyclisation[END_REF][START_REF] Morcillo | Site-Selective Calcium-Catalyzed/Organocatalyzed Condensation of Propargyl Alcohols Tethered to -Keto-esters[END_REF] alcohols, [START_REF] Meyer | Highly Chemoselective Calcium-Catalyzed Propargylic Deoxygenation[END_REF][START_REF] Basson | Synthesis of Functionalized Isoindolinones via Calcium Catalyzed Generation and Trapping of N-Acyliminium Ions[END_REF][START_REF] Xie | Dehydrative Cross-Coupling of Allylic Alcohols with Alkynes[END_REF][START_REF] Xie | Reciprocal-Activation Strategy for Allylic Sulfination with Unactivated Allylic Alcohols[END_REF][START_REF] Morcillo | Calcium-Catalyzed Synthesis of Polysubstituted 2-Alkenylfurans from -Keto Esters Tethered to Propargyl Alcohols[END_REF][START_REF] Yang | DFT Analysis into the Calcium(II)-Catalyzed Coupling of Alcohols with Vinylboronic Acides: Cooperativity of Two Different Lewis Acids and Counterion Effects[END_REF] alkenes [START_REF] -M. Begouin | Calcium-Catalyzed Hydroalkoxylation[END_REF][START_REF] Niggemann | Calcium-Catalyzed Hydroarylation of Alkenes at Room Temperature[END_REF] or more recently sulfonyl [START_REF] Mukherjee | Sulfonamide Synthesis via Calcium Triflimide Activation of Sulfonyl Fluorides[END_REF][START_REF] Mukherjee | SuFEx Activation with Ca(NTf2)2: A Unified Strategy to Access Sulfamides, Sulfamates, and Sulfonamides from S(VI) Fluorides[END_REF] fluorides. [START_REF] Leboeuf | Carbon-Carbon and Carbon-Heteroatom Bond-Forming Transformations Catalyzed by Calcium(II) triflimide[END_REF]28,[START_REF] Begouin | Calcium-Catalyzed Lewis Acid Catalysts[END_REF] Ca(NTf2)PF6, whose Lewis acidity has been evaluated by the Childs method, [START_REF] Davies | The First Calcium-Catalyzed Nazarov Cyclisation[END_REF] has also been associated with hexafluoroisopropanol as the solvent and the resulting system shown by Gandon and Leboeuf to be highly active in various transformations including Aza-Piancatelli, [START_REF] Morcillo | Harnessing the Lewis Acidity of HFIP through its Cooperation with a Calcium(II) Salt: Application to the Aza-Piancatelli Reaction[END_REF][START_REF] Marin | Sulfoxide-Controlled Stereoselective Aza-Piancatelli Reaction[END_REF] hydroarylation, [START_REF] Qi | Calcium(II)-Catalyzed Intermolecular Hydroarylation of Deactivated Styrenes in Hexafluoroisopropanol[END_REF] or hydroamidation [START_REF] Qi | Calcium(II)-Catalyzed Intra-and Intermolecular Hydroamidation of Unactivated Alkenes in Hexafluoroisopropanol[END_REF] or hydroacyloxylation [START_REF] Qi | Calcium(II)-and Triflimide-Catalyzed Intramolecular Hydroacyloxylation of Unactivated Alkenes in Hexafluoroisopropanol[END_REF] reactions. It is noteworthy that under our conditions, KNTf2 itself was unable to promote imine 1a hydrosilylation (entry 4), suggesting that Ca(NTf2)PF6 is the catalytically active species. Furthermore, triflimic acid was unable to promote hydrosilylation, which ruled out the possibility that traces of Tf2NH were at the origin of the observed activity and confirmed that the calcium center played a role in the catalytic process. 5) KPF6 ( 5) 2 87 a Typical procedure: Ca(NTf2)2, KPF6, PhSiH3 and THF (1 mL) were stirred at 25 °C for 10 minutes before adding the aldimine 1a (0.25 mmol) and THF (0.5 mL). The reaction mixture was stirred at 25 °C for 16 h and next hydrolysed with MeOH (1.5 mL) and NaOH (2M, 1.5 mL). b Yield determined by NMR using 1,3,5-trimethoxybenzene as the standard (selectivity > 99%). c after 6h instead of 16.

The amounts of catalyst and additive could be successfully decreased to 10 mol % without significant change (entry 5). Under these conditions, by decreasing the amount of silane by two (2 equiv instead of 4, entry 6), amine 2a could be obtained quantitatively when the reaction was stopped after 16 hours at 25 ° C (entry 6). It is worthy to note that 2a is formed in 86% yield after only 6 hours, suggesting that the conversion is attained before 16 h. Decreasing the amount of Ca(NTf2)PF6/ KPF6 (1:1) from 10 to 5 mol% only lead to a slight decrease of the yield of amine 2a from 99 to 87% (entry 7). With these optimized conditions in hand, phenylsilane was replaced by several cheaper counterparts including diphenylsilane, triphenylsilane, dimethylphenylsilane, triethylsilane and 1,1,3,3-tetramethyldisiloxane. However, none of the tested silanes allowed to observe the conversion of imine 1a at 25 °C. Next, the scope of the method was investigated on aromatic aldimines using Ca(NTf2)2 / PF6 (1:1) (10 mol%) as the catalytic system (Figure 1). (Benzylidene)phenylamine 1b was quantitatively transformed into amine 2b. Imines 1c and 1d, both derived from toluidine, underwent hydrosilylation in good yields as well (98 and 82% isolated yields for 2c and 2d respectively), even in the case of bulkier ortho-substituted naphtyl derivative 1d. Substrates 1e-

Please do not adjust margins

Please do not adjust margins g bearing electron-donating methoxy substituents were converted in fair to high yields (66, 82 and 99% for 2f, 2g and 2e respectively). While imine 1e was fully converted within 16 h at 25 °C, 2f and 2g derived from electron-rich p-methoxyaniline revealed less reactive and an increase in temperature to refluxing THF (65 °C) was required to improve the conversions. The hydrosilylation of imines 1h-j bearing electron-withdrawing trifluoromethyl groups was then investigated. Amines 2h, 2i and 2j could be formed quantitatively and isolated in very high yields (88, 97 and 90% respectively). Here again, the effect of the substituent revealed dependent on its position: while 1h and 1j issued from electron-poor p-trifluoromethylaniline were fully converted at 25 °C within 6 and 16h respectively, imine 1d bearing the CF3 substituent on the "aldehyde" side required higher temperature to be reduced (refluxing THF instead if 25 °C). As in the case of 1a, the halogenated imines 1k and 1l were quantitatively transformed into the corresponding amines 2k and 2l under standard conditions. The method revealed compatible with several functional groups including esters (90% and 82% isolated yields for 2m and 2n), cyano substituents (88% and 76% isolated yields for 2o and 2p) or ketones (94% yield for 2q). Significantly lower yields were obtained for amines 2r-u bearing alkyl substituents at N in refluxing THF. Increasing the amount of calcium catalyst from 10 to 20 mol% did not significantly improve the performances. Therefore, this system appears as complementary to the one reported by Harder, that has been shown to be particularly efficient for imines bearing an alkyl group at N and aryl substituents at C. [START_REF] Elsen | Early Main Group Metal Catalysts for Imine Hydrosilylation[END_REF] Interestingly, in addition to expected amines 2r and 2s, tertiary amines were formed and as an example, N,N-di(4-bromobenzyl)benzylamine 3s, isolated in 20% yield (see ESI p. S12), represents an appealing starting compounds towards pharmaceuticals or sensors. [START_REF] Li | Iridium-Catalyzed Alkylation of Amine and Nitrobenzene with Alcohol to Tertiary Amine under Base-and Solvent-Free Conditions[END_REF] The synthetic pathway to explain the formation of this by-product is still unclear. The heteroaromatic imines 1v and 1w were quantitatively reduced and the expected amines were isolated in good to very high yields (72 and 90% for 2v and 2w respectively). While 2v represents a potential ligand finding application in catalysis, 2w has potential applications in medicinal chemistry for its antifungal properties and also as a precursor for antitubercular agents. [START_REF] Kouznetsov | Antifungal and Cytotoxic Activities of some N-substituted Aniline Derivatives bearing a Hetaryl Fragment[END_REF][START_REF] Arshad | Synthesis of 3-chloro-4-fluorophenyl-3,4-dichlorophenyl substituted thiocarbamide derivatives as potential antitubercular agents[END_REF] At this stage, we were keen to get insights into the processes involved in the previously described hydrosilylation. From a mechanistic point of view, two main hydrosilane activation pathways have been previously proposed (Scheme 1): (i) the Chalk-Harrod and modified Chalk-Harrod mechanism occurring for e. g. with rhodium or platinum catalysts and relying on two-electron oxidative addition and reductive elimination steps (Scheme 1, A); (ii) a ionic mechanism in which a Lewis acidic catalyst enhances the electrophilic character of the silicon center through activation of the Si-H bond (Scheme 1, B). In Ae-catalyzed C=C or C=N hydrosilylation, metal hydride species play a key role in the mechanism and are proposed to be the active species. [START_REF] Garcia | Magnesium Hydride Alkene Insertion and catalytic Hydrosilylation[END_REF][START_REF] Schuhknecht | Regioselective Hydrosilylation of Olefins Catalyzed by a Molecular Calcium Hydride Cation[END_REF][START_REF] Rauch | Synthesis, Structure, and Reactivity of a Terminal Magnesium Hydride Compound with a Carbatrane Motif, [Tism PriBenz ]MgH : A Multifunctional Catalyst for Hydrosilylation and Hydroboration[END_REF][START_REF] Fohlmeister | Ring-Shaped Phosphinoamido-Magnesium-Hydride Complexes : Syntheses, Structures, Reactivity, and Catalysis[END_REF][START_REF] Elsen | Early Main Group Metal Catalysts for Imine Hydrosilylation[END_REF][START_REF] Mukherjee | Hydrido Complexes of Calcium: A new Family of Molecular Alkaline-Earth-Metal Compounds[END_REF] In some of these reactions, the pre-catalyst involves the metal-hydrogen bond. The calcium hydrido complexes can also be generated from amide/alkyl/benzyl calcium precursors and silanes through -bond metathesis (Scheme 1, C). This process has been widely described and exploited in catalytic reactions including hydrogenation or hydro-elementations, [START_REF] Mukherjee | Hydrido Complexes of Calcium: A new Family of Molecular Alkaline-Earth-Metal Compounds[END_REF] and more recently redistribution of hydrosilanes [START_REF] Li | Organocalcium Complex-Catalyzed Selective Redistribution of ArSiH3 or Ar(alkyl)SiH2 to Ar3SiH or Ar2(alkyl)SiH[END_REF] or dehydrogenative silylation of aromatic ethers. [START_REF] Zhao | Calcium-Catalyzed Dehydrogenative Silylation of Aromatic Ethers with Hydrosilanes[END_REF]

Scheme 1: Main mechanisms for silane activation pathways

In our conditions, calcium hydroxide, alkoxides and even calcium triflimidate Ca(NTf2)2 alone are not efficient to promote the hydrosilylation of imine 1a. The fact that hydrosilylation only occurs in the presence of the highly Lewis acidic salt Ca(NTf2)PF6 might suggest that the mechanism involves an electrophilic activation of the Si-H bond (Scheme 1, B). Such pathway was reported for ketones and imines hydrosilylation promoted by perfluoroarylborane such as B(C6F5)3 (Scheme 1, B). [START_REF] Parks | Tris(pentafluorophenyl)boron-Catalyzed Hydrosilylation of Aromatic Aldehydes, Ketones and Esters[END_REF][START_REF] Rendler | Conclusive Evidence for an SN2-Si Mechanism in the B(C6F5)3-Catalyzed Hydrosilylation of Carbonyl Compounds: Implications for the Related Hydrogenation[END_REF][START_REF] Lipke | Electrophilic Activation of Silicon-Hydrogen Bonds in catalytic Hydrosilylations[END_REF][START_REF] Piers | Mechanistic Aspects of Bond Activation with Perfluoroarylboranes[END_REF][START_REF] Mewald | Illuminating the Mechanism of Imines with Both an Axially Chiral Borane and Silane[END_REF] In these processes, hydrosilylation proceeded more rapidly in the case of least basic substrates. [START_REF] Lipke | Electrophilic Activation of Silicon-Hydrogen Bonds in catalytic Hydrosilylations[END_REF] In our conditions, the electronic properties of the substituents were shown to have an effect on the catalytic performances. For example, electron-poor imine 1h with a CF3 group in the para position of the imine nitrogen revealed significantly more reactive than imine 1f with an electron-donating methoxy group in the same position. Indeed, while 1h was quantitatively converted into 2h within 6h at room temperature (Figure 1, note d), 1f required heating to reach a conversion of 66% after 16h. Next the interaction between the Ca(NTf2)PF6 catalyst and each of the substrates, imines and silane, have been investigated. For this and in first intention, the evolution of a stoichiometric mixture of calcium catalyst and imine 1h in deuterated THF was monitored by 1 H NMR at different temperatures (25 °C to -65 °C and back to 25 °C). No obvious change could be observed on the imine spectrum whatever the temperature, suggesting that the presence of the hydrosilane is required for the two substrates to react together. The same behaviour was observed in the case of more electron-rich imine 1f. The same NMR experiment was then done in the case of phenylsilane. The addition of one equivalent of Ca(NTf2)PF6 to phenylsilane did not induce any change on the 1 H NMR spectrum of the silane at room temperature. Next 1 H NMR spectra were collected at lower temperatures, from 25 ° C to -65 ° C. At -25 ° C (ESI § 4.1). Interestingly, the appearance of broad signals at around 6ppm was observed and the signals were becoming increasingly sharp when decreasing the temperature to -65 ° C (ESI, Figure S1 p. S14). The phenomenon was shown to be reversible when coming back to room temperature (ESI, Figure S2 p. S14). These observations suggest a weak coordination of the silane to calcium. [START_REF] Lipke | Electrophilic Activation of Silicon-Hydrogen Bonds in catalytic Hydrosilylations[END_REF][START_REF] Lipke | Catalytic Olefin Hydrosilylation Mediated by Ruthenium  3 -H2Si  Complexes of Primary and Secondary Silanes[END_REF] This journal is © The Royal Society of Chemistry 20xx

Please do not adjust margins

Please do not adjust margins

From all these experimental observations, we propose a putative catalytic cycle (Scheme 2). The process starts with the generation of the catalytic active species and highly Lewis acidic Ca(NTf2)PF6 (represented as [Ca]), where the PF6 -counteranion is not expected to be in the first coordination sphere. [START_REF] Leboeuf | Carbon-Carbon and Carbon-Heteroatom Bond-Forming Transformations Catalyzed by Calcium(II) triflimide[END_REF][START_REF] Xue | Synthesis and Structures of Alkaline Earth Metal Salts of Bis[(trifluoromethyl)sulfonyl]imide[END_REF] The first step of the catalytic cycle would consist in the coordination of the silane to the calcium center Ca(NTf2) + (Scheme 2, step a). Subsequent intermolecular nucleophilic attack of imine on the silicon center may lead to a silyliminium intermediate (Scheme 2, step b), by analogy with the mechanism proposed in the case of B(C6F5)3. [START_REF] Mewald | Illuminating the Mechanism of Imines with Both an Axially Chiral Borane and Silane[END_REF] In the following step c, the H-transfer may occur. The last decoordination step d would enable the release of the expected silylamine and the regeneration of the calcium catalytic active species 3. To gain a better understanding of the mechanism of this catalytic hydrosilation, DFT studies were carried out with a dispersion corrected hybrid functional and an implicit model for the solvent (THF). Natural Bond Orbital (NBO) analyses of the stationary points of the potential energy surface have been carried out. Full computational details are given in the ESI. The Ca 2+ complex with the NTf -ligand, and the substrates (2b imine and PhSiH3) were represented in full. The PF6 -counteranion was supposed to be non-coordinated and was not taken into account for the modelisation. The overall reaction is found to be exergonic (ΔrG 0 = -16.9 kcal•mol -1 ) and requires a Gibbs activation energy of 26.1 kcal•mol -1 relative to the separate reagents (Figure 2). The driving force of the reaction relies on the C-H and Si-N bonds, which are slightly stronger than the broken Si-H and C=N bonds. The reaction mechanism is found to be the succession of two elementary steps. The reaction sequence begins with the coordination of the imine and PhSiH3 to the metal cation, leading to adduct A. The first step requires a low activation barrier (ΔG ‡ = 21.3 kcal•mol - 1 , relative to adduct A , i.e. 14.0 kcal•mol -1 relative to the energy reference), and corresponds to the step during which the Si-N bond is formed, leading to intermediate B (dSi-N = 2.181 Å and 2.019 Å for TSAB and B, respectively). Noteworthy for this intermediate B, the Si atom is found pentavalent and at the center of a trigonal bipyramid. The NBO analysis for this intermediate shows that its relative stability is essentially based on favorable donor-acceptor interactions, on the one hand between the N lone-pair and the three σ * Si-H antibonds (mainly with the σ * Si-H trans to N) and on the other hand between the three σSi-H and the vacant 3s orbital of Ca (see ESI § 5.3). It is also important to note that all attempts to optimize the structure of such a reaction intermediate, where Si is hypervalent, in the absence of Ca(NTf2) + catalyst, have been unsuccessful: the stability of this intermediate is a key-step of the process and can only be ensured with the electrophilic assistance of Ca. This intermediate B also has a characteristic 1 H NMR signature: calculations suggest an isotropic chemical shift δ for the H in alpha from the C functional of imine to 9.0 ppm and shifts for the 3 H bounded to the Si and in interactions with Ca, between 5.0 and 5.8 ppm (ESI § 5.4); these calculated values are Please do not adjust margins Please do not adjust margins consistent with the transiently experimentally observed values of chemical shift (see ESI Figure S3 p. S15). The second step corresponds to the transition from this intermediate B to the product C and is the kinetic determining step (ΔG ‡ = 26.1 kcal•mol -1 with respect to the reference energy). This step corresponds to a β-migration of one of the three H carried by the Si towards the imine C atom. An NBO analysis of the electronic structure of this TSBC transition state shows clearly that the transferred H has a strong hydride character (the corresponding NBO charge is -0.81e); this electrophilic nature allows to better understand the greater efficiency of the process for imines substituted by an electronwithdrawing group with respect to imines substituted by electron-donating groups (2h vs 2f, Fig. 2), which enable respectively the stabilisation/destabilisation of this transition state (see ESI § 5.3). The final step corresponds to the decoordination of the silylamine to the metal (adduct C), leading to the free Ca(NTf2) + complex and the reaction product without interactions. The proposed mechanism, consistent with the experimental observations previously presented, is in favor of a electrophilic Si-H activation pathway. Lastly and to illustrate the interest of the method for organic chemistry, the catalytic system reported here was applied to the synthesis of bioactive amine 2w on gram-scale through reductive amination and by optimizing the conditions (solvent, amount of metal and of silane, Scheme 3). Therefore, in this synthesis, equimolar amounts of 2-furfural, chemical obtained from biomass, 72 and 3,4-dichloroaniline (7 mmol) were allowed to react in 2-methyltetrahydrofuran, a renewable and more eco-friendly solvent. [START_REF] Bisz | 2-Methyltetrahydrofuran: A Green Solvent for Iron-Catalyzed Cross-Coupling Reactions[END_REF] After 6h, 5 mol% of the Ca catalyst and 1.2 equiv of silane were added and the mixture stirred for 24 h at 25 °C before achieving basic hydrolysis. [START_REF] Froidevaux | Biobased Amines: From Synthesis to Polymers; Present and Future[END_REF] H NMR of the crude confirmed the complete conversion of both reactants, the absence of intermediate imine and the quantitative formation of 2w. The latter was isolated in 85% yield after column chromatography, which is in the same order of magnitude than at 1 mmol scale from imine 1w (90%, Figure 1). It is worth noting that for this substrate, the amount of catalyst could be decreased from 10 to 5 mol% and the excess of silane from 2 to 1.2 equivalents, while keeping good performances. Under these conditions, more than 1.4 g of the expected amine could be obtained with high purity.

Conclusions

This method reports a simple and efficient method for imine hydrosilylation using a catalytic system based on non-toxic calcium, the fifth most frequent element in the Earth crust. The proposed catalyst is based on Ca(NTf2)2 and KPF6, which act in a synergistic manner. Both precursors are readily available and easy-to-handle salts that can be stored on the shelves, open on air and used for several months without loss of activity. This catalytic system is able to promote the hydrosilylation of a variety of aldimines under mild conditions (25-65 ° C, 6-16 h) without requiring an inert atmosphere, and shows tolerance to functional groups including halides (I, Br, F), trifluoromethyl, ketones, esters or nitriles. Expected amines are obtained in fair to excellent yields. The value of the method has been shown on the synthesis of a bioactive amine with antifungal properties, that was prepared in gram scale and high yield in environmentally friendly 2methyltetrahydrofuran. It was shown on this example that the imine can be generated in situ from the corresponding aldehyde and amine without isolating the imine, which is interesting from a practical point of view. Overall, due to the nature of the metal (calcium is non-toxic even in large amounts) and the mild reaction conditions, the reported methodology contributes to the search for sustainable syntheses of amines, highly important building blocks in many application fields. The resulting amines are obtained free from transition metal traces, which is of great interest in the field of pharmaceuticals for which the metal contaminants are strictly regulated. No tedious and costly purification is thus needed. In addition, experimental data and DFT calculations are in accordance with an electrophilic Si-H activation pathway by the Ca(NTf2) + catalyst shown to promote imine hydrosilylation for the first time. To the best of our knowledge, such an electrophilic activation of the Si-H bond, well-known for boron catalysts, is not common in alkaline earth chemistry where a Ae-hydride complex is generally generated from calcium precursors and silanes through -bond metathesis (Scheme 1, C). Ca(NTf2) + being shown to activate Si-H bonds for the first time, studies to enlarge the scope of this catalyst to other challenging hydrosilylation reactions are currently underway.

Figure 1 :

 1 Figure 1: Scope of the catalytic system (NMR yield a / isolated yield b )a. Typical procedure (NMR yields): Ca(NTf2)2 (0.025 mmol), KPF6 (0.025 mmol), PhSiH3 (0.5 mmol), THF (1 mL) were stirred at 25 °C for 10 minutes before adding aldimine 1x (0.25 mmol) and THF (0.5 mL). The reaction mixture was stirred at 25 ° C for 16 h and then hydrolysed with MeOH (1.5 mL) and NaOH (2M, 1.5 mL). Yield determined by NMR using 1,3,5-trimethoxybenzene as the standard. b. Typical procedure (isolated yields): Ca(NTf2)2 (0.1 mmol), KPF6 (0.1 mmol), PhSiH3 (2 mmol), THF (4 mL) were stirred at 25 °C for 10 minutes before adding the aldimine 1x (1 mmol) and THF (2 mL). The reaction mixture was stirred at 25 °C for 16 h and then hydrolysed with MeOH (6 mL) and NaOH (2M, 6 mL). c. 65 °C. d. Quantitative NMR yield after 6h. e. Formation of N,N-di(4bromobenzyl)benzylamine 3s (20% isolated yield, see ESI).

Scheme 2 :

 2 Scheme 2: Mechanism for the Ca-catalyzed hydrosilylation of imines proposed by analogy with B(C6F5)3

Figure 2 :

 2 Figure 2: Gibbs energy profile (kcal•mol -1 ) for the hydrosilation of 2b imine catalysed by Ca(NTf) +

Scheme 3 :

 3 Scheme 3: Application of the method for gram-scale synthesis of an amine with antifungal activity

Table 1 :

 1 Optimisation study for the reduction of imine 1a with calcium pre-catalysts

	Entry [Ca] (mol %)	Additive (mol %)	Eq PhSiH3	Yield 2a
					a,b
	1	Ca(NTf2)2 (20)	-	4	10
	2	Ca(NTf2)2 (20)	KPF6 (20)	4	99
	3	-	KPF6 (20)	4	0
	4	-	KNTf2 (20)	4	0
	5	Ca(NTf2)2 (10)	KPF6 (10)	4	99
	6	Ca(NTf2)2 (10)	KPF6 (10)	2	99 (86 c )
	7	Ca(NTf2)2 (

Acknowledgements

The authors thank CNRS, ENSCM and University of Montpellier for funding.

Author Contributions

Yougourthen Boumekla: Investigation, Methodology. Fengxie Xia: Investigation. Lucas Vidal: Investigation. Cédric Totee: Methodology. Christophe Raynaud: Methodology, Software, Formal analysis, Writing-Review and Editing. Armelle Ouali: Conceptualization, Methodology, Writing original draft, Review and Editing, Supervision.

Conflicts of interest

There are no conflicts to declare.

Notes and references


Zheming Wang
email: wangzheming@zjut.edu.cn

Raphaël M Jungers
email: raphael.jungers@uclouvain.be.

Mihály Petreczky
email: mihaly.petreczky@centralelille.fr

Bo Chen
email: bchen@zjut.edu.cn

Li Yu

Learning stability of partially observed switched linear systems

Keywords: Stability, switched systems, scenario approach, observability

This paper deals with learning stability of partially observed switched linear systems under arbitrary switching. Such systems are widely used to describe cyberphysical systems which arise by combining physical systems with digital components. In many real-world applications, the internal states cannot be observed directly. It is thus more realistic to conduct system analysis using the outputs of the system. Stability is one of the most frequent requirement for safety and robustness of cyberphysical systems. Existing methods for analyzing stability of switched linear systems often require the knowledge of the parameters and/or all the states of the underlying system. In this paper, we propose an algorithm for deciding stability of switched linear systems under arbitrary switching based purely on observed output data. The proposed algorithm essentially relies on an output-based Lyapunov stability framework and returns an estimate of the joint spectral radius (JSR). We also prove a probably approximately correct error bound on the quality of the estimate of the JSR from the perspective of statistical learning theory.

Introduction

Verification of safety and robustness of AI systems has gained significant attention in recent years [START_REF] Rudner | Key concepts in AI safety: Robustness and adversarial examples[END_REF][START_REF] Dietterich | Robust artificial intelligence and robust human organizations[END_REF][START_REF] Hamon | Robustness and explainability of artificial intelligence[END_REF]. This is particularly important in the context of application of machine learning algorithms [START_REF] Taylor | Learning for safety-critical control with control barrier functions[END_REF][START_REF] Boffi | Learning stability certificates from data[END_REF][START_REF] Chang | Stabilizing neural control using self-learned almost lyapunov critics[END_REF][START_REF] Giesl | Approximation of lyapunov functions from noisy data[END_REF]. Moreover,all these works require the knowledge of the full state and hybrid behaviors are not taken into consideration. Hence, these techniques are not suitable for the stability analysis of partially observed switched systems.

The contribution of this paper is threefold. First, we propose a stability learning approach for SLSs with only partial observation under observability assumptions. Second, we provide a PAC bound on the JSR with an explicit convergence rate, which allows to derive the sample complexity of the proposed learning approach. Third, we conduct a comparison with hybrid system identification techniques [START_REF] Paoletti | Identification of hybrid systems: A tutorial[END_REF][START_REF] Lauer | Hybrid system identification: Theory and algorithms for learning switching models[END_REF] using numerical examples. More precisely, by the numerical experiments in Section 5, we show that hybrid system identification techniques [START_REF] Paoletti | Identification of hybrid systems: A tutorial[END_REF][START_REF] Lauer | Hybrid system identification: Theory and algorithms for learning switching models[END_REF] not only are computationally expensive but also generate modelling errors which leads to false stability inference.

The rest of the paper is organized as follows. In Section 2, we present the formal problem formulation and some preliminary results on stability of SLSs. Section 3 is the main part of the paper, where we present the proposed output-based Lyapunov framework from the stability learning problem to probabilistic guarantees. In Section 4, we discuss some practical issues about the proposed analysis. In Section 5, we provide numerical simulations and comparison with hybrid system identification techniques.

Notation. We denote by R + and Z + the set of all non-negative real numbers and the set of all non-negative integers respectively. For a square matrix Q, Q ( )0 means Q is positive definite (semi-definite). For a symmetric Q 0, let κ(Q) := λ max (Q)/λ min (Q). Consider the set M := {1, 2, • • • , M } for some given integer M ∈ Z + , M k denotes the k-Cartesian product of M for any k ∈ Z k . Let σ σ σ = (σ 0 , σ 1 , • • • , σ k-1 ) be an element of M k . For any a, b ∈ Z + with b ≥ a, we denote the segment (σ a , • • • , σ b ) by σ σ σ a:b . For consistence, let σ σ σ a:b = ∅ when a > b. For any p ≥ 1, the p-norm of a vector/matrix x is x p ( x is the 2-norm by default), and let x F denote the Frobenius norm.

Problem statement and preliminaries

Switched linear systems Below we will define the notion of switched linear systems and recall some basic properties of such systems. These properties will allow us to relate stability of the system with the observed behavior.

A discrete-time switched linear system (SLS) is a dynamical system with output of the form x(t + 1) = A σ(t) x(t), y(t) = C σ(t) x(t), t ∈ Z +

where x(t) ∈ R n is the state vector, y(t) ∈ R p is the output and σ : Z + → M := {1, 2, • • • , M } is a time-dependent switching signal that indicates the current active mode of the system among M possible modes in {A 1 , A 2 , • • • , A M }. We will use the tuple Σ = (n, {(A i , C i ) : i ∈ M}) to denote the switched linear system above. Intuitively, a SLS is just a collection of linear dynamical systems defined on the same statespace. During the evolution of the SLS, one switches from one linear system to another according to the switching signal. For more details on switched systems see [START_REF] Bertsekas | Convex analysis and optimization[END_REF][START_REF] Sun | Switched linear systems : control and design[END_REF].

Informaly, we would like to decide stability of (1) based on a finite number of observed output data points. In order to state the problem formally, first we will define below what we mean by stability. Then, we will explain our assumption on the data collection mechanism. Stability Let us recall some basic stability results on discrete-time SLSs. We begin with the formal definition of asymptotic stability below.

Definition 1 (Asymptotic stability) The discrete-time SLS (1) is asymptotically stable if for any initial state x(0) ∈ R n and switching signal σ : Z + → M, lim t→+∞ x(t) = 0.

To characterize this asymptotic stability property, we recall the concept of the joint spectral radius (JSR) [START_REF] Jungers | The joint spectral radius: theory and applications[END_REF] of a SLS Σ:

ρ(Σ) := lim k→∞ max σ σ σ∈M k A σ σ σ 1/k . (2)
It is well known that the SLS Σ is asymptotically stable under arbitrary switching if and only if ρ(Σ) < 1, see, e.g., [START_REF] Jungers | The joint spectral radius: theory and applications[END_REF]. In general, computing the exact value of the JSR ρ(Σ) is a difficult problem. Hence, in practice, we approximate ρ(Σ) by computing lower and upper bounds within a Lyapunov framework, where the template of the Lyapunov function V : R n × M k → R is specified for some k ∈ Z + . More precisely, given a Lyapunov function V above, such that for any sequence (i 1 , . . . , i k ) ∈ M k , we solve the following Lyapunov inequality for some choice of integers T > 0:

V (A i1 • • • A i T -k x, (i T -k+1 • • • i T )) ≤ (3)
γ 2(T -k) V (x, i 1 , • • • , i k ), ∀(i 1 , . . . , i T )) ∈ M k , ∀x ∈ R n
where γ ∈ R + and V is parameterized by some variables. We refer the reader to [START_REF] Jungers | The joint spectral radius: theory and applications[END_REF] for some popular Lyapounov templates. In this paper, we consider quadratic Lyapunov functions in the form of

V (x, i 1 , • • • , i k ) = x T P (i1,••• ,i k )
x for some positive definite matrix

P (i1,••• ,i k ) 0.
Data collection We randomly generate multiple trajectories of (1) where the initial state x 0 is uniform and i.i.d. in the unit sphere S n-1 and the switching signal σ t is uniform and i.i.d. in M for any t ∈ Z + . Suppose we generate N ∈ Z + trajectories of length T ∈ Z + , the sample is denoted as

ω N := {(x i 0 , σ σ σ i ) : i = 1, 2, • • • , N }. ( 4
)
where

σ σ σ i = (σ i 0 , σ i 1 , • • • , σ i T -1 ) ∈ M T .
For each sampling pair, we measure the output trajectory data

y i t = C σ i t x i t , x i t+1 = A σ i t x i t , 0 ≤ t ≤ T -1, ∀i (5)
where the subscript t denotes the time instant and the superscript i denotes each trajectory. The whole observed data set is denoted by

D obs := {y i t : 0 ≤ t ≤ T -1, i = 1, 2, • • • , N }. (6)
Formal problem formulation Suppose System (1) is not known, but the observations D obs are available and they correspond to the random sample ω N in (4). Find an estimate γ * (ω N ) of the JSR ρ(Σ). Note that we do not require the information on the switching signal.

Learning stability from output data

In this section, we present a data-driven stability analysis approach for SLSs with partial observation. We start with the procedure to estimate the JSR of a SLS in the form of (1). We then present the probabilistic guarantees which describe the quality of that estimate.

Estimating JSR from data

We propose to estimate the JSR and the corresponding Lyapunov function by solving an optimization problem based on observed data. In order to state the optimization problem, for each trajectory, given the observed data set D obs and some k ∈ Z + , let us define the following time-series data

v i k =      y i 0 y i 1 . . . y i k-1      , z i k =      y i T -k y i T -k+1
. . .

y i T -1      , ∀i. (7)
For notational convenience, let the time-series data set be denoted by, ∀k ≤ T -1,

D k := {(v i k , z i k ) : i = 1, 2, • • • , N }. (8)
Given the data set D k for a sufficiently large k ∈ Z + , we estimate the JSR by solving the following scenario (or sampled-based) program min γ≥0,P (γ, P F ) (9a)

s.t. z P z ≤ γ 2(T -k) v P v, ∀(v, z) ∈ D k , (9b)
I P λI. ( 9c
)
where the minimization is implemented in the lexicographic order1 of the components of the objective function. Let the solution be denoted by (γ * k (ω N ), P * k (ω N )) and and suppose that it is unique. The quantity γ * k (ω N ) will be our estimate of the JSR of the unknown system (1). If γ * k (ω N ) is sufficiently smaller than 1, then we can conclude that the underlying system is stable, at least with high probability. Computational complexity By fixing γ, the constraint (9b) is linear, so that the optimization problem (9) can be solved efficiently using SDP solvers [START_REF] Boyd | Convex Optimization[END_REF] and bisection on γ. The computational complexity of solving it is polynomial in the number of data points ( note that we do not need to know the number of modes). In particular, solving ( 9) is expected to be much less computationally expensive than identifying the underlying SLS, which essentially has a complexity growing exponentially with the number of modes. This is supported by numerical results, see Table 1 in Section 5. Intuition Intuitively, the solution of ( 9) results in a Lypaunov function V (x, (i 1 , • • • , i k )) which can be rewritten as a quadratic function of the outputs and which satisfies (3) with γ ≤ γ * k (ω N ). More precisely, given any k ∈ Z + , consider a switching sequence

σ σ σ = (σ 0 , σ 1 , • • • , σ T -1 ) ∈ M T .
For any initial state x of (1) and any integer k, ∈ Z + with k + ≤ T , define

Y σ σ σ,x, ,k =      y( ) y( + 1)
. . .

y( + k -1)      (10)
where (y(0), • • • y(T -1)) is the output generated by (1) for the switching signal σ(i) = σ i , i = 0, . . . , T -1 and initial state x(0) = x. We consider quadratic Lyapunov functions of the output trajectory which can be expressed as

V (x, σ σ σ) = Y σ σ σ,x,0,k P Y σ σ σ,x,0,k (11)
where P ∈ R kp×kp is a positive definite matrix. It then follows that if V satisfies (3), then the constant γ is an upper bound on the JSR of (1) when k and T satisfy certain conditions, as we will see in Theorem 1. In turn, V satisfies (3), if it satisfies the following inequality: for every

σ σ σ ∈ M T Y σ σ σ,x,T -k,k P Y σ σ σ,x,T -k,k ≤ γ 2(T -k) Y σ σ σ,x,0,k P Y σ σ σ,x,0,k (12)
for every initial state x. Since any output sequence (y(0), y(1), • • • , y(T -1)) arises as Y σ σ σ,x,0,T for some initial state x and switching σ σ σ ∈ M T , it follows that ( 12) is equivalent to requiring that

     y(T -k) y(T -k + 1)
. . .

y(T -1)      P      y(T -k) y(T -k + 1)
. . .

y(T -1)      ≤γ 2(T -k)      y(0) y(1) . . . y(k -1)      P      y(0) y(1) . . . y(k -1)      (13)
holds for any output sequence (y(0), y(1),

The scenario program (9) can be in fact considered as a sampled version of the robust optimization problem [START_REF] Paoletti | Identification of hybrid systems: A tutorial[END_REF].

Pathwise observability

Since our goal is to learn stability from the output trajectory, first we need to recall some technical concepts on observability of switched systems. By incorporating these concepts into Lyapunov stability analysis, we present new results that are needed for developing formal probabilistic stability guarantees in the sequel.

Definition 2 A switching sequence σ σ σ ∈ M k is said to be observable for (1), if the following implication holds:

Y σ σ σ,x,0,k = 0 =⇒ x = 0,
where Y σ σ σ,x,0,k is as in [START_REF] Sontag | Mathematical Control Theory[END_REF]. The smallest k ∈ Z + such that there exists an observable switching sequence σ σ σ ∈ M k is called the observability index of Σ, denoted by h(Σ).

Intuitively, a switching signal is observable, then the state of the system can be reconstructed from the observed outputs. When a SLS Σ has no observable switching signal, we let h(Σ) = ∞.

We also recall a stronger observability condition from [START_REF] Babaali | Pathwise observability and controllability are decidable[END_REF], called pathwise observable.

Definition 3

The SLS (1) is said pathwise observable if there exists k ∈ Z + such that every switching signal σ σ σ ∈ M k is observable. We refer to the smallest such integer k as the pathwise observability index, denoted by H(Σ).

Intuitively, pathwise observability means that the state of the system can be reconstructed from the observed outputs, for any choice of the switching signal. When an SLS Σ is not pathwise observable, we say that H(Σ) = ∞. Let us also point out that, the condition of pathwise observable is decidable as shown in [START_REF] Babaali | Pathwise observability and controllability are decidable[END_REF][START_REF] Jungers | Observability and controllability analysis of linear systems subject to data losses[END_REF] by providing explicit upper bounds on H(Σ).

For any a, b ∈ Z + , let us also define

A σ σ σ a:b := A σ b • • • A σa . By convention, when a > b, let A σ σ σ a:b = I. Following [49], for any σ σ σ = (σ 0 , σ 1 , • • • , σ k-1 ) ∈ M k of length k ∈ Z + , we define the path-dependent observability matrix O Σ (σ σ σ) :=      C σ0 C σ1 A σ0 . . . C σ k-1 A σ k-2 • • • A σ1 A σ0      . ( 15
)
Remark 1 Using the definition of path-dependent observability matrices, a switching sequence

σ σ σ ∈ M k for some k ∈ Z + is said to be observable if rank (O Σ (σ σ σ)) = n. Following this, we say that a SLS Σ = (n, {(A i , C i ) : i ∈ M}) is pathwise observable if there exists k ∈ Z + such that rank (O Σ (σ σ σ)) = n for any σ σ σ ∈ M k .
Note that the output trajectory can be rewritten as Y σ σ σ,x,0,k = O Σ (σ σ σ)x, the quadratic Lyapunov function in [START_REF] Hirsch | Differential equations, dynamical systems, and an introduction to chaos[END_REF] can be rewritten as

V (x, σ σ σ) = x O Σ (σ σ σ) P O Σ (σ σ σ)x.
For notational convenience, we then define the following matrices based on the switching sequence

P σ σ σ Σ (P, , k) = O Σ (σ σ σ :k+ -1 ) P O Σ (σ σ σ :k+ -1 ). ( 16
)
With the definitions above, we obtain a Lyapunov stability result for SLSs.

Theorem 1 Consider an SLS, denoted by Σ = (n, {(A i , C i ) : i ∈ M}), suppose that Σ admits at least one observable switching signal, and denote h(Σ) the observability index as in Definition 2.

Assume that there exist k ∈ Z + , ∈ Z + , γ ≥ 0 and P 0 such that k ≥ h(Σ), and for any σ σ σ ∈ M k+ ,

A σ σ σ 0: -1 P σ σ σ Σ (P, , k)A σ σ σ 0: -1 γ 2 P σ σ σ Σ (P, 0, k), (17)
where P σ σ σ Σ (P, 0, k) and P σ σ σ Σ (P, , k) are given as in [START_REF] Vidal | Recursive identification of switched ARX systems[END_REF]. Then, ρ(Σ) ≤ γ. Proof: For any q ∈ Z + and σ σ σ ∈ M q +k , from [START_REF] Bako | Analysis of the least sum-of-minimums estimator for switched systems[END_REF], it holds that A σ σ σ (q-1) :q -1 P σ σ σ Σ (P, q , k)A σ σ σ (q-1) :q -1 γ 2 P σ σ σ Σ (P, (q -1) , k). This implies that A σ σ σ 0:q -1 P σ σ σ Σ (P, q , k)A σ σ σ 0:q -1 γ 2 A σ σ σ 0:(q-1) -1 P σ σ σ Σ (P, (q -1) , k)A σ σ σ 0:(q-1) -1 . . .

γ 2q P σ σ σ Σ (P, 0, k), ∀σ σ σ ∈ M q +k , q ∈ Z + . ( 18
) Since k ≥ h(Σ), there exists σ σ σ ∈ M k such that rank (O Σ (σ σ σ)) = n from Definition 2. Thus, there exist c ≥ c > 0 such that O Σ (σ σ σ) O Σ (σ σ σ) cI and O Σ (σ σ σ) O Σ (σ σ σ) cI for any σ σ σ ∈ M k .
With this, we have that, for any σ σ σ ∈ M q +k with σ σ σ q :k+q -1 = σ σ σ, A σ σ σ 0:q -1 P σ σ σ Σ (P, q , k)A σ σ σ 0:q -1 λ min (P )cA σ σ σ 0:q -1 A σ σ σ 0:q -1 , P σ σ σ Σ (P, 0, k) cλ max (P )I. The two inequalities above, together with [START_REF] Massucci | A statistical learning perspective on switched linear system identification[END_REF], imply that λ min (P )cA σ σ σ 0:q -1 A σ σ σ 0:q -1 γ 2q cλ max (P )I which means that

A σ σ σ ≤ γ q κ(P ) c c , ∀σ σ σ ∈ M q (19)
Hence,

ρ(Σ) = lim q→∞ max σ σ σ∈M ql A σ σ σ 1 ql ≤ γ lim q→∞ κ(P ) c c 1 2ql = γ.
The stability result in Theorem 1 serves as a basis for the rest of the paper. Observe that the constraint [START_REF] Bako | Analysis of the least sum-of-minimums estimator for switched systems[END_REF] is not amenable as it is for a data-driven approach, as it explicitly uses the system matrices. In order to leverage it in a data-driven framework, we now provide an interpretation of this stability condition from the perspective of robust optimization. Suppose the overall length of the output trajectory is T . For any k ∈ Z + , we formulate the following robust optimization problem

(γ o k ,P o k ) := arg min γ≥0,P I (γ, P F ) (20a) s.t. x A σ σ σ 0: -1 P σ σ σ Σ (P, T -k, k)A σ σ σ 0: -1 x (20b) ≤ γ 2(T -k) x P σ σ σ Σ (P, 0, k)x, ∀(x, σ σ σ) ∈ S n-1 × M T where P σ σ σ
Σ (P, 0, k) and P σ σ σ Σ (P, , k) are given as in [START_REF] Vidal | Recursive identification of switched ARX systems[END_REF]. By homogeneity, (20b) is equivalent to [START_REF] Bako | Analysis of the least sum-of-minimums estimator for switched systems[END_REF]. From this robust optimization formulation, the stability condition in Theorem 1 means that for any initial state x(0) the aggregated quadratic Lyapunov function in [START_REF] Hirsch | Differential equations, dynamical systems, and an introduction to chaos[END_REF] is decreasing at a rate of γ. The problem [START_REF] Van Wingerden | Subspace identification of Bilinear and LPV systems for open-and closed-loop data[END_REF] can be also seen as a reformulation of [START_REF] Paoletti | Identification of hybrid systems: A tutorial[END_REF] If all the dynamics matrices are nonsingular, Theorem 1 in fact implies the pathwise observability property, as stated in the following corollary.

Corollary 1 Suppose the conditions in Theorem 1 hold. Suppose the matrices {A i } i∈M , ≥ k, and γ > 0, the stability condition (17) also implies that rank (O Σ (σ σ σ)) = n for any σ σ σ ∈ M k .

Proof: Since ≥ k, there is no overlapping between σ σ σ 0:k-1 and σ σ σ l:k+l-1 . Again, let σ σ σ ∈ M k be such that rank (O Σ (σ σ σ)) = n. With the fact that A i is invertible for any i ∈ M (as Σ is reversible), the condition [START_REF] Bako | Analysis of the least sum-of-minimums estimator for switched systems[END_REF] implies that, for any σ σ σ ∈ M k+ with σ σ σ l:k+l-1 = σ σ σ,

P σ σ σ Σ (P, 0, k) γ -2 A σ σ σ 0: -1 P σ σ σ Σ (P, , k)A σ σ σ 0: -1 0. ( 21
)
This means that O Σ (σ σ σ) is full-column rank for any σ σ σ ∈ M k .

Remark 2 From Corollary 1, we can see that pathwise observability is not a conservative condition in our output-based Lyapunov framework in which the switching signal is not available.

Almost Lyapunov stability

Before we prove our main result, we introduce the concept of almost Lyapunov stability which allows to describe the stability with unseen regions in the state space. More precisely, we aim to derive formal guarantees on the JSR from an almost stability condition in which the aggregated Lyapunov functions based on the matrices as defined in ( 16) are non-increasing everywhere except on a small subset whose measure is bounded by ε ∈ (0, 1).

To formally state the stability result with an almost Lyapunov function, the following definition is also needed. Given any ε ∈ (0, 1), let

δ(ε) := 1 -I -1 (2ε; n-1 2 , 1 2 ) ε ∈ [0, 1 2 ) 0 ε ≥ 1 2 (22)
where I(x; a, b) the regularized incomplete beta function defined as

I(x; a, b) := x 0 t a-1 (1 -t) b-1 dt 1 0 t a-1 (1 -t) b-1 dt . ( 23
)
A geometric interpretation of the function δ(•) is given in Figure 1. With this definition, we derive the following stability result under the Lyapunov condition (17) with a violating subset.

0 ε δ(ε)
Theorem 2 Consider a pathwise observable SLS Σ as in [START_REF] Rudner | Key concepts in AI safety: Robustness and adversarial examples[END_REF].Suppose there exist k ∈ Z + , ∈ Z + , γ ≥ 0, P 0 and a subset S ⊆ S n-1 such that, k ≥ H(Σ), and for any σ σ σ ∈ M k+ ,

x A σ σ σ 0: -1 P σ σ σ Σ (P, , k)A σ σ σ 0: -1 x ≤γ 2 x P σ σ σ Σ (P, 0, k)x, ∀x ∈ S n-1 \ S. ( 24
)
where P σ σ σ Σ (P, 0, k) and P σ σ σ Σ (P, , k) are given as in [START_REF] Vidal | Recursive identification of switched ARX systems[END_REF]. Then,

ρ(Σ) ≤ γ δ µ(S)χΣ(P,k) 2 (25)
where µ(•) is the uniform probability measure on the unit sphere S n-1 , δ(•) is defined in [START_REF] Jungers | The joint spectral radius: theory and applications[END_REF] and

χ Σ (P, k) := max σ σ σ∈M k det(P σ σ σ Σ (P, 0, k)) λ min (P σ σ σ Σ (P, 0, k)) n . ( 26
)
The proof of Theorem 2 is given in the appendix. From the definition of χ Σ (P, k) in ( 26), pathwise observability is crucial for the stability result in Theorem 2 in the sense that it guarantees the boundedness of χ Σ (P, k). From Theorem 2, more explicit stability guarantees can be also derived, as shown in the following corollary.

Corollary 2 Given the same conditions as in Theorem 2, it holds that χ Σ (P, k) ≤ (c k κ(P )) n-1 and

ρ(Σ) ≤ γ δ µ(S) √ (c k κ(P )) n-1 2 , ( 27
)
where

κ(P ) = λ max (P ) λ min (P ) and c k := max σ σ σ∈M k κ(O Σ (σ σ σ) O Σ (σ σ σ))
Moreover, when I P λI for some λ ≥ 1,

ρ(Σ) ≤ γ δ µ(S) √ (c k λ) n-1 2 . ( 28
)
Proof: By definition, since Σ is pathwise observable with H(Σ) ≤ k, there exists r > 0 such that rI O Σ (σ σ σ) O Σ (σ σ σ) rc k I for any σ σ σ ∈ M k , which leads to the following inequalities:

λ max (P σ σ σ Σ (P, 0, k)) ≤ λ max (O Σ (σ σ σ) O Σ (σ σ σ))λ max (P ) ≤ rc k λ max (P ), λ min (P σ σ σ Σ (P, 0, k)) ≥ λ min (O Σ (σ σ σ) O Σ (σ σ σ))λ min (P ) ≥ rλ min (P ).
Using these inequalities, we arrive at

det(P σ σ σ Σ (P, 0, k)) λ min (P σ σ σ Σ (P, 0, k)) n ≤ λ max (P σ σ σ Σ (P, 0, k)) n-1 λ min (P σ σ σ Σ (P, 0, k)) n-1 ≤ (c k κ(P )) n-1 , ∀σ σ σ ∈ M k .
Hence, it holds that χ Σ (P, k) ≤ (c k κ(P )) n-1 . Putting this inequality into [START_REF] Kenanian | Data driven stability analysis of black-box switched linear systems[END_REF], we obtain [START_REF] Rubbens | Data-driven stability analysis of switched linear systems with sum of squares guarantees[END_REF].

Note that the function δ(•) is decreasing. When κ(P ) ≤ λ, ( 27) implies [START_REF] Wang | A data-driven method for computing polyhedral invariant sets of black-box switched linear systems[END_REF]. With the results above, we are able to extend the technique in [START_REF] Kenanian | Data driven stability analysis of black-box switched linear systems[END_REF] which only considers the fully observed case to the partially observed case.

Main result: Probabilistic stability certificates

In the rest of this section, we formally present our main result, that is, stability certificates based on the solution of the scenario program (9) in a probabilistic sense.

Our derivation relies on the scenario approach (also known as scenario optimization) [START_REF] Calafiore | Uncertain convex programs: randomized solutions and confidence levels[END_REF][START_REF] Calafiore | The scenario approach to robust control design[END_REF][START_REF] Calafiore | Random convex programs[END_REF]. In order to use [START_REF] Calafiore | Random convex programs[END_REF], we need to fulfill a non-degeneracy assumption, formalized below. Definition 4 For the SLS (1) and k, T ∈ Z + , a switching sequence σ σ σ ∈ M T is degenerate if there exist P 0 and γ ≥ 0 such that for any initial state x,

Y σ σ σ,x,T -k,k P Y σ σ σ,x,T -k,k = γ 2(T -k) Y σ σ σ,x,0,k P Y σ σ σ,x,0,k
where Y σ σ σ,x,0,k , Y σ σ σ,x,T -k,k are as in [START_REF] Sontag | Mathematical Control Theory[END_REF].

With the discussions and definitions above, we are now ready to present the main result of this section.

Theorem 3 (Main result) Consider the SLS Σ as given in [START_REF] Rudner | Key concepts in AI safety: Robustness and adversarial examples[END_REF], where the initial state is i.i.d with the uniform distribution over the unit sphere S n-1 and the switching signal is uniform and i.i.d. in M. Given N, T ∈ Z + , the sample set ω N as defined in (4), and

k ≤ T -1, let (γ * k (ω N ), P * k (ω N ))
be the unique solution of the scenario program [START_REF] Sun | Switched linear systems : control and design[END_REF]. Assume that Σ is pathwise observable with H(Σ) ≤ k and that none of the switching sequences in M T is degenerate in the sense of Definition 4. For any ∈ (0, 1), with probability no smaller than 1 -φ( ; d, N ),

ρ(Σ) ≤ γ * (ω N ) T -k δ M T χΣ(P * (ω N ),k) 2 (29)
where d = kp(kp+1)

2

, and χ Σ (•, k) is given in [START_REF] Berger | Chance-constrained quasi-convex optimization with application to data-driven switched systems control[END_REF], δ(•) is defined as in [START_REF] Jungers | The joint spectral radius: theory and applications[END_REF], and

φ( ; d, N ) := 1 -I( ; d, N -d + 1). ( 30
)
The proof of Theorem 3 is presented in the appendix. Let us emphasize that the assumption that none of the sequences is degenerate in Theorem 3 is not conservative in practice. In fact, this assumption is a particular case of Assumption 2 in [START_REF] Calafiore | Random convex programs[END_REF], see Section 3.4 in [START_REF] Calafiore | Random convex programs[END_REF] for discussions on relaxing such an assumption. In the fully observed case, this assumption actually means that none of the matrices {A i } M i=1 is similar to a Barabanov matrix, which is diagonalizable with all the eigenvalues having the same modulus, see [START_REF] Berger | Chance-constrained quasi-convex optimization with application to data-driven switched systems control[END_REF]. Let us also point out that the function χ Σ (•, k) as defined in [START_REF] Berger | Chance-constrained quasi-convex optimization with application to data-driven switched systems control[END_REF] implicitly depends on the parameters of the underlying system Σ. In Subsection 4.3 we present an algorithm for estimating χ Σ (•, k).

The error bound of Theorem 3 implies that the true JSR is smaller than the sample-based solution γ * (ω N ) multiplied with the correction factor

1 T -k δ M T χΣ(P * (ω N ),k) 2 with a high probability 1 -φ( ; d, N ). The probability 1 -φ( ; d, N ) converges to 1 as N → ∞.
That is, the more data points we have, the more certain we are that (29) holds. The factor depends on the accuracy level , and it tends to 1 as → 0. We will explicitly discuss the convergence rate in Section 4.1.

The correction factor above is a posteriori, in the sense that its numerical value depends on the outcome of the scenario program [START_REF] Sun | Switched linear systems : control and design[END_REF]. For this reason it may be difficult to evaluate the quality of this factor. Below we present a modified error bound where the factor with which γ * (ω N ) is multiplied does not depend on data. This then allows to bound that factor using prior knowledge on the set of possible models. This is done by exploiting the constraint I P λI in [START_REF] Sun | Switched linear systems : control and design[END_REF].

Corollary 3 Suppose that the conditions in Theorem 3 hold. There exists a constant c ≥ 1, for any β ∈ (0, 1), with probability no smaller than 1 -β,

ρ(Σ) ≤ γ * k (ω N ) T -k δ M T √ (c λ) n-1 2 (31)
with = I -1 (1 -β; d, N -d + 1
) and d = kp(kp+1)

2

.

Proof: This is a direct consequence of Theorem 3 and Corollary 2 with c = c k . The constant c in (31) depends on the underlying system as shown in Corollary 2. Corollary 3 enables us to know a priori how much data is needed to reach certain accuracy and confidence level. That is, given a fixed confidence level β and a fixed , we are able to compute N such that (31) holds with probability 1 -β. Note that this requires the knowledge of the constant c, which depends on the matrices of the underlying system. Suppose that the underlying unknown system comes from a certain family of SLSs, we can choose c to be an upper bound on the constant max σ σ σ∈M k κ(O Σ (σ σ σ) O Σ (σ σ σ)) of each Σ where Σ varies through all possible SLSs. The constant c can be hence considered as a counterpart of VC dimensions in PAC-style error bounds [START_REF] Vapnik | The nature of statistical learning theory[END_REF], and it captures the complexity of the model class. Alternatively, c could also be estimated from data with high probability, as we will see in Theorem 4 in Section 4.

Remark 3

In fact, our analysis in Section 3.4 can be extended to the case when the initial state is not uniformly distributed, but its distribution P satisfies the following regularity condition: There exists an increasing function ν : [0, 1] → [0, 1] such that, for any S ⊆ S n-1 , P{x : x/ x ∈ S} ≥ ν(µ(S)), where µ(•) is the uniform probability measure on the unit sphere S n-1 . This condition is satisfied for example for Gaussian distributions. Under this condition, the inequality in (29) becomes

ρ(Σ) ≤ γ * (ω N ) T -k δ ν -1 ( M T )χΣ(P * (ω N ),k) 2 . ( 32
)
Remark 4 The proposed approach can be also extended to disturbed systems with bounded additive disturbances in the form of

x(t + 1) = A σ(t) x(t) + w(t), y(t) = C σ(t) x(t) + v(t) (33)
where w(t) and v(t) are bounded. Similar probabilistic guarantees can be derived with a-priori information on the bounds of the disturbances.

Technical issues

In this section, we discuss some technical issues of the proposed data-driven stability analysis approach.

Sample complexity

We first provide some insights into the relation between the size of the sample and the precision of the solution of the scenario program (9) from the perspective of PAC learning [START_REF] Shalev-Shwartz | Understanding machine learning: From theory to algorithms[END_REF]. Let us formally define the sample complexity of the scenario program (9) below.

Definition 5 (Sample complexity) Given β ∈ (0, 1), ε ≥ 0 and any integer k ≥ H(Σ) , the sample complexity of the scenario program (9), denoted by N s (ε, β), is the minimal N ∈ Z + such that

P N {ω N : γ o k ≤ (1 + ε)γ * k (ω N )} ≥ 1 -β, (34)
where γ o k is given in [START_REF] Paoletti | Identification of hybrid systems: A tutorial[END_REF].

In the following proposition, we present some results on the sample complexity for the proposed data-driven approach.

Proposition 1 Suppose the conditions in Theorem 3 hold. For any β ∈ (0, 1) and ε ≥ 0, let the sample complexity N s (ε, β) be defined as in Definition 5. Then, the following results hold: (i) There exists a constant c ≥ 1 such that

N s (ε, β) ≤ N φ ( I(1 - 1 (1+ε) 2(T -k) ; n-1 2 , 1 2 ) M T χ(Q) (c λ) n-1 , β) (35) = O 1 β ( 1 ε ) n 2 . ( 36
)
where N φ ( , β) denotes the minimal N ∈ Z + satisfying φ( ; d, N ) ≤ β for any ∈ (0, 1).

(ii) When the system Σ is not asymptotically stable under arbitrary switching, i.e., ρ(Σ) > 1, for any N ≥ N s (ε, β),

P N {ω N : γ * (ω N ) < 1 1 + ε } ≤ β. ( 37
)
The proof is given in the appendix. From Proposition 1, the sample complexity is polynomial in 1/ε and 1/β, which implies PAC learnability in the sense of Valiant's definition in [START_REF] Valiant | A theory of the learnable[END_REF]. In addition, Property (ii) of Proposition 1 provides a measure of the risk of stability learning using the proposed data-driven approach.

Remark 5 Using tighter explicit bounds of φ( ; d, N ) in [START_REF] Calafiore | Random convex programs[END_REF][START_REF] Alamo | Randomized methods for design of uncertain systems: Sample complexity and sequential algorithms[END_REF], it can be even shown that

N s (ε, β) = O ln( 1 β )( 1 ε ) n 2
.

Alternatively, we can also define sample complexity based on the absolute error, i.e., the minimal N ∈ Z + such that

P N {ω N : γ o ≤ γ * (ω N ) + ε} ≥ 1 -β. ( 38
)
The analysis above can be adapted to this alternative definition. To avoid repetition, we do not intend to provide the details.

Pathwise observability index estimation

The results in the previous section all rely on the condition that k ≥ H(Σ). However, the exact value of H(Σ) is often unavailable. Though explicit bounds on H(Σ) exist in [START_REF] Babaali | Pathwise observability and controllability are decidable[END_REF], they are only useful for small values of n and M . We now show an efficient procedure to estimate H(Σ). Let us define, ∀k ≥ 1,

ξ o k := inf ξ≥0 ξ (39a) s.t. Y σ σ σ,x,k,k Y σ σ σ,x,k,k ≤ ξ 2k Y σ σ σ,x,0,k Y σ σ σ,x,0,k , ∀(x, σ σ σ) ∈ S n-1 × M 2k (39b)
where Y σ σ σ,x,k,k and Y σ σ σ,x,0,k are given in [START_REF] Sontag | Mathematical Control Theory[END_REF]. The following proposition shows an important property of the sequence {ξ o k } k≥1 .

Proposition 2 Suppose the SLS Σ is pathwise observable. Let {ξ o k } k≥1 be defined as in [START_REF] Chang | Neural lyapunov control[END_REF].

Then, ξ o k < ∞ if and only if k ≥ H(Σ).
Given a sample set ω N with a sufficiently long horizon T and the observed trajectories

{y i t : 0 ≤ t ≤ T -1, 1 ≤ i ≤ N }, empirical estimates of {ξ o k : 1 ≤ k ≤ T 2 } are given as ξ k (ω N ) := max 1≤i≤N ṽi k v i k , (40)
where v i k is given in [START_REF] Goebel | Hybrid Dynamical Systems: Modeling, Stability, and Robustness[END_REF] and

ṽi k = (y i k ) (y i k+1 ) • • • (y i 2k-1 ) . ( 41
)
With these estimates, we then consider the minimal k such that ξ k (ω N ) is less than some userdefined threshold. This will be illustrated by a numerical example in the next section.

Explicit bounds

The probabilistic bound in Theorem 3 implicitly depends on the system matrices which are not available. In this section, we show that explicit bounds can also be derived by estimating χ Σ (•, k).

Given any k ≥ H(Σ) and a sample set ω N with the corresponding measurements {y i t :

t = 0, 1, • • • , T -1, i = 1, 2, • • • , N }, let ζ k (ω N ) := max 1≤i≤N v i k , ζ k (ω N ) := min 1≤i≤N v i k , (42)
where v i k is defined in [START_REF] Goebel | Hybrid Dynamical Systems: Modeling, Stability, and Robustness[END_REF]. For any ε ∈ (0, 1) and ε ∈ (0, 1), let us define

ψ ε,ε (ω N ) := 1 δ( εM k 2 ) ζ k (ω N ) ζ k (ω N ) -2 -2δ( ε M k 2 ) . ( 43
)
This allows to estimate χ Σ (•, k) in Theorem 3, which leads to an explicit probabilistic upper bound on ρ(Σ), as stated in the following theorem.

Theorem 4 Consider the same conditions as in Theorem 3. For any ¯ , ε, ε ∈ (0, 1), with probability no smaller than

1 -φ(¯ ; d, N ) -(1 -ε) N -(1 -ε ) N , ρ(Σ) ≤ γ * (ω N ) T -k δ ¯ M T (ψ ε,ε (ω N )) n-1 √ (P * (ω N )) n-1 2 (44)
where ψ ε,ε (ω N ) is given in [START_REF] Dawson | Learning certified control using contraction metric: A survey of neural lyapunov, barrier, and contraction methods[END_REF].

Remark 6 (Checking stability) We are now ready to continue our discussion on checking stability. As it was mentioned in Section 3.1, the main idea is to solve (9) and then to check if γ * k (ω N ) is sufficiently smaller than 1. If we want to make this idea reliable, we can proceed as follows. One option is to choose the confidence level β and check if the right-hand side of (31) is smaller than

1, i.e., if γ * k (ω N ) ≤ T -k δ M T √ (c λ) n-1 2
. We can then conclude that the underlying system is stable, with probability 1 -β over the data. The drawback of this approach that we need to estimate c, for which we need some a-priori knoweldge on the underlying system. Another option is to use Theorem 4: we choose , such that

β = φ(¯ ; d, N ) -(1 -ε) N -(1 -ε ) N and then we check if γ * k (ω N ) ≤ T -k δ ¯ M T (ψ ε,ε (ω N )) n-1 √ (P * (ω N )) n-1 2
. If the latter is the case, then the underlying system is stable with probability 1 -β over the sampled data. Note that P * (ω N ) is computed at the same time as γ * k (ω N ), when (9) is solved.

Numerical examples

In this section, we illustrate the performance of the proposed approach on numerical examples.

To show the advantages of our approach, we make a comparison with the identification-based approach in which we identify the model using hybrid system identification techniques and analyze the stability based on the model. Our codes are available via https://github.com/zhemingwang/ DataDrivenStabilityAnalysis, and all experiments are run on a MacBook Pro with an Intel Core i7 and 16 GB of RAM.

Comparison with hybrid system identification

To analyze properties of the system, a natural idea is to first identify a dynamical model which then allows us to use well-documented model-based techniques. For hybrid systems, there also exist many identification techniques, see, e.g., [START_REF] Paoletti | Identification of hybrid systems: A tutorial[END_REF][START_REF] Lauer | Hybrid system identification: Theory and algorithms for learning switching models[END_REF]. In the comparison, we consider switched auto-regressive models, which are quite popular in hybrid system identification, see, e.g., [START_REF] Vidal | Recursive identification of switched ARX systems[END_REF]. For stability analysis, we convert the switched auto-regressive model into its state-space form using the transformation described in [START_REF] Weiland | On the equivalence of switched affine models and switched arx models[END_REF] and compute the JSR of the augmented model using the JSR toolbox [START_REF] Vankeerberghen | Jsr: A toolbox to compute the joint spectral radius[END_REF]. Note that the equivalence between switched affine models and switched ARX models has been proved in [START_REF] Weiland | On the equivalence of switched affine models and switched arx models[END_REF] under the pathwise observability condition. In particular, let us emphasize that such a conversion preserves internal stability under the pathwise observability condition.

The key step in the identification procedure is clustering where we group or label the output trajectories. For each group, we then estimate the parameters of its auto-regressive model by solving a least-square problem. A few clustering algorithms that we use in the simulation are the following: Generalized Principal Component Analysis (GPCA) [START_REF] Vidal | Generalized principal component analysis (GPCA)[END_REF], Sparse Subspace Clustering (SSC) [START_REF] Elhamifar | Sparse subspace clustering: Algorithm, theory, and applications[END_REF], Sparse Subspace Clustering by Orthogonal Matching Pursuit (SSC-OMP), [START_REF] You | Scalable sparse subspace clustering by orthogonal matching pursuit[END_REF], Elastic net Subspace Clustering (EnSC) [START_REF] You | Oracle based active set algorithm for scalable elastic net subspace clustering[END_REF], and Piecewise Affine Regression and Classification (PARC) [START_REF] Bemporad | A piecewise linear regression and classification algorithm with application to learning and model predictive control of hybrid systems[END_REF].

The numerical example is a three-dimensional switched linear system with 3 modes and 2 outputs. We then generate an output data set of length T = 5 and set k = 3 in [START_REF] Goebel | Hybrid Dynamical Systems: Modeling, Stability, and Robustness[END_REF]. The order of the auto-regressive models is set to be k and the maximal number of groups in the clustering algorithms is set to be M k-1 . The results are given in Figure 2, which shows the JSR estimation of our approach and the identification-based approach for different clustering algorithms as the number of data points increases. From this figure, we can see that the modeling error in hybrid system identification can lead to a false stability inference. Note that more data does not necessarily result in more accurate system identification from an algorithmic point of view, especially when there is a clustering step in the whole procedure. This is supported by Figure 2 as the JSR estimation can become worse as N increases. In contrast, our approach is guaranteed to provide better JSR estimation as N increases. Another practical issue of the identification-based approach is that in the clustering algorithms there are some parameters that need to be tuned carefully. We also make a comparison with the two standard clustering algorithms GPCA and SSC in terms of computational time in Table 1 T id denotes the computational time for the identification step and T JSR denotes the computational time for computing the JSR using the model.

A six-dimensional example

We also apply the proposed data-driven approach to a higher-dimensional example. We consider a switched linear system with n = 6, M = 3, p = 2 where the entries of the dynamics and output matrices are chosen randomly from the uniform distribution over [-1, 1]. We then sample a finite set of initial states following the Gaussian distribution N (0, I) and project them onto the unit sphere. In this way, we obtain a set of initial states that are uniformly distributed on the unit sphere. With this data set, we formulate Problem [START_REF] Sun | Switched linear systems : control and design[END_REF] with k = 3. This is a valid option as it can be verified that the system is pathwise observable with the pathwise observability index H(Σ) = 2. When the information of H(Σ) is not available, we use the procedure in Section 4.2 to estimate H(Σ). Finally, we are ready to solve Problem [START_REF] Sun | Switched linear systems : control and design[END_REF]. The simulation results are given in Figure 4 for different values of horizon length T . As expected, γ * (ω N ) gradually approaches the true JSR (which can be obtained from the JSR toolbox [START_REF] Vankeerberghen | Jsr: A toolbox to compute the joint spectral radius[END_REF]) as N and T increase.

Conclusions

In this paper, we have studied the problem of output-based stability learning of a special family of hybrid systems, namely switched linear systems, using a time-series output data set. We leverage a recently introduced approach for state-based data-driven stability analysis. However, the fact only a (possibly low-dimensional) output is observed incurs additional theoretical challenges that we tackle here. With the proposed output-based Lyapunov framework, we are able to derive probabilistic stability certificates for partially observed switched linear systems.

We have also presented additional procedures which allow to use explicit upper bounds on the JSR of switched linear systems. To validate our approach, we have made a comparison with the identification-based approach in which a model is identified using existing clustering algorithms in the literature. Numerical results suggest that it is beneficial to use our direct analysis approach as modeling errors can lead to false stability inferences. (δ µ(S)χ(P σ σ σ Σ (P,0,k)) 2

) 2 P σ σ σ Σ (P, 0, k). (50)
As σ σ σ is chosen arbitrarily, the inequality above holds for any σ σ σ ∈ M k+ . Note that the function δ(•) is non-increasing. Therefore, with the definition of χ Σ (P, k) as in [START_REF] Berger | Chance-constrained quasi-convex optimization with application to data-driven switched systems control[END_REF], we arrive at A σ σ σ 0: -1 P σ σ σ Σ (P, , k)A σ σ σ 0: -1 γ 2

(δ µ(S)χΣ(P,k)

2

) 2 P σ σ σ Σ (P, 0, k), ∀σ σ σ ∈ M k+ . (51)
Finally, from Theorem 1, we arrive at [START_REF] Kenanian | Data driven stability analysis of black-box switched linear systems[END_REF].

A2 Proof Theorem 3

To simplify the notation, we drop the subscript k in (γ * k (ω N ), P * k (ω N )) in the proof. We use the scenario approach to derive a probabilistic upper bound on the JSR via geometric analysis, following [START_REF] Kenanian | Data driven stability analysis of black-box switched linear systems[END_REF][START_REF] Berger | Chance-constrained quasi-convex optimization with application to data-driven switched systems control[END_REF]. From Theorem 6 in [START_REF] Berger | Chance-constrained quasi-convex optimization with application to data-driven switched systems control[END_REF], the chance-constrained theorem in [START_REF] Campi | The exact feasibility of randomized solutions of uncertain convex programs[END_REF][START_REF] Calafiore | Random convex programs[END_REF] is applicable and we obtain that for any ∈ (0, 1),

P N {ω N : P{V (ω N )} > } ≤ φ( ; d, N ), where V (ω N ) :={(x, σ σ σ) ∈ S n-1 × M T : x A σ σ σ 0: -1 P σ σ σ Σ (P * (ω N )), T -k, k)A σ σ σ 0: -1 x >(γ * (ω N )) 2(T -k) x P σ σ σ Σ (P * (ω N ), 0, k)x}.
For any σ σ σ ∈ M T , let V σ σ σ (ω N ) := {x ∈ S n-1 : (x, σ σ σ) ∈ V (ω N )}. With this definition, we claim that, for any σ σ σ ∈ M T x ∈ S n-1 \ σ σ σ∈M T V σ σ σ (ω N )

x A σ σ σ 0:

-1 P σ σ σ Σ (P * (ω N )), T -k, k)A σ σ σ 0: -1 x ≤(γ * (ω N )) 2(T -k) x P σ σ σ Σ (P * (ω N ), 0, k)x
Note that in the worst case, the sets {V σ σ σ (ω N )} are disjoint. When P{V (ω N )} ≤ , µ( σ σ σ∈M T V σ σ σ (ω N )) ≤ M T , where µ(•) denotes the (probability) uniform measure on S n-1 . From Theorem 2, we conclude that, with probability no smaller than 1 -φ( ; d, N ), ( 29) holds.

A3 Proof of Proposition 1

Proof: (i) Given β ∈ (0, 1) and ε > 0, from Corollary 3, we look for a N such that η(β, N ) ≤ 1 + ε, which is equivalent to φ(

I(1 - 1 (1+ε) 2(T -k) ; n-1 2 , 1 2 ) K 2 , d, N ) ≤ β (52)
where

K 2 = M T χ(Q) (c λ) n-1 . Hence, (35) holds. We then show that N (ε, β) = O 1 β 1 ε n 2
as ε → 0. To do so, we first show that φ( ; d, N ) can be explicitly bounded from above by d (N +1) for any ∈ (0, 1) and any N ∈ Z + . This can be verified using the following manipulations:

φ( ; d, N ) d (N +1) = d-1 i=0 N i i (1 -) N -i d (N +1) = d-1 i=0 i + 1 d N + 1 i + 1 i+1 (1 -) N -i ≤ d i=1 N + 1 i i (1 -) N +1-i ≤ φ( ; d + 1, N + 1) ≤ 1. (53)
This means that

N φ ( , β) ≤ d β . (54)
We then show that I(

x; n-1 2 , 1 2 ) ≥ K 1 x n 2
, where I(x; a, b) is defined as in [START_REF] Vapnik | The nature of statistical learning theory[END_REF] and

K 1 = 4 n 1 0 t n-3 2 (1-t) -1 2 dt
, as follows

I(x; n -1 2 , 1 2 ) = x 0 t n-3 2 (1 -t) -1 2 dt 1 0 t n-3 2 (1 -t) -1 2 dt = x 0 t n-2 2 1 (t(1-t)) 1 2 dt 1 0 t n-3 2 (1 -t) -1 2 dt ≥ 2 x 0 t n-2 2 dt 1 0 t n-3 2 (1 -t) -1 2 dt = K 1 x n 2 , (55)
where the inequality is due to the fact that t(1 -t) ≤ 1 4 . Combing ( 54) and ( 55) yields

N φ ( I(1 - 1 (1+ε) 2(T -k) ; n-1 2 , 1 2 ) M T χ(Q) (c λ) n-1 , β) ≤ K 2 d βI(1 - 1 (1+ε) 2(T -k) ; n-1 2 , 1 2 ) ≤ K 2 d βK 1 (1 - 1 (1+ε) 2(T -k) ) n 2 = K 2 d K 1 β (1 + 1 ε ) n(T -k) (1 + 1 ε ) 2(T -k) -( 1 ε ) 2(T -k) n 2
.

By some manipulations, we get that N s (ε, β) ≤ K2d K1β ( 1 ε ) n 2 as ε → 0, which can be equivalently expressed as [START_REF] Boffi | Learning stability certificates from data[END_REF]. This completes the proof. (ii) From the definition of sample complexity in Definition 5, it holds that P N {ω N :

γ o > (1 + ε)γ * (ω N )} ≤ β for any N ≥ N s (ε, β). The fact that ρ(Σ) > 1 implies that γ o > 1. With this, it can be verified that {ω N : γ * (ω N ) < 1 1+ε } ⊆ {ω N : γ o > (1 + ε)γ * (ω N )}, which implies (37). A4 Proof of Proposition 2 When k ≥ H(Σ), rank (O Σ (σ σ σ)) = n for any σ σ σ ∈ M k . Hence, ξ o k is bounded. (Necessity)
The proof goes by contradiction. Suppose there exists k < H(Σ) such that ξ o k < ∞. From the definition of H(Σ), there exists at least one sequence σ

σ σ ∈ M k such that rank (O Σ (σ σ σ)) < n. The fact that ξ o k < ∞ implies that O Σ (σ σ σ)x = 0 implies O Σ (σ σ σ)A σ σ σ x = 0 for any σ σ σ ∈ M k . In particular, O Σ (σ σ σ)x = 0 implies O Σ (σ σ σ)A σ σ σ x = 0. Then, there exists a matrix G ∈ R pk×pk such that O Σ (σ σ σ)A σ σ σ = GO Σ (σ σ σ), i.e.
, each row of O Σ (σ σ σ)A σ σ σ can be written as a linear combination of the rows in O Σ (σ σ σ). As a result, the periodic sequence σ σ σσ σ σ • • • is unobservable, which contradicts the fact that Σ is pathwise observable.

A5 Proof of Theorem 4

To prove Theorem 4, we first state the following bound on the singular value of the observability matrices.

Lemma 1 Consider the same conditions as in Theorem 3. Then, for any ε ∈ (0, 1) and ε ∈ (0, 1), with probability no smaller than 1 -

(1 -ε) N -(1 -ε ) N , max σ σ σ∈M k σ max (O Σ (σ σ σ)) min σ σ σ∈M k σ min (O Σ (σ σ σ)) ≤ ψ(ω N ) (56)
Proof: Since only the first k steps of the trajectory are relevant, we only consider the sample set ω N of length k. The proof consists of three steps:

Step 1: We consider the robust optimization problem below:

min ζ≥0 ζ : O Σ (σ σ σ)x ≤ ζ, ∀(x, σ σ σ) ∈ S n-1 × M k . ( 57
)
The optimum is exactly max σ σ σ∈M k σ max (O Σ (σ σ σ)). We want to show that the solution ζ k (ω N ) in [START_REF] Chang | Stabilizing neural control using self-learned almost lyapunov critics[END_REF] provides a probabilistic upper bound for Problem [START_REF] Bemporad | A piecewise linear regression and classification algorithm with application to learning and model predictive control of hybrid systems[END_REF]. To do so, we show the following chance-constrained result, given an ε ∈ (0, 1), .

P N
(63)

Step 2: Similarly, we define the following robust optimization problem:

max ζ≥0 ζ : O Σ (σ σ σ)x ≥ ζ, ∀(x, σ σ σ) ∈ S n-1 × M k . ( 64
)
As the constraint above is not convex in x, we cannot repeat the same reasoning in (i). Nevertheless, it still holds that the optimum of (64) is min σ σ σ∈M k σ min (O Σ (σ σ σ)), which can be attained, i.e., there exists (x * , σ σ σ * ) such that Step 3: We now combine the results from Steps 1 & 2. From Step 1, for any ε ∈ (0, 1), the probability that (63) does not hold is less than (1 -ε) N . From Step 2, for any ε ∈ (0, 1) the probability that (65) with ε does not hold is also less than (1 -ε ) N . Hence, the probability that (63) or (65) does not hold becomes (1 -ε) N + (1 -ε ) N , which means that the probability that both of ( 63 This, together with Theorem 3, and Lemma 1, leads to the result in Theorem 4.

Figure 1 :

 1 Figure 1: Illustration of δ(ε): ε is the uniform (probability) measure of the spherical cap in red and δ(ε) is the distance to the base of the spherical cap.

Figure 2 :

 2 Figure2: Comparison with the identification-based approach using different hybrid system identification algorithms.

Figure 3 :

 3 Figure 3: Estimates of ξ o k for different values of k.

Figure 4 :

 4 Figure 4: Data-based convergence rates for different horizon lengths.

  {ω N : Ω(ζ k (ω N )) > ε} = (1 -ε) N (58) where Ω(ζ) := P{(x, σ σ σ) ∈ S n-1 ×M k : O Σ (σ σ σ)x > ζ}. The function Ω : [0, max σ σ σ∈M k σ max (O Σ (σ σ σ))) → [0, 1] is decreasing. Hence, there exists a unique ζ such that Ω(ζ) = ε, denoted by ζ ε . With this, the set {ω N : Ω(ζ k (ω N )) > ε} can be equivalently expressed as {ω N: ω N ∩ {(x, σ σ σ) : O Σ (σ σ σ)x ≥ ζ ε } = ∅} (whose measure is (1 -ε) N), which leads to (58). Let us define the projected violating subset S as follows:S := {x ∈ S n-1 : ∃σ σ σ ∈ M k , O Σ (σ σ σ)x > ζ k (ω N )}.For any σ σ σ ∈ M k , we also define:Sσ σ σ := {x ∈ S n-1 : O Σ (σ σ σ)x > ζ k (ω N )}(59)By definition, S = ∪ σ σ σ∈M k Sσ σ σ , which implies thatP x { S} ≤ σ σ σ∈M k P x { Sσ σ σ }(60)where P x denotes the uniform probability measure on S n-1 and the equality holds when the sets { Sσ σ σ } σ σ σ∈M k are disjoint. With the inequality above, we get thatΩ(ζ k (ω N )) = σ σ σ∈M k P x { Sσ σ σ }P σ {σ σ σ} = 1 M k σ σ σ∈M k P x { Sσ σ σ } ≥ 1 M k P x { S}(61)where P σ denote the uniform distribution on M k . This means that Ω(ζ k (ω N )) ≤ ε impliesP x { S} ≤ M k ε. Hence, P N {ω N : P x { S} ≤ εM k } = (1 -ε) N(62)from (58). Finally, following the same lines as the proof of [25, Theorem 15], we conclude that, with probability no smaller than 1 -(1 -ε) N , max σ σ σ∈M k σ max (O Σ (σ σ σ)) ≤ ζ k (ω N ) δ( εM k 2 )

O

  Σ (σ σ σ * )x * = min σ σ σ∈M k σ min (O Σ (σ σ σ)).

For any ε ∈ (0, 1 )

 1 , we define the set S := {x ∈ S n-1 :|x x * | ≥ δ( εM k 2 )} with P x { S} = εM k . The probability that ω N ∩ S × {σ σ σ * } = ∅ is 1 -(1 -ε) N . In this case, there exists (x, σ σ σ) ∈ ω N such that σ σ σ = σ σ σ * and |x x * | ≥ δ( εM k 2 ), which implies that x -x * ≤ 2 -2δ( εM k 2 ) or x + x * ≤ 2 -2δ( εM k 2 ). From the definition in (42), O Σ (σ σ σ)x ≥ ζ k (ω N ).We then consider the case that x -x * ≤ 2 -2δ( εM k 2 ) (the analysis is exactly the same for the other case). With these relations, it holds thatO Σ (σ σ σ * )x * = O Σ (σ σ σ * )(x + x * -x) ≥ O Σ (σ σ σ * )x -O Σ (σ σ σ * ) x * -x ≥ ζ k (ω N ) -max σ σ σ∈M k O Σ (σ σ σ) 2 -2δ( εM k 2 ).Based on this inequality, we conclude that, with probability no smaller than 1 -(1 -ε) N , min σ σ σ∈M k σ min (O Σ (σ σ σ)) ≥ζ k (ω N )

  ) and (65) hold is no smaller than 1-(1 -ε) N -(1 -ε ) N . Thus,[START_REF] You | Oracle based active set algorithm for scalable elastic net subspace clustering[END_REF] holds with probability no smaller than 1-(1 -ε) N -(1 -ε ) N .From the arguments in the proof of Corollary 2, it holds thatχ Σ (P, k) ≤ (c 2 k κ(P )) n-1wherec k = max σ σ σ∈M k σ max (O Σ (σ σ σ)) min σ σ σ∈M k σ min (O Σ (σ σ σ)) .

Table 1 :

 1 . Computational time (second) for different algorithms:

	N	500	1000	1500	2000
	Our approach 22.08	50.53	61.18	62.48
	GPCA	T id T JSR 15.42 4.92	40.46 32.93	137.90 14.22	256.27 5.19
	SSC	T id T JSR 67.90 894.20 2550.08 3554.40 5015.54 124.18 67.10 120.97

The first component comes first: (γ1, P1 F ) < (γ2, P2 F ) if γ1 < γ2 or else γ1 = γ2 and P1 F < P2 F .

Raphaël M. Jungers is a FNRS honorary Research Associate. This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme under grant agreement No 864017 -L2C. Raphaël M. Jungers is also supported by the Innoviris Foundation and the FNRS (Chist-Era Druid-net). He is currently on sabbatical leave at Oxford University,

A1 Proof of Theorem 2

Since Σ is pathwise observable, P σ σ σ Σ (P, 0, k) 0 and P σ σ σ Σ (P, , k) 0 for any σ σ σ ∈ M k+ . We pick an arbitrary σ σ σ ∈ M k+ and consider the Cholesky decompositions of P σ σ σ Σ (P, 0, k) and P σ σ σ Σ (P, , k): U U = P σ σ σ Σ (P, 0, k), Ũ Ũ = P σ σ σ Σ (P, , k),

where U ∈ R n×n and Ũ ∈ R n×n are triangular matrices. Hence, by the change of coordinates, [START_REF] Shalev-Shwartz | Understanding machine learning: From theory to algorithms[END_REF] becomes

The homogeneity of the dynamics implies that

where Π Sn-1 (•) denote the projection onto S n-1 . Equivalently, we can write [START_REF] Boyd | Convex Optimization[END_REF] as

Following the same arguments in Theorem 15 in [START_REF] Kenanian | Data driven stability analysis of black-box switched linear systems[END_REF], we obtain that

An illustration of the function δ(•) is given in Figure 1. Hence, it holds that Ũ A σ σ σ 0: -1 U -1 Ũ A σ σ σ 0: -1 U -1 γ 2

(δ µ(S)χ(P σ σ σ Σ (P,0,k)) 2