The greedy side of the LASSO: New algorithms for weighted sparse recovery via loss function-based orthogonal matching pursuit

Author name not available (Why is that?)

Publication date: 1 March 2023

Abstract: We propose a class of greedy algorithms for weighted sparse recovery by considering new loss function-based generalizations of Orthogonal Matching Pursuit (OMP). Given a (regularized) loss function, the proposed algorithms alternate the iterative construction of the signal support via greedy index selection and a signal update based on solving a local data-fitting problem restricted to the current support. We show that greedy selection rules associated with popular weighted sparsity-promoting loss functions admit explicitly computable and simple formulas. Specifically, we consider

e l l^{0}

- and

e l l^{1}

-based versions of the weighted LASSO (Least Absolute Shrinkage and Selection Operator), the Square-Root LASSO (SR-LASSO) and the Least Absolute Deviations LASSO (LAD-LASSO). Through numerical experiments on Gaussian compressive sensing and high-dimensional function approximation, we demonstrate the effectiveness of the proposed algorithms and empirically show that they inherit desirable characteristics from the corresponding loss functions, such as SR-LASSO's noise-blind optimal parameter tuning and LAD-LASSO's fault tolerance. In doing so, our study sheds new light on the connection between greedy sparse recovery and convex relaxation.

Has companion code repository: https://github.com/sina-taheri/greedy_lasso_womp

This page was built for publication: The greedy side of the LASSO: New algorithms for weighted sparse recovery via loss function-based orthogonal matching pursuit

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6428119)