Robust Plane Clustering Based on L1-Norm Minimization

Plane clustering methods, typically, $k$ plane clustering ( $k$ PC), play conclusive roles in the family of data clustering. Instead of point-prototype, they aim to seek multiple plane-prototype fitting planes as centers to group the given data into their corresponding clusters based on L2 norm metric. However, they are usually sensitive to outliers because of square operation on the L2 norm. In this paper, we focus on robust plane clustering and propose a L1 norm plane clustering method, termed as $\text{L}1k$ PC. The leading problem is optimized on the L1 ball hull, a non-convex feasible domain. To handle the problem, we provide a new strategy and its related mathematical proofs for L1 norm optimization. Compared to state-of-the-art methods, the advantages of our proposed lie in 4 folds: 1) similar to $k$ PC, it has clear geometrical interpretation; 2) it is more capable of resisting to outlier; 3) theoretically, it is proved that the leading non-convex problem is equivalent to several convex sub-problems. To our best knowledge, this opens up a new way for L1 norm optimization; 4) the $k$ fitting planes are solved by $k$ individual linear programming problems, rather than higher time-consuming eigenvalue equations or quadratic programming problems used in the conventional plane clustering methods. Experiments on some artificial, benchmark UCI and human face datasets show its superiorities in robustness, training time, and clustering accuracy.