Abstract

We present a mathematical analysis of a non-convex energy landscape forrobust subspace recovery. We prove that an underlying subspace is the onlystationary point and local minimizer in a specified neighborhood underdeterministic conditions on a dataset. If the deterministic condition issatisfied, we further show that a geodesic gradient descent method over theGrassmannian manifold can exactly recover the underlying subspace when themethod is properly initialized. Proper initialization by principal componentanalysis is guaranteed with a similar deterministic condition. Under slightlystronger assumptions, the gradient descent method with a special shrinking stepsize scheme achieves linear convergence. The practicality of the deterministiccondition is demonstrated on some statistical models of data, and the methodachieves almost state-of-the-art recovery guarantees on the Haystack Model fordifferent regimes of sample size and ambient dimension. In particular, when theambient dimension is fixed and the sample size is large enough, we show thatour gradient method can exactly recover the underlying subspace for any fixedfraction of outliers (less than 1).

 

Introduction (beta)

None

 

Conclusion (beta)

None