Top

Journal of Scientific Computing

Published in:

04-01-2016

Computing Extreme Eigenvalues of Large Scale Hankel Tensors

Authors: Yannan Chen, Liqun Qi, Qun Wang

Published in: Journal of Scientific Computing | Issue 2/2016

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

search-config

AI-assisted search

Off

Abstract

Large scale tensors, including large scale Hankel tensors, have many applications in science and engineering. In this paper, we propose an inexact curvilinear search optimization method to compute Z- and H-eigenvalues of mth order n dimensional Hankel tensors, where n is large. Owing to the fast Fourier transform, the computational cost of each iteration of the new method is about \(\mathcal {O}(mn\log (mn))\). Using the Cayley transform, we obtain an effective curvilinear search scheme. Then, we show that every limiting point of iterates generated by the new algorithm is an eigen-pair of Hankel tensors. Without the assumption of a second-order sufficient condition, we analyze the linear convergence rate of iterate sequence by the Kurdyka–Łojasiewicz property. Finally, numerical experiments for Hankel tensors, whose dimension may up to one million, are reported to show the efficiency of the proposed curvilinear search method.

previous article Solving Multi-linear Systems with -Tensors

next article A Novel Scheme for Liouville’s Equation with a Discontinuous Hamiltonian and Applications to Geometrical Optics

Dont have a licence yet? Then find out more about our products and how to get one 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

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

See “http://en.wikipedia.org/wiki/Cayley_transform”.

Attouch, H., Bolte, J.: On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Math. Program. Ser. B 116, 5–16 (2009)MathSciNetCrossRefMATH

Attouch, H., Bolte, J., Redont, P., Soubeyran, A.: Proximal alternating minimization and projection methods for nonconvex problems: an approach based on the Kurdyka–Łojasiewicz inequality. Math. Oper. Res. 35, 438–457 (2010)MathSciNetCrossRefMATH

Bader, B., Kolda, T.: Efficient MATLAB computations with sparse and factored tensors. SIAM J. Sci. Comput. 30, 205–231 (2007)MathSciNetCrossRefMATH

Barzilai, J., Borwein, J.M.: Two-point step size gradient methods. IMA J. Numer. Anal. 8, 141–148 (1988)MathSciNetCrossRefMATH

Bolte, J., Daniilidis, A., Lewis, A.: The Łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems. SIAM J. Optim. 17, 1205–1223 (2006)MathSciNetCrossRefMATH

Boyer, R., De Lathauwer, L., Abed-Meraim, K.: Higher order tensor-based method for delayed exponential fitting. IEEE Trans. Signal Process. 55, 2795–2809 (2007)MathSciNetCrossRef

Chang, K.C., Pearson, K., Zhang, T.: On eigenvalue problems of real symmetric tensors. J. Math. Anal. Appl. 350, 416–422 (2009)MathSciNetCrossRefMATH

Chen, L., Han, L., Zhou, L.: Computing tensor eigenvalues via homotopy methods, (2015). arXiv:1501.04201v3

Chen, Y., Dai, Y., Han, D., Sun, W.: Positive semidefinite generalized diffusion tensor imaging via quadratic semidefinite programming. SIAM J. Imaging Sci. 6, 1531–1552 (2013)MathSciNetCrossRefMATH

10.

Chen, Y., Qi, L., Wang, Q.: Positive semi-definiteness and sum-of-squares property of fourth order four dimensional Hankel tensors, (2015). arXiv:1502.04566v8

11.

Choi, J.H., Vishwanathan, S.V.N.: DFacTo: distributed factorization of tensors, (2014). arXiv:1406.4519v1

12.

Cichocki, A., Phan, A.-H.: Fast local algorithms for large scale nonnegative matrix and tensor factorizations. IEICE Trans. Fund. Electron. E92–A, 708–721 (2009)CrossRef

13.

Cooper, J., Dutle, A.: Spectra of uniform hypergraphs. Linear Algebra Appl. 436, 3268–3292 (2012)MathSciNetCrossRefMATH

14.

Cui, C., Dai, Y., Nie, J.: All real eigenvalues of symmetric tensors. SIAM J. Matrix Anal. Appl. 35, 1582–1601 (2014)MathSciNetCrossRefMATH

15.

Dai, Y.: A positive BB-like stepsize and an extension for symmetric linear systems, In: Workshop on Optimization for Modern Computation, Beijing, China, (2014), http://bicmr.pku.edu.cn/conference/opt-2014/slides/Yuhong-Dai

16.

de Almeida, A.L.F., Kibangou, A.Y.: Distributed large-scale tensor decomposition, In: IEEE International Conference on Acoustics, Speech and Siganl Processing (ICASSP) (2014) 26–30

17.

De Lathauwer, L., De Moor, B., Vandewalle, J.: On the best rank-\(1\) and rank-\((R_1, R_2,\ldots, R_N)\) approximation of higher-order tensors. SIAM J. Matrix Anal. Appl. 21, 1324–1342 (2000)MathSciNetCrossRefMATH

18.

Ding, W., Qi, L., Wei, Y.: Fast Hankel tensor-vector product and its application to exponential data fitting. Numer. Linear Algebra Appl. 22, 814–832 (2015)MathSciNetCrossRef

19.

Ding, W., Wei, Y.: Generalized tensor eigenvalue problems. SIAM J. Matrix Anal. Appl. 36, 1073–1099 (2015)MathSciNetCrossRefMATH

20.

Friedland, S., Nocedal, J., Overton, M.L.: The formulation and analysis of numerical methods for inverse eigenvalue problems. SIAM J. Numer. Anal. 24, 634–667 (1987)MathSciNetCrossRefMATH

21.

Goldfarb, D., Wen, Z., Yin, W.: A curvilinear search method for the \(p\)-harmonic flow on spheres. SIAM J. Imaging Sci. 2, 84–109 (2009)MathSciNetCrossRefMATH

22.

Golub, G.H., Van Loan, C.F.: Matrix Computations, 4th edn. The Johns Hopkins University Press, Baltimore (2013). ISBN 978-1-4214-0794-4MATH

23.

Han, L.: An unconstrained optimization approach for finding real eigenvalues of even order symmetric tensors. Numer. Algebra Control Optim. 3, 583–599 (2013)MathSciNetCrossRefMATH

24.

Hao, C., Cui, C., Dai, Y.: A sequential subspace projection method for extreme Z-eigenvalues of supersymmetric tensors. Numer. Linear Algebra Appl. 22, 283–298 (2015)MathSciNetCrossRefMATH

25.

Hao, C., Cui, C., Dai, Y.: A feasible trust-region method for calculating extreme Z-eigenvalues of symmetric tensors, Pacific J. Optim. 11, 291–307 (2015)

26.

Hillar, C.J. , Lim, L.-H.: Most tensor problems are NP-hard, J. ACM 60 (2013) article 45:1–39

27.

Hu, S., Huang, Z., Qi, L.: Finding the extreme Z-eigenvalues of tensors via a sequential SDPs method. Numer. Linear Algebra Appl. 20, 972–984 (2013)MathSciNetCrossRefMATH

28.

Kang, U., Papalexakis, E., Harpale, A., Faloutsos, C.: GigaTensor: scaling tensor analysis up by 100 times—algorithms and discoveries, In: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 316–324 (2012)

29.

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

30.

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

31.

Kolda, T.G., Mayo, J.R.: An adaptive shifted power method for computing generalized tensor eigenpairs. SIAM J. Matrix Anal. Appl. 35, 1563–1581 (2014)MathSciNetCrossRefMATH

32.

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), 1: 129–132 (2005)

33.

Łojasiewicz, S.: Une propriété topologique des sous-ensembles analytiques réels, Les Équations aux Dérivées Partielles, Éditions du centre National de la Recherche Scientifique, Paris, 87–89 (1963)

34.

Luque, J.-G., Thibon, J.-Y.: Hankel hyperdeterminants and Selberg integrals. J. Phys. A 36, 5267–5292 (2003)MathSciNetCrossRefMATH

35.

McAuley, J., Leskovec, J.: Hidden factors and hidden topics: understanding rating dimensions with review text, In: Proceeding of the 7th ACM Conference on Recommender Systems, 165–172 (2013)

36.

Ni, G., Qi, L., Bai, M.: Geometric measure of entanglement and U-eigenvalues of tensors. SIAM J. Matrix Anal. Appl. 35, 73–87 (2014)MathSciNetCrossRefMATH

37.

Ni, Q., Qi, L., Wang, F.: An eigenvalue method for testing positive definiteness of a multivariate form. IEEE Trans. Automat. Control 53, 1096–1107 (2008)MathSciNetCrossRef

38.

Nie, J., Wang, L.: Semidefinite relaxations for best rank-1 tensor approximations. SIAM J. Matrix Anal. Appl. 35, 1155–1179 (2014)MathSciNetCrossRefMATH

39.

Oropeza, V., Sacchi, M.: Simultaneous seismic data denoising and reconstruction via multichannel singular spectrum analysis. Geophysics 76, V25–V32 (2011)CrossRef

40.

Papy, J.M., De Lathauwer, L., Van Huffel, S.: Exponential data fitting using multilinear algebra: the single-channel and multi-channel case. Numer. Linear Algebra Appl. 12, 809–826 (2005)MathSciNetCrossRefMATH

41.

Papy, J.M., De Lathauwer, L., Van Huffel, S.: Exponential data fitting using multilinear algebra: the decimative case. J. Chemom. 23, 341–351 (2009)CrossRef

42.

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

43.

Qi, L.: Hankel tensors: associated Hankel matrices and Vandermonde decomposition. Commun. Math. Sci. 13, 113–125 (2015)MathSciNetCrossRefMATH

44.

Qi, L., Wang, F., Wang, Y.: Z-eigenvalue methods for a global polynomial optimization problem. Math. Program. Ser. A 118, 301–316 (2009)MathSciNetCrossRefMATH

45.

Qi, L., Yu, G., Xu, Y.: Nonnegative diffusion orientation distribution function. J. Math. Imaging Vis. 45, 103–113 (2013)MathSciNetCrossRefMATH

46.

Schatz, M.D., Low, T.-M., Van De Geijn, R.A., Kolda, T.G.: Exploiting symmetry in tensors for high performance. SIAM J. Sci. Comput. 36, C453–C479 (2014)CrossRefMATH

47.

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

48.

Smith, R.S.: Frequency domain subspace identification using nuclear norm minimization and Hankel matrix realizations. IEEE Trans. Automat. Control 59, 2886–2896 (2014)MathSciNetCrossRef

49.

Song, Y., Qi, L.: Infinite and finite dimensional Hilbert tensors. Linear Algebra Appl. 451, 1–14 (2014)MathSciNetCrossRefMATH

50.

Trickett, S., Burroughs, L., Milton, A.: Interpolating using Hankel tensor completion, In: SEG Annual Meeting, 3634–3638 (2013)

51.

Van Huffel, S.: Enhanced resolution based on minimum variance estimation and exponential data modeling. Signal Process. 33, 333–355 (1993)CrossRef

52.

Van Huffel, S., Chen, H., Decanniere, C., Van Hecke, P.: Algorithm for time-domain NMR data fitting based on total least squares. J. Magn. Reson. Ser. A 110, 228–237 (1994)CrossRef

53.

Wen, Z., Yin, W.: A feasible method for optimization with orthogonality constraints. Math. Program. Ser. A 142, 397–434 (2013)MathSciNetCrossRefMATH

54.

Xu, C.: Hankel tensors, Vandermonde tensors and their positivities, Linear Algebra Appl., in press (2015)

Title: Computing Extreme Eigenvalues of Large Scale Hankel Tensors
Authors: Yannan Chen
Liqun Qi
Qun Wang
Publication date: 04-01-2016
Publisher: Springer US
Published in: Journal of Scientific Computing / Issue 2/2016
Print ISSN: 0885-7474
Electronic ISSN: 1573-7691
DOI: https://doi.org/10.1007/s10915-015-0155-8

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+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 2/2016

Efficient Spectral-Galerkin Method and Analysis for Elliptic PDEs with Non-local Boundary Conditions

Solving Multi-linear Systems with $$\mathcal {M}$$ M -Tensors

Computation Algorithm for Convex Semi-infinite Program with Second-Order Cones: Special Analyses for Affine and Quadratic Case

A Novel Scheme for Liouville’s Equation with a Discontinuous Hamiltonian and Applications to Geometrical Optics

An Adaptive $$\varvec{P_1}$$ P 1 Finite Element Method for Two-Dimensional Transverse Magnetic Time Harmonic Maxwell’s Equations with General Material Properties and General Boundary Conditions

A Cell-Centered Nonlinear Finite Volume Scheme Preserving Fully Positivity for Diffusion Equation

Premium Partner