A new strategy for Toeplitz matrix.

Kostic, Aleksandra

Abstract: In this note we bring a completely new strategy for calculating the minimum eigenvalue [[lambda].sub.1.sup.(n)] of a real symmetric, positive definite Toeplitz matrix (RSPDTMO T,. The strategy is particularly applicable to the modeling of secular functions, since it is based on a calculation of the smallest pole of secular functions. It is also pointed to structure of the array, which consists of the smallest eigenvalue of the main sub matrices of the RSPDTM [T.sub.n].

Key words: eigenvalue problem, Toeplitz matrix, new strategy

1. INTRODUCTION

The problem of finding the smallest eigenvalue [[lambda].sub.1.sup.(n)] of a real symmetric, positive definite Toeplitz matrix (RSPDTM) [T.sub.n] is of considerable interest in signal processing. Given the covariance sequence of the observed data, Pisarenko (Pisarenko, 1973) suggested a method which determines the sinusoidal frequencies from the eigenvector of the covariance matrix associated with its minimum eigenvalue.

Because of this, there are various methods for calculating the smallest eigenvalue. These methods are divided into three groups:

1. Methods based on characteristic polynomial of the RSPDTM (Mastronardi, N & Boley, D., 1999, Mackens & Voss, 2000, Melman, 2006, Kostic & Cohodar, 2008)

2. Methods based on secular function (Cybenko & Van Loan, 1986, Mackens & Voss 1997, Kostic & Voss 2002, Kostic, Velic & Hadziabdic, 2010, Kostic, Velic & Bektesevic 2011)

3. Hybrid methods (Kostic & Voss, 2003)

Due to its special structure possessed by Toeplitz matrices we use the information we obtain from the appropriate matrix of a smaller size for calculating the value of the characteristic polynomial or the secular equation. Durbin's algorithm is used to solve Yule-Walker system:

[T.sub.n][y.sup.(n)] = - [([t.sup.(n)]).sup.T] (1)

where

[([t.sup.(n)]).sup.T] = [([t.sub.1], ..., [t.sub.n]).sup.T] (2)

For solving system (1) we use solutions of the Yule-Walker system

[T.sub.j][y.sup.(j)] = ([t.sub.1], [t.sub.2], ..., [t.sub.j]) (3) recursively.

These recursions enable us to determine the position of test parameters in relation to the eigenvalues of the RSPDTM [T.sub.j](j = 1,2, ..., n).

In Section 2 we introduce the basic concepts and notation. In Section 3 we briefly bring you already used information in our earlier algorithms about smallest eigenvalue and some general information about RSPDTM [T.sub.j] (j=1,2,..n). In Section 4 is a new strategy for RSPDTM. In Section 5 we make a conclusion.

2. PRELIMINARES

The Teoplitz matrix is quadratic matrix which has the same elements in its respective diagonals, which means that [a.sub.ij] = [a.sub.n+1-Ln+1-i]. Because we take in consideration symmetric matrices it also means that [a.sub.ij] = [a.sub.ji]. The Teoplitz matrix is defined with vector (1, [t.sub.1], ..., [t.sub.n-1])[member of][R.sup.n] so the [(ij).sup.th] element of an n x n symmetric Toeplitz matrix [T.sub.n] is given by [t.sub.[absolute value of i-j]]. We can conclude, form above given, that Teoplitz matrices are centrosymmetric and satisfy [JT.sub.n]J= [T.sub.n]. We use I for the identity matrix and J:= [([[delta].sub.i,n+1-i)].sub.i,j=1,...,n] for the exchange, or "flip" matrix.

3. SPECIAL STRUCTURE AND ITS CURRENT USE

It is clear that RSPDTM have the following form

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (4)

or, written differently

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5)

In general,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (6)

Next relation is valid for the corresponding eigenvalues [[lambda].sup.(j).sub.i] [less than or equal to] [[lambda].sup.(j).sub.i+1] (i = 1,2,...,j; j = 1,2,...,n).

We have already emphasized the importance of Durbin's algorithm that allows the characteristic polynomial [p.sub.j] ([lambda]) of the RSPDTM [T.sub.j] to be calculated as follows

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (7)

where [[beta].sub.k]([lambda]) are Schur-Szego parameters of the Durbin's algorithm. It is also important to apply

[[beta].sub.j]([lambda]) = [q.sub.1,j]([lambda]):= [p.sub.j]([lambda])/[p.sub.j-1]([lambda]) (8)

which means that [[lambda].sub.1.sup.(j-1)]) is pole of the secular function.

4. A NEW STRATEGY

In this section we present a new strategy. One motivation for this is the fact that the secular functions defined in the work (Kostic, Velic & Bektesevic, 2011) [q.sub.j,n]([lambda]):= [p.sub.n]([lambda])/[p.sub.n-j]([lambda]), can be difficult to model. An attempt was of the modelling was made in paper (Kostic, Velic & Hadziabdic, 2010) for j = 2.

Strategy of the new idea consists in the fact that we calculate the smallest pole of the secular function [q.sub.j,n] ([lambda]). This pole is at the same time the lowest eigenvalue [[lambda].sup.(j).sub.1] of [T.sub.j]. If we know the smallest pole then it would be no problem to find a rational model of our secular equation. For j = n/2 cost for Durbin's step for finding a pole would be [n.sup.2]/2.

Of course the intermediate results obtained from finding the pole can still be used for retrieval of the [[lambda].sup.(n).sub.1].

It is interesting to note that, at the end, some of the eigenvalues of the RSPDTM can now be red for small dimensions. EB. for n = 1 we have certain eigenvalue [[lambda].sup.(1).sub.1] = 1.

For n - 2 we have [[lambda].sup.(2).sub.1] = min(1 - [t.sub.1], 1 + [t.sub.1]). For n = 3 one of the eigenvalues is [t.sub.2]. Therefore it is interesting to consider the array [{[[lambda].sup.(j).sub.1]}.sub.j=1,2,...,n] which consists of smallest eigenvalues of the matrix [T.sub.j] (j=1,2,..n).

This new strategy will be presented for special case of j=1.

ALGORITHM

For k-4,5 until n-1 determine [[lambda].sup.(k).sub.1] make rational model [r.sub.k+1] for [q.sub.1,k+1] find [[lambda].sup.(k+1).sub.1] as smallest root of [r.sub.k+1] End

In the algorithm presented above we have started the first step for k=4 because, as we can se from the earlier text that [[lambda].sup.(1).sub.1] [[lambda].sup.(2).sub.1] and [[lambda].sup.(3).sub.1] are already known.

5. CONCLUSION AND FURTHER RESEARCH

Here, we have adopted a new strategy for calculation of the smallest eigenvalue of the RSPDT matrix. The basic idea is to first calculate pole of our secular equation based on known algorithms. Calculation of the pole provides easier modelling of the secular function. This is a new idea in Toeplitz matrix research.

Future research will be practiced, as usual on the CVL class of matrices, which are the following class of Toeplitz matrices:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (9)

where m is chosen such that the diagonal of 7", is normalized to [t.sub.0] = 1. [T.sub.[theta]] = ([t.sub.i,j]) = (cos([theta](i-j))) and [[eta].sub.k] and [[theta].sub.k] are uniformly distributed random in the interval [0,1].

Further research for the next paper is planned to also exploit the symmetry properties of a real symmetric positive Teoplitz matrices.

6. REFERENCES

Cybenko, G. & Van Loan, C.F. (1986). Computing the minimum eigenvalue of a symmetric positive definite Toeplitz matrix, SIAM J. Sci. Stat. Comput, Vol. 7, No. 1, pp. 123-131. MRO819462(87b:65042)

Kostic, A. & Voss, H (2002). A method of order 1 [square root of 3] for computing the smallest eigenvalue of a symmetric Toeplitz matrix. WSEAS Transactions of Mathematics, Vol. 1, pp. 1-7

Kostic A. & Voss H. (2003). A hybrid method for computing the smallest eigenvalue of a symmetric and positive definite Toeplitz matrix, Report 53, Arbeitsbereich Mathematik, TU Hamburg-Harburg

Kostic A. (2004) Verfahren zur Bestimmung einiger extremaler Eienwerte einer symmetrischen Toeplitz Matrix, Shaker Verlag, ISBN 3-8322-3235-4, Aachen

Kostic (2009) b. Quadratic approximation of characteristic poliynomial of SPDTM, DAAAM Internacional scientific book 2009, Branko Katalinic, pp 71-80. DAAAM Internacional Vienna, 2009

Kostic & Cohodar (2008). Quadratic approximation of characteristic polynomial of symmetric positive definite Toeplitz matrix, Proceedings of 19th International DAAAM Symposium, ISBN 978-3-901509-68-1,ISSN 1726-9679, pp 192

Kostic A., Velic M. & Bektesevic J. (2011). Practical strategies for stabilisation of algorithms based on secular equations of RSPDTM, Proceedings of 10th International Conference on Accomplishments in Electrical and Mechanical Engineering and Information technology (10; 2011; Banja Luka), ISBN 978-99938-39-36-1, COBISS.BH-ID 2029592

Kostic A., Velic M. & Hadziabdic V. (2010). New secular equation of RSPDT matrix and its rational approximation, Proceedings of 21th International DAAAM Symposium, ISBN 978-3-901509-73-51,ISSN 1726-9679, pp 0043

Mackens, W. & Voss, H. (1998). A projection method for computing the minimum eigenvalue of a symmetric positive definite Toeplitz matrix. Lin.Alg.Appl. 275-276:401-415.

Mackens, W. & Voss, H. (2000). Computing the minimum eigenvalue of a symmetric positive definite Toeplitz matrix by Newton-type methods. SIAM J. Sci. Comput., Vol. 21. No. 4, pp. 1650-1656 MR1756049 (2001g:65043)

Mackens, W. & Voss, H. (1997). The minimum eigenvalue of a symmetric positive definite Toeplitz matrix and rational Hermitian interpolSymtion. SIAM J. Matr. Anal Appl, Vol. 18. pp. 523-534

Mastronardi, N & Boley, D.(1999). Computing the smallest eigenpair of a symmetric positive definite Toeplitz matrix. SIAM J. Sci. Comput. Vol. 20, No. 5, pp. 1921-1927. MR 1694690

Pisarenko, V. F. (1973) The retrieval of harmonics from a covariance function. Geophys. J. R.. astr. Soc. Vol. 33., pp. 347-366