# Recovery Guarantees for Distributed-OMP

arXiv: https://arxiv.org/abs/2209.07230 · HTML: https://mlsanity.com/paper/2209.07230/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 76 references that are in the map.
- First posted on arXiv 15 Sep 2022.

## Builds on (most cited first, 13 of 13)

- [Best Subset Selection via a Modern Optimization Lens](https://mlsanity.com/paper/1507.03133/) (2015)
- [CoCoA: A General Framework for Communication-Efficient Distributed Optimization](https://mlsanity.com/paper/1611.02189/) (2016)
- [Efficient Distributed Learning with Sparsity](https://mlsanity.com/paper/1605.07991/) (2016)
- [Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation](https://mlsanity.com/paper/1311.3494/) (2013)
- [On the Optimality of Averaging in Distributed Statistical Learning](https://mlsanity.com/paper/1407.2724/) (2014)
- [Distributed Learning with Sublinear Communication](https://mlsanity.com/paper/1902.11259/) (2019)
- [Clustered Federated Learning via Generalized Total Variation Minimization](https://mlsanity.com/paper/2105.12769/) (2021)
- [Distributed Sparse Normal Means Estimation with Sublinear Communication](https://mlsanity.com/paper/2102.03060/) (2021)
- [The Trimmed Lasso: Sparse Recovery Guarantees and Practical Optimization by the Generalized Soft-Min Penalty](https://mlsanity.com/paper/2005.09021/) (2020)
- [Distributed Sparse Feature Selection in Communication-Restricted Networks](https://mlsanity.com/paper/2111.02802/) (2021)
- [Decentralized Joint-Sparse Signal Recovery: A Sparse Bayesian Learning Approach](https://mlsanity.com/paper/1507.02387/) (2015)
- [Distributed recovery of jointly sparse signals under communication constraints](https://mlsanity.com/paper/1611.02431/) (2016)
- [Tight Recovery Guarantees for Orthogonal Matching Pursuit Under Gaussian Noise](https://mlsanity.com/paper/1905.12347/) (2019)

## Abstract (arXiv)

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.