Structure of the Hessian matrix and an economical implementation of Newton’s method in the problem of canonical approximation of tensors
- 25 June 2010
- journal article
- Published by Pleiades Publishing Ltd in Computational Mathematics and Mathematical Physics
- Vol. 50 (6) , 927-945
Abstract
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.Keywords
This publication has 20 references indexed in Scilit:
- Unsupervised Multiway Data Analysis: A Literature SurveyIEEE Transactions on Knowledge and Data Engineering, 2008
- Tensor Rank and the Ill-Posedness of the Best Low-Rank Approximation ProblemSIAM Journal on Matrix Analysis and Applications, 2008
- Minimization methods for approximating tensors and their comparisonComputational Mathematics and Mathematical Physics, 2006
- Trigonometric identities and sums of separable functionsThe Mathematical Intelligencer, 2005
- Algorithms for Numerical Analysis in High DimensionsSIAM Journal on Scientific Computing, 2005
- Rank-One Approximation to High Order TensorsSIAM Journal on Matrix Analysis and Applications, 2001
- Numerical Optimization1999
- The Conjugate Gradient Method and Trust Regions in Large Scale OptimizationSIAM Journal on Numerical Analysis, 1983
- Analysis of Individual Differences in Multidimensional Scaling Via an N-way Generalization of “Eckart-Young” DecompositionPsychometrika, 1970
- Adaptive Control Processes1961