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


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
Issue number9
StatePublished - Sep 1 2015


  • 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