The classical result of Vandermonde decomposition of positive semidefinite Toeplitz matrices can date back to the early twentieth century. It forms the basis of modern subspace and recent atomic norm methods for frequency estimation. In this paper, we study the Vandermonde decomposition in which the frequencies are restricted to lie in a given interval, referred to as frequency-selective Vandermonde decomposition. The existence and uniqueness of the decomposition are studied under explicit conditions on the Toeplitz matrix. The new result is connected by duality to the positive real lemma for trigonometric polynomials nonnegative on the same frequency interval. Its applications in the theory of moments and line spectral estimation are illustrated. In particular, it provides a solution to the truncated trigonometric K-moment problem. It is used to derive a primal semidefinite program formulation of the frequency-selective atomic norm in which the frequencies are known a priori to lie in a certain frequency band. Numerical examples are also provided.
This paper extends our conference paper @cite_22 in which the FS Vandermonde decomposition of Toeplitz matrices was studied. In addition to this, we show in this paper the connection between the FS Vandermonde decomposition and the PRL for trigonometric polynomials. Its applications to the moment theory and frequency estimation are also studied in more detail.
@cite_22
2516586151 2045463928 2155893732 2747169803
A classical result in mathematics dating back to the early twentieth century states that a rank-deficient, positive semidefinite, Toeplitz matrix admits a unique Vandermonde decomposition. This forms the basis of modern subspace and recent continuous compressed sensing (or gridless sparse) methods for frequency estimation. Conventionally, the Vandermonde decomposition is defined on the entire frequency domain; but in this paper, we show that the decomposition can be restricted to a prescribed frequency interval if the Toeplitz matrix also satisfies another linear matrix inequality. Besides solving an open classical moment problem in mathematics, this result is applied to practical frequency estimation scenarios in which the frequencies are known a priori to lie in certain frequency intervals. We show that the recent continuous compressed sensing methods derived based on the standard Vandermonde decomposition can be modified in a universal yet simple way to exploit this prior knowledge by applying the new Vandermonde decomposition result. Numerical results are provided to illustrate advantages of the proposed solutions. Part I: Toeplitz Forms: Preliminaries Orthogonal polynomials. Algebraic properties Orthogonal polynomials. Limit properties The trigonometric moment problem Eigenvalues of Toeplitz forms Generalizations and analogs of Toeplitz forms Further generalizations Certain matrices and integral equations of the Toeplitz type Part II: Applications of Toeplitz Forms: Applications to analytic functions Applications to probability theory Applications to statistics Appendix: Notes and references Bibliography Index. This paper considers the problem of finding n × n matrices Ak and Bk that minimize @math , where @math denotes Kronecker product and T is a banded n × n block Toeplitz matrix with banded n × n Toeplitz blocks. It is shown that the optimal Ak and Bk are banded Toeplitz matrices, and an efficient algorithm for computing the approximation is provided. An image restoration problem from the Hubble Space Telescope (HST) is used to illustrate the effectiveness of an approximate SVD preconditioner constructed from the Kronecker product decomposition. In a typical communications problem, Toeplitz matrices Φ arise when modeling the task of determining an unknown impulse response a from a given probe signal φ. When a is sparse, then whenever Φ formed from the probe signal φ 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 ∼ S 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.