  Projective clustering is a problem with both theoretical and practical
importance and has received a great deal of attentions in recent years. Given a
set of points $P$ in $\mathbb{R}^{d}$ space, projective clustering is to find a
set $\mathbb{F}$ of $k$ lower dimensional $j$-flats so that the average
distance (or squared distance) from points in $P$ to their closest flats is
minimized. Existing approaches for this problem are mainly based on
adaptive/volume sampling or core-sets techniques which suffer from several
limitations. In this paper, we present the first uniform random sampling based
approach for this challenging problem and achieve linear time solutions for
three cases, general projective clustering, regular projective clustering, and
$L_{\tau}$ sense projective clustering. For the general projective clustering
problem, we show that for any given small numbers $0<\gamma, \epsilon <1$, our
approach first removes $\gamma|P|$ points as outliers and then determines $k$
$j$-flats to cluster the remaining points into $k$ clusters with an objective
value no more than $(1+\epsilon)$ times of the optimal for all points. For
regular projective clustering, we demonstrate that when the input points
satisfy some reasonable assumption on its input, our approach for the general
case can be extended to yield a PTAS for all points. For $L_{\tau}$ sense
projective clustering, we show that our techniques for both the general and
regular cases can be naturally extended to the $L_{\tau}$ sense projective
clustering problem for any $1 \le \tau < \infty$. Our results are based on
several novel techniques, such as slab partition, $\Delta$-rotation, symmetric
sampling, and recursive projection, and can be easily implemented for
applications.
