Toeplitz Matrices and Compressive Sensing

Last week, at the last GdR meeting "MIA et Ondes" organized by Alexandre Baussard and Jalal Fadili, I had a brief conversation with Frederic Barbaresco and Antoine Liutkus, While discussing, it became apparent that some of the things Frederic does in radar signal processing might be very relevant to a set of issues we have seen in compressive sensing and related fields. In particular, their sensors put out covariance matrices that happen to have a Toeplitz structure. The literature on the more general model of covariance matrices will be done later but in order to see of the interesting mathematics developed there would be a further interest, I went back to the search feature of this blog and started looking where we had instances of Toeplitz matrices even though in some cases, those are not positive definite.

First a definition, quite simply a Toeplitz matrix is "a matrix with the same entries along all its diagonals". Hence, because these matrices represents  discretized version of convolution , it pops up in many instance of sensing or in our case, in many instances measurement matrices. For short, any time there is tomography, a Toeplitz matrix should be in the surroundings.  They can also characterizes a discrete linear time invariant (LTI) systems. 

From [1]

Signal processing theory such as prediction, estimation, detection, classification, regression, and communcations and information theory are most thoroughly developed under the assumption that the mean is constant and that the covariance is Toeplitz, i.e., KX(k, j) = KX(k − j), in which case the process is said to be weakly stationary. (The terms “covariance stationary” and “second order stationary” also are used when the covariance is assumed to be Toeplitz.) In this case the n × n covariance matrices Kn = [KX(k, j); k, j = 0, 1, . . . , n − 1] are Toeplitz matrices. Much of the theory of weakly stationary processes involves applications of Toeplitz matrices. Toeplitz matrices also arise in solutions to differential and integral equations, spline functions, and problems and methods in physics, mathematics, statistics, and signal processing.

From [2] 

Toeplitz matrices appear naturally in a variety of problems in engineering. Since positive semi-definite Toeplitz matrices can be viewed as shift-invariant autocorrelation matrices, considerable attention has been paid to them, especially in the areas of stochastic filtering and digital signal processing applications [12] and [21]. Several problems in digital signal processing and control theory require the computation of a positive definite Toeplitz matrix that closely approximates a given matrix. For example, because of rounding or truncation errors incurred while evaluating F, F does not satisfy one or all conditions. Another example in the power spectral estimation of a wide-sense stationary process from a finite number of data, the matrix F formed from the estimated autocorrelation coefficients, is often not a positive definite Toeplitz matrix [18]. In control theory, the Gramian assignment problem for discrete-time single input system requires the computation of a positive definite Toeplitz matrix which also satisfies certain inequality constraints [16].

As one can see from the references below, most of the community's concern has been focused on its use for the measurement matrices and how admissibility condition could be derived (Restricted Isometry property). The Toeplitz model is also behind the streaming measurement model and attendant reconstruction. The generic problem of tomography is a convolution of the real world with probes and we are looking for understanding those measurement matrices in essence. In particular coded aperture falls in that toeplitz/convolution model.

From slides of [40]

From [4]

In our context, the design of a metric that is specific to the manifold of positive definite or positive definite Toeplitz matrices could have an impact on everything that let us design and know better the measurement matrix used in actual hardware i.e. blind deconvolution or calibration. It could also have an impact detection in systems other than radar such as the recent compressive hardware such as the lightfield and time of flights cameras or even random system systems.... to be continued.

Merry Christmas y'all.

 PS: As a passing note, I noted in 2007 thaT Nick Trefethen HAD pointed out that both some Random matrices and Toeplitz matrices have large pseudo-spectra:

The eigenvalues of finite banded Toeplitz matrices lie on curves in the complex plane that have been characterized by Schmidt and Spitzer [SS60]. In contrast, the spectrum of the corresponding infinite dimensional Toeplitz operator is the set of points in the complex plane that a(T) encloses with non-zero winding number; see Theorem 1.17 of [BS99]. The limit of the spectrum of banded Toeplitz matrices as the dimension goes to infinity is thus typically very different from the spectrum of the limit.

This uncomfortable situation can be resolved by considering the behavior of pseudospectra. Though the eigenvalues of the finite Toeplitz matrices may fall on curves in the complex plane, Landau [Lan75], Reichel and Trefethen [RT92b], and Böttcher [Böt94] have observed that the resolvent norm ||(zI-TN)-1|| grows exponentially in the matrix dimension for all z in the interior of the spectrum of the corresponding infinite dimensional operator. (As a result, it is difficult to accurately compute eigenvalues of non-symmetric banded Toeplitz matrices even for matrices of relatively modest dimensions, and this signals a warning against basing analysis of finite Toeplitz matrices based on eigenvalues alone.) Furthermore the above cited authors also concluded that the pseudospectra of TN converge to the pseudospectra of T.

References:

1. Toeplitz and Circulant Matrices: A review, Robert M. Gray
2. Toeplitz Matrix Approximation by Suliman Al-Homidan
3. Coding and sampling for compressive tomography, David J. Brady
4. Random Convolution and l_1Filtering, Justin Romberg
5. Architectures for Compressive Sampling Justin Romberg
6. Compression Limits for Random Vectors with Linearly Parameterized Second-Order Statistics by Daniel Romero, Roberto Lopez-Valcarce, Geert Leus
7. Joint Sparsity Recovery for Spectral Compressed Sensing by Yuejie Chi
8. Covariance Estimation in High Dimensions via Kronecker Product Expansions by Theodoros Tsiligkaridis, Alfred O. Hero III
9. SENSING BY RANDOM CONVOLUTION Justin Romberg
10. COMPRESSIVE SENSING BY RANDOM CONVOLUTION, Justin Romberg
11. Practical Compressive Sensing with Toeplitz and Circulant Matrices Wotao Yin, Simon Morgan, Junfeng Yang, Yin Zhang
12. Random Filters for Compressive Sampling and Reconstruction .J. Tropp, M. Wakin, M. Duarte, D. Baron, and R. Baraniuk
13. Compressed Sensing of Analog Signals in Shift-Invariant Spaces, Yonina C. Eldar
14. Compressive Sensing for Streaming Signals using the Streaming Greedy Pursuit, Petros T. Boufounos, M. Salman Asif
15. Compressive System Identification (CSI): Theory and Applications of Exploiting Sparsity in the Analysis of High-Dimensional Dynamical Systems
16.  Concentration of Measure Inequalities for Compressive Toeplitz Matrices with Applications (See also the companion technical report).
17. Compressive System Identification (CSI): Theory and Applications of Exploiting Sparsity in the Analysis of High-Dimensional Dynamical Systems. Borhan Sanandaji 
18. Toeplitz Matrix Based Sparse Error Correction in System Identification: Outliers and Random Noises by Weiyu Xu, Er-Wei Bai, Myung Cho
19. The Circulant Rational Covariance Extension Problem: The Complete Solution  by Anders Lindquist, Giorgio Picci
20. Novel Toeplitz Sensing Matrices for Compressive Radar Imaging  Lu Gan , Kezhi Li , Cong Ling 
21. Calibration and Blind Compressive Sensing
22. Looking through walls and around corners with incoherent light: Wide-field real-time imaging through scattering media [updated]
23. LEARNING A CIRCULANT SENSING MATRIX by YANGYANG XU, WOTAO YIN, SUSAN CHEN, AND STANLEY OSHER. 
24. Concentration of Measure Inequalities for Toeplitz Matrices with Applications by Borhan M. Sanandaji, Tyrone L. Vincent, and Michael B. Wakin. The abstract reads:
25. On the Relation between Block Diagonal Matrices and Compressive Toeplitz Matrices by Han Lun Yap and Christopher J. Rozell.
26. Compressive Topology Identification of Interconnected Dynamic Systems via Clustered Orthogonal Matching Pursuit by Borhan Sanandaji, Tyrone Vincent, and Michael Wakin. 
27. Exact Topology Identification of Large-Scale Interconnected Dynamical Systems from Compressive Observations by Borhan Sanandaji, Tyrone Vincent, and Michael Wakin. 
28. Orthogonal symmetric Toeplitz matrices for compressed sensing: Statistical isometry property by Kezhi Li, Lu Gan, Cong Ling.
29. Circulant and Toeplitz Matrices in Compressed Sensing by Holger Rauhut.
30. Toeplitz-Structured Chaotic Sensing Matrix for Compressive Sensing by Lei Yu,Jean-Pierre Barbot, Gang Zheng, Hong Sun. 
31. YALL1: Your ALgorithms for L1, Random Teoplitz / Circulant / Convolution
32. Practical compressive sensing with Toeplitz and circulant matrices byWotao Yin, Simon Morgan, Junfeng Yang, Yin Zhang.
33. CS: A Short Discussion with Gerry Skinner, a Specialist in Coded Aperture Imaging. 
34. A Restricted Isometry Property for Structurally-Subsampled Unitary Matrices by Waheed Bajwa, Akbar Sayeed and Robert Nowak, 
35. Compressed Blind De-convolution by Venkatesh Saligrama, Manqi Zhao.
36. Toeplitz-structured compressed sensing matrices by Waheed Bajwa, Jarvis Haupt, Gil Raz,Stephen Wright, and Robert Nowak. 
37. Toeplitz Random Encoding for Reduced Acquisition Using Compressed Sensing by Haifeng Wang, Dong Liang, Kevin F. King, Leslie Ying. The attendant poster is here.
38. Circulant and Toeplitz Matrices in Compressed Sensing by Holger Rauhut. The abstract reads:
39. A New Algorithm for the Nearest Singular Toeplitz Matrix to a Given Toeplitz Matrix, Andrew Yagle
40. Roummel Marcia and Rebecca Willett, Compressive Coded Aperture Superresolution Image Reconstruction - additional material can be found here while the slides are here
41. CS: The EPFL CMOS CS Imager, Compressive Sampling of Pulse Trains Spread the Spectrum !
42. Toeplitz compressed sensing matrices with applications to sparse channel estimation, Jarvis Haupt,Waheed Bajwa, Gil Raz and Robert Nowak
43. Deterministic Designs with Deterministic Guarantees: Toeplitz Compressed Sensing Matrices, Sequence Designs and System Identification by Venkatesh Saligrama. 
44. Compressed Sensing: Compressive Coded Aperture Superresolution Image Reconstruction, TOMBO, CASSI
45. Compressed channel sensing by R. Nowak, W. Bajwa, and J. Haupt
46. Toeplitz Block Matrices in Compressed Sensing. by Florian Sebert, Leslie Ying, and Yi Ming Zou 
47. Annihilating filter-based decoding in the compressed sensing framework by Ali Hormati and Martin Vetterli "....we first denoise the signal using an iterative algorithm that finds the closest rank $k$ and Toeplitz matrix to the measurements matrix (in Frobenius norm) before applying the annihilating filter method..." 
48. Toeplitz-structured compressed sensing matrices by Waheed Bajwa, Jarvis Haupt, Gil Raz, Stephen Wright, and Robert Nowak. 
49. Nick Trefethen pointed out that both some Random matrices and Toeplitz matrices have large pseudo-spectra: http://nuit-blanche.blogspot.fr/2007/07/random-projection-lapack.html
50. Randomized Matrix Computations by Victor Y. Pan, Guoliang Qian, Ai-Long Zheng. 

Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.