An Algebraic Approach to Non-Orthogonal General Joint Block Diagonalization

Yunfeng Cai, Chengyu Liu

Abstract

The Non-Orthogonal General Joint Block Diagonalization (NOGJBD) problem is a critical task in signal processing and data analysis, aiming to find a single nonsingular matrix $W$ that simultaneously transforms a set of real matrices into block-diagonal forms. Traditional iterative optimization methods for NOGJBD often suffer from local minima and high sensitivity to initialization. This paper presents a novel algebraic framework that reformulates the problem into solving a system of linear equations and a subsequent eigenvalue decomposition. We introduce two numerical methods—a fast greedy approach and a robust conservative strategy—and demonstrate their effectiveness through synthetic benchmarks and signal separation tasks.

Introduction

Joint Block Diagonalization (JBD) is a fundamental component in applications such as Independent Component Analysis (ICA) and tensor decompositions. While many existing algorithms assume the transformation is orthogonal or that the target matrices are symmetric, real-world data frequently requires a more flexible, non-orthogonal approach. The General JBD problem (GJBD) is particularly challenging because it does not impose symmetry constraints on the input matrices.

Historically, JBD has been treated as a non-convex optimization problem, where an objective function representing the "energy" of off-diagonal blocks is minimized. However, these methods are prone to numerical instability and can become trapped in local minima. This paper proposes an alternative algebraic perspective, shifting the focus from iterative optimization to the properties of linear operators.

The Algebraic Framework

The core of the proposed method lies in the observation that if a set of matrices $\mathcal{A} = \{A_i\}_{i=1}^m$ can be jointly block-diagonalized, there exists a matrix $Z$ that satisfies the system of linear equations:

$$A_i Z = Z^T A_i, \quad i=1, \dots, m$$

By solving this system, we can recover the underlying block structure of the matrix set. The workflow consists of three primary stages:

  1. Null Space Analysis: We define a linear operator $\mathcal{L}$ based on the system of equations. In the exact case, we find the null space of $\mathcal{L}$; in the presence of noise, we identify a "near-null space" using Singular Value Decomposition (SVD).
  2. Generic Matrix Construction: A "generic" matrix $Z$ is constructed as a random linear combination of the basis vectors of the identified null space.
  3. Eigenvalue Decomposition (EVD): An EVD is performed on $Z$. The resulting eigenvectors provide the basis for the diagonalizer $W$.

Proposed Algorithms

To implement this framework, we propose two specific algorithms:

  • geanogjbd-greedy: This method is designed for speed. It determines the block partition by identifying significant gaps between the real parts of the eigenvalues of $Z$.
  • geanogjbd-consv (Conservative): This is a more robust, iterative "divide and conquer" strategy. It recursively splits the problem into smaller sub-problems, ensuring greater stability in environments with high noise levels.

Experimental Evaluation

We evaluated the proposed methods using both synthetic data and a practical signal processing benchmark.

Synthetic Random Data

Matrices were generated using a mixing model $A_i = V^T D_i V$, where $V$ is a random mixing matrix and $D_i$ are block-diagonal. We tested the algorithms across a range of Signal-to-Noise Ratios (SNR). The geanogjbd-consv algorithm demonstrated superior robustness, significantly outperforming standard iterative methods like JBD-NCG and JBD-LM at low SNR levels (e.g., SNR=20). At higher SNRs (40 to 80), our algebraic methods achieved performance indices comparable to state-of-the-art optimization toolboxes like Tensorlab.

Convolutive Mixtures of Sources

We applied the framework to a classic signal processing problem involving the separation of three source signals from observed mixtures. The algebraic approach successfully recovered the source signals with higher correlation to the originals than traditional methods, particularly when significant noise was present.

Key Insights and Uniqueness

A major contribution of this work is the establishment of a necessary and sufficient condition for the uniqueness of the NOGJBD solution (up to permutation and scaling). Furthermore, we found that in noisy conditions, the imaginary parts of the eigenvalues of $Z$ remain negligible. This allows the clustering of eigenvalues based solely on their real parts to effectively reveal the hidden block structure.

Conclusion and Future Work

By transforming a hard non-convex optimization problem into a linear algebra problem, we provide a more stable and theoretically grounded approach to NOGJBD. While the current implementation faces a computational complexity of $O(n^6)$—limiting its use for matrices larger than $n=100$—this provides a clear path for future research. Subsequent work will focus on exploiting the sparse or Kronecker-product structure of the operator $\mathcal{L}$ to reduce complexity and extending the framework to rectangular matrix sets.

Summary updated

Abstract

The exact/approximate non-orthogonal general joint block diagonalization ({\sc nogjbd}) problem of a given real matrix set $\mathcal{A}=\{A_i\}_{i=1}^m$ is to find a nonsingular matrix $W\in\mathbb{R}^{n\times n}$ (diagonalizer) such that $W^T A_i W$ for $i=1,2,\dots, m$ are all exactly/approximately block diagonal matrices with the same diagonal block structure and with as many diagonal blocks as possible. In this paper, we show that a solution to the exact/approximate {\sc nogjbd} problem can be obtained by finding the exact/approximate solutions to the system of linear equations $A_iZ=Z^TA_i$ for $i=1,\dots, m$, followed by a block diagonalization of $Z$ via similarity transformation. A necessary and sufficient condition for the equivalence of the solutions to the exact {\sc nogjbd} problem is established. Two numerical methods are proposed to solve the {\sc nogjbd} problem, and numerical examples are presented to show the merits of the proposed methods.
BibTeX
@article{cai2017algebraic,
  author = {Yunfeng Cai and Chengyu Liu},
  title = {{An Algebraic Approach to Non-Orthogonal General Joint Block Diagonalization}},
  journal = {SIAM J. Matrix Anal. Appl.},
  year = {2017},
  doi = {10.1137/16m1080756},
}
Figure