Sparse and Smooth Signal Estimation: Convexification of L0 Formulations

Alper Atamturk, Andres Gomez and Shaoning Han. “Sparse and Smooth Signal Estimation: Convexification of L0 Formulations”. Journal of Machine Learning Research. 

Abstract: Signal estimation problems with smoothness and sparsity priors can be naturally modeled as quadratic optimization with L0-“norm” constraints. Since such problems are non-convex and hard-to-solve, the standard approach is, instead, to tackle their convex surrogates based on L1-norm relaxations. In this paper, we propose new iterative (convex) conic quadratic relaxations that exploit not only the L0-“norm” terms, but also the fitness and smoothness functions. The iterative convexification approach substantially closes the gap between the L0-“norm” and its L1 surrogate. These stronger relaxations lead to significantly better estimators than L1-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 yield solutions within 1% of the exact L0 approach, and can tackle instances with up to 100,000 variables under one minute.