A critical review of Mises method applied to the Toeplitz matrix.

Kostic, Aleksandra

Abstract: In this note we critically examine the application of Mises method to find the largest eigenvalue [[lambda].sub.n] of a real symmetric positive definite Toeplitz matrix (RSPDTM). The Mises method is considered a simple method because it is based on matrix multiplication. Special properties of the Toeplitz matrix enable us to multiply it with the symmetrical vector with only [n.sup.2] flops. However practical results are already not satisfactory in terms of number of steps and when matrices have small dimension n which is explained with linear convergence of the method.

Key words: eigenvalue problem, Toeplitz matrix, mises method

1. INTRODUCTION

The problem of finding the smallest eigenvalue [[lambda].sub.1] of a real synunetric, 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. The computation of the minimum eigenvalue of [T.sub.n] was studied in, e. g. (Cybenko & Van Loan, 1986; Kostic, 2004; Kostic & Cohodar, 2008; Mackens & Voss, 1997, 1998, 2000; Melman, 2006; Mastronardi & Boley, 1999). Cybenko and Van Loan (Cybenko & Van Loan, 1986) presented an algorithm, which is a combination of bisection and Newton's method for the secular equation. This approach was improved considerably in (Mackens & Voss, 1997) and (Kostic & Voss, 2002) by replacing Newton's method by a more appropriate root finding methods for the secular equation. Taking advantage of the fact that the spectrum of a symmetric Toeplitz matrix can be divided into odd and even parts the methods based on the secular equation were accelerated in (Voss, 1999).

Kostic (Kostic, 2004) has determined first five zeros of characteristic polynomial and 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's method for determination of arbitrary eigenvalue in the ease of characteristic polynomial. Kostic and Cohodar (Kostic & Cohodar, 2008) have solved this problem coming up to the computation of the second derivative characteristic polynomial by using additionally 0.75 iterations. Melman in (Melman, 2006) has also recommended method for cheap determination of first derivation of characteristic polynomial. 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.

Kostic (Kostic, 2009) has determined eigenvalue from the middle of the spectnma by applying characteristic polynomial.

However, all mentioned algorithms are based on Yule-Walker equations and Durbin's algorithm. For an n x n symmetric Toeplitz matrix [T.sub.n] defined by (1, [t.sub.1],[t.sub.2], ..., [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] and is named Yule-Walker system. 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 sub matrices are non-singular. This algorithm requires 2[n.sup.2]+O(n) flops. In addition, here are: Split-Durbin algorithm, Split Levinson algorithm, Even-Odd algorithm, Even-Odd Split Levinson algorithm and superfast methods. Split-Durbin algorithm requires 3[n.sup.2]/2+O(n) flops.

The question is whether it is possible to develop a good method for calculating some of the eigenvalues by using the special structure of Toeplitz matrices and not find themselves using the Yule-Walker system and Durbin's algorithm.

In Section 2 we introduce the basic concepts and notation. In Section 3 we deliver the basics of the Mises Method. In Section 4 we critically analyze the method and its application to RSPDT matrix. In Section 5 we bring the 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-j,n+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 J[T.sub.n]J=[T.sub.n]. We use I for the identity matrix and J:= [([delta]i,n+1-i).sub.i,j=1,...,n] for the exchange, or "flip" matrix.

3. MISES METHOD

Mises Method is one of the simplest methods for determining the largest eigenvalue. Method is described with following algorithm in easiest possible manner:

ALGORITHM

For m=0,1, ... until convergence to

[v.sup.m+1] = A[u.sub.m]

[k.sub.m+1] = [e.sup.(1)'] x [v.sub.m+1]

[u.sub.m+1] = [v.sub.m+1]/[k.sub.m+1]

End

In this algorithm matrix A has format nxn and matrices um and vm+1 have format nx1 which means that they are column matrices. Matrix e(1) is matrix with nx1 dimension which contains number one as its first element. We have taken the symbol " for notation of the transposed matrix. In this manner we have insured that km+1 is real number.

Convergence is linear with a convergence factor

q := max [absolute value of [[lambda].sub.1]/[[lambda].sub.n]], i = 1,2, ..., n -1 (1)

where [[lambda].sub.n] is the biggest eigenvalue and [[lambda].sub.1] is the smallest eigenvalue of the RSPDTM [T.sub.n]. For initial vector we take column matrix x=ones (n,1), which has number one for all its components.

4. MISES METHOD FOR TOEPLITZ MATRICES

Even though we have briefly given all known methods for determination of spectrum, all of those methods are based on Durbin's algorithm. Here, we try to present method in which we will not use Durbin's algorithm. Since RSPDTM [T.sub.n] has a special structure, costs of multiplication with the symmetrical column matrix x can be reduced. Let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2)

be RSPDT matrix, and let n be even number, which means that n = 2k, k [member of] N. Let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3)

be symmetrical vector. Than,

[T.sub.n] b = C (4)

where C is also symmetrical vector. Symmetry of the vector C is consequence of the matrix multiplication of matrix [T.sub.n] and vector b, where [T.sub.n] has Teoplitz structure and b has its symmetry properties.

In case of a square matrix, product of matrix with dimensions nxn and vector with dimensions nx1 gives matrix which has nx1 dimension with an expenditure of 2[n.sup.2] flops. Given the symmetry and centosymmetry of the Toeplitz matrix, here this expenditure costs [n.sup.2] flops. Since the Mieses method is exclusively based on matrix multiplication the illusion is created that despite the linear convergence of the method it can be applied. But with the application of the CVL class of matrices, that is, the following class of Toeplitz matrices (5), especially for dimension n=32 we get very bad results. CVL class is defined with

[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[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] ( cf. Cybenko and Van Loan).

5. CONCLUSION

Although one might expect that Mieses method because of its simplicity and due to special Toeplitz matrix structure, allows finding largest eigenvalue of the Toeplitz matrix with satisfactory number of flops, a practice completely denies this. This means that the use of Durbin's algorithm in case of Toeplitz matrix is justified and desirable.

This method should be avoided when it comes to Teoplitz matrices, because numerical experiments show that for finding biggest eigenvalue of RSPDTM necessary number of flops is equal to number of flops which is equal to 15,2 steps in case when Durbin's algorithm is applied. This fact says that calculating eigenvalues in this manner is not rational because the costs are very big. For comparison, for finding eigenvalue from the middle of the spectrum only 8,8 Durbin's steps are necessary. Extreme eigenvalues, the biggest one and the smallest one, should be found with smaller number of flops than eigenvalues from the middle of the spectrum.

6. REFERENCES

Cybenko, G. & Van Loan, C.F. (1986). Computing the minimum eigenvalue of a symmetric positive definite Toeplitz matrix, SIAM d. Sci. Star. 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. (2004) Verfahren zur Bestimmung einiger extremaler Eienwerte einer symmetrischen Toeplitz Matrix, Shaker Verlag, ISBN 3-8322-3235-4, Aachen

Kostic (2009) Determination of eigenvalues from middle spectrum of positive definite toeplitz matrix by newton method for characteristic polynomial Proceedings of 20th International DAAAM Symposium, ISBN 978-3-901509-70-4, ISSN 1726-9679, pp 192

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

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. MR1694690

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

Voss, H. (1999) Symmetric schemes for computing the minimum eigenvalue of a symmetric Toeplitz matrix. Lin.Alg.Appl.387:359-371