On the Relation between Block Diagonal Matrices and Compressive Toeplitz Matrices (bibtex)
by and
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