# Matrix Completion with Cross-Concentrated Sampling: Bridging Uniform Sampling and CUR Sampling

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

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 66 references that are in the map.
- First posted on arXiv 20 Aug 2022.

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

- [Guaranteed Matrix Completion via Non-convex Factorization](https://mlsanity.com/paper/1411.8003/) (2014)
- [Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent](https://mlsanity.com/paper/2005.08898/) (2020)
- [Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent](https://mlsanity.com/paper/1605.07051/) (2016)
- [Incoherence-Optimal Matrix Completion](https://mlsanity.com/paper/1310.0154/) (2013)
- [Matrix Completion on Graphs](https://mlsanity.com/paper/1408.1717/) (2014)
- [Improving CUR Matrix Decomposition and the Nystr"om Approximation via Adaptive Sampling](https://mlsanity.com/paper/1303.4207/) (2013)
- [Robust CUR Decomposition: Theory and Imaging Applications](https://mlsanity.com/paper/2101.05231/) (2021)
- [Guarantees of Riemannian Optimization for Low Rank Matrix Completion](https://mlsanity.com/paper/1603.06610/) (2016)
- [Exact Reconstruction of Euclidean Distance Geometry Problem Using Low-rank Matrix Completion](https://mlsanity.com/paper/1804.04310/) (2018)
- [Structured Matrix Completion with Applications to Genomic Data Integration](https://mlsanity.com/paper/1504.01823/) (2015)
- [Rapid Robust Principal Component Analysis: CUR Accelerated Inexact Low Rank Estimation](https://mlsanity.com/paper/2010.07422/) (2020)
- [Fast Exact Matrix Completion with Finite Samples](https://mlsanity.com/paper/1411.1087/) (2014)
- [Greedy Column Subset Selection: New Bounds and Distributed Algorithms](https://mlsanity.com/paper/1605.08795/) (2016)
- [Mode-wise Tensor Decompositions: Multi-dimensional Generalizations of CUR Decompositions](https://mlsanity.com/paper/2103.11037/) (2021)
- [Structured Gradient Descent for Fast Robust Low-Rank Hankel Matrix Completion](https://mlsanity.com/paper/2204.03316/) (2022)
- [Fast Robust Tensor Principal Component Analysis via Fiber CUR Decomposition](https://mlsanity.com/paper/2108.10448/) (2021)
- [CUR Algorithm for Partially Observed Matrices](https://mlsanity.com/paper/1411.0860/) (2014)
- [Riemannian CUR Decompositions for Robust Principal Component Analysis](https://mlsanity.com/paper/2206.09042/) (2022)
- [Link Prediction via Matrix Completion](https://mlsanity.com/paper/1606.06812/) (2016)

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

- [On the Robustness of Cross-Concentrated Sampling for Matrix Completion](https://mlsanity.com/paper/2401.15566/) (2024)
- [Localization from structured distance matrices via low-rank matrix recovery](https://mlsanity.com/paper/2311.18076/) (2023)
- [Guarantees of a Preconditioned Subgradient Algorithm for Overparameterized Asymmetric Low-rank Matrix Recovery](https://mlsanity.com/paper/2410.16826/) (2024)
- [Accelerating Ill-conditioned Hankel Matrix Recovery via Structured Newton-like Descent](https://mlsanity.com/paper/2406.07409/) (2024)
- [Incomplete Graph Learning: A Comprehensive Survey](https://mlsanity.com/paper/2502.12412/) (2025)
- [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)
- [Non-convex approaches for low-rank tensor completion under tubal sampling](https://mlsanity.com/paper/2303.12721/) (2023)
- [Maximal Volume Matrix Cross Approximation for Image Compression and Least Squares Solution](https://mlsanity.com/paper/2309.17403/) (2023)
- [Randomized Approach to Matrix Completion: Applications in Recommendation Systems and Image Inpainting](https://mlsanity.com/paper/2403.01919/) (2024)
- [Recovering Wasserstein Distance Matrices from Few Measurements](https://mlsanity.com/paper/2509.19250/) (2025)
- [Robust Low-Tubal-Rank Tensor Completion under Cross-Concentrated Sampling](https://mlsanity.com/paper/2608.03928/) (2026)

## Abstract (arXiv)

While uniform sampling has been widely studied in the matrix completion literature, CUR sampling approximates a low-rank matrix via row and column samples. Unfortunately, both sampling models lack flexibility for various circumstances in real-world applications. In this work, we propose a novel and easy-to-implement sampling strategy, coined Cross-Concentrated Sampling (CCS). By bridging uniform sampling and CUR sampling, CCS provides extra flexibility that can potentially save sampling costs in applications. In addition, we also provide a sufficient condition for CCS-based matrix completion. Moreover, we propose a highly efficient non-convex algorithm, termed Iterative CUR Completion (ICURC), for the proposed CCS model. Numerical experiments verify the empirical advantages of CCS and ICURC against uniform sampling and its baseline algorithms, on both synthetic and real-world datasets.