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

A Randomized Singular Value Decomposition for Third-Order Oriented Tensors

  • Published:
Journal of Optimization Theory and Applications Aims and scope Submit manuscript

Abstract

The oriented singular value decomposition (O-SVD) proposed by Zeng and Ng provides a hybrid approach to the t-product-based third-order tensor singular value decomposition with the transformation matrix being a factor matrix of the higher-order singular value decomposition. Continuing along this vein, this paper explores realizing the O-SVD efficiently by drawing a connection to the tensor-train rank-1 decomposition and gives a truncated O-SVD. Motivated by the success of probabilistic algorithms, we develop a randomized version of the O-SVD and present its detailed error analysis. The new algorithm has advantages in efficiency while keeping good accuracy compared with the current tensor decompositions. Our claims are supported by numerical experiments on several oriented tensors from real applications.

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

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

Notes

  1. https://v.qq.com/x/page/v3237ztwzs7.html.

References

  1. Bader, B.W., Kolda, T.G.: Matlab Tensor Toolbox, version 3.2.1 (2017). https://www.tensortoolbox.org

  2. Batselier, K., Liu, H., Wong, N.: A constructive algorithm for decomposing a tensor into a finite sum of orthonormal rank-1 terms. SIAM J. Matrix Anal. Appl. 36, 1315–1337 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  3. Brand, M.: Fast low-rank modifications of the thin singular value decomposition. Linear Algebra Appl. 415, 20–30 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  4. Carroll, J.D., Chang, J.J.: Analysis of individual differences in multidimensional scaling via an N-way generalization of “Eckart-Young” decomposition. Psychometrika 35, 283–319 (1970)

  5. Che, M., Chen, J., Wei, Y.: Perturbations of the TCUR decomposition for tensor valued data in the Tucker format. J. Optim. Theory Appl. 194, 852–877 (2022)

    Article  MathSciNet  MATH  Google Scholar 

  6. Che, M., Wei, Y.: Randomized algorithms for the approximations of Tucker and the tensor train decompositions. Adv. Comput. Math. 45, 395–428 (2019)

    Article  MathSciNet  MATH  Google Scholar 

  7. Che, M., Wei, Y., Yan, H.: The computation of low multilinear rank approximations of tensors via power scheme and random projection. SIAM J. Matrix Anal. Appl. 41, 605–636 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  8. Che, M., Wei, Y., Yan, H.: An efficient randomized algorithm for computing the approximate Tucker decomposition. J. Sci. Comput. 88, 32 (2021)

    Article  MathSciNet  MATH  Google Scholar 

  9. Che, M., Wei, Y., Yan, H.: Randomized algorithms for the low multilinear rank approximations of tensors. J. Comput. Appl. Math. 390, 113380 (2021)

    Article  MathSciNet  MATH  Google Scholar 

  10. Cichocki, A., Mandic, D., De Lathauwer, L., Zhou, G., Zhao, Q., Caiafa, C., Phan, H.A.: Tensor decompositions for signal processing applications: from two-way to multiway component analysis. IEEE Signal Process Mag. 32, 145–163 (2015)

    Article  Google Scholar 

  11. De Lathauwer, L., De Moor, B., Vandewalle, J.: A multilinear singular value decomposition. SIAM J. Matrix Anal. Appl. 21, 1253–1278 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  12. Drineas, P., Mahoney, M.W.: RandNLA: randomized numerical linear algebra. Commun. ACM 59, 80–90 (2016)

    Article  Google Scholar 

  13. Eckart, C., Young, G.: The approximation of one matrix by another of lower rank. Psychometrika 1, 211–218 (1936)

    Article  MATH  Google Scholar 

  14. Eisavi, V.: Hyperspectral remote sensing scenes—gic php (2017). http://www.ehu.eus/ccwintco/index.php?title=Hyperspectral_Remote_Sensing_Scenes

  15. Halko, N., Martinsson, P.G., Tropp, J.A.: Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions. SIAM Rev. 53, 217–288 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  16. Harshman, R.A.: Foundations of the PARAFAC procedure: models and conditions for an “explanatory’’ multi-mode factor analysis. UCLA Work. Pap. Phonetics 16, 1–84 (1969)

    Google Scholar 

  17. Horn, R.A., Johnson, C.R.: Matrix Analysis, 2nd edn. Cambridge University Press, Cambridge (2013)

    MATH  Google Scholar 

  18. Jacod, J., Protter, P.: Probability Essentials. Springer, Berlin (2012)

    MATH  Google Scholar 

  19. 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, 148–172 (2013)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  22. Kolda, T.G., Bader, B.W., Kenny, J.P.: Higher-order web link analysis using multilinear algebra. In: Proceedings of the 5th IEEE International Conference on Data Mining, ICDM ’05, USA. IEEE Computer Society, pp. 242—249 (2005)

  23. Lu, C.: Tensor-tensor product toolbox (2018). https://github.com/canyilu/tproduct

  24. Mahoney, M.W.: Randomized algorithms for matrices and data. Found. Trends Mach. Learn. 3, 123–224 (2011)

    MATH  Google Scholar 

  25. Martinsson, P.-G., Rokhlin, V., Tygert, M.: A randomized algorithm for the decomposition of matrices. Appl. Comput. Harmon. Anal. 30, 47–68 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  26. Minster, R., Saibaba, A.K., Kilmer, M.E.: Randomized algorithms for low-rank tensor decompositions in the Tucker format. SIAM J. Math. Data Sci. 2, 189–215 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  27. Oseledets, I.V.: Tensor-train decomposition. SIAM J. Sci. Comput. 33, 2295–2317 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  28. Qi, L., Chen, H., Chen, Y.: Tensor Eigenvalues and Their Applications. Advances in Mechanics and Mathematics, vol. 39. Springer, Singapore (2018)

    Google Scholar 

  29. Qi, L., Luo, Z.: Tensor Analysis: Spectral Theory and Special Tensors. Society for Industrial and Applied Mathematics, Philadelphia (2017)

    Book  MATH  Google Scholar 

  30. Rokhlin, V., Szlam, A., Tygert, M.: A randomized algorithm for principal component analysis. SIAM J. Matrix Anal. Appl. 31, 1100–1124 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  31. Saibaba, A.K.: Randomized subspace iteration: analysis of canonical angles and unitarily invariant norms. SIAM J. Matrix Anal. Appl. 40, 23–48 (2019)

    Article  MathSciNet  MATH  Google Scholar 

  32. Shabat, G., Shmueli, Y., Aizenbud, Y., Averbuch, A.: Randomized LU decomposition. Appl. Comput. Harmon. Anal. 44, 246–272 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  33. Signoretto, M., Tran Dinh, Q., De Lathauwer, L., Suykens, J.A.K.: Learning with tensors: a framework based on convex optimization and spectral regularization. Mach. Learn. 94, 303–351 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  34. Sorber, L., Van Barel, M., De Lathauwer, L.: Optimization-based algorithms for tensor decompositions: canonical polyadic decomposition, decomposition in rank-\(({L}_{r},{L}_{r},1)\) terms, and a new generalization. SIAM J. Optimiz. 23, 695–720 (2013)

    Article  MATH  Google Scholar 

  35. Tucker, L.R.: Some mathematical notes on three-mode factor analysis. Psychometrika 31, 279–311 (1966)

    Article  MathSciNet  Google Scholar 

  36. Vannieuwenhoven, N., Vandebril, R., Meerbergen, K.: A new truncation strategy for the higher-order singular value decomposition. SIAM J. Sci. Comput. 34, A1027–A1052 (2012)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  Google Scholar 

  38. Wei, Y., Xie, P., Zhang, L.: Tikhonov regularization and randomized GSVD. SIAM J. Matrix Anal. Appl. 37, 649–675 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  39. Xie, P., Xiang, H., Wei, Y.: Randomized algorithms for total least squares problems. Numer. Linear Algebra Appl. 26, e2219 (2019)

    Article  MathSciNet  MATH  Google Scholar 

  40. Zeng, C., Ng, M.K.: Decompositions of third-order tensors: HOSVD, T-SVD, and beyond. Numer. Linear Algebra Appl. 27, e2290 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  41. Zhang, J., Saibaba, A.K., Kilmer, M.E., Aeron, S.: A randomized tensor singular value decomposition based on the t-product. Numer. Linear Algebra Appl. 25, e2179 (2018)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

We would like to acknowledge the handling editor and three anonymous referees for their useful comments and constructive suggestions which helped considerably to improve the quality of the paper. This work is supported by the National Natural Science Foundation of China (Nos. 12271108, 11801534), the Innovation Program of Shanghai Municipal Education Committee and the Fundamental Research Funds for the Central Universities (No. 202264006).

Author information

Authors and Affiliations

  1. School of Mathematical Sciences, Ocean University of China, Qingdao, 266100, People’s Republic of China

    Minghui Ding & Pengpeng Xie

  2. School of Mathematical Sciences and and Key Laboratory of Mathematics for Nonlinear Sciences, Fudan University, Shanghai, 200433, People’s Republic of China

    Yimin Wei

Authors
  1. Minghui Ding
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yimin Wei
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Pengpeng Xie
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Pengpeng Xie.

Additional information

Communicated by Liqun Qi.

Publisher's Note

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

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

Ding, M., Wei, Y. & Xie, P. A Randomized Singular Value Decomposition for Third-Order Oriented Tensors. J Optim Theory Appl 197, 358–382 (2023). https://doi.org/10.1007/s10957-023-02177-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10957-023-02177-5

Keywords

Mathematics Subject Classification

Search

Navigation