Fusion regularized clustering has gained considerable attention for its ability to perform clustering without prior knowledge of the number of clusters. However, its performance deteriorates in high-dimensional settings due to redundant or noisy features. To address this issue, we propose a novel group sparsity-based fusion regularized clustering model, termed GSFRC, which enables both accurate clustering and informative feature selection. Specifically, GSFRC introduces a bi-level group sparsity regularizer that integrates an inter-group sparsity term ($ l_{2, p} $-norm) and an intra-group sparsity term ($ l_q $-norm) to capture both global and local feature structures, where the parameters $ p $ and $ q $ are chosen from the interval $ [0, 1) $. In theory, we establish the necessary Karush–Kuhn–Tucker (KKT) optimality conditions for the resulting nonconvex and non-Lipschitz optimization problem. In the algorithm, we develop an efficient scheme based on the alternating direction method of multipliers (ADMM), and we provide a rigorous global convergence analysis under mild conditions. Extensive experiments demonstrate that the proposed method achieves superior clustering accuracy, stronger feature selection capability, and higher robustness compared with existing fusion regularized clustering approaches.
Citation: Xiangru Xing, Lingchen Kong, Xin Wang, Xianchao Xiu. Group sparsity-based fusion regularized clustering: New model and convergent algorithm[J]. Journal of Industrial and Management Optimization, 2026, 22(1): 44-69. doi: 10.3934/jimo.2026003
Fusion regularized clustering has gained considerable attention for its ability to perform clustering without prior knowledge of the number of clusters. However, its performance deteriorates in high-dimensional settings due to redundant or noisy features. To address this issue, we propose a novel group sparsity-based fusion regularized clustering model, termed GSFRC, which enables both accurate clustering and informative feature selection. Specifically, GSFRC introduces a bi-level group sparsity regularizer that integrates an inter-group sparsity term ($ l_{2, p} $-norm) and an intra-group sparsity term ($ l_q $-norm) to capture both global and local feature structures, where the parameters $ p $ and $ q $ are chosen from the interval $ [0, 1) $. In theory, we establish the necessary Karush–Kuhn–Tucker (KKT) optimality conditions for the resulting nonconvex and non-Lipschitz optimization problem. In the algorithm, we develop an efficient scheme based on the alternating direction method of multipliers (ADMM), and we provide a rigorous global convergence analysis under mild conditions. Extensive experiments demonstrate that the proposed method achieves superior clustering accuracy, stronger feature selection capability, and higher robustness compared with existing fusion regularized clustering approaches.
| [1] |
L. Ling, Y. Gu, S. Zhang, J. Wen, A generalized $K$-means problem for clustering and an ADMM-based $K$-means algorithm, J. Ind. Manag. Optim., 20 (2024), 2089–2115. https://doi.org/10.3934/jimo.2023157 doi: 10.3934/jimo.2023157
|
| [2] |
L. Gao, J. Bien, D. Witten, Selective inference for hierarchical clustering, J. Am. Stat. Assoc., 119 (2024), 332–342. https://doi.org/10.1080/01621459.2022.2116331 doi: 10.1080/01621459.2022.2116331
|
| [3] |
L. Ding, C. Li, D. Jin, S. Ding, Survey of spectral clustering based on graph theory, Pattern Recogn., 151 (2024), 110366. https://doi.org/10.1016/j.patcog.2024.110366 doi: 10.1016/j.patcog.2024.110366
|
| [4] |
Y. Zhu, X. Xiu, W. Liu, C. Yin, Joint sparse subspace clustering via fast $l_{2, 0}$-norm constrained optimization, Expert Syst. Appl., 265 (2025), 125845. https://doi.org/10.1016/j.eswa.2024.125845 doi: 10.1016/j.eswa.2024.125845
|
| [5] | M. Wang, G. I. Allen, Integrative generalized convex clustering optimization and feature selection for mixed multi-view data, J. Mach. Learn. Res., 22 (2021), 2498–2571. |
| [6] | Z. Wang, Y. Yuan, J. Ma, T. Zeng, D. Sun, Randomly projected convex clustering model: Motivation, realization, and cluster recovery guarantees, J. Mach. Learn. Res., 26 (2025), 1–57. |
| [7] |
Q. Feng, C. Chen, L. Liu, A review of convex clustering from multiple perspectives: Models, optimizations, statistical properties, applications, and connections, IEEE Trans. Neural Netw. Learn. Syst., 35 (2024), 13122–13142. https://doi.org/10.1109/TNNLS.2023.3276393 doi: 10.1109/TNNLS.2023.3276393
|
| [8] | K. Pelckmans, J. De Brabanter, J. A. Suykens, B. D. Moor, Convex clustering shrinkage, in PASCAL Workshop on Statistics and Optimization of Clustering Workshop, 2005. |
| [9] | F. Lindsten, H. Ohlsson, L. Ljung, Clustering using sum-of-norms regularization: With application to particle filter output computation, in 2011 IEEE Statistical Signal Processing Workshop (SSP), 2011, 201–204. https://doi.org/10.1109/SSP.2011.5967659 |
| [10] | T. D. Hocking, A. Joulin, F. Bach, J. P. Vert, Clusterpath an algorithm for clustering using convex fusion penalties, in Proc. Int. Conf. Mach. Learn., 2011. |
| [11] |
Z. Wang, X. Liu, Q. Li, A euclidean distance matrix model for convex clustering, J. Optim. Theory Appl., 205 (2025), 1. https://doi.org/10.1007/s10957-025-02616-5 doi: 10.1007/s10957-025-02616-5
|
| [12] | D. Sun, K. C. Toh, Y. Yuan, Convex clustering: Model, theoretical guarantee and efficient algorithm, J. Mach. Learn. Res., 22 (2021), 427–458. |
| [13] | M. Lin, Y. Zhang, Low rank convex clustering for matrix-valued observations, arXiv preprint arXiv: 2412.17328. |
| [14] |
H. Chen, L. Kong, Y. Li, A novel convex clustering method for high-dimensional data using semiproximal ADMM, Math. Probl. Eng., 2020 (2020), 1–12. https://doi.org/10.1155/2020/9216351 doi: 10.1155/2020/9216351
|
| [15] |
Y. Yuan, M. Lin, D. Sun, K. C. Toh, Adaptive sieving: A dimension reduction technique for sparse optimization problems, Math. Program. Comput., 17 (2025), 585–616. https://doi.org/10.1007/s12532-025-00282-2 doi: 10.1007/s12532-025-00282-2
|
| [16] | B. Wang, Y. Zhang, W. Sun, Y. Fang, Sparse convex clustering, J. Comput. Graph. Stat., 27 (2018), 393–403. https://doi.org/10.1080/10618600.2017.1377081 |
| [17] | T. Hastie, R. Tibshirani, M. Wainwright, Statistical learning with sparsity: The lasso and generalizations, 1 Eds., New York: CRC Press, 2015. https://doi.org/10.1201/b18401 |
| [18] |
A. Parekh, I. W. Selesnick, Improved sparse low-rank matrix estimation, Signal Process., 139 (2017), 62–69. https://doi.org/10.1016/j.sigpro.2017.04.011 doi: 10.1016/j.sigpro.2017.04.011
|
| [19] |
Y. Zhu, X. Zhang, G. Wen, W. He, D. Cheng, Double sparse-representation feature selection algorithm for classification, Multimed. Tools Appl., 76 (2017), 17525–17539. https://doi.org/10.1007/s11042-016-4121-8 doi: 10.1007/s11042-016-4121-8
|
| [20] | X. Xiu, C. Huang, P. Shang, W. Liu, Bi-sparse unsupervised feature selection, IEEE Trans. Image Process., (2025), 1–15. https://doi.org/10.1109/TIP.2025.3620667 |
| [21] |
Y. Hu, J. X. Liu, Y. L. Gao, J. Shang, DSTPCA: Double-sparse constrained tensor principal component analysis method for feature selection, IEEE/ACM Trans. Comput. Biol. Bioinform., 18 (2021), 1481–1491. https://doi.org/10.1109/TCBB.2019.2943459 doi: 10.1109/TCBB.2019.2943459
|
| [22] |
Y. Xu, G. Liu, X. Lu, C. Xie, L. Xue, T. Jiang, Double sparse structure-enhanced mmWave NLOS imaging under multiangle relay surface, IEEE Trans. Signal Process., 72 (2024), 5628–5643. https://doi.org/10.1109/TSP.2024.3505938 doi: 10.1109/TSP.2024.3505938
|
| [23] |
S. Liao, C. Han, T. Guo, B. Li, Subspace Newton method for sparse group $l_0$ optimization problem, J. Global Optim., 90 (2024), 93–125. https://doi.org/10.1007/s10898-024-01396-y doi: 10.1007/s10898-024-01396-y
|
| [24] |
J. Huang, J. L. Horowitz, S. Ma, Asymptotic properties of bridge estimators in sparse high-dimensional regression models, Ann. Stat., 36 (2008), 587–613. https://doi.org/10.1214/009053607000000875 doi: 10.1214/009053607000000875
|
| [25] |
R. Chartrand, Exact reconstruction of sparse signals via nonconvex minimization, IEEE Signal Process. Lett., 14 (2007), 707–710. https://doi.org/10.1109/LSP.2007.898300 doi: 10.1109/LSP.2007.898300
|
| [26] |
L. Niu, R. Zhou, Y. Tian, Z. Qi, P. Zhang, Nonsmooth penalized clustering via $l_p$ regularized sparse regression, IEEE Trans. Cybern., 47 (2016), 1423–1433. https://doi.org/10.1109/TCYB.2016.2546965 doi: 10.1109/TCYB.2016.2546965
|
| [27] |
H. Chen, L. Kong, Y. Li, Nonconvex clustering via $l_0$ fusion penalized regression, Pattern Recogn., 128 (2022), 108689. https://doi.org/10.1016/j.patcog.2022.108689 doi: 10.1016/j.patcog.2022.108689
|
| [28] |
X. Gao, Y. Bai, Smoothed hybrid $l_p$-$l_2$ model for sparse optimization, J. Ind. Manag. Optim., 21 (2025), 4712–4729. https://doi.org/10.3934/jimo.2025071 doi: 10.3934/jimo.2025071
|
| [29] |
J. Bolte, S. Sabach, M. Teboulle, Proximal alternating linearized minimization for nonconvex and nonsmooth problems, Math. Program., 146 (2014), 459–494. https://doi.org/10.1007/s10107-013-0701-9 doi: 10.1007/s10107-013-0701-9
|
| [30] |
K. Guo, D. Han, T. T. Wu, Convergence of alternating direction method for minimizing sum of two nonconvex functions with linear constraints, Int. J. Comput. Math., 94 (2017), 1653–1669. https://doi.org/10.1080/00207160.2016.1227432 doi: 10.1080/00207160.2016.1227432
|
| [31] |
H. Zhang, J. Gao, J. Qian, J. Yang, C. Xu, B. Zhang, Linear regression problem relaxations solved by nonconvex ADMM with convergence analysis, IEEE Trans. Circuits Syst. Video Technol., 34 (2024), 828–838. https://doi.org/10.1109/TCSVT.2023.3291821 doi: 10.1109/TCSVT.2023.3291821
|
| [32] | A. Beck, First-order methods in optimization, SIAM, 2017. https://doi.org/10.1137/1.9781611974997 |
| [33] | S. Zhou, X. Xiu, Y. Wang, D. Peng, Revisiting $l_q$ ($0 \le q < 1$) norm regularized optimization, arXiv preprint arXiv: 2306.14394 |
| [34] |
J. Liu, M. Feng, X. Xiu, W. Liu, X. Zeng, Efficient and robust sparse linear discriminant analysis for data classification, IEEE Trans. Emerg. Top. Comput. Intell., 9 (2024), 617–629. https://doi.org/10.1109/TETCI.2024.3403912 doi: 10.1109/TETCI.2024.3403912
|
| [35] | R. T. Rockafellar, R. J. B. Wets, Variational analysis, Springer Science & Business Media, 2009. https://doi.org/10.1007/978-3-642-02431-3 |
| [36] |
C. Chen, B. He, Y. Ye, X. Yuan, The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent, Math. Program., 155 (2016), 57–79. https://doi.org/10.1007/s10107-014-0826-5 doi: 10.1007/s10107-014-0826-5
|
| [37] |
S. Zhou, G. Y. Li, Federated learning via inexact ADMM, IEEE Trans. Pattern Anal. Mach. Intell., 45 (2023), 9699–9708. https://doi.org/10.1109/TPAMI.2023.3243080 doi: 10.1109/TPAMI.2023.3243080
|
| [38] | T. T. Cui, Y. Z. Dang, Y. Gao, Distributed multi-block partially symmetric Bregman ADMM for nonconvex and nonsmooth sharing problem, J. Oper. Res. Soc. China, (2025), 1–27. https://doi.org/10.1007/s40305-024-00579-4 |
| [39] |
M. Chao, Z. Deng, J. Jian, Convergence of linear Bregman ADMM for nonconvex and nonsmooth problems with nonseparable structure, Complexity, 2020 (2020), 6237942. https://doi.org/10.1155/2020/6237942 doi: 10.1155/2020/6237942
|
| [40] |
J. Yin, C. Tang, J. Jian, Q. Huang, A partial Bregman ADMM with a general relaxation factor for structured nonconvex and nonsmooth optimization, J. Global Optim., 89 (2024), 899–926. https://doi.org/10.1007/s10898-024-01384-2 doi: 10.1007/s10898-024-01384-2
|
| [41] |
H. Attouch, J. Bolte, B. F. Svaiter, Convergence of descent methods for semi-algebraic and tame problems: Proximal algorithms, forward–backward splitting, and regularized Gauss–Seidel methods, Math. Program., 137 (2013), 91–129. https://doi.org/10.1007/s10107-011-0484-9 doi: 10.1007/s10107-011-0484-9
|
| [42] |
F. Yang, Z. Xu, H. Wang, L. Sun, M. Zhai, J. Zhang, A hybrid feature selection algorithm combining information gain and grouping particle swarm optimization for cancer diagnosis, PLoS One, 19 (2024), e0290332. https://doi.org/10.1371/journal.pone.0290332 doi: 10.1371/journal.pone.0290332
|
| [43] |
H. Chen, L. Kong, W. Qu, X. Xiu, An enhanced regularized clustering method with adaptive spurious connection detection, IEEE Signal Process. Lett., 30 (2023), 1332–1336. https://doi.org/10.1109/LSP.2023.3316023 doi: 10.1109/LSP.2023.3316023
|
| [44] |
K. Zhan, F. Nie, J. Wang, Y. Yang, Multiview consensus graph clustering, IEEE Trans. Image Process., 28 (2018), 1261–1270. https://doi.org/10.1109/TIP.2018.2877335 doi: 10.1109/TIP.2018.2877335
|
| [45] |
S. G. Fang, D. Huang, C. D. Wang, Y. Tang, Joint multi-view unsupervised feature selection and graph learning, IEEE Trans. Emerg. Top. Comput. Intell., 8 (2024), 16–31. https://doi.org/10.1109/TETCI.2023.3306233 doi: 10.1109/TETCI.2023.3306233
|
| [46] |
P. Zhang, X. Liu, J. Xiong, S. Zhou, W. Zhao, E. Zhu, et al., Consensus one-step multi-view subspace clustering, IEEE Trans. Knowl. Data Eng., 34 (2022), 4676–4689. https://doi.org/10.1109/TKDE.2020.3045770 doi: 10.1109/TKDE.2020.3045770
|
 jimo-22-01-003-s001.pdf |
 |
Figures(7) / Tables(5)
Xiangru Xing, Lingchen Kong, Xin Wang, Xianchao Xiu. Group sparsity-based fusion regularized clustering: New model and convergent algorithm[J]. Journal of Industrial and Management Optimization, 2026, 22(1): 44-69. doi: 10.3934/jimo.2026003
DownLoad: