Skip to content

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

License

Notifications You must be signed in to change notification settings

hiroyuki-kasai/OLSTEC

Repository files navigation

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

List of benchmarks

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.

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.