A randomized algorithm for simultaneously diagonalizing symmetric matrices by congruence
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915264317095936 |
|---|---|
| author | He, Haoze Kressner, Daniel |
| author_facet | He, Haoze Kressner, Daniel |
| contents | A family of symmetric matrices $A_1,\ldots, A_d$ is SDC (simultaneous diagonalization by congruence, also called non-orthogonal joint diagonalization) if there is an invertible matrix $X$ such that every $X^T A_k X$ 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. Under a mild regularity assumption, robust recovery is also established: Given a family that is $ε$-close to SDC then RSDC diagonalizes, with high probability, the family up to an error of norm $\mathcal{O}(ε)$. Under a positive definiteness assumption, which often holds in applications, stronger results are established, including a bound on the condition number of the transformation matrix. For practical use, we suggest to combine 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_16557 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A randomized algorithm for simultaneously diagonalizing symmetric matrices by congruence He, Haoze Kressner, Daniel Numerical Analysis 65F15, 65F30, 68W20, 15A22, 15A27 A family of symmetric matrices $A_1,\ldots, A_d$ is SDC (simultaneous diagonalization by congruence, also called non-orthogonal joint diagonalization) if there is an invertible matrix $X$ such that every $X^T A_k X$ 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. Under a mild regularity assumption, robust recovery is also established: Given a family that is $ε$-close to SDC then RSDC diagonalizes, with high probability, the family up to an error of norm $\mathcal{O}(ε)$. Under a positive definiteness assumption, which often holds in applications, stronger results are established, including a bound on the condition number of the transformation matrix. For practical use, we suggest to combine 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. |
| title | A randomized algorithm for simultaneously diagonalizing symmetric matrices by congruence |
| topic | Numerical Analysis 65F15, 65F30, 68W20, 15A22, 15A27 |
| url | https://arxiv.org/abs/2402.16557 |