Skalierbare dünnbesetzte Unterraumclustering durch orthogonale Matchingverfolgung

Subspace-Clustering-Methoden, die auf der Regularisierung mit $\ell_1$, $\ell_2$ oder der nuklearen Norm basieren, sind aufgrund ihrer Einfachheit, theoretischen Garantien und empirischen Erfolgen sehr populär geworden. Die Wahl des Regularisators kann jedoch sowohl Theorie als auch Praxis erheblich beeinflussen. Zum Beispiel garantiert die Regularisierung mit $\ell_1$, unter weitreichenden Bedingungen (z.B. beliebige Subräume und verfälschte Daten), eine subraum-erhaltende Affinität (d.h., es gibt keine Verbindungen zwischen Punkten aus verschiedenen Subräumen). Allerdings erfordert sie die Lösung eines groß angelegten konvexen Optimierungsproblems. Im Gegensatz dazu bieten die Regularisierung mit $\ell_2$ und der nuklearen Norm effiziente geschlossene Formlösungen, aber um eine subraum-erhaltende Affinität zu garantieren, müssen sehr starke Annahmen getroffen werden, z.B. unabhängige Subräume und unverfälschte Daten. In dieser Arbeit untersuchen wir eine Subspace-Clustering-Methode, die auf orthogonalem Matching Pursuit basiert. Wir zeigen, dass diese Methode sowohl rechnerisch effizient ist als auch unter weitreichenden Bedingungen eine subraum-erhaltende Affinität garantiert. Experimente mit synthetischen Daten bestätigen unsere theoretische Analyse, und Anwendungen im Bereich der Handschriftenerkennung und Gesichtsclustering zeigen, dass unser Ansatz den besten Kompromiss zwischen Genauigkeit und Effizienz erreicht.