On the Relation between Block Diagonal Matrices and Compressive Toeplitz Matrices (bibtex)

by H.L. Yap and C.J. Rozell

Abstract:

In a typical communications problem, Toeplitz matrices $\Phi$ arise when modeling the task of determining an unknown impulse response $a$ from a given probe signal $\phi$. When $a$ is sparse, then whenever $\Phi$ formed from the probe signal $\phi$ satisfy the Restricted Isometry Property (RIP), $a$ can be robustly recovered from its measurements via l1-minimization. In this paper, we derived the RIP for compressive Toeplitz matrices whose number of rows of the matrices $J$ is much smaller than the number of columns $N$. We show that J should scale like $J \sim S^2 \log(N)$, where $S$ is the sparsity of the impulse response. While this is marginally worse than the state-of-the-art scaling currently achieved in the literature, the novelty of this work comes from making the relation between the Toeplitz matrix of interest to a block diagonal matrix. The proof of the RIP then follows from using recent results on the concentration of measure inequalities of block diagonal matrices, together with a standard covering-and-counting argument.

Reference:

On the Relation between Block Diagonal Matrices and Compressive Toeplitz MatricesH.L. Yap and C.J. Rozell. Technical report, Georgia Institute of Technology, School of Electrical and Computer Engineering, October 2011.

Bibtex Entry:

@TechReport{yap.11h, author = {Yap, H.L. and Rozell, C.J.}, title = {On the Relation between Block Diagonal Matrices and Compressive {T}oeplitz Matrices}, institution = {Georgia Institute of Technology, School of Electrical and Computer Engineering}, year = 2011, month = {October}, abstract = {In a typical communications problem, Toeplitz matrices $\Phi$ arise when modeling the task of determining an unknown impulse response $a$ from a given probe signal $\phi$. When $a$ is sparse, then whenever $\Phi$ formed from the probe signal $\phi$ satisfy the Restricted Isometry Property (RIP), $a$ can be robustly recovered from its measurements via l1-minimization. In this paper, we derived the RIP for compressive Toeplitz matrices whose number of rows of the matrices $J$ is much smaller than the number of columns $N$. We show that J should scale like $J \sim S^2 \log(N)$, where $S$ is the sparsity of the impulse response. While this is marginally worse than the state-of-the-art scaling currently achieved in the literature, the novelty of this work comes from making the relation between the Toeplitz matrix of interest to a block diagonal matrix. The proof of the RIP then follows from using recent results on the concentration of measure inequalities of block diagonal matrices, together with a standard covering-and-counting argument.}, url = {http://siplab.gatech.edu/pubs/yapGTTR2011.pdf} }

Powered by bibtexbrowser