Sparse and Smooth Signal Estimation: Convexification of L0 Formulations
Alper Atamturk (atamturkberkeley.edu)
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 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. Experiments using an off-the-shelf conic quadratic solver on synthetic as well as real datasets indicate that the proposed iterative convex relaxations lead to significantly better estimators than L1-norm while preserving the computational efficiency. In addition, the parameters of the model and the resulting estimators are easily interpretable.
Keywords: Mixed-integer quadratic optimization, conic quadratic optimization, perspective formulation, lasso, sparsity
Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )
Citation: BCOL Research Report 18.05, IEOR, University of California-Berkeley.
Entry Submitted: 11/27/2018
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|