Online Orthogonal Matching Pursuit
This work addresses the computational resource bottleneck in feature selection for high-dimensional sparse linear regression, which is relevant for practitioners dealing with large datasets.
This paper introduces Online Orthogonal Matching Pursuit (OOMP), an online algorithm for sparse linear regression that sequentially selects features and allocates samples as needed. It provides theoretical guarantees for support recovery and analyzes computational complexity.
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.