2020/07/01 by Christina Lee Yu, Yu, Christina Lee, Xumei Xi +1
Engineering · Mathematics · Medicine · #Advanced Neuroimaging Techniques and Applications #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Numerical Analysis (math.NA) #Sparse and Compressive Sensing Techniques #Tensor decomposition and applications
paper · pdf · doi:10.48550/arxiv.2007.00736
openalex publication_date 2020/07/01 · openalex created_date 2021/09/27 · openalex updated_date 2026/07/28
Tensor completion exhibits an interesting computational-statistical gap in terms of the number of samples needed to perform tensor estimation. While there are only Θ(tn) degrees of freedom in a t-order tensor with nt entries, the best known polynomial time algorithm requires O(nt/2) samples in order to guarantee consistent estimation. In this paper, we show that weak side information is sufficient to reduce the sample complexity to O(n). The side information consists of a weight vector for each of the modes which is not orthogonal to any of the latent factors along that mode; this is significantly weaker than assuming noisy knowledge of the subspaces. We provide an algorithm that utilizes this side information to produce a consistent estimator with O(n1+κ) samples for any small constant κ> 0. We also provide experiments on both synthetic and real-world datasets that validate our theoretical insights.