An Accelerated Proximal Gradient Algorithm for Hankel Tensor Completion

doi:10.1007/s40305-022-00422-8

Abstract

Abstract: In this paper, an accelerated proximal gradient algorithm is proposed for Hankel tensor completion problems. In our method, the iterative completion tensors generated by the new algorithm keep Hankel structure based on projection on the Hankel tensor set. Moreover, due to the special properties of Hankel structure, using the fast singular value thresholding operator of the mode-s unfolding of a Hankel tensor can decrease the computational cost. Meanwhile, the convergence of the new algorithm is discussed under some reasonable conditions. Finally, the numerical experiments show the effectiveness of the proposed algorithm.

Key words: Hankel tensor, Tensor completion, Accelerated proximal gradient algorithm

CLC Number:

Chuan-Long Wang, Xiong-Wei Guo, Xi-Hong Yan. An Accelerated Proximal Gradient Algorithm for Hankel Tensor Completion[J]. Journal of the Operations Research Society of China, 2024, 12(2): 461-477.

TrendMD

References

[1] Bertalmio, M., Sapiro, G., Caselles, V., Ballester, C.:Image inpainting. In:SIGGRAPH Conference (2000)
[2] Morup, M.:Applications of tensor (multiway array) factorizations and decompositions in data mining. Wiley Interdiscip. Rev. Data Min. Knowl. Discov. 1(1), 24-40(2011)
[3] Comon, P.:Tensor decompositions, state of the art and applications. Stats. 1-24(2009)
[4] Signoretto, M., Van de Plas, R., De Moor, B., Suykens, J.A.K.:Tensor versus matrix completion:a comparison with application to spectral data. IEEE Signal Process. Lett. 18(7), 403-406(2011)
[5] Kolda, T.G., Bader, B.W., Kenny, J.P.:Higher-order web link analysis using multilinear algebra. In:Fifth IEEE International Conference on Data Mining, pp. 27-30(2005)
[6] Liu, J., Musialski, P., Wonka, P., Ye, J.:Tensor completion for estimating missing values in visual data. IEEE Trans. Pattern Anal. Mach. Intell. 35(1), 208-220(2013)
[7] Liu, J., Musialski, P., Wonka, P., Ye,J.:Tensor completion for estimating missing values in visual data. In:IEEE International Conference on Computer Vision, pp. 2114-2121(2009)
[8] Gandy, S., Recht, B., Yamada, I.:Tensor completion and low-n-rank tensor recovery via convex optimization. Inverse Prob. 27(2), 025010(2011)
[9] Tan, H., Feng, J., Li, F., Zhang, Y., Chen, T.:Low multilinear rank tensor completion with missing data. Energy Procedia 11, 201-209(2011)
[10] Xue, S., Qiu, W., Liu, F., Jin, X.:Low-rank tensor completion by trunncated nuclear norm regularization. In:24th International Conference on Pattern Recognition, pp. 2600-2605(2018)
[11] Zhang, Z., Aeron, S.:Exact tensor completion using t-SVD. IEEE Trans. Signal Process. 65(6), 1511-1526(2017)
[12] Zhang, Z., Ely, G., Aeron, S., Hao, N., Kilmer, M.:Novel methods for multilinear data completion and de-noising based on tensor-svd. In:2014 IEEE Conference on Computer Vision and Pattern Recognition, pp. 3842-3949(2014)
[13] Badeau, R., Boyer, R.:Fast multilinear singular value decomposition for structured tensors. Siam J. Matrix Anal. Appl. 30(3), 1008-1021(2008)
[14] Smith, R.S.:Frequency domain subspace identification using nuclear norm minimization and Hankel matrix realizations. IEEE Trans. Autom. Control 59(11), 2886-2896(2014)
[15] Vanhecke, S.V., Decannierep, C., Vanhuffel, S., Chen, H., Decabbiere, C.:Algorithm for time-domain NMR data fitting based on total least squares. J. Mag. Reson. Ser. A. 110(2), 228-237(1994)
[16] Ding, W., Qi, L., Wei, Y.:Fast Hankel tensor-vector product and its application to exponential data fitting. Numer. Linear Algebra Appl. 22(5), 814-832(2015)
[17] Qi, L.:Hankel tensors:associated Hankel matrices and Vandermonde decomposition. Communications in Mathematical Sciences (2015). https://doi.org/10.4310/CMS.2015.v13.n1.a6
[18] Xu, C.:Hankel tensors, Vandermonde tensors and their positivities. Linear Algebra Appl. 491, 56-72(2016)
[19] Chen, Y., Qi, L., Wang, Q.:Positive semi-definiteness and sum-of-squares property of fourth order four dimensional Hankel tensors. J. Comput. Appl. Math. 302, 356-368(2016)
[20] Ding, W., Qi, L., Wei, Y.:Inheritance properties and sum-of-squares decomposition of Hankel tensors:theory and algorithms. BIT Numer. Math. 57(1), 1-22(2016)
[21] Adamo, A., Mazzucchelli, P.:3D interpolation using Hankel tensor completion by orthogonal mathching pursuit. In:GNGTS (2014)
[22] Trickett, S., Burroughs, L.,Milton, A.:Interpolation using Hankel tensor completion.In:Seg Technical Program Expanded Abstracts, pp. 3634-3638(2013)
[23] Toh, C.K., Yun, S.:An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems. Pac. J. Optim. 6(3), 615-640(2010)
[24] Comon, P., Golub, G., Lim, L.H., Mourrain, B.:Symmetric tensors and symmetric tensor rank. Siam J. Matrix Anal. Appl. 30(3), 1254-1279(2008)
[25] Nie, J., Ye, K.:Hankel tensor decompositions and ranks. SIAM J. Matrix Anal. Appl. 40(2), 486-516(2019)
[26] Golub, G.H., VanLoan, C.F.:Matrix Computations. The Johns Hopkins University Press, Baltimore (1996)
[27] Cai, J.F., Candès, E.J., Shenm, Z.:A singular value thresholding algorithm for matrix completion. SIAM J. Optim. 20(4), 1956-1982(2010)
[28] Beck, A., Teboulle, M.:A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imag. Sci. 2(1), 183-202(2009)