1
$\begingroup$

I have the following recursive sequence:

$Z_k = Z_{k-1} - AA^TZ_{k-1}xx^T$ where $Z_k \in \mathbb R^{n \times d}, A \in \mathbb R^{n \times d}, d > n, rank(A) = n, x \in \mathbb R^{d \times 1}$

$A$ is a constant matrix, $x$ is a constant vector. Theoretically, this sequence of matrices $Z_k$ is entirely determined by $Z_0$ the initial element of the sequence.

If I give you $Z_0$ you are able to find $Z_k$ for any $k$.

Suppose I want to find $Z_{100}$. Is it possible to find an expression for $Z_k$ as a function of $Z_0$ so that I don't actually have to find $Z_1, Z_2, ..., Z_{99}$?

$\endgroup$
1
  • 2
    $\begingroup$ This is a linear recurrence relation, so in theory it is possible to work out the general formula for $Z_k$, provided that the matrices $A$ and $x$ are explicitly given. Not sure whether there is an optimization for this special kind of recurrence relation. $\endgroup$
    – WhatsUp
    Jan 15 at 0:51
5
$\begingroup$

Let $B=AA^T$ and $X=xx^T$. Note that $X^k=\|x\|^{2k-1}X$.

\begin{align*} Z_1& = Z_{0} - BZ_{0}X \\ % Z_2& = Z_{1} - BZ_{1}X % = Z_{0} - BZ_{0}X -B\big[Z_{0} - BZ_{0}X\big]X % = Z_{0} - 2BZ_{0}X + B^2Z_{0}X^2 \\ % Z_3& = Z_{2} - BZ_{2}X % = Z_{1} - BZ_{1}X -B\big[Z_{1} - BZ_{1}X\big]X % = Z_{1} - 2BZ_{1}X + B^2Z_{1}X^2 \\ % & = Z_{0} - 3BZ_{0}X + 3B^2Z_{0}X^2-B^3Z_{0}X^3 . \end{align*}

So that by induction,

\begin{align*} % Z_n& =\sum_{k=0}^n-1^k\binom nk B^kZ_0X^k % = Z_0 + \sum_{k=1}^n-1^k\binom nk \|x\|^{2k-1}B^kZ_0X\\ % & = Z_0-\frac1{\|x\|^2}Z_0X + \frac1{\|x\|^2} % \bigg[\sum_{k=0}^n-1^k\binom nk \|x\|^{2k}B^k\bigg]Z_0X \\ % & =Z_0-\frac1{\|x\|^2}Z_0X + \frac1{\|x\|^2} % [I-\|x\|^2B]^nZ_0X \\ % & =Z_0-\frac1{\|x\|^2}Z_0xx^T + \frac1{\|x\|^2} % [I-\|x\|^2AA^T]^nZ_0xx^T % \end{align*}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.