# Effective Streaming Low-tubal-rank Tensor Approximation via Frequent Directions

arXiv: https://arxiv.org/abs/2108.10129 · HTML: https://mlsanity.com/paper/2108.10129/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 52 references that are in the map.
- First posted on arXiv 23 Aug 2021.

## Builds on (most cited first, 13 of 13)

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Tensor Robust Principal Component Analysis with A New Tensor Nuclear Norm](https://mlsanity.com/paper/1804.03728/) (2018)
- [Exact tensor completion using t-SVD](https://mlsanity.com/paper/1502.04689/) (2015)
- [Frequent Directions : Simple and Deterministic Matrix Sketching](https://mlsanity.com/paper/1501.01711/) (2015)
- [Tensor Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Tensors via Convex Optimization](https://mlsanity.com/paper/1708.04181/) (2017)
- [Fast and Guaranteed Tensor Decomposition via Sketching](https://mlsanity.com/paper/1506.04448/) (2015)
- [Low-Rank Tucker Approximation of a Tensor From Streaming Data](https://mlsanity.com/paper/1904.10951/) (2019)
- [Efficient Linear Bandits through Matrix Sketching](https://mlsanity.com/paper/1809.11033/) (2018)
- [Grassmannian Optimization for Online Tensor Completion and Tracking with the t-SVD](https://mlsanity.com/paper/2001.11419/) (2020)
- [Effective Tensor Sketching via Sparsification](https://mlsanity.com/paper/1710.11298/) (2017)
- [Low-Rank Autoregressive Tensor Completion for Multivariate Time Series Forecasting](https://mlsanity.com/paper/2006.10436/) (2020)
- [Randomized Approximation of the Gram Matrix: Exact Computation and Probabilistic Bounds](https://mlsanity.com/paper/1310.1502/) (2013)
- [Randomized Online CP Decomposition](https://mlsanity.com/paper/2007.10798/) (2020)

## Built on by (most cited first, 1 of 1)

- [An Improved Frequent Directions Algorithm for Low-Rank Approximation via Block Krylov Iteration](https://mlsanity.com/paper/2109.11703/) (2021)

## Abstract (arXiv)

Low-tubal-rank tensor approximation has been proposed to analyze large-scale and multi-dimensional data. However, finding such an accurate approximation is challenging in the streaming setting, due to the limited computational resources. To alleviate this issue, this paper extends a popular matrix sketching technique, namely Frequent Directions, for constructing an efficient and accurate low-tubal-rank tensor approximation from streaming data based on the tensor Singular Value Decomposition (t-SVD). Specifically, the new algorithm allows the tensor data to be observed slice by slice, but only needs to maintain and incrementally update a much smaller sketch which could capture the principal information of the original tensor. The rigorous theoretical analysis shows that the approximation error of the new algorithm can be arbitrarily small when the sketch size grows linearly. Extensive experimental results on both synthetic and real multi-dimensional data further reveal the superiority of the proposed algorithm compared with other sketching algorithms for getting low-tubal-rank approximation, in terms of both efficiency and accuracy.