Geodesic
The structure of the Hessian and the efficient implementation of Newton's method in the problem of the canonical approximation of tensors
Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 50 (2010) no. 6, pp. 979-998 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

A tensor given by its canonical decomposition is approximated by another tensor (again, in the canonical decomposition) of fixed lower rank. For this problem, the structure of the Hessian matrix of the objective function is analyzed. It is shown that all the auxiliary matrices needed for constructing the quadratic model can be calculated so that the computational effort is a quadratic function of the tensor dimensionality (rather than a cubic function as in earlier publications). An economical version of the trust region Newton method is proposed in which the structure of the Hessian matrix is efficiently used for multiplying this matrix by vectors and for scaling the trust region. At each step, the subproblem of minimizing the quadratic model in the trust region is solved using the preconditioned conjugate gradient method, which is terminated if a negative curvature direction is detected for the Hessian matrix. 
@article{ZVMMF_2010_50_6_a0,
     author = {V. A. Kazeev and E. E. Tyrtyshnikov},
     title = {The structure of the {Hessian} and the efficient implementation of {Newton's} method in the problem of the canonical approximation of tensors},
     journal = {\v{Z}urnal vy\v{c}islitelʹnoj matematiki i matemati\v{c}eskoj fiziki},
     pages = {979--998},
     year = {2010},
     volume = {50},
     number = {6},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_6_a0/}
}
TY  - JOUR
AU  - V. A. Kazeev
AU  - E. E. Tyrtyshnikov
TI  - The structure of the Hessian and the efficient implementation of Newton's method in the problem of the canonical approximation of tensors
JO  - Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
PY  - 2010
SP  - 979
EP  - 998
VL  - 50
IS  - 6
UR  - http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_6_a0/
LA  - ru
ID  - ZVMMF_2010_50_6_a0
ER  - 
%0 Journal Article
%A V. A. Kazeev
%A E. E. Tyrtyshnikov
%T The structure of the Hessian and the efficient implementation of Newton's method in the problem of the canonical approximation of tensors
%J Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki
%D 2010
%P 979-998
%V 50
%N 6
%U http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_6_a0/
%G ru
%F ZVMMF_2010_50_6_a0
V. A. Kazeev; E. E. Tyrtyshnikov. The structure of the Hessian and the efficient implementation of Newton's method in the problem of the canonical approximation of tensors. Žurnal vyčislitelʹnoj matematiki i matematičeskoj fiziki, Tome 50 (2010) no. 6, pp. 979-998. http://geodesic.mathdoc.fr/item/ZVMMF_2010_50_6_a0/

[1] Bellman R., Adaptive control processes: A guided tour, Princeton Univ. Press, Princeton, NJ, 1961 | MR | Zbl

[2] Beylkin G., Mohlenkamp M. J., “Algorithms for numerical analysis in high dimensions”, SIAM. J. Sci. Comput., 26:6 (2005), 2133–2159 | DOI | MR | Zbl

[3] Evrim A., Bülent V., “Unsupervised multiway data analysis: A literature survey”, IEEE Trans. Knowledge and Data Engng., 21:1 (2009), 6–20 | DOI

[4] Zhang T., Golub G. H., “Rank-one apporoximation to high order tensors”, SIAM J. Matrix Analys. and Appl., 23:2 (2001), 534–550 | DOI | MR | Zbl

[5] Oseledets I. V., Savostyanov D. V., “Minimizatsionnye metody approksimatsii tenzorov i ikh sravnenie”, Zh. vychisl. matem. i matem. fiz., 46:10 (2006), 1725–1734 | MR

[6] Kazeev V. A., “O probleme kanonicheskogo razlozheniya tenzorov, odnom algoritme ee resheniya v primenenii ego k poisku bystrykh matrichnykh algoritmov”, Sovr. probl. fundamentalnykh i prikl. nauk, Tr. 51-i nauchn. konf. MFTI, v. VIII, Probl. sovrem. fiz., MFTI, M., 2008, 225–228

[7] Espig M., Effiziente Bestapproximation mittels Summen von Elementartensoren in hohen Dimensionen, Ph. D. thesis, Univ. Leipzig, 2008

[8] Caroll J. D., Chang J. J., “Analysis of individual differences in multidimensional scaling via an $N$-way generalization of “Eckart-Young” decomposition”, Psychometrika, 35 (1970), 283–319 | DOI

[9] Harshman R. A., “Foundations of the PARAFAC procedure: Models and conditions for an “explanatory” multimodal factor analysis”, UCLA Working Papers in Phonetics, 16 (1970), 1–84

[10] de Silva V., Lim L. H., “Tensor rank and the ill-posedness of the best low-rank approximation problem”, SIAM J. Matrix Analys. and Appl., 30:3 (2008), 1084–1127 | DOI | MR

[11] Tyrtyshnikov E. E., Matrichnyi analiz i lineinaya algebra, Fizmatlit, M., 2007

[12] Mohlenkamp M. J., Monzón L., “Trigonometric identities and sums of separable functions”, Math. Intelligencer, 27:2 (2005), 65–69 | DOI | MR | Zbl

[13] Steihaug T., “The conjugate gradient method and trust regions in large scale optimization”, SIAM J. Numer. Analys., 20:3 (1983), 626–637 | DOI | MR | Zbl

[14] Nocedal J., Wright S., Numerical optimization, Springer, New York, 1999 | MR | Zbl

[15] Shultz G. A., Schnabel R. B., Byrd R. H., “A family of trust-region-based algorithms for unconstrained minimization with strong global convergence properties”, SIAM J. Numer. Analys., 22:1 (1985), 47–67 | DOI | MR | Zbl

[16] Byrd R. H., Shultz G. A., “A trust region algorithm for nonlinearly constrained optimization”, SIAM J. Numer. Analys., 24:5 (1987), 1152–1170 | DOI | MR | Zbl

[17] Byrd R. H., Schnabel R. B., Shultz G. A., “Approximate solution of the trust regions problem by minimization over two-dimensional subspaces”, Math. Program., 40 (1988), 247–263 | DOI | MR | Zbl

[18] Gay D. M., “Computing optimal locally constrained steps”, SIAM J. Sci. and Statist. Comput., 2:2 (1981), 186–197 | DOI | MR | Zbl

[19] Sorensen D. C., “Newton's method with a model trust modification”, SIAM J. Numer. Analys., 19:3 (1982), 409–426 | DOI | MR | Zbl

[20] Djoković D. Ž., “On the Hadamard product of matrices”, Math. Z., 86:5 (1965), 395 | DOI | MR | Zbl

[21] Horn R. A., Johnson C. R., Matrix analysis, Cambridge Univ. Press, 1985 | MR | Zbl

[22] Strassen V., “Gaussian elimination is not optimal”, Numer. Math., 13 (1969), 354–356 | DOI | MR | Zbl

[23] Landsberg J. M., “The border rank of the multiplication of $2\times2$ matrices in seven”, J. Amer. Math. Soc., 19:2 (2005), 447–459 | DOI | MR

[24] Flad H.-J., Khoromskij B. N., Savostyanov D. V., Tyrtyshnikov E. E., “Verification of the cross 3D algorithm on quantum chemistry data”, Rus. J. Numer. Analys. and Math. Modelling, 23:4 (2008), 210–220 | MR