Quasi-Newton Methods on Grassmannians and Multilinear Approximations of Tensors

By Berkant Savas, Lek-Heng Lim. 2009

137 citations recorded by the source corpus.

In this paper we proposed quasi-Newton and limited memory quasi-Newton methods for objective functions defined on Grassmannians or a product of Grassmannians. Specifically we defined BFGS and limited memory BFGS updates in local and global coordinates on Grassmannians or a product of these. We proved that, when local coordinates are used, our BFGS updates on Grassmannians share the same optimality property as the usual BFGS updates on Euclidean spaces. When applied to the best multilinear rank approximation problem for general and symmetric tensors, our approach yields fast, robust, and accurate algorithms that exploit the special Grassmannian structure of the respective problems and which work on tensors of large dimensions and arbitrarily high order. Extensive numerical experiments are included to substantiate our claims.

Subfields: Computational Mathematics, Computational Theory and Mathematics, Numerical Analysis

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mathematics

In Computational Theory and Mathematics

In Numerical Analysis

Citations in the corpus

A literature survey of low‐rank tensor approximation techniques (2013, neutral): “Recent developments include Newton-type methods on manifolds [71, 131, 132, 229], a Jacobi algorithm for symmetric tensors [130], generalizations of Krylov subspace meth-ods [98,228], and modiﬁcations of the HOSVD [259].”
Numerical solution of the Hartree-Fock equation by multilevel tensor-structured methods (2011, methodology): “6.1 Brief summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 6.2 Presentations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140”
A New Truncation Strategy for the Higher-Order Singular Value Decomposition (2012, methodology): “For instance, the T-HOSVD is used to initialize iterative algorithms to compute the best rank-1 approximation [7, 28, 63] or best approximation of a specified multilinear rank [11, 15, 24, 26, 51].”
MACH: Fast Randomized Tensor Decompositions (2009, methodology): “, [41], [1]), currently i n practice the approach followed is the Alternating Least Squares, which involves the computationally expensive SVD.”
Krylov-Type Methods for Tensor Computations (2010, unknown): “An important thread of research in this field is the computation of low multilinear rank approximations of tensors [21,6,7,1,33,5,9,28,15,25,17,20].”
Jacobi Algorithm for the Best Low Multilinear Rank Approximation of Symmetric Tensors (2013, methodology): “An advantage of the proposed algorithm over the one in [45] is our comprehensive convergence analysis.”
Krylov-type methods for tensor computations I (2013, background): “An important thread of research in this field is the computation of low multilinear rank approximations of tensors [21,6,7,1,33,5,9,28,15,25,17,20].”
Tensor Decompositions for Signal Processing Applications: From two-way to multiway component analysis (2014, background): “Optimization-based algorithms exploiting second-order information have also been proposed [71], [72].”
Variational calculus with sums of elementary tensors of fixed rank (2012, unknown): “It suggests that the approach might be competitive with optimization algorithms for alternative tensor formats as the Tucker Format [30] or the HT [17] format (with the TT format [26–28] as special case), for which the development is also still in progress: For the Tucker format, one obtains an opti”
Best Low Multilinear Rank Approximation of Higher-Order Tensors, Based on the Riemannian Trust-Region Scheme (2011, methodology): “Recently, Newton-type algorithms for the best low multilinear rank approximation of tensors have been developed in [25, 17, 39], the first one being based on [2].”