# An adaptive shortest-solution guided decimation approach to sparse high-dimensional linear regression

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 41 references that are in the map.
- First posted on arXiv 28 Nov 2022.

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

- [From Denoising to Compressed Sensing](https://mlsanity.com/paper/1406.4175/) (2014)
- [A survey of sparse representation: algorithms and applications](https://mlsanity.com/paper/1602.07017/) (2016)
- [On Iterative Hard Thresholding Methods for High-dimensional M-Estimation](https://mlsanity.com/paper/1410.5137/) (2014)
- [A Primal Dual Active Set with Continuation Algorithm for the ℓ0-Regularized Optimization Problem](https://mlsanity.com/paper/1403.0515/) (2014)
- [High-dimensional regression in practice: an empirical study of finite-sample prediction, variable selection and ranking](https://mlsanity.com/paper/1808.00723/) (2018)
- [Sparse Estimation with the Swept Approximated Message-Passing Algorithm](https://mlsanity.com/paper/1406.4311/) (2014)
- [Compressed Sensing by Shortest-Solution Guided Decimation](https://mlsanity.com/paper/1709.08388/) (2017)

## Abstract (arXiv)

High-dimensional linear regression model is the most popular statistical model for high-dimensional data, but it is quite a challenging task to achieve a sparse set of regression coefficients. In this paper, we propose a simple heuristic algorithm to construct sparse high-dimensional linear regression models, which is adapted from the shortest solution-guided decimation algorithm and is referred to as ASSD. This algorithm constructs the support of regression coefficients under the guidance of the least-squares solution of the recursively decimated linear equations, and it applies an early-stopping criterion and a second-stage thresholding procedure to refine this support. Our extensive numerical results demonstrate that ASSD outperforms LASSO, vector approximate message passing, and two other representative greedy algorithms in solution accuracy and robustness. ASSD is especially suitable for linear regression problems with highly correlated measurement matrices encountered in real-world applications.