Open AccessFast Mixed Integer Quadratic Programming for Sparse Signal Estimation
Author(s) -
Sangjun Park,
Heung-No Lee
Publication year - 2018
Publication title -
ieee access
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.587
H-Index - 127
ISSN - 2169-3536
DOI - 10.1109/access.2018.2875022
Subject(s) - aerospace , bioengineering , communication, networking and broadcast technologies , components, circuits, devices and systems , computing and processing , engineered materials, dielectrics and plasmas , engineering profession , fields, waves and electromagnetics , general topics for engineers , geoscience , nuclear engineering , photonics and electrooptics , power, energy and industry applications , robotics and control systems , signal processing and analysis , transportation
It has been recently shown that the $l_{0}$ -norm problem can be reformulated into a mixed integer quadratic programming (MIQP) problem. CPLEX, a commercial optimization software package that can solve integer programming problems, is used to find the global solution to this MIQP problem for sparse signal estimation. However, CPLEX uses an exhaustive approach to search a feasible space to this MIQP problem. Thus, its running time grows exponentially as the problem dimension grows. This means that CPLEX quickly becomes computationally intractable for higher dimension problems. In this paper, we aim to propose a fast first-order-type method for solving this MIQP problem based on the alternating direction method. We conduct extensive simulations to demonstrate that: 1) our method is used to estimate a sparse signal by solving this problem and 2) our method is computationally tractable for problem dimensions up to the order of 1 million.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom