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.

翻译：用于特性选择的贪婪算法被广泛用于恢复线性模型中稀有的高维矢量。 在古典程序中,主要重点是抽样复杂性,很少考虑或根本没有考虑所需的计算资源。我们提出了一个新的在线算法:在线正统匹配追逐(OOMP),用于在稀薄线性回归随机设计设置中在线支持恢复。我们的程序按顺序选择特征,将样本的配置按照需要按候选特性进行,并优化选定一组变量来估计回归系数。关于这一算法产出的理论保证得到证明,并分析其计算复杂性。