Lune

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.

Questions to start from

Lune can draw on

the full paper · related work

Get the answer

Free to start. No credit card required.

Lineage

Builds onCited byLeft to right by year; the more cited, the higher.

Builds on2

  1. CURSOR: Scalable Mixed-Order Hypergraph Matching with CUR DecompositionQixuan Zheng, Ming Zhang, Hong YanCVPR 2024
  2. Efficient Robust Principal Component Analysis via Block Krylov Iteration and CUR DecompositionShun Fang, Zhengqin Xu, Shiqian Wu, Shoulie XieCVPR 2023

Related papers

  1. Streaming Coresets for Symmetric Tensor FactorizationRachit Chhaya, Jayesh Choudhari, Anirban Dasgupta, Supratim ShitICML 2020 · 16 citations
  2. Fast Deterministic CUR Matrix Decomposition with Accuracy AssuranceYasutoshi Ida, Sekitoshi Kanai, Yasuhiro Fujiwara, Tomoharu Iwata et al.ICML 2020 · 14 citations
  3. Fast and Accurate Online Coupled Matrix-Tensor Factorization via Frequency RegularizationYong-chan Park, Seungjoo Lee, U KangKDD 2026 · 1 citation
  4. 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
  5. 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
Dusk over the sea between two cliffs drawn in fine vertical lines