Sample Complexity of Low-rank Tensor Recovery from Uniformly Random Entries

2024/08/07 by Hiroki Hamaguchi, Hamaguchi, Hiroki, Shin-ichi Tanigawa +1 · 1 citation
Computer Science · Engineering · Mathematics · #Algebraic Geometry (math.AG) #Combinatorics (math.CO) #Computational Physics and Python Applications #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Probability (math.PR) #Sparse and Compressive Sensing Techniques #Tensor decomposition and applications

paper · pdf · doi:10.48550/arxiv.2408.03504

openalex publication_date 2024/08/07 · openalex created_date 2024/10/22 · openalex updated_date 2026/07/28

Abstract

We show that a generic tensor T∈ \mathbbF^{n× n× …× n} of order k and CP rank d can be uniquely recovered from nlog n+dnlog log n +o(nlog log n) uniformly random entries with high probability if d and k are constant and \mathbbF∈ \ℝ,ℂ\. The bound is tight up to the coefficient of the second leading term and improves on the existing O(n^(k)/(2)\rm polylog(n)) upper bound for order k tensors. The bound is obtained by showing that the projection of the Segre variety to a random axis-parallel linear subspace preserves d-identifiability with high probability if the dimension of the subspace is nlog n+dnlog log n +o(nlog log n) and n is sufficiently large.

Cited by

• Sufficient conditions for bipartite rigidity, symmetric completability and hyperconnectivity of graphs

Related

• Typical ranks of random order-three tensors
• Provable Near-Optimal Low-Multilinear-Rank Tensor Recovery
• The Average Spectrum Norm and Near-Optimal Tensor Completion
• On Polynomial Time Methods for Exact Low Rank Tensor Completion
• Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan