  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.
