Absorbing Diagonal Algorithm: An Eigensolver of O(n2.584963 log 1/ɛ) Complexity at Accuracy ɛ.

Eigenvalue decomposition is widely used in dimensionality reduction for knowledge engineering, in particular principal component analysis and other similar spectral methods. Traditional eigenvalue decomposition algorithms for decomposing a matrix of size n × n are usually of complexity O(n3), due to a bottleneck in using Householder/Givens transforms to convert a general matrix to a tri-diagonal one. It is proposed in this article a new algorithm that takes only O(n2.584963 log 1/ɛ) computational complexity to achieve accuracy ɛ of eigenvalue decomposition for any ɛ > 0 . The basic idea of our algorithm is to convert a matrix into a diagonal form in multi-scale divide and conquer scheme, and the conversion is to iteratively and recursively apply two phases of operations called diagonal attractions and diagonal absorptions respectively. In a diagonal attraction, it attracts the off-diagonal entries to make the entries nearer to the diagonal larger in magnitude than those farther away from the diagonal. In a diagonal absorption, it absorbs the near-to-diagonal nonzero entries into the diagonal. In such a scheme, no Householder or Givens transforms are involved. Moreover, diagonal attractions and diagonal absorptions can be implemented with fast matrix multiplications. The scheme’s divide and conquer pattern also allows our algorithm to be easily mapped to modern computer hardware. Our algorithm also complements well the family of randomized eigenvalue/SVD algorithms using sampling techinques, which are of complexity O(nα polylog (1/ɛ)) with small α but very large overheads in the polylog. Their strength in the small exponent α of n in complexity was easily cancelled by the exploding overheads in the polylog. Now, with their low-accuracy estimate refined by our algorithm for high accuracy, their strength can be boosted significantly. [ABSTRACT FROM AUTHOR]