Toeplitz compressed sensing matrices with applications to sparse channel estimation

Jarvis Haupt, Waheed U. Bajwa, Gil Raz, Robert Nowak

Research output: Contribution to journalArticlepeer-review

341 Scopus citations


Compressed sensing (CS) has recently emerged as a powerful signal acquisition paradigm. In essence, CS enables the recovery of high-dimensional sparse signals from relatively few linear observations in the form of projections onto a collection of test vectors. Existing results show that if the entries of the test vectors are independent realizations of certain zero-mean random variables, then with high probability the unknown signals can be recovered by solving a tractable convex optimization. This work extends CS theory to settings where the entries of the test vectors exhibit structured statistical dependencies. It follows that CS can be effectively utilized in linear, time-invariant system identification problems provided the impulse response of the system is (approximately or exactly) sparse. An immediate application is in wireless multipath channel estimation. It is shown here that time-domain probing of a multipath channel with a random binary sequence, along with utilization of CS reconstruction techniques, can provide significant improvements in estimation accuracy compared to traditional least-squares based linear channel estimation strategies. Abstract extensions of the main results are also discussed, where the theory of equitable graph coloring is employed to establish the utility of CS in settings where the test vectors exhibit more general statistical dependencies.

Original languageEnglish (US)
Article number5605341
Pages (from-to)5862-5875
Number of pages14
JournalIEEE Transactions on Information Theory
Issue number11
StatePublished - Nov 2010

Bibliographical note

Funding Information:
Manuscript received August 29, 2008; revised March 17, 2010. Date of current version October 20, 2010. This work was supported in part by the National Science Foundation under Grant CCF-0353079 and Grant ECS-0529381, and in part by the DARPA Analog-to-Information Program. The material in this paper was presented in part at the 14th IEEE/SP Workshop on Statistical Signal Processing, Madison, WI, August 2007, and at the 42nd Annual Conference on Information Sciences and Systems, Princeton, NJ, March 2008.


  • Circulant matrices
  • Hankel matrices
  • Toeplitz matrices
  • compressed sensing
  • restricted isometry property
  • sparse channel estimation
  • wireless communications


Dive into the research topics of 'Toeplitz compressed sensing matrices with applications to sparse channel estimation'. Together they form a unique fingerprint.

Cite this