Nonconvex Linear System Identification with Minimal State Representation

• URL: http://arxiv.org/abs/2504.18791v1
• Date: Sat, 26 Apr 2025 04:11:02 GMT
• Title: Nonconvex Linear System Identification with Minimal State Representation
• Authors: Uday Kiran Reddy Tadipatri, Benjamin D. Haeffele, Joshua Agterberg, Ingvar Ziemann, René Vidal,
• Abstract summary: Low-order linear System IDent (SysID) addresses the challenge of estimating the parameters of a linear dynamical system from finite samples of inputs with minimal state observations.
• Score: 34.203983563629144
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Low-order linear System IDentification (SysID) addresses the challenge of estimating the parameters of a linear dynamical system from finite samples of observations and control inputs with minimal state representation. Traditional approaches often utilize Hankel-rank minimization, which relies on convex relaxations that can require numerous, costly singular value decompositions (SVDs) to optimize. In this work, we propose two nonconvex reformulations to tackle low-order SysID (i) Burer-Monterio (BM) factorization of the Hankel matrix for efficient nuclear norm minimization, and (ii) optimizing directly over system parameters for real, diagonalizable systems with an atomic norm style decomposition. These reformulations circumvent the need for repeated heavy SVD computations, significantly improving computational efficiency. Moreover, we prove that optimizing directly over the system parameters yields lower statistical error rates, and lower sample complexities that do not scale linearly with trajectory length like in Hankel-nuclear norm minimization. Additionally, while our proposed formulations are nonconvex, we provide theoretical guarantees of achieving global optimality in polynomial time. Finally, we demonstrate algorithms that solve these nonconvex programs and validate our theoretical claims on synthetic data.

Related papers

• The Inductive Bias of Flatness Regularization for Deep Matrix Factorization [58.851514333119255]
  This work takes the first step toward understanding the inductive bias of the minimum trace of the Hessian solutions in deep linear networks. We show that for all depth greater than one, with the standard Isometry Property (RIP) on the measurements, minimizing the trace of Hessian is approximately equivalent to minimizing the Schatten 1-norm of the corresponding end-to-end matrix parameters.
  arXiv  Detail & Related papers  (2023-06-22T23:14:57Z)
• Direct Estimation of Parameters in ODE Models Using WENDy: Weak-form Estimation of Nonlinear Dynamics [0.0]
  We introduce the Weak-form Estimation of Dynamics (WENDy) method for estimating model parameters for non-linear systems of ODEs. WENDy computes accurate estimates and is robust to large (biologically relevant) levels of measurement noise. We demonstrate the high robustness and computational efficiency by applying WENDy to estimate parameters in some common models from population biology, neuroscience, and biochemistry.
  arXiv  Detail & Related papers  (2023-02-26T08:49:34Z)
• System Identification via Nuclear Norm Regularization [44.9687872697492]
  This paper studies the problem of identifying low-order linear systems via Hankel nuclear norm regularization. We provide novel statistical analysis for this regularization and carefully contrast it with the unregularized ordinary least-squares (OLS) estimator.
  arXiv  Detail & Related papers  (2022-03-30T20:56:27Z)
• Efficient learning of hidden state LTI state space models of unknown order [0.7614628596146599]
  We address two related estimation problems arising in the setup of hidden state linear time invariant (LTI) state space systems. Namely, the estimation of any finite number of the system's Markov parameters and the estimation of a minimal realization for the system. For both problems, we provide statistical guarantees in the form of various estimation error upper bounds, $rank$ recovery conditions, and sample complexity estimates.
  arXiv  Detail & Related papers  (2022-02-03T14:59:13Z)
• Unified Convergence Analysis for Adaptive Optimization with Moving Average Estimator [75.05106948314956]
  We show that an increasing large momentum parameter for the first-order moment is sufficient for adaptive scaling.<n>We also give insights for increasing the momentum in a stagewise manner in accordance with stagewise decreasing step size.
  arXiv  Detail & Related papers  (2021-04-30T08:50:24Z)
• Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
  We propose a simple and efficient unsupervised feature selection method, by combining reconstruction error with $l_2,p$-norm regularization. We present an efficient optimization algorithm to solve the proposed unsupervised model, and analyse the convergence and computational complexity of the algorithm theoretically.
  arXiv  Detail & Related papers  (2020-12-29T04:08:38Z)
• Reduction of the Number of Variables in Parametric Constrained Least-Squares Problems [0.20305676256390928]
  This paper proposes techniques for reducing the number of involved optimization variables. We show the good performance of the proposed techniques in numerical tests and in a linearized MPC problem of a nonlinear benchmark process.
  arXiv  Detail & Related papers  (2020-12-18T18:26:40Z)
• A Scalable, Adaptive and Sound Nonconvex Regularizer for Low-rank Matrix Completion [60.52730146391456]
  We propose a new non scalable low-rank regularizer called "nuclear Frobenius norm" regularizer, which is adaptive and sound. It bypasses the computation of singular values and allows fast optimization by algorithms. It obtains state-of-the-art recovery performance while being the fastest in existing matrix learning methods.
  arXiv  Detail & Related papers  (2020-08-14T18:47:58Z)
• Understanding Implicit Regularization in Over-Parameterized Single Index Model [55.41685740015095]
  We design regularization-free algorithms for the high-dimensional single index model. We provide theoretical guarantees for the induced implicit regularization phenomenon.
  arXiv  Detail & Related papers  (2020-07-16T13:27:47Z)
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization [56.05635751529922]
  We propose a new randomized algorithm for solving L2-regularized least-squares problems based on sketching. We consider two of the most popular random embeddings, namely, Gaussian embeddings and the Subsampled Randomized Hadamard Transform (SRHT)
  arXiv  Detail & Related papers  (2020-06-10T15:00:09Z)
• Loss landscapes and optimization in over-parameterized non-linear systems and neural networks [20.44438519046223]
  We show that wide neural networks satisfy the PL$*$ condition, which explains the (S)GD convergence to a global minimum. We show that wide neural networks satisfy the PL$*$ condition, which explains the (S)GD convergence to a global minimum.
  arXiv  Detail & Related papers  (2020-02-29T17:18:28Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.