Randomized Joint Diagonalization of Symmetric Matrices

DOI10.1137/22M1541265MaRDI QIDQ6130646zbMATH OpenFDO

Authors Daniel Kressner

Publication date 3 April 2024

Published in SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2212.07248

zbMATH Keywords

approximate joint diagonalizationindependent component analysismatrix analysisrandomized numerical linear algebra

Mathematics Subject Classification ID

Orthogonal matrices (15B10) Random matrices (algebraic aspects) (15B52) Hermitian, skew-Hermitian, and related matrices (15B57) Orthogonalization in numerical linear algebra (65F25) Randomized algorithms (68W20)

Abstract: 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 $epsilon$-near to a commuting family, RJD jointly diagonalizes this family, with high probability, up to an error of norm O($epsilon$). No other existing method is known to enjoy such a universal robust recovery guarantee. 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.

Recommendations

• Joint approximate diagonalization of positive definite Hermitian matrices
• Newton Method for Joint Approximate Diagonalization of Positive Definite Hermitian Matrices
• A new Jacobi-like method for joint diagonalization of arbitrary non-defective matrices
• Some perturbation results for a normalized non-orthogonal joint diagonalization problem
• Solving the general joint block diagonalization problem via linearly independent eigenvectors of a matrix polynomial.

Cites work

• A fast algorithm for joint diagonalization with non-orthogonal transformations and its application to blind source separation
• A Link between the Canonical Decomposition in Multilinear Algebra and Simultaneous Matrix Diagonalization
• A new method of moments for latent variable models
• A Parallel Eigensolver for Dense Symmetric Matrices Based on Multiple Relatively Robust Representations
• A randomized multivariate matrix pencil method for superresolution microscopy
• A spectral algorithm for latent Dirichlet allocation
• Approximate joint diagonalization with Riemannian optimization on the general linear group
• Blind separation of instantaneous mixtures of nonstationary sources
• Diagonality measures of Hermitian positive-definite matrices with application to the approximate joint diagonalization problem
• Distance to normal elements in C^-algebras of real rank zero
• Estimating Extremal Eigenvalues and Condition Numbers of Matrices
• Globally convergent Jacobi-type algorithms for simultaneous orthogonal symmetric tensor diagonalization
• scientific article; zbMATH DE number 47363 (Why is no real title available?)
• scientific article; zbMATH DE number 1253975 (Why is no real title available?)
• scientific article; zbMATH DE number 1064704 (Why is no real title available?)
• scientific article; zbMATH DE number 6159604 (Why is no real title available?)
• Jacobi algorithm for the best low multilinear rank approximation of symmetric tensors
• Jacobi Angles for Simultaneous Diagonalization
• Joint approximate diagonalization of positive definite Hermitian matrices
• Making almost commuting matrices commute
• Nonorthogonal Joint Diagonalization by Combining Givens and Hyperbolic Rotations
• Numerical Methods for Simultaneous Diagonalization
• On a perturbation bound for invariant subspaces of matrices
• Quadratic optimization for simultaneous matrix diagonalization
• Riemannian Optimization and Approximate Joint Diagonalization for Blind Source Separation
• Tensor decompositions for learning latent variable models
• Understanding machine learning. From theory to algorithms
• Wilkinson's bus: weak condition numbers, with an application to singular polynomial eigenproblems

Cited in

(5)

• Randomized methods for computing joint eigenvalues, with applications to multiparameter eigenvalue problems and root finding
• A simple, randomized algorithm for diagonalizing normal matrices
• Parallel implementations of Riemannian conjugate gradient methods for joint approximate diagonalization
• Representations of the symmetric group are decomposable in polynomial time
• The eigenvalue decomposition of normal matrices by the skew-symmetric part

This page was built for publication: Randomized Joint Diagonalization of Symmetric Matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6130646)