Average Controllabilityの導入の背景を理解する（計算メモ）

はじめに

Network Controllability系の論文に出てくる量の「気持ち」を理解するために、導出を追ってみました。

問題設定

離散的なlinear time invariant systemを考える。
$\displaystyle x(t+1) = Ax(t)+Bu(t) \ \ \ \cdot \cdot \cdot (1)$
Aはノード数nの有向グラフ $\mathcal G := (\mathcal V , \mathcal E)$ の接続行列 $A=[a_{ij}], a_{ij} \in \mathbb R$ を表し、control nodes setを $\mathcal K := \{k_1, ..., k_m\} \subseteq \mathcal V$ とした時に $B := [e_{k_1}, ..., e_{k_m}]$ とする。

$x(t) \in \mathbb R^n$ をシステムの状態、 $u(t)\in \mathbb R^m$ を入力信号とする。

この系において状態の始状態を $x(0)=0$ , 終状態を $x_f$ とした時に $x(T) = x_f$ となるような入力列 $u: \mathbb N_{\geqslant 0} \rightarrow \mathbb R^m$ を求めることを考える。

Controllability Gramian

そのような $u$ が存在するための必要十分条件は次の可制御性行列
$\displaystyle C := [B, AB ,... ,A^{T-1}B ]$
の階数が $n$ であることである。

次に具体的な $u$ を求める。(1)より、
$\displaystyle \begin{eqnarray} x_f &=& A^{T-1}Bu(0) + \dotsb + A^{T-t-1}Bu(t) + \dotsb + Bu(T-1)\\ &=& C[u(T-1), \dotsb ,u(0)]^\mathsf{T} \ ... \ (2) \end{eqnarray}$
$C$ がランク落ちしていないためこれを満たす $u$ は存在するが $C \in \mathbb R^{n\times nm}$ より方程式は不定となる。

そこで $\|u\|^2=\sum_{\tau=0}^{T-1}\|u(\tau)\|^2$ が最小となるノルム最小解 $u^\ast$ を求めることを考える。

ここで、Contrllability Gramian $\mathcal W$ を次のように定義する。
$\displaystyle \mathcal W := \sum_{\tau=0}^{T-1}A^{\tau}BB^{\mathsf{T}}(A^{\mathsf T})^{\tau} = CC^{\mathsf T}$
天下り式になるが、射影行列 $P=C^{\mathsf T} \mathcal W^{-1} C$ を導入すると(2)を満たす任意の $u$ について $u^\ast = Pu$ になることが次のように示される。
まず、
$\displaystyle \begin{eqnarray} Cu^\ast &=& CPu \\ &=& CC^{\mathsf T}\mathcal W^{-1} Cu \\ &=& \mathcal W \mathcal W^{-1} Cu = x_f \end{eqnarray}$
より $u^\ast$ は(2)を満たす。
次にノルムが最小になることについて。
$P^{\mathsf T} = P$ 、
$P^2 = P$
に注意して、
$\displaystyle \begin{eqnarray} \|u\|^2 &=& \|Pu + (I-P)u\|^2 \\ &=& \|Pu\|^2 + 2\langle Pu, (I-P)u \rangle + \|(I-P)u\|^2 \end{eqnarray}$

ここで、
$\displaystyle \begin{eqnarray} \langle Pu, (I-P)u\rangle &=& \langle u, P^{\mathsf T}(I-P)u \rangle \\ &=& \langle u, P(I-P)u\rangle \\ &=& \langle u,0\rangle = 0 \end{eqnarray}$
より、
$\|u\|^2 = \|Pu\|^2 + \|(I-P)u\|^2 \geq \|Pu\|^2 = \|u\ast\|^2$
が成立することから $u\ast = Pu = C^{\mathsf T}\mathcal W^{-1} x_f$ はノルム最小解になる。
なお、一時刻ごとの $u^\ast$ の値は $u^\ast(t) = B^{\mathsf T}(A^{\mathsf T})^{T-t-1}\mathcal W^{-1}x_f$ と書ける。

なお、Controllability Gramianについて、
$\displaystyle \begin{eqnarray} 0 \leq \|u^\ast\|^2 &=& u^\ast\mathsf T u^\ast \\ &=& x_f^{\mathsf T} (\mathcal W^{-1})^{\mathsf T} CC^{\mathsf T} \mathcal W^{-1} x_f \\ &=& x_f^{\mathsf T}\mathcal W^{-1} x_f \ \dotsb \ (3) \end{eqnarray}$
から半正定値であることが分かるが、 $\mathcal W^{-1}$ が正則であるため
$\forall x \neq 0, \mathcal W^{-1}x \neq 0$
$\therefore x^{\mathsf T}\mathcal W^{-1} x \neq 0$
より正定値。

Control Energy

$x_f$ を単位超球面上の点に制限した時（ $\|x_f\|=1$ ）、 $\|u^\ast \|^2$ をControl Energyとする。
$\displaystyle E(u,T) := \|u^\ast \|^2 = \sum_{\tau=0}^{T-1} \|u^\ast (\tau) \|^2$
Control Energyについて次のことが分かる。
$E(u,T) = x_f \mathcal W^{-1} x_f \geq \lambda_{max}(\mathcal W^{-1}) = \lambda_{min}^{-1}(\mathcal W)$
なお、一つ目の等式は(3)に基づき、2つめの不等式は $\mathcal W^{-1}$ の直交変換を行えば成り立つことが分かる。
これよりControllability Gramianの最小固有値はnetwork controllabilityの指標として採用されることがあり、そこでは「最もエネルギーが必要な終状態（＝最も悪いケース）を実現するために必要になるエネルギー」という考え方に基づいて定義されている。

Average Energy, Average Controllability

一方、 $x_f$ に到達させるために必要なエネルギーの平均をnetwork controllabilityの指標として採用する場合も考えられる。この時は $\|x_f\|=1$ という条件下での $E(u, T)$ の期待値を考え、これをAverage Energyと呼ぶ。
$\displaystyle \int_{ \|x\|=1}x_i x_j dx = \frac{1}{n}\delta_{ij}$ に注意して、
$\displaystyle \begin{eqnarray} \int_{\|x\|=1} x^{\mathsf T} \mathcal W^{-1} x dx &=& \sum_i \int_{\|x\|=1} x_i \sum_j \mathcal W^{-1}_{ij}x_j dx \\ &=& \sum_{ij} \mathcal W^{-1}_{ij} \int_{\|x\|=1}x_i x_j dx \\ &=& \frac{1}{n} \mathrm{Tr}(\mathcal W^{-1}) \end{eqnarray}$
より、Average ControllabilityはControllability Gramianの逆行列のトレースとなる。

ただし、 $\mathrm{Tr}(\mathcal W^{-1})$ は計算が安定しなく、また以下の不等式により $\mathrm{Tr}(\mathcal W)$ によって下から押さえられるため、Danielle S. Bassettらは $\mathrm{Tr}(\mathcal W)$ をAverage Controllabilityとしてnetwork controllabilityの指標（の一つ）にしている。
$\mathrm{Tr}(\mathcal W) = \sum_{i=1}^{n} \lambda_i \leq n\lambda_{max}$ より、
$\displaystyle \begin{eqnarray} \mathrm{Tr}(\mathcal W^{-1}) &=& \sum_{i=1}^n \frac{1}{\lambda_i} = \frac{1}{\lambda_{min}} + \ \dotsb \ + \frac{1}{\lambda_{max}} \\ &\geq & \frac{n}{\lambda_{max}} \geq \frac{n^2}{ \mathrm{Tr}(\mathcal W)} \end{eqnarray}$