Sparse least squares solutions of multilinear equations. (English) Zbl 07855982
Summary: In this paper, we propose a sparse least squares (SLS) optimization model for solving multilinear equations, in which the sparsity constraint on the solutions can effectively reduce storage and computation costs. By employing variational properties of the sparsity set, along with differentiation properties of the objective function in the SLS model, the first-order optimality conditions are analysed in terms of the stationary points. Based on the equivalent characterization of the stationary points, we propose the Newton Hard-Threshold Pursuit (NHTP) algorithm and establish its locally quadratic convergence under some regularity conditions. Numerical experiments conducted on simulated datasets including cases of Completely Positive(CP)-tensors and symmetric strong M-tensors illustrate the efficiency of our proposed NHTP method.
MSC:
| 90C46 | Optimality conditions and duality in mathematical programming |
| 90C26 | Nonconvex programming, global optimization |
Keywords:
sparse least squares; multilinear equations; Newton hard-thresholding pursuit; completely positive tensor; symmetric strong M-tensorReferences:
| [1] | Yan, J, Xu, Y, Huang, Z.A homotopy method for solving multilinear systems with strong completely positive tensors. Appl Math Lett. 2022;124:Article ID 107636. · Zbl 1489.65063 |
| [2] | Ding, W, Wei, Y.Solving multi-linear systems with M-tensors. J Sci Comput. 2016;68(2):689-715. · Zbl 1371.65032 |
| [3] | Han, L.A homotopy method for solving multilinear systems with M-tensors. Appl Math Lett. 2017;69:49-54. · Zbl 1375.65060 |
| [4] | Li, D, Xie, S, Xu, H.Splitting methods for tensor equations. Numer Linear Algebra Appl. 2017;24(5):Article ID e2102. · Zbl 1463.65049 |
| [5] | Xie, Z, Jin, X, Wei, Y.Tensor methods for solving symmetric M-tensor systems. J Sci Comput. 2018;74(1):412-425. · Zbl 1392.65080 |
| [6] | Cui, L, Li, M, Song, Y.Preconditioned tensor splitting iterations method for solving multi-linear systems. Appl Math Lett. 2019;96:89-94. · Zbl 1503.65066 |
| [7] | Xie, Z, Jin, X, Wei, Y.A fast algorithm for solving circulant tensor systems. Linear Multilinear Algebra. 2016;65(9):1894-1904. · Zbl 1370.15027 |
| [8] | Li, X, Ng, MK.Solving sparse non-negative tensor equations: algorithms and applications. Front Math China. 2015;10(3):649-680. · Zbl 1323.65027 |
| [9] | Liang, M, Dai, L.Alternating minimization methods for solving multilinear systems. Math Probl Eng. 2021;2021:1-13. · Zbl 1512.90221 |
| [10] | Li, Z, Dai, Y, Gao, H.Alternating projection method for a class of tensor equations. J Comput Appl Math. 2019;346:490-504. · Zbl 1451.65051 |
| [11] | Beik, FP, Najafi-Kalyani, M.A preconditioning technique in conjunction with Krylov subspace methods for solving multilinear systems. Appl Math Lett. 2021;116:Article ID 107051. · Zbl 1469.65070 |
| [12] | Luo, Z, Qi, L, Xiu, N.The sparsest solutions to Z-tensor complementarity problems. Optim Lett. 2017;11(3):471-482. · Zbl 1394.90540 |
| [13] | Nikolova, M.Description of the minimizers of least squares regularized with \(l_0 \) -norm. Uniqueness of the global minimizer. SIAM J Imaging Sci. 2013;6(2):904-937. · Zbl 1281.65092 |
| [14] | Shen, X, Pan, W, Zhu, Y, et al. On constrained and regularized high-dimensional regression. Ann Inst Statist Math. 2013;65(5):807-832. · Zbl 1329.62307 |
| [15] | Bertsimas, D, Shioda, R.Algorithm for cardinality-constrained quadratic optimization. Comput Optim Appl. 2009;43(1):1-22. · Zbl 1178.90262 |
| [16] | Gotoh, JY, Takeda, A, Tono, K.DC formulations and algorithms for sparse optimization problems. Math Program. 2017;169(1):141-176. · Zbl 06869181 |
| [17] | Needell, D, Tropp, JA.CoSaMP: iterative signal recovery from incomplete and inaccurate samples. Appl Comput Harmon Anal. 2009;26(3):301-321. · Zbl 1163.94003 |
| [18] | Beck, A, Eldar, YC.Sparsity constrained nonlinear optimization: optimality conditions and algorithms. SIAM J Optim. 2013;23(3):1480-1509. · Zbl 1295.90051 |
| [19] | Kyrillidis, A, Cevher, V. Recipes on hard thresholding methods. In: Proceedings of the 4th IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing. IEEE; 2011. p. 353-356. · Zbl 1311.90141 |
| [20] | Blumensath, T, Davies, ME.Normalized iterative hard thresholding: guaranteed stability and performance. IEEE J-STSP. 2010;4(2):298-309. |
| [21] | Blumensath, T.Accelerated iterative hard thresholding. Signal Process. 2012;92(3):752-756. |
| [22] | Foucart, S.Hard thresholding pursuit: an algorithm for compressive sensing. SIAM J Numer Anal. 2011;49(6):2543-2563. · Zbl 1242.65060 |
| [23] | Yuan, X, Li, P, Zhang, T.Gradient hard thresholding pursuit. J Mach Learn Res. 2018;18:1-43. · Zbl 1471.90114 |
| [24] | Bahmani, S, Raj, B, Boufounos, PT.Greedy sparsity-constrained optimization. J Mach Learn Res. 2013;14:807-841. · Zbl 1320.90046 |
| [25] | Zhou, S, Xiu, N, Qi, H.Global and quadratic convergence of Newton Hard-Thresholding Pursuit. J Mach Learn Res. 2021;22(12):1-45. · Zbl 1539.65071 |
| [26] | Qi, L.Eigenvalues of a real supersymmetric tensor. J Symb Comput. 2005;40(6):1302-1324. · Zbl 1125.15014 |
| [27] | Yang, Y, Yang, Q.Further results for Perron-Frobenius theorem for nonnegative tensors. SIAM J Matrix Anal Appl. 2010;31(5):2517-2530. · Zbl 1227.15014 |
| [28] | Zhao, C, Xiu, N, Qi, H, et al. A Lagrange-Newton algorithm for sparse nonlinear programming. Math Program. 2022;195:903-928. · Zbl 1504.90164 |
| [29] | Sun, D, Toh, K-C, Yuan, Y.Convex clustering: model, theoretical guarantee and efficient algorithm. J Mach Learn Res. 2021;22(9):1-32. · Zbl 1539.68281 |
| [30] | Zhou, S, Pan, L, Xiu, N, et al. Quadratic convergence of smoothing Newton’s method for 0/1 loss optimization. SIAM J Optim. 2021;31:3184-3211. · Zbl 1483.90126 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
