10,000+ 회 가속화된 강건한 부분 집합 선택 (ARSS)

대규모 데이터에서 노이즈 정보를 포함한 부분 집합 선택은 다양한 응용 분야에서 점점 더 인기 있는 문제입니다. 그러나 이 문제는 여전히 매우 어려운데, 현재의 방법들이 일반적으로 속도가 느리고 이상치에 민감하기 때문입니다. 이러한 두 가지 문제를 해결하기 위해 가속화된 강건한 부분 집합 선택(Accelerated Robust Subset Selection, ARSS) 방법을 제안합니다. 특히 부분 집합 선택 영역에서는, 표현 손실을 측정하는 데 $\ell_{p}(0<p\leq1)$-노름 기반 지표를 사용하는 첫 번째 시도입니다. 이로 인해 큰 오류가 목적 함수를 지배하는 것을 방지하여 이상치 요소에 대한 강건성이 크게 향상되었습니다. 실제로 데이터 크기는 일반적으로 특성 길이보다 훨씬 큽니다, 즉 $N \gg L$입니다. 이 관찰에 기반하여 계산 비용을 크게 줄이는 속도 향상 솔버(Alternating Direction Method of Multipliers (ALM) 및 동등 유도를 통해)를 제안합니다. 이론적으로 계산 복잡도는 $O(N^{4})$에서 $O(N^{2}L)$으로 대폭 감소됩니다. 10개의 벤치마크 데이터셋을 이용한 광범위한 실험 결과, 제안된 방법이 최신 방법들을 능가할 뿐만 아니라 가장 관련성이 높은 방법보다 10,000+ 배 더 빠르게 실행됨을 확인하였습니다.