Is there a way to implement recurrence in numpy wi

Question

I have the following problem. There is a matrix X and I need to generate a matrix H such that values of i_th row in matrix H are determined by i_th row of the matrix X and (i-1)_th row of matrix H.

H_{i} = F(X_{i}, H_{i-1})

To calculate the first row of matrix H we use a special out-of-the-matrix row (row zero, so to say).

Is there a way to implement this recurrence efficiently, in a vectorized form, without using for loops?

Answer 1

There is no other way (in general) except for an explicit for loop. This is because there is no way to parallelize this task across the rows (since every row depends on some other row).

What makes this even harder is that you can easily generate chaotic behavior, for example with the seemingly innocent looking logistic map: x_{n+1} = r * x_n * (1 - x_{n-1}).

You can only find a way around this if you manage to find a closed form, essentially eliminating the recurrence relation. But this has to be done for each recurrence relation and I am pretty sure you are not even guaranteed that a closed form exists...