New secular equation of RSPDT matrix and its rational approximation.

Kostic, Aleksandra ; Velic, Melisa ; Hadziabdic, Vahidin 等

1. INTRODUCTION

The problem of finding the smallest eigenvalue [[lambda].sub.l.sup. (n)] of a real symmetric, positive definite Toeplitz matrix (RSPDT) [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, N & Boley, D.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).

The paper is organized as follows. In Section 2 we present the basic properties of Toeplitz matrices and the notation we will use. In Section 3 we present the new method which is based on new secular equation and its approximation. In Section 4 we present conclusion and further research.

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. For simplicity's sake, our notation will not explicitly indicate the dimensions of the matrices I and J.

We note that for any [lambda] [member of] R, the matrix ([T.sub.n]-[lambda]1) is symmetric and centrossymmetric, whenever [T.sub.n] is. 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.n-1]), this system of linear equations is given by

[T.sub.n][y.sup. (n)] = [-t.sup. (n)] where [t.sup. (n)] = [([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 sub matrices are non-singular. This algorithm requires 2[n.sup.2]+0(n) flops.

3. NEW METHOD

In this section we discuss the new method.

Let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

be RSPDT matrix. We denote by [t.sub.j] [member of] [R.sup. (j,j)] its j-th principal sub matrix, and we assume that its diagonal is normalized by [t.sub.0] = 1. If [[lambda].sup. (j).sub.1] [less than or equal to] [[lambda].sup. (j).sub.2] [less than or equal to] ... [less than or equal to] [[lambda].sup. (j).sub.1] are the eigenvalues of [t.sub.j] then the interlacing property

[[lambda].sup. (k).sub.j-1] [less than or equal to] [[lambda].sup. (k- 1).sub.j-1] [less than or equal to] [[lambda].sup. (k).sub.j], [less than or equal to] 2 [less than or equal to] j [less than or equal to] k [less than or equal to] n, holds.

In the determinant is defined the characteristic polynomial

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2)

of matrix [T.sub.n] where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We denote [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

By matrix multiplication it is easy to get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3)

From last equation and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4)

we get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5)

For above proposed calculation we spent 6(n-3) flops. In equation (2) by using block elimination matrix B is eliminated. This way we get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (6)

where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (7)

We get following recursion

Xn [lambda] = [X.sub.n-2] ([lambda])det (A - [B.sup.T]([T.sub.n-2] - [lambda]l-1] B)

and we define new secular equation:

det (A - [B.sup.T]([T.sub.n - 2 - [lambda]l)-1 B) = 0

From modular decomposition of matrix we [T.sub.n-2] - [lambda]I we

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (8)

and its rational approximation

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (9)

where a, b, c, d and e are determined such that:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

By making first derivation of odd equations respectively, we get even equations.

4. CONCLUSION

We have presented new secular equation of RSPDT matrix [T.sub.n] and theoretically constructed its rational approximation. Our goal is to improve already existing algorithms which are based on secular equation (Mackens & Voss 1997) and (Kostic & Voss, 2002). With new algorithm we try to overcome the situation when minimal eigenvalues of matrix [T.sub.n] and [T.sub.n]-1 are too close to each other. In this note, suggested approximation is convenient because coefficients a, b, c, d and e are easily computed and their computing does not require large number of flops. Through numerical experiments, which will be goal of future research, we will compare behaviour of new and old secular equation, as well as their rational approximations. By doing so, we will consider algorithm which has smaller number of flops and which is numerically more stable, to be the better one. In further research it is necessary to practically confirm suggested algorithm, compare it with previous algorithm and use symmetry properties of eigenvector.

5. 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. 17

Kostic A. (2004) Verfahren zur Bestimmung einiger extremaler Eienwerte 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 192

Mackens, W. & Voss, H. (1998). A projection method for computing the minimum eigenvalue of a symmetric positive definite Toeplitz matrix. Lin.Alg.Appl. 275276: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