Reduced row echelon form and non-linear approximation for subspace segmentation and high-dimensional data clustering

Given a set of data W={w1,…,wN}∈RDW={w1,…,wN}∈RD drawn from a union of subspaces, we focus on determining a nonlinear model of the form U=⋃i∈ISiU=⋃i∈ISi, where {Si⊂RD}i∈I{Si⊂RD}i∈I is a set of subspaces, that is nearest to W. The model is then used to classify W into clusters. Our approach is based on the binary reduced row echelon form of data matrix, combined with an iterative scheme based on a non-linear approximation method. We prove that, in absence of noise, our approach can find the number of subspaces, their dimensions, and an orthonormal basis for each subspace SiSi. We provide a comprehensive analysis of our theory and determine its limitations and strengths in presence of outliers and noise.