On the nuclear norm and the singular value decomposition of tensors

DOI10.1007/S10208-015-9264-XzbMATH Open1343.15016arXiv1308.3860OpenAlexW2130150942MaRDI QIDQ300892FDOQ300892

Harm Derksen

Publication date: 29 June 2016

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

Abstract: Finding the rank of a tensor is a problem that has many applications. Unfortunately it is often very difficult to determine the rank of a given tensor. Inspired by the heuristics of convex relaxation, we consider the nuclear norm instead of the rank of a tensor. We determine the nuclear norm of various tensors of interest. Along the way, we also do a systematic study various measures of orthogonality in tensor product spaces and we give a new generalization of the Singular Value Decomposition to higher order tensors.

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

Recommendations

• Singular vectors of orthogonally decomposable tensors
• A Jacobi-Type Method for Computing Orthogonal Tensor Decompositions
• Symmetric tensor nuclear norms
• On the Tensor SVD and the Optimal Low Rank Orthogonal Approximation of Tensors
• Orthogonal tensor decompositions

zbMATH Keywords

tensor productmatrix completionnuclear normsingular value decompositiontensor decompositionCANDECOMPPARFAC

Mathematics Subject Classification ID

Eigenvalues, singular values, and eigenvectors (15A18) Multilinear algebra, tensor calculus (15A69) Matrix completion problems (15A83) Numerical solutions to overdetermined systems, pseudoinverses (65F20) Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60)

Cites Work

• Matrix completion from noisy entries
• Analysis of individual differences in multidimensional scaling via an \(n\)-way generalization of ``Eckart-Young decomposition
• Powers of tensors and fast matrix multiplication
• Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics
• Exact matrix completion via convex optimization
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• A Multilinear Singular Value Decomposition
• Tensor Rank and the Ill-Posedness of the Best Low-Rank Approximation Problem
• Tensor completion and low-n-rank tensor recovery via convex optimization
• Infinite dimensional analysis. A hitchhiker's guide.
• Most Tensor Problems Are NP-Hard
• Gaussian elimination is not optimal
• Title not available (Why is that?)
• Multiplying matrices faster than coppersmith-winograd
• Produits tensoriels topologiques et espaces nucléaires
• Matrix multiplication via arithmetic progressions
• On the ranks and border ranks of symmetric tensors
• \(0(n^{2.7799})\) complexity for \(n\times n\) approximate matrix multiplication
• Beyond the Alder-Strassen bound.
• Apolarity for determinants and permanents of generic matrices
• Tensor rank is NP-complete
• The rank of \(n \times n\) matrix multiplication is at least \(3n^2 - 2\sqrt{2}n^{\frac{3}{2}} - 3n\)
• Blind Multilinear Identification
• New Lower Bounds for the Rank of Matrix Multiplication
• Multiarray signal processing: tensor decomposition meets compressed sensing
• A Theory of Cross-Spaces. (AM-26)
• The permanent of a square matrix
• An inequality of Hadamard type for permanents

Cited In (29)

• Fano schemes for generic sums of products of linear forms
• Tensor approximation approach to calculation of singular values and vectors for SVD problem
• Bad and good news for Strassen's laser method: border rank of \(\mathrm{Perm}_3\) and strict submultiplicativity
• Algebraic Methods for Tensor Data
• A bound for the Waring rank of the determinant via syzygies
• Numerical stability and tensor nuclear norm
• Rank and border rank of Kronecker powers of tensors and Strassen's laser method
• Explicit tensors of border rank at least 2d−2 in K^d ⊗ K^d ⊗ K^d in arbitrary characteristic
• Relations of the nuclear norm of a tensor and its matrix flattenings
• Further results on tensor nuclear norms
• Bounds on Dimension Reduction in the Nuclear Norm
• The zonoid algebra, generalized mixed volumes, and random determinants
• Completely positive tensor recovery with minimal nuclear value
• Symmetric Tensor Nuclear Norms
• Combinatorial methods for the spectral \(p\)-norm of hypermatrices
• An improved upper bound for the Waring rank of the determinant
• Singular Value Decompositions and Low Rank Approximations of Tensors
• Une décomposition en valeurs singulières d'un élément d'un produit tensoriel de k espaces de Hilbert séparables
• A concise proof to the spectral and nuclear norm bounds through tensor partitions
• A General Theory of Singular Values with Applications to Signal Denoising
• On the tensor rank of $3\times 3$ permanent and determinant
• On norm compression inequalities for partitioned block tensors
• On the tensor spectral \(p\)-norm and its dual norm via partitions
• Nuclear norm of higher-order tensors
• Highly entangled tensors
• New lower bounds for matrix multiplication and
• Tensor denoising via dual Schatten norms
• Approximate real symmetric tensor rank
• Bounds on the spectral norm and the nuclear norm of a tensor based on tensor partitions

This page was built for publication: On the nuclear norm and the singular value decomposition of tensors

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