<p>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 <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="43670_2025_98_Article_IEq1.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="15" /> </InlineMediaObject> <EquationSource Format="TEX">$ \ell ^0 $</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>ℓ</mi> <mn>0</mn> </msup> </math></EquationSource> </InlineEquation>- and <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="43670_2025_98_Article_IEq2.gif" Format="GIF" Height="16" Rendition="HTML" Resolution="72" Type="Linedraw" Width="15" /> </InlineMediaObject> <EquationSource Format="TEX">$ \ell ^1 $</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>ℓ</mi> <mn>1</mn> </msup> </math></EquationSource> </InlineEquation>-based versions of the weighted Least Absolute Shrinkage and Selection Operator (LASSO), 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 by empirically showing that they can outperform standard OMP (with respect to accuracy and computational cost) and 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.</p>

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

期刊论文
发表日期：

2025年2月10日

查看全文

Sina Mohammad-Taheri,
Simone Brugiapaglia

摘要

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 $ \ell ^0 $ $ℓ^{0}$ - and $ \ell ^1 $ $ℓ^{1}$ -based versions of the weighted Least Absolute Shrinkage and Selection Operator (LASSO), 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 by empirically showing that they can outperform standard OMP (with respect to accuracy and computational cost) and 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.