Can the following iterative update on a $n$-element vector $\mathbf{x}_t$ be computed in $O(n)$ computations? \begin{align*} \mathbf{x}_{t+1} & = a_t\mathbf{y}_t + \mathbf{A}_t \mathbf{x}_t \,,\\ \mathbf{A}_{t+1} & = \mathbf{A}_t + b_t \mathbf{y}_t \mathbf{z}_t^T \,. \end{align*} Here $a_t$, $b_t$ are (random) scalars, $\mathbf{y}_t$ and $\mathbf{z}_t$ are $n$-element (random) column vectors and $\mathbf{A}_t$ is a $n \times n$ matrix. Without loss of generality, we may assume $\mathbf{A}_0 = \mathbf{0}_{n\times n}$ such that, e.g., $\mathbf{x}_1 = a_0 \mathbf{y}_0$.
When $n$ is large, an explicit computation of $\mathbf{A}_t \mathbf{x}_t$ may be prohibitively expensive. We could instead compute $$ \mathbf{A}_t \mathbf{x}_t = \sum_{n=0}^{t-1} b_n \mathbf{y}_n ( \mathbf{z}_n^T \mathbf{x}_t ) \,, $$ which takes $O(nt)$ computations rather than $O(n^2)$. Unfortunately, as $t$ grows this also may become too slow.
Note that $\mathbf{A}_t$ is only used in the context $\mathbf{A}_t \mathbf{x}_t$. I do not want to store this matrix explicitly, because of its size, so I am looking if a way exists for rewrite the update using only several $n$-element vectors.
I tried storing a vector representing $\mathbf{A}_t \mathbf{x}_t$, but I could not find a $O(n)$ update for this vector.