Assume you have a linear regression model $Y=\beta X$ with a high dimensional (say 1 000 000 resulting from dummy coding) vector $X$. You want to use this regression to predict $Y$. But dependence is expected to change with time: typically $Y=\beta(t)X$. You have a new dataset every day $t$ and want to forecast $\beta(t+1)$ for the next day.

For simplicity imagine $\beta(t)$ is essentially varying in a Brownian way: a random walk with normally distributed independent steps. Even though the best forecast for $\beta(t+1)$ is $\beta(t)$, you don't know $\beta(t)$ today, only an estimation. Using data from several days would increase the precision but you have to take dynamics into account. The ideal method is to deal with $\beta(t)$ as a state of a Kalman filter. But it's (almost) not possible in high dimension since you barely can't store the covariance matrix for $\beta$.

I'm looking for methods that are cheaper and could be thought as approximations of the Kalman filter. I'm thinking of:

  • regularize each day towards your previous estimate
  • work with a diagonal approximation of the covariance matrix

Do you know of any method for a similar problem that has been tried?

  • $\begingroup$ I added this to the question. $\endgroup$ – Benoit Sanchez Nov 28 '17 at 16:19
  • $\begingroup$ A few millions per day: from web traffic. Dimensions are binary variables resulting from dummy coding. $\endgroup$ – Benoit Sanchez Nov 30 '17 at 16:33

Nothing is stopping you from pre-processing your data better (e.g. by using subject-matter expertise or using more standard dimension-reduction techniques). However, you may also set your observation equation to $$ Y_t=X_t S \beta(t) $$ where $S$ is some tall and skinny matrix, which allows you to shrink the dimension of your state. Elements of $S$ can be treated as known, or estimated with a Maximum Likelihood Procedure.

Another trick is running separate Kalman filters for different blocks of observations, which allows for simple parallelization. If you don't have any fixed-coefficient predictors, then this decoupling is exact if your state transition matrix, your state covariance matrix, your observation matrix, and your observation covariance are all block-diagonal. It would be approximate if there was at least one of these four matrices that wasn't. You can prove this just by writing out the Kalman recursions with block-diagonal matrices.


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.