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