# Une analyse par matrices aléatoires du clustering en ligne : comprendre l'impact des limitations en mémoire

Hugo Lebeau, Romain Couillet, Florent Chatelain

## ► To cite this version:

Hugo Lebeau, Romain Couillet, Florent Chatelain. Une analyse par matrices aléatoires du clustering en ligne : comprendre l'impact des limitations en mémoire. GRETSI 2022 - XXVIIIème Colloque Francophone de Traitement du Signal et des Images, Sep 2022, Nancy, France. pp.1-4. hal-03756033

HAL Id: hal-03756033

https://hal.science/hal-03756033v1

Submitted on 22 Aug 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Une analyse par matrices aléatoires du clustering en ligne : comprendre l'impact des limitations en mémoire

Hugo LEBEAU<fnref n="1" />, Romain COUILLET<fnref n="1" />, Florent CHATELAIN<fnref n="2" />

¹Université Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, 38000 Grenoble, France

²Université Grenoble Alpes, CNRS, Grenoble INP, GIPSA-lab, 38000 Grenoble, France

hugo.lebeau@univ-grenoble-alpes.fr, romain.couillet@univ-grenoble-alpes.fr, florent chatelain@grenoble-inp.fr

**Résumé** – Cet article présente une analyse par matrices aléatoires du clustering sur des flux de données. En supposant que, du fait de limitations mémoire, l'on a accès qu'à un petit nombre de données, la matrice de Gram ne peut être calculée que partiellement. Dans un contexte où les données sont de grande dimension, on étudie sa distribution spectrale limite et ses valeurs et vecteurs propres isolés. Puis, on précise comment ces résultats permettent de réaliser un clustering spectral en ligne avec des garanties de performance théoriques. Des applications au clustering d'images confirment nos résultats.

**Abstract** – This article introduces a random matrix framework for the analysis of clustering on data streams. Assuming that, due to memory limitations, only a few data points are available, the Gram matrix can only be partially computed. Under a large dimensional data regime, we study its limiting spectral distribution and its isolated eigenvalues and eigenvectors. We detail how these results can be used to perform efficient online kernel spectral clustering with theoretical performance guarantees. Our findings are empirically confirmed on image clustering tasks.

## 1 Introduction

Alors que la quantité phénoménale de données générées sans relâche ne cesse de croître, le désastre écologique nous pousse à considérer de nouvelles manières, plus sobres, d'utiliser nos ressources de calcul. L'apprentissage en ligne peut ainsi sembler être une approche pertinente pour traiter des données de grande dimension avec des moyens mémoire limités; que ce soit à cause d'un volume de données trop grand, ou parce que l'on est restreint à l'utilisation d'un ordinateur conventionnel.

De nombreux travaux ont déjà proposé des approches algorithmiques de clustering sur des flux de données [3]. La plupart exploitent les données telles quelles et voient donc leurs performances se dégrader à mesure que la dimension augmente. Il est néanmoins possible de contrer ce fléau de la dimension en projetant les données sur un espace de dimension inférieure.

Au vu des performances séduisantes du clustering spectral sur des données de grande dimension, des adaptations en ligne ont été proposées (notamment [7]). Il est en effet bien moins énergivore que la plupart des algorithmes de clustering classiques puisqu'il permet de drastiquement réduire la dimension des données en ne conservant que quelques composantes spectrales dominantes. De plus, cet algorithme jouit d'intéressant résultats d'optimalité.<fnref n="1" />

Récemment, l'analyse par matrices aléatoires de la matrice

de Gram $K = \frac{1}{p}X^\top X$ calculée à partir d'un échantillon de $n$ données $X = [x_1 \dots x_n] \in \mathbb{R}^{p \times n}$ a permis de montrer que d'énormes gains en coût calculatoire pouvaient être obtenus au prix d'une perte de performance négligeable [1, 6]. À la lumière de ces résultats, de la puissance du clustering spectral sur des données de grande dimension et de la praticité de l'apprentissage en ligne pour traiter de grands flux de données avec peu de ressources mémoire, cet article présente un algorithme de clustering spectral en ligne auquel s'ajoute une analyse de performances rigoureuse grâce à la théorie des matrices aléatoires. Nos résultats sont validés sur des applications au clustering d'images.

## 2 Modèle d'apprentissage en ligne

### 2.1 Position du problème

Soit $X = [x_1 \dots x_n] \in \mathbb{R}^{p \times n}$ un échantillon de $n$ données de dimension $p$ réparties en deux classes $C^{\pm}$ de barycentres respectifs $\pm\mu \in \mathbb{R}^p$.<fnref n="2" /> On définit aussi le vecteur $j \in \{\pm 1\}^n$ tel que $j_i = +1$ si $x_i \in C^+$ et $j_i = -1$ si $x_i \in C^-$.<fnref n="2" />

**Hypothèse 1.** Les éléments de $j$ sont des réalisations indépendantes d'une loi de mesure $\pi^{-}\delta_{-1} + \pi^{+}\delta_{+1}$ où $\pi^{-}, \pi^{+} > 0$ et $\pi^{-} + \pi^{+} = 1$. À savoir : la classe $C^{\pm}$ est représentée en

<footnote n="1">1. Il atteint le seuil de transition de phase optimal (c'est-à-dire qu'il fait mieux qu'un choix aléatoire dès que cela est théoriquement possible) et réalise l'erreur de classification optimale sur des modèles de mélange de gaussiennes.</footnote>

<footnote n="2">2. On se restreint ici au cas simplifié de données binaires centrées empiriquement. Le cas général à $K$ classes peut être traité par une étude plus approfondie [5].</footnote>
proportion $\pi^{\pm}$ et la classe de $\mathbf{x}_i$ ne dépend pas de celle de $\{\mathbf{x}_j\}_{j \neq i}$.

**Hypothèse 2 (Condition de non-trivialité).**

$$0 < \liminf_{p \to +\infty} \|\boldsymbol{\mu}\| \le \limsup_{p \to +\infty} \|\boldsymbol{\mu}\| < +\infty.$$

C'est-à-dire que le problème ne devient ni trop facile ($\|\boldsymbol{\mu}\| \to +\infty$) ni trop difficile ($\|\boldsymbol{\mu}\| \to 0$).

**Hypothèse 3 (Modèle de bruit additif).** $\mathbf{X} = \mathbf{P} + \mathbf{Z}$ où $\mathbf{P} = \boldsymbol{\mu}\mathbf{j}^{\top}$ est une matrice déterministe (signal) et $\mathbf{Z}$ est une matrice aléatoire (bruit) à entrées indépendantes de loi normale centrée réduite $\mathcal{N}(0, 1)$.

Dans un contexte en ligne, seul un petit nombre $L$ de données peut être conservé en mémoire. Le calcul de la matrice de Gram $\mathbf{K} = \frac{1}{p}\mathbf{X}\mathbf{X}^{\top}$ est alors limité à une bande de rayon $L$ autour de sa diagonale : l'élément $\mathbf{K}_{i,j} = \frac{1}{p}\mathbf{x}_i\mathbf{x}_j^{\top}$ ne peut être calculé que si $|i-j| < L$. On modélise cela par l'application d'un masque $\mathbf{T} = [\mathbf{1}_{|i-j|<L}]_{1 \le i,j \le n}$ :

$$\mathbf{K}_L = \frac{\mathbf{X}^{\top}\mathbf{X}}{p} \odot \mathbf{T} \quad \text{avec} \quad \mathbf{T} = \begin{bmatrix} 1 & \dots & 1 & 0 \\ \vdots & \ddots & \vdots & \vdots \\ 1 & \dots & 1 & 1 \\ 0 & \dots & 1 & 1 \end{bmatrix}$$

où $\odot$ représente le produit de Hadamard.

De par l'optimalité du clustering spectral classique, on s'attend à obtenir de bonnes performances avec la matrice $\mathbf{K}_L$ tant que $L$ et $n$ restent du même ordre. Notre objectif est donc de décrire le comportement spectral de $\mathbf{K}_L$ lorsque $n, p$ et $L$ sont grands. Pour cela, on considère le régime où $n, p, L \to +\infty$ avec $p/n \to c \in ]0, +\infty[$ et $(2L-1)/n \to \varepsilon \in ]0, +\infty[$.$^3$

## 2.2 Approximation circulante

Malgré son apparente simplicité, la matrice de Toeplitz $\mathbf{T}$ s'avère contraignante dans nos calculs, à cause de l'appariation "d'effets de bord". On lui préférera son approximation circulante $\mathbf{C} = [\mathbf{1}_{|i-j|<L} + \mathbf{1}_{|i-j|>n-L}]_{1 \le i,j \le n}$ qui fait paraître ces effets indésirables tout en conservant un spectre "proche" de celui de la matrice originale [4].

On note $\{\tau_k\}_{0 \le k < n}$ et $\{\psi_k\}_{0 \le k < n}$ les valeurs propres de $\mathbf{T}$ et $\mathbf{C}$ respectivement. La décomposition spectrale de l'approximation circulante est bien connue :

$$\psi_k = \nu_L \left( \frac{2k\pi}{n} \right) \quad \text{avec} \quad \nu_L(x) = \frac{\sin\left(\left(2L-1\right)\frac{x}{2}\right)}{\sin\left(\frac{x}{2}\right)}$$

et $\mathbf{C} = \mathbf{F}\mathbf{\Psi}\mathbf{F}^*$ où $\mathbf{F}$ est la matrice de Fourier d'ordre $n$ ($\mathbf{F}_{i,j} = \frac{1}{\sqrt{n}}e^{-\frac{2i\pi}{n}(i-1)(j-1)}$) et où $\mathbf{\Psi} = \text{diag}(\psi_k)_{0 \le k < n}$.

On observe empiriquement que les résultats des théorèmes 1 et 2 exposés ci-après restent valables dans le cadre qui nous intéresse après avoir remplacé les $\psi_k$ par $\tau_k$ et $\mathbf{F}$ par une base orthonormale $\mathbf{G}$ de vecteurs propres de $\mathbf{T}$ dans les formules présentées.

# 3 Résultats

Afin de comprendre l'impact du cadre en ligne de notre problème, on étudie le spectre de la matrice de Gram incomplète $\mathbf{K}_L$. Son comportement spectral en grande dimension peut être analysé via sa résolvante, objet d'étude classique en théorie des matrices aléatoires [2] :

$$\mathbf{Q}(z) = (\mathbf{K}_L - z\mathbf{I}_n)^{-1} \quad z \in \mathbb{C} \setminus \text{sp}(\mathbf{K}_L)$$

où $\text{sp}(\mathbf{K}_L)$ est l'ensemble des valeurs propres de $\mathbf{K}_L$. En particulier, la transformée de Stieltjes $m_n$ de la distribution spectrale empirique $\mu_n = \frac{1}{n} \sum_{\xi \in \text{sp}(\mathbf{K}_L)} \delta_{\xi}$ de $\mathbf{K}_L$ est la trace normalisée de sa résolvante : $m_n(z) \equiv \int_{\mathbb{R}} \frac{\mu_n(dt)}{t-z} = \frac{1}{n} \text{tr } \mathbf{Q}(z)$.

## 3.1 Distribution spectrale limite

Notre premier théorème présente un équivalent déterministe de la résolvante lorsque le masque $\mathbf{T}$ est approché par $\mathbf{C}$ : $\tilde{\mathbf{Q}}(z) = (\tilde{\mathbf{K}}_L - z\mathbf{I}_n)^{-1}$ avec $\tilde{\mathbf{K}}_L = \frac{\mathbf{X}^{\top}\mathbf{X}}{p} \odot \mathbf{C}$. Précisément, on définit une matrice $\tilde{\mathbf{Q}}(z)$ telle que, pour toutes suites de matrices $\mathbf{A}_n \in \mathbb{R}^{n \times n}$ et vecteurs $\mathbf{a}_n, \mathbf{b}_n \in \mathbb{R}^n$ de norme (spectrale et euclidienne respectivement) unitaire, $\frac{1}{n} \text{tr } \mathbf{A}_n(\tilde{\mathbf{Q}}(z) - \tilde{\mathbf{Q}}(z)) \to 0$ et $\mathbf{a}_n^{\top}(\tilde{\mathbf{Q}}(z) - \tilde{\mathbf{Q}}(z))\mathbf{b}_n \to 0$ presque sûrement lorsque $n, p, L \to +\infty$. On note cela $\tilde{\mathbf{Q}}(z) \leftrightarrow \tilde{\mathbf{Q}}(z)$.

**Théorème 1 (Équivalent déterministe de $\tilde{\mathbf{Q}}(z)$).** Sous les hypothèses 1-3, $\tilde{\mathbf{K}}_L$ admet une distribution spectrale limite $\mu$ lorsque $n, p, L \to +\infty$. Sa transformée de Stieltjes $m$ est solution de

$$1 + zm(z) = \frac{p}{n} \sum_{k=0}^{n-1} \frac{m(z) \frac{\psi_k}{p}}{1 + m(z) \frac{\psi_k}{p}} \quad z \in \mathbb{C} \setminus \text{supp } \mu.$$

De plus, si $\text{dist}(z, \text{supp } \mu) > \frac{2L-1}{p}$, alors

$$\tilde{\mathbf{Q}}(z) \leftrightarrow \tilde{\mathbf{Q}}(z) \equiv m(z) [\mathbf{D}_j\mathbf{F}] (\mathbf{I}_n + \|\boldsymbol{\mu}\|^2 \mathbf{\Lambda}(z))^{-1} [\mathbf{D}_j\mathbf{F}]^*$$

où $\mathbf{\Lambda}(z) = m(z) \frac{\Psi}{p} (\mathbf{I}_n + m(z) \frac{\Psi}{p})^{-1}$ et $\mathbf{D}_j = \text{diag } j$ est la matrice diagonale induite par le vecteur $\mathbf{j}$.

On observe dans ce théorème que $\tilde{\mathbf{Q}}(z)$ est l'inverse d'une perturbation de l'identité qui n'est pas de petit rang (la matrice diagonale $\mathbf{\Lambda}(z)$), contrairement à ce que l'on a l'habitude de voir dans les modèles dits spikes classiques. Néanmoins la plupart des éléments diagonaux de $\mathbf{\Lambda}(z)$ seront généralement assez petits pour que seul un petit nombre de valeurs propres (les spikes) s'isolent des autres. On s'attend donc à voir un petit nombre de valeurs propres en dehors du spectre limite de $\mathbf{K}_L$.

Il est possible de calculer numériquement la transformée de Stieltjes $m$ et d'en déduire la distribution spectrale limite de $\tilde{\mathbf{K}}_L$. La Figure 1 présente des exemples de distributions spectrales empirique et limite de $\tilde{\mathbf{K}}_L$ en l'absence de signal (haut) et pour un mélange de deux classes (bas). Dans ce dernier cas, on observe effectivement l'apparition de plusieurs valeurs propres s'isolant du support limite. Ces dernières portent l'information que l'on cherche à retrouver et il convient de s'y intéresser plus précisément.

<footnote n="3">3. La convergence des résultats asymptotiques présentés est au moins $O(1/\sqrt{n})$, ils restent donc valides à un horizon grand mais fini.</footnote>
<figure><img src="image_2.png" /><figcaption>FIGURE 1 – Distribution spectrale empirique (DSE) et distribution spectrale limite (DSL) de $\tilde{K}_L$. L’axe des ordonnées est en échelle logarithmique. En haut : bruit seul, $\mathbf{x}_i \sim \mathcal{N}(0, \mathbf{I}_p)$. En bas : mélange de deux classes, $\mathbf{x}_i \sim \mathcal{N}(\pm\boldsymbol{\mu}, \mathbf{I}_p)$ avec $\|\boldsymbol{\mu}\| = 2$. Les tirets verts indiquent les positions asymptotiques des spikes $\tilde{\xi}_k$. Paramètres : $n = 2500$, $L = 750$ et $p = 1250$ (gauche) ou $p = 75$ (droite).</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>FIGURE 2 – Position de la transition de phase ($\|\boldsymbol{\mu}\|^2$) du vecteur propre dominant de la matrice à noyau en fonction du paramètre $\varepsilon = \frac{2L-1}{n}$ avec $n/p = 100$. La classification n’est possible qu’au-dessus de la courbe correspondant à la méthode employée. Les tirets noirs indiquent la transition de phase optimale (lorsque toutes les données sont disponibles). Vert : clustering spectral en ligne. Rouge : clustering spectral standard avec $L$ données.</figcaption></figure>

## 3.2 Comportement des spikes

Par une analyse de la matrice $\tilde{Q}(z)$, le théorème suivant précise la position asymptotique des valeurs propres isolées ainsi que l’aspect des vecteurs propres associés.

**Théorème 2** (Transition de phase, valeurs propres isolées et alignements des vecteurs propres). Pour chaque entier $k \in \{0, \dots, n-1\}$, on définit

$$ \bar{\xi}_k = (\|\boldsymbol{\mu}\|^2 + 1) \frac{\psi_k}{p} \left( 1 + \frac{p}{n} \sum_{l=0}^{n-1} \frac{1}{\left(\|\boldsymbol{\mu}\|^2 + 1\right) \frac{\psi_k}{\psi_l} - 1} \right) $$

et

$$ \bar{\zeta}_k = \frac{\|\boldsymbol{\mu}\|^2}{\|\boldsymbol{\mu}\|^2 + 1} \left( 1 - \frac{p}{n} \sum_{l=0}^{n-1} \frac{1}{\left[ \left( \|\boldsymbol{\mu}\|^2 + 1 \right) \frac{\psi_k}{\psi_l} - 1 \right]^2} \right). $$

Les trois propositions suivantes sont alors équivalentes.

1. $\psi_k \neq 0$ et $\bar{\xi}_k \notin \text{supp } \boldsymbol{\mu}$.

2. $\bar{\zeta}_k > 0$.

3. Presque sûrement, $\bar{\xi}_k$ est la position asymptotique d'une valeur propre isolée (un spike) de $\tilde{K}_L$.

De plus, dans ce cas, la matrice $\mathbf{U}_k = [\mathbf{u}_l]_{\substack{\psi_k=\psi_l \\ 0 \le l < n}}$ rassemble tous les vecteurs propres de $\tilde{K}_L$ dont la valeur propre associée converge p.s. vers $\bar{\xi}_k$ et

$$ \mathbf{U}_k \mathbf{U}_k^\top \leftrightarrow \bar{\zeta}_k [\mathbf{D}_j \mathbf{F}] \mathcal{D}_k [\mathbf{D}_j \mathbf{F}]^* $$

où $\mathcal{D}_k = \text{diag}(\mathbf{1}_{\psi_k=\psi_l})_{0 \le l < n}$.

Pour bien comprendre ce théorème, il faut voir $\bar{\xi}_k$ comme la position asymptotique *potentielle* d'un spike et $\bar{\zeta}_k$ comme une valeur indicatrice : lorsqu'elle est positive, un spike existe bien autour de $\bar{\xi}_k$ (tirets vers dans la Figure 1) et alors, plus $\bar{\zeta}_k$ est proche de 1, meilleure est la “qualité” de l’information portée par le vecteur propre associé. La valeur de $\bar{\zeta}_k$ correspond en effet à l’alignement asymptotique entre le vecteur proprepirique associé $\mathbf{u}_k$ et le vecteur population $\mathbf{v}_k = \mathbf{F}_{:,k} \odot \mathbf{j}$ correspondant au vecteur $\mathbf{j}$ (l’information recherchée) modulé par la base de Fourier<fnref n="4" /> : $|\mathbf{u}_k^* \mathbf{v}_k|^2 \xrightarrow{\text{p.s.}} \bar{\zeta}_k$. Notons que ces valeurs propres isolées peuvent apparaître des deux côtés du spectre, et même entre deux composantes continues (cf. Figure 1) !

# 4 Clustering spectral en ligne

## 4.1 Compromis performance – coût

Les résultats du théorème 2 nous permettent de trouver la position de la transition de phase, c’est-à-dire la valeur de $\|\boldsymbol{\mu}\|$ en-dessous de laquelle la classification n’est plus réalisable. Elle est donnée par l’équation $\bar{\zeta}_k(\|\boldsymbol{\mu}\|) = 0$. De plus, on sait désormais qu’au-delà de celle-ci, les vecteurs propres isolés de $\tilde{K}_L$ s’alignent avec des versions modulées du vecteur $\mathbf{j}$, qu’il est alors possible d’estimer.

La Figure 2 présente la position $\|\boldsymbol{\mu}\|^2$ de la transition de phase en fonction de $\varepsilon = \frac{2L-1}{n}$ avec l’erreur de classification (théorique) du clustering spectral en ligne lorsque $n/p = 100$.

<footnote n="4">4. On rappelle qu’il s’agit des vecteurs propres du masque $\mathbf{C}$.</footnote>
Celle-ci est comparée avec le clustering *par batches*, c'est-à-dire le clustering spectral standard n'utilisant que les *L* données disponibles en mémoire. La transition de phase de cette dernière a lieu bien plus tard que celle de la méthode proposée. À mesure que $\epsilon$ croît (c'est-à-dire que la mémoire disponible augmente), le seuil optimal $||\mu||^2 = \sqrt{c}$ en-dessous duquel aucune classification non-triviale n'est possible est atteint. De plus, à $\epsilon$ fixé, l'erreur de classification décroît logiquement vers 0 lorsque la puissance du signal croît.

## 4.2 Principe de l'algorithme

On considère un flux de données de longueur (possiblement infinie) $T \ge n$. À chaque pas de temps, une nouvelle donnée $\mathbf{x}_t$ entre en mémoire tandis que $\mathbf{x}_{t-L}$ est supprimée. La matrice de Gram est ensuite mise à jour :

$$[\mathbf{K}_L^{(t)}]_{i,j} = \frac{1}{p} \mathbf{x}_{t-n+i}^{\top} \mathbf{x}_{t-n+j} \mathbf{1}_{|i-j|<L}$$

L'alignement des vecteurs propres isolés de $\mathbf{K}_L^{(t)}$ avec les vecteurs population (théorème 2) permet alors la classification des $n$ dernières données.<fnref n="5" /> Cet algorithme classifie donc les $n$ derniers points à chaque instant, même si la plupart d'entre eux ne sont déjà plus conservés en mémoire !

Remarque 1 (Choix de $n$ et $L$). Tandis que $L$ représente le nombre de données conservées en mémoire, $n \ge L$ correspond au nombre de données que l'on classifie à chaque pas de temps. Ces deux paramètres sont fixés par l'utilisateur en prenant en compte les précédentes considérations sur la performance (Figure 2) et les limitations mémoire : l'espace nécessaire est $O(Lp + Ln)$ pour les données et la matrice de Gram.

## 4.3 Applications au clustering d'images

Pour illustrer nos résultats, on simule deux flux d'images. Le premier avec $T = 20000$ représentations VGG ($p = 4096$) d'images de chiens (collie) et chats (tabby) générées avec un réseau BigGAN. Le second avec $T = 14000$ images de Fashion-MNIST ($p = 784$) des classes coat et ankle boot. Dans les deux cas, on choisit $n = 1000$ et $L = 100$.

La Figure 3 représente l'erreur de classification à $t_0 + \Delta t$ d'une donnée arrivée à $t_0$, ainsi que l'erreur de classification globale obtenue avec un vote majoritaire (tirets verts) et l'erreur de classification obtenue avec un clustering spectral $T \times T$ standard<fnref n="6" /> (pointillés noirs). Les performances obtenues avec l'algorithme en ligne sont très proches de celles du clustering spectral complet mais ce premier nécessite beaucoup moins de ressources mémoire ($O(Lp + Ln)$ contre $O(Tp + T^2)$).

# 5 Conclusions et perspectives

Une approche par matrices aléatoires nous a permis de montrer que des performances quasi-optimales pouvaient être obtenues.

<figure><img src="image_4.png" /><figcaption>FIGURE 3 – Errur de classification en fonction du retard $\Delta t$ sur les images BigGAN (haut) et Fashion-MNIST (bas). Il s'agit de l'erreur de classification moyenne à $t_0 + \Delta t$ pour une donnée arrivée à $t_0$. Les tirets verts indiquent l'erreur de classification globale (obtenue par vote majoritaire). Les pointillés noirs représentent l'erreur de classification obtenue par clustering spectral $T \times T$ hors ligne. **Paramètres** : $T = 20000$, $n = 1000$, $p = 4096$, $L = 100$ (images BigGAN) et $T = 14000$, $n = 1000$, $p = 784$, $L = 100$ (Fashion-MNIST).</figcaption></figure>

nues sur des données de grande dimension avec un algorithme de clustering spectral en ligne. La méthode proposée résulte d'une analyse asymptotique précisant les performances atteignables lors de clustering sur un flux de données. Le cadre en ligne manque cependant de résultats d'optimalité de la part de la théorie de l'information, qui est une piste à approfondir.

## Références

[1] R. Couillet, F. Chatelain, and N. Le Bihan. Two-way kernel matrix puncturing : towards resource-efficient PCA and spectral clustering. arXiv:2102.12293 [cs, stat], May 2021. arXiv: 2102.12293.

[2] R. Couillet and Z. Liao. Random Matrix Methods for Machine Learning: When Theory meets Applications. 2021.

[3] M. Ghesmoune, M. Lebbah, and H. Azzag. State-of-the-art on clustering data streams. Big Data Analytics, 1(1):13, Dec. 2016.

[4] R. M. Gray. Toeplitz and Circulant Matrices: A Review. Foundations and Trends® in Communications and Information Theory, 2(3):155-239, Jan. 2006. Publisher: Now Publishers, Inc.

[5] H. Lebeau, R. Couillet, and F. Chatelain. A random matrix analysis of data stream clustering : coping with limited memory resources. In Proceedings of the 39th International Conference on Machine Learning. PMLR, July 2022.

[6] Z. Liao, R. Couillet, and M. W. Mahoney. Sparse Quantized Spectral Clustering. arXiv:2010.01376 [cs, math, stat], Oct. 2020. arXiv: 2010.01376.

[7] S. Yoo, H. Huang, and S. P. Kasiviswanathan. Streaming spectral clustering. In 2016 IEEE 32nd International Conference on Data Engineering (ICDE), pages 637-648, May 2016.

<footnote n="5">5. Dans le cas binaire considéré ici, le vecteur propre dominant suffit.</footnote>

<footnote n="6">6. Qu'on sait atteindre le seuil de transition de phase optimal.</footnote>