论文标题
在线正交匹配追求
Online Orthogonal Matching Pursuit
论文作者
论文摘要
用于特征选择的贪婪算法被广泛用于恢复线性模型中的稀疏高维矢量。在经典程序中，主要重点是样本复杂性，几乎没有考虑到所需的计算资源。我们提出了一种新颖的在线算法：在线正交匹配追踪（OOMP），以在线支持稀疏线性回归的随机设计设置。我们的过程依次选择功能，仅根据需要的样品分配在候选特征之间进行交替，并在选定的一组变量集上进行优化以估计回归系数。关于该算法的输出的理论保证已得到证明，并分析了其计算复杂性。
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.
