  Greedy algorithms for feature selection are widely used for recovering sparse
high-dimensional vectors in linear models. In classical procedures, the main
emphasis was put on the sample complexity, with little or no consideration of
the computation resources required. We present a novel online algorithm: Online
Orthogonal Matching Pursuit (OOMP) for online support recovery in the random
design setting of sparse linear regression. Our procedure selects features
sequentially, alternating between allocation of samples only as needed to
candidate features, and optimization over the selected set of variables to
estimate the regression coefficients. Theoretical guarantees about the output
of this algorithm are proven and its computational complexity is analysed.
