  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.
