针对高维数据在采集、传输和存储过程中易出现条目缺失的问题,本文研究基于Tucker秩的张量补全问题。为减弱核范数松弛对较大奇异值的过度惩罚,并提高凸差模型的求解效率,本文在邻近凸差算法框架下提出一种惯性Bregman邻近凸差算法。该算法引入惯性外推策略,并以Bregman距离诱导的邻近项替代传统Frobenius范数邻近项,从而更灵活地刻画张量补全问题的结构信息。理论方面,在适当的水平集紧性假设和Kurdyka-Łojasiewicz性质下,证明了算法生成序列的收敛性,并说明其极限点为相应优化模型的稳定点。脑MRI图像恢复实验表明,与邻近凸差算法相比,所提算法具有更高的恢复精度;与高精度低秩张量补全算法相比,所提算法在计算时间上具有优势。
This paper studies the tensor completion problem based on Tucker rank for high-dimensional data whose entries are prone to missing during acquisition, transmission, and storage. To alleviate the over-penalization of large singular values caused by nuclear norm relaxation and improve the solution efficiency of the difference-of-convex model, an inertial Bregman proximal difference-of-convex algorithm is proposed within the proximal difference-of-convex algorithm framework. The proposed algorithm introduces an inertial extrapolation strategy and replaces the traditional Frobenius norm proximal term with a Bregman-distance-induced proximal term, thereby characterizing the structural information of tensor completion problems more flexibly. On the theoretical side, under a suitable compactness assumption on the level set and the Kurdyka-Łojasiewicz property, the convergence of the sequence generated by the algorithm is proved, and its limit points are shown to be stationary points of the corresponding optimization model. Experiments on brain MRI image recovery show that, compared with the proximal difference-of-convex algorithm, the proposed algorithm achieves higher recovery accuracy; compared with the high-accuracy low-rank tensor completion algorithm, the proposed algorithm has an advantage in computation time.
[1] Goldfarb D, Qin Z. Robust low-rank tensor recovery: models and algorithms [J]. SIAM Journal on Matrix Analysis and Applications, 2014, 35(1): 225-253.
[2] Coupier D, Desolneux A, Ycart B. Image denoising by statistical area thresholding [J]. Journal of Mathematical Imaging and Vision, 2005, 22(2): 183-197.
[3] Criminisi A, Pérez P, Toyama K. Region filling and object removal by exemplar-based image inpainting [J]. IEEE Transactions on Image Processing, 2004, 13(9): 1200-1212.
[4] Selvaraju R R, Cogswell M, Das A, et al. Grad-CAM: visual explanations from deep networks via gradient-based localization [C]//Proceedings of the IEEE International Conference on Computer Vision, 2017: 618-626.
[5] Komodakis N. Image completion using global optimization [C]//2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2006, 1: 442-452.
[6] Bengua J A, Phien H N, Tuan H D, et al. Efficient tensor completion for color image and video recovery: low-rank tensor train [J]. IEEE Transactions on Image Processing, 2017, 26(5): 2466-2479.
[7] Liu J, Musialski P, Wonka P, et al. Tensor completion for estimating missing values in visual data [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2012, 35(1): 208- 220.
[8] Gandy S, Recht B, Yamada I. Tensor completion and low-n-rank tensor recovery via convex optimization [J]. Inverse Problems, 2011, 27(2): 025010.
[9] Kolda T G, Bader B W. Tensor decompositions and applications [J]. SIAM Review, 2009, 51(3): 455-500.
[10] Filipovi M, Juki A. Tucker factorization with missing data with application to low-n-rank tensor completion [J]. Multidimensional Systems and Signal Processing, 2015, 26(3): 677-692.
[11] Yokota T, Zhao Q, Cichocki A. Smooth PARAFAC decomposition for tensor completion [J]. IEEE Transactions on Signal Processing, 2016, 64(20): 5423-5436.
[12] Lu C, Feng J, Chen Y, et al. Tensor robust principal component analysis with a new tensor nuclear norm [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2019, 42(4): 925-938.
[13] Oseledets I V. Tensor-train decomposition [J]. SIAM Journal on Scientific Computing, 2011, 33(5): 2295-2317.
[14] Wang W, Aggarwal V, Aeron S. Efficient low rank tensor ring completion [C]//Proceedings of the IEEE International Conference on Computer Vision, 2017: 5697-5705.
[15] Wang C L, Nan J K, Yan X H. Tensor completion via L*-LF optimization model [J/OL]. Journal of the Operations Research Society of China, 2025-06-21, https://doi.org/10.1007/s40305-025-00600-4.
[16] Tao P D, An L T H. Convex analysis approach to DC programming: theory, algorithms and applications [J]. Acta Mathematica Vietnamica, 1997, 22(1): 289-355.
[17] An L T H, Tao P D. The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems [J]. Annals of Operations Research, 2005, 133(1): 23-46.
[18] Souza J C O, Oliveira P R, Soubeyran A. Global convergence of a proximal linearized algorithm for difference of convex functions [J]. Optimization Letters, 2016, 10(7): 1529-1539.
[19] Takahashi S, Fukuda M, Tanaka M. New Bregman proximal type algorithms for solving DC optimization problems [J]. Computational Optimization and Applications, 2022, 83(3): 893- 931.
[20] De Oliveira W, Tcheou M P. An inertial algorithm for DC programming [J]. Set-Valued and Variational Analysis, 2019, 27(4): 895-919.
[21] Gao X, Cai X, Wang X, et al. An alternating structure-adapted Bregman proximal gradient descent algorithm for constrained nonconvex nonsmooth optimization problems and its inertial variant [J]. Journal of Global Optimization, 2023, 87(1): 277-300.
[22] Ma S, Goldfarb D, Chen L. Fixed point and Bregman iterative methods for matrix rank minimization [J]. Mathematical Programming, 2011, 128(1): 321-353.
[23] Bregman L M. The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming [J]. USSR Computational Mathematics and Mathematical Physics, 1967, 7(3): 200-217.
[24] Li H. Singular value decomposition [M]//Li H. (ed.) Machine learning methods, Singapore: Springer Nature, 2023: 311-336.
[25] Brinkhuis J. Convex analysis for optimization: a unified approach [M]. Cham: Springer, 2020.
[26] Bolte J, Sabach S, Teboulle M. Proximal alternating linearized minimization for nonconvex and nonsmooth problems [J]. Mathematical Programming, 2014, 146(1): 459-494.
[27] 刘浩洋, 户将, 李勇锋, 等. 最优化: 建模、算法与理论 [M]. 北京: 高等教育出版社, 2020.
[28] Yan L, Shin Y, Xiu D. Sparse approximation using L1- L2 minimization and its application to stochastic collocation [J]. SIAM Journal on Scientific Computing, 2017, 39(1): A229-A254.
[29] Mukkamala M C, Ochs P. Beyond alternating updates for matrix factorization with inertial Bregman proximal gradient algorithms [J]. Advances in Neural Information Processing Systems, 2019, 32: 4268-4278.
[30] Li G, Pong T K. Calculus of the exponent of Kurdyka- Lojasiewicz inequality and its applications to linear convergence of first-order methods [J]. Foundations of Computational Mathematics, 2018, 18(5): 1199-1232.
北大中文核心期刊