1

Given a Weighted Linear Least Squares problem where the cost function is given by:

$$ J = { \left( x - H \Theta \right) }^{T} {C}^{-1} { \left( x - H \Theta \right) } $$

There is a Sequential Solution for the cases we get a sample by sample of $ \left\{ x \left[ 0 \right], x \left[ 1 \right], \cdots x \left[ N \right] \right\} $

Namely, given $ x \left[ N + 1 \right] $ we can derive $ \hat{\Theta} \left[ N + 1 \right] $ by

$$ \hat{\Theta} \left[ N + 1 \right] = \hat{\Theta} \left[ N \right] + K \left[ N + 1 \right] \left( x \left[ N + 1 \right] - {h}^{T} \left[ n \right] \hat{\Theta} \left[ N \right] \right) $$

With the appropriate choice of $ K \left[ N + 1 \right] $ (Very similar to Kalman Filter).

The question is, can we have a sequential form to a Tikhonov Regularized Least Squares problem where the cost function is given by:

$$ J = { \left( x - H \Theta \right) }^{T} {C}^{-1} { \left( x - H \Theta \right) } + \lambda {\left \| W \Theta \right \|}^{2}_{2} $$

Is there such form?

Carl
  • 11,532
  • 7
  • 45
  • 102
Royi
  • 966
  • 8
  • 20
  • (+1) In light of the formulation of ridge regression (which is mathematically equivalent to this problem) that I gave recently in an answer at http://stats.stackexchange.com/a/164546/919, I would venture to say the answer is "yes"--and all you have to do is modify the dataset initially as described there and apply your sequential solution without any change. I suspect there may be an elegant Bayesian formulation, too, that ought to lead to the same solution. – whuber Aug 06 '15 at 12:10
  • 1
    Is http://stats.stackexchange.com/questions/81740/ a duplicate? – Juho Kokkala Aug 06 '15 at 12:30
  • @whuber, I think it might work. I will give it a try. Though I think some adjustments to your solution might be needed, mainly writing $ {y}_{\star} = {\left[ 0, y \right]}^{T} $. – Royi Aug 06 '15 at 12:54
  • @whuber, What do you mean by Bayesian? Do you mean the Kalman Filter? If you can do that, it would be amazing. – Royi Aug 06 '15 at 13:04
  • Re first comment: Yes, that is exactly what I had in mind. You start off with $\lambda W$ as your augmented data table (for $N=-1$) and begin updating it at the very first observation (at $N=0$). Go on from there to perform a sequential generalized least squares algorithm for $N=0, 1, ... $. Re second comment: The sequential updating algorithm has such a strong flavor of a Bayesian update that trying to frame it as such seems like a promising approach, if only for conceptual purposes. If that's possible, then it's likely already been done and maybe someone will provide a reference for you. – whuber Aug 06 '15 at 13:08
  • @whuber, If someone managed to incorporate regularization into the Kalman filter in a similar model, it would be great. In Kalman Filter the regularization should be applied to the state vector. – Royi Aug 06 '15 at 13:16

0 Answers0