Quadratic approximation of characteristic polynomial of symmetric positive definite Toeplitz matrix.

Kostic, Aleksandra ; Cohodar, Maida

1. INTRODUCTION

The problem of finding the smallest eigenvalue [[lambda].sub.1] of a real symmetric, positive definite Toeplitz matrix [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; Mackens & Voss, 1997, 2000; Melman, 2006).

In this paper we propose new modification of Newton's method for the computation of the roots of the characteristic polynomial of a real symmetric positive definite Toeplitz matrix. To compute the Newton step in (Mackens & Voss, 2000; Mastronardi & Boley, 1999), these methods use a recursion for the evaluation of the characteristic polynomial and its derivative which requires O([n.sup.2]) flops to solving the Yule-Walker equations. Melman in (Melman,2006) show that this recursion can be replaced by a shorter computation, involving the computation of the trace of an appropriate matrix, and, after solving the Yule-Walker equations, requiring only O(n) flops.

As it is pointed out, the paper presents new modified Newton method which is based on the Taylor expansion of the 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. In this way, we replace the characteristic polynomial with the polynomial of the second order from the Taylor series, which faster convergences than classical Newton method in enough small neighborhood of the smallest eigenvalue.

In Section 2 we present the basic properties of Toeplitz matrices and the notation we will use. In Section 3 we compute the new Newton's method and in Section 4 we compare the methods. In Section 5 we present 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 [(1, [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. 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 recursively computing the solutions to lower-dimensional systems, provided all principal submatrices are non-singular. This algorithm requires 2[n.sup.2] + O(n) flops.

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

The characteristic polynomial for the symmetric matrix [T.sub.n] is given by [p.sub.n]([lambda]):=det([T.sub.n] - [lambda]I). If Newtton's method were 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 [T.sub.n], 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.sup.n-1] - [lambda]I).sup.-1] t the secular function. With w= -J[T.sub.n-1]t, the Gohenberg-Semencul formula for the inverse of [T.sub.n] is then given by:

[T.sup.-1.sub.n] = -1/q(0)([M.sub.1][M.sup.T.sub.1] - [M.sup.T.sub.o][M.sub.0]), (2)

where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

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

Theorem1. The Newton step for the characteristic polynomial [p.sub.n]([lambda]) of an n x n symmetric positive definite Toeplitz matrix [T.sub.n] at [lambda] = [bar.[lambda]] < [[lambda].sub.1] is given by:

N([bar.[lambda]]) = q([bar.[lambda]]/[n.summation over (j=1)](2j - n)[w.sup.2.sub.j] (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, as well as the method with double Newton step. We have idea to moreover apply Gohberg-Semencul formulae for development the second derivative of the characteristic polynomial. Namely, we need to approximate our characteristic polynomial with the polynomial of the second order based on the Taylor series. Let p([lambda]) := [p.sub.n]([bar.[lambda]]) + [p'.sub.n]([bar.[lambda]])([lambda] - [bar.[lambda]]) + [p".sub.n]([bar.[lambda])/2! ([lambda] - [bar.[lambda]]) (4)

is approximation of characteristic polynomial [p.sub.n] whereby [bar.[lambda]] is not eigenvale of the matrix [T.sub.n]. So, we can find approximated value of the smallest eigenvalue using solution of the equation:

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

Coefficient a: = [p".sub.n]([bar.[lambda]])/2! [p.sub.n]([bar.[lambda]]) can be easy calculated, because it holds 2 x a = [(trace ([T.sup.-1.sub.n])).sup.2] - trace ([T.sup.-2.sub.n]). It is obviously from trace([T.sup.-1.sub.n]) = [n.summation over (i=1)] 1/[[lambda].sub.i] and trace([T.sup.-2.sub.n]) = [n.summation over (i=1)] 1/[[lambda].sup.2.sub.i], where [[lambda].sub.i], i=1,2, ..., n are all eigenvalues of the matrix [T.sub.n]. To calculate trace([T.sup.-2.sub.n]) = [n.summation over (i=1)] 1/[[lambda].sub.i] we need to find some elements of matrix [T.sup.-1.sub.n]. Without loss of generality we will consider case vhen n is even. As matrix [T.sub.n] has specific structure, each element [c.sub.ij] located out of the main and southwest-northeast diagonal of matrix [T.sup.-1.sub.n] = 1/q(0)[([c.sub.i,j]).sub.i,j=1,2, ..., n] 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:

[c.sub.i,i-k] = [c.sub.i+1,i-k+1] + [w.sub.i] x [w.sub.i-k] - [w.sub.n-i] x [w.sub.n-i+k], [c.sub.i,i-k-1] = [c.sub.i+1,i-k] + [w.sub.i] x [w.sub.i-k-1] - [w.sub.n-i] x [w.sub.n-i+k+1], (6)

for k=0,2, ..., n-4, i=n-1, ..., ((n+k)/2)+1.

For above proposed calculation we spent (n-2)n flops. As it holds trace([T.sup.-2.sub.n]) = 1/[q.sup.2](0) [n.summation over (i=1)][n.summation over (j=1)][c.sup.2.sub.i,j] = that additionally gives [n.sup.2]/2 flops. That means, for new step it is necessary 7[n.sup.2]/2+O(n) flops. Although method is expensive, it gives good results as we are enough closely to eigenvalue of matrix. If it would be combined with Newton method with double step it gives improving that numerical results show.

4. NUMERICAL RESULTS

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

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

where m is chosen such that the diagonal of [T.sub.n] 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] (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.

5. CONCLUSION AND FUTURE RESEARCH

In this paper we present modified Newton method for characteristic polynomial of symmetric positive definite Toeplitz matrix which approximates characteristic polynomial with second order polynomial from Taylor series. On this way, we improved previously developed algorithm what we also have expected, because we used second derivative of characteristic polynomial. In other words, approximation of characteristic polynomial with second order polynomial, as well as development of second derivative of characteristic polynomial are the new results and the main contribution of the paper.

It would be very interested to approximate the even and odd polynomial of the second order on above pointed out manner but with much more using property of symmetry of the Toeplitz matrices. Also, results would be applied on methods based on secular function and its Pade approximation.

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)

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 Eienwerte einer symmetrischen Toeplitz Matrix, Shaker Verlag, ISBN 3-8322-3235-4, Aachen

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

Table 1. The average number of Durbin steps
Method with double Newton step is denoted with dnm in Table 1.

dim New method Method dnm

 32 5.47 5.74
 64 5.89 6.3
128 5.59 6
256 5.99 6.59
512 6.5725 7.03
1024 6.8425 7.57