Exploiting symmetry in characteristic polynomial of RSPDTM.

Kostic, Aleksandra ; Velic, Melisa ; Mehuljic, Midhat 等

1. INTRODUCTION

The problem of finding the smallest eigenvalue Xj 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 and Cohodar 2008) have solved this problem coming up to the computation of the second derivative characteristic polynomial to 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, 2009a) has determined eigenvalue from the middle of the spectrum by applying characteristical polynomial. In this note we speed up method that is given above by using symmetry properties. Specified structure of the Toeplitz matrix provides relatively simple and cheaper calculating the second derivatives of even and odd characteristic polynomial in sense of flop's numbers. The basic properties of Toeplitz matrices and used notation are presented in Section 2. In Section 3 we present Newton's method for even and odd characteristic polynomial and in Section 4 we give algorithm. 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 [(l,[t.sub.1], ..., [t.sub.n-1]).sup.T] [member of] [R.sup.n]. The matrix [T.sub.n] satisfies J[T.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. We say that an eigenvector x is symmetric and corresponding eigenvalue [lambda] is even if x = Jx, and x is called skew-symmetric and X is odd if x=-Jx. Canton and Butler (Canton & Butler 1976) show the following theorem:

Theoreml. Let [T.sub.n] [member of] [R.sup. (n,n)] a RSPDTM of order n. There exists an orthonormal basis for [R.sup.n], composed of [??] even and [??] odd eigenvectors, where [??] denotes the integral part of a.

The symmetry class of the principal eigenvector is known in advance only for a small class of Toeplitz matrices. For general Toeplitz matrices [T.sub.n] the symmetry class is detected by the

algorithm at negligible cost.

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 (l,[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.l], ..., [t.sub.n]).sup.T]. There exist several methods to solve these equations. Durbin's algorithm solves them by recursively computing the solutions to lowerdimensional systems, provided all principal sub matrices are non-singular. This algorithm requires 2[n.sup.2]+O(n) flops. There are too: 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.

3. EXPLOITING SYMMETRY

The characteristic polynomial for RSPDTM [T.sub.n] is given by [p.sub.n]([lambda]):=det([T.sub.n] - [lambda]I). Let n be even. We denote by [[lambda].sup.e.sub.i], i = 1,2, ..., [pi]/2, and [[lambda].sup.0.sub.i], = 1, ..., [pi]/2 the even and odd eigenvalues of the matrix [T.sub.n] respectively. Then the characteristic polynomial [p.sub.n] of [T.sub.n] can be factorized into

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] denote

even and odd characteristic polynomial of [T.sub.n].

As we apply Gohberg-Semencul formulae (Gohberg&Semencul, 1972) for the inverse of a Toeplitz matrix we use the next definition.

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

[T.sup.-1.sub.n] = -(Vq(0))([M.sub.l][M.sup.T.sub.l] - [M.sup.T.sub.0][M.sub.0]), (1)

where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Melman in (Melman, 2006) shows following theorems: Theorem2. The Newton step for the even and odd characteristic polynomials [p.sup.e.sub.n]([lambda]) and [p.sup.0.sub.n] ([lambda]) of an n x n symmetric positive definite Toeplitz matrix [T.sub.n] at [lambda] = [bar.[lambda]] < [[lambda].sub.1] are given by:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3)

where q is as in Definition 1. and the first row of T is given

by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. For compactness of writing, we have set [w.sub.0] = 0 and [w.sub.n] = 1.

On this way, Melman (Melman, 2006) has avoided the use of recursion for development of the first derivatives of even and odd characteristic polynomial and has minimized costs of first derivative computing. 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 even and odd characteristic polynomial. The second derivative of characteristic polynomial and even and odd characteristic polynomials are important for providing of convergence, because one of convergence criteria is:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where ft is start parameter.

It is important to point out that information about position of test parameter, i.e. how many eigenvalues lie behind it, we find using Durbin algorithm and Sylvester theorem. Before we can compute coefficient b for the even characteristic polynomial and c for the odd characteristic polynomial, we need a following result. Lemmal. For a non-singular symmetric Toeplitz matrix [T.sub.n]

given with

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The following holds

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

(Kostic, 2009b) gives

Theore[m.sup.3]. Coefficients [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] at [lambda] = [bar.[lambda]], where [bar.[lambda]] is not one of the eigenvalues of [t.sub.n], are given

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4)

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

is the inverse matrix of the matrix [t.sub.n] - [bar.[lambda]]I and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5)

New method is based on use of method presented in (Kostic, 2009), but this time on even or odd characteristic polynomial, depending of eigenvalue we search, i.e. is it even or odd. Before we use new method it is necessary to determine is eigenvalue even or odd.

4. ALGORITHAMS

We briefly sketch algorithms. We take initial value |io=1.1 because it is shown in practice as the best initial value for determination of X from the middle of the spectrum. Let the variable t monitor whether X is even or odd or the type of [[lambda].sub.i] is not yet known:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

UNTIL [tau]=0 use method from (kostic, 2009a) for characteristical polynomial

if [tau]=1 use method from (kostic, 2009a) for even characteristical polynomial until convergence else use method from (kostic, 2009a) for odd characteristical polynomial.

5. CONCLUSION

In this note we have used properties of symmetry to improve method presented in (Kostic, 2009a). We gave algorithm which describes this improvement and we applied convergence criteria for Newton's method for even and odd characteristic polynomial. It is necessary to make numerical experiments with goal of comparing this algorithm with method described in (Kostic 2009a) and verify numerical stability of this method. In further research the goal is to improve this method by exploiting the symmetry properties of eigenvectors.

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, ISBN 978-3-901509-68-1,ISSN 1726-9679, pp 8999

Kostic (2009)a. 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 17269679, pp 192

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

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