Expressivity of congruence-based architectures for DNNs on positive-definite matrices

Technical Summary: Expressivity of Congruence-Based Architectures for DNNs on Positive-Definite Matrices

Problem Formulation
Symmetric positive-definite (SPD) matrices are ubiquitous in scientific and engineering applications, encoding second-order information such as signal correlations and covariances. While the set of SPD matrices naturally forms a Riemannian manifold, enabling the use of Riemannian machine learning techniques, the expressivity of Deep Neural Networks (DNNs) designed for this data remains poorly understood. Specifically, the paper investigates the SPDNet architecture, which relies on "congruence-like" layers (BiMap layers) where an input matrix $X$ is transformed as $X \mapsto WXW^\top$. A critical constraint in SPDNet is the enforcement of semi-orthogonality on the weight matrices $W$ (i.e., $WW^\top = I_p$) to ensure optimization stability. The core problem addressed is whether this constraint, combined with specific activation functions (like ReEig), limits the representational power (expressivity) of deep architectures, potentially rendering them equivalent to shallow networks.

Methodology
The authors analyze a general class of architectures defined by the signal propagation equation:
$$X_\ell = g(W_\ell X_{\ell-1} W_\ell^\top)$$
where $g$ is a matrix activation function (e.g., ReEig) acting on eigenvalues, and $W_\ell$ are weight matrices. The study proceeds in two main theoretical phases:

1. Orthogonal Weights ($W \in O(n)$): The authors prove that if all weight matrices are square and orthogonal, the depth of the network does not increase expressivity. They utilize the property that matrix functions are invariant under congruence with orthogonal matrices.
2. Semi-Orthogonal Weights ($W \in St(n, p)$): The authors extend the analysis to rectangular semi-orthogonal matrices. They leverage Poincaré's Separation Theorem, which dictates that the eigenvalues of $W^\top A W$ are bounded by the eigenvalues of $A$. This spectral containment implies that the range of eigenvalues cannot expand beyond the initial spectrum of the input.

The paper further examines the interaction between these feature extractors and final classifiers. It evaluates the compatibility of congruence-based feature extraction with various Riemannian distances (Affine-Invariant, Log-Euclidean, Stein, Bures-Wasserstein, and Euclidean) by testing their invariance properties under congruence transformations.

Key Contributions and Results

• Collapse of Deep Architectures: The paper demonstrates that for certain activation functions, imposing (semi-)orthogonality constraints on weight matrices causes deep networks to collapse into one-hidden-layer equivalents, regardless of the network depth.
  • Orthogonal Case: If $W$ is orthogonal, the network is equivalent to a single layer with an activation function composed $L$ times. If the scalar activation function $\sigma$ is idempotent (e.g., ReLU, hard tanh), the composition $g^{(L)}$ simplifies to $g$, meaning the deep network is strictly equivalent to a single hidden layer.
  • Semi-Orthogonal Case: If $W$ is semi-orthogonal and the activation function $\sigma$ acts as the identity on the interval containing the input spectrum (or maps the spectrum into such an interval), the network again collapses to a single congruence transformation. This is a direct consequence of Poincaré's Separation Theorem, which prevents the expansion of spectral diversity necessary for deep hierarchical feature learning in this specific setting.
• Loss of Spectral Diversity: The lack of expressivity is attributed to a "loss of spectral diversity." Semi-orthogonal congruence transformations constrain the eigenvalues of the output to lie within the eigenvalue interval of the input. Consequently, for activation functions that rely on spectral expansion or modification, the depth provides no additional discriminative power.
• Classifier Incompatibility: The study reveals that several celebrated distances between SPD matrices (Affine-Invariant, Stein, and Euclidean) are invariant under congruence with orthogonal or invertible matrices.
  • If a classifier relies on these invariant distances (e.g., Minimum Riemannian Distance to Mean), and the feature extractor uses congruence layers with orthogonal weights, the distance between any two data points remains unchanged throughout the network.
  • This implies that such classifiers cannot separate data from different classes if the feature extraction relies solely on these invariant transformations, as the relative geometry of the data is preserved rather than transformed to enhance separability.

Significance and Claims
The paper claims that the standard design choices in SPDNet—specifically the semi-orthogonality constraint on BiMap layers—fundamentally limit the architecture's expressivity for certain activation functions. The authors argue that this constraint leads to a degeneracy where deep networks offer no advantage over shallow ones, a phenomenon driven by the spectral constraints of Poincaré's Separation Theorem.

Furthermore, the work highlights a critical mismatch between congruence-based feature extraction and classifiers relying on invariant metrics. If the feature extractor preserves the spectral and geometric structure of the data (due to orthogonal constraints), classifiers based on invariant distances fail to benefit from the feature extraction process. The paper concludes that future designs for SPD DNNs must reconsider these constraints, potentially exploring new activation functions or relaxing orthogonality requirements to restore the expressivity of deep architectures.