Sparse and Smooth Signal Estimation: Convexification of L0 Formulations

Abstract

Signal estimation problems with smoothness and sparsity priors can be naturally modeled as quadratic optimization with ${\ell }_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 ${\ell }_1$-norm relaxations. In this paper, we propose a new iterative (convex) conic quadratic relaxations that exploit not only the ${\ell }_0$-"norm" terms, but also the fitness and smoothness functions. The iterative convexification approach substantially closes the gap between the ${\ell }_0$-"norm" and its ${\ell }_1$ surrogate. These stronger relaxations lead to significantly better estimators than ${\ell }_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 \rev{yield solutions within 1\% of the exact ${\ell }_0$ approach, and can tackle instances with up to 100,000 variables under one minute.

arXiv commentBCOL Research Report 18.05, IEOR, UC Berkeley

References in corpus (12)

• Nearly unbiased variable selection under minimax concave penalty
• Consistency of the group Lasso and multiple kernel learning
• Fast Online Deconvolution of Calcium Imaging Data
• Fast non-negative deconvolution for spike train inference from population calcium imaging
• The ALAMO approach to machine learning
• Extended Comparisons of Best Subset Selection, Forward Stepwise Selection, and the Lasso
• Properties and refinements of the fused lasso
• Lower bounds on the performance of polynomial-time algorithms for sparse linear regression
• The DFS Fused Lasso: Linear-Time Denoising over General Graphs
• Tight MIQP Reformulations for Semi-Continuous Quadratic Programming: Lift-and-Convexification Approach
• Regularization vs. Relaxation: A conic optimization perspective of statistical variable selection
• Rank-one Convexification for Sparse Regression

Cited by in corpus (4)

• Rank-one Convexification for Sparse Regression
• Ideal formulations for constrained convex optimization problems with indicator variables
• 2x2 convexifications for convex quadratic optimization with indicator variables
• Scalable Inference of Sparsely-changing Markov Random Fields with Strong Statistical Guarantees