Entrywise tensor-train approximation of large tensors via random embeddings

Abstract

The theory of low-rank tensor-train approximation is well understood when the approximation error is measured in the Frobenius norm. The entrywise maximum norm is equally important but is significantly weaker for large tensors, making the estimates obtained via the Frobenius norm and norm equivalence pessimistic or even meaningless. In this article, we derive a direct estimate of the entrywise approximation error that is applicable in some of these cases. The estimate is given in terms of the higher-order generalization of the matrix factorization norm, and its proof is based on the tensor-structured Hanson--Wright inequality. The theoretical results are accompanied by numerical experiments carried out with the method of alternating projections.

arXiv commentAccepted for publication in SIAM Journal on Matrix Analysis and Applications

References in corpus (9)

• The density-matrix renormalization group in the age of matrix product states
• Efficient classical simulation of slightly entangled quantum computations
• Estimates of moments and tails of Gaussian chaoses
• Matrix Completion via Max-Norm Constrained Optimization
• Operator Norm Inequalities between Tensor Unfoldings on the Partition Lattice
• Low-Rank Matrix Approximation in the Infinity Norm
• Low-rank nonnegative tensor approximation via alternating projections and sketching
• Tensor train completion: local recovery guarantees via Riemannian optimization
• On the distance to low-rank matrices in the maximum norm

Cited by in corpus (2)

• Quasioptimal alternating projections and their use in low-rank approximation of matrices and tensors
• When big data actually are low-rank, or entrywise approximation of certain function-generated matrices