A Characterization of Deterministic Sampling Patterns for Low-Rank Matrix Completion

2015·Arxiv

Abstract

Abstract

Low-rank matrix completion (LRMC) problems arise in a wide variety of applications. Previous theory mainly provides conditions for completion under missing-at-random samplings. This paper studies deterministic conditions for completion. An incomplete completable if there are at most finitely many rank-r matrices that agree with all its observed entries. Finite completability is the tipping point in LRMC, as a few additional samples of a finitely completable matrix guarantee its unique completability. The main contribution of this paper is a deterministic sampling condition for finite completablility. We use this to also derive deterministic sampling conditions for unique completability that can be efficiently verified. We also show that under uniform random sampling schemes, these conditions are satisfied with high probability if O(max{r,log d}) entries per column are observed. These findings have several implications on LRMC regarding lower bounds, sample and computational complexity, the role of coherence, adaptive settings and the validation of any completion algorithm. We complement our theoretical results with experiments that support our findings and motivate future analysis of uncharted sampling regimes.

1 Introduction

Low-rank matrix completion (LRMC) has attracted a lot of attention in recent years because of its broad range of applications, e.g., recommender systems and collaborative filtering [1] and image processing [2].

The problem entails exactly recovering all the entries in a rank-r matrix, given only a subset of its entries. LRMC is usually studied under a missing-at-random and bounded-coherence model. Under this model, necessary and suffi-cient conditions for perfect recovery are known [3–8]. Other approaches require additional coherence and spectral gap conditions [9], use rigidity theory [10], algebraic geometry and matroid theory [11] to derive necessary and sufficient conditions for completion of deterministic samplings, but a characterization of completable sampling patterns remains an important open question.

We say an incomplete matrix is finitely rank-r completable if there exist at most finitely many rank-r matrices that agree with all its observed entries. There exist sampling/observation patterns that guarantee finite completablility, but if just a single one of the observed entries is instead missing, then there are infinitely many completions. Conversely, adding a few observations to such a pattern guarantees unique completability. Thus, finite completablility is the tipping point in LRMC.

Whether a matrix is finitely completable depends on which entries are observed. Yet no characterization of the sets of observed entries that allow or prevent finite completablility is known.

The main result of this paper is a sampling condition for finite completablility, that is, a condition on the observed entries of a matrix to guarantee that it can be completed in at most finitely many ways. In addition, we provide deterministic sampling conditions for unique completability that can be efficiently verified. Finally, we show that uniform random samplings with O(max{r,log d}) entries per column satisfy these conditions with high probability.

Our results have implications on LRMC regarding lower bounds, sample and computational complexity, the role of coherence, adaptive settings and validation conditions to verify the output of any completion algorithm. We complement our theoretical results with experiments that support our findings and motivate future analysis of uncharted sampling regimes.

Organization of the Paper

In Section 2 we formally state the problem and our main results. In Section 3 we discuss their implications in the context of previous work, and present our experiments. We present the proof of our main theorem in Section 4, and we leave the proofs of our other statements to Sections 5 and 6.

2 Model and Main Results

Let denote the incomplete version of a , rank-r data matrix X, observed only in the nonzero locations of , a matrix with binary entries. The goal of LRMC is to recover X from .

This problem is tantamount to identifying the r-dimensional subspace spanned by the columns in X, and this is how we will approach it. First observe that since X is rank-r, a column with fewer than r samples cannot be completed. A column with exactly r observations can be uniquely completed once is known, but it provides no information to identify . We will thus assume that:

The key insight of the paper is that observing r + 1 entries in a column of X places one constraint on what may be. For example, if we observe r + 1 entries of a particular column, then not all r-dimensional subspaces will be consistent with the entries. If we observe more columns with r + 1 entries, then even fewer subspaces will be consistent with them. In effect, each column with r + 1 observations places one constraint that an r-dimensional subspace must satisfy in order to be consistent with the observations. The observed entries in different columns may or may not produce redundant constraints. As we will see, the pattern of observed entries determines whether or not the constraints are redundant, thus indicating the number of subspaces that satisfy them. The main result of this paper is a simple condition on the pattern of observed entries that guarantees that only a finite number of subspaces satisfies all the constraints. This in turn provides a simple condition for exact matrix completion.

Remark 1. We point out that any observation, in addition to the r + 1 per column that we assume, cannot increase the number of rank-r matrices that agree with the observations. So in general, if some columns of X are observed on more than r + 1 entries, all we need is that the observed entries include a pattern with exactly r + 1 observations per column satisfying our sampling conditions.

Also notice that completing X is the same as completing , so a row with fewer than r observations cannot be completed. While we do not assume that each row is observed on at least r entries, our sampling conditions guarantee that this is the case.

Let Grdenote the Grassmannian manifold of r-dimensional subspaces in . Observe that each rank-r matrix X can be uniquely represented in terms of a subspace Gr(spanning the columns of X) and an coefficient matrix . See Figure 1 to build some intuition. Let denote the uniform measure on Gr, and the Lebesgue measure on . Our statements hold for almost every (a.e.) X with respect to the product measure .

The paper’s main result is the following theorem, which gives a deterministic sampling condition to guarantee that at most a finite number of r-dimensional subspaces are consistent with .

Given a matrix, let denote its number of columns and the number of its nonzero rows.

Figure 1: Each column in a rank-r matrix X corresponds to a point in an r-dimensional subspace . In these figures, is a 2-dimensional subspace (plane) in general position. In the left, the columns of X are in general position inside , that is, drawn independently according to an absolutely continuous distribution with respect to the Lebesgue measure on , for example, according to a gaussian distribution on . In this case, the probability of observing a sample as in the right, where all columns lie in a line inside , is zero. Our results hold for every rank-r matrix, except for a set of measure zero of pathological cases as in the right.

The proof of Theorem 1 is given in Section 4. In words, condition (i) asks that every subset of n columns of has at least n/r + r nonzero rows.

such that has exactly r+1 nonzero entries per column. This way, each column of encodes exactly one constraint that candidate subspaces must satisfy in order to be consistent with the observed data. In this case we can simply take to be the matrix formed with the first columns of . One may verify that satisfies (i). Hence satisfies the conditions of Theorem 1.

Unique Completability

Theorem 1 is easily extended to a condition on that is sufficient to guarantee that one and only one subspace is consistent with , which in turn suffices for exact matrix completion.

The proof of Theorem 2 is given in Section 5. In words, condition (ii) asks that every subset of n columns of has at least n+r nonzero rows. Notice that (1) is a weaker condition than (2), but (1) is required to hold for all the subsets of columns, while (2) is required to hold only for all the subsets of columns.

Example 2. Consider as in Example 1. Take to be the matrix formed with the first columns of and to be the matrix formed with the last columns of . One may verify that satisfies (i) and that satisfies (ii). Hence satisfies the conditions of Theorem 2.

Theorem 1 implies that columns with r + 1 entries are necessary for finite completablility (hence also for unique completability). There are cases when columns are also sufficient for unique completability, e.g., if r = 1, where finite completablility is equivalent to unique completability (see Proposition 1).

In general, though, unique completability requires more columns than finite completablility (see Example 5). Theorem 2 gives deterministic sufficient sampling conditions for unique completability that only require columns. This shows that with just a few more observations, unique completability follows from finite completablility.

We point out that when the conditions of Theorem 2 are met, can be uniquely identified as

where V is the unique solution to the polynomial system F(V) = 0, with F as defined in Section 4.

Once is known, X can be perfectly recovered observing only r entries per column. To see this, let be a basis of , and let be a subset of {1,... ,d} with exactly r elements. We will use the subscript to denote restriction to the rows in . Since the coefficients of column x in the basis are given by , we can recover the entire column as .

In general, verifying condition (i) in Theorems 1 and 2 may be computationally prohibitive, especially for large d. On the other hand, one can easily and effi-ciently verify whether (ii) is satisfied by checking the dimension of the null-space of a sparse matrix (Algorithm 1). Fortunately, there is a tight relation between conditions (i) and (ii), summarized in the following lemma. The proofs of the statements in this section are given in Section 6.

Lemma 1. Let be a matrix formed with a subset of the columns in . Suppose can be partitioned into r matrices , each of size , such that (ii) holds for every . Then satisfies (i).

As consequence of Lemma 1 we obtain an additional sufficient condition for completability that only involves (ii).

Corollary 1. Let be given, and suppose A1 holds. Then almost every X can be uniquely recovered from if contains r + 1 disjoint matrices , each of size , such that (ii) holds for every .

Example 3. Consider as in Example 1. We can partition into , as depicted in Example 1. One may verify that satisfies (ii) for every 1. Hence satisfies the conditions of Corollary 1.

With Corollary 1 we show that completable patterns appear with high probability under uniform random sampling schemes with as little as O(max{r,log d}) samples per column.

Theorem 3. Let 0 1 be given. Suppose and that each column of X is observed in at least entries, distributed uniformly at random and independently across columns, with

Then with probability at least 1 will be finitely rank-r completable (if ) and uniquely completable (if ).

In many situations, though, sampling is not uniform. For instance, in vision, occlusion of objects can produce missing data in very non-uniform random patterns. In cases like this, we can partition (e.g., randomly) into matrices , each with columns. We can use Algorithm 1 below to determine whether each satisfies (ii). If this is the case, is completable by Corollary 1. More about this is discussed in Section 3.

To present the algorithm, let us introduce the matrix A that will allow us to determine efficiently whether a sampling satisfies (ii). Let be a matrix formed with ˘columns of , and let index the nonzero entries in the column of . Let U be a matrix drawn according to , an absolutely continuous distribution with respect to the Lebesgue measure on , and let denote the restriction of U to the nonzero rows in . Let be a nonzero vector in ker , and be the vector in with the entries of in the nonzero locations of and zeros elsewhere. Finally, let A denote the