An Overview of Robust Subspace Recovery

The works on FMS [49] and GGD [68] do not have proofs of fast convergence, even though we observe fast convergence in practice for these methods (using line search in GGD). On the other hand, TORP [17] is guaranteed to linearly converge and thus has better theoretical complexity despite being slower in practice. RANSAC also runs in O(NDd), provided that the number of iterations is not too large. Arias-Castro and Wang [2] bound the number of iterations required for exact recovery when SNR d and the data is noiseless and in general position with respect to the underlying subspace. However, they show that for lower SNR the number of iterations becomes exponential in d.