Partial Trace Regression and Low-Rank Kraus Decomposition

Hachem Kadri, Stéphane Ayache, Riikka Huusari, Alain Rakotomamonjy, Liva Ralaivola

Introduction

In classical linear regression, models map vectors to scalars. "Trace regression" takes this a step further by mapping matrices to scalars. However, many modern machine learning problems require mapping a matrix to another matrix.

For example, in Brain-Computer Interfaces (BCI), researchers often represent mental states as covariance matrices. When a subject moves from one session to another, these matrices shift (a phenomenon known as domain shift). To correct this, we need a way to transform the "source" covariance matrix into a "target" covariance matrix.

This matrix-to-matrix mapping introduces two major challenges:

  1. Parameter Explosion: A naive linear mapping between matrices involves a massive number of parameters, inevitably leading to overfitting.
  2. Structural Constraints: In many applications, the input and output matrices are Positive Semidefinite (PSD). Standard regression techniques do not guarantee that the predicted output will remain PSD, which can break downstream algorithms.

To address these issues, researchers have introduced Partial Trace Regression (PTR), a novel framework that extends standard regression to map matrix-valued inputs directly to matrix-valued outputs while preserving their structural properties.

Methods: Partial Trace Regression

The authors propose using the partial trace operator—a concept central to quantum mechanics—to define the mapping between matrices.

Visual representation of the partial trace operation on a block matrix.

The Low-Rank Kraus Decomposition

To make the model learnable, robust, and capable of preserving PSD properties, the researchers restrict the search space to Completely Positive (CP) maps. According to the Kraus Representation Theorem from quantum information theory, any such map can be written as:

$$\Phi(X) = \sum_{j=1}^r A_j X A_j^T$$

Where $A_j$ are called Kraus operators. This formulation provides several key advantages:

  • PSD-Preservation by Design: Because the Kraus representation is used, the model cannot produce a non-PSD output if the input is PSD. This "hard-coded" constraint is much more reliable than adding a soft penalty term during training.
  • Regularization via Rank: Instead of using standard norm-based regularization, the authors use the "Kraus rank" ($r$) to control model complexity. A low $r$ means fewer parameters and better generalization to unseen data.
Error rates across different Kraus Ranks, demonstrating regularization via rank.
  • Optimization: The model is implemented using modern autodifferentiation frameworks (like TensorFlow/Keras), allowing the non-convex optimization problem to be solved efficiently with Stochastic Gradient Descent (SGD).
  • Theoretical Bounds: The paper provides a formal proof for the "pseudo-dimension" of this function class, offering a theoretical guarantee on how well the model generalizes based on the chosen Kraus rank.

Key Insights and Results

The authors evaluated PTR on simulated data, BCI domain adaptation tasks, and multi-view kernel matrix completion (using the Multiple Features Digits Dataset).

  • Matrix Completion as Regression: One of the paper's most elegant insights is showing that completing a block-structured PSD matrix is mathematically equivalent to a partial trace regression problem. On block-structured completion tasks, PTR achieved a Mean Squared Error (MSE) of 0.572, drastically outperforming standard trace regression (2.996) and Tensor Train Neural Networks (3.942).
  • Efficiency and Recovery: In simulations, PTR accurately recovered the true underlying model even with limited data, significantly outperforming standard multivariate regression and tensor-based methods.
  • BCI Performance: On real-world EEG data, using PTR for "Out-of-Sample Adaptation" improved classification accuracy across multiple subjects. It nearly matched the performance of "Full Adaptation" methods, which unrealistically require seeing all test data beforehand.

Limitations and Future Work

While highly effective, the framework has a few limitations:

  • Linearity: The core theory focuses on linear mappings. While the authors experimented with "stacking" layers (similar to a deep neural network) to introduce non-linearity, the theoretical generalization bounds for these multi-layer architectures are not yet established.
  • Hyperparameter Tuning: Performance depends heavily on choosing the right block sizes and Kraus rank ($r$). In unsupervised settings, tuning these parameters can be challenging.
  • Scalability: Although more efficient than naive approaches, the computational cost still grows with the size of the matrices and the Kraus rank, potentially limiting its use for extremely high-dimensional data without further optimization.

Summary updated

Abstract

The trace regression model, a direct extension of the well-studied linear regression model, allows one to map matrices to real-valued outputs. We here introduce an even more general model, namely t...
BibTeX
@inproceedings{kadri2020partial,
  author = {Hachem Kadri and Stéphane Ayache and Riikka Huusari and Alain Rakotomamonjy and Liva Ralaivola},
  title = {{Partial Trace Regression and Low-Rank Kraus Decomposition}},
  booktitle = {International Conference on Machine Learning},
  year = {2020},
  url = {https://openreview.net/forum?id=RJdwrgqXLU},
}
Figure