# Sparse and Smooth Signal Estimation: Convexification of L0 Formulations

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Nov 2018.

## Built on by (most cited first, 10 of 10)

- [Strong Optimal Classification Trees](https://mlsanity.com/paper/2103.15965/) (2021)
- [Grouped Variable Selection with Discrete Optimization: Computational and Statistical Perspectives](https://mlsanity.com/paper/2104.07084/) (2021)
- [On the convex hull of convex quadratic optimization problems with indicators](https://mlsanity.com/paper/2201.00387/) (2022)
- [Safe Screening for Logistic Regression with ℓ0-ℓ2 Regularization](https://mlsanity.com/paper/2202.00467/) (2022)
- [Outlier detection in regression: conic quadratic formulations](https://mlsanity.com/paper/2307.05975/) (2023)
- [Constrained Optimization of Rank-One Functions with Indicator Variables](https://mlsanity.com/paper/2303.18158/) (2023)
- [State-driven Implicit Modeling for Sparsity and Robustness in Neural Networks](https://mlsanity.com/paper/2209.09389/) (2022)
- [Solution Path of Time-varying Markov Random Fields with Discrete Regularization](https://mlsanity.com/paper/2307.13750/) (2023)
- [Scalable First-order Method for Certifying Optimal k-Sparse GLMs](https://mlsanity.com/paper/2502.09502/) (2025)
- [From Sequential Nodes to GPU Batches: Parallel Branch and Bound for Optimal k-Sparse GLMs](https://mlsanity.com/paper/2605.22188/) (2026)

## Abstract (arXiv)

Signal estimation problems with smoothness and sparsity priors can be naturally modeled as quadratic optimization with ℓ0-"norm" constraints. Since such problems are non-convex and hard-to-solve, the standard approach is, instead, to tackle their convex surrogates based on ℓ1-norm relaxations. In this paper, we propose a new iterative (convex) conic quadratic relaxations that exploit not only the ℓ0-"norm" terms, but also the fitness and smoothness functions. The iterative convexification approach substantially closes the gap between the ℓ0-"norm" and its ℓ1 surrogate. These stronger relaxations lead to significantly better estimators than ℓ1-norm approaches and also allow one to utilize affine sparsity priors. In addition, the parameters of the model and the resulting estimators are easily interpretable. Experiments with a tailored Lagrangian decomposition method indicate that the proposed iterative convex relaxations revyield solutions within 1% of the exact ℓ0 approach, and can tackle instances with up to 100,000 variables under one minute.