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

A stable minimal (controllable and observable) system $\mathrm{\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

$A{W}_C+W_C{A}^T=-B{B}^T$

$A^T{W}_O+W_{O}A=-C^{T}C$

respectively, satisfy $W_C=W_O=diag({\sigma }_1,\dots ,{\sigma }_n)$ with ${\sigma }_1\ge {\sigma }_2\ge \dots \ge {\sigma }_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{\lambda (W_C{W}_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})=(TA{T}^{-1},TB,C{T}^{-1}).$

This transformed system has balanced Gramians $W_C=T\widetilde{W_C}{T}^T$ and $W_O=T^{-T}\widetilde{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{array}{cc}{\tilde{A}}_{11}& {\tilde{A}}_{12}\\ {\tilde{A}}_{21}& {\tilde{A}}_{22}\end{array}\right],\left[\begin{array}{c}{\tilde{B}}_1\\ {\tilde{B}}_2\end{array}\right],\left[\begin{array}{cc}{\tilde{C}}_1& {\tilde{C}}_2\end{array}\right])$.

By truncating the discardable states, the truncated reduced system is then given by $\hat{\mathrm{\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 $\mathrm{\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

$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=diag({\sigma }_1,\dots ,{\sigma }_n)$ with ${\sigma }_1\ge {\sigma }_2\ge \dots \ge {\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})=(TE{T}^{-1},TA{T}^{-1},TB,C{T}^{-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{array}{cc}{\tilde{E}}_{11}& {\tilde{E}}_{12}\\ {\tilde{E}}_{21}& {\tilde{E}}_{22}\end{array}\right],\left[\begin{array}{cc}{\tilde{A}}_{11}& {\tilde{A}}_{12}\\ {\tilde{A}}_{21}& {\tilde{A}}_{22}\end{array}\right],\left[\begin{array}{c}{\tilde{B}}_1\\ {\tilde{B}}_2\end{array}\right],\left[\begin{array}{cc}{\tilde{C}}_1& {\tilde{C}}_2\end{array}\right],\tilde{D})$.

By truncating the discardable states, the truncated reduced system is then given by $\hat{\mathrm{\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^{T}S,W_O=R^{T}R$ are computed. Next, the Singular Value Decomposition of $S{R}^T$ is computed:

$S{R}^T=U\mathrm{\Sigma }{V}^T.$

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

$S{R}^T=\left[\begin{array}{c}{U}_1{U}_2\end{array}\right]\left[\begin{array}{cc}{\mathrm{\Sigma }}_1& \\ & {\mathrm{\Sigma }}_2\end{array}\right]\left[\begin{array}{c}{V}_1^T\\ V_2^T\end{array}\right].$

The truncation of discardable partitions $U_2,V_2^T,{\mathrm{\Sigma }}_2$ results in the reduced order model $(P^{T}EQ,P^{T}AQ,P^{T}B,CQ,D)$ where

$P^T={\mathrm{\Sigma }}_1^{-\frac{1}{2}}{V}_1^{T}R{E}^{-1},$

$Q=S^T{U}_1{\mathrm{\Sigma }}_1^{-\frac{1}{2}}.$

Note that $P^{T}EQ=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:

$\Vert \mathrm{\Sigma }-\hat{\mathrm{\Sigma }}{\Vert }_2\le 2\Vert u{\Vert }_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=J{A}^T$

$B=J{C}^T$

then the solution of the Sylvester Equation

$A{W}_X+W_{X}A=-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\mathrm{\Sigma }{V}^T$

also allows a partitioning

$W_X=\left[\begin{array}{c}{U}_1{U}_2\end{array}\right]\left[\begin{array}{cc}{\mathrm{\Sigma }}_1& \\ & {\mathrm{\Sigma }}_2\end{array}\right]\left[\begin{array}{c}{V}_1^T\\ V_2^T\end{array}\right].$

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