Solving General Joint Block Diagonalization Problem via Linearly Independent Eigenvectors of a Matrix Polynomial

Yunfeng Cai, Guanghui Cheng, Decai Shi

TL;DR

This paper introduces a novel algebraic approach to solve the General Joint Block Diagonalization (GJBD) problem by leveraging the eigenvectors of a matrix polynomial. The proposed three-stage algorithm, called PEAR (Partial Eigenvector approach with Refinement), provides a computationally efficient $O(n^3)$ solution that works for both exact and approximate cases, outperforming traditional optimization-based methods in speed and stability.

What Problem Does This Paper Address?

In fields like signal processing and data analysis, researchers often encounter sets of matrices that share a hidden structure. The goal of Joint Block Diagonalization (JBD) is to find a single transformation matrix (a "diagonalizer") that turns all matrices in a set into a block-diagonal form simultaneously.

The "General" version (GJBD) is particularly challenging because, unlike standard JBD, we don't know the number or the sizes of the diagonal blocks beforehand. This is a critical problem in Blind Source Separation (BSS), where one tries to recover independent groups of signals from observed mixtures without knowing the mixing process or the internal dependencies of the signal groups.

Existing methods usually fall into two camps:

  1. Optimization-based: These can get stuck in local minima and often require a good initial guess.
  2. Algebraic: These are more robust but often computationally expensive (some requiring $O(n^6)$ operations) or limited to specific matrix types (like Hermitian matrices).

Methods

The authors propose a shift in perspective: instead of treating the matrices as a collection, they combine them into a matrix polynomial $P(\lambda) = \sum_{i=0}^p \lambda^i A_i$.

Their algorithm, PEAR (Partial Eigenvector approach with Refinement), consists of three main stages:

  1. Eigenproblem Solving Stage: They compute $n$ linearly independent eigenvectors of the matrix polynomial. This effectively captures the shared structure of the entire matrix set in a single step.
  2. Block Structure Revealing Stage: To find how these eigenvectors group into blocks, the authors use a clever graph-theoretic approach. They construct a graph where vertices represent eigenvectors and edges represent their "connectedness" across the matrix set. By analyzing the Graph Laplacian and using spectral clustering (k-means), they determine the optimal block partition and the necessary permutation matrix.
  3. Refinement Stage: Since real-world data is noisy, the initial algebraic solution might be "low quality." They use an iterative refinement process to minimize the off-block-diagonal energy, significantly improving the final diagonalizer.

Datasets

The paper evaluates the PEAR algorithm using:

  • Synthetic Random Data: Matrices generated via a mixing model $A_i = V^H D_i V$, where $V$ is a complex mixing matrix and $D_i$ are block-diagonal. Noise is added to the off-diagonal parts, and performance is measured across various Signal-to-Noise Ratios (SNR).
  • Convolutive Mixtures: A specific benchmark case (Example 4.2 from prior literature) involving the separation of source signals to test the algorithm's real-world applicability in signal processing.

Key Insights and Ideas

  • The Polynomial Connection: The most significant "aha" moment is proving that the diagonalizer for the GJBD problem is composed of the eigenvectors of the associated matrix polynomial. This transforms a complex joint optimization problem into a well-understood eigenvalue problem.
  • Weak Assumptions: The theory only requires that the geometric multiplicity of the eigenvalues equals one—a much "weaker" and more common condition than requiring all eigenvalues to be simple.
  • Graph-Based Partitioning: Using the Graph Laplacian to find the block structure is a robust way to handle the "permutation" problem (deciding which eigenvector belongs to which block) without prior knowledge of block sizes.
  • Efficiency: By reducing the problem to an $O(n^3)$ eigenvalue computation, the method scales much better than previous $O(n^6)$ algebraic approaches.

Key Results

  • Robustness to Noise: In numerical tests, PEAR achieved a 100% success rate in identifying the correct block structure when the SNR was 60dB or higher.
  • Superior Speed: Compared to the SCMC (a state-of-the-art algebraic method), PEAR's CPU time increases much more slowly as the matrix size grows. For large matrices, PEAR is orders of magnitude faster.
  • Refinement Matters: The authors showed that while the first two stages provide a good "sub-optimal" solution, the Stage 3 refinement is crucial for matching the accuracy of heavy-duty optimization methods like JBD-LM and JBD-NCG.

Limitations and Future Work

  • Low SNR Failure: At very low SNRs (below 40dB), the block structure in Stage 2 becomes "fuzzy," and the algorithm may fail to find the correct partition.
  • Real vs. Complex: While the paper introduces "Stage 2.5" to find real diagonalizers, it relies on the assumption that a real solution exists and is equivalent to the complex one, which isn't always true.
  • Tensor Extensions: The authors suggest that this matrix polynomial approach could be extended to solve the Block Term Decomposition (BTD) of third-order tensors, particularly for non-square or non-congruent cases, which remains an open and exciting research direction.

Summary updated

Abstract

In this paper, we consider the exact/approximate general joint block diagonalization (GJBD) problem of a matrix set $\{A_i\}_{i=0}^p$ ($p\ge 1$), where a nonsingular matrix $W$ (often referred to as diagonalizer) needs to be found such that the matrices $W^{H}A_iW$'s are all exactly/approximately block diagonal matrices with as many diagonal blocks as possible. We show that the diagonalizer of the exact GJBD problem can be given by $W=[x_1, x_2, \dots, x_n]Π$, where $Π$ is a permutation matrix, $x_i$'s are eigenvectors of the matrix polynomial $P(λ)=\sum_{i=0}^pλ^i A_i$, satisfying that $[x_1, x_2, \dots, x_n]$ is nonsingular, and the geometric multiplicity of each $λ_i$ corresponding with $x_i$ equals one. And the equivalence of all solutions to the exact GJBD problem is established. Moreover, theoretical proof is given to show why the approximate GJBD problem can be solved similarly to the exact GJBD problem. Based on the theoretical results, a three-stage method is proposed and numerical results show the merits of the method.
BibTeX
@misc{cai2017solving,
  author = {Yunfeng Cai and Guanghui Cheng and Decai Shi},
  title = {{Solving General Joint Block Diagonalization Problem via Linearly Independent Eigenvectors of a Matrix Polynomial}},
  year = {2017},
  eprint = {1704.05642},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1704.05642},
}
Figure