Joint spectral radius
Encyclopedia
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.
the joint spectral radius is defined as follows:
Spectral radius
In mathematics, the spectral radius of a square matrix or a bounded linear operator is the supremum among the absolute values of the elements in its spectrum, which is sometimes denoted by ρ.-Matrices:...
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 the joint spectral radius is defined as follows:-
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 RotaGian-Carlo RotaGian-Carlo Rota was an Italian-born American mathematician and philosopher.-Life:Rota was born in Vigevano, Italy...
and StrangGilbert StrangWilliam Gilbert Strang , usually known as simply Gilbert Strang or Gil Strang, is a renowned American mathematician, with contributions to finite element theory, the calculus of variations, wavelet analysis and linear algebra...
, two mathematicians from MITMassachusetts Institute of TechnologyThe Massachusetts Institute of Technology is a private research university located in Cambridge, Massachusetts. MIT has five schools and one college, containing a total of 32 academic departments, with a strong emphasis on scientific and technological education and research.Founded in 1861 in...
, but started attracting attention with the work of Ingrid DaubechiesIngrid DaubechiesIngrid Daubechies is a Belgian physicist and mathematician. She was between 2004 and 2011 the William R. Kenan Jr. Professor in the mathematics and applied mathematics departments at Princeton University. In January 2011 she moved to Duke University as a Professor in mathematics. She is the first...
and Jeffrey LagariasJeffrey LagariasJeffrey Clark Lagarias is a mathematics professor at the University of Michigan.- Education :While in high school in 1966, Lagarias studied astronomy at the Summer Science Program....
. 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-hardNP-hardNP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
to compute or to approximate, even when the set
consists of only two matrices with all nonzero entries of the two
matrices which are constrained to be equal (Gurvits provides a polynomial-time
algorithm for the case of binary matrices ). Moreover, the question "
" is an undecidable problemUndecidable problemIn computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is impossible to construct a single algorithm that always leads to a correct yes-or-no answer....
. 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.
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 methods approximate the extremal norm with modern optimization techniques, like ellipsoid norm approximation, semidefinite programmingSemidefinite programmingSemidefinite programming is a subfield of convex optimization concerned with the optimization of a linear objective functionover the intersection of the cone of positive semidefinite matrices with an affine space, i.e., a spectrahedron....
, Sum Of SquaresPolynomial SOSIn mathematics, a form h of degree 2m in the real n-dimensional vector x is sum of squares of forms if and only if there exist forms g_1,\ldots,g_k of degree m such that...
, conic programmingConic optimizationConic optimization is a subfield of convex optimization that studies a class of structured convex optimization problems called conic optimization problems...
. 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
there is a product 
of matrices in this set such that
"
In the above equation "
" refers to the classical spectral radiusSpectral radiusIn mathematics, the spectral radius of a square matrix or a bounded linear operator is the supremum among the absolute values of the elements in its spectrum, which is sometimes denoted by ρ.-Matrices:...
of the matrix
This conjecture, proposed in 1995, has been proved 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 systemsDynamical systemA dynamical system is a concept in mathematics where a fixed rule describes the time dependence of a point in a geometrical space. Examples include the mathematical models that describe the swinging of a clock pendulum, the flow of water in a pipe, and the number of fish each springtime in a...
. Indeed, the system defined by the equations
is stableLyapunov stabilityVarious types of stability may be discussed for the solutions of differential equations describing dynamical systems. The most important type is that concerning the stability of solutions near to a point of equilibrium. This may be discussed by the theory of Lyapunov...
if and only if
The joint spectral radius became popular when Ingrid DaubechiesIngrid DaubechiesIngrid Daubechies is a Belgian physicist and mathematician. She was between 2004 and 2011 the William R. Kenan Jr. Professor in the mathematics and applied mathematics departments at Princeton University. In January 2011 she moved to Duke University as a Professor in mathematics. She is the first...
and Jeffrey LagariasJeffrey LagariasJeffrey Clark Lagarias is a mathematics professor at the University of Michigan.- Education :While in high school in 1966, Lagarias studied astronomy at the Summer Science Program....
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 agentsAutonomous agentAn autonomous agent is an intelligent agent operating on an owner's behalf but without any interference of that ownership entity. An intelligent agent, however appears according to a multiply cited statement in a no longer accessible IBM white paper as follows:Intelligent agents are software...
consensus, combinatorics on wordsCombinatorics on wordsCombinatorics on words is a branch of mathematics which applies combinatorics to words and formal languages. The study of combinatorics on words arose independently within several branches of mathematics, e.g. number theory, group theory and probability...
,...
Related notions
The joint spectral radius is the generalization of the spectral radiusSpectral radiusIn mathematics, the spectral radius of a square matrix or a bounded linear operator is the supremum among the absolute values of the elements in its spectrum, which is sometimes denoted by ρ.-Matrices:...
of a matrix for a set of several matrices. However, much 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
.
The p-radius characterizes the rate of growth of the
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.
External links
- The JSR toolbox A matlab implementation of the various algorithms for computing the JSR