Balanced Truncation

Balanced Truncation is an important projection model reduction method which delivers high quality reduced models by making an extra effort in choosing the projection subspaces.

Derivation

We consider linear time-invariant systems, defined in generalized state-space form by

$E \dot{x} = A x + B u,$

$y = C x + D u,$

where nonsingularity of $E$ and stability ( $A - λ E$ stable) is assumed.

A stable minimal (controllable and observable) system $Σ$ , realized by $(E, A, B, C, D)$ , is called balanced^[1], if the systems Controllability Gramian and Observability Gramian, i.e. the solutions $W_{C}$ and $W_{O}$ of the (generalized) Lyapunov equations

$A W_{C} E^{T} + E W_{C} A^{T} = - B B^{T},$

$A^{T} {\hat{W}}_{O} E + E^{T} {\hat{W}}_{O} A = - C^{T} C, W_{O} = E^{T} {\hat{W}}_{O} E,$

satisfy $W_{C} = W_{O} = d i a g (σ_{1}, \dots, σ_{n})$ with $σ_{1} \geq σ_{2} \geq \dots \geq σ_{n} > 0$ . Since in general, the spectrum of $W_{C} W_{O}$ are the squared Hankel Singular Values for such a balanced system, they are given by: $\sqrt{λ (W_{C} W_{O})} = {σ_{1}, \dots, σ_{n}}$ .

An arbitrary system $(E, A, B, C, D)$ can be transformed into a balanced system $(\tilde{E}, \tilde{A}, \tilde{B}, \tilde{C}, \tilde{D})$ via a state-space transformation:

$(\tilde{E}, \tilde{A}, \tilde{B}, \tilde{C}, \tilde{D}) = (T E T^{- 1}, T A T^{- 1}, T B, C T^{- 1}, D) .$

This transformed system has balanced Gramians $W_{C} = T \tilde{W_{C}} T^{T}$ and $W_{O} = T^{- T} \tilde{W_{O}} T^{- 1}$ which are equal and diagonal. The balanced systems states are ordered (descendingly) by how controllable and observable they are, thus allowing a partion of the form:

$(\tilde{E}, \tilde{A}, \tilde{B}, \tilde{C}, \tilde{D}) = ([\begin{matrix} {\tilde{E}}_{11} & {\tilde{E}}_{12} \\ {\tilde{E}}_{21} & {\tilde{E}}_{22} \end{matrix}], [\begin{matrix} {\tilde{A}}_{11} & {\tilde{A}}_{12} \\ {\tilde{A}}_{21} & {\tilde{A}}_{22} \end{matrix}], [\begin{matrix} {\tilde{B}}_{1} \\ {\tilde{B}}_{2} \end{matrix}], [\begin{matrix} {\tilde{C}}_{1} & {\tilde{C}}_{2} \end{matrix}], \tilde{D})$ .

By truncating the discardable states, the truncated reduced system is then given by $\hat{Σ} = ({\tilde{E}}_{11}, {\tilde{A}}_{11}, {\tilde{B}}_{1}, {\tilde{C}}_{1}, \tilde{D})$ .

Implementation: SR Method

The necessary balancing transformation can be computed by the SR Method^[2]. First, the Cholesky factors of the Gramians $W_{C} = S^{T} S, W_{O} = R^{T} R$ are computed. Next, the Singular Value Decomposition of $S R^{T}$ is computed:

$S R^{T} = U Σ V^{T} .$

Now, partitioning $U, V$ , for example based on the Hankel singuar Values, gives

$S R^{T} = [\begin{matrix} U_{1} U_{2} \end{matrix}] [\begin{matrix} Σ_{1} \\ Σ_{2} \end{matrix}] [\begin{matrix} V_{1}^{T} \\ V_{2}^{T} \end{matrix}] .$

The truncation of discardable partitions $U_{2}, V_{2}^{T}, Σ_{2}$ results in the reduced order model $(P^{T} E Q, P^{T} A Q, P^{T} B, C Q, D)$ where

$P^{T} = Σ_{1}^{- \frac{1}{2}} V_{1}^{T} R E^{- 1},$

$Q = S^{T} U_{1} Σ_{1}^{- \frac{1}{2}} .$

Note that $P^{T} E Q = I_{r}$ which makes $Q P^{T}$ an oblique projector and hence Balanced Trunctation a Petrov-Galerkin projection method. The reduced model is stable with Hankel Singular Values given by $σ_{1}, \dots, σ_{r}$ , where r is the order of the reduced system. It is possible to choose $r$ via the computable error bound^[3]:

$‖ Σ - \hat{Σ} ‖_{2} \leq 2 ‖ u ‖_{2} \sum_{k = r + 1}^{n} σ_{k} .$

Direct Truncation

A related truncation-based approach is Direct Truncation^[4]. Given a stable and symmetric system $(A, B, C, D)$ , such that there exists a transformation $J$

$A J = J A^{T}$

$B = J C^{T}$

then the solution of the Sylvester Equation

$A W_{X} + W_{X} A = - B C$

is the Cross Gramian, of which the absolute value of its spectrum equals the Hankel Singular Values:

$| λ (W_{X}) | = {σ_{1}, \dots, σ_{r}}$ .

Thus the Singular Value Decomposition of the Cross Gramian

$W_{X} = U Σ V^{T}$

also allows a partitioning

$W_{X} = [\begin{matrix} U_{1} U_{2} \end{matrix}] [\begin{matrix} Σ_{1} \\ Σ_{2} \end{matrix}] [\begin{matrix} V_{1}^{T} \\ V_{2}^{T} \end{matrix}] .$

and a subsequent truncation of the discardable states, to which the above error bound also applies.

References

↑ B.C. Moore, "Principal component analysis in linear systems: Controllability, observability, and model reduction", IEEE Transactions on Automatic Control , vol.26, no.1, pp.17,32, Feb 1981
↑ A.J. Laub; M.T. Heath; C. Paige; R. Ward, "Computation of system balancing transformations and other applications of simultaneous diagonalization algorithms," IEEE Transactions on Automatic Control, vol.32, no.2, pp.115,122, Feb 1987
↑ D.F. Enns, "Model reduction with balanced realizations: An error bound and a frequency weighted generalization," The 23rd IEEE Conference on Decision and Control, vol.23, pp.127,132, Dec. 1984
↑ Antoulas, Athanasios C. "Approximation of large-scale dynamical systems". Vol. 6. Society for Industrial and Applied Mathematics, 2009; ISBN 978-0-89871-529-3

[1] B.C. Moore, "Principal component analysis in linear systems: Controllability, observability, and model reduction", IEEE Transactions on Automatic Control , vol.26, no.1, pp.17,32, Feb 1981

[2] A.J. Laub; M.T. Heath; C. Paige; R. Ward, "Computation of system balancing transformations and other applications of simultaneous diagonalization algorithms," IEEE Transactions on Automatic Control, vol.32, no.2, pp.115,122, Feb 1987

[3] D.F. Enns, "Model reduction with balanced realizations: An error bound and a frequency weighted generalization," The 23rd IEEE Conference on Decision and Control, vol.23, pp.127,132, Dec. 1984

[4] Antoulas, Athanasios C. "Approximation of large-scale dynamical systems". Vol. 6. Society for Industrial and Applied Mathematics, 2009; ISBN 978-0-89871-529-3

[1]

[2]

[3]

[4]