基于随机投影和OMP的大规模稀疏线性回归算法

摘要

在海量样本和超高维度的大规模稀疏学习中,其高效训练是一个极具挑战的问题.针对大规模稀疏线性回归中时间效率低和单次计算复杂度高等问题,通过引入随机矩阵算法对数据矩阵进行k-低秩近似降维;为降低求解复杂度,提出利用经典的正交匹配追踪算法(Orthogonal Matching Pursuit,OMP)求解稀疏线性回归问题.理论分析表明提出的基于随机投影OMP算法具有指数级收敛速度和较低的计算复杂度.实验结果表明,其重构误差与传统算法相比具有明显优势,同时验证了算法的收敛性和低复杂性.