A New Sampling Technique for Tensors

02/17/2015
by   Srinadh Bhojanapalli, et al.
0

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 new way to select, in a biased random way, only O(n^1.5/ϵ^2) of the possible n^3 elements while still achieving each of the three goals: (a) tensor sparsification: for a tensor that has to be formed from arbitrary samples, compute very few elements to get a good spectral approximation, and for arbitrary orthogonal tensors (b) tensor completion: recover an exactly low-rank tensor from a small number of samples via alternating least squares, or (c) tensor factorization: approximating factors of a low-rank tensor corrupted by noise. Our sampling can be used along with existing tensor-based algorithms to speed them up, removing the computational bottleneck in these methods.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset

Sign in with Google

×

Use your Google Account to sign in to DeepAI

×

Consider DeepAI Pro