Matrix Completion With Cross-Concentrated Sampling: Bridging Uniform Sampling and CUR Sampling
Matrix Completion With Cross-Concentrated Sampling: Bridging Uniform Sampling and CUR Sampling
复制标题
DOI：
10.1109/tpami.2023.3261185
复制
发表时间：
2022-08
影响因子：
23.6
通讯作者：
HanQin Cai;Longxiu Huang;Pengyu Li;D. Needell
中科院分区：
文献类型：
--
作者：
HanQin Cai;Longxiu Huang;Pengyu Li;D. Needell
虽然均匀采样在矩阵补全文献中得到了广泛研究，但 CUR 采样通过行和列样本来近似低秩矩阵。不幸的是，这两种采样模型都缺乏针对实际应用中各种情况的灵活性。在这项工作中，我们提出了一种新颖且易于实施的采样策略，称为交叉集中采样（CCS）。通过桥接统一采样和 CUR 采样，CCS 提供了额外的灵活性，可以潜在地节省应用中的采样成本。此外，我们还为基于CCS的矩阵补全提供了充分条件。此外，我们为所提出的 CCS 模型提出了一种高效的非凸算法，称为迭代 CUR 完成（ICURC）。数值实验验证了 CCS 和 ICURC 在合成数据集和真实数据集上相对于均匀采样及其基线算法的经验优势。
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.