OLSTEC : OnLine Low-rank Subspace tracking by TEnsor CP Decomposition in Matlab

Authors: Hiroyuki Kasai

Last page update: Sep. 12, 2017

Latest library version: 1.0.1 (see Release notes for more info)

Introduction

OLSTEC is an online tensor subspace tracking algorithm based on the Canonical Polyadic decomposition (CP decomposition) (or PARAFAC or CANDECOMP decomposition) exploiting the recursive least squares (RLS).

Motivation

OLSTEC presents a new online tensor tracking algorithm for the partially observed high-dimensional data stream corrupted by noise. We focus on the fixed-rank higher-order matrix completion (i.e., tensor completion) algorithm with a second-order stochastic gradient descent based on the CP decomposition exploiting the recursive least squares (RLS). Specifically, we consider the case where the partially observed tensor slice is acquired sequentially over time. Then, we estimate {A, B, C} by minimizing the exponentially weighted least squares defined as

Reference

• H.Kasai, "Fast online low-rank tensor subspace tracking by CP decomposition using recursive least squares from incomplete observations," Neurocomputing, Volume 347, 28, pp. 177-190, 2019.
  • Publisher's web site
  • arXiv web site
• H.Kasai, "Online low-rank tensor subspace tracking from incomplete data by CP decomposition using recursive least squares," IEEE International conference on Acoustics, Speech and Signal Processing (ICASSP), 2016.
  • Publisher's web site
  • arXiv web site

List of benchmarks

• Online tensor tracking algorithm
  • TeCPSGD
    • M. Mardani, G. Mateos, and G.B. Giannakis, "Subspace learning and imputation for streaming big data matrices and tensors," IEEE Transactions on Signal Processing, vol. 63, no. 10, pp. 266-2677, 2015.
• Online matrix tracking algorithms
  • Grasta
    • Jun He, Laura Balzano, and John C.S. Lui, "Online robust subspace tracking from partial information," arXiv:1109.3827, 2011.
    • Jun He, Laura Balzano, and Arthur Szlam, "Incremental gradient on the grassmannian for online foreground and background separation in subsampled video," IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2012.
  • Grouse
    • L. Balzano, R. Nowak, and B. Recht, "Online identification and tracking of subspaces from highly incomplete information," arXiv:1006.4046, 2010.
  • Petrels
    • Y. Chi, Y. C. Eldar, and R. Calderbank, "Petrels: Parallel subspace estimation and tracking using recursive least squares from partial observations," IEEE Transactions on Signal Processing, vol. 61, no. 23, pp. 5947-5959, 2013.
• Batch tensor CP decomposition algorithm
  • CP-WOPT
    • E. Acar, D. M. Dunlavy, T. G. Kolda, and M. Mprup, "Scalable tensor factorizations with missing data," Proceedings of the 2010 SIAM International Conference on Data Mining (SDM10), 2010, pp. 701-712.

Folders and files

./                              - Top directory.
./README.md                     - This readme file.
./olstec.m                      - OLSTEC algorithm file.
./run_me_first.m                - The scipt that you need to run first.
./demo.m                        - Demonstration script to check and understand this package easily. 
./test_comparison_syntheric.m   - Demonstration script for synthetic dataset. 
./test_comparison_real.m        - Demonstration script for real dataset. 
|auxiliary/                     - Some auxiliary tools for this project.
|benchmark/                     - Project files for benchmarks.
|tool/                          - 3rd party tools.

• 3rd party tools
  • tensor_toolbox_2.6 and poblano_toolbox_1.1 for CP-WOPT.

First to do

Run run_me_first for path configurations.

%% First run the setup script
run_me_first; 

Usage example: Syhtethic dataset demo

Now, just execute demo for demonstration of this package.

%% Execute the demonstration script
demo; 

The "demo.m" file contains below.

% set paramters
tensor_dims = [100, 100, 200];
rank        = 5;
fraction    = 0.1;
inverse_snr = 1e-4;

% generate tensor
data_subtype = 'Static';
[A,~,~,Omega,~,~,~,~,~,~,~,~] = generate_synthetic_tensor(tensor_dims, rank, fraction, inverse_snr, data_subtype);


% OLSTEC
options.verbose = 2;
[Xsol_olstec, infos_olstec, sub_infos_olstec] = olstec(A, Omega, [], tensor_dims, rank, [], options);


% plotting
figure;
semilogy(sub_infos_olstec.inner_iter, sub_infos_olstec.err_residual, '-r', 'linewidth', 2.0);
legend('OLSTEC');
xlabel('data stream index');
ylabel('normalized residual error');    


figure;
semilogy(sub_infos_olstec.inner_iter, sub_infos_olstec.err_run_ave, '-r', 'linewidth', 2.0);
legend('OLSTEC');
xlabel('data stream index');
ylabel('running average error');   

• Output results

More results

• Real-world dataset with moving background

  • The input video is created virtually by moving cropped partial image from its original entire frame image of video of "Airport Hall".
  • The cropping window with 288x200 moves from the leftmost partial image to the rightmost, then returns to the leftmost image after stopping a certain period of time.
  • The generated video includes right-panning video from 38-th to 113-th frame and from 342-th to 417-th frame, and left-panning video from 190-th to 265-th frame.
  • results
    • Normalized residual error and running average error.
    • Input image, caluculated low-rank image, and residual error image at 283-th frame.

License

This code is free and open source for academic/research purposes (non-commercial).

Problems or questions

If you have any problems or questions, please contact the author: Hiroyuki Kasai (email: hiroyuki dot kasai at waseda dot jp)

Release Notes

• Version 1.0.1 (Sep 12, 2017)
  • Bug fixed.
• Version 1.0.0 (June 07, 2017)
  • Initial version.