# On the Robustness of Cross-Concentrated Sampling for Matrix Completion

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 32 references that are in the map.
- First posted on arXiv 28 Jan 2024.

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

- [Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent](https://mlsanity.com/paper/2005.08898/) (2020)
- [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)
- [Learned Robust PCA: A Scalable Deep Unfolding Approach for High-Dimensional Outlier Detection](https://mlsanity.com/paper/2110.05649/) (2021)
- [Accelerated Alternating Projections for Robust Principal Component Analysis](https://mlsanity.com/paper/1711.05519/) (2017)
- [Robust CUR Decomposition: Theory and Imaging Applications](https://mlsanity.com/paper/2101.05231/) (2021)
- [Rapid Robust Principal Component Analysis: CUR Accelerated Inexact Low Rank Estimation](https://mlsanity.com/paper/2010.07422/) (2020)
- [Robust Spectral Compressed Sensing via Structured Matrix Completion](https://mlsanity.com/paper/1304.8126/) (2013)
- [Robust PCA by Manifold Optimization](https://mlsanity.com/paper/1708.00257/) (2017)
- [Matrix Completion with Cross-Concentrated Sampling: Bridging Uniform Sampling and CUR Sampling](https://mlsanity.com/paper/2208.09723/) (2022)
- [Structured Gradient Descent for Fast Robust Low-Rank Hankel Matrix Completion](https://mlsanity.com/paper/2204.03316/) (2022)
- [Robust Tensor CUR Decompositions: Rapid Low-Tucker-Rank Tensor Recovery with Sparse Corruption](https://mlsanity.com/paper/2305.04080/) (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)

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

- [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)
- [Robust Anomaly Detection via Tensor Pseudoskeleton Decomposition](https://mlsanity.com/paper/2502.09926/) (2025)
- [Robust Low-Tubal-Rank Tensor Completion under Cross-Concentrated Sampling](https://mlsanity.com/paper/2608.03928/) (2026)

## Abstract (arXiv)

Matrix completion is one of the crucial tools in modern data science research. Recently, a novel sampling model for matrix completion coined cross-concentrated sampling (CCS) has caught much attention. However, the robustness of the CCS model against sparse outliers remains unclear in the existing studies. In this paper, we aim to answer this question by exploring a novel Robust CCS Completion problem. A highly efficient non-convex iterative algorithm, dubbed Robust CUR Completion (RCURC), is proposed. The empirical performance of the proposed algorithm, in terms of both efficiency and robustness, is verified in synthetic and real datasets.