Goto

Collaborating Authors

Fast and Guaranteed Tensor Decomposition via Sketching

Neural Information Processing Systems

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 com- putation of tensor contractions via FFTs, without explicitly forming the tensors. Such tensor contractions are encountered in decomposition methods such as ten- sor power iterations and alternating least squares.


Fast and Guaranteed Tensor Decomposition via Sketching

arXiv.org Machine Learning

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.


Multi-dimensional Tensor Sketch

arXiv.org Machine Learning

Sketching refers to a class of randomized dimensionality reduction methods that aim to preserve relevant information in large-scale datasets. They have efficient memory requirements and typically require just a single pass over the dataset. Efficient sketching methods have been derived for vector and matrix-valued datasets. When the datasets are higher-order tensors, a naive approach is to flatten the tensors into vectors or matrices and then sketch them. However, this is inefficient since it ignores the multi-dimensional nature of tensors. In this paper, we propose a novel multi-dimensional tensor sketch (MTS) that preserves higher order data structures while reducing dimensionality. We build this as an extension to the popular count sketch (CS) and show that it yields an unbiased estimator of the original tensor. We demonstrate significant advantages in compression ratios when the original data has decomposable tensor representations such as the Tucker, CP, tensor train or Kronecker product forms. We apply MTS to tensorized neural networks where we replace fully connected layers with tensor operations. We achieve nearly state of art accuracy with significant compression on image classification benchmarks.


Online and Differentially-Private Tensor Decomposition

Neural Information Processing Systems

Tensor decomposition is positioned to be a pervasive tool in the era of big data. In this paper, we resolve many of the key algorithmic questions regarding robustness, memory efficiency, and differential privacy of tensor decomposition. We propose simple variants of the tensor power method which enjoy these strong properties. We propose the first streaming method with a linear memory requirement. Moreover, we present a noise calibrated tensor power method with efficient privacy guarantees.


Tensor Grid Decomposition with Application to Tensor Completion

arXiv.org Machine Learning

The recently prevalent tensor train (TT) and tensor ring (TR) decompositions can be graphically interpreted as (locally) linear interconnected latent factors and possess exponential decay of correlation. The projected entangled pair state (PEPS, also called two-dimensional TT) extends the spatial dimension of TT and its polycyclic structure can be considered as a square grid. Compared with TT, its algebraic decay of correlation means the enhancement of interaction between tensor modes. In this paper we adopt the PEPS and develop a tensor grid (TG) decomposition with its efficient realization termed splitting singular value decomposition (SSVD). By utilizing the alternating least squares (ALS) a method called TG-ALS is used to interpolate the missing entries of a tensor from its partial observations. Different kinds of data are used in the experiments, including synthetic data, color images and real-world videos. Experimental results demonstrate that the TG has much power of representation than TT and TR.