论文标题
分布式恢复保证
Recovery Guarantees for Distributed-OMP
论文作者
论文摘要
我们基于正交匹配追踪（OMP）研究了高维稀疏线性回归的分布方案。此类方案特别适合将中央融合中心连接到具有计算和通信限制的最终机器的设置。我们证明，在适当的假设下，分布式-Omp的方案恢复了回归向量的支撑，并在其稀疏性和对数方面的通信中恢复了通信。值得注意的是，即使在低信噪比的情况下，这也能够保持单个机器无法检测支持。我们的模拟表明，分布式功能方案具有更具体的计算密集型方法，在某些情况下甚至表现优于它们。
We study distributed schemes for high-dimensional sparse linear regression, based on orthogonal matching pursuit (OMP). Such schemes are particularly suited for settings where a central fusion center is connected to end machines, that have both computation and communication limitations. We prove that under suitable assumptions, distributed-OMP schemes recover the support of the regression vector with communication per machine linear in its sparsity and logarithmic in the dimension. Remarkably, this holds even at low signal-to-noise-ratios, where individual machines are unable to detect the support. Our simulations show that distributed-OMP schemes are competitive with more computationally intensive methods, and in some cases even outperform them.
