{
"id": "1805.06445",
"version": "v1",
"published": "2018-05-16T17:51:14.000Z",
"updated": "2018-05-16T17:51:14.000Z",
"title": "On the Convergence of the SINDy Algorithm",
"authors": [
"Linan Zhang",
"Hayden Schaeffer"
],
"comment": "24 pages, 4 figures, 3 tables",
"categories": [
"math.OC",
"cs.IT",
"math.IT"
],
"abstract": "One way to understand time-series data is to identify the underlying dynamical system which generates it. This task can be done by selecting an appropriate model and a set of parameters which best fits the dynamics while providing the simplest representation (i.e. the smallest amount of terms). One such approach is the sparse identification of nonlinear dynamics framework [6] which uses a sparsity-promoting algorithm that iterates between a partial least-squares fit and a thresholding (sparsity-promoting) step. In this work, we provide some theoretical results on the behavior and convergence of the algorithm proposed in [6]. In particular, we prove that the algorithm approximates local minimizers of an unconstrained $\\ell^0$-penalized least-squares problem. From this, we provide sufficient conditions for general convergence, rate of convergence, and conditions for one-step recovery. Examples illustrate that the rates of convergence are sharp. In addition, our results extend to other algorithms related to the algorithm in [6], and provide theoretical verification to several observed phenomena.",
"revisions": [
{
"version": "v1",
"updated": "2018-05-16T17:51:14.000Z"
}
],
"analyses": {
"keywords": [
"convergence",
"sindy algorithm",
"algorithm approximates local minimizers",
"partial least-squares fit",
"understand time-series data"
],
"note": {
"typesetting": "TeX",
"pages": 24,
"language": "en",
"license": "arXiv",
"status": "editable"
}
}
}