/
JSR+matprod.bib
17034 lines (16552 loc) · 896 KB
/
JSR+matprod.bib
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
% !Mode:: "BibTeX"
@PREAMBLE{"
\providecommand{\bbljan}[0]{January}
\providecommand{\bblfeb}[0]{February}
\providecommand{\bblmar}[0]{March}
\providecommand{\bblapr}[0]{April}
\providecommand{\bblmay}[0]{May}
\providecommand{\bbljun}[0]{June}
\providecommand{\bbljul}[0]{July}
\providecommand{\bblaug}[0]{August}
\providecommand{\bblsep}[0]{September}
\providecommand{\bbloct}[0]{October}
\providecommand{\bblnov}[0]{November}
\providecommand{\bbldec}[0]{December}"}
@ARTICLE{AGGM:Automatica22,
author = "Aazan, Georges and Girard, Antoine and Greco, Luca and
Mason, Paolo",
title = "Stability of shuffled switched linear systems: {A} joint
spectral radius approach",
journal = "Automatica J. IFAC",
fjournal = "Automatica. A Journal of IFAC, the International Federation
of Automatic Control",
year = "2022",
volume = "143",
pages = "Paper No. 110434, 13",
issn = "0005-1098",
mrclass = "93C30 (93C55 93D05)",
mrnumber = "4444685",
zblnumber = "1497.93159",
hal_id = "hal-03257026",
hal_version = "v3",
doi = "10.1016/j.automatica.2022.110434",
url = "https://www.sciencedirect.com/science/article/pii/S0005109822002886",
annote = "A switching signal for a switched system is said to be
shuffled if all modes of the system are activated
infinitely often. In this paper, we develop tools to
analyze stability properties of discrete-time switched
linear systems driven by shuffled switching signals. We
introduce the new notion of shuffled joint spectral radius
(SJSR), which intuitively measures how much the state of
the system contracts each time the signal shuffles (i.e.
each time all modes have been activated). We show how this
notion relates to stability properties of the associated
switched systems. In particular, we show that some switched
systems that are unstable for arbitrary switching signals
can be stabilized by using switching signals that shuffle
sufficiently fast and that the SJSR allows us to derive an
expression of the minimal shuffling rate required to
stabilize the system. We then present several approaches to
compute lower and upper bounds of the SJSR using tools such
as the classical joint spectral radius, Lyapunov functions
and finite state automata. Several tightness results of the
bounds are established. Finally, numerical experiments are
presented to illustrate the main results of the paper.",
}
@INCOLLECTION{AGMG2024,
author = "Aazan, Georges and Girard, Antoine and Mason, Paolo and
Greco, Luca",
editor = "Postoyan, Romain and Frasca, Paolo and Panteley, Elena and
Zaccarian, Luca",
title = "A Joint Spectral Radius for {$\omega$}-Regular
Language-Driven Switched Linear Systems",
booktitle = "Hybrid and Networked Dynamical Systems: Modeling, Analysis
and Control",
year = "2024",
publisher = "Springer Nature Switzerland",
address = "Cham",
pages = "161--178",
isbn = "978-3-031-49555-7",
doi = "10.1007/978-3-031-49555-7_7",
url = "https://link.springer.com/chapter/10.1007/978-3-031-49555-7_7",
annote = "In this chapter, we introduce some tools to analyze
stability properties of discrete-time switched linear
systems driven by switching signals belonging to a given
$\omega$-regular language. More precisely, we assume that
the switching signals are generated by a deterministic
B{\"u}chi automaton whose alphabet coincides with the set
of modes of the switched system. We present the notion of
$\omega$-regular joint spectral radius ($\omega$-RJSR),
which intuitively describes the contraction of the state
when the run associated with the switching signal visits an
accepting state of the automaton. Then, we show how this
quantity is related to the stability properties of such
systems. Specifically, we show how this notion can
characterize a class of stabilizing switching signals for a
switched system that is unstable for arbitrary switching.
Though the introduced quantity is hard to compute, we
present some methods to approximate it using Lyapunov and
automata-theoretic techniques. More precisely, we show how
upper bounds can be computed by solving a convex
optimization problem. To validate the results of our work,
we finally show a numerical example related to the
synchronization of oscillators over a communication
network.",
}
@PHDTHESIS{Ahmadi08,
author = "Ahmadi, Amir Ali",
authauthor = "Ahmadi, Amir",
title = "Non-monotonic {L}yapunov functions for stability of
nonlinear and switched systems: theory and computation",
school = "Dept. of Electrical Engineering and Computer Science",
address = "Massachusetts Institute of Technology",
year = "2008",
url = "https://dspace.mit.edu/handle/1721.1/44206",
annote = "Lyapunov's direct method, which is based on the existence of
a scalar function of the state that decreases monotonically
along trajectories, still serves as the primary tool for
establishing stability of nonlinear systems. Since the main
challenge in stability analysis based on Lyapunov theory is
always to find a suitable Lyapunov function, weakening the
requirements of the Lyapunov function is of great interest.
In this thesis, we relax the monotonicity requirement of
Lyapunov's theorem to enlarge the class of functions that
can provide certificates of stability. Both the discrete
time case and the continuous time case are covered.
Throughout the thesis, special attention is given to
techniques from convex optimization that allow for
computationally tractable ways of searching for Lyapunov
functions. Our theoretical contributions are therefore
amenable to convex programming formulations. In the
discrete time case, we propose two new sufficient
conditions for global asymptotic stability that allow the
Lyapunov functions to increase locally, but guarantee an
average decrease every few steps. Our first condition is
nonconvex, but allows an intuitive interpretation. The
second condition, which includes the first one as a special
case, is convex and can be cast as a semidefinite program.
We show that when non-monotonic Lyapunov functions exist,
one can construct a more complicated function that
decreases monotonically. We demonstrate the strength of our
methodology over standard Lyapunov theory through examples
from three different classes of dynamical systems. First,
we consider polynomial dynamics where we utilize techniques
from sum-of-squares programming. Second, analysis of
piecewise and systems is performed. Here, connections to
the method of piecewise quadratic Lyapunov functions are
made.(cont.) Finally, we examine systems with arbitrary
switching between a finite set of matrices. It will be
shown that tighter bounds on the joint spectral radius can
be obtained using our technique. In continuous time, we
present conditions invoking higher derivatives of Lyapunov
functions that allow the Lyapunov function to increase but
bound the rate at which the increase can happen. Here, we
build on previous work by Butz that provides a nonconvex
sufficient condition for asymptotic stability using the
first three derivatives of Lyapunov functions. We give a
convex condition for asymptotic stability that includes the
condition by Butz as a special case. Once again, we draw
the connection to standard Lyapunov functions. An example
of a polynomial vector field is given to show the potential
advantages of using higher order derivatives over standard
Lyapunov theory. We also discuss a theorem by Yorke that
imposes minor conditions on the first and second
derivatives to reject existence of periodic orbits, limit
cycles, or chaotic attractors. We give some simple convex
conditions that imply the requirement by Yorke and we
compare them with those given in another earlier work.
Before presenting our main contributions, we review some
aspects of convex programming with more emphasis on
semidefinite programming. We explain in detail how the
method of sum of squares decomposition can be used to
efficiently search for polynomial Lyapunov functions.",
}
@INPROCEEDINGS{AhmJun:CDC13,
author = "Ahmadi, Amir Ali and Jungers, Rapha{\"e}l M.",
authauthor = "Ahmadi, Amir and Rapha{\"e}l Jungers",
title = "Switched stability of nonlinear systems via {SOS}-convex
{L}yapunov functions and semidefinite programming",
booktitle = "Proceedings of the 52nd IEEE Annual Conference on Decision
and Control (CDC)",
year = "2013",
pages = "727--732",
doi = "10.1109/CDC.2013.6759968",
url = "https://ieeexplore.ieee.org/document/6759968",
annote = "We introduce the concept of sos-convex Lyapunov functions
for stability analysis of discrete time switched systems.
These are polynomial Lyapunov functions that have an
algebraic certificate of convexity, and can be efficiently
found by semidefinite programming. We show that convex
polynomial Lyapunov functions are universal (i.e.,
necessary and sufficient) for stability analysis of
switched linear systems. On the other hand, we show via an
explicit example that the minimum degree of an sos-convex
Lyapunov function can be arbitrarily higher than a
(non-convex) polynomial Lyapunov function. (The proof is
omitted.) In the second part, we show that if the switched
system is defined as the convex hull of a finite number of
nonlinear functions, then existence of a non-convex common
Lyapunov function is not a sufficient condition for
switched stability, but existence of a convex common
Lyapunov function is. This shows the usefulness of the
computational machinery of sos-convex Lyapunov functions
which can be applied either directly to the switched
nonlinear system, or to its linearization, to provide proof
of local switched stability for the nonlinear system. An
example is given where no polynomial of degree less than 14
can provide an estimate to the region of attraction under
arbitrary switching.",
}
@ARTICLE{AhmJun14,
author = "Ahmadi, Amir Ali and Jungers, Rapha{\"e}l M.",
authauthor = "Ahmadi, Amir and Jungers, Rapha{\"e}l",
title = "On Complexity of {L}yapunov Functions for Switched Linear
Systems",
journal = "IFAC Proceedings Volumes",
year = "2014",
volume = "47",
number = "3",
pages = "5992--5997",
issn = "1474-6670",
doi = "10.3182/20140824-6-ZA-1003.02484",
url = "https://www.sciencedirect.com/science/article/pii/S1474667016425504",
note = "19th IFAC World Congress",
annote = "We show that for any positive integer $d$, there are
families of switched linear systems --- in fixed dimension
and defined by two matrices only --- that are stable under
arbitrary switching but do not admit (i) a polynomial
Lyapunov function of degree $\le d$, or (ii) a polytopic
Lyapunov function with $\le d$ facets, or (iii) a piecewise
quadratic Lyapunov function with $\le d$ pieces. This
implies that there cannot be an upper bound on the size of
the linear and semidefinite programs that search for such
stability certificates. Several constructive and
non-constructive arguments are presented which connect our
problem to known (and rather classical) results in the
literature regarding the finiteness conjecture,
undecidability, and non-algebraicity of the joint spectral
radius. In particular, we show that existence of a sum of
squares Lyapunov function implies the finiteness property
of the optimal product.",
}
@ARTICLE{AhmJng:NAHS16,
author = "Ahmadi, Amir Ali and Jungers, Rapha{\"e}l M.",
authauthor = "Ahmadi, Amir and Jungers, Rapha{\"e}l",
title = "Lower bounds on complexity of {L}yapunov functions for
switched linear systems",
journal = "Nonlinear Anal. Hybrid Syst.",
fjournal = "Nonlinear Analysis. Hybrid Systems",
year = "2016",
volume = "21",
pages = "118--129",
eprinttype = "arXiv",
eprint = "1504.03761",
issn = "1751-570X",
mrclass = "93D30 (90C90)",
mrnumber = "3500076",
zblnumber = "1382.93028",
doi = "10.1016/j.nahs.2016.01.003",
url = "https://www.sciencedirect.com/science/article/pii/S1751570X16000121",
annote = "We show that for any positive integer $d$, there are
families of switched linear systems --- in fixed dimension
and defined by two matrices only --- that are stable under
arbitrary switching but do not admit (i) a polynomial
Lyapunov function of degree $\le d$, or (ii) a polytopic
Lyapunov function with $\le d$ facets, or (iii) a piecewise
quadratic Lyapunov function with $\le d$ pieces. This
implies that there cannot be an upper bound on the size of
the linear and semidefinite programs that search for such
stability certificates. Several constructive and
non-constructive arguments are presented which connect our
problem to known (and rather classical) results in the
literature regarding the finiteness conjecture,
undecidability, and non-algebraicity of the joint spectral
radius. In particular, we show that existence of an
extremal piecewise algebraic Lyapunov function implies the
finiteness property of the optimal product, generalizing a
result of Lagarias and Wang. As a corollary, we prove that
the finiteness property holds for sets of matrices with an
extremal Lyapunov function belonging to some of the most
popular function classes in controls.",
}
@ARTICLE{AJPR:IFACSRCD12,
author = "Ahmadi, Amir Ali and Jungers, Raphael M. and Parrilo, Pablo
A. and Roozbehani, Mardavij",
authauthor = "Ahmadi, Amir and Jungers, Raphael and Parrilo, Pablo and
Roozbehani, Mardavij",
title = "When is a set of {LMI}s a sufficient condition for
stability?",
journal = "IFAC Proceedings Volumes",
year = "2012",
volume = "45",
number = "13",
pages = "313--318",
eprinttype = "arXiv",
eprint = "1201.3227",
issn = "1474-6670",
doi = "10.3182/20120620-3-DK-2025.00098",
url = "https://www.sciencedirect.com/science/article/pii/S1474667015377077",
note = "7th IFAC Symposium on Robust Control Design",
annote = "We study stability criteria for discrete time switching
systems. We investigate the structure of sets of LMIs that
are a sufficient condition for stability (i.e., such that
any switching system which satisfies these LMIs is stable).
We provide an exact characterization of these sets. As a
corollary, we show that it is PSPACE-complete to recognize
whether a particular set of LMIs implies the stability of a
switching system.",
}
@ARTICLE{AJPR:SIAMJCO14,
author = "Ahmadi, Amir Ali and Jungers, Rapha{\"e}l M. and Parrilo,
Pablo A. and Roozbehani, Mardavij",
authauthor = "Ahmadi, Amir and Jungers, Rapha{\"e}l and Parrilo, Pablo and
Roozbehani, Mardavij",
title = "Joint spectral radius and path-complete graph {L}yapunov
functions",
journal = "SIAM J. Control Optim.",
fjournal = "SIAM Journal on Control and Optimization",
year = "2014",
volume = "52",
number = "1",
pages = "687--717",
eprinttype = "arXiv",
eprint = "1111.3427",
issn = "0363-0129",
mrclass = "93D30 (37C75)",
mrnumber = "3168608",
mrreviewer = "Bryan E. Cain",
zblnumber = "1292.93093",
doi = "10.1137/110855272",
url = "https://epubs.siam.org/doi/10.1137/110855272",
annote = "We introduce the framework of path-complete graph Lyapunov
functions for approximation of the joint spectral radius.
The approach is based on the analysis of the underlying
switched system via inequalities imposed among multiple
Lyapunov functions associated to a labeled directed graph.
Inspired by concepts in automata theory and symbolic
dynamics, we define a class of graphs called path-complete
graphs, and show that any such graph gives rise to a method
for proving stability of the switched system. This enables
us to derive several asymptotically tight hierarchies of
semidefinite programming relaxations that unify and
generalize many existing techniques such as common
quadratic, common sum of squares, and
maximum/minimum-of-quadratics Lyapunov functions. We
compare the quality of approximation obtained by certain
classes of path-complete graphs including a family of dual
graphs and all path-complete graphs with two nodes on an
alphabet of two matrices. We provide approximation
guarantees for several families of path-complete graphs,
such as the De Bruijn graphs, establishing as a byproduct a
constructive converse Lyapunov theorem for
maximum/minimum-of-quadratics Lyapunov functions.",
}
@INPROCEEDINGS{AJPR:HCSS11,
author = "Ahmadi, Amir Ali and Jungers, Rapha{\"e}l and Parrilo, Pablo
A. and Roozbehani, Mardavij",
authauthor = "Ahmadi, Amir and Jungers, Rapha{\"e}l and Parrilo, Pablo and
Roozbehani, Mardavij",
title = "Analysis of the joint spectral radius via {L}yapunov
functions on path-complete graphs",
booktitle = "Proceedings of the 14th international conference on Hybrid
systems: computation and control (HSCC'11)",
publisher = "ACM",
address = "New York, NY, USA",
year = "2011",
pages = "13--22",
mrnumber = "3207287",
zblnumber = "1364.93376",
doi = "10.1145/1967701.1967706",
url = "https://dl.acm.org/doi/10.1145/1967701.1967706",
annote = "We study the problem of approximating the joint spectral
radius (JSR) of a finite set of matrices. Our approach is
based on the analysis of the underlying switched linear
system via inequalities imposed between multiple Lyapunov
functions associated to a labeled directed graph. Inspired
by concepts in automata theory and symbolic dynamics, we
define a class of graphs called path-complete graphs, and
show that any such graph gives rise to a method for proving
stability of the switched system. This enables us to derive
several asymptotically tight hierarchies of semidefinite
programming relaxations that unify and generalize many
existing techniques such as common quadratic, common sum of
squares, maximum/minimum-of-quadratics Lyapunov functions.
We characterize all path-complete graphs consisting of two
nodes on an alphabet of two matrices and compare their
performance. For the general case of any set of $n\times n$
matrices we propose semidefinite programs of modest size
that approximate the JSR within a multiplicative factor of
$1/\sqrt[4]{n}$ of the true value. We establish a notion of
duality among path-complete graphs and a constructive
converse Lyapunov theorem for maximum/minimum-of-quadratics
Lyapunov functions.",
}
@INPROCEEDINGS{AhmPar:CDC05,
author = "Ahmadi, Amir Ali and Parrilo, Pablo A.",
authauthor = "Ahmadi, Amir and Parrilo, Pablo",
title = "Non-monotonic {L}yapunov functions for stability of discrete
time nonlinear and switched systems",
booktitle = "Proceedings of the 47th IEEE Conference on Decision and
Control (CDC)",
year = "2008",
pages = "614--621",
doi = "10.1109/CDC.2008.4739402",
url = "https://ieeexplore.ieee.org/document/4739402",
annote = "We relax the monotonicity requirement of Lyapunov's theorem
to enlarge the class of functions that can provide
certificates of stability. To this end, we propose two new
sufficient conditions for global asymptotic stability that
allow the Lyapunov functions to increase locally, but
guarantee an average decrease every few steps. Our first
condition is non-convex, but allows an intuitive
interpretation. The second condition, which includes the
first one as a special case, is convex and can be cast as a
semidefinite program. We show that when non-monotonic
Lyapunov functions exist, one can construct a more
complicated function that decreases monotonically. We
demonstrate the strength of our methodology over standard
Lyapunov theory through examples from three different
classes of dynamical systems. First, we consider polynomial
dynamics where we utilize techniques from sum-of-squares
programming. Second, analysis of piecewise affine systems
is performed. Here, connections to the method of piecewise
quadratic Lyapunov functions are made. Finally, we examine
systems with arbitrary switching between a finite set of
matrices. It will be shown that tighter bounds on the joint
spectral radius can be obtained using our technique.",
}
@INPROCEEDINGS{AhmPar:CDC12,
author = "Ahmadi, Amir Ali and Parrilo, Pablo A.",
authauthor = "Ahmadi, Amir and Parrilo, Pablo",
title = "Joint Spectral Radius of Rank One Matrices and the Maximum
Cycle Mean Problem",
booktitle = "Proceedings of the 51st Annual Conference on Decision and
Control (CDC), 10-13 Dec.",
organization = "IEEE",
year = "2012",
pages = "731--733",
doi = "10.1109/CDC.2012.6425992",
url = "https://ieeexplore.ieee.org/document/1582513",
annote = "We prove several exact results on approximability of joint
spectral radius by matrix norms induced by Euclidean norms.
We point out, perhaps for the first time in this context, a
difference between complex and real cases. New connections
of joint spectral radius to convex geometry and
combinatorics are established. Several open problems are
posed.",
}
@INPROCEEDINGS{ABMW:MTNS12,
author = "Ait Rami, Mustafa and Bokharaie, Vahid S. and Mason, Oliver
and Wirth, Fabian R.",
authauthor = "Ait Rami, Mustafa and Bokharaie, Vahid and Mason, Oliver and
Wirth, Fabian",
title = "Extremal norms for positive linear inclusions",
booktitle = "20th International Symposium on Mathematical Theory of
Networks and Systems, MTNS2012, 9--13 July",
organization = "The University of Melburne",
address = "Melbourne",
year = "2012",
url = "https://citeseerx.ist.psu.edu/document?type=pdf&doi=224a9b6ba92e969309775ff068fd1ad522692483",
annote = "We consider the joint spectral radius of sets of matrices
for discrete or continuous positive linear inclusions and
study associated extremal norms. We show that under a
matrix-theoretic notion of irreducibility there exist
absolute extremal norms. This property is used to extend
regularity results for the joint spectral radius. In
particular, we see that in the case of positive systems
irreducibility in the sense of nonnegative matrices, which
is weaker than the usual representation theoretic concept,
is sufficient for local Lipschitz properties of the joint
spectral radius.",
}
@ARTICLE{Alpin:MZ10,
author = "Al'pin, {\relax{}Yu}. A.",
authauthor = "Al'pin, {\relax{}Yu}.",
title = "Bounds for the joint spectral radii of a set of nonnegative
matrices",
journal = "Math. Notes",
fjournal = "Mathematical Notes",
year = "2010",
volume = "87",
number = "1",
pages = "12--14",
issn = "0001-4346",
mrclass = "15B48 (15A42)",
mrnumber = "2730378 (2011j:15054)",
mrreviewer = "Mihail Voicu",
zblnumber = "1202.15022",
zblreviewer = "Ludwig Elsner (Bielefeld)",
doi = "10.1134/S0001434610010025",
url = "https://link.springer.com/article/10.1134/S0001434610010025",
annote = "For a finite set $\Sigma$ of nonnegative matrices of order
$n$ the upper and lower joint spectral radius is defined.
Bounds for these magnitudes are given in terms of the
following matrix $S=(s_{ij})$, where $s_{ij}
=\max\{\sum_{k} a_{ik} : A\in\Sigma, a_{ij} >0\}$ and in
terms of the similarly defined matrix $S^{-}$. It is shown
that the upper joint spectral radius is bounded by the max
spectral radius of S and that a similar result holds for
the lower joint spectral radius. This generalizes results
for the case of one matrix. In the proof methods of max
algebra are used.",
}
@ARTICLE{ASU:I11,
author = "Allen, Jeffrey and Seeger, Benjamin and Unger, Deborah",
title = "On the size of the resonant set for the products of
{$2\times 2$} matrices",
journal = "Involve",
fjournal = "Involve. A Journal of Mathematics",
year = "2011",
volume = "4",
number = "2",
pages = "157--166",
eprinttype = "arXiv",
eprint = "1106.2903",
issn = "1944-4176",
mrclass = "37H15 (37C85 37H05)",
mrnumber = "2876196",
zblnumber = "1233.37029",
doi = "10.2140/involve.2011.4.157",
url = "https://msp.org/involve/2011/4-2/p05.xhtml",
annote = "For $\theta\in[0,2\pi)$, consider the rotation matrix
$R_\theta$ and \[h=\left(\begin{array}{cc}\lambda & 0\\ 0 &
0\end{array}\right),\quad\lambda>1.\] Let $W_n(\theta)$
denote the product of $m$ $R_{\theta}$'s and $n$ $h$'s with
the condition $m\leq[\epsilon n]$ ($0<\epsilon< 1$). We
analyze the measure of the set of $\theta$ for which
$\|W_n( \theta)\|\geq\lambda^{\delta n}$ ($0<\delta< 1$).
This can be regarded as a model problem for the so-called
Bochi--Fayad conjecture.",
}
@INPROCEEDINGS{AltPar:CDC19,
author = "Altschuler, Jason M. and Parrilo, Pablo A.",
authauthor = "Jason Altschuler and Parrilo, Pablo",
title = "Lyapunov exponent of rank-one matrices: ergodic formula and
inapproximability of the optimal distribution",
booktitle = "2019 IEEE 58th Conference on Decision and Control (CDC),
11-13 Dec.",
publisher = "IEEE",
address = "Nice, France, France",
year = "2019",
pages = "4439--4445",
eprinttype = "arXiv",
eprint = "1905.07531",
doi = "10.1109/CDC40024.2019.9029462",
url = "https://ieeexplore.ieee.org/document/9029462",
annote = "The \emph{Lyapunov exponent} corresponding to a set of
square matrices $\mathcal{A} = \{A_1, \dots, A_n \}$ and a
probability distribution $p$ over $\{1, \dots, n\}$ is
$\lambda(\mathcal{A}, p) := \lim_{k \to \infty} \frac{1}{k}
\,\mathbb{E} \log \lVert{A_{\sigma_k} \cdots
A_{\sigma_2}A_{\sigma_1}}\rVert$, where $\sigma_i$ are
i.i.d. according to $p$. This quantity is of fundamental
importance to control theory since it determines the
asymptotic convergence rate $e^{\lambda(\mathcal{A}, p)}$
of the stochastic linear dynamical system $x_{k+1} =
A_{\sigma_k} x_k$. This paper investigates the following
``design problem'': given $\mathcal{A}$, compute the
distribution $p$ minimizing $\lambda(\mathcal{A}, p)$. Our
main result is that it is NP-hard to decide whether there
exists a distribution $p$ for which $\lambda(\mathcal{A},
p) < 0$, i.e. it is NP-hard to decide whether this
dynamical system can be stabilized.\par This hardness
result holds even in the ``simple'' case where
$\mathcal{A}$ contains only rank-one matrices. Somewhat
surprisingly, this is in stark contrast to the Joint
Spectral Radius -- the deterministic kindred of the
Lyapunov exponent -- for which the analogous optimization
problem for rank-one matrices is known to be exactly
computable in polynomial time.\par To prove this hardness
result, we first observe via Birkhoff's Ergodic Theorem
that the Lyapunov exponent of rank-one matrices admits a
simple formula and in fact is a quadratic form in~$p$.
Hardness of the design problem is shown through a reduction
from the Independent Set problem. Along the way, simple
examples are given illustrating that $p \mapsto
\lambda(\mathcal{A}, p)$ is neither convex nor concave in
general, and a connection is made to the fact that the
Martin distance on the $(1, n)$ Grassmannian is not a
metric. See.~\cite{AltPar:SIAMJCO20}.",
}
@ARTICLE{AltPar:SIAMJCO20,
author = "Altschuler, Jason M. and Parrilo, Pablo A.",
authauthor = "Jason Altschuler and Parrilo, Pablo",
title = "Lyapunov exponent of rank-one matrices: ergodic formula and
inapproximability of the optimal distribution",
journal = "SIAM J. Control Optim.",
fjournal = "SIAM Journal on Control and Optimization",
year = "2020",
volume = "58",
number = "1",
pages = "510--528",
issn = "0363-0129",
mrclass = "37M25 (68Q17)",
mrnumber = "4068319",
zblnumber = "1451.93408",
doi = "10.1137/19M1264072",
url = "https://epubs.siam.org/doi/10.1137/19M1264072",
annote = "The \emph{Lyapunov exponent} corresponding to a set of
square matrices $\mathcal{A} = \{A_1, \dots, A_n \}$ and a
probability distribution $p$ over $\{1, \dots, n\}$ is
$\lambda(\mathcal{A}, p) := \lim_{k \to \infty} \frac{1}{k}
\,\mathbb{E} \log \lVert{A_{\sigma_k} \cdots
A_{\sigma_2}A_{\sigma_1}}\rVert$, where $\sigma_i$ are
i.i.d. according to $p$. This quantity is of fundamental
importance to control theory since it determines the
asymptotic convergence rate $e^{\lambda(\mathcal{A}, p)}$
of the stochastic linear dynamical system $x_{k+1} =
A_{\sigma_k} x_k$. This paper investigates the following
``design problem'': given $\mathcal{A}$, compute the
distribution $p$ minimizing $\lambda(\mathcal{A}, p)$. Our
main result is that it is NP-hard to decide whether there
exists a distribution $p$ for which $\lambda(\mathcal{A},
p) < 0$, i.e. it is NP-hard to decide whether this
dynamical system can be stabilized.\par This hardness
result holds even in the ``simple'' case where
$\mathcal{A}$ contains only rank-one matrices. Somewhat
surprisingly, this is in stark contrast to the Joint
Spectral Radius -- the deterministic kindred of the
Lyapunov exponent -- for which the analogous optimization
problem for rank-one matrices is known to be exactly
computable in polynomial time.\par To prove this hardness
result, we first observe via Birkhoff's Ergodic Theorem
that the Lyapunov exponent of rank-one matrices admits a
simple formula and in fact is a quadratic form in~$p$.
Hardness of the design problem is shown through a reduction
from the Independent Set problem. Along the way, simple
examples are given illustrating that $p \mapsto
\lambda(\mathcal{A}, p)$ is neither convex nor concave in
general. We conclude with extensions to continuous
distributions, exchangeable processes, Markov processes,
and stationary ergodic processes.
See.~\cite{AltPar:CDC19}.",
}
@ARTICLE{AndoShih:SIAM:98,
author = "Ando, Tsuyoshi and Shih, Mau-Hsiang",
title = "Simultaneous contractibility",
journal = "SIAM J. Matrix Anal. Appl.",
fjournal = "SIAM Journal on Matrix Analysis and Applications",
year = "1998",
volume = "19",
number = "2",
pages = "487--498 (electronic)",
issn = "0895-4798",
mrclass = "15A60 (47A30)",
mrnumber = "1614074 (99c:15046)",
mrreviewer = "Sivaram K. Narayan",
zblnumber = "0912.15033",
zblreviewer = "Alexey Alimov (Moskva)",
doi = "10.1137/S0895479897318812",
url = "https://epubs.siam.org/doi/10.1137/S0895479897318812",
annote = "Let $\mathcal{C}$ be a set of $n\times n$ complex matrices.
For $m = 1,2,\ldots$, $\mathcal{C}^{m}$ is the set of all
products of matrices in $\mathcal{C}$ of length $m$. Denote
by $\hat{r}(\mathcal{C})$ the joint spectral radius of
$\mathcal{C}$, that is, \[\hat{r}(\mathcal{C})\stackrel{\rm
def}{=}\limsup_{m\to\infty}[\sup_{A\in \mathcal{C}^m}\| A\|
]^{\frac{1}{m}}.\] We call $\mathcal{C}$
\emph{simultaneously contractible} if there is an
invertible matrix $S$ such that \[\sup\{\| S^{-1}AS\|;\
A\in \mathcal{C}\}<1,\] where $\| \cdot\|$ is the spectral
norm. This paper is primarily devoted to determining the
optimal joint spectral radius range for simultaneous
contractibility of bounded sets of $n\times n$ complex
matrices, that is, the maximum subset $J$ of $[0,1)$ such
that if $\mathcal{C}$ is a bounded set of $n\times n$
complex matrices and $\hat{r}(\mathcal{C})\in J$, then
$\mathcal{C}$ is simultaneously contractible. The central
result proved in this paper is that this maximum subset is
$[0,\frac{1}{\sqrt{n}})$. Our method of proof is based on a
matrix-theoretic version of complex John's ellipsoid
theorem and the generalized Gelfand spectral radius
formula.",
}
@ARTICLE{AT:JMAA77,
author = "Anthonisse, Jac. M. and Tijms, Henk",
authauthor = "Anthonisse, Jac. and Tijms, Henk",
title = "Exponential convergence of products of stochastic matrices",
journal = "J. Math. Anal. Appl.",
fjournal = "Journal of Mathematical Analysis and Applications",
year = "1977",
volume = "59",
number = "2",
pages = "360--364",
issn = "0022-247x",
mrclass = "60J10 (15A51)",
mrnumber = "0443092 (56 \#1465)",
mrreviewer = "E. Seneta",
zblnumber = "0381.15011",
doi = "10.1016/0022-247X(77)90114-7",
annote = "This paper considers a finite set of stochastic matrices of
finite order. Conditions are given under which any product
of matrices from this set converges to a constant
stochastic matrix. Also, it is shown that the convergence
is exponentially fast.",
}
@BOOK{AKKK:92:e,
author = "Asarin, E. A. and Kozyakin, V. S. and Krasnosel'ski{\u\i},
M. A. and Kuznetsov, N. A.",
authauthor = "Asarin, E. and Kozyakin, Victor and Krasnosel'skii, Mark and
Kuznetsov, N.",
title = "Analiz ustoichivosti rassinkhronizovannykh diskretnykh
sistem",
publisher = "Nauka",
address = "Moscow",
year = "1992",
pages = "408",
isbn = "5-02-006946-9",
mrclass = "93D05 (39A11)",
mrnumber = "1693324",
url = "http://eqworld.ipmnet.ru/ru/library/books/AsarinKozyakinKrasnoselskijKuznecov1992ru.pdf",
note = "In Russian, English title: ``Stability analysis of
desynchronized (asynchronous) discrete-time systems''",
annote = "Control systems with asynchronous data exchange are
considered. The stability theory of such systems (for
various desynchronization classes) is presented. Some
results may be considered as a new chapter of the theory of
matrices. The correctness of the proposed models is also
investigated. Many open problems are set forth. For
engineers, mathematicians and control theorists. In
Russian.",
}
@ARTICLE{AKKK:MCM90,
author = "Asarin, E. A. and Krasnoselskii, M. A. and Kozyakin, V. S.
and Kuznetsov, N. A.",
authauthor = "Asarin, E. and Krasnosel'skii, Mark and Kozyakin, Victor and
Kuznetsov, N.",
title = "On modelling systems with non-synchronously operating
impulse elements",
journal = "Math. Comput. Model.",
fjournal = "Mathematical and Computer Modelling",
year = "1990",
volume = "14",
number = "C",
pages = "70--73",
zblnumber = "0744.93082",
zblreviewer = "E. Eitelberg (Durban)",
doi = "10.1016/0895-7177(90)90149-H",
annote = "Systems with impulse elements operating by some reason
non-synchronously are often used in control science,
technique, economics, ecology etc. To analyze such
desynchronized systems one needs new constructions. Some
results connected with new models and computer methods of
stability analysis are set forth. The methods of stability
analysis of synchronized systems are well developed. As a
computer experiment has demonstrated all the conceivable
effects of synchronized systems loosing, gaining or
conserving stability are possible. So desynchronized
systems require the development of special methods of
stability analysis. In some simple cases the conditions of
stability can be expressed by formulae. In other situations
numerical methods of stability analysis of desynchronized
systems are to be developed. Three situations of this kind
are discussed in detail. 1. Phase and frequency
desynchronized systems, i.e. linear systems with
periodically switched components are considered. 2. It is
discussed, what is to be done if a system is sensitive to
desynchronization (looses stability under
desynchronization). A method to do away with such a
sensitivity is proposed. 3. Stochastically desynchronized
systems are considered.",
}
@ARTICLE{ADFP:93,
author = "Asarin, E. and Diamond, Phil and Fomenko, I. and Pokrovskii,
A.",
title = "Chaotic phenomena in desynchronized systems and stability
analysis",
journal = "Comput. Math. Appl.",
fjournal = "Computers {\&} Mathematics with Applications. An
International Journal",
year = "1993",
volume = "25",
number = "1",
pages = "81--87",
coden = "CMAPDK",
issn = "0898-1221",
mrclass = "58F13 (58F03 58F10 93D05)",
mrnumber = "1192675 (93k:58144)",
mrreviewer = "Peter E. Kloeden",
zblnumber = "0774.93057",
zblreviewer = "T. Duncan (Lawrence)",
doi = "10.1016/0898-1221(93)90214-G",
url = "https://www.sciencedirect.com/science/article/pii/089812219390214G",
annote = "Complex systems tend to be desynchronized, as part and
parcel of their internal organization and internal
connections. One way that this may arise is from quite
small mismatching of operating times of system components.
On the other hand, lack of synchronization can be built
into the system. For example, ``chaotic'' iterations and
asynchronous algorithms are exploited in parallel
processing. Too, a system may be susceptible of change by
numerous factors at different, asynchronous times. In all
cases, it is important to understand the effect that
desynchronization can have on the stability of the system
and the convergence properties of processes.\par We
consider the symbolic dynamics of desynchronized switching
times and extract a numerical quantity whose values
determine the stability characteristics of the system. An
important role in the proof is played by Hilbert's
projective metric.",
}
@INPROCEEDINGS{ACDDHK:STACS15,
author = "Asarin, Eugene and Cervelle, Julien and Degorre, Aldric and
Dima, Catalin and Horn, Florian and Kozyakin, Victor",
editor = "Ollinger, Nicolas and Vollmer, Heribert",
title = "Entropy Games and Matrix Multiplication Games",
booktitle = "33rd Symposium on Theoretical Aspects of Computer Science,
(STACS 2016)",
series = "LIPIcs. Leibniz Int. Proc. Inform.",
publisher = "Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik",
address = "Dagstuhl, Germany",
year = "2016",
volume = "47",
pages = "11:1--11:14",
isbn = "978-3-95977-001-9",
issn = "1868-8969",
mrclass = "91A10 (15A99 68Q25)",
mrnumber = "3539108",
zblnumber = "1390.91016",
hal_id = "hal-01164086",
hal_version = "v3",
doi = "10.4230/LIPIcs.STACS.2016.11",
url = "https://drops.dagstuhl.de/opus/volltexte/2016/5712/",
language = "english",
annote = "Two intimately related new classes of games are introduced
and studied: entropy games (EGs) and matrix multiplication
games (MMGs). An EG is played on a finite arena by
two-and-a-half players: Despot, Tribune and the
non-deterministic People. Despot wants to make the set of
possible People's behaviors as small as possible, while
Tribune wants to make it as large as possible. An MMG is
played by two players that alternately write matrices from
some predefined finite sets. One wants to maximize the
growth rate of the product, and the other to minimize it.
We show that in general MMGs are undecidable in quite a
strong sense. On the positive side, EGs correspond to a
subclass of MMGs, and we prove that such MMGs and EGs are
determined, and that the optimal strategies are simple. The
complexity of solving such games is in
$\mathsf{NP}\cap\mathsf{coNP}$.",
}
@INCOLLECTION{AKKKP:88,
author = "Asarin, {\relax{}Ye}. A. and Kozyakin, V. S. and
Krasnosel'ski{\u\i}, M. A. and Kuznetsov, N. A. and
Pokrovski{\u\i}, A. V.",
authauthor = "Asarin, E. and Kozyakin, Victor and Krasnosel'skii, Mark and
Kuznetsov, N. and Pokrovskii, Alexei",
title = "On some new types of mathematical models of complex
systems",
booktitle = "Modelling and adaptive control ({S}opron, 1986)",
series = "Lecture Notes in Control and Inform. Sci.",
publisher = "Springer",
address = "Berlin",
year = "1988",
volume = "105",
pages = "10--26",
mrclass = "93A10 (93C55 93D20)",
mrnumber = "958694",
zblnumber = "0648.93025",
zblreviewer = "A. Van{\v{e}}{\v{c}}ek",
doi = "10.1007/BFb0043174",
url = "https://link.springer.com/chapter/10.1007/BFb0043174",
annote = "The paper is aimed at consideration of two new models whose
study has just begun. Desynchronized linear models are
introduced as discrete linear models with the state
coordinates changing at different times. Desynchronization
is suggested as the easiest way to attain stability for
some systems. Moreover, the limit hysteresis nonlinearities
are introduced and the averaging principle is studied.",
}
@ARTICLE{ASJ:IEEECSL17,
author = "Athanasopoulos, N. and Smpoukis, K. and Jungers, R. M.",
authauthor = "Athanasopoulos, N. and Smpoukis, K. and Jungers, R.",
title = "Invariant sets analysis for constrained switching systems",
journal = "IEEE Control Systems Letters",
year = "2017",
volume = "1",
number = "2",
pages = "256--261",
month = oct,
issn = "2475-1456",
mrnumber = "4208542",
doi = "10.1109/LCSYS.2017.2714840",
url = "https://ieeexplore.ieee.org/document/7946088/",
annote = "We study discrete time linear constrained switching systems
with additive disturbances, in the general setting where
the switching acts on the system matrices, the disturbance
sets, and the state constraint sets. Our primary goal is to
extend the existing invariant set constructions when the
switching signal is constrained by a given automation. We
achieve it by working with a relaxation of invariance,
namely the multi-set invariance. By exploiting recent
results on computing the stability metrics for these
systems, we establish explicit bounds on the number of
iterations required for each construction. Last, as an
application, we develop new maximal invariant set
constructions for the case of linear systems in far fewer
iterations compared to the state-of-the-art.",
}
@ARTICLE{ABY:CMH10,
author = "Avila, Artur and Bochi, Jairo and Yoccoz, Jean-Christophe",
title = "Uniformly hyperbolic finite-valued {${\rm
SL}(2,\mathbb{R})$}-cocycles",
journal = "Comment. Math. Helv.",
fjournal = "Commentarii Mathematici Helvetici. A Journal of the Swiss
Mathematical Society",
year = "2010",
volume = "85",
number = "4",
pages = "813--884",
eprinttype = "arXiv",
eprint = "0808.0133",
issn = "0010-2571",
mrclass = "37D20 (15B99 37A20 37G35)",
mrnumber = "2718140 (2012c:37050)",
mrreviewer = "M{\'a}rio Bessa",
zblnumber = "1201.37032",
zblreviewer = "Andrzej Piatkowski ({\L}{\'o}d{\'z})",
doi = "10.4171/CMH/212",
url = "https://www.ems-ph.org/journals/show_abstract.php?issn=0010-2571&vol=85&iss=4&rank=4",
annote = "We consider finite families of $\mathit{SL}(2,\mathbb{R})$
matrices whose products display uniform exponential growth.
These form open subsets of $(\mathit{SL}(2,\mathbb{R}))^N$,
and we study their components, boundary, and complement. We
also consider the more general situation where the allowed
products of matrices satisfy a Markovian rule.\par More
precisely, $N$ will be an integer bigger than $1$, and the
base $X=\Sigma\subset N^{\mathbb{Z}}$ will be a transitive
subshift of finite type (also called topological Markov
chain), equipped with the shift map
$\sigma:\Sigma\to\Sigma$. We will only consider cocycles
defined by a map $A:\Sigma\to\mathit{SL}(2,\mathbb{R})$
depending only on the letter in position zero. The
parameter space will be therefore the product
$(\mathit{SL}(2,\mathbb{R}))^N$. The parameters
$(A_1,\ldots ,A_N)$ which correspond to a uniformly
hyperbolic cocycle form an open set $\mathcal{H}$ which is
the object of our study: we would like to describe its
boundary, its connected components, and its complement.
Roughly speaking, we will see that this goal is attained
for the full shift on two symbols, and that new phenomena
appear with at least $3$ symbols which make such a complete
description much more difficult and complicated.",
}
@ARTICLE{AvilaRob:JMD09,
author = "Avila, Artur and Roblin, Thomas",
title = "Uniform exponential growth for some {${\rm
SL}(2,\mathbb{R})$} matrix products",
journal = "J. Mod. Dyn.",
fjournal = "Journal of Modern Dynamics",
year = "2009",
volume = "3",
number = "4",
pages = "549--554",
hal_id = "hal-00365299",
hal_version = "v1",
issn = "1930-5311",
mrclass = "37H15 (37A05 37C85 37D05)",
mrnumber = "2587085 (2011f:37099)",
mrreviewer = "Jairo Bochi",
zblnumber = "1189.37060",
doi = "10.3934/jmd.2009.3.549",
url = "https://www.aimsciences.org/article/doi/10.3934/jmd.2009.3.549",
annote = "Given a hyperbolic matrix $H\in SL(2,\mathbb{R})$, we prove
that for almost every $R\in SL(2,\mathbb{R})$, any product
of length $n$ of $H$ and $R$ grows exponentially fast with
$n$ provided the matrix $R$ occurs less than
$o(\frac{n}{\log n\log\log n})$ times.",
}
@INPROCEEDINGS{CACJ:DLT19,
author = "Azfar, Umer and Catalano, Costanza and Charlier, Ludovic and
Jungers, Rapha{\"e}l M.",
authauthor = "Catalano, Costanza and Azfar, Umer and Charlier, Ludovic and
Jungers, Rapha{\"e}l",
editor = "Hofman, Piotrek and Skrzypczak, Micha{\l}",
title = "A Linear Bound on the $k$-Rendezvous Time for Primitive Sets
of {NZ} Matrices",
booktitle = "Developments in language theory",
series = "Lecture Notes in Comput. Sci.",
publisher = "Springer, Cham",
year = "2019",
volume = "11647",
pages = "59--73",
eprinttype = "arXiv",