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})$.

Balancing and Truncation

The necessary balancing transformation can be computed by the Square-Root method. First, the Cholesky factors of the Gramians $W_C=S^TS,\; W_O=R^TR$ are computed. Alternatively to the Cholesky factorization, the Singular Value Decomposition can be employed: $W_O = U_O \Sigma_O U_O^T \Rightarrow S = (U_O \Sigma_O^\frac{1}{2})^T$ and $W_C = U_C \Sigma_C U_C^T \Rightarrow R = (U_C \Sigma_C^\frac{1}{2})^T$. 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 Singular 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.$

Cross Gramian MOR

A related Gramian-based approach is Cross Gramian Balanced 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.