Show the sum of a sequence of trace is convergent. $\operatorname{trace}( \sum_{t=0}^{\infty} (A')^t C' \Sigma_S C A^t S)$

Question

I encountered this problem when doing research.

Matrices are all real-valued. $\Sigma_S$ is a covariance matrix. One can assume $\Sigma_S$ is positive definite. $A$ is a square matrix with dimension $n\times n$. $C$ is a $n\times m$ matrix where $m\leq n$. $C$ is a bit redundant here. One can assume that $C'\Sigma_S C$ is positive definite.

Now I want to find the conditions on $A$ and $C'\Sigma_S C$ such that $$ \operatorname{trace}( \sum_{t=0}^{\infty} (A')^t C' \Sigma_S C A^t S) < \infty $$ where $S$ is positive definite. Here, prime $'$ means transpose and $A^t$ refers to the $t$th power of matrix $A.

Ideas: We can write $C\Sigma_SC = LL'$ and assume that $(A,L)$ is controllable. We can see $\sum_{t=0}^\infty (A')^t LL'A^t$ is actually the infinite-horizon controllability Gramian. If all eigenvalues of $A$ have magnitudes less than $1$, then there is a unique positive definite solution of $$ W_\infty -A'W_\infty A = LL'. $$ And the controllability Gramian can be expressed as $W_\infty = \sum_{t=0}^\infty (A')^t LL'A^t.$ Then, we have $trace( \sum_{t=0}^{T} (A')^t C' \Sigma_S C A^t S)\rightarrow \operatorname{trace}(W_\infty S)$ as $T\rightarrow \infty$.

But this convergence requires that $A$ is table and $(A,L)$ is controllable. Can we conclude $$ \operatorname{trace}( \sum_{t=0}^{\infty} (A')^t C' \Sigma_S C A^t S) < \infty $$ using only the assumption that $(A,L)$ is controllable?

More Background:

Consider a linear-quadratic-gaussian optimal control problem with a discrete-time linear system $$ x_{t+1} = Ax_t + Bu_t + Cw_t, $$ where $x_t$ is the state, $u_t$ is the control and $w_t$ is Gaussian noise with zero mean and variance $\mathbf{E}[w_t' w_\tau ]=\Sigma_S\delta(t-\tau)$. Here, $\delta(\cdot)$ is the Kronecker delta function. Given $x_0 =x$, let $\mathcal{F}_t = \{x_0,u_0,\dotsc,u_{t-1}\}$. And the problem is associated with quadratic stage cost $x_t'Qx_t + u_t' Ru_t$ with $Q\geq 0$ and $R\geq 0$.

We have $\hat{x}_t = \mathbf{E}\left[ x_t \middle \vert \mathcal{F}_t \right] = A^{t-1}x +\sum_{\tau=0}^{t-1}A^{t-1-\tau}B u_\tau$. And the variance of estimation error $P_t(\mathcal{F}_t) := \mathbf{E}\left[(x_t -\hat{x}_t)'(x_t - \hat{x}_t)\middle\vert \mathcal{F}_t\right]$ is propagated as $P_{t+1} = A' P_t A + C'\Sigma_SC$ with $P_0 =0$. Thus, $P_t(\mathcal{F}_t)$ can be expressed as $$ P_t(\mathcal{F}_t) = \sum_{\tau=0}^{t-1} (A')^\tau C' \Sigma_S C A^\tau. $$

Let $S = A' PB (R+ B' P B)^{-1}B' PA$ where $P$ is a positive definite solution of an algebraic Riccati equation. Then the control performance degradation at time $t$ by not having observations from times $0$ to $t$ is $$ \mathbf{E}\left[ (x_t - \hat{x})'S(x_t - \hat{x}) \middle\vert \mathcal{F}_t\right] = \operatorname{trace}(P_{t}(\mathcal{F}_t) S) = \operatorname{trace}(\sum_{\tau=0}^{t-1} (A')^\tau C' \Sigma_S C A^\tau S). $$

Wants to find the loosest conditions such that the degradation is bounded as $t\rightarrow \infty$.

Added Questions: Under what conditions will the accumulated degradation with a discounted factor $\beta<1$ $$ \sum_{t=0}^\infty \beta^t \operatorname{trace}(P_{t}(\mathcal{F}_t) S) $$ be bounded?

Answer 1

Because $C'\Sigma_S C$ is positive definite, the function $$ \|M\| = \sqrt{\operatorname{trace}(M' S^{1/2}[C'\Sigma_S C]S^{1/2}M)} $$ defines a matrix norm. With Gelfand's formula, we have $$ \rho(M) = \lim_{k \to \infty} \|M^k\|^{1/k}. $$ Now, note that $$ \operatorname{trace}( (A')^t C' \Sigma_S C A^t S) = \\ \operatorname{trace}( S^{1/2}(A')^t C' \Sigma_S C A^t S^{1/2}) = \\ \operatorname{trace}(([S^{-1/2}AS^{1/2}]')^t S^{1/2}C' \Sigma_S CS^{1/2} [S^{-1/2}AS^{1/2}]^t ) = \\ \|(S^{-1/2}AS^{1/2})^t\|^2. $$ Note that $S^{-1/2}AS^{1/2}$ has the same eigenvalues as $A$. With Gelfand's formula, we can conclude by the root test that the sum will necessarily diverge when $A$ has any eigenvalue of magnitude strictly greater than $1$.

We can also see that if $A$ has an eigenvalue of maximal magnitude (exactly) $1$, then the sum diverges. Indeed, if $v$ is a (possibly complex) unit eigenvector of $S^{-1/2}AS^{1/2}$ associated with the eigenvalue $\lambda$ with $|\lambda| = 1$, then we have $$ \|(S^{-1/2}AS^{1/2})^t\|^2 \geq v'[(S^{-1/2}AS^{1/2})^t]' S^{1/2}[C'\Sigma_S C]S^{1/2}[(S^{-1/2}AS^{1/2})^t]v =\\ |\lambda|^{2t} v'S^{1/2}[C'\Sigma_S C]S^{1/2}v = \\ v'S^{1/2}[C'\Sigma_S C]S^{1/2}v > 0. $$ So, the sequence being added has a positive lower bound. So, the sum necessarily diverges.

In other words, the sum will converge if and only if all eigenvalues of $A$ have magnitude smaller than $1$.

Answer 2

Let $x_{t+1} = Ax_t + Bu_t$ be a DT control system. Usually, $BB'$ is not invertible and thus not positive definite (for which case Ben presented his answer). Here, I'd like to show the divergence in the general case, where $(A,B)$ is controllable.

The $T$-horizon controllability gramian is defined by $W_T := \sum_{t=0}^TA^tBB'(A')^t$. Its eigenvalues tell us something about how far we can reach at time $T$ from zero. However, what you have here is the expression $Tr(W_TS)$ and you would like to know whether is has a limit as $T\to\infty$ if $A$ is not stable. As Ben already showed for the case that $BB'$ is positive definite (in which case $(A,B)$ is trivially controllable), the answer is no. Here is my reasoning:

1. If $C$ is positive semi-definite, then $Tr(C)\ge \langle Cx,x\rangle$ for any unit vector $x$.

Indeed, if $C = U'DU$ is the eigenvalue decomposition of $C$, then, setting $y := Ux$, we have $$ \langle Cx,x\rangle = \langle DUx,Ux\rangle = \sum_k\lambda_ky_k^2\le\sum_k\lambda_k = Tr(C) $$ since $y_k^2\le\|y\|^2 = \|Ux\|^2 = \|x\|^2\le 1$ for each $k$.

2. Assume that $A$ (and thus also $A'$) has an eigenvalue $\lambda$ with $|\lambda|\ge 1$. Choose a corresponding eigenvector $x\neq 0$ for $A'$. Then $$ \langle W_T x,x\rangle = \sum_{t=0}^T\|B'(A')^tx\|^2 = \sum_{t=0}^T|\lambda|^{2t}\|B'x\|^2\,\ge\,(T+1)\|B'x\|^2. $$ As $(A,B)$ is controllable, the Kalman matrix $K = (B,AB,\ldots,A^{n-1}B)$ has full rank $n$ and so its transpose $K'$ has trivial kernel. If $B'x = 0$ and $A'x = \lambda x$, then $K'x=0$, which is impossible. So, $\|B'x\|\neq 0$.

3. We now come to the conclusion. Let $y$ be a vector such that $S^{1/2}y = x$, where $x$ is as in 2. above. Then, by 1. and 2., \begin{align*} Tr(W_TS) &= Tr(S^{1/2}W_TS^{1/2})\,\ge\,\|y\|^{-2}\langle S^{1/2}W_TS^{1/2}y,y\rangle\\ &= \|y\|^{-2}\langle W_Tx,x\rangle\ge C\cdot T \end{align*} with $C = \|y\|^{-2}\|B'x\|^2$. This shows that $Tr(W_TS)\to\infty$ as $T\to\infty$.