10.000-fach beschleunigte robuste Teilmengeauswahl (ARSS)

Die Auswahl von Teilmengen aus massiven Daten mit verrauschten Informationen gewinnt für verschiedene Anwendungen zunehmend an Bedeutung. Dieses Problem bleibt jedoch hochgradig herausfordernd, da aktuelle Methoden im Allgemeinen langsam sind und anfällig für Ausreißer. Um die beiden genannten Probleme zu lösen, schlagen wir eine beschleunigte robuste Teilmenge-Auswahlmethode (ARSS) vor. Insbesondere in der Bereich der Teilmengeauswahl ist dies der erste Versuch, das $\ell_{p}(0<p\leq1)$-Norm-basierte Maß für den Repräsentationsverlust einzusetzen, um große Fehler daran zu hindern, unser Ziel zu dominieren. Dadurch wird die Robustheit gegenüber Ausreißerelementen erheblich gesteigert. Tatsächlich ist die Datenmenge in der Regel viel größer als die Merkmallänge, d.h. $N \gg L$. Auf dieser Beobachtung basierend schlagen wir einen Beschleunigungslöser (mittels ALM und äquivalenter Ableitungen) vor, um die Rechenkosten stark zu reduzieren – theoretisch von $O(N^{4})$ auf $O(N^{2}L)$. Umfangreiche Experimente an zehn Benchmark-Datensätzen bestätigen, dass unsere Methode nicht nur den Stand der Technik übertreffen kann, sondern auch mehr als 10.000-mal schneller läuft als die am stärksten verwandte Methode.