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 based on the Controllability and Observability of the underlying control system.

Derivation

A stable minimal (controllable and observable) linear 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.$

Time- and frequency-limited BT

Time- and frequency-limited BT are modifications of BT targeted at achieving a high approximation quality within finite time $[0,T], T<\infty$ or frequency regions $[\omega_1,\omega_2], 0\leq\omega_1<\omega_2<\infty$, while allowing large approximation errors outside these regions. Starting point of the derivation are the integral expressions of the Gramians

$W_{C}=\int\limits_0^{\infty}\mathrm{e}^{At}BB^T \mathrm{e}^{A^Tt}\mathrm{d}t=\frac{1}{2\pi}\int\limits_{-\infty}^{\infty}(i\omega I-A)^{-1}BB^T (i\omega I-A)^{-H}\mathrm{d}\omega,\quad W_O=\int\limits_0^{\infty}\mathrm{e}^{A^Tt}C^TC \mathrm{e}^{At}\mathrm{d}t=\frac{1}{2\pi}\int\limits_{-\infty}^{\infty}(i\omega I-A)^{-H}C^TC (i\omega I-A)^{-1}\mathrm{d}\omega.$

Restricting the integration domain of the time-domain integrals to $[0,T]$ leads to the time-limited Gramians

$W_{C,T}=\int\limits_0^{T}\mathrm{e}^{At}BB^T \mathrm{e}^{A^Tt}\mathrm{d}t,\quad W_{O,T}=\int\limits_0^{T}\mathrm{e}^{A^Tt}C^TC \mathrm{e}^{At}\mathrm{d}t.$

which are the solutions of the time-limited Lyapunov equations

$AW_{C,T}+W_{C,T}A^T=f(A)BB^Tf(A)^T-BB^T,\quad A^TW_{O,T}+W_{O,T}A=f(A)^TC^TCf(A)-C^TC\quad\text{with}\quad f(A)= \mathrm{e}^{AT}.$

Likewise, restricting the frequency-domain integral expressions of $W_C,W_0$ to $\Omega:=[-\omega_2,-\omega_2]\cup[\omega_1,\omega_2]$ leads to the frequency-limited Lyapunov equations

$AW_{C,\Omega}+W_{C,\Omega}A^T=-f(A)BB^T-BB^Tf(A)^T,\quad A^TW_{O,\Omega}+W_{O,\Omega}A=-f(A)^TC^TC-C^TCf(A)\quad\text{with}\quad f(A)= \frac{1}{\pi}\mathrm{Re}\left(i\log\left((A+i\omega_1I)^{-1}(A+i\omega_2I)\right)\right),$

see, e.g., . Time-limited and Frequency-limited BT are then obtained by using Cholesky- or low-rank factors of the restricted Gramians $W_{C,T},W_{O,T}$ and, respectively,$W_{C,\Omega},W_{O,\Omega}$ instead of the infinite Gramians $W_C,W_0$.

Computational strategies for large-scale systems for dealing with the matrix functions $f(A)$ and for computing the required low-rank factors of Gramians $W_{C,\Omega},W_{O,\Omega}$ and $W_{C,T},W_{O,T}$ are proposed in , .

The handling of generalized state-space systems can be adopted right away from the unrestricted BT case.

In general, neither time- nor frequency-limited BT guarantee that the stability of the original system is preserved and, hence, do also not provide an $H_{\infty}$ error bound similar to the one of unrestricted BT. Modified time- or frequency-limited BT fixes this, but has been found to be inferior compared to unrestricted BT and (unmodified) time-/frequency-limited BT in terms of computational efficiency. The achieved accuracy is also lower compared to time-/frequency-limited BT. In H2-type error bounds for Time-limited BT are derived which do not rely on stability preservation. Moreover, some experiments in indicate that Time-limited BT might be a potential candidate for reducing unstable systems.

Cross Gramian MOR

A related Gramian-based approach is Cross Gramian Model Order Reduction,. 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. Note that, although the similarities to the standard balanced truncation approach, the reduced order model obtained with this method is not balanced for non-symmetric systems.