Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Riemannian conjugate gradient method for low-rank tensor completion

  • Published:
Advances in Computational Mathematics Aims and scope Submit manuscript

Abstract

Tensor completion aims to reconstruct a high-dimensional data from the partial element missing tensors under a low-rank constraint, which may be seen as a least-squares problem on manifold. In this paper, we propose a new Riemannian conjugate gradient method for the tensor completion which performs Riemannian optimization techniques on a fixed transformed multi-rank tensor manifold. More specifically, we generalize the classical Dai-Yuan conjugate gradient method from the Euclidean space to the manifold with fixed rank, and developed within the framework of retraction-based optimization on manifold. Finally, the convergence properties of the proposed algorithm are derived. Numerical experiments with synthetic data and real images demonstrate the feasibility and effectiveness of our approach.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Davenport, M.A., Romberg, J.: An overview of low-rank matrix recovery from incomplete observations. IEEE J. Sel. Top. Sig. Process. 10(4), 608–622 (2016)

    Article  Google Scholar 

  2. Wen, Z., Yin, W., Zhang, Y.: Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm. Math. Prog. Comput. 4(4), 333–361 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  3. 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 (2012)

    Article  Google Scholar 

  4. Gandy, S., Recht, B., Yamada, I.: Tensor completion and low-n-rank tensor recovery via convex optimization. Inverse Probl. 27(2), 025010 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  5. Ji, T., Huang, T., Zhao, X., Ma, T., Deng, L.: A non-convex tensor rank approximation for tensor completion. Appl. Math. Model. 48, 410–422 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  6. Gao, S., Fan, Q.: Robust schatten-p norm based approach for tensor completion. J. Sci. Comput. 82(1), 1–23 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  7. Shi, C., Huang, Z., Wan, L., Xiong, T.: Low-rank tensor completion based on log-det rank approximation and matrix factorization. J. Sci. Comput. 80(3), 1888–1912 (2019)

    Article  MathSciNet  MATH  Google Scholar 

  8. Xu, W., Zhao, X., Ji, T., Miao, J., Ma, T., Wang, S., Huang, T.: Laplace function based nonconvex surrogate for low-rank tensor completion. Sig. Process. Image Commun. 73, 62–69 (2019)

    Article  Google Scholar 

  9. Gu, S., Zhang, L., Zuo, W., Feng, X.: Weighted nuclear norm minimization with application to image denoising. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 2862–2869. IEEE, (2014)

  10. Xu, Y.., Hao, R.., Yin, W.., Su, Z..: Parallel matrix factorization for low-rank tensor completion. Inverse Probl. Imaging. 9(2), 601–624 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  11. Ji, T., Huang, T., Zhao, X., Ma, T., Liu, G.: Tensor completion using total variation and low-rank matrix factorization. Inf. Sci. 326, 243–257 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  12. Zhou, P., Lu, C., Lin, Z., Zhang, C.: Tensor factorization for low-rank tensor completion. IEEE Trans. Image Process. 27(3), 1152–1163 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  13. Lin, X., Ng, M.K., Zhao, X.: Tensor factorization with total variation and tikhonov regularization for low-rank tensor completion in imaging data. J. Math. Imaging Vis. 62(6), 900–918 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  14. He, B., Tao, M., Yuan, X.: Alternating direction method with gaussian back substitution for separable convex programming. SIAM J. Optim. 22(2), 313–340 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  15. Long, Z., Liu, Y., Chen, L., Zhu, C.: Low rank tensor completion for multiway visual data. Signal Process. 155, 301–316 (2019)

    Article  Google Scholar 

  16. Kilmer, M.E., Braman, K., Hao, N., Hoover, R.C.: Third-order tensors as operators on matrices: a theoretical and computational framework with applications in imaging. SIAM J. Matrix Anal. Appl. 34(1), 148–172 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  17. Kilmer, M.E., Martin, C.D., Perrone, L.: A third-order generalization of the matrix svd as a product of third-order tensors, Tufts University. Department of Computer Science, Tech. Rep. TR-2008-4

  18. Braman, K.: Third-order tensors as linear operators on a space of matrices. Linear Algebra Appl. 433(7), 1241–1253 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  19. Martin, C.D., Shafer, R., Larue, B.: An order-p tensor factorization with applications in imaging. SIAM J. Sci. Comput. 35(1), 474–490 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  20. Misha, E., Kilmer, C., Martin, D.: Factorization strategies for third-order tensors. Linear Algebra Appl. 435(3), 641–658 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  21. Uschmajew, A., Vandereycken, B.: The geometry of algorithms using hierarchical tensors. Linear Algebra Appl. 439(1), 133–166 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  22. Kressner, D., Steinlechner, M., Vandereycken, B.: Low-rank tensor completion by Riemannian optimization. BIT Numer Math. 54(2), 447–468 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  23. Vandereycken, B.: Low-rank matrix completion by Riemannian optimization. SIAM J. Optim. 23(2), 1214–1236 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  24. Steinlechner, M.: Riemannian optimization for high-dimensional tensor completion. SIAM J. Sci. Comput. 38(5), S461–S484 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  25. Song, G., Wang, X., Ng, M.K.: Riemannian conjugate gradient descent method for fixed multi rank third-order tensor completion. J. Comput. Appl. Math. 421, 114866 (2023)

  26. Heidel, G., Schulz, V.: A Riemannian trust-region method for low-rank tensor completion. Numer. Linear Algebra Appl. 25(6), e2175 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  27. Kolda, T.G., Bader, B.W.: Tensor decompositions and applications. SIAM Rev. 51(3), 455–500 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  28. Kernfeld, E.., Kilmer, M.., Aeron, S..: Tensor-tensor products with invertible linear transforms. Linear Algebra Appl. 485, 545–570 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  29. Xu, W. Zhao, X. Ng, M.: A fast algorithm for cosine transform based tensor singular value decomposition, arXiv:1902.03070

  30. Kilmer, M.E., Martin, C.D.: Factorization strategies for third-order tensors. Linear Algebra Appl. 435(3), 641–658 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  31. Zhang, Z., Aeron, S.: Exact tensor completion using t-svd. IEEE Trans. Signal Process. 65(6), 1511–1526 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  32. Absil, P.-A., Mahony, R., Sepulchre, R., Optimization algorithms on matrix manifolds, Princeton University Press, 2009

  33. Fletcher, R., Reeves, C.M.: Function minimization by conjugate gradients. Comput. J. 7(2), 149–154 (1964)

    Article  MathSciNet  MATH  Google Scholar 

  34. Polak, E.., Ribiere, G..: Note sur la convergence de méthodes de directions conjuguées. ESAIM Math. Model. Numer. Anal.-Modél. Math. Anal. Numér. 3(R1), 35–43 (1969)

    MATH  Google Scholar 

  35. Dai, Y., Yuan, Y.: A nonlinear conjugate gradient method with a strong global convergence property. SIAM J. Optim. 10(1), 177–182 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  36. Andrei, N.: Acceleration of conjugate gradient algorithms for unconstrained optimization. Appl. Math. Comput. 213(2), 361–369 (2009)

    MathSciNet  MATH  Google Scholar 

  37. Andrei, N.: New accelerated conjugate gradient algorithms as a modification of dai–yuan computational scheme for unconstrained optimization. J. Comput. Appl. Math. 234(12), 3397–3410 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  38. Ring, W., Wirth, B.: Optimization methods on Riemannian manifolds and their application to shape space. SIAM J. Optim. 22(2), 596–627 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  39. Sato, H., Iwai, T.: A new, globally convergent Riemannian conjugate gradient method. Optimization. 64(4), 1011–1031 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  40. Sato, H.: A dai-yuan-type Riemannian conjugate gradient method with the weak wolfe conditions. Comput. Optim. Appl. 64(1), 101–118 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  41. Wang, Z., Bovik, A.C., Sheikh, H.R., Simoncelli, E.P.: Image quality assessment: from error visibility to structural similarity. IEEE Trans. Image Process. 13(4), 600–612 (2004)

    Article  Google Scholar 

Download references

Acknowledgements

The authors thank the editor and the reviewers for the constructive and helpful comments on the revision of this article. The authors would like to thank Professor Guang-Jing Song, School of Mathematics and Information Sciences, Weifang University, for sending us the code, which led to an improvement of the paper.

Author information

Authors and Affiliations

  1. College of Mathematics and Computational Science, Guangxi Colleges and Universities Key Laboratory of Data Analysis and Computation, Guilin University of Electronic Technology, 541004, Guilin, People’s Republic of China

    Shan-Qi Duan, Xue-Feng Duan, Chun-Mei Li & Jiao-Fen Li

  2. Department of Mathematics, Shanghai University, 200444, Shanghai, People’s Republic of China

    Shan-Qi Duan

Authors
  1. Shan-Qi Duan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Xue-Feng Duan
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Chun-Mei Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Jiao-Fen Li
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Xue-Feng Duan.

Ethics declarations

Conflict of interest

The authors declare no competing interests.

Additional information

Communicated by: Ivan Oseledets

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

The work was supported by the National Natural Science Foundation of China (No.12201149, 12261026), the Natural Science Foundation of Guangxi Province (No.2022JJA110051) and the Innovation Project of GUET Graduate Education (No.2021YCXS113).

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Duan, SQ., Duan, XF., Li, CM. et al. Riemannian conjugate gradient method for low-rank tensor completion. Adv Comput Math 49, 41 (2023). https://doi.org/10.1007/s10444-023-10036-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s10444-023-10036-0

Keywords

Mathematics Subject Classification (2010)

Search

Navigation