In this work, we introduce a fast adaptive algorithm for CANDECOMP/PARAFAC decomposition of streaming three-way tensors using randomized sketching techniques. By leveraging randomized least-squares regression and approximating matrix multiplication, we propose an efficient first-order estimator to minimize an exponentially weighted recursive leastsquares cost function. Our algorithm is fast, requiring a low computational complexity and memory storage.
- Our MATLAB code requires the Tensor Toolbox which is already attached to this repository.
- MATLAB 2019a
Quick Start: Just run the file DEMO.m
- PARAFAC_SDT, PARAFAC_RLST (2009): D. Nion et al. “Adaptive algorithms to track the PARAFAC decomposition of a third-order tensor,” IEEE Trans. Signal Process., 2009.
- SOAP (2017): N.V. Dung et al. “Second-order optimization based adaptive PARAFAC decomposition of three-way tensors,” Digit. Signal Process., 2017.
- OLCP (2016): S. Zhou et al. “Accelerating online CP decompositions for higher order tensors,” ACM Int. Conf. Knowl. Discover. Data Min., 2016
- OLSTEC (2017): H. Kasai, “Fast online low-rank tensor subspace tracking by CP decomposition using recursive least squares from incomplete observations,” Neurocomput., 2017
Running time and estimation accuracy of adaptive CP algorithms
This code is free and open source for research purposes. If you use this code, please acknowledge the following paper.
[1] L.T. Thanh, K. Abed-Meraim, N.L. Trung, A. Hafiance. "A fast randomized adaptive CP decomposition for streaming tensors". IEEE Int. Conf. Acoust. Speech Signal Process. (IEEE ICASSP), 2021.