Clustering parcimonieux de sous-espaces à grande échelle par poursuite d'appariement orthogonal

Les méthodes de clustering de sous-espaces basées sur la régularisation $\ell_1$, $\ell_2$ ou nucléaire ont connu une grande popularité en raison de leur simplicité, de leurs garanties théoriques et de leur succès empirique. Cependant, le choix du régulariseur peut avoir un impact significatif tant sur la théorie que sur la pratique. Par exemple, la régularisation $\ell_1$ est garantie pour fournir une affinité préservant les sous-espaces (c'est-à-dire qu'il n'y a pas de connexions entre des points appartenant à des sous-espaces différents) sous des conditions larges (par exemple, des sous-espaces arbitraires et des données corrompues). Toutefois, elle nécessite la résolution d'un problème d'optimisation convexe à grande échelle. En revanche, la régularisation $\ell_2$ et nucléaire offre des solutions explicites efficaces, mais requiert des hypothèses très fortes pour garantir une affinité préservant les sous-espaces, par exemple des sous-espaces indépendants et des données non corrompues. Dans cet article, nous étudions une méthode de clustering de sous-espaces basée sur le poursuite d'appariement orthogonal (orthogonal matching pursuit). Nous montrons que cette méthode est à la fois efficace sur le plan computationnel et garantie pour fournir une affinité préservant les sous-espaces sous des conditions larges. Des expériences sur des données synthétiques vérifient notre analyse théorique, et des applications au clustering de chiffres manuscrits et de visages montrent que notre approche réalise le meilleur compromis entre précision et efficacité.