Time varying regression in high dimension: cheaper than the Kalman filter

Question

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?

Answer 1

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.