Recovery algorithms for high-dimensional rank one tensors

2017/11/10 by Krieg, David, Rudolf, Daniel
#41A15 #41A25 #41A63 #65D99 #65Y20 #FOS: Mathematics #Numerical Analysis (math.NA)

paper · doi:10.48550/arxiv.1711.03986

Abstract

We present deterministic algorithms for the uniform recovery of d-variate rank one tensors from function values. These tensors are given as product of d univariate functions whose rth weak derivative is bounded by M. The recovery problem is known to suffer from the curse of dimensionality for M≥ 2^r r!. For smaller M, a randomized algorithm is known which breaks the curse. We construct a deterministic algorithm which is even less costly. In fact, we completely characterize the tractability of this problem by three different ranges of the parameter M.

Related

• Optimal low rank tensor recovery
• Provable Near-Optimal Low-Multilinear-Rank Tensor Recovery
• On Polynomial Time Methods for Exact Low Rank Tensor Completion
• Tractability of the approximation of high-dimensional rank one tensors
• Optimal Low-Rank Tensor Recovery from Separable Measurements: Four Contractions Suffice