In online sparse linear approximation, measurement vectors arrive one at a time and the learner must commit to a K-sparse coefficient vector before seeing each one, aiming for low static regret against the best fixed sparse vector in hindsight. This work introduces Follow-The-Approximate-Sparse-Leader (FTASL), a meta-policy that converts any greedy sparse-recovery algorithm into an online predictor by running it on the running average of past measurements, with an aggressive every-round variant and a lazy powers-of-two variant. Under a realizability assumption it proves a data-dependent sublinear static-regret bound interpolating between logarithmic and square-root growth.
Online sparse linear approximation (OSLA): measurement vectors arrive one at a time and, before seeing each one, the learner must predict a K-sparse coefficient vector that will best approximate it a…