Publications Details

Publications / Other Report

The Average Spectrum Norm and Near-Optimal Tensor Completion

Lopez, Oscar F.; Lehoucq, Rich; Llosa-Vite, Carlos; Prasadan, Arvind; Dunlavy, Daniel M.

We propose the average spectrum norm to study the minimum number of measurements required to approximate a multidimensional array (i.e., sample complexity) via low-rank tensor recovery. Our focus is on the tensor completion problem, where the aim is to estimate a multiway array using a subset of tensor entries corrupted by noise. Our average spectrum norm-based analysis provides near-optimal sample complexities, exhibiting dependence on the ambient dimensions and rank that do not suffer from exponential scaling as the order increases.