TY - JOUR

T1 - Toeplitz compressed sensing matrices with applications to sparse channel estimation

AU - Haupt, Jarvis

AU - Bajwa, Waheed U.

AU - Raz, Gil

AU - Nowak, Robert

PY - 2010/11/1

Y1 - 2010/11/1

N2 - 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.

AB - 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.

KW - Circulant matrices

KW - Hankel matrices

KW - Toeplitz matrices

KW - compressed sensing

KW - restricted isometry property

KW - sparse channel estimation

KW - wireless communications

UR - http://www.scopus.com/inward/record.url?scp=77956563404&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77956563404&partnerID=8YFLogxK

U2 - 10.1109/TIT.2010.2070191

DO - 10.1109/TIT.2010.2070191

M3 - Article

AN - SCOPUS:77956563404

VL - 56

SP - 5862

EP - 5875

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

SN - 0018-9448

IS - 11

M1 - 5605341

ER -