Matrix Completion With Cross-Concentrated Sampling: Bridging Uniform Sampling and CUR Sampling.

Area of Science:

• Data Science
• Machine Learning
• Numerical Analysis

Background:

• Matrix completion is crucial for reconstructing incomplete data.
• Existing uniform and CUR sampling methods lack flexibility for real-world scenarios.
• Low-rank matrix approximation is a key challenge in data analysis.

Purpose of the Study:

• Introduce a novel, flexible sampling strategy: Cross-Concentrated Sampling (CCS).
• Develop an efficient algorithm for CCS-based matrix completion.
• Demonstrate the advantages of CCS over existing sampling techniques.

Main Methods:

• Proposed Cross-Concentrated Sampling (CCS) bridging uniform and CUR sampling.
• Developed a non-convex algorithm, Iterative CUR Completion (ICURC), for CCS.
• Conducted numerical experiments on synthetic and real-world datasets.

Main Results:

• CCS provides enhanced flexibility and potential cost savings in sampling.
• A sufficient condition for CCS-based matrix completion was established.
• ICURC demonstrated empirical advantages over baseline algorithms.

Conclusions:

• CCS offers a more adaptable and cost-effective sampling strategy for matrix completion.
• The proposed ICURC algorithm is efficient for the CCS model.
• CCS and ICURC show significant empirical benefits in various applications.