ISCA: an Iterative Simplicial-Complex Approximation Method to Solve k-Hyperplane Clustering to Global Optimality

We propose the Iterative Simplicial-Complex Approximation (ISCA) method to solve to global optimality the k-HC - the k-Hyperplane Clustering problem that asks to find k hyperplanes that minimize the sum of squared 2-norm (Euclidean) distances between each point and its closest hyperplane. ISCA is based on Spatial Branch and Bound (SBB) and approximates the infeasible unit ball of the hyperplane normals featured in k-HC from the inside with a growing simplicial complex, which is adaptively refined by gluing to it, via multiway branching, new simplices whose apexes are the radial projections onto the unit sphere of infeasible relaxation solutions. We prove that ISCA never discards a feasible solution, thereby certifying global optimality when its gap closes, and that the relaxation given by its initial simplex yields lower bounds within a tight multiplicative factor of 1/n^2. Experimentally, we show that ISCA improves upon the state of the art as the ambient dimension grows: on the instances with n >= 4, it reduces the mean optimality gap by 25% and it proves a nonzero lower bound on nine instances on which that of the state of the art is still zero, while the converse never occurs; with n in 5, 6, 7, it also solves more instances and is 1.7x faster in geometric mean.