- Source: Joint spectral radius
In mathematics, the joint spectral radius is a generalization of the classical notion of spectral radius of a matrix, to sets of matrices. In recent years this notion has found applications in a large number of engineering fields and is still a topic of active research.
General description
The joint spectral radius of a set of matrices is the maximal asymptotic growth rate of products of matrices taken in that set. For a finite (or more generally compact) set of matrices
M
=
{
A
1
,
…
,
A
m
}
⊂
R
n
×
n
,
{\displaystyle {\mathcal {M}}=\{A_{1},\dots ,A_{m}\}\subset \mathbb {R} ^{n\times n},}
the joint spectral radius is defined as follows:
ρ
(
M
)
=
lim
k
→
∞
max
{
‖
A
i
1
⋯
A
i
k
‖
1
/
k
:
A
i
∈
M
}
.
{\displaystyle \rho ({\mathcal {M}})=\lim _{k\to \infty }\max {\{\|A_{i_{1}}\cdots A_{i_{k}}\|^{1/k}:A_{i}\in {\mathcal {M}}\}}.\,}
It can be proved that the limit exists and that the quantity actually does not depend on the chosen matrix norm (this is true for any norm but particularly easy to see if the norm is sub-multiplicative). The joint spectral radius was introduced in 1960 by Gian-Carlo Rota and Gilbert Strang, two mathematicians from MIT, but started attracting attention with the work of Ingrid Daubechies and Jeffrey Lagarias. They showed that the joint spectral radius can be used to describe smoothness properties of certain wavelet functions. A wide number of applications have been proposed since then. It is known that the joint spectral radius quantity is NP-hard to compute or to approximate, even when the set
M
{\displaystyle {\mathcal {M}}}
consists of only two matrices with all nonzero entries of the two
matrices which are constrained to be equal. Moreover, the question "
ρ
≤
1
?
{\displaystyle \rho \leq 1?}
" is an undecidable problem. Nevertheless, in recent years much progress has been done on its understanding, and it appears that in practice the joint spectral radius can often be computed to satisfactory precision, and that it moreover can bring interesting insight in engineering and mathematical problems.
Computation
= Approximation algorithms
=In spite of the negative theoretical results on the joint spectral radius computability, methods have been proposed that perform well in practice. Algorithms are even known, which can reach an arbitrary accuracy in an a priori computable amount of time. These algorithms can be seen as trying to approximate the unit ball of a particular vector norm, called the extremal norm. One generally distinguishes between two families of such algorithms: the first family, called polytope norm methods, construct the extremal norm by computing long trajectories of points. An advantage of these methods is that in the favorable cases it can find the exact value of the joint spectral radius and provide a certificate that this is the exact value.
The second family of methods approximate the extremal norm with modern optimization techniques, such as ellipsoid norm approximation, semidefinite programming, Sum Of Squares, and conic programming. The advantage of these methods is that they are easy to implement, and in practice, they provide in general the best bounds on the joint spectral radius.
= The finiteness conjecture
=Related to the computability of the joint spectral radius is the following conjecture:
"For any finite set of matrices
M
⊂
R
n
×
n
,
{\displaystyle {\mathcal {M}}\subset \mathbb {R} ^{n\times n},}
there is a product
A
1
…
A
t
{\displaystyle A_{1}\dots A_{t}}
of matrices in this set such that
ρ
(
M
)
=
ρ
(
A
1
…
A
t
)
1
/
t
.
{\displaystyle \rho ({\mathcal {M}})=\rho (A_{1}\dots A_{t})^{1/t}.}
"
In the above equation "
ρ
(
A
1
…
A
t
)
{\displaystyle \rho (A_{1}\dots A_{t})}
" refers to the classical spectral radius of the matrix
A
1
…
A
t
.
{\displaystyle A_{1}\dots A_{t}.}
This conjecture, proposed in 1995, was proven to be false in 2003. The counterexample provided in that reference uses advanced measure-theoretical ideas. Subsequently, many other counterexamples have been provided, including an elementary counterexample that uses simple combinatorial properties matrices and a counterexample based on dynamical systems properties. Recently an explicit counterexample has been proposed in. Many questions related to this conjecture are still open, as for instance the question of knowing whether it holds for pairs of binary matrices.
Applications
The joint spectral radius was introduced for its interpretation as a stability condition for discrete-time switching dynamical systems. Indeed, the system defined by the equations
x
t
+
1
=
A
t
x
t
,
A
t
∈
M
∀
t
{\displaystyle x_{t+1}=A_{t}x_{t},\quad A_{t}\in {\mathcal {M}}\,\forall t}
is stable if and only if
ρ
(
M
)
<
1.
{\displaystyle \rho ({\mathcal {M}})<1.}
The joint spectral radius became popular when Ingrid Daubechies and Jeffrey Lagarias showed that it rules the continuity of certain wavelet functions. Since then, it has found many applications, ranging from number theory to information theory, autonomous agents consensus, combinatorics on words,...
Related notions
The joint spectral radius is the generalization of the spectral radius of a matrix for a set of several matrices. However, many more quantities can be defined when considering a set of matrices: The joint spectral subradius characterizes the minimal rate of growth of products in the semigroup generated by
M
{\displaystyle {\mathcal {M}}}
.
The p-radius characterizes the rate of growth of the
L
p
{\displaystyle L_{p}}
average of the norms of the products in the semigroup.
The Lyapunov exponent of the set of matrices characterizes the rate of growth of the geometric average.
References
Further reading
Raphael M. Jungers (2009). The joint spectral radius, Theory and applications. Springer. ISBN 978-3-540-95979-3.
Vincent D. Blondel; Michael Karow; Vladimir Protassov; Fabian R. Wirth, eds. (2008). "Linear Algebra and its Applications: special issue on the joint spectral radius". Linear Algebra and Its Applications. 428 (10). Elsevier.
Antonio Cicone (2011). "PhD thesis. Spectral Properties of Families of Matrices. Part III" (PDF).
Jacques Theys (2005). "PhD thesis. Joint Spectral Radius: Theory and approximations" (PDF). Archived from the original (PDF) on 2007-06-13.
Kata Kunci Pencarian:
- Eurofighter Typhoon
- Joint spectral radius
- Spectral radius
- JSR
- Gilbert Strang
- Hybrid system
- Gian-Carlo Rota
- Lyapunov stability
- Numerical range
- Proton
- Brown dwarf
