Partial Trace Regression and Low-Rank Kraus Decomposition

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

Introduction

Standard linear regression models are designed to map vector-valued inputs to scalar outputs. While trace regression extends this to matrix-to-scalar mappings, many modern machine learning tasks—such as Brain-Computer Interfaces (BCI) and 3D computer vision—require mapping a matrix to another matrix. A critical challenge in these domains is that the data often consists of covariance or kernel matrices, which must remain Positive Semidefinite (PSD). Standard multivariate regression techniques that flatten matrices into vectors fail to preserve this structural geometry, leading to invalid outputs.

This paper introduces Partial Trace Regression (PTR), a mathematically rigorous framework that leverages concepts from quantum information theory to provide structurally aware, PSD-preserving linear predictors.

The Partial Trace Regression Framework

The core of the proposed model is the "partial trace" operator, a generalization of the standard matrix trace. While a standard trace reduces a matrix to a single scalar, the partial trace $\text{tr}_m$ operates on block matrices, summing the traces of individual sub-blocks to produce a smaller matrix output.

The partial trace operator $\text{tr}_m$ maps a block matrix to a smaller matrix by summing the traces of its sub-blocks.

To ensure the model is learnable and inherently preserves the PSD property, the authors parameterize the regression as a "completely positive map" using the Kraus representation:

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

In this formulation, $X$ is the input matrix, and $A_j$ are the learned Kraus operators (weight matrices). The hyperparameter $r$, known as the "Kraus rank," controls the model's complexity. This decomposition is particularly elegant because the quadratic form $A X A^\top$ mathematically guarantees a PSD output if the input $X$ is PSD, eliminating the need for expensive projection steps during training.

Empirical Performance and Rank Recovery

The Kraus rank $r$ acts as a natural low-rank regularizer. The authors demonstrate that the model can effectively recover the underlying structure of a mapping from limited data. As shown in simulated experiments, the regression error drops precipitously once the model's Kraus rank matches the true rank of the data-generating process.

Regression error as a function of Kraus rank $r$. The error significantly drops when $r$ reaches the true rank of the underlying mapping, provided sufficient samples are available.

In comparative tests, PTR significantly outperformed baseline methods. On simulated PSD-to-PSD regression tasks, PTR achieved a Mean Squared Error (MSE) of 0.001, whereas standard trace regression (0.028) and multivariate regression (0.058) lagged behind. Even complex architectures like Tucker Neural Networks (0.595) struggled to match PTR's efficiency and accuracy.

Real-World Applications

Domain Adaptation in BCI

In Brain-Computer Interface tasks, EEG data is often represented as covariance matrices. PTR was used to map these matrices across different user sessions, providing an inductive model for domain adaptation. It performed competitively with Optimal Transport methods while maintaining the ability to process out-of-sample data without recomputation.

Multi-View Matrix Completion

The authors also framed PSD matrix completion as a partial trace regression problem. On the UCI Multiple Features Digits dataset, a "stacked" (depth-2) PTR model was able to reconstruct kernel matrices even when 90% of the data was missing. Downstream classification accuracy remained nearly identical to baselines with access to the full dataset, proving the model's robustness.

Conclusion

By bridging quantum mechanics and classical machine learning, Partial Trace Regression offers a powerful tool for handling PSD-constrained matrix data. The Kraus decomposition provides a built-in architectural constraint that is both computationally efficient and statistically sound. Future research into "Deep Kraus Networks"—stacking multiple PTR layers with non-linearities—promises to further extend the capabilities of this framework for complex, high-dimensional matrix tasks.

Summary updated

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