Fast and Accurate Dual-Way Streaming PARAFAC2 for Irregular Tensors -- Algorithm and Application

• URL: http://arxiv.org/abs/2305.18376v1
• Date: Sun, 28 May 2023 05:56:47 GMT
• Title: Fast and Accurate Dual-Way Streaming PARAFAC2 for Irregular Tensors -- Algorithm and Application
• Abstract summary: We propose Dash, an efficient and accurate PARAFAC2 decomposition method working in the dual-way streaming setting. Dash achieves 14.0x faster speed than existing PARAFAC2 decomposition methods for newly arrived data. We also provide discoveries for detecting anomalies in real-world datasets, including Subprime Mortgage Crisis and COVID-19.
• Score: 25.241802754640958
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: How can we efficiently and accurately analyze an irregular tensor in a dual-way streaming setting where the sizes of two dimensions of the tensor increase over time? What types of anomalies are there in the dual-way streaming setting? An irregular tensor is a collection of matrices whose column lengths are the same while their row lengths are different. In a dual-way streaming setting, both new rows of existing matrices and new matrices arrive over time. PARAFAC2 decomposition is a crucial tool for analyzing irregular tensors. Although real-time analysis is necessary in the dual-way streaming, static PARAFAC2 decomposition methods fail to efficiently work in this setting since they perform PARAFAC2 decomposition for accumulated tensors whenever new data arrive. Existing streaming PARAFAC2 decomposition methods work in a limited setting and fail to handle new rows of matrices efficiently. In this paper, we propose Dash, an efficient and accurate PARAFAC2 decomposition method working in the dual-way streaming setting. When new data are given, Dash efficiently performs PARAFAC2 decomposition by carefully dividing the terms related to old and new data and avoiding naive computations involved with old data. Furthermore, applying a forgetting factor makes Dash follow recent movements. Extensive experiments show that Dash achieves up to 14.0x faster speed than existing PARAFAC2 decomposition methods for newly arrived data. We also provide discoveries for detecting anomalies in real-world datasets, including Subprime Mortgage Crisis and COVID-19.

Related papers

• LimiX-2M: Mitigating Low-Rank Collapse and Attention Bottlenecks in Tabular Foundation Models [56.999481798138625]
  LimiX-2M is a 2M- parameter model that outperforms larger TabPFN-v2 and TabICL baselines on widely used benchmarks.<n>We present a unified tokenize-and-route framework for strong Tabular foundation models (TFMs)<n>Results highlight value-aware tokenization and readout-aligned routing as key levers for improving the accuracy--efficiency trade-off in TFMs.
  arXiv  Detail & Related papers  (2026-06-03T06:07:33Z)
• GSPN-2: Efficient Parallel Sequence Modeling [101.33780567131716]
  Generalized Spatial Propagation Network (GSPN) addresses this by replacing quadratic self-attention with a line-scan propagation scheme.<n>GSPN-2 establishes a new efficiency frontier for modeling global spatial context in vision applications.
  arXiv  Detail & Related papers  (2025-11-28T07:26:45Z)
• ReLATE: Learning Efficient Sparse Encoding for High-Performance Tensor Decomposition [1.1681618004689642]
  ReLATE is a reinforcement-learned adaptive tensor encoding framework.<n>It builds efficient sparse tensor representations without labeled training samples.<n>It consistently outperforms expert-designed formats across diverse sparse tensor data sets, with a geometric-mean speedup of 1.4-1.46X.
  arXiv  Detail & Related papers  (2025-08-29T23:45:09Z)
• Neutralizing Token Aggregation via Information Augmentation for Efficient Test-Time Adaptation [59.1067331268383]
  Test-Time Adaptation (TTA) has emerged as an effective solution for adapting Vision Transformers (ViT) to distribution shifts without additional training data.<n>To reduce inference cost, plug-and-play token aggregation methods merge redundant tokens in ViTs to reduce total processed tokens.<n>We formalize this problem as Efficient Test-Time Adaptation (ETTA), seeking to preserve the adaptation capability of TTA while reducing inference latency.
  arXiv  Detail & Related papers  (2025-08-05T12:40:55Z)
• xLSTMAD: A Powerful xLSTM-based Method for Anomaly Detection [0.794682109939797]
  We propose xLSTMAD, the first anomaly detection method that integrates a full encoder-decoder xLSTM architecture.<n>We evaluate our method on the comprehensive TSB-AD-M benchmark, which spans 17 real-world datasets.<n>In our results, xLSTM showcases state-of-the-art accuracy, outperforming 23 popular anomaly detection baselines.
  arXiv  Detail & Related papers  (2025-06-28T10:39:09Z)
• Sparse Tensor PCA via Tensor Decomposition for Unsupervised Feature Selection [8.391109286933856]
  We develop two Sparse Principal Component Analysis (STPCA) models that utilize the projection directions in the factor matrices to perform unsupervised feature selection. For both models, we prove the optimal solution of each subproblem falls onto the Hermitian Positive Semidefinite Cone (HPSD) According to the experimental results, the two proposed methods are suitable for handling different data tensor scenarios and outperform the state-of-the-art UFS methods.
  arXiv  Detail & Related papers  (2024-07-24T04:04:56Z)
• Does Long-Term Series Forecasting Need Complex Attention and Extra Long Inputs? [21.15722677855935]
  Transformer-based models have achieved impressive performance on various time series tasks. Long-Term Series Forecasting (LTSF) tasks have also received extensive attention in recent years. Due to the inherent computational complexity and long sequences demanding of Transformer-based methods, its application on LTSF tasks still has two major issues.
  arXiv  Detail & Related papers  (2023-06-08T08:37:49Z)
• RSC: Accelerating Graph Neural Networks Training via Randomized Sparse Computations [56.59168541623729]
  Training graph neural networks (GNNs) is time consuming because sparse graph-based operations are hard to be accelerated by hardware. We explore trading off the computational precision to reduce the time complexity via sampling-based approximation. We propose Randomized Sparse Computation, which for the first time demonstrate the potential of training GNNs with approximated operations.
  arXiv  Detail & Related papers  (2022-10-19T17:25:33Z)
• Softmax-free Linear Transformers [90.83157268265654]
  Vision transformers (ViTs) have pushed the state-of-the-art for visual perception tasks. Existing methods are either theoretically flawed or empirically ineffective for visual recognition. We propose a family of Softmax-Free Transformers (SOFT)
  arXiv  Detail & Related papers  (2022-07-05T03:08:27Z)
• Monarch: Expressive Structured Matrices for Efficient and Accurate Training [64.6871423399431]
  Large neural networks excel in many domains, but they are expensive to train and fine-tune. A popular approach to reduce their compute or memory requirements is to replace dense weight matrices with structured ones. We propose a class of matrices (Monarch) that is hardware-efficient.
  arXiv  Detail & Related papers  (2022-04-01T17:37:29Z)
• DPar2: Fast and Scalable PARAFAC2 Decomposition for Irregular Dense Tensors [29.072651980087713]
  We propose DPar2, a fast and scalable PARAFAC2 decomposition method for irregular dense tensors. Extensive experiments show that DPar2 is up to 6.0x faster than competitors on real-world irregular tensors.
  arXiv  Detail & Related papers  (2022-03-24T01:43:13Z)
• Sketching as a Tool for Understanding and Accelerating Self-attention for Long Sequences [52.6022911513076]
  Transformer-based models are not efficient in processing long sequences due to the quadratic space and time complexity of the self-attention modules. We propose Linformer and Informer to reduce the quadratic complexity to linear (modulo logarithmic factors) via low-dimensional projection and row selection. Based on the theoretical analysis, we propose Skeinformer to accelerate self-attention and further improve the accuracy of matrix approximation to self-attention.
  arXiv  Detail & Related papers  (2021-12-10T06:58:05Z)
• Hankel-structured Tensor Robust PCA for Multivariate Traffic Time Series Anomaly Detection [9.067182100565695]
  This study proposes a Hankel-structured tensor version of RPCA for anomaly detection in spatial data. We decompose the corrupted matrix into a low-rank Hankel tensor and a sparse matrix. We evaluate the method by synthetic data and passenger flow time series.
  arXiv  Detail & Related papers  (2021-10-08T19:35:39Z)
• SreaMRAK a Streaming Multi-Resolution Adaptive Kernel Algorithm [60.61943386819384]
  Existing implementations of KRR require that all the data is stored in the main memory. We propose StreaMRAK - a streaming version of KRR. We present a showcase study on two synthetic problems and the prediction of the trajectory of a double pendulum.
  arXiv  Detail & Related papers  (2021-08-23T21:03:09Z)
• Random Feature Attention [69.4671822971207]
  We propose RFA, a linear time and space attention that uses random feature methods to approximate the softmax function. RFA can be used as a drop-in replacement for conventional softmax attention and offers a straightforward way of learning with recency bias through an optional gating mechanism. Experiments on language modeling and machine translation demonstrate that RFA achieves similar or better performance compared to strong transformer baselines.
  arXiv  Detail & Related papers  (2021-03-03T02:48:56Z)
• SliceNStitch: Continuous CP Decomposition of Sparse Tensor Streams [22.348422397331984]
  We propose SLICENSTITCH for continuous CANDECOMP/PARAFAC decomposition. It has numerous time-critical applications, including anomaly detection, recommender systems, and stock market prediction. We show, theoretically and experimentally, that SLICENSTITCH is (1) 'Any time': updating factor immediately without having to wait until the current time period ends, (2) Fast: with constant-time updates up to 759x faster than online methods, and (3) Accurate: with fitness comparable (specifically, 72 160%) to offline methods.
  arXiv  Detail & Related papers  (2021-02-23T06:28:42Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.