Concatenated Matrix SVD: Compression Bounds, Incremental Approximation, and Error-Constrained Clustering

Résumé Technique : SVD de Matrices Concatenées : Bornes de Compression, Approximation Incrémentale et Clustering sous Contrainte d'Erreur

Formulation du Problème

Le machine learning moderne, le traitement du signal et le calcul scientifique génèrent fréquemment de grandes collections de matrices $\mathcal{A} = \{A_i\}_{i=1}^N$ qui nécessitent un stockage et une manipulation sous des contraintes de mémoire strictes. Une approche standard pour compresser ces données est la décomposition en valeurs singulières (SVD) tronquée, qui fournit l'approximation de bas rang optimale dans la norme de Frobenius. Lorsqu'on dispose de plusieurs matrices, une extension naturelle consiste à les concaténer horizontalement en une seule matrice $M = [A_1, \dots, A_K]$ et à appliquer une SVD tronquée unique. Cette stratégie permet le partage de paramètres et une compression coordonnée, particulièrement lorsque les matrices présentent des espaces colonnes alignés ou superposés.

Cependant, un défi fondamental demeure : quels sous-ensembles de matrices peuvent être concaténés et compressés ensemble en toute sécurité tout en garantissant que l'erreur de reconstruction jointe reste en dessous d'une tolérance spécifiée par l'utilisateur ? Les approches existantes reposent sur un regroupement heuristique, des contraintes architecturales ou des hypothèses liées au domaine (par exemple, le regroupement des poids par couche dans les réseaux de neurones). Ces méthodes manquent de garanties fondées sur les principes concernant l'erreur d'approximation SVD résultante. La concaténation de matrices mal alignées peut augmenter considérablement le rang effectif, entraînant des erreurs de reconstruction nettement plus élevées que la compression de matrices de manière indépendante. Le problème central est de concevoir un cadre de clustering basé sur des critères de conscience de la compression, garantissant que l'erreur d'approximation SVD jointe prédite respecte des budgets d'erreur explicites sans nécessiter la formation explicite de la matrice concaténée complète.

Méthodologie

L'article introduit un cadre théorique pour le clustering conscient de la compression, basé sur de nouvelles bornes spectrales caractérisant l'évolution des valeurs singulières sous concaténation horizontale. La méthodologie procède à travers trois développements théoriques et algorithmiques principaux :

1. Bornes Spectrales pour les Matrices Concatenées

Les auteurs dérivent deux bornes inférieures distinctes sur les valeurs singulières d'une matrice concaténée $M = [A_1, \dots, A_K]$, qui produisent par la suite des bornes supérieures sur l'erreur de reconstruction SVD de rang $r$ optimale $E_r(M)$.

• Borne Supérieure Basée sur Weyl (Théorème 1) : En exploitant le théorème de monotonicité de Weyl pour les matrices hermitiennes, les auteurs établissent que les valeurs singulières de la matrice concaténnée sont bornées inférieurement par les valeurs singulières de n'importe quel bloc individuel. Cela conduit à une borne supérieure globale sur l'erreur de reconstruction :
  $$E_r^2(M) \leq \sum_{j=1}^K \|A_j\|_F^2 - \max_{1 \leq j \leq K} \sum_{i=1}^r \sigma_i^2(A_j)$$
  Cette borne est peu coûteuse en calcul, s'appuyant uniquement sur les normes de Frobenius et les principales valeurs singulières des blocs individuels. Cependant, elle est conservatrice, car elle repose sur un bloc « ancre » unique et ne parvient pas à capturer la structure partagée entre plusieurs blocs.

• Bornes Globales Basées sur le Résidu (Théorème 2 & Corollaire 1) : Pour obtenir des garanties plus serrées, les auteurs analysent les valeurs singulières des résidus incrémentaux. En définissant le résidu orthogonal $R_i = (I - Q_{i-1}Q_{i-1}^\top)A_i$ (où $Q_{i-1}$ engendre l'espace de portée des blocs précédents), ils montrent que les valeurs singulières de la matrice concaténée sont bornées inférieurement par les valeurs singulières des résidus concaténés $\tilde{R} = [R_1, \dots, R_K]$. Cela produit une borne d'erreur plus précise :
  $$E_r^2(M) \leq \sum_{i=1}^K \|A_i\|_F^2 - \sum_{j=1}^r \mu_j^2(\tilde{R})$$
  où $\mu_j$ sont les valeurs singulières de la matrice résiduelle. Cette borne capture l'« innovation » cumulative (nouvelles directions) contribuée par tous les blocs, fournissant un certificat prouvable pour la fusion des matrices.

2. Estimateur Approximatif Incrémental

Pour répondre aux enjeux de scalabilité, l'article propose un estimateur approximatif efficace basé sur la SVD tronquée incrémentale. Au lieu de calculer les résidus exacts ou de former la matrice concaténée complète, cette méthode maintient une base orthonormale pour le sous-espace singulier gauche dominant et une petite matrice de Gram pour suivre les valeurs singulières approximatives.

• L'estimateur met à jour le sous-espace et les valeurs singulières à mesure que de nouveaux blocs sont ajoutés, en tronquant la représentation au rang $r$ à chaque étape.
• L'erreur prédite est calculée comme un estimateur « plug-in » : $\tilde{E}_r(M) = (\sum \|A_i\|_F^2 - \sum_{j=1}^r \tilde{\sigma}_j^2)^{1/2}$.
• Bien que cette méthode ne fournisse pas de garanties déterministes de pire cas (car la troncature peut écarter des directions qui deviennent significatives ultérieurement), elle offre une efficacité computationnelle et une précision empirique substantielles.

3. Algorithmes de Clustering

S'appuyant sur ces bornes, les auteurs conçoivent trois algorithmes de clustering gloutons qui fusionnent les matrices uniquement lorsque l'erreur prédite reste en dessous d'un seuil $\varepsilon$ :

1. Clustering Max-Norm : Utilise la borne basée sur Weyl. C'est la méthode la plus rapide mais elle produit des clusters conservateurs, échouant souvent à fusionner des blocs qui pourraient être compressés ensemble.
2. Clustering Basé sur le Résidu : Utilise la borne basée sur le résidu. Il fournit des garanties de précision de reconstruction prouvables et des résultats plus serrés, mais impose des coûts de calcul plus élevés en raison de la nécessité de suivre les sous-espaces résiduels.
3. Clustering Incrémental Approximatif : Utilise l'estimateur plug-in. Il équilibre vitesse et qualité de compression, atteignant les taux de compression les plus élevés en pratique sans garanties formelles.

Principales Contributions

• Cadre Théorique : L'article établit le premier cadre théoriquement fondé pour le clustering de matrices sous des contraintes explicites de compression SVD, allant au-delà du regroupement heuristique.
• Nouvelles Bornes Spectrales : Il dérive de nouvelles bornes supérieures globales sur l'erreur de reconstruction SVD concaténée en utilisant la monotonicité de Weyl et l'analyse des résidus incrémentaux.
• Certificats de Fusion Sensibles à la Compression : Les auteurs définissent des conditions calculables (certificats de fusion) qui permettent des décisions de clustering glouton sans calculer explicitement les valeurs singulières de la matrice concaténée.
• Spectre Algorithmique : Trois algorithmes sont proposés, couvrant un compromis entre vitesse, précision prouvable et scalabilité, permettant un contrôle explicite de l'erreur de reconstruction.

Résultats Expérimentaux

Le cadre a été évalué sur quatre ensembles de données diversifiés : tenseurs de canaux MIMO Qualcomm, imagerie satellite BigEarthNet-S1, PDEBench (écoulements générés par PDE) et poids du modèle SmolVLM2.

• Compression vs Garanties :
  • Max-Norm : Considérablement la plus rapide mais a souvent échoué à réaliser une compression (ratio de compression $\approx 1$) en raison de bornes lâches, particulièrement sur des jeux de données comme PDEBench.
  • Basé sur le Résidu : A fourni des garanties d'erreur strictes et des résultats stables, mais était ordres de grandeur plus lent que l'approche max-norm.
  • Incrémental Approximatif : A atteint les taux de compression les plus élevés (par exemple, jusqu'à 45x sur PDEBench) tout en restant nettement plus rapide que les méthodes de résidus exactes.
• Conservatisme de l'Estimateur : Les diagnostics ont montré que les estimateurs max-norm et basés sur le résidu étaient strictement conservateurs (slack positif). L'estimateur approximatif a produit des estimations beaucoup plus serrées (slack proche de zéro) et, empiriquement, n'a pas sous-estimé l'erreur réelle dans les jeux de données testés.
• Impact Aval : Sur la tâche de prévision PDEBench, l'article a démontré qu'une faible erreur de reconstruction est corrélée à une forte performance en aval. Crucialement, une concaténation complète naïve (sans clustering) a conduit à une perte de performance catastrophique malgré une compression élevée, validant la nécessité de l'approche de clustering proposée.
• Baselines : Les méthodes de clustering classiques (k-means, HDBSCAN) n'ont pas pu fournir une erreur de reconstruction contrôlée, entraînant souvent des erreurs élevées et instables même avec des taux de compression élevés.

Signification et Revendications

L'article affirme établir la compression SVD consciente de la concaténation comme un fondement principalisé pour le clustering et la compression de grandes collections de matrices. En unifiant la théorie des perturbations spectrales, l'estimation incrémentale des valeurs singulières et le clustering piloté par la compression, ce travail fournit à la fois des garanties théoriques et des algorithmes pratiques.

Les auteurs soulignent que leur approche déplace le paradigme du regroupement heuristique vers un clustering contrôlé par l'erreur. Contrairement aux méthodes existantes qui reposent sur la proximité architecturale ou la similitude sémantique, les algorithmes proposés lient directement la formation des clusters à l'erreur d'approximation de bas rang prédite. Cela permet un contrôle de l'exactitude explicite et interprétable, garantissant que la fusion de matrices ne viole pas les contraintes de reconstruction.

Le travail est modeste quant à son étendue : il traite le rang cible comme un hyperparamètre fixe et opère dans un cadre hors ligne. Les auteurs reconnaissent que l'optimisation conjointe de la sélection du rang et du clustering, ainsi que les extensions aux contextes de flux (streaming) et aux normes alternatives (par exemple, la norme spectrale), restent des directions ouvertes pour la recherche future. De plus, bien que l'estimateur approximatif ait performé de manière satisfaisante empiriquement, l'article note son absence de garanties formelles de pire cas et le potentiel de sous-estimation dans certains cas pathologiques spécifiques, le positionnant comme une heuristique pratique qui complète les méthodes prouvables.