A New Sampling Technique for Tensors

Abstract

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}/{\epsilon }^2)$ of the possible $n^3$ elements while still achieving each of the three goals: \\ {\em (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 {\em (b) tensor completion:} recover an exactly low-rank tensor from a small number of samples via alternating least squares, or {\em (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.

29 pages,3 figures

References in corpus (7)

• Scalable Tensor Factorizations for Incomplete Data
• Square Deal: Lower Bounds and Improved Relaxations for Tensor Recovery
• A Spectral Algorithm for Latent Dirichlet Allocation
• On degeneration of tensors and algebras
• Provable Tensor Factorization with Missing Data
• A statistical model for tensor PCA
• Tensor sparsification via a bound on the spectral norm of random tensors

Cited by in corpus (9)

• Adaptive Sampling of RF Fingerprints for Fine-grained Indoor Localization
• Fast and Guaranteed Tensor Decomposition via Sketching
• Uniform Hypergraph Partitioning: Provable Tensor Methods and Sampling Techniques
• Tensor Completion Algorithms in Big Data Analytics
• Cross: Efficient Low-rank Tensor Completion
• Streaming Coresets for Symmetric Tensor Factorization
• Implicit Regularization and Entrywise Convergence of Riemannian Optimization for Low Tucker-Rank Tensor Completion
• Robust Max Entrywise Error Bounds for Tensor Estimation from Sparse Observations via Similarity Based Collaborative Filtering
• Spatio-Temporal Tensor Sketching via Adaptive Sampling