A mixed integer linear programming formulation for the sparse recovery problem in compressed sensing

Karahanoğlu, Nazım Burak and Erdoğan, Hakan and Birbil, Ş. İlker (2013) A mixed integer linear programming formulation for the sparse recovery problem in compressed sensing. In: IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP 2013), Vancouver, BC

Full text not available from this repository. (Request a copy)

Abstract

We propose a new mixed integer linear programming (MILP) formulation of the sparse signal recovery problem in compressed sensing (CS). This formulation is obtained by introduction of an auxiliary binary vector, where ones locate the recovered nonzero indices. Joint optimization for finding this auxiliary vector together with the underlying sparse vector leads to the proposed MILP formulation. By addition of a few appropriate constraints, this problem can be solved by existing MILP solvers. In contrast to other methods, this formulation is not an approximation of the sparse optimization problem, but is its equivalent. Hence, its solution is exactly equal to the optimal solution of the original sparse recovery problem, once it is feasible. We demonstrate this by recovery simulations involving different sparse signal types. The proposed scheme improves recovery over the mainstream CS recovery methods especially when the underlying sparse signals have constant amplitude nonzero elements.
Item Type: Papers in Conference Proceedings
Subjects: T Technology > TK Electrical engineering. Electronics Nuclear engineering
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Electronics
Faculty of Engineering and Natural Sciences
Depositing User: Hakan Erdoğan
Date Deposited: 21 Jan 2014 11:26
Last Modified: 26 Apr 2022 09:12
URI: https://research.sabanciuniv.edu/id/eprint/22987

Actions (login required)

View Item
View Item