Optimization Online


Sparse and Smooth Signal Estimation: Convexification of L0 Formulations

Alper Atamturk (atamturk***at***berkeley.edu)
Andres Gomez (agomez***at***pitt.edu)
Shaoning Han (shaoning.han***at***pitt.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.

Download: [PDF]

Entry Submitted: 11/27/2018
Entry Accepted: 11/27/2018
Entry Last Modified: 01/22/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society