Tensor Rank and the Ill-Posedness of the Best Low-Rank Approximation Problem
From MaRDI portal
principal component analysismultiway arraystensor decompositionstensorstensor rankmultidimensional arraysparafaclow-rank tensor approximationsEckart-Young theoremnumerical multilinear algebracandecomphyperdeterminantsBrégman divergence of tensors
Factor analysis and principal components; correspondence analysis (62H25) Multilinear algebra, tensor calculus (15A69) Vector and tensor algebra, theory of invariants (15A72) Canonical forms, reductions, classification (15A21) Decomposition methods (49M27) Semialgebraic sets and related spaces (14P10) Vector spaces, linear dependence, rank, lineability (15A03) 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)- Adaptive low-rank approximations for operator equations: accuracy control and computational complexity
- Real rank two geometry
- Typical ranks of \(m\times n\times(m-1)n\) tensors with \(3\leq m\leq n\) over the real number field
- Structured matrix problems from tensors
- Computing symmetric rank for symmetric tensors
- Estimating a few extreme singular values and vectors for large-scale matrices in tensor train format
- A note on the gap between rank and border rank
- A TT-based hierarchical framework for decomposing high-order tensors
- New estimations on the upper bounds for the nuclear norm of a tensor
- Constrained optimization with low-rank tensors and applications to parametric problems with PDEs
- Stability of low-rank tensor representations and structured multilevel preconditioning for elliptic PDEs
- Multilinear Control Systems Theory
- Dynamically orthogonal tensor methods for high-dimensional nonlinear PDEs
- Weighted Moore-Penrose inverses of arbitrary-order tensors
- A hyperspace of convex bodies arising from tensor norms
- Even-order Toeplitz tensor: framework for multidimensional structured linear systems
- Tensor completion via multi-directional partial tensor nuclear norm with total variation regularization
- The numerical approximation of nonlinear functionals and functional differential equations
- Tensor robust principal component analysis via the tensor nuclear over Frobenius norm
- Accelerated doubly stochastic gradient descent for tensor CP decomposition
- Diagonal Gaussian mixture models and higher order tensor decompositions
- A geometric approach to linear cryptanalysis
- The Segre cone of Banach spaces and multilinear mappings
- Pseudospectra localizations for generalized tensor eigenvalues to seek more positive definite tensors
- Higher-order principal component analysis for the approximation of tensors in tree-based low-rank formats
- Multi-dimensional image recovery via fully-connected tensor network decomposition under the learnable transforms
- Separability of Hermitian tensors and PSD decompositions
- Robust and resource-efficient identification of two hidden layer neural networks
- Efficient alternating least squares algorithms for low multilinear rank approximation of tensors
- Cross approximation in tensor electron density computations
- An equi-directional generalization of adaptive cross approximation for higher-order tensors
- Tensorized low-rank circulant preconditioners for multilevel Toeplitz linear systems from high-dimensional fractional Riesz equations
- Tensor train spectral method for learning of hidden Markov models (HMM)
- Multilayer tensor factorization with applications to recommender systems
- Three-way clustering of multi-tissue multi-individual gene expression data using semi-nonnegative tensor decomposition
- Incremental algorithms for truncated higher-order singular value decompositions
- Least-squares bilinear clustering of three-way data
- Topology of tensor ranks
- The geometric measure of entanglement for a symmetric pure state with non-negative amplitudes
- Low-rank tensor methods for Markov chains with applications to tumor progression models
- On Kruskal's theorem that every \(3{\times}3{\times}3\) array has rank at most 5
- Canonical forms of order-\(k\) \((k = 2, 3, 4)\) symmetric tensors of format \(3\times\cdots\times 3\) over prime fields
- Inertial accelerated SGD algorithms for solving large-scale lower-rank tensor CP decomposition problems
- Contextual tensor decomposition by projected alternating least squares
- Learning diagonal Gaussian mixture models and incomplete tensor decompositions
- IETI-based low-rank method for PDE-constrained optimization
- Convergence rate analysis for the higher order power method in best rank one approximations of tensors
- New efficient data-driven reduced order models for oscillatory dynamics
- Simultaneous component analysis by means of Tucker3
- Multiple points, scheme rank and symmetric tensor rank
- A note on the three-way generalization of the Jordan canonical form
- When does subtracting a rank-one approximation decrease tensor rank?
- Rank classification of 2 2 2 2 2 tensors over F₂
- Lower bounds on the rank and symmetric rank of real tensors
- Efficient multi-scale computation of products of orbitals in electronic structure calculations
- Cayley's hyperdeterminant: A combinatorial approach via representation theory
- On polynomial time methods for exact low-rank tensor completion
- Canonical forms of 2 2 2 and 2 2 2 2 arrays over F₂ and F₃
- Musings on multilinear fitting
- Best \(k\)-layer neural network approximations
- On the equivalence between low-rank matrix completion and tensor rank
- The Computation of Low Multilinear Rank Approximations of Tensors via Power Scheme and Random Projection
- The nonconvex tensor robust principal component analysis approximation model via the weighted _p-norm regularization
- The low-rank approximation of fourth-order partial-symmetric and conjugate partial-symmetric tensor
- A neural tensor decomposition model for high-order sparse data recovery
- Adaptive frame-based color image denoising
- On the closedness and geometry of tensor network state sets
- A robust adaptive decomposable Volterra filter based on the hyperbolic tangent Leclerc function and its performance analysis
- Symmetric tensor rank and scheme rank: an upper bound in terms of secant varieties
- Tensors in computations
- Bayesian inversion for electromyography using low-rank tensor formats
- Triangular decomposition of CP factors of a third-order tensor with application to solving nonlinear systems of equations
- Generalized inverses of Boolean tensors via the Einstein product
- 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
- HOID: higher order interpolatory decomposition for tensors based on Tucker representation
- scientific article; zbMATH DE number 7387190 (Why is no real title available?)
- Successive Rank-One Approximations for Nearly Orthogonally Decomposable Symmetric Tensors
- An efficient reduced-order model based on dynamic mode decomposition for parameterized spatial high-dimensional PDEs
- On the Tensor SVD and the Optimal Low Rank Orthogonal Approximation of Tensors
- Proper generalized decompositions and separated representations for the numerical solution of high dimensional stochastic problems
- On the generic and typical ranks of 3-tensors
- Constrained Candecomp/Parafac via the Lasso
- News algorithms for tensor decomposition based on a reduced functional
- Numerical solution of the Boltzmann equation with S-model collision integral using tensor decompositions
- Low-rank tensor methods for partial differential equations
- Tensor theta norms and low rank recovery
- Pencil-based algorithms for tensor rank decomposition are not stable
- Global convergence of rank-one PGD approximations by alternate minimization
- Minimal divergence for border rank-2 tensor approximation
- 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
- SOTT: greedy approximation of a tensor as a sum of tensor trains
- Preconditioners and tensor product solvers for optimal control problems from chemotaxis
- Matrix factorization for low-rank tensor completion using framelet prior
- Tensor network alternating linear scheme for MIMO Volterra system identification
- Rank 1 decompositions of symmetric tensors outside a fixed support
- Inference for low-rank tensors -- no need to debias
- Subtracting a best rank-1 approximation may increase tensor rank
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)
