2014/03/04 by James Voss, Mikhail A. Belkin, Voss, James +4 · 1 citation
Computer Science · Engineering · Mathematics · #Algorithm #Artificial intelligence #Basis (linear algebra) #Blind Source Separation Techniques #Cluster analysis #Computer science #Convex function #Convex optimization #Convexity #FOS: Computer and information sciences #Image and Signal Denoising Methods #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Mathematical optimization #Mathematics #Minification #Optimization problem #Regular polygon #Sparse and Compressive Sensing Techniques #Spectral clustering #cs.LG #stat.ML
paper · pdf · doi:10.48550/arxiv.1403.0667
22 pages
openalex publication_date 2014/03/04 · arxiv created 2016/05/04 · arxiv updated 2016/05/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
In recent years, spectral clustering has become a standard method for data analysis used in a broad range of applications. In this paper we propose a new class of algorithms for multiway spectral clustering based on optimization of a certain "contrast function" over the unit sphere. These algorithms, partly inspired by certain Independent Component Analysis techniques, are simple, easy to implement and efficient. Geometrically, the proposed algorithms can be interpreted as hidden basis recovery by means of function optimization. We give a complete characterization of the contrast functions admissible for provable basis recovery. We show how these conditions can be interpreted as a "hidden convexity" of our optimization problem on the sphere; interestingly, we use efficient convex maximization rather than the more common convex minimization. We also show encouraging experimental results on real and simulated data.