Top

BIT Numerical Mathematics

Published in:

10-05-2018

On the spectral problem for trivariate functions

Authors: Behnam Hashemi, Yuji Nakatsukasa

Published in: BIT Numerical Mathematics | Issue 4/2018

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Using a variational approach applied to generalized Rayleigh functionals, we extend the concepts of singular values and singular functions to trivariate functions defined on a rectangular parallelepiped. We also consider eigenvalues and eigenfunctions for trivariate functions whose domain is a cube. For a general finite-rank trivariate function, we describe an algorithm for computing the canonical polyadic (CP) decomposition, provided that the CP factors are linearly independent in two variables. All these notions are computed using Chebfun3; a part of Chebfun for numerical computing with 3D functions. Application in finding the best rank-1 approximation of trivariate functions is investigated. We also prove that if the function is analytic and two-way orthogonally decomposable (odeco), then the CP values decay geometrically, and optimal finite-rank approximants converge at the same rate.

previous article Energy behaviour of the Boris method for charged-particle dynamics

next article Stochastic discrete Hamiltonian variational integrators

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Unless in the exceptional case that the initial vectors correspond to a saddle point of (2.1) [25, Thm. 2].

Relative to a tolerance to which (2.10) holds; machine epsilon by default.

See e.g. [52] for an analogous discussion regarding eigenvalues of symmetric discrete tensors.

The singular quadruplets for odeco tensors is fully studied in [44], which shows that the number of singular values grows rapidly with both the dimension and size, and that the singular vector tuples form a positive-dimensional variety. Extending such results to the continuous case is an interesting open problem.

This is the function doublehelix from the Chebfun gallery.

Atkinson, K., Han, W.: Theoretical Numerical Analysis. Springer, New York (2005)CrossRef

Bebendorf, M.: Adaptive cross approximation of multivariate functions. Constr. Approx. 34(2), 149–179 (2011)MathSciNetCrossRef

Benson, A.R., Gleich, D.F., Lim, L.H.: The spacey random walk: a stochastic process for higher-order data. SIAM Rev. 59(2), 321–345 (2017)MathSciNetCrossRef

Beylkin, G., Mohlenkamp, M.J.: Numerical operator calculus in higher dimensions. Proc. Natl. Acad. Sci. 99(16), 10246–10251 (2002)MathSciNetCrossRef

Beylkin, G., Mohlenkamp, M.J.: Algorithms for numerical analysis in high dimensions. SIAM J. Sci. Comput. 26(6), 2133–2159 (2005)MathSciNetCrossRef

Blekherman, G., Teitler, Z.: On maximum, typical and generic ranks. Math. Ann. 362(3–4), 1021–1031 (2015)MathSciNetCrossRef

Bigoni, D., Engsig-Karup, A.P., Marzouk, Y.M.: Spectral tensor-train decomposition. SIAM J. Sci. Comput. 38(4), A2405–A2439 (2016)MathSciNetCrossRef

Chevreuil, M., Lebrun, R., Nouy, A., Rai, P.: A least-squares method for sparse low rank approximation of multivariate functions. SIAM/ASA J. Uncertain. Quantif. 3(1), 897–921 (2015)MathSciNetCrossRef

Courant, R., Hilbert, D.: Methods of Mathematical Physics, vol. 1. CUP Archive, Cambridge (1965)MATH

10.

De Lathauwer, L.: A link between the canonical decomposition in multilinear algebra and simultaneous matrix diagonalization. SIAM J. Matrix Anal. Appl. 28(3), 642–666 (2006). (electronic)MathSciNetCrossRef

11.

De Lathauwer, L., Comon, P., De Moor, B., Vandewalle, J.: Higher-order power method. In: Nonlinear Theory and its Applications, NOLTA95, vol. 1 (1995)

12.

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

13.

De Lathauwer, L., De Moor, B., Vandewalle, J.: Computation of the canonical decomposition by means of a simultaneous generalized Schur decomposition. SIAM J. Matrix Anal. Appl. 26(2), 295–327 (2004). (electronic)MathSciNetCrossRef

14.

Demmel, J.: Applied Numerical Linear Algebra. SIAM, Philadelphia (1997)CrossRef

15.

De Silva, V., Lim, L.-H.: Tensor rank and the ill-posedness of the best low-rank approximation problem. SIAM J. Matrix Anal. Appl. 30(3), 1084–1127 (2008)MathSciNetCrossRef

16.

Domanov, I., Lathauwer, L.D.: Canonical polyadic decomposition of third-order tensors: reduction to generalized eigenvalue decomposition. SIAM J. Matrix Anal. Appl. 35(2), 636–660 (2014)MathSciNetCrossRef

17.

Driscoll, T.A., Hale, N., Trefethen, L.N.: Chebfun Guide. Pafnuty Publications, Oxford (2014)

18.

Engel, E., Dreizler, R.M.: Density Functional Theory: An Advanced Course. Springer, New York (2011)CrossRef

19.

Falcó, A., Hackbusch, W.: On minimal subspaces in tensor representations. Found. Comput. Math. 12(6), 765–803 (2012)MathSciNetCrossRef

20.

Golub, G.H., Van Loan, C.F.: Matrix Computations. Johns Hopkins University Press, Baltimore (2013)MATH

21.

Gorodetsky, A.A., Karaman, S., Marzouk, Y.M.: Function-train: a continuous analogue of the tensor-train decomposition. arXiv:1510.09088v2 (2016)

22.

Hackbusch, W.: Tensor Spaces and Numerical Tensor Calculus, Springer Series in Computational Mathematics, vol. 42. Springer, Heidelberg (2012)CrossRef

23.

Hashemi, B., Trefethen, L.N.: Chebfun in three dimensions. SIAM J. Sci. Comput. 39(5), C341–363 (2017)MathSciNetCrossRef

24.

Hille, E., Tamarkin, J.D.: On the characteristic values of linear integral equations. Acta Math. 57(1), 1–76 (1931)MathSciNetCrossRef

25.

Kofidis, E., Regalia, P.A.: On the best rank-1 approximation of higher-order supersymmetric tensors. SIAM J. Matrix Anal. Appl. 23(3), 863–884 (2002)MathSciNetCrossRef

26.

Kolda, T.: Orthogonal tensor decompositions. SIAM J. Matrix Anal. Appl. 23(1), 243–255 (2001)MathSciNetCrossRef

27.

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

28.

Kolda, T.G., Mayo, J.R.: Shifted power method for computing tensor eigenpairs. SIAM J. Matrix Anal. Appl. 32(4), 1095–1124 (2011)MathSciNetCrossRef

29.

Kress, R.: Linear Integral Equations. Springer, Berlin (2014)CrossRef

30.

Kruskal, J.B.: Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics. Linear Algebra Appl. 18(2), 95–138 (1977)MathSciNetCrossRef

31.

Kruskal, J.B.: Rank, decomposition, and uniqueness for 3-way and n-way arrays. In: Coppi, R., Bolasco, S. (eds.) Multiway Data Analysis, pp. 7–18. North-Holland, New York (1989)

32.

Leurgans, S.E., Ross, R.T., Abel, R.B.: A decomposition for three-way arrays. SIAM J. Matrix Anal. Appl. 14(4), 1064–1083 (1993)MathSciNetCrossRef

33.

Li, W., Ng, M.K.: On the limiting probability distribution of a transition probability tensor. Linear Multilinear Algebra 62(3), 362–385 (2014)MathSciNetCrossRef

34.

Lickteig, T.: Typical tensorial rank. Linear Algebra Appl. 69, 95–120 (1985)MathSciNetCrossRef

35.

Lim, L.H.: Singular values and eigenvalues of tensors: a variational approach. In: Proceedings of the IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP ‘05), pp. 129–132 (2005)

36.

Little, G., Reade, J.: Eigenvalues of analytic kernels. SIAM J. Math. Anal. 15, 133–136 (1984)MathSciNetCrossRef

37.

Mercer, J.: Functions of positive and negative type and their connection with the theory of integral equations. Philos. Trans. R. Soc. Lond. A 209, 415–446 (1909)CrossRef

38.

Moler, Cleve B., Stewart, G.W.: An algorithm for generalized matrix eigenvalue problems. SIAM J. Numer. Anal. 10(2), 241–256 (1973)MathSciNetCrossRef

39.

Nakatsukasa, Y.: Finding a trivariate basis of rank-one functions. Chebfun example (2016). http://www.chebfun.org/examples/approx3/FindingRankOne.html

40.

Nakatsukasa, Y., Soma, T., Uschmajew, A.: Finding a low-rank basis in a matrix subspace. Math. Program. 162(1–2), 325–361 (2017)MathSciNetCrossRef

41.

Oseledets, I.V.: Constructive representation of functions in low-rank tensor formats. Constr. Approx. 37(1), 1–18 (2013)MathSciNetCrossRef

42.

Qi, L.: Eigenvalues of a real supersymmetric tensor. J. Symb. Comput. 40(6), 1302–1324 (2005)MathSciNetCrossRef

43.

Regalia, P.A., Kofidis, E.: The higher-order power method revisited: convergence proofs and effective initialization. In: Proceedings of the 2000 IEEE International Conference on Acoustics, Speech, and Signal. Processing (ICASSP ’00), vol. 5, pp. 2709–2712. IEEE (2000)

44.

Robeva, E., Seigal, A.: Singular vectors of orthogonally decomposable tensors. Linear Multilinear Algebra 65, 2457–2471 (2017)MathSciNetCrossRef

45.

Sanchez, E., Kowalski, B.R.: Tensorial resolution: a direct trilinear decomposition. J. Chemom. 4(1), 29–45 (1990)CrossRef

46.

Schmidt, E.: Zur Theorie der linearen und nichtlinearen Integralgleichungen. I Teil. Entwicklung willkuerlichen Funktionen nach System vorgeschriebener. Math. Ann. 63, 433–476 (1907)MathSciNetCrossRef

47.

Schultz, T., Seidel, H.P.: Estimating crossing fibers: a tensor decomposition approach. IEEE Trans. Vis. Comput. Graph. 14(6), 1635–1642 (2008)CrossRef

48.

Spatschek, R., Eidel, B.: Driving forces for interface kinetics and phase field models. Int. J. Solids Struct. 50(14), 2424–2436 (2013)CrossRef

49.

Stakgold, I., Holst, M.J.: Green’s Functions and Boundary Value Problems. John Wiley & Sons, Hoboken (2011)CrossRef

50.

Stewart, G.W.: On the early history of the singular value decomposition. SIAM Rev. 35(4), 551–566 (1993)MathSciNetCrossRef

51.

Strassen, V.: Rank and optimal computation of generic tensors. Linear Algebra Appl. 52, 645–685 (1983)MathSciNetCrossRef

52.

Sturmfels, B.: Tensors and their eigenvectors. Not. Am. Math. Soc. 63(6), 604–606 (2016)MathSciNetCrossRef

53.

Townsend, A.: Computing with functions in two dimensions. Ph.D. thesis, University of Oxford (2014)

54.

Townsend, A., Trefethen, L.N.: Continuous analogues of matrix factorizations. Proc. R. Soc. A 471(2173), 20140,585 (2015)MathSciNetCrossRef

55.

Trefethen, L.N.: Householder triangularization of a quasimatrix. IMA J. Numer. Anal. 30(4), 887–897 (2010)MathSciNetCrossRef

56.

Trefethen, L.N.: Approximation Theory and Approximation Practice. SIAM, Philadelphia (2013)MATH

57.

Uschmajew, A.: Regularity of tensor product approximations to square integrable functions. Constr. Approx. 34, 371–391 (2011)MathSciNetCrossRef

58.

Uschmajew, A.: A new convergence proof for the higher-order power method and generalizations. Pac. J. Optim. 11, 309–321 (2015)MathSciNetMATH

59.

van Groesen, E.: Applied analytical method. In: Lecture Notes for Applied Analysis & Mathematical Physics (2001)

60.

Vannieuwenhoven, N., Nicaise, J., Vandebril, R., Meerbergen, K.: On generic nonexistence of the Schmidt–Eckart–Young decomposition for complex tensors. SIAM J. Matrix Anal. Appl. 35(3), 886–903 (2014)MathSciNetCrossRef

61.

Zhang, T., Golub, G.H.: Rank-one approximation to high order tensors. SIAM J. Matrix Anal. Appl. 23(2), 534–550 (2001)MathSciNetCrossRef

Title: On the spectral problem for trivariate functions
Authors: Behnam Hashemi
Yuji Nakatsukasa
Publication date: 10-05-2018
Publisher: Springer Netherlands
Published in: BIT Numerical Mathematics / Issue 4/2018
Print ISSN: 0006-3835
Electronic ISSN: 1572-9125
DOI: https://doi.org/10.1007/s10543-018-0710-4

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Other articles of this Issue 4/2018

Weak convergence of Galerkin approximations for fractional elliptic stochastic PDEs with spatial white noise

Stochastic discrete Hamiltonian variational integrators

Asymptotic quadratic convergence of the parallel block-Jacobi EVD algorithm with dynamic ordering for Hermitian matrices

Multiple orthogonal polynomials applied to matrix function evaluation

On the zero-stability of multistep methods on smooth nonuniform grids

Energy behaviour of the Boris method for charged-particle dynamics

Premium Partner