A Randomized Algorithm for Simultaneously Diagonalizing Symmetric Matrices by Congruence

ABSTRACT

A family of symmetric matrices is simultaneously diagonalizable by congruence (SDC), also called nonorthogonal joint diagonalization, if there is an invertible matrix such that every is diagonal. In this work, a novel randomized SDC (RSDC) algorithm is proposed that reduces SDC to a generalized eigenvalue problem by considering two (random) linear combinations of the family. We establish exact recovery: RSDC achieves diagonalization with probability 1 if the family is exactly SDC. For regular SDC families, we derive a perturbation bound showing that any congruence diagonalizer of the perturbed random pair nearly diagonalizes the entire family. Under a positive definiteness assumption, which often holds in applications, this yields a high‐probability robust‐recovery guarantee: if the input family is ‐close to SDC, then RSDC diagonalizes it up to an error of norm . In this case, we also establish a bound on the condition number of the transformation matrix. For practical use, we suggest combining RSDC with an optimization algorithm. The performance of the resulting method is verified for synthetic data, image separation, and EEG analysis tasks. It turns out that our newly developed method outperforms existing optimization‐based methods in terms of efficiency while achieving a comparable level of accuracy.