Randomized Joint Diagonalization of Symmetric Matrices
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917596241068032 |
|---|---|
| author | He, Haoze Kressner, Daniel |
| author_facet | He, Haoze Kressner, Daniel |
| contents | Given a family of nearly commuting symmetric matrices, we consider the task of computing an orthogonal matrix that nearly diagonalizes every matrix in the family. In this paper, we propose and analyze randomized joint diagonalization (RJD) for performing this task. RJD applies a standard eigenvalue solver to random linear combinations of the matrices. Unlike existing optimization-based methods, RJD is simple to implement and leverages existing high-quality linear algebra software packages. Our main novel contribution is to prove robust recovery: Given a family that is $ε$-near to a commuting family, RJD jointly diagonalizes this family, with high probability, up to an error of norm O($ε$). We also discuss how the algorithm can be further improved by deflation techniques and demonstrate its state-of-the-art performance by numerical experiments with synthetic and real-world data. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2212_07248 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Randomized Joint Diagonalization of Symmetric Matrices He, Haoze Kressner, Daniel Numerical Analysis Given a family of nearly commuting symmetric matrices, we consider the task of computing an orthogonal matrix that nearly diagonalizes every matrix in the family. In this paper, we propose and analyze randomized joint diagonalization (RJD) for performing this task. RJD applies a standard eigenvalue solver to random linear combinations of the matrices. Unlike existing optimization-based methods, RJD is simple to implement and leverages existing high-quality linear algebra software packages. Our main novel contribution is to prove robust recovery: Given a family that is $ε$-near to a commuting family, RJD jointly diagonalizes this family, with high probability, up to an error of norm O($ε$). We also discuss how the algorithm can be further improved by deflation techniques and demonstrate its state-of-the-art performance by numerical experiments with synthetic and real-world data. |
| title | Randomized Joint Diagonalization of Symmetric Matrices |
| topic | Numerical Analysis |
| url | https://arxiv.org/abs/2212.07248 |