Kernel reconstruction: An exact greedy algorithm for compressive sensing

Beihassen Bayar, Nidhal Bouaynaya, Roman Shterenberg

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

Compressive sensing is the theory of sparse signal recovery from undersampled measurements or observations. Exact signal reconstruction is an NP hard problem. A convex approximation using the l1-norm has received a great deal of theoretical attention. Exact recovery using the l1 approximation is only possible under strict conditions on the measurement matrix, which are difficult to check. Many greedy algorithms have thus been proposed. However, none of them is guaranteed to lead to the optimal (sparsest) solution. In this paper, we present a new greedy algorithm that provides an exact sparse solution of the problem. Unlike other greedy approaches, which are only approximations of the exact sparse solution, the proposed greedy approach, called Kernel Reconstruction, leads to the exact optimal solution in less operations than the original combinatorial problem. An application to the recovery of sparse gene regulatory networks is presented.

Original languageEnglish (US)
Title of host publication2014 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2014
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1390-1393
Number of pages4
ISBN (Electronic)9781479970889
DOIs
StatePublished - Feb 5 2014
Event2014 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2014 - Atlanta, United States
Duration: Dec 3 2014Dec 5 2014

Publication series

Name2014 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2014

Other

Other2014 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2014
Country/TerritoryUnited States
CityAtlanta
Period12/3/1412/5/14

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Information Systems

Fingerprint

Dive into the research topics of 'Kernel reconstruction: An exact greedy algorithm for compressive sensing'. Together they form a unique fingerprint.

Cite this