Variational Garrote for Sparse Inverse Problems¶

Conference: CVPR 2026 arXiv: 2603.12562 Code: N/A Area: Image Restoration Keywords: sparse inverse problem, Variational Garrote, LASSO, ℓ₀ sparsity, CT reconstruction

TL;DR¶

Under a unified sparse inverse problem framework, this paper systematically compares \(\ell_1\) regularization (LASSO) with Variational Garrote (VG, a method that approximates \(\ell_0\) sparsity via variational binary gating) across three tasks—signal resampling, denoising, and sparse-view CT reconstruction—demonstrating that VG significantly reduces the minimum generalization error in severely underdetermined settings, with the greatest advantage observed at sampling rates below 20% or with very few projection angles.

Background & Motivation¶

Background: Inverse problems—recovering unknown signals from incomplete or corrupted measurements—arise broadly in signal processing and computational imaging, encompassing interpolation, denoising, deblurring, and CT reconstruction. Sparse regularization is a central tool for solving such problems, with different regularizers encoding different prior assumptions.

Limitations of Prior Work: \(\ell_1\) regularization (LASSO) is the dominant sparse recovery approach, offering convex optimization guarantees and computational efficiency. However, LASSO suffers from two fundamental drawbacks: (1) persistent coefficient shrinkage—large coefficients are systematically biased toward zero; and (2) no explicit separation between active and inactive variables—support set recovery is unstable under highly correlated predictors, yielding approximately sparse rather than truly sparse solutions.

Key Challenge: Ideal sparse recovery requires the \(\ell_0\) norm (corresponding to a spike-and-slab prior), but direct optimization is NP-hard. The central challenge is achieving support set recovery quality close to \(\ell_0\) while retaining computational tractability.

Goal: To systematically evaluate the performance gap between \(\ell_1\) and \(\ell_0\)-approximation regularizers across multiple inverse problems, with particular focus on strongly underdetermined regimes where the information bottleneck is severe.

Key Insight: Variational Garrote (VG) introduces latent binary gating variables with a variational relaxation, providing a differentiable approximation to \(\ell_0\). By decoupling coefficient magnitude estimation from support set selection, VG approximates the spike-and-slab prior while retaining a single differentiable objective.

Core Idea: Replace LASSO's continuous shrinkage with VG's variational binary gating to approximate \(\ell_0\) sparsity, achieving more accurate support set recovery and lower generalization error in severely underdetermined inverse problems.

Method¶

Overall Architecture¶

All inverse problems are unified under the linear inverse problem formulation \(\mathbf{y} = \mathbf{A}\mathbf{x} + \boldsymbol{\epsilon}\), which, in a transform domain \(\mathbf{x} = \boldsymbol{\Psi}\mathbf{w}\), reduces to sparse linear regression \(\hat{\mathbf{w}} = \arg\min_{\mathbf{w}} \frac{1}{2}\|\mathbf{y} - \boldsymbol{\Theta}\mathbf{w}\|_2^2 + \lambda \mathcal{R}(\mathbf{w})\). The three tasks share this framework but employ different forward operators and information bottlenecks: signal resampling (subsampling mask), denoising (identity operator with additive noise), and sparse-view CT (discrete Radon transform).

Key Designs¶

Variational Binary Gating Mechanism of Variational Garrote:
- Function: A binary gating variable \(s_i \in \{0,1\}\) is introduced for each regression coefficient \(w_i\), yielding the gated model \(y_\mu = \sum_i w_i s_i X_{i\mu} + \xi_\mu\). A Bernoulli prior \(p(s_i|\gamma) = e^{\gamma s_i}/(1+e^\gamma)\) controls sparsity.
- Mechanism: Exact inference is intractable; mean-field variational inference is applied, \(q(\mathbf{s}) = \prod_i q_i(s_i)\), with activation probability \(m_i = q(s_i=1)\). The objective is the free energy \(F(\mathbf{w}, \mathbf{m}) = \beta E_{\text{rec}} + \Omega_{\text{prior}} - H_{\text{entropy}}\), where the reconstruction energy includes a variance term from gating uncertainty: \(\frac{1}{2}\sum_\mu \sum_i m_i(1-m_i)w_i^2 X_{i\mu}^2\).
- Design Motivation: By decoupling coefficient magnitude (\(w_i\)) from support set selection (\(m_i\)), VG eliminates the continuous shrinkage bias of LASSO. The hyperparameter \(\gamma\) controls prior sparsity, while \(\beta\) can be analytically optimized as \(\log E_{\text{rec}}\), further simplifying tuning.
Model-Agnostic Fair Comparison Methodology:
- Function: A fair cross-model comparison scheme is designed to handle the fact that LASSO's \(\lambda\) and VG's \(\gamma\) are not directly comparable.
- Mechanism: A broad sweep of regularization hyperparameters is performed for each method, and training-error versus generalization-error curves (bias–variance tradeoff) are plotted. The minimum generalization error (MGE) serves as the indicator of each method's optimal performance at each information bottleneck level, with training error used as an empirical proxy for regularization strength.
- Design Motivation: Comparisons made at specific hyperparameter settings may be biased. Comparing optimal performance under each method's best configuration avoids unfairness introduced by incommensurable hyperparameters.
Unified Experimental Framework with Information Bottleneck Analysis:
- Function: Three inverse problems from different domains are cast into a common sparse regression framework; the role of prior–data alignment is examined by systematically varying bottleneck severity.
- Mechanism: Audio signals (synthetic sinusoids and TinySOL flute tones) are strictly sparse in the DCT domain, while CT images exhibit structured sparsity in the pixel domain. Systematic variation of bottleneck parameters (sampling ratio \(R = 5\%\text{–}50\%\), noise amplitude \(\alpha = 0.01\text{–}1\), projection angles \(K = 10\text{–}120\)) reveals how the degree of prior alignment affects reconstruction quality.
- Design Motivation: Signals in different domains differ in their sparsity characteristics. A systematic comparison within a unified framework separates the intrinsic advantage of the method from domain-specific properties.

Loss & Training¶

AdamW optimizer with an initial learning rate of 0.3 and a ReduceLROnPlateau scheduler, terminating when the learning rate falls below \(10^{-5}\) (early stopping), with a maximum of 50,000 iterations. Audio experiments use batches of 100 independent mask/noise instances to stabilize optimization.

Key Experimental Results¶

Main Results¶

Task	Bottleneck Condition	VG Performance	LASSO Performance	VG Advantage
Synthetic signal resampling	\(R = 5\%\text{–}50\%\)	Lower MGE	Higher MGE	Most pronounced at \(R < 20\%\)
Real flute resampling	\(R = 5\%\text{–}50\%\)	Lower MGE	Higher MGE	Clear at low sampling rates
Synthetic signal denoising	\(\alpha = 0.01\text{–}1\)	Lower across full range	Higher	Most significant at low-to-moderate noise
CT (4 datasets)	\(K = 10\text{–}120\)	Lower MSE, smaller variance	Slightly higher	FBP >> LASSO > VG

Ablation Study / Behavioral Analysis¶

Behavioral Feature	VG	LASSO	Notes
Training error trajectory	Abrupt jump	Smooth and continuous	VG gate activation is a discrete phase-transition phenomenon
Jump in denoising	Absent	—	Noise blurs spectral support, suppressing phase transitions
CT boundary sharpness	Occasionally weaker	Slightly better	VG reconstructs uniform regions well but may blur edges
Computational complexity	Additional gating variables	Convex with global guarantees	VG has no global convergence guarantee

Key Findings¶

VG exhibits phase-transition-style jumps in the training error curve—frequency components are activated or deactivated as a whole with changes in \(\gamma\)—consistent with the discrete nature of the spike-and-slab prior. LASSO produces smooth trajectories due to continuous shrinkage.
In the denoising task, VG's jumps disappear, as noise blurs the effective spectral support and small hyperparameter changes no longer trigger discrete component activation.
In CT experiments, VG reconstructs large homogeneous regions more accurately but yields slightly weaker edge sharpness, suggesting that VG and TV regularization are complementary.

Highlights & Insights¶

Training–generalization error curves as a model-agnostic comparison tool: This approach elegantly sidesteps the problem of incommensurable hyperparameters across differently parameterized methods and is transferable to any setting requiring comparison of regularization schemes.
VG's phase-transition behavior reveals the essence of the ℓ₀ prior: The discrete activation of gating variables causes step-wise jumps in training error—VG either fully "sees" a frequency component or ignores it entirely, with no intermediate state as in LASSO. This is advantageous for truly sparse signals.
Prior–data alignment perspective: Regularization is interpreted as a probabilistic prior assumption, and reconstruction quality depends on how well the prior matches the true data distribution. This insight can guide the selection of regularization schemes in specific applications.

Limitations & Future Work¶

Restricted to linear inverse problems: All experiments involve linear forward operators; nonlinear settings (e.g., inverse problems parameterized by deep networks) are not addressed.
CT operates in the pixel domain: Transform-domain sparsification (e.g., wavelets) is not employed, limiting the comprehensiveness of the comparison.
No global convergence guarantee for VG: The non-convex objective is sensitive to initialization and training schedules.
VG + TV combination unexplored: CT results suggest VG excels in homogeneous regions but underperforms LASSO at boundaries; introducing VG-style priors in the gradient domain is a natural direction for improvement.
Potential extension to deep networks: The paper proposes applying VG gating to the weights of the final layers of deep networks as a future direction.

vs. LASSO: LASSO uses a Laplace prior, is computationally efficient, but suffers from continuous shrinkage bias. VG uses a spike-and-slab approximation, achieving more accurate support set recovery but at the cost of non-convexity. VG's advantage is greatest in strongly underdetermined settings.
vs. Elastic Net / SCAD / MCP: These methods also attempt to mitigate LASSO's shrinkage bias but remain within the continuous relaxation framework; VG achieves a more fundamental departure through discrete gating.
vs. Deep learning reconstruction methods: This paper focuses on the effect of priors in classical optimization, but VG's gating concept can be embedded into deep unrolling networks as a learnable prior component.

Rating¶

Novelty: ⭐⭐⭐ VG itself is not new (proposed in 2014); the contribution lies in the systematic experimental comparison.
Experimental Thoroughness: ⭐⭐⭐⭐ Three tasks, multiple datasets, careful regularization sweeps, and detailed error curve analysis.
Writing Quality: ⭐⭐⭐⭐ Theoretical derivations are clear and the unified framework is well constructed.
Value: ⭐⭐⭐ Provides practical guidance for prior selection in sparse inverse problems.