Online learning

banner-982162_1920
mathematics-1044070_1920
geometry-1023846_1920
lego-1124010_1920
previous arrow
next arrow

OLSTEC

OnLine Low-rank Subspace tracking by TEnsor CP Decomposition

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). 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 \{{\bf A}, {\bf B}, {\bf C}\} by minimizing the exponentially weighted least squares defined as

\displaystyle{\min_{\scriptsize{\bf A},{\bf B},{\bf C}}}\ \ \frac{1}{2} \sum_{\tau=1}^t \lambda^{t-\tau} \biggl[ {\| {\bf \Omega}_\tau \circledast \bigl[ {\bf Y}_\tau - {\bf A} {\rm diag}({\bf b}^\tau) {\bf C}^T \bigr] \|_F^2} +\ {\bar{\mu}(\| {\bf A}\|_F^2 + \|{\bf C}\|_F^2) + \mu[\tau] \| {\bf b}^\tau \|_2^2} \biggr]}.

欠損データを含む高次元ストリームデータを対象として，テンソル分解に基づくオンライン低ランク部分空間追跡法 OnLine Low-rank Subspace tracking  by TEnsor CP Decomposition (OLSTEC) を提案する．当該データが低次元線形空間に位置することを仮定し，本問題をオンライン型・低ランクテンソル補完問題として定義している．特に，着目するデータが時事刻々と入力されるストリームデータで，且つデータの部分空間が緩やかに変化する状況を想定する．提案法のOLSTEC法は，逐次最小二乗法 (RLS) による速い収束性能を有する勾配法に基づいている．


Reconstructed subspace images in surveillance video application (Airport Hall dataset).

Publications

  • HK, “Fast online low-rank tensor subspace tracking by CP decomposition using recursive least squares from incomplete observations,” Neurocomputing2019, arXiv2017 (Extended version of below).
  • HK, “Online low-rank tensor subspace tracking from incomplete data by CP decomposition using recursive least squares,” IEEE ICASSP2016, arXiv2016.

The software is available at Github.