Low-Rank Tucker Approximation of a Tensor From Streaming Data
This paper describes a new algorithm for computing a low-Tucker-rank approximation of a tensor. The method applies a randomized linear map to the tensor to obtain a sketch that captures the important directions within each mode, as well as the interactions among the modes. The sketch can be extracted from streaming or distributed data or with a single pass over the tensor, and it uses storage proportional to the degrees of freedom in the output Tucker approximation. The algorithm does not require a second pass over the tensor, although it can exploit another view to compute a superior approximation. The paper provides a rigorous theoretical guarantee on the approximation error. Extensive numerical experiments show that that the algorithm produces useful results that improve on the state of the art for streaming Tucker decomposition.
Code (2)
Methods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Fast Tucker Rank Reduction for Non-Negative Tensors Using Mean-Field Approximation
We present an efficient low-rank approximation algorithm for non-negative tensors. The algorithm is derived from our two findings: First, we show that rank-1 approximation for tensors can be viewed as a mean-field approx…
Tensor DecompositionNear-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions
We study low rank approximation of tensors, focusing on the tensor train and Tucker decompositions, as well as approximations with tree tensor networks and more general tensor networks. For tensor train decomposition, we…
Dimensionality ReductionTensor DecompositionTensor NetworksThe Exact Solution to Rank-1 L1-norm TUCKER2 Decomposition
We study rank-1 {L1-norm-based TUCKER2} (L1-TUCKER2) decomposition of 3-way tensors, treated as a collection of $N$ $D \times M$ matrices that are to be jointly decomposed. Our contributions are as follows. i) We prove t…
Combinatorial OptimizationFast Low-Rank Tensor Decomposition by Ridge Leverage Score Sampling
Low-rank tensor decomposition generalizes low-rank matrix approximation and is a powerful technique for discovering low-dimensional structure in high-dimensional data. In this paper, we study Tucker decompositions and us…
regressionTensor DecompositionBlack-Box Approximation and Optimization with Hierarchical Tucker Decomposition
We develop a new method HTBB for the multidimensional black-box approximation and gradient-free optimization, which is based on the low-rank hierarchical Tucker decomposition with the use of the MaxVol indices selection …