A simple, randomized algorithm for diagonalizing normal matrices

A matrix \(A \in {\mathbb {C}}^{n\times n}\) is called normal if \(AA^* = A^* A\), where \(A^*\) denotes the Hermitian transpose of A. Equivalently, the Hermitian and skew-Hermitian parts of A commute:It is a basic linear algebra fact that A is normal if and only if it can be diagonalized by a unitary matrix U, that is, \(U^* A U\) is diagonal.

Our recent work [12] on diagonalizing commuting matrices suggests a simple method for performing the diagonalization of a general normal matrix A: Draw two independent random numbers \(\mu _H, \mu _S \in {\mathbb {R}}\) from the standard normal distribution \(\mathcal N(0,1)\) and compute a unitary matrix U that diagonalizes the Hermitian matrix \(\mu _H H + \mu _S \textrm{i} S\). This results in the following algorithm:

Bild vergrößern

As we will explain in Sect. 2, RandDiag succeeds with probability one in exact arithmetic and remains fairly robust in the presence of errors introduced due to, e.g., roundoff. The main computational cost is in line 3, which directly benefits from decades of research and development on Hermitian eigenvalue solvers [4, 11, 18] and software, such as LAPACK [2]. This makes RandDiag very simple to implement in scientific computing software environments. For example, these are the Matlab and Python implementations of RandDiag:

Bild vergrößern

Bild vergrößern

Compared to the Hermitian case, the case of a general normal matrix A is much less developed. In particular, we are not aware of a single publicly available implementation of an eigenvalue solver tailored to (complex) normal matrices, despite the fact that the development of such algorithms is a classical topic in numerical analysis. Already in 1959, Goldstine and Horwitz [10] proposed and analyzed a Jacobi-like method that annihilates the off-diagonal part of A by alternatingly applying Givens rotations. Ruhe [16] established local quadratic convergence of this method when applying Givens rotations in cyclic order and developed later on, in [17], a modified version for finding the normal matrix that is nearest (in Frobenius norm) to a given matrix. Since then, research on Jacobi methods for normal matrices has fallen nearly dormant, with the notable exception of [5]. However, two closely related problems have continued to attract interest: (1) Several algorithms have been developed for the more general task of simultaneously diagonalizing (nearly) commuting Hermitian matrices, including Jacobi-like methods [6, 7], optimization-based methods [21, 22], a “do-one-then-do-the-other” (DODO) approach [20], as well as randomized methods; see [12] and the references therein. By applying them to the commuting Hermitian matrices \(H, \textrm{i}S\), any of these algorithms can be used to diagonalize a normal matrix \(A = H + S\). Very recently [14], the DODO approach was adapted to block diagonalize a real normal matrix with a real orthogonal matrix. (2) When A is unitary, its Hessenberg form can be described by \(\mathcal O(n)\) parameters, the so called Schur parameters, which is the basis of efficient algorithms [1, 3] for diagonalizing A. Unitary eigenvalue problems play an important role in mathematical physics; a recent application to modelling thermal conductivity can be found in [13]. The unitary variant of the QR algorithm described in [3] has been implemented in the eiscor Fortran 90 package.¹

RandDiag is not only very simple but it is also fast, as demonstrated by our numerical experiments in Sect. 3. Experience [8] has shown that significant efforts are needed to make Jacobi-like methods, like the one by Goldstine and Horwitz, competitive. Even for the special case of a unitary matrix A, already the initial reduction to Hessenberg form required by the unitary QR algorithm can be more costly than RandDiag. Note, however, that not all applications may require this reduction; see [9] for an example.

We start our analysis of RandDiag by showing that it almost surely returns the correct result in the absence of error.

The proof of Theorem 1 reveals why randomness is needed in RandDiag. Suppose that, instead of choosing \(\mu _H,\mu _S\) randomly, we hard-coded a choice \(\mu _H = \alpha \), \(\mu _S = \beta \) for arbitrary fixed \(\alpha , \beta \in \mathbb R\) in RandDiag. Then RandDiag would fail for the matrixwith some unitary matrix \(U_0 \not = I\). In this case, \(\mu _H H + \mu _S \mathrm i S = 0\) and \(U=I\) would be a viable (and likely) output of RandDiag. But, clearly, \(U = I\) does not diagonalize A.

When working in finite-precision arithmetic, the assumption of Theorem 1, that A is exactly normal, is not reasonable, unless A has a particularly simple structure, like Hermitian or diagonal. Already representing the entries of a, say, unitary matrix as floating point numbers introduces an error (on the order of the unit round-off u) that destroys normality. The Hermitian eigenvalue solver utilized in line 3 of RandDiag introduces additional error. If a backward stable method is used in line 3, one can conclude that RandDiag is executed for a slightly perturbed matrix \(A+E\), with \(\Vert E\Vert _F = \mathcal O( u \Vert A\Vert _F)\). However, it is unlikely that E preserves normality; the best one can reasonably hope for in that situation is that the transformation returned by RandDiag diagonalizes A up to an off-diagonal error proportional to \(\Vert E\Vert _F\). In the following, we indeed establish such a robustness property by utilizing results on randomized joint diagonalization from [12]. Note that \({{\,\textrm{offdiag}\,}}(\cdot )\) refers to the off-diagonal part of a matrix, obtained by setting its diagonal entries to zero.

The result of Corollary 3 guarantees, with high probability, an off-diagonal error proportional to the input error, if one allows for a magnification of the error by a factor that grows polynomially with n. Note that Corollary 3 also implies a backward error result because \(\tilde{U}\) diagonalizes the normal matrix \(\tilde{A} - \tilde{U}{{\,\textrm{offdiag}\,}}(\tilde{U}^*\tilde{A}\tilde{U})\tilde{U}^*\). In turn, this allows one to apply perturbation results, such as the Hoffmann-Wielandt theorem [19, Thm. IV.3.1], to draw conclusions on, e.g., the quality of the approximate eigenvalues obtained from the diagonal of \(\tilde{U}^*\tilde{A} \tilde{U}\).

Note that, both, Theorem 2 and Corollay 3 make the (simplifying) assumption that the random variables involved are not affected by perturbations.

In this section, we present a few numerical experiments to indicate the efficiency of RandDiag. With no (efficient) implementation of the Jacobi-like methods mentioned in Sect. 1 being available, the main competitor to RandDiag appears to be the (non-symmetric) QR algorithm [11] to compute the unitary matrix that transforms A into Schur form. Thanks to the backward stability of the QR algorithm, such an approach enjoys a strong robustness property in the sense of Corollary 3.

All experiments were carried out on a Dell XPS 13 2-In-1 with an Intel Core i7-1165G7 CPU and 16GB of RAM. We have implemented² RandDiag in Python 3.8, calling LAPACK routines via Scipy for computing spectral and Schur decompositions. All experiments have been carried out in double precision and all execution times/errors are averaged over 100 runs with fixed input matrices. For the computed matrix \(\tilde{U}\), we report the off-diagonal error \(\Vert {{\,\textrm{offdiag}\,}}(\tilde{U}^*A \tilde{U})\Vert _F\).