Alternating Mahalanobis Distance Minimization for Accurate and Well-Conditioned CP Decomposition
From MaRDI portal
Publication:6087747
alternating least squarescondition numberCP decompositioneigenvaluesMahalanobis distancesingular valuestensor decomposition
Multilinear algebra, tensor calculus (15A69) Vector and tensor algebra, theory of invariants (15A72) Numerical optimization and variational techniques (65K10) Numerical algorithms for computer arithmetic, etc. (65Y04) Complexity and performance of numerical algorithms (65Y20) Approximation algorithms (68W25)
Abstract: CP decomposition (CPD) is prevalent in chemometrics, signal processing, data mining and many more fields. While many algorithms have been proposed to compute the CPD, alternating least squares (ALS) remains one of the most widely used algorithm for computing the decomposition. Recent works have introduced the notion of eigenvalues and singular values of a tensor and explored applications of eigenvectors and singular vectors in areas like signal processing, data analytics and in various other fields. We introduce a new formulation for deriving singular values and vectors of a tensor by considering the critical points of a function different from what is used in the previous work. Computing these critical points in an alternating manner motivates an alternating optimization algorithm which corresponds to alternating least squares algorithm in the matrix case. However, for tensors with order greater than equal to , it minimizes an objective function which is different from the commonly used least squares loss. Alternating optimization of this new objective leads to simple updates to the factor matrices with the same asymptotic computational cost as ALS. We show that a subsweep of this algorithm can achieve a superlinear convergence rate for exact CPD with known rank and verify it experimentally. We then view the algorithm as optimizing a Mahalanobis distance with respect to each factor with ground metric dependent on the other factors. This perspective allows us to generalize our approach to interpolate between updates corresponding to the ALS and the new algorithm to manage the tradeoff between stability and fitness of the decomposition. Our experimental results show that for approximating synthetic and real-world tensors, this algorithm and its variants converge to a better conditioned decomposition with comparable and sometimes better fitness as compared to the ALS algorithm.
Recommendations
- Optimization-based algorithms for tensor decompositions: canonical polyadic decomposition, decomposition in rank-(L_r,L_r,1) terms, and a new generalization
- A trust-region-based alternating least-squares algorithm for tensor decompositions
- A Practical Randomized CP Tensor Decomposition
- Canonical polyadic decomposition of third-order tensors: reduction to generalized eigenvalue decomposition
- Canonical polyadic decomposition of third-order tensors: relaxed uniqueness conditions and algebraic algorithm
Cites work
- A comparison of algorithms for fitting the PARAFAC model
- A Practical Randomized CP Tensor Decomposition
- Accelerating alternating least squares for tensor decomposition by pairwise perturbation
- All real eigenvalues of symmetric tensors
- An enhanced line search scheme for complex-valued tensor decompositions. Application in DS-CDMA
- Analysis of individual differences in multidimensional scaling via an \(n\)-way generalization of ``Eckart-Young decomposition
- Approximate matrix and tensor diagonalization by unitary transformations: convergence of Jacobi-type algorithms
- Comparison of Accuracy and Scalability of Gauss--Newton and Alternating Least Squares for CANDECOMC/PARAFAC Decomposition
- Computing dense tensor decompositions with optimal dimension trees
- Computing the gradient in optimization algorithms for the CP decomposition in constant memory through tensor blocking
- Condition numbers for the tensor rank decomposition
- Enhanced Line Search: A Novel Method to Accelerate PARAFAC
- Exact line and plane search for tensor optimization
- Exploiting symmetry in tensors for high performance: multiplication with symmetric tensors
- Further results on Moore-Penrose inverses of tensors with application to tensor nearness problems
- Globally convergent Jacobi-type algorithms for simultaneous orthogonal symmetric tensor diagonalization
- scientific article; zbMATH DE number 6378089 (Why is no real title available?)
- scientific article; zbMATH DE number 3023295 (Why is no real title available?)
- Local convergence of the alternating least squares algorithm for canonical tensor approximation
- Low complexity damped Gauss-Newton algorithms for CANDECOMP/PARAFAC
- Metric Learning
- Metric learning: a survey
- Moore–Penrose inverse of tensors via Einstein product
- Most tensor problems are NP-hard
- Musings on multilinear fitting
- Nesterov acceleration of alternating least squares for canonical tensor decomposition: momentum step size selection and restart mechanisms.
- Optimization-based algorithms for tensor decompositions: canonical polyadic decomposition, decomposition in rank-(L_r,L_r,1) terms, and a new generalization
- Parallel Candecomp/Parafac decomposition of sparse tensors using dimension trees
- Shifted power method for computing tensor eigenpairs
- Singular vectors of orthogonally decomposable tensors
- Tensor Decomposition for Signal Processing and Machine Learning
- Tensor Decompositions and Applications
- Tensor decompositions for learning latent variable models
- Tensor eigenvalues and their applications
- The Z-eigenvalues of a symmetric tensor and its application to spectral hypergraph theory.
- The condition number of join decompositions
- The condition number of many tensor decompositions is invariant under Tucker compression
This page was built for publication: Alternating Mahalanobis Distance Minimization for Accurate and Well-Conditioned CP Decomposition
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6087747)
