Nuit Blanche: Toeplitz Matrices and Compressive Sensing

Wednesday, December 25, 2013

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: