Approximating the nearest stable discrete-time system

Nicolas Gillis, Michael Karow, Punit Sharma

TL;DR

This paper introduces a novel way to find the "nearest" stable version of an unstable discrete-time linear system. By re-characterizing stable matrices using a new "SUB" factorization ($A = S^{-1}UBS$), the authors transform a notoriously difficult non-convex optimization problem into one that can be solved efficiently using a fast projected gradient method, outperforming previous state-of-the-art heuristics in both speed and accuracy.

What Problem Does This Paper Address?

In control theory and system identification, we often model processes using discrete-time linear systems: $x(t+1) = Ax(t)$. For the system to be "stable" (meaning it doesn't blow up over time), the eigenvalues of the matrix $A$ must reside within or on the unit circle of the complex plane.

However, real-world data is noisy. You might identify a system from observations only to find that the resulting matrix $A$ is slightly unstable. The challenge is to find a stable matrix $X$ that is as close as possible to your original $A$ (typically measured by the Frobenius norm). This is a "notoriously difficult" problem because the set of stable matrices is non-convex and neither open nor closed, leading to optimization landscapes filled with local minima.

Methods

The authors' primary contribution is a new characterization of the set of stable matrices. They prove that a matrix $A$ is stable if and only if it admits a SUB form: $$A = S^{-1}UBS$$ Where:

  • $S$ is a positive definite matrix (defining a coordinate transformation).
  • $U$ is an orthogonal matrix.
  • $B$ is a positive semidefinite contraction (its singular values are $\le 1$).

This factorization is powerful because it breaks the complex "stability" constraint into three simpler constraints. The authors then propose a Fast Projected Gradient Method (FGM) to minimize the distance $\|A - S^{-1}UBS\|_F^2$.

Key technical highlights include:

  • Efficient Projections: The authors derive explicit formulas to project onto the sets of orthogonal matrices and semidefinite contractions.
  • Acceleration: They use Nesterov-style acceleration with a "restart" strategy to speed up convergence.
  • Initialization: Since the problem is non-convex, starting points matter. They propose three strategies: a standard polar decomposition, an LMI-based (Lyapunov) approach, and a multi-start random heuristic.

Datasets

As a theoretical and algorithmic paper, it evaluates its performance on specific matrix structures known to be challenging in numerical linear algebra:

  • Grcar Matrices: Banded Toeplitz matrices whose eigenvalues naturally sit outside the unit circle.
  • Scaled All-One Matrices: Rank-one matrices used to test the algorithm's ability to find global vs. local minima.
  • Literature Benchmarks: Specific 3x3 and 5x5 unstable matrices pulled from previous studies (e.g., Guglielmi & Protasov, 2018) to compare error rates directly.

Key Insights and Ideas

  • The Power of Parameterization: Instead of trying to optimize $X$ directly under a messy constraint, changing the variables to $(S, U, B)$ makes the feasible set "easy" to project onto. This is a classic optimization trick applied here to a new domain.
  • Non-Convexity isn't a Dealbreaker: While the problem remains non-convex, the SUB form creates a landscape where first-order methods (like FGM) can find high-quality local optima very quickly.
  • Scalability: Previous methods (like successive convex approximation) were second-order and struggled with matrices larger than $n=50$. Because FGM only requires $O(n^3)$ operations per iteration (mostly matrix multiplications and SVDs), it can handle matrices with $n=1000$ on a standard laptop.

Key Results

  • Superior Accuracy: On Grcar matrices, the FGM approach consistently found lower relative errors than the previous state-of-the-art "SuccConv" algorithm.
  • Speedup: FGM converges significantly faster than successive convex approximation methods. For example, in a 10x10 Grcar matrix test, FGM reached a stable solution in a fraction of the time required by other methods.
  • Robustness: The multi-start random initialization (mRand-FGM) proved particularly effective at escaping poor local minima that trapped simpler initialization strategies.

Limitations and Future Work

  • Global Optimality: As with most non-convex solvers, there is no guarantee that the algorithm finds the absolute nearest stable matrix, only a locally optimal one.
  • Non-Uniqueness: The SUB decomposition is not unique (e.g., $S$ can be scaled by any constant $\alpha$), which might affect numerical stability or convergence speed in ways not yet fully explored.
  • Complex Matrices: While the paper focuses on real matrices, the authors note the theory extends to the complex plane, but they haven't implemented or tested that version extensively.
  • Structure Preservation: Future work could involve extending this to "port-Hamiltonian" systems, which have specific physical properties that must be preserved during stabilization.

Summary updated

Abstract

In this paper, we consider the problem of stabilizing discrete-time linear systems by computing a nearby stable matrix to an unstable one. To do so, we provide a new characterization for the set of stable matrices. We show that a matrix $A$ is stable if and only if it can be written as $A=S^{-1}UBS$, where $S$ is positive definite, $U$ is orthogonal, and $B$ is a positive semidefinite contraction (that is, the singular values of $B$ are less or equal 1). This characterization results in an equivalent optimization problem with a feasible set on which it is easy to project. We propose a very efficient fast projected gradient method to solve the problem in variables $(S,U,B)$. We show the effectiveness of the proposed method compared to other approaches.
BibTeX
@inproceedings{gillis2019approximating,
  author = {Nicolas Gillis and Michael Karow and Punit Sharma},
  title = {{Approximating the nearest stable discrete-time system}},
  booktitle = {Linear},
  year = {2019},
  doi = {10.1016/j.laa.2019.03.014},
}
Figure