Fast and Guaranteed Tensor Decomposition via Sketching

Abstract

Tensor CANDECOMP/PARAFAC (CP) decomposition has wide applications in statistical learning of latent variable models and in data mining. In this paper, we propose fast and randomized tensor CP decomposition algorithms based on sketching. We build on the idea of count sketches, but introduce many novel ideas which are unique to tensors. We develop novel methods for randomized computation of tensor contractions via FFTs, without explicitly forming the tensors. Such tensor contractions are encountered in decomposition methods such as tensor power iterations and alternating least squares. We also design novel colliding hashes for symmetric tensors to further save time in computing the sketches. We then combine these sketching ideas with existing whitening and tensor power iterative techniques to obtain the fastest algorithm on both sparse and dense tensors. The quality of approximation under our method does not depend on properties such as sparsity, uniformity of elements, etc. We apply the method for topic modeling and obtain competitive results.

29 pages. Appeared in Proceedings of Advances in Neural Information Processing Systems (NIPS), held at Montreal, Canada in 2015

References in corpus (2)

• DFacTo: Distributed Factorization of Tensors
• A New Sampling Technique for Tensors

Cited by in corpus (20)

• Tensor Networks for Dimensionality Reduction and Large-Scale Optimizations. Part 2 Applications and Future Perspectives
• Beating the Perils of Non-Convexity: Guaranteed Training of Neural Networks using Tensor Methods
• STORE: Sparse Tensor Response Regression and Neuroimaging Analysis
• A literature survey of matrix methods for data science
• Tensor Random Projection for Low Memory Dimension Reduction
• T-Singular Values and T-Sketching for Third Order Tensors
• Orthogonalized ALS: A Theoretically Principled Tensor Decomposition Algorithm for Practical Use
• Low-Rank Tucker Approximation of a Tensor From Streaming Data
• Multiresolution Tensor Learning for Efficient and Interpretable Spatial Analysis
• Marchenko-Pastur law with relaxed independence conditions
• Partially Observed Dynamic Tensor Response Regression
• PLANC: Parallel Low Rank Approximation with Non-negativity Constraints
• Spectral Methods for Nonparametric Models
• A near-optimal algorithm for approximating the John Ellipsoid
• Streaming Coresets for Symmetric Tensor Factorization
• Higher-order Count Sketch: Dimensionality Reduction That Retains Efficient Tensor Operations
• ISLET: Fast and Optimal Low-rank Tensor Regression via Importance Sketching
• Lower Memory Oblivious (Tensor) Subspace Embeddings with Fewer Random Bits: Modewise Methods for Least Squares
• A Sampling-Based Method for Tensor Ring Decomposition
• Efficient Tensor Contraction via Fast Count Sketch