Matrix Completion with Deterministic Sampling: Theories and Methods

Abstract

In some significant applications such as data forecasting, the locations of missing entries cannot obey any non-degenerate distributions, questioning the validity of the prevalent assumption that the missing data is randomly chosen according to some probabilistic model. To break through the limits of random sampling, we explore in this paper the problem of real-valued matrix completion under the setup of deterministic sampling. We propose two conditions, isomeric condition and relative well-conditionedness, for guaranteeing an arbitrary matrix to be recoverable from a sampling of the matrix entries. It is provable that the proposed conditions are weaker than the assumption of uniform sampling and, most importantly, it is also provable that the isomeric condition is necessary for the completions of any partial matrices to be identifiable. Equipped with these new tools, we prove a collection of theorems for missing data recovery as well as convex/nonconvex matrix completion. Among other things, we study in detail a Schatten quasi-norm induced method termed isomeric dictionary pursuit (IsoDP), and we show that IsoDP exhibits some distinct behaviors absent in the traditional bilinear programs.

References in corpus (10)

• Robust Recovery of Subspace Structures by Low-Rank Representation
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
• Guaranteed Matrix Completion via Non-convex Factorization
• Matrix Completion from Noisy Entries
• Incoherence-Optimal Matrix Completion
• Non-convex Robust PCA
• Necessary and Sufficient Conditions for Success of the Nuclear Norm Heuristic for Rank Minimization
• A Characterization of Deterministic Sampling Patterns for Low-Rank Matrix Completion
• A Combinatorial Algebraic Approach for the Identifiability of Low-Rank Matrix Completion

Cited by in corpus (3)

• Recovery of Future Data via Convolution Nuclear Norm Minimization
• Time Series Forecasting via Learning Convolutionally Low-Rank Models
• COMET: Convolutional Dimension Interaction for Collaborative Filtering