Machine learning and data science are undeniably among the mainstream areas of academic research in recent years in the field of electrical and information engineering. Within this realm, the mathematical performance analysis of algorithms is recognized as a challenging problem. Therefore, the vast majority of existing research results often rely on computer simulations or related empirical rules to verify the performance of algorithms, lacking rigorous mathematical theoretical foundations. This study focuses on algorithm development and deriving performance guarantees for an important issue in unsupervised learning---sparse subspace clustering.

Leveraging advancements of compressive sensing in the field of signal processing, we propose using the weighted L1-norm minimization algorithm for data clustering. By appropriately weighting data points, our proposed scheme effectively enhances the accuracy of subspace data clustering without increasing additional computational complexity, especially in scenarios where subspaces are close to each other. In addition to algorithm development, we further derive rigorous mathematical performance analysis. Unlike existing literature that is confined to mathematical sufficiency conditions for perfect data point identification, we begin with a more intuitive probabilistic perspective by directly introducing the correct identification rate of data points as a performance metric. This probabilistic approach faithfully reflects all possibilities of correct or misjudged data point events, providing a novel and more practical analytical criterion for performance guarantees in sparse subspace clustering, which is more aligned with real-world scenarios.  

▶ Jwo-Yuh Wu, Liang-Chi Huang, Ming-Hsun Yang, and Chun-Hung Liu, "Sparse subspace clustering via two-step reweighted L1-minimization: algorithm and provable neighbor recovery rates," in IEEE Trans. Information Theory, vol. 67, no. 2, pp. 1216-1263, Feb. 2021. (Link)
▶ Jwo-Yuh Wu, Liang-Chi Huang, Wen-Hsuan Li, Chun-Hung Liu, and Rung-Hung Gau, "Greedier is better: Selecting multiple neighbors per iteration for sparse subspace clustering," in Transactions on Machine Learning Research, 2023. (Link)