Balanced Truncation

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

Derivation

A stable minimal (controllable and observable) system \(\Sigma\), realized by \((A,B,C)\)

\[ \dot{x} = Ax + Bu\]

\[ y = Cx\]

is called balanced, if the systems Controllability Gramian and Observability Gramian, the solutions \(W_C\) and \(W_O\) of the Lyapunov equations

\[ AW_C+W_CA^T=-BB^T \]

\[ A^TW_O+W_OA=-C^TC \]

respectively, 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 \((A,B,C)\) can be transformed into a balanced system \((\tilde{A},\tilde{B},\tilde{C})\) via a state-space transformation:

\[ (\tilde{A},\tilde{B},\tilde{C})= (TAT^{-1},TB,CT^{-1}).\]

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{A},\tilde{B},\tilde{C})= \left (\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}\right)\].

By truncating the discardable states, the truncated reduced system is then given by \( \hat{\Sigma}=(\tilde{A}_{11},\tilde{B}_1,\tilde{C}_1) \).

Generalization

Considering a 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.

Similarly, 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\).

Again, 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).\]

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 it to an oblique projector and hence Balanced Truncation 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.