Robust Matrix Completion With Deterministic Sampling via Convex Optimization

Area of Science:

• Matrix analysis
• Optimization theory
• Signal processing

Background:

• Robust matrix completion typically assumes random sampling, limiting practical applications.
• Deterministic sampling offers advantages for hardware implementation but lacks theoretical guarantees.
• Existing methods struggle with arbitrary sampling patterns.

Purpose of the Study:

• To develop a theoretical framework for robust matrix completion under deterministic sampling.
• To establish conditions for unique recovery of low-rank and sparse matrices.
• To propose and generalize a convex optimization algorithm for deterministic matrix completion.

Main Methods:

• Introduced a restricted approximate isometry property.
• Utilized a modified golfing scheme and strengthened incoherence conditions.
• Developed a convex optimization algorithm using nuclear norm and convolutional nuclear norm.

Main Results:

• Proved unique recoverability of latent matrices via convex optimization with high probability.
• Established the first exact-recovery theory for robust matrix completion with arbitrary deterministic sampling.
• Demonstrated algorithm efficacy on synthetic and real-world image data.

Conclusions:

• Deterministic sampling is viable for robust matrix completion with theoretical guarantees.
• The proposed generalized algorithm effectively recovers matrices in practical scenarios.
• This work bridges the gap between theoretical analysis and hardware implementation.