Fifty Three Matrix Factorizations: A systematic approach

Alan Edelman, Sungwoo JeongSIAM J. Matrix Anal. Appl 2021 · OpenReview

TL;DR

This paper presents a systematic catalog of 53 matrix factorizations, many of which are novel, derived from the generalized Cartan decomposition of Lie theory. This comprehensive approach unifies and extends existing factorizations like the SVD, offering a deeper understanding of matrix structure with potential for new algorithmic computations and applications.

What Problem Does This Paper Address?

Matrix factorizations, such as the Singular Value Decomposition (SVD), are fundamental tools in linear algebra with widespread applications. While many factorizations exist, driven by specific demands or generalizations, there's been a lack of a unifying framework to understand their relationships. This paper aims to address this by systematically deriving and cataloging a large number of matrix factorizations, inspired by the generalized Cartan decomposition from Lie theory, to provide a comprehensive and structured view of this area.

Methods

The core methodology of this paper is the application of the generalized Cartan decomposition, and its related KAK and K₁AK₂ decompositions, to classical Lie groups. The authors systematically explore various classical Lie groups (GL, U, Sp, O) and their associated involutions to derive matrix factorizations. They present a structured approach, organized by the type of matrices being factorized (orthogonal, unitary, invertible, symplectic, etc.), and provide explicit theorems for each of the 53 identified factorizations. The paper also discusses "factorization folding," a technique to generalize the link between SVD and eigendecomposition, and explores how these factorizations can be related to symmetric and indefinite eigenproblems.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • A Unified Framework: The paper demonstrates that many seemingly disparate matrix factorizations can be systematically derived from the principles of Lie theory, specifically the generalized Cartan decomposition. This provides a powerful unifying perspective.
  • The Power of Lie Theory: The authors argue that Lie theory, often considered abstract, has been "lurking hidden" in the foundations of matrix computations, and this work makes that connection explicit.
  • Novel Factorizations: The catalog of 53 factorizations includes many that are believed to be new, opening avenues for further research and application.
  • Historical Context: The paper provides a valuable historical perspective on the development of key factorizations like the SVD, CS decomposition, and KAK decomposition, highlighting how important ideas can be overlooked or underappreciated.
  • Factorization Folding: The concept of "factorization folding" is introduced as a way to generalize the relationship between SVD and eigendecomposition, and to connect different types of factorizations.

Key Results

The paper's primary result is the systematic derivation and cataloging of 53 matrix factorizations, presented in Table 1. These factorizations arise from the generalized Cartan decomposition applied to various classical Lie groups. The paper provides explicit theorems for each factorization, detailing the structure of the factors involved (e.g., unitary, orthogonal, symplectic matrices) and their relationships. For instance, it reinterprets the SVD as a KAK decomposition of the general linear group and introduces new factorizations for orthogonal, unitary, invertible, symplectic, and indefinite matrices.

Limitations and Future Work

The authors acknowledge that their list of 53 factorizations is not exhaustive and that "factorization folding" could be explored in greater depth in future work. They also note that the choice of maximal abelian subalgebras in some decompositions can be non-unique, although the resulting factorizations are isomorphic. The paper suggests that these newly identified factorizations can lead to further work on algorithmic computations and applications.

Summary updated

Abstract

The success of matrix factorizations such as the singular value decomposition (SVD) has motivated the search for even more factorizations. We catalog 53 matrix factorizations, most of which we believe to be new. Our systematic approach, inspired by the generalized Cartan decomposition of Lie theory, also encompasses known factorizations such as the SVD, the symmetric eigendecomposition, the CS decomposition, the hyperbolic SVD, structured SVDs, the Takagi factorization, and others thereby covering familiar matrix factorizations as well as ones that were waiting to be discovered. We suggest that Lie theory has one way or another been lurking hidden in the foundations of the very successful field of matrix computations with applications routinely used in so many areas of computation. In this paper, we investigate consequences of the Cartan decomposition and the little known generalized Cartan decomposition for matrix factorizations. We believe that these factorizations once properly identified can lead to further work on algorithmic computations and applications.
BibTeX
@article{edelman2021fifty,
  author = {Alan Edelman and Sungwoo Jeong},
  title = {{Fifty Three Matrix Factorizations: A systematic approach}},
  journal = {SIAM J. Matrix Anal. Appl.},
  year = {2021},
  url = {https://openreview.net/forum?id=MBQdikmPty},
}

Loading related content...

Figure