Linear convergence of an alternating polar decomposition method for low rank orthogonal tensor approximations

DOI10.1007/S10107-022-01867-8MaRDI QIDQ6038672zbMATH OpenOpenAlexWikidataFDO

Authors Shenglong Hu, Ke Ye

Publication date 2 May 2023

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1912.04085

zbMATH Keywords

\(R\)-linear convergenceglobal convergencelow rank orthogonal tensor approximationorthogonally decomposable tensorssublinear convergence

Mathematics Subject Classification ID

Multilinear algebra, tensor calculus (15A69) Numerical methods for low-rank matrix approximation; matrix compression (65F55)

Abstract: Low rank orthogonal tensor approximation (LROTA) is an important problem in tensor computations and their applications. A classical and widely used algorithm is the alternating polar decomposition method (APD). In this article, an improved version iAPD of the classical APD is proposed. For the first time, all the following four fundamental properties are established for iAPD: (i) the algorithm converges globally and the whole sequence converges to a KKT point without any assumption; (ii) it exhibits an overall sublinear convergence with an explicit rate which is sharper than the usual $O(1/k)$ for first order methods in optimization; (iii) more importantly, it converges $R$-linearly for a generic tensor without any assumption; (iv) for almost all LROTA problems, iAPD reduces to APD after finitely many iterations if it converges to a local minimizer.

Recommendations

• A convergence analysis for an algorithm computing a symmetric low rank orthogonal approximation of a symmetric tensor
• Orthogonal low rank tensor approximation: alternating least squares method and its global convergence
• Numerical computation for orthogonal low-rank approximation of tensors
• A Global Convergence Analysis for Computing a Symmetric Low-Rank Orthogonal Approximation
• The epsilon-alternating least squares for orthogonal low-rank tensor approximation and its global convergence

Cites work

• A Counterexample to the Possibility of an Extension of the Eckart--Young Low-Rank Approximation Theorem for the Orthogonal Rank Tensor Decomposition
• A Jacobi-Type Method for Computing Orthogonal Tensor Decompositions
• A literature survey of low-rank tensor approximation techniques
• A new convergence proof for the higher-order power method and generalizations
• Approximate matrix and tensor diagonalization by unitary transformations: convergence of Jacobi-type algorithms
• Calculus of the exponent of Kurdyka-Łojasiewicz inequality and its applications to linear convergence of first-order methods
• Canonical polyadic decomposition with a columnwise orthonormal factor matrix
• Characterizations of Łojasiewicz inequalities: Subgradient flows, talweg, convexity
• Clarke Subgradients of Stratifiable Functions
• Computing the Polar Decomposition—with Applications
• Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
• Convergence rate analysis for the higher order power method in best rank one approximations of tensors
• Explicit bounds for the Łojasiewicz exponent in the gradient inequality for polynomials
• First-order methods almost always avoid strict saddle points
• First-order methods in optimization
• Globally convergent Jacobi-type algorithms for simultaneous orthogonal symmetric tensor diagonalization
• scientific article; zbMATH DE number 5968745 (Why is no real title available?)
• scientific article; zbMATH DE number 1818892 (Why is no real title available?)
• scientific article; zbMATH DE number 4146164 (Why is no real title available?)
• scientific article; zbMATH DE number 45789 (Why is no real title available?)
• scientific article; zbMATH DE number 3563286 (Why is no real title available?)
• scientific article; zbMATH DE number 3572315 (Why is no real title available?)
• scientific article; zbMATH DE number 1201576 (Why is no real title available?)
• scientific article; zbMATH DE number 6159604 (Why is no real title available?)
• scientific article; zbMATH DE number 7410750 (Why is no real title available?)
• scientific article; zbMATH DE number 5223994 (Why is no real title available?)
• Independent component analysis, a new concept?
• Introductory lectures on convex optimization. A basic course.
• Jacobi algorithm for the best low multilinear rank approximation of symmetric tensors
• LAPACK Users' Guide
• Local convergence of the alternating least squares algorithm for canonical tensor approximation
• Majorization for Changes in Angles Between Subspaces, Ritz Values, and Graph Laplacian Spectra
• Matrix Analysis
• Morse Theory. (AM-51)
• Musings on multilinear fitting
• Numerical computation for orthogonal low-rank approximation of tensors
• On approximate diagonalization of third order symmetric tensors by orthogonal transformations
• On gradients of functions definable in o-minimal structures
• On the Best Rank-1 and Rank-(R₁ ,R₂ ,. . .,R_N) Approximation of Higher-Order Tensors
• On the global convergence of the alternating least squares method for rank-one approximation to generic tensors
• On the Tensor SVD and the Optimal Low Rank Orthogonal Approximation of Tensors
• Orthogonal and unitary tensor decomposition from an algebraic perspective
• Orthogonal low rank tensor approximation: alternating least squares method and its global convergence
• Orthogonal tensor decompositions
• Proximal alternating linearized minimization for nonconvex and nonsmooth problems
• Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality
• Rank-one approximation to high order tensors
• Successive Rank-One Approximations for Nearly Orthogonally Decomposable Symmetric Tensors
• Tensor analysis. Spectral theory and special tensors
• Tensor Decompositions and Applications
• Tensor decompositions for learning latent variable models
• Tensor Rank and the Ill-Posedness of the Best Low-Rank Approximation Problem
• Tensor spaces and numerical tensor calculus
• The epsilon-alternating least squares for orthogonal low-rank tensor approximation and its global convergence
• The Geometry of Algorithms with Orthogonality Constraints
• Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics
• Variational Analysis

Cited in

(14)

• Nondegeneracy of eigenvectors and singular vector tuples of tensors
• An inexact augmented Lagrangian method for computing strongly orthogonal decompositions of tensors
• Nonlinear power-like iteration by polar decomposition and its application to tensor approximation
• A convergence analysis for an algorithm computing a symmetric low rank orthogonal approximation of a symmetric tensor
• The epsilon-alternating least squares for orthogonal low-rank tensor approximation and its global convergence
• A Global Convergence Analysis for Computing a Symmetric Low-Rank Orthogonal Approximation
• Jacobi-type algorithms for homogeneous polynomial optimization on Stiefel manifolds with applications to tensor approximations
• Black Box Approximation in the Tensor Train Format Initialized by ANOVA Decomposition
• Local convergence of alternating low‐rank optimization methods with overrelaxation
• An alternating algorithm for structure preserving CP-decompositions of partially symmetric tensors
• The R-linear convergence of IPPDA for symmetric low rank orthogonal tensor approximation
• Quantifying low rank approximations of third order symmetric tensors
• A sparse optimization approach for simultaneous orthogonal tensor diagonalization
• Some properties of bi-form optimization over generalized spheres

This page was built for publication: Linear convergence of an alternating polar decomposition method for low rank orthogonal tensor approximations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6038672)