A New Sampling Technique for Tensors.

摘要: In this paper we propose new techniques to sample arbitrary third-order tensors, with an objective of speeding up tensor algorithms that have recently gained popularity in machine learning. Our main contribution is a way select, biased random way, only $O(n^{1.5}/\epsilon^2)$ the possible $n^3$ elements while still achieving each three goals: \\ {\em (a) sparsification}: for has be formed from samples, compute very few get good spectral approximation, and orthogonal tensors (b) completion:} recover exactly low-rank small number samples via alternating least squares, or (c) factorization:} approximating factors corrupted by noise. sampling can used along existing tensor-based speed them up, removing computational bottleneck these methods.