Leave-One-Out Approach for Matrix Completion: Primal and Dual Analysis

DOI10.1109/TIT.2020.2992769MaRDI QIDQ5138892zbMATH OpenOpenAlexFDO

Authors Lijun Ding, Yudong Chen

Publication date 4 December 2020

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1803.07554

zbMATH Keywords

nuclear norm minimization (NNM)iterative stochastic proceduresLeave-One-Out analysislow-rank matrix completion problemsProjected Gradient Descent (PGD)

Mathematics Subject Classification ID

Estimation in multivariate analysis (62H12) Applications of mathematical programming (90C90) Matrix completion problems (15A83) Nonconvex programming, global optimization (90C26)

Abstract: In this paper, we introduce a powerful technique based on Leave-one-out analysis to the study of low-rank matrix completion problems. Using this technique, we develop a general approach for obtaining fine-grained, entrywise bounds for iterative stochastic procedures in the presence of probabilistic dependency. We demonstrate the power of this approach in analyzing two of the most important algorithms for matrix completion: (i) the non-convex approach based on Projected Gradient Descent (PGD) for a rank-constrained formulation, also known as the Singular Value Projection algorithm, and (ii) the convex relaxation approach based on nuclear norm minimization (NNM). Using this approach, we establish the first convergence guarantee for the original form of PGD without regularization or sample splitting}, and in particular shows that it converges linearly in the infinity norm. For NNM, we use this approach to study a fictitious iterative procedure that arises in the dual analysis. Our results show that NNM recovers an $d$-by-$d$ rank-$r$ matrix with $mathcalO(murlog(mur)dlogd)$ observed entries. This bound has optimal dependence on the matrix dimension and is independent of the condition number. To the best of our knowledge, this is the first sample complexity result for a tractable matrix completion algorithm that satisfies these two properties simultaneously.

Recommendations

• Matrix completion and related problems via strong duality
• Exact matrix completion via convex optimization
• The \(N_{0}^{1}\)-matrix completion problem
• On a Class of Matrix Completion Problems
• Matrix completion via max-norm constrained optimization
• Non-convex matrix completion and related problems via strong duality
• An alternating minimization method for matrix completion problems
• scientific article; zbMATH DE number 4158856
• A note on matrix completion problems
• The nonsingular matrix completion problem

Cited in

(7)

• Robust Matrix Completion with Heavy-Tailed Noise
• Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence
• GNMR: a provable one-line algorithm for low rank matrix recovery
• WARPd: a linearly convergent first-order primal-dual algorithm for inverse problems with approximate sharpness conditions
• Iterative Collaborative Filtering for Sparse Matrix Estimation
• Leave-one-out singular subspace perturbation analysis for spectral clustering
• Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution Under Random Designs

This page was built for publication: Leave-One-Out Approach for Matrix Completion: Primal and Dual Analysis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5138892)