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} = Ax + Bu,$

$y = Cx + Du,$

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

A stable minimal (controllable and observable) system $\Sigma$, realized by $(E,A,B,C,D)$, is called balanced, if the systems Controllability Gramian and Observability Gramian, i.e. the solutions $W_C$ and $W_O$ of the (generalized) Lyapunov equations

$AW_CE^T+EW_CA^T=-BB^T,$

$A^T\hat W_OE+E^T\hat W_OA=-C^TC, \quad W_O=E^T\hat W_O E,$

satisfy $W_C=W_O=diag(\sigma_1,\dots,\sigma_n)$ with $\sigma_1\geq\sigma_2\geq \dots\geq\sigma_n>0$. Since in general, the spectrum of $W_CW_O$ are the squared Hankel Singular Values for such a balanced system, they are given by: $\sqrt{\lambda(W_CW_O)} = \{\sigma_1,\dots,\sigma_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})= (TET^{-1},TAT^{-1},TB,CT^{-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})= \left (\begin{bmatrix}\tilde{E}_{11} & \tilde{E}_{12}\\ \tilde{E}_{21} & \tilde{E}_{22}\end{bmatrix}, \begin{bmatrix}\tilde{A}_{11} & \tilde{A}_{12}\\ \tilde{A}_{21} & \tilde{A}_{22}\end{bmatrix},\begin{bmatrix}\tilde{B}_1\\\tilde{B}_2\end{bmatrix},\begin{bmatrix} \tilde{C}_1 &\tilde{C}_2 \end{bmatrix},\tilde{D}\right)$.

By truncating the discardable states, the truncated reduced system is then given by $\hat{\Sigma}=(\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. First, the Cholesky factors of the Gramians $W_C=S^TS,\; W_O=R^TR$ are computed. Next, the Singular Value Decomposition of $SR^T\;$ is computed:

$SR^T= U\Sigma V^T.$

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

$SR^T= \begin{bmatrix} U_1 U_2 \end{bmatrix} \begin{bmatrix} \Sigma_1 & \\ & \Sigma_2\end{bmatrix} \begin{bmatrix} V_1^T\\V_2^T\end{bmatrix}.$

The truncation of discardable partitions $U_2,V^T_2,\Sigma_2$ results in the reduced order model $(P^TEQ,P^TAQ,P^TB,CQ,D)\;$ where

$P^T=\Sigma_1^{-\frac{1}{2}}V_1^T R E^{-1},$

$Q= S^T U_1 \Sigma_1^{-\frac{1}{2}}.$

Note that $P^TEQ=I_r$ which makes $QP^T$ an oblique projector and hence Balanced Trunctation a Petrov-Galerkin projection method. The reduced model is stable with Hankel Singular Values given by $\sigma_1,\dots,\sigma_r$, where r is the order of the reduced system. It is possible to choose $r$ via the computable error bound:

$\|\Sigma-\hat{\Sigma}\|_2 \leq 2 \|u\|_2 \sum_{k=r+1}^n\sigma_k.$

Direct Truncation

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

$AJ = JA^T$

$B = JC^T$

then the solution of the Sylvester Equation

$AW_X+W_XA=-BC$

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

$|\lambda(W_X)| = \{\sigma_1,\dots,\sigma_r\}$.

Thus the Singular Value Decomposition of the Cross Gramian

$W_X = U\Sigma V^T$

also allows a partitioning

$W_X = \begin{bmatrix} U_1 U_2 \end{bmatrix} \begin{bmatrix} \Sigma_1 & \\ & \Sigma_2\end{bmatrix} \begin{bmatrix} V_1^T\\V_2^T\end{bmatrix}.$

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