Our paper on non-monotonic Lyapunov functions [1] and our paper on simultaneous state and sparse input recovery [2] have been accepted to the Conference on Decision and Control 2023!
[1]
![[doi]](https://mallada.ece.jhu.edu/wp-content/plugins/papercite/img/external.png)
R. Siegelmann, Y. Shen, F. Paganini, and E. Mallada, “A Recurrence-based Direct Method for Stability Analysis and GPU-based Verification of Non-monotonic Lyapunov Functions,” in
62nd IEEE Conference on Decision and Control (CDC), 2023, pp. 6665-6672.
[Bibtex] [Abstract] [Download PDF]
Lyapunov direct method is a powerful tool that provides a rigorous framework for stability analysis and control design for dynamical systems. A critical step that enables the application of the method is the existence of a Lyapunov function $V$—a function whose value monotonically decreases along the trajectories of the dynamical system. Unfortunately, finding a Lyapunov function is often tricky and requires ingenuity, domain knowledge, or significant computational power. At the core of this challenge is the fact that the method requires every sub-level set of $V$ ($V_łeq c$) to be forward invariant, thus implicitly coupling the geometry of $V_łeq c$ and the trajectories of the system. In this paper, we seek to disentangle this dependence by developing a direct method that substitutes the concept of invariance with a more flexible notion known as recurrence. A set is ($τ$-)recurrent if every trajectory that starts in the set returns to it (within $τ$ seconds) infinitely often. We show that, under mild conditions, the recurrence of level sub-level sets is sufficient to guarantee stability, asymptotic stability, and exponential stability. We further provide a GPU-based algorithm that can to verify whether $V$ satisfies such conditions up to an arbitrarily small subset of the equilibrium.
@inproceedings{sspm2023cdc,
abstract = {Lyapunov direct method is a powerful tool that provides a rigorous framework for stability analysis and control design for dynamical systems. A critical step that enables the application of the method is the existence of a Lyapunov function $V$---a function whose value monotonically decreases along the trajectories of the dynamical system. Unfortunately, finding a Lyapunov function is often tricky and requires ingenuity, domain knowledge, or significant computational power. At the core of this challenge is the fact that the method requires every sub-level set of $V$ ($V_łeq c$) to be forward invariant, thus implicitly coupling the geometry of $V_łeq c$ and the trajectories of the system. In this paper, we seek to disentangle this dependence by developing a direct method that substitutes the concept of invariance with a more flexible notion known as recurrence. A set is ($τ$-)recurrent if every trajectory that starts in the set returns to it (within $τ$ seconds) infinitely often. We show that, under mild conditions, the recurrence of level sub-level sets is sufficient to guarantee stability, asymptotic stability, and exponential stability. We further provide a GPU-based algorithm that can to verify whether $V$ satisfies such conditions up to an arbitrarily small subset of the equilibrium.},
author = {Siegelmann, Roy and Shen, Yue and Paganini, Fernando and Mallada, Enrique},
bdsk-url-3 = {https://doi.org/10.1109/CDC49753.2023.10383373},
booktitle = {62nd IEEE Conference on Decision and Control (CDC)},
doi = {10.1109/CDC49753.2023.10383373},
grants = {CPS-2136324, CAREER-1752362, EPICS-2330450},
month = {12},
organization = {IEEE},
pages = {6665--6672},
record = {presented, accepted Jul 2023, submitted Mar 2023},
title = {A Recurrence-based Direct Method for Stability Analysis and GPU-based Verification of Non-monotonic Lyapunov Functions},
url = {https://mallada.ece.jhu.edu/pubs/2023-CDC-SSPM.pdf},
year = {2023}
}
[2]
K. Poe, E. Mallada, and R. Vidal, “Necessary and Sufficient Conditions for Simultaneous State and Input Recovery of Linear Systems with Sparse Inputs by $\ell_1$-Minimization,” in
62nd IEEE Conference on Decision and Control (CDC), 2023, pp. 6499-6506.
[Bibtex] [Abstract] [Download PDF]
The study of theoretical conditions for recovering sparse signals from compressive measurements has received a lot of attention in the research community. In parallel, there has been a great amount of work characterizing conditions for the recovery both the state and the input to a linear dynamical system (LDS), including a handful of results on recovering sparse inputs. However, existing sufficient conditions for recovering sparse inputs to an LDS are conservative and hard to interpret, while necessary and sufficient conditions have not yet appeared in the literature. In this work, we provide (1) the first characterization of necessary and sufficient conditions for the existence and uniqueness of sparse inputs to an LDS, (2) the first necessary and sufficient conditions for a linear program to recover both an unknown initial state and a sparse input, and (3) simple, interpretable recovery conditions in terms of the LDS parameters. We conclude with a numerical validation of these claims and discuss implications and future directions.
@inproceedings{pmv2023cdc,
abstract = {The study of theoretical conditions for recovering sparse signals from compressive measurements has received a lot of attention in the research community. In parallel, there has been a great amount of work characterizing conditions for the recovery both the state and the input to a linear dynamical system (LDS), including a handful of results on recovering sparse inputs. However, existing sufficient conditions for recovering sparse inputs to an LDS are conservative and hard to interpret, while necessary and sufficient conditions have not yet appeared in the literature. In this work, we provide (1) the first characterization of necessary and sufficient conditions for the existence and uniqueness of sparse inputs to an LDS, (2) the first necessary and sufficient conditions for a linear program to recover both an unknown initial state and a sparse input, and (3) simple, interpretable recovery conditions in terms of the LDS parameters. We conclude with a numerical validation of these claims and discuss implications and future directions.
},
author = {Poe, Kyle and Mallada, Enrique and Vidal, Rene},
bdsk-url-3 = {https://doi.org/10.1109/CDC49753.2023.10383682},
booktitle = {62nd IEEE Conference on Decision and Control (CDC)},
doi = {10.1109/CDC49753.2023.10383682},
grants = {CPS-2136324,CAREER-1752362},
month = {12},
pages = {6499--6506},
record = {presented, accepted Jul 2023, submitted Mar 2023},
title = {Necessary and Sufficient Conditions for Simultaneous State and Input Recovery of Linear Systems with Sparse Inputs by $\ell_1$-Minimization},
url = {https://mallada.ece.jhu.edu/pubs/2023-CDC-PMV.pdf},
year = {2023}
}