Matrix completion with deterministic pattern - a geometric perspective
This work addresses theoretical stability and identifiability issues in matrix completion for applications like recommendation systems, but it is incremental as it builds on existing geometric perspectives without introducing a new paradigm.
The paper tackles the matrix completion problem with deterministic patterns by establishing conditions for local uniqueness and identifiability of the true matrix, proposing a well-posedness condition and showing it is generic, and introducing a sequential testing procedure for rank determination with numerical validation.
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.