# Robust CUR Decomposition: Theory and Imaging Applications

arXiv: https://arxiv.org/abs/2101.05231 · HTML: https://mlsanity.com/paper/2101.05231/

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 53 references that are in the map.
- First posted on arXiv 5 Jan 2021.

## Builds on (most cited first, 11 of 11)

- [Non-convex Robust PCA](https://mlsanity.com/paper/1410.7660/) (2014)
- [Fast Algorithms for Robust PCA via Gradient Descent](https://mlsanity.com/paper/1605.07784/) (2016)
- [Optimal CUR Matrix Decompositions](https://mlsanity.com/paper/1405.7910/) (2014)
- [Accelerated Alternating Projections for Robust Principal Component Analysis](https://mlsanity.com/paper/1711.05519/) (2017)
- [Improving CUR Matrix Decomposition and the Nystr"om Approximation via Adaptive Sampling](https://mlsanity.com/paper/1303.4207/) (2013)
- [A Critique of Self-Expressive Deep Subspace Clustering](https://mlsanity.com/paper/2010.03697/) (2020)
- [Rapid Robust Principal Component Analysis: CUR Accelerated Inexact Low Rank Estimation](https://mlsanity.com/paper/2010.07422/) (2020)
- [Greedy Column Subset Selection: New Bounds and Distributed Algorithms](https://mlsanity.com/paper/1605.08795/) (2016)
- [Column subset selection is NP-complete](https://mlsanity.com/paper/1701.02764/) (2017)
- [Reverse iterative volume sampling for linear regression](https://mlsanity.com/paper/1806.01969/) (2018)
- [CUR Decompositions, Similarity Matrices, and Subspace Clustering](https://mlsanity.com/paper/1711.04178/) (2017)

## Built on by (most cited first, 20 of 20)

- [Learned Robust PCA: A Scalable Deep Unfolding Approach for High-Dimensional Outlier Detection](https://mlsanity.com/paper/2110.05649/) (2021)
- [Mode-wise Tensor Decompositions: Multi-dimensional Generalizations of CUR Decompositions](https://mlsanity.com/paper/2103.11037/) (2021)
- [Matrix Completion with Cross-Concentrated Sampling: Bridging Uniform Sampling and CUR Sampling](https://mlsanity.com/paper/2208.09723/) (2022)
- [Robust Tensor CUR Decompositions: Rapid Low-Tucker-Rank Tensor Recovery with Sparse Corruption](https://mlsanity.com/paper/2305.04080/) (2023)
- [Latent Graph Inference with Limited Supervision](https://mlsanity.com/paper/2310.04314/) (2023)
- [Fast Robust Tensor Principal Component Analysis via Fiber CUR Decomposition](https://mlsanity.com/paper/2108.10448/) (2021)
- [Riemannian CUR Decompositions for Robust Principal Component Analysis](https://mlsanity.com/paper/2206.09042/) (2022)
- [On the Robustness of Cross-Concentrated Sampling for Matrix Completion](https://mlsanity.com/paper/2401.15566/) (2024)
- [CURSOR: Scalable Mixed-Order Hypergraph Matching with CUR Decomposition](https://mlsanity.com/paper/2402.16594/) (2024)
- [Accelerating Ill-conditioned Hankel Matrix Recovery via Structured Newton-like Descent](https://mlsanity.com/paper/2406.07409/) (2024)
- [S3Attention: Improving Long Sequence Attention with Smoothed Skeleton Sketching](https://mlsanity.com/paper/2408.08567/) (2024)
- [Structured Sampling for Robust Euclidean Distance Geometry](https://mlsanity.com/paper/2412.10664/) (2024)
- [Co-Separable Nonnegative Matrix Factorization](https://mlsanity.com/paper/2109.00749/) (2021)
- [Error Analysis of Tensor-Train Cross Approximation](https://mlsanity.com/paper/2207.04327/) (2022)
- [A Dual Basis Approach for Structured Robust Euclidean Distance Geometry](https://mlsanity.com/paper/2505.18414/) (2025)
- [Boosting Nystr"om Method](https://mlsanity.com/paper/2302.11032/) (2023)
- [Orthogonally weighted ℓ2,1 regularization for rank-aware joint sparse recovery: algorithm and analysis](https://mlsanity.com/paper/2311.12282/) (2023)
- [Randomized Approach to Matrix Completion: Applications in Recommendation Systems and Image Inpainting](https://mlsanity.com/paper/2403.01919/) (2024)
- [Approximation of the Proximal Operator of the ℓ_∞ Norm Using a Neural Network](https://mlsanity.com/paper/2408.11211/) (2024)
- [Property Inheritance for Subtensors in Tensor Train Decompositions](https://mlsanity.com/paper/2504.11396/) (2025)

## Abstract (arXiv)

This paper considers the use of Robust PCA in a CUR decomposition framework and applications thereof. Our main algorithms produce a robust version of column-row factorizations of matrices D=L+S where L is low-rank and S contains sparse outliers. These methods yield interpretable factorizations at low computational cost, and provide new CUR decompositions that are robust to sparse outliers, in contrast to previous methods. We consider two key imaging applications of Robust PCA: video foreground-background separation and face modeling. This paper examines the qualitative behavior of our Robust CUR decompositions on the benchmark videos and face datasets, and find that our method works as well as standard Robust PCA while being significantly faster. Additionally, we consider hybrid randomized and deterministic sampling methods which produce a compact CUR decomposition of a given matrix, and apply this to video sequences to produce canonical frames thereof.