Fusion Subspace Clustering: Full and Incomplete Data
This addresses the problem of subspace clustering with missing data for machine learning and data analysis applications, offering a novel and efficient solution that overcomes key limitations of prior methods.
The paper tackles subspace clustering for both complete and incomplete data by introducing a fusion penalty-based algorithm that avoids lifting and handles noise, low to full-rank data, and approaches optimal sampling rates. Experiments show it matches state-of-the-art performance with complete data and significantly outperforms existing methods when data is missing.
Modern inference and learning often hinge on identifying low-dimensional structures that approximate large scale data. Subspace clustering achieves this through a union of linear subspaces. However, in contemporary applications data is increasingly often incomplete, rendering standard (full-data) methods inapplicable. On the other hand, existing incomplete-data methods present major drawbacks, like lifting an already high-dimensional problem, or requiring a super polynomial number of samples. Motivated by this, we introduce a new subspace clustering algorithm inspired by fusion penalties. The main idea is to permanently assign each datum to a subspace of its own, and minimize the distance between the subspaces of all data, so that subspaces of the same cluster get fused together. Our approach is entirely new to both, full and missing data, and unlike other methods, it directly allows noise, it requires no liftings, it allows low, high, and even full-rank data, it approaches optimal (information-theoretic) sampling rates, and it does not rely on other methods such as low-rank matrix completion to handle missing data. Furthermore, our extensive experiments on both real and synthetic data show that our approach performs comparably to the state-of-the-art with complete data, and dramatically better if data is missing.