CVPR Findings2026
Online Interpretable Matrix Decomposition for Large-Scale Streaming Data
Muhammad A. A. Abdelgawad, Abdelrahman B. M. Eldaly, Meng Xinmin, Peng Jing, Abdurrashid Ibrahim Sanka, Ray C.C. Cheung, Hong Yan
Abstract
The CUR decomposition has emerged as a powerful matrix factorization technique for interpretable dimensionality reduction, particularly valuable in computer vision and pattern recognition applications where preserving actual data samples is crucial. However, existing CUR methods are primarily designed for batch processing and become computationally prohibitive when dealing with streaming data, a common scenario across many applications. In this paper, we propose online CUR-type approximation with exact columns and compressed rows algorithms that maintain computational efficiency while preserving approximation quality. We propose two variants: one based on leverage-score sampling and another using the discrete empirical interpolation method for column/row selection. We provide rigorous mathematical analysis, including approximation bounds and complexity analysis for the proposed algorithms. Extensive experiments on synthetic and real-world datasets demonstrate that our methods offer high computational efficiency compared to batch methods, while maintaining comparable reconstruction accuracy. This makes them particularly suitable for large-scale applications such as real-time video and traffic network analysis.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Lineage
Builds on2
Related papers
- Streaming Coresets for Symmetric Tensor FactorizationRachit Chhaya, Jayesh Choudhari, Anirban Dasgupta, Supratim ShitICML 2020 · 16 citations
- Fast Deterministic CUR Matrix Decomposition with Accuracy AssuranceYasutoshi Ida, Sekitoshi Kanai, Yasuhiro Fujiwara, Tomoharu Iwata et al.ICML 2020 · 14 citations
- Fast and Accurate Online Coupled Matrix-Tensor Factorization via Frequency RegularizationYong-chan Park, Seungjoo Lee, U KangKDD 2026 · 1 citation
- Fast and Accurate Dual-Way Streaming PARAFAC2 for Irregular Tensors - Algorithm and ApplicationJun-Gi Jang, Jeongyoung Lee, Yong-chan Park, U KangKDD 2023 · 9 citations
- Fast Exact Leverage Score Sampling from Khatri-Rao Products with Applications to Tensor DecompositionVivek Bharadwaj, Osman Asif Malik, Riley Murray, Laura Grigori et al.NeurIPS 2023 · 14 citations
