低秩张量填充的加速随机临近梯度算法

doi:10.12286/jssx.j2021-0809

计算数学 ›› 2022, Vol. 44 ›› Issue (4): 534-544.DOI: 10.12286/jssx.j2021-0809

低秩张量填充的加速随机临近梯度算法

郭雄伟, 王川龙

工程科学计算山西省高等学校重点实验室(太原师范学院), 晋中 030619

收稿日期:2021-05-10 出版日期:2022-11-14 发布日期:2022-11-08
通讯作者: 王川龙,Email:clwang1964@163.com.
基金资助:
国家自然科学基金（11371275），山西省自然科学基金（201601D011004），山西省研究生教育创新项目（2021Y713）和太原师范学院研究生教育创新项目（SYYJSJC-2164）资助.

PDF ( 167 ) 引用

郭雄伟, 王川龙. 低秩张量填充的加速随机临近梯度算法[J]. 计算数学, 2022, 44(4): 534-544.

Guo Xiongwei, Wang Chuanlong. AN ACCELERATED STOCHASTIC PROXIMAL GRADIENT ALGORITHM FOR LOW RANK TENSOR COMPLETION[J]. Mathematica Numerica Sinica, 2022, 44(4): 534-544.

AN ACCELERATED STOCHASTIC PROXIMAL GRADIENT ALGORITHM FOR LOW RANK TENSOR COMPLETION

Guo Xiongwei, Wang Chuanlong

Key Laboratory of Engineering and Computational Science (Taiyuan Normal University), Shanxi Province Department of Education, Jinzhong 030619, China

Received:2021-05-10 Online:2022-11-14 Published:2022-11-08

本文提出了一种求解低秩张量填充问题的加速随机临近梯度算法.张量填充模型可以松弛为平均组合形式的无约束优化问题,在迭代过程中,随机选取该组合中的某一函数进行变量更新,有效减少了张量展开、矩阵折叠及奇异值分解带来的较大的计算花费.本文证明了算法的收敛率为$O (1/k^{2})$.最后,随机生成的和真实的张量填充实验结果表明新算法在CPU时间上优于现有的三种算法.

关键词： 张量填充, 加速临近梯度算法

In this paper, an accelerated stochastic proximal gradient algorithm is proposed for low rank tensor completion problem. The tensor completion model is relaxed into an unconstrained optimization problem in the form of average combination. In the iterative process, a function of this combination is randomly selected for variable update, which effectively reduces the large calculation cost caused by tensor unfolding, matrix folding, and singular value decomposition. We prove that the convergence rate of this algorithm is $O(1/k^{2})$. Finally, numerical results on randomly generated and real tensor completion problems demonstrate new algorithm is better than three existing algorithms in CPU time.

Key words: tensor completion, accelerated proximal gradient algorithm

MR(2010)主题分类:

分享此文:

[1] Bertalmio M, Sapiro G, Caselles V, et al. Image Inpainting[C]. SIGGRAPH conference. 2000.
[2] MøRup M. Applications of tensor (multiway array) factorizations and decompositions in data mining[J]. Wiley Interdisciplinary Reviews:Data Mining and Knowledge Discovery, 2011, 1(1):24-40.
[3] Signoretto M, Raf V, Moor B D, et al. Tensor Versus Matrix Completion:A Comparison With Application to Spectral Data[J]. IEEE Signal Processing Letters, 2011, 18(7):403-406.
[4] Comon P. Tensor Decompositions, State of the Art and Applications[J]. IMA Conf. Mathematics in Singal Processing, arXiv:0905.0454, 2009.
[5] Tucker L. Some mathematical notes on three-mode factor analysis[J]. Psychometrika, 1966, 31(3):279-311.
[6] Kiers H. Towards a Standardized Notation and Terminology in Multiway Analysis[J]. Journal of Chemometrics, 2000, 14(3):105-122.
[7] Hitchcock F L. The Expression of a Tensor or a Polyadic as a Sum of Products[J]. Journal of Mathematical Physics, 1927, 6(1):164-189.
[8] Liu J, Musialski P, Wonka P, et al. Tensor completion for estimating missing values in visual data[C]. IEEE Trans Pattern Anal Mach Intell(35), 2013, 1:208-220.
[9] Gandy S, Recht B, Yamada I. Tensor completion and low-n-rank tensor recovery via convex optimization[J]. Inverse Problems, 2011, 27(2):025010.
[10] Signoretto M, Dinh Q T, Lathauwer L D, et al. Learning with tensors:a framework based on convex optimization and spectral regularization[J]. Machine Learning, 2014, 94(3):303-351.
[11] Ji T, Huang T, Zhao X, et al. A non-convex tensor rank approximation for tensor completion-ScienceDirect[J]. Applied Mathematical Modelling, 2017, 48:410-422.
[12] Kasai H, Mishra B. Low-rank tensor completion:a Riemannian manifold preconditioning approach[J]. Proceedings of the 33rd international conference on machine learning, 2016, 48:1012-1021.
[13] Friedland S, Lim L-H. Nuclear norm of higher-order tensors[J]. Mathematics of computation, 2018, 87(311):1255-1281.
[14] Liu Y, Long Z, Huang H, et al. Low CP Rank and Tucker Rank Tensor Completion for Estimating Missing Components in Image Data[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2020, 30(4):944-954.
[15] Zhao Q, Zhang L, Cichocki A. Bayesian CP Factorization of Incomplete Tensors with Automatic Rank Determination[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2015, 37(9):1751-1763.
[16] Golub G H, Van Loan C F. Matrix computations 4th Edition. Johns Hopkins Studies in Mathematical Sciences, 2009.
[17] Cai J F, Candè E J, Shen Z. A Singular Value Thresholding algorithm for Matrix Completion[J]. SIAM Journal on Optimization, 2010, 20(4):1956-1982.
[18] Beck A, Teboulle M. A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems[J]. Siam J Imaging Sciences, 2009, 2(1):183-202.

No related articles found!

阅读次数

全文

摘要

低秩张量填充的加速随机临近梯度算法

AN ACCELERATED STOCHASTIC PROXIMAL GRADIENT ALGORITHM FOR LOW RANK TENSOR COMPLETION

扫码分享