Stability in linear dynamical systems

This Bodes well



The intersection of linear dynamical systems and stability of dynamic systems.

Related: detecting non-stationarity.

There is not much content here because I spent 2 years working on it and am too traumatised to revisit it.

Informally, I am admitting as β€œstable” any dynamical system which does not explode super-polynomially fast; We can think of these as systems where if the system is not stationary then at least the rate of change might be.

Energy-preserving systems are a special case of this.

There are many problems I am interested in that touch upon this.

Pole representations

In the univariate, discrete-time case, in discrete-time linear systems terms, these are systems that have no poles outside the unit circle, but might have poles on the unit circle. In continuous time it is about systems that have no poles with positive real part. For finitely realizable systems this boils down to tracking trigonometric roots, e.g. Megretski (2003).

In a multivariate context we might consider eigenvalues of the transfer matrix in a similar light.

van Handel (2017) for example mention the standard result that the eigenvalues of a symmetric matrix \(X\) are the roots of the characteristic polynomial \(\chi(t)=\operatorname{det}(t I-X)\) and, equivalently, the poles of the Stieltjes transform \(s(t):=\operatorname{Tr}\left[(t I-X)^{-1}\right]=\frac{d}{d t} \log \chi(t)\)

Reparameterisation

We can use cunning reparameterisation to keep systems stable. This Betancourt podcast on Sarah Heaps’ paper (Heaps 2020) on parameterising stationarity in vector auto regressions is deep and IMO points the way to some other neat tricks in neural nets. She constructs interesting priors for this case, using some reparametrisations by Ansley and Kohn (1986).

Maybe related: Roy, Mcelroy, and Linton (2019)

Continuous time

TBC.

Stability and gradient descent

What if we are incrementally learning a system and wish the gradient descent steps not to push it away from stability? In such a case, we can possibly side-step the problem by using a topology which maximises system stability (Laroche 2007).

References

Ahn, Sungjin, Anoop Korattikara, and Max Welling. 2012. β€œBayesian Posterior Sampling via Stochastic Gradient Fisher Scoring.” In Proceedings of the 29th International Coference on International Conference on Machine Learning, 1771–78. ICML’12. Madison, WI, USA: Omnipress.
Alexos, Antonios, Alex J. Boyd, and Stephan Mandt. 2022. β€œStructured Stochastic Gradient MCMC.” In Proceedings of the 39th International Conference on Machine Learning, 414–34. PMLR.
Ansley, Craig F., and Robert Kohn. 1986. β€œA Note on Reparameterizing a Vector Autoregressive Moving Average Model to Enforce Stationarity.” Journal of Statistical Computation and Simulation 24 (2): 99–106.
Bishop, Adrian N., and Pierre Del Moral. 2016. β€œOn the Stability of Kalman-Bucy Diffusion Processes.” SIAM Journal on Control and Optimization 55 (6): 4015–47.
Carini, A., V.J. Mathews, and G.L. Sicuranza. 1999. β€œSufficient Stability Bounds for Slowly Varying Direct-Form Recursive Linear Filters and Their Applications in Adaptive IIR Filters.” IEEE Transactions on Signal Processing 47 (9): 2561–67.
Chen, Tianqi, Emily Fox, and Carlos Guestrin. 2014. β€œStochastic Gradient Hamiltonian Monte Carlo.” In Proceedings of the 31st International Conference on Machine Learning, 1683–91. Beijing, China: PMLR.
Chen, Zaiwei, Shancong Mou, and Siva Theja Maguluri. 2021. β€œStationary Behavior of Constant Stepsize SGD Type Algorithms: An Asymptotic Characterization.” arXiv.
Del Moral, P., A. Kurtzmann, and J. Tugaut. 2017. β€œOn the Stability and the Uniform Propagation of Chaos of a Class of Extended Ensemble Kalman-Bucy Filters.” SIAM Journal on Control and Optimization 55 (1): 119–55.
Dumitrescu, Bogdan. 2017. Positive trigonometric polynomials and signal processing applications. Second edition. Signals and communication technology. Cham: Springer.
Geronimo, Jeffrey S., and Hugo J. Woerdeman. 2004. β€œPositive Extensions, FejΓ©r-Riesz Factorization and Autoregressive Filters in Two Variables.” Annals of Mathematics 160 (3): 839–906.
Gu, Albert, Isys Johnson, Karan Goel, Khaled Saab, Tri Dao, Atri Rudra, and Christopher RΓ©. 2021. β€œCombining Recurrent, Convolutional, and Continuous-Time Models with Linear State Space Layers.” In Advances in Neural Information Processing Systems, 34:572–85. Curran Associates, Inc.
Handel, Ramon van. 2017. β€œStructured Random Matrices.” In Convexity and Concentration, edited by Eric Carlen, Mokshay Madiman, and Elisabeth M. Werner, 107–56. The IMA Volumes in Mathematics and Its Applications. New York, NY: Springer.
Hardt, Moritz, Tengyu Ma, and Benjamin Recht. 2018. β€œGradient Descent Learns Linear Dynamical Systems.” The Journal of Machine Learning Research 19 (1): 1025–68.
Heaps, Sarah E. 2020. β€œEnforcing Stationarity Through the Prior in Vector Autoregressions.” arXiv:2004.09455 [Stat], April.
Kuznetsov, Vitaly, and Mehryar Mohri. 2014. β€œGeneralization Bounds for Time Series Prediction with Non-Stationary Processes.” In Algorithmic Learning Theory, edited by Peter Auer, Alexander Clark, Thomas Zeugmann, and Sandra Zilles, 260–74. Lecture Notes in Computer Science. Bled, Slovenia: Springer International Publishing.
Laroche, Jean. 2007. β€œOn the Stability of Time-Varying Recursive Filters.” Journal of the Audio Engineering Society 55 (6): 460–71.
Mandt, Stephan, Matthew D. Hoffman, and David M. Blei. 2017. β€œStochastic Gradient Descent as Approximate Bayesian Inference.” JMLR, April.
Mattingley, J., and S. Boyd. 2010. β€œReal-Time Convex Optimization in Signal Processing.” IEEE Signal Processing Magazine 27 (3): 50–61.
Maxwell, J. Clerk. 1867. β€œOn Governors.” Proceedings of the Royal Society of London 16 (January): 270–83.
Megretski, A. 2003. β€œPositivity of Trigonometric Polynomials.” In 42nd IEEE International Conference on Decision and Control (IEEE Cat. No.03CH37475), 4:3814–3817 vol.4.
Menzer, Fritz, and Christof Faller. 2010. β€œUnitary Matrix Design for Diffuse Jot Reverberators.”
Oliveira, MaurΓ­cio C. de, and Robert E. Skelton. 2001. β€œStability Tests for Constrained Linear Systems.” In Perspectives in Robust Control, 241–57. Lecture Notes in Control and Information Sciences. Springer, London.
Regalia, P., and M. Sanjit. 1989. β€œKronecker Products, Unitary Matrices and Signal Processing Applications.” SIAM Review 31 (4): 586–613.
Roy, Anindya, Tucker S. Mcelroy, and Peter Linton. 2019. β€œConstrained Estimation of Causal Invertible VARMA.” Statistica Sinica 29 (1): 455–78.
Seuret, Alexandre, and FrΓ©dΓ©ric Gouaisbaut. 2013. β€œWirtinger-Based Integral Inequality: Application to Time-Delay Systems.” Automatica 49 (9): 2860–66.
Simchowitz, Max, Horia Mania, Stephen Tu, Michael I. Jordan, and Benjamin Recht. 2018. β€œLearning Without Mixing: Towards A Sharp Analysis of Linear System Identification.” arXiv:1802.08334 [Cs, Math, Stat], February.
Tilma, Todd, and E C G Sudarshan. 2002. β€œGeneralized Euler Angle Paramterization for SU(N).” Journal of Physics A: Mathematical and General 35 (48): 10467–501.

No comments yet. Why not leave one?

GitHub-flavored Markdown & a sane subset of HTML is supported.