Summation of polynomial matrix multiplication in terms of vector outer product

434 Views Asked by At

Consider the following summation

$$ \sum_{i=1}^{T-1}C(A^i-A^{i-1})Bx_{t-i} $$ where $A$ is a $d \times d$ diagonal matrix, i.e. $A=\text{diag}(\alpha_1,\cdots,\alpha_d)$, $C$ is an $m \times d$, $B$ is a $d \times n$ and $x$ is a vector in $\mathbb{R}^n$.

The above is equal to the following

$$ \sum_{l=1}^{d}(c_l\otimes b_l)\sum_{i=1}^{T-1}\mu(\alpha_l)(i)x_{t-i} $$ where $\mu(\alpha_l)$ is a continuous family of vectors as $\mu\,\,: [0,1] \rightarrow \mathbb{R}^T$ with entries $\mu(\alpha_l)(i)=(\alpha_l-1)\alpha_l^i$, $c_l$ is the $l$-th column of $C$, and $b_l$ is the $l$-th row of $B$. For more information, please refer to the following paper by Elad Hazan page 7:

Learning Linear Dynamical Systems via Spectral Filtering

1

There are 1 best solutions below

0
On

I would start by the following:

Since $A$ is a diagonal matrix we can rewrite it using a summation of $d$ matrix where each matrix has one element $$ A=\sum_{l=1}^{d}( \alpha_1 \begin{bmatrix} 1 & 0 &\cdots \\0 & 0 \\\vdots & & \ddots \end{bmatrix} + \cdots + \alpha_l \begin{bmatrix} \ddots & & \vdots \\ & 0 &0 \\ \cdots & 0 & 1 \end{bmatrix}) $$ To put the fisrt matrix in a more succinct way, we can write $e_1 \otimes e_1 =\begin{bmatrix} 1 & 0 &\cdots \\0 & 0 \\\vdots & & \ddots \end{bmatrix}$, where $e_1 =\begin{bmatrix} 1 \\0 \\\vdots \end{bmatrix}$ and so forth. So we have

$$ A=\sum_{l=1}^{d}( \alpha_1 e_1 \otimes e_1 + \cdots + \alpha_l e_l \otimes e_l) $$ Then we have $$ \sum_{i=1}^{T-1}C(\sum_{l=1}^{d}(e_l \otimes e_l)(\alpha_l^i-\alpha_l^{i-1}))Bx_{t-i} $$ Now we can pull $C$ and $B$ into the second sum because they do not depend on the index of the sum. Note that $C e_l=c_l$ which is equal to the column $l$ of $C$ and $e_lB=b_l$ which is equal to the row$l$ of $C$

$$ \sum_{i=1}^{T-1}\sum_{l=1}^{d}(C e_l \otimes e_lB)(\alpha_l^i-\alpha_l^{i-1})x_{t-i}=\sum_{i=1}^{T-1}\sum_{l=1}^{d}(c_l \otimes b_l)(\alpha_l^i-\alpha_l^{i-1})x_{t-i} $$

We can swap the summations and since $c_l \otimes b_l$ does not depend on the $i$ we can rearrange them as

$$ =\sum_{l=1}^{d}c_l \otimes b_l\sum_{i=1}^{T-1}(\alpha_l^i-\alpha_l)^{i-1}x_{t-i}=\sum_{l=1}^{d}c_l \otimes b_l\sum_{i=1}^{T-1}(\alpha_l-1)(\alpha_l^{i-1})x_{t-i} $$

Using the definition of $\mu$ we conclude the proof

$$ =\sum_{l=1}^{d}c_l \otimes b_l\sum_{i=1}^{T-1}\mu(\alpha_l)(i)x_{t-i} $$