mlsanityData to 14 Oct 2026

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

arXiv 2208.09723 ↗First posted 20 Aug 2022cs.LG cs.NA math.NAcited by 12

Not on the map. Why?

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.

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

19 of 66 references.

References · 19

  1. 2014Guaranteed Matrix Completion via Non-convex Factorizationcited by 82
  2. 2020Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descentcited by 71
  3. 2016Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descentcited by 39
  4. 2013Incoherence-Optimal Matrix Completioncited by 27
  5. 2014Matrix Completion on Graphscited by 26
  6. 2013Improving CUR Matrix Decomposition and the Nystr"om Approximation via Adaptive Samplingcited by 21
  7. 2021Robust CUR Decomposition: Theory and Imaging Applicationscited by 20
  8. 2016Guarantees of Riemannian Optimization for Low Rank Matrix Completioncited by 19
  9. 2018Exact Reconstruction of Euclidean Distance Geometry Problem Using Low-rank Matrix Completioncited by 18
  10. 2015Structured Matrix Completion with Applications to Genomic Data Integrationcited by 17
  11. 2020Rapid Robust Principal Component Analysis: CUR Accelerated Inexact Low Rank Estimationcited by 16
  12. 2014Fast Exact Matrix Completion with Finite Samplescited by 15
7 more
  1. 2016Greedy Column Subset Selection: New Bounds and Distributed Algorithmscited by 13
  2. 2021Mode-wise Tensor Decompositions: Multi-dimensional Generalizations of CUR Decompositionscited by 13
  3. 2022Structured Gradient Descent for Fast Robust Low-Rank Hankel Matrix Completioncited by 11
  4. 2021Fast Robust Tensor Principal Component Analysis via Fiber CUR Decompositioncited by 8
  5. 2014CUR Algorithm for Partially Observed Matricescited by 7
  6. 2022Riemannian CUR Decompositions for Robust Principal Component Analysiscited by 7
  7. 2016Link Prediction via Matrix Completioncited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 3; 2024: 6; 2025: 2; 2026: 1.

12 papers.

  1. 2024On the Robustness of Cross-Concentrated Sampling for Matrix Completioncited by 5
  2. 2023Localization from structured distance matrices via low-rank matrix recoverycited by 4
  3. 2024Guarantees of a Preconditioned Subgradient Algorithm for Overparameterized Asymmetric Low-rank Matrix Recoverycited by 4
  4. 2024Accelerating Ill-conditioned Hankel Matrix Recovery via Structured Newton-like Descentcited by 3
  5. 2025Incomplete Graph Learning: A Comprehensive Surveycited by 3
  6. 2024S3Attention: Improving Long Sequence Attention with Smoothed Skeleton Sketchingcited by 2
  7. 2024Structured Sampling for Robust Euclidean Distance Geometrycited by 2
  8. 2023Non-convex approaches for low-rank tensor completion under tubal samplingcited by 1
  9. 2023Maximal Volume Matrix Cross Approximation for Image Compression and Least Squares Solutioncited by 0
  10. 2024Randomized Approach to Matrix Completion: Applications in Recommendation Systems and Image Inpaintingcited by 0
  11. 2025Recovering Wasserstein Distance Matrices from Few Measurementscited by 0
  12. 2026Robust Low-Tubal-Rank Tensor Completion under Cross-Concentrated Samplingcited by 0