How can I vectorize this segment of pseudocode:
for i from 1 to n
y[i] := y[i-1] + α * (x[i] - y[i-1])
Add a comment
|
2 Answers
Your original equation can be written:
y[i] = alpha*x[i] + (1-alpha)*y[i-1]
This is an infinite impulse response (IIR) filter. You can take the Z transform to get:
Y(z) = alpha*X(z) + (1-alpha)*Y(z^-1)
which can be manipulated to give the transfer function of the filter
Y(z)/X(z) = alpha/(1 + (alpha-1)*z^-1)
You can use the lfilter function in scipy.signal (docs) to speed up your calculation:
import scipy.signal as sig
y = sig.lfilter([alpha], [1, alpha-1], x)
This is not, strictly speaking, vectorization. But it has the same effect: it speeds up the calculation by performing the loop in C.
Comments
It can not be vectorized. Your induction is simply y[i] = a * x[i] + (1-a) * y[i-1]
Think of y[n] like a polynomial, a * x[i] and y[0] will be the coefficients and 1-a will be the variable. And there is no way to vectorize the evaluation of a polynomial.
1 Comment
user2357112
It might not actually be executed vectorized, but in NumPy, writing an operation in terms of NumPy built-ins and vectorized notation generally puts the work into C code instead of interpreted Python. This makes things much faster, even if execution is serial.