Programming codes

ROLCP: A fast randomized adaptive CP decomposition for streaming tensors

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 least-squares cost function. Our algorithm is fast, requiring a low computational complexity and memory storage.

Fig: Streaming tensors


Fig: Average running time of adaptive algorithms on different synthetic tensors.	Fig: Performance of six adaptive CP algorithms

Download

MATLAB code can be downloaded here.

Requirement

Our code requires the Tensor Toolbox http://www.tensortoolbox.org/.

Demo

Quick Start: Run the file DEMO.m

State-of-the-art algorithms for comparison

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.2.

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

Reference

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, and A. Hafiance. “A fast randomized adaptive CP decomposition for streaming tensors”. IEEE Int. Conf. Acoust. Speech Signal Process. (ICASSP), 2021. [PDF].

Contact

LE Trung Thanh

AVITECH Institute
VNU University of Engineering and Technology, Vietnam

Email: thanhletrung@vnu.edu.vn // letrungthanhtbt@gmail.com

SAME CATEGORY

GitHub

DLAD: Image Entropy Reduction via Anisotropic Diffusion Steered by Probability Map from CNNs

Medical images are often very large and medical image compression is important in teleradiology and teleinterventions. Medial image compression is challenging due to the quality of the images should remain sufficient for medical purpose. The lossless compression methods do not degrade the quality of the image, however their compression ratios are often very low. This […]

Network coding

Network coding (NC) is considered a breakthrough to improve throughput, robustness, and security of wireless networks. Although the theoretical aspects of NC have been extensively investigated, there have been only few experiments with pure NC schematics. This work presents an implementation of NC under a two-way relay model and extends it to two non-straightforward scenarios: […]