Command Palette
Search for a command to run...
Skalierbare dünnbesetzte Unterraumclustering durch orthogonale Matchingverfolgung
Skalierbare dünnbesetzte Unterraumclustering durch orthogonale Matchingverfolgung
Chong You; Daniel P. Robinson; Rene Vidal
Zusammenfassung
Subspace-Clustering-Methoden, die auf der Regularisierung mit ℓ1, ℓ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 ℓ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 ℓ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.