Matrix completion with deterministic pattern - a geometric perspective

Abstract

We consider the matrix completion problem with a deterministic pattern of observed entries. In this setting, we aim to answer the question: under what condition there will be (at least locally) unique solution to the matrix completion problem, i.e., the underlying true matrix is identifiable. We answer the question from a certain point of view and outline a geometric perspective. We give an algebraically verifiable sufficient condition, which we call the well-posedness condition, for the local uniqueness of MRMC solutions. We argue that this condition is necessary for local stability of MRMC solutions, and we show that the condition is generic using the characteristic rank. We also argue that the low-rank approximation approaches are more stable than MRMC and further propose a sequential statistical testing procedure to determine the "true" rank from observed entries. Finally, we provide numerical examples aimed at verifying validity of the presented theory.

References in corpus (12)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• The Convex Geometry of Linear Inverse Problems
• A Simpler Approach to Matrix Completion
• Templates for Convex Cone Problems with Applications to Sparse Signal Recovery
• Recovering low-rank matrices from few coefficients in any basis
• An overview of low-rank matrix recovery from incomplete observations
• Guaranteed Matrix Completion via Non-convex Factorization
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• Incoherence-Optimal Matrix Completion
• Practical sketching algorithms for low-rank matrix approximation
• A Characterization of Deterministic Sampling Patterns for Low-Rank Matrix Completion
• On Deterministic Sampling Patterns for Robust Low-Rank Matrix Completion

Cited by in corpus (7)

• Inference and Uncertainty Quantification for Noisy Matrix Completion
• Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimization
• Matrix Completion with Nonconvex Regularization: Spectral Operators and Scalable Algorithms
• Testing Rank of Incomplete Unimodal Matrices
• Rank one tensor completion problem
• HOSVD-Based Algorithm for Weighted Tensor Completion
• Truncated Matrix Completion - An Empirical Study