Thesis (Ph. D.)--University of Hong Kong, 1993.

Eigenstructure based techniques have been studied extensively in the last decade to estimate the number and locations of incoming radiating sources using a passive sensor array. One of the early limitations was the computational load involved in arriving at the eigendecompositions. The introduction of VLSI circuits and parallel processors however, has reduced the cost of computation A tremendously. As a consequence, we study eigendecomposition algorithms with highly parallel and A localized data flow, in order to take advantage of VLSI capabilities. This dissertation presents a fast Recursive/Iterative Toeplitz (Hermitian) Eigenspace (RITE) algorithm, and its extension to the generalized strongly regular eigendecomposition situation (C-RITE). Both procedures exhibit highly parallel structures, and their applicability to fast passive array processing is emphasized. The algorithms compute recursively in increasing order, the complete (generalized) eigendecompositions of the successive subproblems contained in the maximum size one. At each order, a number of independent, structurally identical, non-linear problems is solved in parallel. The (generalized) eigenvalues are found by quadratically convergent iterative search techniques. Two different search methods, a restricted Newton approach and a rational approximation based technique are considered. The eigenvectors are found by solving Toeplitz systems efficiently. The multiple minimum (generalized) eigenvalue case and the case of a cluster of small (generalized) eigenvalues are treated also. Eigenpair residual norms and orthonormality norms in comparison with IMSL library routines, indicate good performance and stability behavior for increasing dimensions for both the RITE and C-RITE algorithms. Application of the procedures to the Direction Of Arrival (DOA) identification problem, using the MUSIC algorithm, is presented. The order-recursive properties of RITE and C-RITE permit estimation of angles for all intermediate orders imbedded in the original problem, facilitating the earliest possible estimation of the number and location of radiating sources. The detection algorithm based on RITE or C-RITE can then stop, thereby minimizing the overall computational load to that corresponding to the smallest order for which angle of arrival estimation is indicated to be reliable. Some extensions of the RITE procedure to Hermitian (non-Toeplitz) matrices are presented. This corresponds in the array processing context to correlation matrices estimated from non-linear arrays or incoming signals with non-stationary characteristics. A first—order perturbation approach and two Subspace Iteration (SI) methods are investigated. The RITE decomposition of the Toeplitzsized (diagonally averaged) matrix is used as a starting point. Results show that the SI based techniques lead to good approximation of the eigen-information, with the rate of convergence depending upon the SNR ar1d the angle difference between incoming sources, the convergence being faster than starting the SI method from an arbitrary initial matrix. / Ph. D.

[pt] Em 1994, Henry Landau mostrou que uma matriz de Toeplitz real simétrica pode assumir qualquer valor real. O objetivo desse texto é apresentar a demonstração de Landau. São empregadas técnicas de teoria de grau topológico e teoria espectral. / [en] In 1994, Henry Landau proved that a real, symmetric Toeplitz matrix obtains an arbitrary real spectrum. In this text, we present the details of his proof. The key ingredients are topological degree theory and spectral theory.

by Wun-Cheung Tang. / Thesis (M.Phil.)--Chinese University of Hong Kong, 1998. / Includes bibliographical references. / Abstract also in Chinese. / Abstracts --- p.1 / Introduction --- p.3 / Toeplitz and Circulant Matrices --- p.3 / Conjugate Gradient Method --- p.6 / Cosine Transform Preconditioner --- p.7 / Regularization --- p.10 / Summary --- p.13 / Paper A --- p.19 / Paper B --- p.36

University of Macau / Faculty of Science and Technology / Department of Mathematics

This paper is devoted to asymptotic estimates for the condition numbers $\kappa(T_n(a))=||T_n(a)|| ||T_n^(-1)(a)||$ of large $n\cross n$ Toeplitz matrices $T_N(a)$ in the case where $\alpha \element L^\infinity$ and $Re \alpha \ge 0$ . We describe several classes of symbols $\alpha$ for which $\kappa(T_n(a))$ increases like $(log n)^\alpha, n^\alpha$ , or even $e^(\alpha n)$ . The consequences of the results for singular values, eigenvalues, and the finite section method are discussed. We also consider Wiener-Hopf integral operators and multidimensional Toeplitz operators.

This thesis describes improvements of the periodic QZ algorithm and several variants of the Schur algorithm for block Toeplitz matrices. Documentation of the available software is included.

We consider random symmetric Toeplitz matrices of size n. Assuming that the entries on the diagonals are independent centered random variables with finite γ-th moment (γ>2), a law of large numbers is established for the largest eigenvalue. Following the approach of Sen and Virág (2013), in the limit of large n, the largest rescaled eigenvalue is shown to converge to the limit 0.8288... . The background theory is explained and some symmetry results on the eigenvectors of the Toeplitz matrix and an auxiliary matrix are presented. A numerical investigation illustrates the rate of convergence and the oscillatory nature of the eigenvectors of the Toeplitz matrix. Finally, the possibility of proving a limiting distribution for the largest eigenvalue is discussed, and suggestions for future research are made. / Vi betraktar stokastiska Toeplitz-matriser av storlek n. Givet att elementen på diagonalerna är oberoende, centrerade stokastiska variabler med ändligt γ-moment (γ>2), fastställer vi ett stora talens lag för det största egenvärdet. Med metoden från Sen och Virág (2013) visar vi att det största omskalade egenvärdet konvergera mot gränsen 0.8288... . Bakgrundsteorin förklaras och några symmetriresultat för Toeplitz-matrisens egenvektorer presenteras. En numerisk undersökning illustrerar konvergenshastigheten och Toeplitz-matrisens egenvektorers periodiska natur. Slutligen diskuteras möjligheten att bevisa en asymptotisk fördelning för de största egenvärderna och förslag för fortsatt forskning läggs fram.

An isospectral algorithm is one which manipulates a matrix without changing its spectrum. In this thesis we study three interrelated examples of isospectral algorithms, all pertaining to Toeplitz matrices in some fashion, and one directly involving orthogonal polynomials. The first set of algorithms we study come from discretising a continuous isospectral flow designed to converge to a symmetric Toeplitz matrix with prescribed eigenvalues. We analyse constrained, isospectral gradient flow approaches and an isospectral flow studied by Chu in 1993. The second set of algorithms compute the spectral measure of a Jacobi operator, which is the weight function for the associated orthogonal polynomials and can include a singular part. The connection coefficients matrix, which converts between different bases of orthogonal polynomials, is shown to be a useful new tool in the spectral theory of Jacobi operators. When the Jacobi operator is a finite rank perturbation of Toeplitz, here called pert-Toeplitz, the connection coefficients matrix produces an explicit, computable formula for the spectral measure. Generalisation to trace class perturbations is also considered. The third algorithm is the infinite dimensional QL algorithm. In contrast to the finite dimensional case in which the QL and QR algorithms are equivalent, we find that the QL factorisations do not always exist, but that it is possible, at least in the case of pert-Toeplitz Jacobi operators, to implement shifts to generate rapid convergence of the top left entry to an eigenvalue. A fascinating novelty here is that the infinite dimensional matrices are computed in their entirety and stored in tailor made data structures. Lastly, the connection coefficients matrix and the orthogonal transformations computed in the QL iterations can be combined to transform these pert-Toeplitz Jacobi operators isospectrally to a canonical form. This allows us to implement a functional calculus for pert-Toeplitz Jacobi operators.

This paper is devoted to asymptotic estimates for the condition numbers $\kappa(T_n(a))=||T_n(a)|| ||T_n^(-1)(a)||$ of large $n\cross n$ Toeplitz matrices $T_N(a)$ in the case where $\alpha \element L^\infinity$ and $Re \alpha \ge 0$ . We describe several classes of symbols $\alpha$ for which $\kappa(T_n(a))$ increases like $(log n)^\alpha, n^\alpha$ , or even $e^(\alpha n)$ . The consequences of the results for singular values, eigenvalues, and the finite section method are discussed. We also consider Wiener-Hopf integral operators and multidimensional Toeplitz operators.