Leave-One-Out Analysis for Nonconvex Robust Matrix Completion with General Thresholding Functions
<|reference_start|>Leave-One-Out Analysis for Nonconvex Robust Matrix Completion with General Thresholding Functions: We study the problem of robust matrix completion (RMC), where the partially observed entries of an underlying low-rank matrix is corrupted by sparse noise. Existing analysis of the non-convex methods for this problem either requires the explicit but empirically redundant regularization in the algorithm or requires sample splitting in the analysis. In this paper, we consider a simple yet efficient nonconvex method which alternates between a projected gradient step for the low-rank part and a thresholding step for the sparse noise part. Inspired by leave-one out analysis for low rank matrix completion, it is established that the method can achieve linear convergence for a general class of thresholding functions, including for example soft-thresholding and SCAD. To the best of our knowledge, this is the first leave-one-out analysis on a nonconvex method for RMC. Additionally, when applying our result to low rank matrix completion, it improves the sampling complexity of existing result for the singular value projection method.<|reference_end|>
@article{wang2024leave-one-out,
    title={Leave-One-Out Analysis for Nonconvex Robust Matrix Completion with
  General Thresholding Functions},
    author={Tianming Wang, Ke Wei},
    journal={arXiv preprint arXiv:2407.19446},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.19446},
    primaryClass={cs.IT math.IT stat.ML}
}