A Barzilai-Borwein gradient algorithm for spatio-temporal internet traffic data completion via tensor triple decomposition. (English) Zbl 1528.68041
Summary: With the coming of high-speed network and 5G era, internet traffic data is crucial for various network tasks such as traffic engineering, capacity planning and anomaly detection. To explore the natural spatio-temporal structure of network flow, we use the novel triple decomposition of tensors to establish an optimization model with the spatio-temporal regularization for completing the internet traffic data. A Barzilai-Borwein gradient algorithm is designed for solving the spatio-temporal internet traffic tensor completion problem. We prove the convergence of this algorithm and analyze its convergence rate with the tool of the Kurdyka-Łojasiewicz property. Numerical experiments on Abilene and GÉANT datasets report that the proposed tensor completion method is effective.
MSC:
| 68M11 | Internet topics |
| 15A69 | Multilinear algebra, tensor calculus |
| 90C90 | Applications of mathematical programming |
Keywords:
Internet traffic tensor; tensor completion; triple tensor decomposition; optimization algorithmReferences:
| [1] | Acar, E.; Dunlavy, DM; Kolda, TG; Mørup, M., Scalable tensor factorizations for incomplete data, Chemometr. Intell. Lab. Syst., 106, 41-56 (2011) · doi:10.1016/j.chemolab.2010.08.004 |
| [2] | Attouch, H.; Bolte, J., On the convergence of the proximal algorithm for nonsmooth functions involving analytic features, Math. Program., 116, 5-16 (2009) · Zbl 1165.90018 · doi:10.1007/s10107-007-0133-5 |
| [3] | Attouch, H.; Bolte, J.; Redont, P.; Soubeyran, A., Proximal alternating minimization and projection methods for nonconvex problems: An approach based on the Kurdyka-Łojasiewicz inequality, Math. Oper. Res., 35, 438-457 (2010) · Zbl 1214.65036 · doi:10.1287/moor.1100.0449 |
| [4] | Barzilai, J.; Borwein, JM, Two-point step size gradient methods, IMA J. Numer. Anal., 8, 141-148 (1988) · Zbl 0638.65055 · doi:10.1093/imanum/8.1.141 |
| [5] | Bolte, J.; Daniilidis, A.; Lewis, A., The Łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems, SIAM J. Optim., 17, 1205-1223 (2007) · Zbl 1129.26012 · doi:10.1137/050644641 |
| [6] | Candès, EJ; Recht, B., Exact matrix completion via convex optimization, Found. Comput. Math., 9, 717-772 (2009) · Zbl 1219.90124 · doi:10.1007/s10208-009-9045-5 |
| [7] | Chen, C.; Li, X.; Ng, M.; Yuan, X., Total variation based tensor decomposition for multi-dimensional data with time dimension, Numer. Linear Algebra Appl., 22, 999-1019 (2015) · Zbl 1349.65141 · doi:10.1002/nla.1993 |
| [8] | Chen, X.; He, Z.; Sun, L., A Bayesian tensor decomposition approach for spatiotemporal traffic data imputation, Transp. Res. Part C: Emerg. Technol., 98, 73-84 (2019) · doi:10.1016/j.trc.2018.11.003 |
| [9] | Chen, X.; He, Z.; Wang, J., Spatial-temporal traffic speed patterns discovery and incomplete data recovery via SVD-combined tensor decomposition, Transp. Res. Part C: Emerg. Technol., 86, 59-77 (2018) · doi:10.1016/j.trc.2017.10.023 |
| [10] | Chen, X.; Yang, J.; Sun, L., A nonconvex low-rank tensor completion model for spatiotemporal traffic data imputation, Transp. Res. Part C: Emerg. Technol., 117, 102673 (2020) · doi:10.1016/j.trc.2020.102673 |
| [11] | De Lathauwer, L., Decompositions of a higher-order tensor in block terms-Part I: lemmas for partitioned matrices, SIAM J. Matrix Anal. Appl., 30, 1022-1032 (2008) · Zbl 1177.15031 · doi:10.1137/060661685 |
| [12] | De Lathauwer, L., Decompositions of a higher-order tensor in block terms-Part II: definitions and uniqueness, SIAM J. Matrix Anal. Appl., 30, 1033-1066 (2008) · Zbl 1177.15032 · doi:10.1137/070690729 |
| [13] | De Lathauwer, L.; Nion, D., Decompositions of a higher-order tensor in block terms-Part III: alternating least squares algorithms, SIAM J. Matrix Anal. Appl., 30, 1067-1083 (2008) · Zbl 1177.15033 · doi:10.1137/070690730 |
| [14] | de Goulart, JDM; Kibangou, AY; Favier, G., Traffic data imputation via tensor completion based on soft thresholding of Tucker core, Transp. Res. Part C: Emerg. Technol., 85, 348-362 (2017) · doi:10.1016/j.trc.2017.09.011 |
| [15] | De Silva, V.; Lim, L-H, Tensor rank and the ill-posedness of the best low-rank approximation problem, SIAM J. Matrix Anal. Appl., 30, 1084-1127 (2008) · Zbl 1167.14038 · doi:10.1137/06066518X |
| [16] | Gunnar, A., Johansson, M., Telkamp, T.: “Traffic matrix estimation on a large IP backbone: A comparison on real data”, in Proc. 4th ACM SIGCOMM Conf. Internet Meas. (2004) 149-160 |
| [17] | “Introduction to Cisco IOS NetFlow - A Technical Overview”, (2012) |
| [18] | Jiang, B.; Yang, F.; Zhang, S., Tensor and its tucker core: The invariance relationships, Num. Linear Algebra Appl., 24, e2086 (2017) · Zbl 1424.15047 · doi:10.1002/nla.2086 |
| [19] | Jiang, Q., Ng, M.: “Robust low-tubal-rank tensor completion via convex optimization”, Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19) (2019) 2649-2655 |
| [20] | Kolda, TG; Bader, B., Tensor decompositions and applications, SIAM Rev., 51, 455-500 (2009) · Zbl 1173.65029 · doi:10.1137/07070111X |
| [21] | Liu, J.; Musialski, P.; Wonka, P.; Ye, J., Tensor completion for estimating missing values in visual data, IEEE Trans. Pattern Anal. Mach. Intell., 35, 208-220 (2013) · doi:10.1109/TPAMI.2012.39 |
| [22] | Majumdar, A.: Matrix Completion via Thresholding, MATLAB Central File Exchange. Retrieved March 28, 2020 |
| [23] | Medina, A.; Taft, N.; Salamatian, K.; Bhattacharyya, S.; Diot, C., Traffic matrix estimation: Existing techniques and new directions, ACM SIGCOMM Comput. Commun. Rev., 32, 161-174 (2002) · doi:10.1145/964725.633041 |
| [24] | Qi, L.; Chen, Y.; Bakshi, M.; Zhang, X., Triple decomposition and tensor recovery of third order tensors, SIAM J. Matrix Anal. Appl., 42, 299-329 (2021) · Zbl 1467.15020 · doi:10.1137/20M1323266 |
| [25] | Roughan, M.; Zhang, Y.; Willinger, W.; Qiu, L., Spatio-temporal compressive sensing and internet traffic matrices (extended version), IEEE/ACM Trans. Network., 20, 662-676 (2012) · doi:10.1109/TNET.2011.2169424 |
| [26] | Sidiropoulos, ND; De Lathauwer, L.; Fu, X.; Huang, K.; Papalexakis, EE; Faloutsos, C., Tensor decomposition for signal processing and machine learning, IEEE Trans. Signal Process., 65, 3551-3582 (2017) · Zbl 1415.94232 · doi:10.1109/TSP.2017.2690524 |
| [27] | Tootoonchian, A., Ghobadi, M., Ganjali, Y.: “OpenTM: Traffic matrix estimator for OpenFlow networks”. in Proc. Int. Conf. Passive Active Netw. Meas. (2010) 201-210 |
| [28] | Tune, P., Roughan, M.: “Internet traffic matrices: a primer”, in ACM SIGCOMM eBook: Recent Advances in Networking, (2013) |
| [29] | Uhlig, S.; Quoitin, B.; Lepropre, J.; Balon, S., Providing public intradomain traffic matrices to the research community, ACM SIGCOMM Computer Commun. Rev., 36, 1, 83-86 (2006) · doi:10.1145/1111322.1111341 |
| [30] | Vardi, Y., Network tomography: Estimating source-destination traffic intensities from link data, J. Am. Stat. Assoc., 91, 365-377 (1996) · Zbl 0871.62103 · doi:10.1080/01621459.1996.10476697 |
| [31] | Wang, L.; Xie, K.; Semong, T.; Zhou, H., Missing data recovery based on tensor-CUR decomposition, IEEE Access, 6, 532-544 (2017) · doi:10.1109/ACCESS.2017.2770146 |
| [32] | Xie, K.; Peng, C.; Wang, X.; Xie, G.; Wen, J.; Cao, J.; Zhang, D.; Qin, Z., Accurate recovery of internet traffic data under variable rate measurements, IEEE/ACM Trans. Network., 26, 1137-1150 (2018) · doi:10.1109/TNET.2018.2819504 |
| [33] | Xie, K., Wang, L., Wang, X., Xie, G., Wen, J., Zhang, G.: “Accurate recovery of internet traffic data: A tensor completion approach”, IEEE INFOCOM 2016 - The 35th Annual IEEE International Conference on Computer Communications (2016) |
| [34] | Xie, K.; Wang, L.; Wang, X.; Xie, G.; Wen, J.; Zhang, G.; Cao, J.; Zhang, D., Accurate recovery of internet traffic data: a sequential tensor completion approach, IEEE/ACM Trans. Network., 26, 793-806 (2018) · doi:10.1109/TNET.2018.2797094 |
| [35] | Xu, Y.; Yin, W., A block coordinate method for regularized multiconvex optimization with applications to nonnegatove tensor factorizatn and completion, SIAM J. Imaging Sci., 6, 1758-1789 (2013) · Zbl 1280.49042 · doi:10.1137/120887795 |
| [36] | Xu, Y.; Hao, R.; Yin, W.; Su, Z., Parallel matrix factorization for low-rank tensor completion, Inverse Problems Imaging, 9, 601-624 (2015) · Zbl 1359.15021 · doi:10.3934/ipi.2015.9.601 |
| [37] | Zhang, Y.; Roughan, M.; Duffield, N.; Greenberg, A., Fast accurate computation of large-scale IP traffic matrices from link loads, ACM SIGMETRICS Perform. Eval. Rev., 31, 206-217 (2003) · doi:10.1145/885651.781053 |
| [38] | Zhang, Z., Ely, G., Aeron, S., Hao, N., Kilmer, M.: “Novel methods for multilinear data completion and de-noising based on tensor-SVD”, 2014 IEEE Conference on Computer Vision and Pattern Recognition, Columbus, OH, 2014, pp. 3842-3849 |
| [39] | Zhou, H., Zhang, D., Xie, K., Chen, Y.: “Spatio-temporal tensor completion for imputing missing internet traffic data”, in Proc. IEEE 34th Int. Perform Comput. Commun. Conf. (2015) 1-7 |
| [40] | Zhou, H., Zhang, D., Xie, K., Chen, Y.: “Robust spatio-temporal tensor recovery for internet traffic data”, in 2016 IEEE Trustcom/BigDataSE/ISPA (2016) 1404-1411 |
| [41] | Zhou, P.; Lu, C.; Lin, Z.; Zhang, C., Tensor factorization for low-rank tensor completion, IEEE Trans. Image Process., 27, 1152-1163 (2018) · Zbl 1409.94796 · doi:10.1109/TIP.2017.2762595 |
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.
