A scalable optimization approach for fitting canonical tensor decompositions

By Evrim Acar, Daniel M. Dunlavy, Tamara G. Kolda. 2011

303 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Mathematics, Hardware and Architecture

How researchers see this paper

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

In Artificial Intelligence

In Computational Mathematics

In Hardware and Architecture

Citations in the corpus

A literature survey of low‐rank tensor approximation techniques (2013, neutral): “More recent developments for general tensors include work on increasing the efficiency and robustness of gradient-based and Newton-like methods [2,73,75,141,224,225], modifying and improving ALS (alternating least squares) [42, 58, 59, 91, 226], studying the convergence of ALS [52, 195, 255] and red”
DFacTo: Distributed Factorization of Tensors (2014, methodology): “Therefore, as predicted by theory, DFacTo (ALS, GD) does not enjoy significant speedups when compared to GigaTensor, CPALS and CPOPT.”
On Fast Computation of Gradients for CANDECOMP/PARAFAC Algorithms (2012, methodology): “Instead of alternating estimation, all-at-once algorithms such as the OPT algorithm [1], the PMF3, damped Gauss-Newton (dGN) algorithms [24,33] and fast dGN [25,26,32] are studied to deal with problems of a slow convergence of the ALS in some cases.”
New ALS Methods With Extrapolating Search Directions and Optimal Step Size for Complex-Valued Tensor Decompositions (2011, methodology): “Some gradient based optimization methods, including nonlinear conjugate-gradient, limited-memory BFGS and truncated Newton’s method, are employed to exploit higher-order search directions for CP [1], [2].”
All-at-once Optimization for Coupled Matrix and Tensor Factorizations (2011, background): “, the number of extracted components is more than the true number of underlying components [2, 32].”
A Nonlinear GMRES Optimization Algorithm for Canonical Tensor Decomposition (2011, methodology): “In recent work on CP decomposition, Acar et al. [1] consider ﬁrst-order optimization algorithms for Optimization Problem I.”
Temporal Link Prediction Using Matrix and Tensor Factorizations (2010, background): “In the Netflix contest, for example, Bell and Koren [2007] consider the “binary view of the data” as important as the ratings themselves.”
Scalable Tensor Factorizations for Incomplete Data (2010, methodology): “Due to the well-known indeterminacies of the CP model, it may also be desirable to add regularization to the objective function as in [20], but this has not been necessary thus far in our experiments.”
Tensors for Data Mining and Data Fusion (2016, methodology): “Acar et al. [2011] apply ALGORITHM 1: Alternating Least Squares for CP g., at random) 2: while convergence criterion is not met do 3: Normalize columns of B 7: Normalize columns of C and store norm in λ 9: end while ﬁrst-order gradient optimization methods such as limited-memory BFGS. Phan et al.…”
Learning Separable Filters (2013, methodology): “To compute the CPDs we tried a simple alternate leastsquares optimization and the CP-OPT algorithm of [1], implemented in the MATLAB tensor toolbox.”
Tensor Networks for Dimensionality Reduction and Large-scale Optimization: Part 1 Low-Rank Tensor Decompositions (2016, unknown): “Alternative algorithms for the CP decomposition of huge-scale tensors, include tensor sketching – a random mapping technique, which exploits kernel methods and regression [278], and the class of distributed algorithms such as the CPOPT [4], the DFacTo [45] and the GigaTensor which is based on Hadoop”
CANDECOMP/PARAFAC Decomposition of High-Order Tensors Through Tensor Reshaping (2012, methodology): “For example, there are numerous algorithms for CPD including the alternating least squares (ALS) algorithm [2], [1] with line search extrapolation methods [1], [17], [4], [18], [19], rotation [20] and compression [21], or all-at-once algorithms such as the OPT algorithm [22], the conjugate gradient ”
Low-Rank Tensor Learning with Discriminant Analysis for Action Classification and Image Recovery (2014, background): “…approaches have been proposed as well, which, in general, estimate a rank-one tensor via vector outer production (Espig 2007; Kazeev and Tyrtyshnikov 2010; Acar, Dunlavy, and Kolda 2011; Espig and Hackbusch 2012; Phan, Anh Huy and Tichavskỳ, Petr and Cichocki, Andrzej 2012; 2013; Shi et al. 2013).”
Low Complexity Damped Gauss-Newton Algorithms for CANDECOMP/PARAFAC (2012, methodology): “All-at-once algorithms such as the OPT algorithm [1], the PMF3, damped Gauss-Newton (dGN) algorithms [11, 20, 29, 31] simultaneously update a.”
Low-rank tensor methods for linear systems and eigenvalue problems (2012, background): “B([1]) 34 B([2]) 34 B([3]) 34 B([4]) 34 B([1]) 1234 B([2]) 1234 B([3]) 1234 B([4]) 1234 U [3] 1 U [2] 1 U [1] 1”
Algorithm 941 (2014, background): “Unfortunately, developing a robust and efficient algorithm for this format, which yields an approximation to any desirable accuracy, remains a subtle problem; see Acar et al. [2011] and Espig and Hackbusch [2012] for recent progress.”
FFT-based Kronecker product approximation to micromagnetic long-range interactions (2012, methodology): “Algorithms for computing canonical decompositions are mostly based on optimization, e.g. alternating least squares [22], gradient based or nonlinear least squares methods [3] or Gauss-Newton [30].”
Low-Rank Tensor Krylov Subspace Methods for Parametrized Linear Systems (2011, methodology): “Recently developed methods for low-rank approximation in CP decomposition can be found in [1, 14, 30] and overcome some of these subtleties.”