| Summary: | Summary: In this paper, we propose two new provable algorithms for tracking online low-rank approximations of high-order streaming tensors with missing data. The first algorithm, dubbed adaptive Tucker decomposition (ATD), minimizes a weighted recursive least-squares cost function to obtain the tensor factors and the core tensor in an efficient way, thanks to an alternating minimization framework and a randomized sketching technique. Under the canonical polyadic (CP) model, the second algorithm, called ACP, is developed as a variant of ATD when the core tensor is imposed to be identity. Both algorithms are low-complexity tensor trackers that have fast convergence and low memory storage requirements. A unified convergence analysis is presented for ATD and ACP to justify their performance. Experiments indicate that the two proposed algorithms are capable of streaming tensor decomposition with competitive performance with respect to estimation accuracy and runtime on both synthetic and real data. The bigger picture: Low-rank approximation methods are a class of mathematical techniques commonly used to help process large datasets, especially in signal processing and machine learning applications. These methods allow multidimensional data to be represented by a set of low-dimensional components and can be powerful tools for discovering valuable information or deriving new insights from complex data. Applying these methods to streaming data, which are being continuously generated and must be analyzed in real time, remains challenging due to the increasing size and complexity of these datasets over time. These challenges are particularly acute for datasets with missing values. This paper proposes a novel adaptive method for tracking online low-rank approximations of multidimensional streaming data, resulting in two efficient tensor trackers that accurately estimate the underlying components of noisy, incomplete, and high-dimensional observations. The effectiveness of the proposed approach is demonstrated in various experiments, including the analysis of EEG data and video sequences.
|
|---|