Probabilistic Recovery of Multiple Subspaces in Point Clouds by Geometric lp Minimization

Understand

We assume data independently sampled from a mixture distribution on the unit ball of the D-dimensional Euclidean space with K+1 components: the first component is a uniform distribution on that ball representing outliers and the other K components are uniform distributions along K d-dimensional linear subspaces restricted to that ball.

• We study both the simultaneous recovery of all K underlying subspaces and the recovery of the best l0 subspace (i.e., with largest number of points) by minimizing the lp-averaged distances of data points from d-dimensional subspaces of the D-dimensional space.
• Unlike other lp minimization problems, this minimization is non-convex for all p>0 and thus requires different methods for its analysis.
• We show that if 0<p <= 1, then both all underlying subspaces and the best l0 subspace can be precisely recovered by lp minimization with overwhelming probability.