Metrics for Multivariate Dictionaries

Sylvain Chevallier, Quentin Barthélemy, Jamal Atif

Abstract

Overcomplete representations and dictionary learning algorithms kept attracting a growing interest in the machine learning community. This paper addresses the emerging problem of comparing multivariate overcomplete representations. Despite a recurrent need to rely on a distance for learning or assessing multivariate overcomplete representations, no metrics in their underlying spaces have yet been proposed. Henceforth we propose to study overcomplete representations from the perspective of frame theory and matrix manifolds. We consider distances between multivariate dictionaries as distances between their spans which reveal to be elements of a Grassmannian manifold. We introduce Wasserstein-like set-metrics defined on Grassmannian spaces and study their properties both theoretically and numerically. Indeed a deep experimental study based on tailored synthetic datasets and real EEG signals for Brain-Computer Interfaces (BCI) have been conducted. In particular, the introduced metrics have been embedded in clustering algorithm and applied to BCI Competition IV-2a for dataset quality assessment. Besides, a principled connection is made between three close but still disjoint research fields, namely, Grassmannian packing, dictionary learning and compressed sensing.

Introduction

In sparse representation and dictionary learning, the goal is to find a set of "atoms"—basic building blocks—that can efficiently represent complex data. While numerous algorithms exist to learn these dictionaries, a rigorous method for comparing them has been notably absent. This challenge is particularly acute for multivariate data, such as multi-channel EEG or color images.

Traditional evaluation methods often rely on "detection rates," which count how many atoms in a learned dictionary are "close enough" to a ground truth. However, this approach is binary and non-smooth. It fails to account for the fact that two dictionaries might represent the same information even if their raw coordinates differ—for instance, if they are rotated versions of each other or if their atoms are linear combinations of one another. There is a clear need for a metric that captures the underlying information content rather than just coordinate-wise similarity.

Methodology: The Geometry of Information

The proposed framework bridges Grassmannian packing, dictionary learning, and compressed sensing. The core innovation lies in how atoms and dictionaries are represented:

  1. Atoms as Subspaces: Rather than treating a multivariate atom as a simple matrix, it is viewed as a subspace. The collection of all such subspaces forms a Grassmannian manifold. This shift allows the use of established distances on these manifolds, such as Chordal or Geodesic distances, which are naturally invariant to linear transformations and rotations.
Figure 1: Visualization of the distance between two subspaces W and U on a Grassmannian manifold, characterized by principal angles like theta_2.
  1. Wasserstein Set-Metrics: To compare entire dictionaries (sets of atoms), the authors introduce Wasserstein-like set-metrics (Earth Mover's Distance). By treating a dictionary as a distribution of points on the Grassmannian manifold, the resulting "frame distance" becomes a smooth pseudo-metric. This metric is invariant to linear combinations, providing a more "honest" measure of the information content within a dictionary.

Experimental Validation

The metrics were validated using both synthetic and real-world datasets:

  • Synthetic Datasets: Randomly generated multivariate atoms were used to test recovery under various conditions. The Wasserstein-Chordal metric demonstrated superior convergence tracking, providing a stable, smooth curve of the learning process, whereas traditional detection rates often remained at zero until an abrupt spike.
  • BCI Competition IV-2a: This dataset contains EEG signals from subjects performing motor imagery tasks. The metrics allowed for clustering subjects based on their learned dictionaries, revealing distinct profiles for "BCI-inefficient" subjects. Furthermore, the metrics quantitatively confirmed "session drift"—the significant change in a subject's "brain dictionary" between different days—explaining the necessity for daily BCI recalibration.

Results and Discussion

The proposed metrics showed remarkable neurobiological alignment. When clustering dictionaries learned from different motor imagery tasks (e.g., hand vs. tongue), the resulting clusters reflected the physical organization of the motor cortex. Additionally, the metrics proved robust to noise, remaining effective even at low signal-to-noise ratios (down to 10 dB).

While computationally more intensive than simple correlation checks, the Wasserstein distances offer a much clearer picture of algorithmic convergence. Future work may involve using these metrics as regularization terms in dictionary learning to enforce specific geometric properties, such as "packing," ensuring that atoms are optimally spread out across the manifold.

Summary updated

Abstract

Overcomplete representations and dictionary learning algorithms kept attracting a growing interest in the machine learning community. This paper addresses the emerging problem of comparing multivariate overcomplete representations. Despite a recurrent need to rely on a distance for learning or assessing multivariate overcomplete representations, no metrics in their underlying spaces have yet been proposed. Henceforth we propose to study overcomplete representations from the perspective of frame theory and matrix manifolds. We consider distances between multivariate dictionaries as distances between their spans which reveal to be elements of a Grassmannian manifold. We introduce Wasserstein-like set-metrics defined on Grassmannian spaces and study their properties both theoretically and numerically. Indeed a deep experimental study based on tailored synthetic datasetsand real EEG signals for Brain-Computer Interfaces (BCI) have been conducted. In particular, the introduced metrics have been embedded in clustering algorithm and applied to BCI Competition IV-2a for dataset quality assessment. Besides, a principled connection is made between three close but still disjoint research fields, namely, Grassmannian packing, dictionary learning and compressed sensing.
BibTeX
@inproceedings{chevallier2014metrics,
  author = {Sylvain Chevallier and Quentin Barthélemy and Jamal Atif},
  title = {{Metrics for Multivariate Dictionaries}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2014},
  doi = {10.1109/icassp.2014.6854993},
}
Figure