Preconditioning for underdetermined linear systems with sparse solutions

Evaggelia Tsiligianni, Lisimachos P. Kondi, Aggelos K Katsaggelos

Research output: Contribution to journalArticlepeer-review

12 Scopus citations

Abstract

Performance guarantees for the algorithms deployed to solve underdetermined linear systems with sparse solutions are based on the assumption that the involved system matrix has the form of an incoherent unit norm tight frame. Learned dictionaries, which are popular in sparse representations, often do not meet the necessary conditions for signal recovery. In compressed sensing (CS), recovery rates have been improved substantially with optimized projections; however, these techniques do not produce binary matrices, which are more suitable for hardware implementation. In this paper, we consider an underdetermined linear system with sparse solutions and propose a preconditioning technique that yields a system matrix having the properties of an incoherent unit norm tight frame. While existing work in preconditioning concerns greedy algorithms, the proposed technique is based on recent theoretical results for standard numerical solvers such as BP and OMP. Our simulations show that the proposed preconditioning improves the recovery rates both in sparse representations and CS; the results for CS are comparable to optimized projections.

Original languageEnglish (US)
Article number7008458
Pages (from-to)1239-1243
Number of pages5
JournalIEEE Signal Processing Letters
Volume22
Issue number9
DOIs
StatePublished - Sep 1 2015

Keywords

  • Compressed sensing
  • incoherent unit norm tight frames
  • preconditioning
  • sparse representations

ASJC Scopus subject areas

  • Signal Processing
  • Electrical and Electronic Engineering
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Preconditioning for underdetermined linear systems with sparse solutions'. Together they form a unique fingerprint.

Cite this