Communications on Applied Mathematics and Computation >

2021 , Vol. 3 >Issue 2: 257 - 279

DOI: https://doi.org/10.1007/s42967-020-00090-6

ORIGINAL PAPER

MERACLE: Constructive Layer-Wise Conversion of a Tensor Train into a MERA

Expand
  • 1 Delft Center for Systems and Control, Delft University of Technology, Delft, the Netherlands;
    2 Skolkovo Institute of Science and Technology(SKOLTECH), 121205 Moscow, Russia;
    3 The Department of Electrical and Electronic Engineering, The University of Hong Kong, Hong Kong, China

Received date: 2019-12-20

  Revised date: 2020-07-17

  Online published: 2021-05-26

Supported by

This research was partially supported by the Ministry of Education and Science of the Russian Federation (grant 14.756.31.0001).

Fold

Abstract

In this article, two new algorithms are presented that convert a given data tensor train into either a Tucker decomposition with orthogonal matrix factors or a multi-scale entanglement renormalization ansatz (MERA). The Tucker core tensor is never explicitly computed but stored as a tensor train instead, resulting in both computationally and storage efcient algorithms. Both the multilinear Tucker-ranks as well as the MERA-ranks are automatically determined by the algorithm for a given upper bound on the relative approximation error. In addition, an iterative algorithm with low computational complexity based on solving an orthogonal Procrustes problem is proposed for the frst time to retrieve optimal rank-lowering disentangler tensors, which are a crucial component in the construction of a low-rank MERA. Numerical experiments demonstrate the efectiveness of the proposed algorithms together with the potential storage beneft of a low-rank MERA over a tensor train.

Key words： Tensors; Tensor train; Tucker decomposition; HOSVD; MERA; Disentangler

Cite this article

Kim Batselier, Andrzej Cichocki, Ngai Wong . MERACLE: Constructive Layer-Wise Conversion of a Tensor Train into a MERA[J]. Communications on Applied Mathematics and Computation, 2021 , 3(2) : 257 -279 . DOI: 10.1007/s42967-020-00090-6

References

1. Batselier, K. (Kim):Data to reproduce experiments in research article "meracle:constructive layer-wise conversion of a tensor train into a MERA" (2020). https://doi.org/10.4121/UUID:CB37D1B8-A505-46EB-8C42-FE819429624B. https://data.4tu.nl/repository/uuid:cb37d1b8-a505-46eb-8c42-fe819429624b
2. Carroll, J., Chang, J.J.:Analysis of individual diferences in multidimensional scaling via an n-way generalization of "Eckart-Young" decomposition. Psychometrika 35(3), 283-319 (1970)
3. Cichocki, A., Lee, N., Oseledets, I., Phan, A.H., Zhao, Q., Mandic, D.P.:Tensor networks for dimensionality reduction and large-scale optimization:part 1 low-rank tensor decompositions. Foundations and Trends? in Machine Learning 9(4/5), 249-429 (2016)
4. 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 Sig. Process. Mag. 32(2), 145-163 (2015)
5. Cichocki, A., Phan, A.H., Zhao, Q., Lee, N., Oseledets, I., Sugiyama, M., Mandic, D.P.:Tensor networks for dimensionality reduction and large-scale optimization:part 2 applications and future perspectives. Foundations and Trends? in Machine Learning 9(6), 431-673 (2017)
6. De Lathauwer, L., De Moor, B., Vandewalle, J.:A multilinear singular value decomposition. SIAM J. Matrix Anal. Appl. 21(4), 1253-1278 (2000)
7. Dolgov, S., Khoromskij, B.:Two-level QTT-Tucker format for optimized tensor calculus. SIAM J. Matrix Anal. Appl. 34(2), 593-623 (2013)
8. Espig, M., Hackbusch, W., Handschuh, S., Schneider, R.:Optimization problems in contracted tensor networks. Comput. Visualization Sci. 14(6), 271-285 (2011)
9. Espig, M., Naraparaju, K.K., Schneider, J.:A note on tensor chain approximation. Comput. Visualization Sci. 15(6), 331-344 (2012)
10. Evenbly, G., Vidal, G.:Algorithms for entanglement renormalization. Phys. Rev. B 79, 144108 (2009)
11. Golub, G.H., van Loan, C.F.:Matrix Computations, fourth edn. Johns Hopkins University Press (2013)
12. Grasedyck, L.:Hierarchical singular value decomposition of tensors. SIAM J. Matrix Anal. Appl. 31(4), 2029-2054 (2010)
13. Hackbusch, W., Kühn, S.:A new scheme for the tensor representation. J. Fourier Anal. Appl. 15(5), 706-722 (2009)
14. Halko, N., Martinsson, P.G., Tropp, J.A.:Finding structure with randomness:probabilistic algorithms for constructing approximate matrix decompositions. SIAM Rev. 53(2), 217-288 (2011)
15. Harshman, R.A.:Foundations of the PARAFAC procedure:models and conditions for an "explanatory" multi-modal factor analysis. UCLA Working Papers in Phonetics 16(1), 84 (1970)
16. Hitchcock, F.:The expression of a tensor or a polyadic as a sum of products. J. Math. Phys. 6, 164-189 (1927)
17. Holtz, S., Rohwedder, T., Schneider, R.:The alternating linear scheme for tensor optimization in the tensor train format. SIAM J. Sci. Comput. 34(2), A683-A713 (2012)
18. Khoromskij, B.N.:O(dlog N)-quantics approximation of N-d tensors in high-dimensional numerical modeling. Constructive Approx. 34(2), 257-280 (2011)
19. Kolda, T., Bader, B.:Tensor decompositions and applications. SIAM Rev. 51(3), 455-500 (2009)
20. Lehoucq, R.B., Sorensen, D.C.:Defation techniques for an implicitly restarted Arnoldi iteration. SIAM J. Matrix Anal. Appl. 17(4), 789-821 (1996)
21. Oseledets, I.:Tensor-train decomposition. SIAM J. Sci. Comput. 33(5), 2295-2317 (2011)
22. Oseledets, I., Tyrtyshnikov, E.:TT-cross approximation for multidimensional arrays. Linear Algebra Appl. 422(1), 70-88 (2010)
23. Rommer, S., Östlund, S.:Class of ansatz wave functions for one-dimensional spin systems and their relation to the density matrix renormalization group. Phys. Rev. B 55, 2164-2181 (1997)
24. Schollwöck, U.:The density-matrix renormalization group in the age of matrix product states. Annals of Physics 326(1), 96-192 (2011)
25. Shi, Y.Y., Duan, L.M., Vidal, G.:Classical simulation of quantum many-body systems with a tree tensor network. Phys. Rev. A 74(2), 022320 (2006)
26. Sidiropoulos, N.D., De Lathauwer, L., Fu, X., Huang, K., Papalexakis, E.E., Faloutsos, C.:Tensor decomposition for signal processing and machine learning. IEEE Trans. Sig. Process. 65(13), 3551-3582 (2017)
27. Tucker, L.R.:Some mathematical notes on three-mode factor analysis. Psychometrika 31(3), 279-311 (1966)
28. Vannieuwenhoven, N., Vandebril, R., Meerbergen, K.:A new truncation strategy for the higher-order singular value decomposition. SIAM J. Sci. Comput. 34(2), A1027-A1052 (2012)
29. Vervliet, N., Debals, O., Sorber, L., Van Barel, M., De Lathauwer, L.:Tensorlab 3.0 (2016). https://www.tensorlab.net.
30. Vidal, G.:A class of quantum many-body states that can be efciently simulated. Phys. Rev. Lett. 101, 110501 (2008)
Options
Outlines

/

〈 〉

Copyright © Editorial By Communications on Applied Mathematics and Computation
沪ICP备09014157