Tensor Rank and the Ill-Posedness of the Best Low-Rank Approximation Problem

DOI10.1137/06066518XzbMath1167.14038arXivmath/0607647OpenAlexW2132267493WikidataQ60307005 ScholiaQ60307005MaRDI QIDQ5320726

Lek-Heng Lim, Vin De Silva

Publication date: 22 July 2009

Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

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

zbMATH Keywords

principal component analysishyperdeterminantscandecompparafactensor ranktensorstensor decompositionsmultidimensional arrayslow-rank tensor approximationsEckart-Young theoremnumerical multilinear algebramultiway arraysBrégman divergence of tensors

Mathematics Subject Classification ID

Factor analysis and principal components; correspondence analysis (62H25) Vector and tensor algebra, theory of invariants (15A72) Semialgebraic sets and related spaces (14P10) Decomposition methods (49M27) Multilinear algebra, tensor calculus (15A69) Vector spaces, linear dependence, rank, lineability (15A03) Canonical forms, reductions, classification (15A21) General topics in the theory of data (68P01)

Related Items

Convex Bodies Associated to Tensor Norms, Estimating latent trends in multivariate longitudinal data via Parafac2 with functional and structural constraints, Low-Rank Tucker Approximation of a Tensor from Streaming Data, Randomized Algorithms for Rounding in the Tensor-Train Format, Tensors in computations, Separability of Hermitian tensors and PSD decompositions, SOTT: Greedy Approximation of a Tensor as a Sum of Tensor Trains, Linear convergence of an alternating polar decomposition method for low rank orthogonal tensor approximations, Low-rank tensor methods for partial differential equations, The condition number of many tensor decompositions is invariant under Tucker compression, High‐fidelity tensor‐decomposition based matrix formation for isogeometric buckling analysis of laminated shells with solid‐shell formulation, Tensor product approach to modelling epidemics on networks, Spurious Valleys, NP-Hardness, and Tractability of Sparse Matrix Factorization with Fixed Support, Numerical solution of the Boltzmann equation with S-model collision integral using tensor decompositions, Minimality of tensors of fixed multilinear rank, Unnamed Item, Tensor completion via multi-directional partial tensor nuclear norm with total variation regularization, Incremental algorithms for truncated higher-order singular value decompositions, 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, A geometric approach to linear cryptanalysis, Accelerated doubly stochastic gradient descent for tensor CP decomposition, Least-squares bilinear clustering of three-way data, The Computation of Low Multilinear Rank Approximations of Tensors via Power Scheme and Random Projection, On Best Low Rank Approximation of Positive Definite Tensors, Further results on tensor nuclear norms, Non-negative low-rank approximations for multi-dimensional arrays on statistical manifold, TR-STF: a fast and accurate tensor ring decomposition algorithm via defined scaled tri-factorization, Variational Bayesian inference for CP tensor completion with subspace information, Factor Models for High-Dimensional Tensor Time Series, Unnamed Item, A Riemannian Trust Region Method for the Canonical Tensor Rank Approximation Problem, Large Margin Low Rank Tensor Analysis, Real rank boundaries and loci of forms, The maximally entangled symmetric state in terms of the geometric measure, Hankel Tensor Decompositions and Ranks, Multiresolution Low-rank Tensor Formats, Hermitian Tensor Decompositions, HIGH-ORDER COPOSITIVE TENSORS AND ITS APPLICATIONS, Algebraic Methods for Tensor Data, Approximate tensor decompositions: Disappearance of many separations, FFT-based Kronecker product approximation to micromagnetic long-range interactions, Low-Rank Tensor Recovery using Sequentially Optimal Modal Projections in Iterative Hard Thresholding (SeMPIHT), Total variation based tensor decomposition for multi‐dimensional data with time dimension, Typical ranks ofm×n× (m− 1)ntensors with 3 ≤m≤nover the real number field, Canonical forms of order-k(k= 2, 3, 4) symmetric tensors of format 3 × … × 3 over prime fields, On the hyperdeterminant for 2×2×3 arrays, Subtracting a best rank-1 approximation may increase tensor rank, Optimal Sparse Singular Value Decomposition for High-Dimensional High-Order Data, A Low-Rank Tensor Method for PDE-Constrained Optimization with Isogeometric Analysis, The Segre cone of Banach spaces and multilinear mappings, A TT-Based Hierarchical Framework for Decomposing High-Order Tensors, Tensor networks for MIMO LPV system identification, On best rank-2 and rank-(2,2,2) approximations of order-3 tensors, Pencil-Based Algorithms for Tensor Rank Decomposition are not Stable, From Computation to Comparison of Tensor Decompositions, Numerical Computation for Orthogonal Low-Rank Approximation of Tensors, The Dynamics of Swamps in the Canonical Tensor Approximation Problem, Numerical algorithms for high-performance computational science, Preconditioners and Tensor Product Solvers for Optimal Control Problems from Chemotaxis, Incremental CP Tensor Decomposition by Alternating Minimization Method, Systems of Polynomial Equations, Higher-Order Tensor Decompositions, and Multidimensional Harmonic Retrieval: A Unifying Framework. Part II: The Block Term Decomposition, Adaptive low-rank approximations for operator equations: Accuracy control and computational complexity, News Algorithms for tensor decomposition based on a reduced functional, Multilinear Control Systems Theory, Fast Multidimensional Convolution in Low-Rank Tensor Formats via Cross Approximation, Lower Memory Oblivious (Tensor) Subspace Embeddings with Fewer Random Bits: Modewise Methods for Least Squares, On the Uniqueness and Perturbation to the Best Rank-One Approximation of a Tensor, Bayesian inversion for electromyography using low-rank tensor formats, Computing the Gradient in Optimization Algorithms for the CP Decomposition in Constant Memory through Tensor Blocking, Generalized inverses of Boolean tensors via the Einstein product, A Recursive Eigenspace Computation for the Canonical Polyadic Decomposition, Guarantees for Existence of a Best Canonical Polyadic Approximation of a Noisy Low-Rank Tensor, Estimating a Few Extreme Singular Values and Vectors for Large-Scale Matrices in Tensor Train Format, Global convergence of rank-one PGD approximations by alternate minimization, Minimal divergence for border rank-2 tensor approximation, Matrix Rigidity and the Ill-Posedness of Robust PCA and Matrix Completion, Convergence rate analysis for the higher order power method in best rank one approximations of tensors, New estimations on the upper bounds for the nuclear norm of a tensor, 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, Adaptive frame-based color image denoising, Efficient alternating least squares algorithms for low multilinear rank approximation of tensors, 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, On the nuclear norm and the singular value decomposition of tensors, Set evincing the ranks with respect to an embedded variety (symmetric tensor rank and tensor rank), On the rank of a Latin tensor, On the reduction of multivariate quadratic systems to best rank-1 approximation of three-way tensors, Recursive decomposition of multidimensional tensors, Simultaneous component analysis by means of Tucker3, Tensor-sparsity of solutions to high-dimensional elliptic partial differential equations, Low-rank approximation in the numerical modeling of the Farley-Buneman instability in ionospheric plasma, Proper generalized decompositions and separated representations for the numerical solution of high dimensional stochastic problems, On the convergence of a greedy rank-one update algorithm for a class of linear systems, Structured multi-way arrays and their applications, Computing symmetric rank for symmetric tensors, The subbundles of decomposable vector bundles over an elliptic curve, Symmetric tensor rank over an infinite field, Eigenvectors of tensors and algorithms for Waring decomposition, The geometry of algorithms using hierarchical tensors, Tensor network alternating linear scheme for MIMO Volterra system identification, On minimal subspaces in tensor representations, The convex geometry of linear inverse problems, Exact probabilities for typical ranks of \(2 \times 2 \times 2\) and \(3 \times 3 \times 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, Nearest-neighbor interaction systems in the tensor-train format, On the convergence of alternating minimization methods in variational PGD, 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, Adaptive near-optimal rank tensor approximation for high-dimensional operator equations, A proper generalized decomposition for the solution of elliptic problems in abstract form by using a functional Eckart-Young approach, Constructive representation of functions in low-rank tensor formats, Efficient multi-scale computation of products of orbitals in electronic structure calculations, Cayley's hyperdeterminant: A combinatorial approach via representation theory, Fast stray field computation on tensor grids, A fully symmetric nonlinear biorthogonal decomposition theory for random fields, Tensor rank is not multiplicative under the tensor product, Fast structured matrix computations: tensor rank and Cohn-Umans method, Sets computing the symmetric tensor rank, An upper bound for the tensor rank, The numerical approximation of nonlinear functionals and functional differential equations, Proper generalized decomposition for nonlinear convex problems in tensor Banach spaces, Decomposition of homogeneous polynomials with low rank, On the \(X\)-rank with respect to linearly normal curves, On the generic and typical ranks of 3-tensors, Tensor-based methods for numerical homogenization from high-resolution images, Higher-order principal component analysis for the approximation of tensors in tree-based low-rank formats, Regularity of tensor product approximations to square integrable functions, On the typical rank of real polynomials (or symmetric tensors) with a fixed border rank, Minimum (maximum) rank of sign pattern tensors and sign nonsingular tensors, A note on the three-way generalization of the Jordan canonical form, On the rank and the approximation of symmetric tensors, Weighted Moore-Penrose inverses of arbitrary-order tensors, On accelerating the regularized alternating least-squares algorithm for tensors, A hyperspace of convex bodies arising from tensor norms, Tensor networks and hierarchical tensors for the solution of high-dimensional partial differential equations, Multilayer tensor factorization with applications to recommender systems, On the interconnection between the higher-order singular values of real tensors, Equivariant minimax dominators of the MLE in the array normal model, A higher-order LQ decomposition for separable covariance models, Greedy low-rank approximation in Tucker format of solutions of tensor linear systems, Parallel tensor methods for high-dimensional linear PDEs, Diagonalization of tensors with circulant structure, Factorization strategies for third-order tensors, On polynomial time methods for exact low-rank tensor completion, On the ranks and border ranks of symmetric tensors, Rank 1 decompositions of symmetric tensors outside a fixed support, A note on nonclosed tensor formats, \(O(d \log N)\)-quantics approximation of \(N\)-\(d\) tensors in high-dimensional numerical modeling, Tensor ranks and symmetric tensor ranks are the same for points with low symmetric tensor rank, Tensor ranks for the inversion of tensor-product binomials, Randomized interpolative decomposition of separated representations, A numerical solver for high dimensional transient Fokker-Planck equation in modeling polymeric fluids, Robust reduced order modeling of heat transfer in a back step flow, 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 \(\ell_p\)-norm regularization, On uniqueness conditions for Candecomp/Parafac and Indscal with full column rank in one mode, Data-driven reduced order modeling based on tensor decompositions and its application to air-wall heat transfer in buildings, Subsets of a projective variety \(S\subset \mathbb P^n\) spanning a given \(P \in \mathbb P^n\), 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, Iterative algorithms for the post-processing of high-dimensional data, Stability analysis of hierarchical tensor methods for time-dependent PDEs, Twist tensor total variation regularized-reweighted nuclear norm based tensor completion for video missing area recovery, 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, Adaptive stochastic Galerkin FEM with hierarchical tensor representations, Inference for low-rank tensors -- no need to debias, On the typical rank of real binary forms, Learning diagonal Gaussian mixture models and incomplete tensor decompositions, Low Rank Tensor Manifold Learning, Polynomial foldings and rank of tensors, Solving the master equation without kinetic Monte Carlo: tensor train approximations for a CO oxidation model, The Optimization Landscape for Fitting a Rank-2 Tensor with a Rank-1 Tensor, Tensor-based dynamic mode decomposition, Solving phase-field models in the tensor train format to generate microstructures of bicontinuous composites, Successive Rank-One Approximations for Nearly Orthogonally Decomposable Symmetric Tensors, Interpolatory tensorial reduced order models for parametric dynamical systems, On Kruskal's theorem that every \(3{\times}3{\times}3\) array has rank at most 5, Tensor completion via fully-connected tensor network decomposition with regularized factors, Tensor Completion in Hierarchical Tensor Representations, Rank-1 Tensor Properties with Applications to a Class of Tensor Optimization Problems, On the closedness and geometry of tensor network state sets, Canonical forms of 2 × 2 × 2 and 2 × 2 × 2 × 2 symmetric tensors over prime fields, A note on the gap between rank and border rank, An upper bound for the real tensor rank and the real symmetric tensor rank in terms of the complex ranks, Statistically optimal and computationally efficient low rank tensor completion from noisy entries, The stratification by rank for homogeneous polynomials with border rank 5 which essentially depend on five variables, Topology of tensor ranks, An approximation method of CP rank for third-order tensor completion, Complex best \(r\)-term approximations almost always exist in finite dimensions, Reverse-order law for core inverse of tensors, Condition numbers for the tensor rank decomposition, High-order sum-of-squares structured tensors: theory and applications, Tensorized low-rank circulant preconditioners for multilevel Toeplitz linear systems from high-dimensional fractional Riesz equations, Conjugate gradient-like methods for solving general tensor equation with Einstein product, Discrete Fourier Transform Tensors and Their Ranks, The symmetric rank and decomposition of \(m\)-order \(n\)-dimensional \((n = 2,3,4)\) symmetric tensors over the binary field, Rank classification of tensors over, The average number of critical rank-one approximations to a tensor, Constrained Optimization with Low-Rank Tensors and Applications to Parametric Problems with PDEs, Rank properties and computational methods for orthogonal tensor decompositions, Learning algebraic models of quantum entanglement, Iterative low-rank approximation solvers for the extension method for fractional diffusion, Matrix factorization for low-rank tensor completion using framelet prior, Low Rank Symmetric Tensor Approximations, Maximum relative distance between real rank-two and rank-one tensors, On manifolds of tensors of fixed TT-rank, The Condition Number of Join Decompositions, Tensor decompositions and rank increment conjecture, Nuclear norm of higher-order tensors, On global convergence of alternating least squares for tensor approximation, Structured Matrix Problems from Tensors, The average condition number of most tensor rank decomposition problems is infinite, Lower bounds on the rank and symmetric rank of real tensors, Approximation rates for the hierarchical tensor format in periodic Sobolev spaces, Bounded-rank tensors are defined in bounded degree, Stability of low-rank tensor representations and structured multilevel preconditioning for elliptic PDEs, An equi-directional generalization of adaptive cross approximation for higher-order tensors, Multiple points, scheme rank and symmetric tensor rank, Dynamically orthogonal tensor methods for high-dimensional nonlinear PDEs, On the typical rank of real bivariate polynomials, Constrained Candecomp/Parafac via the Lasso, The special sign indeterminacy of the direct-fitting Parafac2 model: some implications, cautions, and recommendations for simultaneous component analysis, Tensor inversion and its application to the tensor equations with Einstein product, On the equivalence between low-rank matrix completion and tensor rank, Fast truncation of mode ranks for bilinear tensor operations, On the best rank-1 approximation to higher-order symmetric tensors, CLASSIFICATION OF ENTANGLEMENT IN SYMMETRIC STATES, The hyperdeterminant and triangulations of the 4-cube, Linear subspaces of symmetric tensors whose non-zero elements have at least a prescribed rank, Subtracting a best rank‐1 approximation from p × p × 2(p≥2) tensors, The geometric measure of entanglement for a symmetric pure state with non-negative amplitudes, 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, Numerical tensor calculus, Matrix completion and tensor rank, Random Projections for Low Multilinear Rank Tensors, The maximum rank of 2 × ⋯ × 2 tensors over 𝔽₂, Spectral Tensor-Train Decomposition, HOID: Higher Order Interpolatory Decomposition for Tensors Based on Tucker Representation, Computing images of polynomial maps, Cross approximation in tensor electron density computations, An inexact augmented Lagrangian method for computing strongly orthogonal decompositions of tensors, Unfoldings and the rank-one approximation of the tensor, Low-Rank Approximation and Completion of Positive Tensors, Jordan canonical form of three-way tensor with multilinear rank \((4,4,3)\), Approximation Algorithms for Tensor Clustering, Semialgebraic Geometry of Nonnegative Tensor Rank, 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, Canonical forms of 2 × 2 × 2 and 2 × 2 × 2 × 2 arrays over 𝔽₂and 𝔽₃, The Hitchhiker guide to: secant varieties and tensor decomposition, Three-mode factor analysis by means of Candecomp/Parafac, Tensors of nonnegative rank two, A literature survey of low-rank tensor approximation techniques, Optimization on the hierarchical Tucker manifold - applications to tensor completion, A note on the ranks of 2 × 2 × 2 and 2 × 2 × 2 × 2 tensors, 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, Real rank two geometry