Tensor Rank and the Ill-Posedness of the Best Low-Rank Approximation Problem
From MaRDI portal
Brégman divergence of tensorscandecompEckart-Young theoremhyperdeterminantslow-rank tensor approximationsmultidimensional arraysmultiway arraysnumerical multilinear algebraparafacprincipal component analysistensor decompositionstensor ranktensors
Semialgebraic sets and related spaces (14P10) Vector spaces, linear dependence, rank, lineability (15A03) Canonical forms, reductions, classification (15A21) Multilinear algebra, tensor calculus (15A69) Vector and tensor algebra, theory of invariants (15A72) Decomposition methods (49M27) Factor analysis and principal components; correspondence analysis (62H25) General topics in the theory of data (68P01)
Abstract: There has been continued interest in seeking a theorem describing optimal low-rank approximations to tensors of order 3 or higher, that parallels the Eckart-Young theorem for matrices. In this paper, we argue that the naive approach to this problem is doomed to failure because, unlike matrices, tensors of order 3 or higher can fail to have best rank-r approximations. The phenomenon is much more widespread than one might suspect: examples of this failure can be constructed over a wide range of dimensions, orders and ranks, regardless of the choice of norm (or even Bregman divergence). Moreover, we show that in many instances these counterexamples have positive volume: they cannot be regarded as isolated phenomena. In one extreme case, we exhibit a tensor space in which no rank-3 tensor has an optimal rank-2 approximation. The notable exceptions to this misbehavior are rank-1 tensors and order-2 tensors. In a more positive spirit, we propose a natural way of overcoming the ill-posedness of the low-rank approximation problem, by using weak solutions when true solutions do not exist. In our work we emphasize the importance of closely studying concrete low-dimensional examples as a first step towards more general results. To this end, we present a detailed analysis of equivalence classes of 2-by-2-by-2 tensors, and we develop methods for extending results upwards to higher orders and dimensions. Finally, we link our work to existing studies of tensors from an algebraic geometric point of view. The rank of a tensor can in theory be given a semialgebraic description; i.e., can be determined by a system of polynomial inequalities. In particular we make extensive use of the 2-by-2-by-2 hyperdeterminant.
Recommendations
- On best rank-\(2\) and rank-\((2,2,2)\) approximations of order-\(3\) tensors
- Subtracting a best rank‐1 approximation from p × p × 2(p≥2) tensors
- Guarantees for existence of a best canonical polyadic approximation of a noisy low-rank tensor
- Subtracting a best rank-1 approximation may increase tensor rank
- Perturbation theory and optimality conditions for the best multilinear rank approximation of a tensor
Cited in
(only showing first 100 items - show all)- Robust reduced order modeling of heat transfer in a back step flow
- On uniqueness conditions for Candecomp/Parafac and Indscal with full column rank in one mode
- The subbundles of decomposable vector bundles over an elliptic curve
- Equivariant minimax dominators of the MLE in the array normal model
- A higher-order LQ decomposition for separable covariance models
- Convergence rate analysis for the higher order power method in best rank one approximations of tensors
- Generalization of the tensor renormalization group approach to 3-D or higher dimensions
- Finding the limit of diverging components in three-way Candecomp/Parafac -- a demonstration of its practical merits
- On the minimal ranks of matrix pencils and the existence of a best approximate block-term tensor decomposition
- On the spectral problem for trivariate functions
- A seminorm regularized alternating least squares algorithm for canonical tensor decomposition
- Set evincing the ranks with respect to an embedded variety (symmetric tensor rank and tensor rank)
- On the rank of a Latin tensor
- Simultaneous component analysis by means of Tucker3
- Tensor network alternating linear scheme for MIMO Volterra system identification
- Nearest-neighbor interaction systems in the tensor-train format
- On the convergence of alternating minimization methods in variational PGD
- Tensor rank is not multiplicative under the tensor product
- Fast structured matrix computations: tensor rank and Cohn-Umans method
- The numerical approximation of nonlinear functionals and functional differential equations
- Higher-order principal component analysis for the approximation of tensors in tree-based low-rank formats
- A note on the three-way generalization of the Jordan canonical form
- On accelerating the regularized alternating least-squares algorithm for tensors
- On minimal subspaces in tensor representations
- The convex geometry of linear inverse problems
- Exact probabilities for typical ranks of 2 2 2 and 3 3 2 tensors
- Ranks of tensors and a generalization of secant varieties
- Some convergence results on the regularized alternating least-squares method for tensor decomposition
- Musings on multilinear fitting
- Block tensors and symmetric embeddings
- Monotonically convergent algorithms for symmetric tensor approximation
- Krylov-type methods for tensor computations.I
- A tensor decomposition approach to data compression and approximation of ND systems
- A regularized Newton method for the efficient approximation of tensors represented in the canonical tensor format
- Constructive representation of functions in low-rank tensor formats
- Sets computing the symmetric tensor rank
- An upper bound for the tensor rank
- On the \(X\)-rank with respect to linearly normal curves
- On the rank and the approximation of symmetric tensors
- Weighted Moore-Penrose inverses of arbitrary-order tensors
- A hyperspace of convex bodies arising from tensor norms
- Multilayer tensor factorization with applications to recommender systems
- Greedy low-rank approximation in Tucker format of solutions of tensor linear systems
- Parallel tensor methods for high-dimensional linear PDEs
- On polynomial time methods for exact low-rank tensor completion
- Rank 1 decompositions of symmetric tensors outside a fixed support
- A note on nonclosed tensor formats
- Tensor theta norms and low rank recovery
- A Barzilai-Borwein gradient algorithm for spatio-temporal Internet traffic data completion via tensor triple decomposition
- The nonconvex tensor robust principal component analysis approximation model via the weighted _p-norm regularization
- A tensor rank theory and maximum full rank subtensors
- Data-driven reduced order modeling based on tensor decompositions and its application to air-wall heat transfer in buildings
- Triangular decomposition of CP factors of a third-order tensor with application to solving nonlinear systems of equations
- A proximal point like method for solving tensor least-squares problems
- High order singular value decomposition for plant diversity estimation
- Uniform matrix product states from an algebraic geometer's point of view
- A Krylov-Schur-like method for computing the best rank-\((r_1,r_2,r_3)\) approximation of large and sparse tensors
- Multi-dimensional image recovery via fully-connected tensor network decomposition under the learnable transforms
- Low-rank tensor methods for Markov chains with applications to tumor progression models
- Inertial accelerated SGD algorithms for solving large-scale lower-rank tensor CP decomposition problems
- Robust and resource-efficient identification of two hidden layer neural networks
- Best \(k\)-layer neural network approximations
- Inference for low-rank tensors -- no need to debias
- Learning diagonal Gaussian mixture models and incomplete tensor decompositions
- Solving phase-field models in the tensor train format to generate microstructures of bicontinuous composites
- Interpolatory tensorial reduced order models for parametric dynamical systems
- Tensor completion via fully-connected tensor network decomposition with regularized factors
- On the closedness and geometry of tensor network state sets
- Topology of tensor ranks
- Complex best \(r\)-term approximations almost always exist in finite dimensions
- Reverse-order law for core inverse of tensors
- High-order sum-of-squares structured tensors: theory and applications
- Conjugate gradient-like methods for solving general tensor equation with Einstein product
- Iterative low-rank approximation solvers for the extension method for fractional diffusion
- Matrix factorization for low-rank tensor completion using framelet prior
- Tensor decompositions and rank increment conjecture
- Stability of low-rank tensor representations and structured multilevel preconditioning for elliptic PDEs
- Dynamically orthogonal tensor methods for high-dimensional nonlinear PDEs
- Linear subspaces of symmetric tensors whose non-zero elements have at least a prescribed rank
- Symmetric tensor rank and scheme rank: an upper bound in terms of secant varieties
- An upper bound for the symmetric tensor rank of a low degree polynomial in a large number of variables
- Computing images of polynomial maps
- An inexact augmented Lagrangian method for computing strongly orthogonal decompositions of tensors
- Unfoldings and the rank-one approximation of the tensor
- Jordan canonical form of three-way tensor with multilinear rank \((4,4,3)\)
- Three-way clustering of multi-tissue multi-individual gene expression data using semi-nonnegative tensor decomposition
- Best rank-k approximations for tensors: generalizing Eckart-Young
- Even-order Toeplitz tensor: framework for multidimensional structured linear systems
- A tensor decomposition algorithm for large ODEs with conservation laws
- Tensor train spectral method for learning of hidden Markov models (HMM)
- Pseudospectra localizations for generalized tensor eigenvalues to seek more positive definite tensors
- The Hitchhiker guide to: secant varieties and tensor decomposition
- Three-mode factor analysis by means of Candecomp/Parafac
- Tensors of nonnegative rank two
- Optimization on the hierarchical Tucker manifold - applications to tensor completion
- Real rank two geometry
- Adaptive stochastic Galerkin FEM with hierarchical tensor representations
- Solving the master equation without kinetic Monte Carlo: tensor train approximations for a CO oxidation model
- A note on the gap between rank and border rank
- The stratification by rank for homogeneous polynomials with border rank 5 which essentially depend on five variables
This page was built for publication: Tensor Rank and the Ill-Posedness of the Best Low-Rank Approximation Problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5320726)
