Determination of eigenvalues from middle spectrum of positive definite Toeplitz matrix by Newton method for characteristic polynomial.

Kostic, Aleksandra

1. INTRODUCTION

The problem of finding the smallest eigenvalue [[lambda].sub.1] 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. For this reason there are more methods for determination of the smallest eigenvalue. Trench (Trench, 1989) was investigating determination of eigenvalues of RSPDTM and he suggested determination of arbitrary eigenvalue from the spectrum by applying the Pegasus method to the secular function, because convergence of the Newton method for the secular function was not being assured without addition conditions.

Kostic (Kostic, 2004) has determined first five zeros of characteristic polynomial, i.e. secular function. To find characteristic polynomial above author has used Meahly strategy, but in the case of secular function author has modified secular function in interval of two poles, where desired zero lied. An expensive calculating of second derivative of polynomial avoids the usage of Newton method for determination of arbitrary eigenvalue in the case of characteristic polynomial.

Kostic and Cohodar (Kostic & Cohodar, 2008) have solved this problem coming up to the computation of the second order polynomial to 0.75 iterations. Melman in (Melman, 2006) has also recommended this method applying cheap determination of the first derivative of the function.

Melman in (Melman, 2006) shows that this recursion can be replaced by a shorter computation, involving the computation of the trace of an appropriate matrix, that, after solving the Yule-Walker equations, requires only O(n) flops.

As it is pointed out, the paper presents Newton method for determination of eigenvalue from the middle spectrum, in other word from arbitrary place, for characteristic polynomial. Specified structure of the Toeplitz matrix provides relatively simple and cheaper calculating the second derivatives of function in sense of flop's numbers. The basic properties of Toeplitz matrices and used notation are presented in Section 2. In Section 3 we compute the new Newton's method and in Section 4 we compare the methods. The conclusion and further research are presented in Section 5.

2. PRELIMINARIES

The [(i,j).sup.th] element of an n x n symmetric Toeplitz matrix [T.sub.n] is given by [t.sub.[absolute value of i-j]] for some vector (1, [[t.sub.1], ..., [t.sub.n-1]).sup.T] [member of] [R.sup.n]. The matrix [T.sub.n] satisfies [JT.sub.n]J= [T.sub.n] and is therefore centrosymmetric. We use I for the identity matrix and J for the exchange, or "flip" matrix with ones on its southwest-northeast diagonal and zeros everywhere else. We note that for any [lambda][member of]R, the matrix ([T.sub.n]-[lambda]I) is symmetric and centrossymmetric, whenever [T.sub.n] is also symmetric and centrossymmetric. In what follows, an important role is played by the so-called Yule-Walker equations. For an n x n symmetric Toeplitz matrix [T.sub.n], defined by (1, [t.sub.1], ..., [t.sub.n-1]), this system of linear equations is given by [T.sub.n][y.sup.n]=-t where t=[([t.sub.1], ..., [t.sub.n]).sup.T]. There exist several methods to solve these equations. Durbin's algorithm solves them by recursively computing the solutions to lower-dimensional systems, provided all principal submatrices are non-singular. This algorithm requires 2[n.sub.2]+O(n) flops.

3. THE (MODIFIED) NEWTON'S METHOD FOR THE CHARACTERISTIC POLYNOMIAL

The characteristic polynomial for RSPDTM [T.sub.n] is given by [p.sub.n]([lambda]):=det([T.sub.n] -[lambda]I). If Newton's method has been used to compute the roots of this polynomial, then the following lemma gives a convenient expression for the Newton step.

Lema1. The Newton step for the characteristic polynomial [p.sub.n]([lambda]) of an n x n matrix [T.sub.n] at [lambda] = [bar.[lambda]], where [bar.[lambda]] is not one of the eigenvalues of Tn, is given by:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

As we apply Gohberg-Semencul formulae (Gohberg&Semencul, 1972) for the inverse of a Toeplitz matrix we use the next definition. With the first row of [T.sub.n] given by (1, [t.sup.T]), we first define

Definition 1. Let q([lambda]) := -1+[lambda]+[t.sup.T] [(T.sub.n-1]-[lambda]I).sup.-1]t the secular function. With w= -[JT.sub.n-1]t, the Gohenberg-Semencul formulae for the inverse of [T.sub.n] is then given by:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (2)

Melman in (Melman, 2006) shows the following theorem:

Theorem1. The Newton step for the characteristic polynomial [p.sub.n]([lambda]) of a RSPDTM [T.sub.n] at [lambda] = [bar.[lambda]] is given by:

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

where q is as in Definition 1. and the first row of [T.sub.n] is given by (1,[t.sup.T]) and w = ([w.sub.1], ..., [w.sub.n-1]) = -J[([T.sub.n-1 - [bar.[lambda]I).sup.-1]t. For compactness of writing, we have set [w.sub.n]=1.

On this way, Melman (Melman, 2006) avoided the use of recursion for development of the first derivatives of function and minimized development of the first derivation of characteristic polynomial to O(n) flops. In this manner, there are assumptions for efficiency applying of the Newton method. We have idea to moreover apply Gohberg-Semencul formulae for development the second derivative of the characteristic polynomial. The second derivative of characteristic polynomial is important for providing of convergence, because one of convergence criteria sounds:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] 1, where [mu] is start parameter.

Coefficient a = [p.sub.n]" ([mu])/[p.sub.n] ([mu]) can be easy calculated, because it holds [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. It is obviously from [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. To calculate [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] we need to find some elements of matrix [([T.sub.n] - [mu]I).sup.-1]. Without loss of generality we will consider case vhen n is even. As matrix [T.sub.n] has specific structure, each element [c.sub.i,j] located out of the main and southwest-northeast diagonal of matrix [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] are repeated four times in the matrix and two times on these diagonals. On this way, during calculation these elements, it is needed only quarto of them, that results to cheaper algorithm. Required elements can be calculated by using following recursions:

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

For above proposed calculation we spent (n-2)n flops. As it holds [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], that additionally gives [n.sub.2]/2 flops. That means, for new step it is necessary 7[n.sub.2]/2+O(n) flops. Herein, it is important to point out that information about position of test parameter, i.e. how many eigenvalues lie behind its, we find using Durbin algorithm that is based on the Sylvester theorem. To calculate the second derivative for this iteration we use combination methods proposed in (Kostic & Cohodar, 2008) with iteration:

[mu] = [mu] + N([mu]) a/2N[([mu]).sup.3].

[FIGURE 1 OMITTED]

4. NUMERICAL RESULTS

To test the method we considered the following class of Toeplitz matrices:

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

where m is chosen such that the diagonal of [T.sub.n] is normalized to [t.sub.0]=1. [T.sub.[theta]] = ([t.sub.t,j]) = (cos([theta](i - j))) and [[eta].sub.k] and [[theta].sub.k] are uniformly distributed random in the interval [0,1] ( cf. Cybenko and Van Loan). Table 1 contains the average number of Durbin steps needed to determine in 100 test problem each of the dimension n=32,64,128,256,512 and 1024.

The initial value of 1.1 leads to the best results. Numerical simulation shows that eigenvalues from the middle spectrum can lie very closely to each other that additionally can slow down algorithm.

5. CONCLUSION AND FUTURE RESEARCH

In this paper we present the Newton method for characteristic polynomial of symmetric positive definite Toeplitz matrix which we determinate of eigenvalues from the middle spectrum. The convergence criterion is based on the first and second derivatives of characteristic polynomial. The paper presents how to develop the second derivative of its.

It would be very interested to approximate the even and odd polynomial of the positive definite Toeplitz matrices, but with much more using property of their symmetry.

6. REFERENCES

Gohberg, I.C. & Semencul, A. A. (1972). The inversion of finite Toeplitz matrices and their continual analogues. (Russian), Mat. Issued. Vol. 7., No. 2(24), pp. 201-223. MR0353038 (50:5524)

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

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

Melman, A. (2006). Computation of the Newton step for the even and odd characteristic polynomials of a symmetric positive definite Toeplitz matrix. Mathematics of computation. Vol. 75, No 254, pp. 817-832, S 025-5718(05)01796-5 Pisarenko, V. F. (1973). The retrieval of harmonics from a covariance function. Geophys. J. R.. astr. Soc. Vol. 33., pp. 347-366

Trench, W. F. (1989). Numerical solution of the eigenvalue problem for Hermitian Toeplitz matrices. SIAM J. Matrix Anal. Appl., 10(2): 135-146

Tab. 1. The average number of Durbin steps

 Ordinal number
dim of eigenvalue Method

32 17 8.8875
64 33 9.7925
128 65 10.0075
256 129 11.2325
512 257 12.6525
1024 513 13.8575