On the reducibility of finite Toeplitz matrices - applications in speech analysis and pattern recognition
On the reducibility of finite Toeplitz matrices - applications in speech analysis and pattern recognition
复制标题
有限托普利茨矩阵的可约性 - 在语音分析和模式识别中的应用
DOI：
10.1016/0165-1684(82)90057-3
复制
发表时间：
1982
影响因子：
4.4
通讯作者：
S. Morgera
中科院分区：
文献类型：
--
作者：
S. Morgera
利用中心对称矩阵的结果，证明了Toeplitz矩阵的行列式(特征方程)可以分解成两(三)个乘积，这取决于矩阵的阶数N是否是偶数(奇数)。这种因式分解将计算行列式的乘法复杂性降低了约75%。此外，通过引用被称为循环的Toeplitz矩阵的特殊类，证明了与“偶”和“奇”调和特征向量相关联的特征值在行列式因子中规则地交错。对于一般的Toeplitz矩阵，这些特征向量由Griander和Szegö的正交多项式产生；而对于循环式，这些特征向量与离散傅立叶变换(DFT)相关。所提出的显式因式分解为评估Toeplitz矩阵行列式计算的计算复杂性提供了一种很好的方法。例如，可以很容易地证明，对于N偶数，Toeplitz三对角矩阵的行列式可以精确地通过12N次加法和12N次乘法来计算；而且，对于N偶数，通过只计算M阶马尔可夫矩阵的行列式，可以有效地计算一阶马尔可夫矩阵的行列式，其中M是N的最大奇因数。这些结果本身是非常有趣的；然而，重要的一点是，因子分解和与之相关的正交性变换似乎在Toeplitz矩阵产生的许多应用领域中返回了使用直接方法的计算吸引力。为了说明这一点，详细讨论了语音分析和三维模式识别中的例子；由于因式分解的结果，对于这些问题的某些方面现在似乎可以有丰富的解释。
Using results obtained for centrosymmetric matrices, it is shown that the determinant (characteristic equation) of a Toeplitz matrix can be factored into two (three) products, depending on whether the order N of the matrix is even (odd). This factorization reduces the multiplicative complexity of calculating the determinant by about 75%. Furthermore, by appealing to the specialized class of Toeplitz matrices known as circulants, it is shown that the eigenvalues associated with the ‘even’and ‘odd’harmonic eigenvectors interlace regularly in the determinant factors. For general Toeplitz matrices, these eigenvectors arise from the orthogonal polynomials of Grenander and Szegö; whereas, for circulants, the eigenvectors are associated with the Discrete Fourier Transform (DFT). The explicit factorization developed is found to provide an excellent method for assessing the computational complexity of determinant calculation for Toeplitz matrices. For example, it is easily shown that the determinant of a Toeplitz tridiagonal matrix may be computed in exactly 1 2 N additions and 1 2 N multiplications, for N even; also, the determinant of a first order Markovian matrix may be efficiently computed by computing just the determinant of a Markovian matrix of order M, where M is the largest odd divisor of N, for N even. These results in themselves are quite interesting; however, the important point is that the factorization and an orthogonality transformation associated with it seem to return computational attractiveness to the use of a direct approach in the many application areas in which Toeplitz matrices arise. To illustrate this, examples in speech analysis and three-dimensional pattern recognition are discussed in some detail; a rich interpretation now appears to be possible for certain aspects of these problems, due to the factorization results.