Lyapunov Exponent of Rank-One Matrices: Ergodic Formula and Inapproximability of the Optimal Distribution

DOI10.1137/19M1264072MaRDI QIDQ5217944zbMATH OpenWikidataFDO

Authors Pablo A. Parrilo, Jason M. Altschuler

Publication date 26 February 2020

Published in SIAM Journal on Control and Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1905.07531, https://epubs.siam.org/doi/pdf/10.1137/19M1264072

zbMATH Keywords

asymptotic stabilityhardness of approximationLyapunov exponentstochastic linear dynamical system

Mathematics Subject Classification ID

Asymptotic stability in control theory (93D20) Stochastic stability in control theory (93E15)

Abstract: The Lyapunov exponent corresponding to a set of square matrices $mathcalA=A_1,dots,A_n$ and a probability distribution $p$ over $1,dots,n$ is $lambda(mathcalA,p):=li{m}_{koinfty}frac1k,mathbbElog|A_{sigm{a}_k}cdots{A}_{sigm{a}_2}{A}_{sigm{a}_1}|$, where $sigm{a}_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(mathcalA,p)}$ of the stochastic linear dynamical system $x_{k+1}=A_{sigm{a}_k}{x}_k$. This paper investigates the following "design problem": given $mathcalA$, compute the distribution $p$ minimizing $lambda(mathcalA,p)$. Our main result is that it is NP-hard to decide whether there exists a distribution $p$ for which $lambda(mathcalA,p)<0$, i.e. it is NP-hard to decide whether this dynamical system can be stabilized. This hardness result holds even in the "simple"' case where $mathcalA$ 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. 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 $pmapstolambda(mathcalA,p)$ is neither convex nor concave in general. We conclude with extensions to continuous distributions, exchangeable processes, Markov processes, and stationary ergodic processes.

Recommendations

• The distribution of Lyapunov exponents: Exact results for random matrices
• scientific article; zbMATH DE number 919606
• scientific article; zbMATH DE number 3936077
• scientific article; zbMATH DE number 19548
• Exact Lyapunov exponent for infinite products of random matrices
• Lower and upper bounds for the largest Lyapunov exponent of matrices
• Asymptotic Lyapunov exponents for large random matrices
• scientific article; zbMATH DE number 1409835
• Invariant functions for the Lyapunov exponents of random matrices
• Uniformity of Lyapunov exponents for non-invertible matrices

Cites work

• A characterization of the minimum cycle mean in a digraph
• A hybrid method for computing Lyapunov exponents
• A PTAS for the minimization of polynomials of fixed degree over the simplex
• An Algorithm for Restricted Least Squares Regression
• An upper bound for the largest Lyapunov exponent of a Markovian product of nonnegative matrices
• Approximation of the joint spectral radius using sum of squares
• Bounds on Lyapunov Exponents via Entropy Accumulation
• Encyclopedia of Distances
• Exact computation of joint spectral characteristics of linear operators
• Generic properties of the lower spectral radius for some low-rank pairs of matrices
• scientific article; zbMATH DE number 5454133 (Why is no real title available?)
• scientific article; zbMATH DE number 2079140 (Why is no real title available?)
• Iterated Random Functions
• Joint spectral characteristics of matrices: a conic programming approach
• Joint spectral radius and path-complete graph Lyapunov functions
• Lectures on Lyapunov exponents
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Lower bounds for the maximal Lyapunov exponent
• Lyapunov Spectral Intervals: Theory and Computation
• Maxima for Graphs and a New Proof of a Theorem of Turán
• Noncommuting Random Products
• On some inequalities for the gamma and psi functions
• On the regularity of de Rham curves
• Overlap-free words and spectra of matrices
• Perturbation theory for approximation of Lyapunov exponents by QR methods
• Probability and random processes.
• Probability. Theory and examples.
• Products of Random Matrices
• Random Matrices and Their Applications
• Random walks on reductive groups
• Rank-one characterization of joint spectral radius of finite matrix family
• Subadditivity, Generalized Products of Random Matrices and Operations Research
• Symmetric Measures on Cartesian Products
• The boundedness of all products of a pair of matrices is undecidable
• The generalized joint spectral radius. A geometric approach
• The Lyapunov exponent and joint spectral radius of pairs of matrices are hard - when not impossible - to compute and to approximate

Cited in

(5)

• Optimal control problem for the Lyapunov exponents of random matrix products
• Approximating min-mean-cycle for low-diameter graphs in near-optimal time and memory
• Uniqueness of ergodic optimization of top Lyapunov exponent for typical matrix cocycles
• Convergence rate of Markov chains over switching distance regular networks
• Computation of Lyapunov exponents of matrix products

This page was built for publication: Lyapunov Exponent of Rank-One Matrices: Ergodic Formula and Inapproximability of the Optimal Distribution

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5217944)