TY - GEN

T1 - Toeplitz-structured compressed sensing matrices

AU - Bajwa, Waheed U.

AU - Haupt, Jarvis D.

AU - Raz, Gil M.

AU - Wright, Stephen J.

AU - Nowak, Robert D.

PY - 2007/12/1

Y1 - 2007/12/1

N2 - The problem of recovering a sparse signal x ∈ ℝn from a relatively small number of its observations of the form y = Ax ∈ ℝk, where A is a known matrix and k ≪ n, has recently received a lot of attention under the rubric of compressed sensing (CS) and has applications in many areas of signal processing such as data compression, image processing, dimensionality reduction, etc. Recent work has established that if A is a random matrix with entries drawn independently from certain probability distributions then exact recovery of x from these observations can be guaranteed with high probability. In this paper, we show that Toeplitz-structured matrices with entries drawn independently from the same distributions are also sufficient to recover x from y with high probability, and we compare the performance of such matrices with that of fully independent and identically distributed ones. The use of Toeplitz matrices in CS applications has several potential advantages: (i) they require the generation of only O(n) independent random variables; (ii) multiplication with Toeplitz matrices can be efficiently implemented using fast Fourier transform, resulting in faster acquisition and reconstruction algorithms; and (iii) Toeplitz-structured matrices arise naturally in certain application areas such as system identification.

AB - The problem of recovering a sparse signal x ∈ ℝn from a relatively small number of its observations of the form y = Ax ∈ ℝk, where A is a known matrix and k ≪ n, has recently received a lot of attention under the rubric of compressed sensing (CS) and has applications in many areas of signal processing such as data compression, image processing, dimensionality reduction, etc. Recent work has established that if A is a random matrix with entries drawn independently from certain probability distributions then exact recovery of x from these observations can be guaranteed with high probability. In this paper, we show that Toeplitz-structured matrices with entries drawn independently from the same distributions are also sufficient to recover x from y with high probability, and we compare the performance of such matrices with that of fully independent and identically distributed ones. The use of Toeplitz matrices in CS applications has several potential advantages: (i) they require the generation of only O(n) independent random variables; (ii) multiplication with Toeplitz matrices can be efficiently implemented using fast Fourier transform, resulting in faster acquisition and reconstruction algorithms; and (iii) Toeplitz-structured matrices arise naturally in certain application areas such as system identification.

KW - Compressed sensing

KW - Restricted isometry property

KW - System identification

KW - Toeplitz matrices

KW - Underdetermined systems of linear equations

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

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

U2 - 10.1109/SSP.2007.4301266

DO - 10.1109/SSP.2007.4301266

M3 - Conference contribution

AN - SCOPUS:41949102240

SN - 142441198X

SN - 9781424411986

T3 - IEEE Workshop on Statistical Signal Processing Proceedings

SP - 294

EP - 298

BT - 2007 IEEE/SP 14th Workshop on Statistical Signal Processing, SSP 2007, Proceedings

T2 - 2007 IEEE/SP 14th WorkShoP on Statistical Signal Processing, SSP 2007

Y2 - 26 August 2007 through 29 August 2007

ER -