Distributed Matrix Completion and Robust Factorization

Introduction

The scale of modern scientific and technological datasets poses major new challenges for computational and statistical science. Data analyses and learning algorithms suitable for modest-sized datasets are often entirely infeasible for the terabyte and petabyte datasets that are fast becoming the norm. There are two basic responses to this challenge. One response is to abandon algorithms that have superlinear complexity, focusing attention on simplified algorithms that—in the setting of massive data—may achieve satisfactory results because of the statistical strength of the data. While this is a reasonable research strategy, it requires developing suites of algorithms of varying computational complexity for each inferential task and calibrating statistical and computational efficiencies. There are many open problems that need to be solved if such an effort is to bear fruit.

The other response to the massive data problem is to retain existing algorithms but to apply them to subsets of the data. To obtain useful results under this approach, one embraces parallel and distributed computing architectures, applying existing base algorithms to multiple subsets of the data in parallel and then combining the results. Such a divide-and-conquer methodology has two main virtues: (1) it builds directly on algorithms that have proven their value at smaller scales and that often have strong theoretical guarantees, and (2) it requires little in the way of new algorithmic development. The major challenge, however, is in preserving the theoretical guarantees of the base algorithm once one embeds the algorithm in a computationally-motivated divide-and-conquer procedure. Indeed, the theoretical guarantees often refer to subtle statistical properties of the data-generating mechanism (e.g., sparsity, information spread, and near low-rankedness). These may or may not be retained under the “divide” step of a putative divide-and-conquer solution. In fact, we generally would expect subsampling operations to damage the relevant statistical structures. Even if these properties are preserved, we face the difficulty of combining the intermediary results of the “divide” step into a final consilient solution to the original problem. The question, therefore, is whether we can design divide-and-conquer algorithms that manage the tradeoffs relating these statistical properties to the computational degrees of freedom such that the overall algorithm provides a scalable solution that retains the theoretical guarantees of the base algorithm.

In this paper,A preliminary form of this work appears in Mackey et al. . we explore this issue in the context of an important class of machine learning algorithms—the matrix factorization algorithms underlying a wide variety of practical applications, including collaborative filtering for recommender systems (e.g., and the references therein), link prediction for social networks , click prediction for web search , video surveillance , graphical model selection , document modeling , and image alignment . We focus on two instances of the general matrix factorization problem: noisy matrix completion , where the goal is to recover a low-rank matrix from a small subset of noisy entries, and noisy robust matrix factorization , where the aim is to recover a low-rank matrix from corruption by noise and outliers of arbitrary magnitude. These two classes of matrix factorization problems have attracted significant interest in the research community.

Various approaches have been proposed for scalable noisy matrix factorization problems, in particular for noisy matrix completion, though the vast majority tackle rank-constrained non-convex formulations of these problems with no assurance of finding optimal solutions . In contrast, convex formulations of noisy matrix factorization relying on the nuclear norm have been shown to admit strong theoretical estimation guarantees , and a variety of algorithms [e.g., 27, 28, 42] have been developed for solving both matrix completion and robust matrix factorization via convex relaxation. Unfortunately, however, all of these methods are inherently sequential, and all rely on the repeated and costly computation of truncated singular value decompositions (SVDs), factors that severely limit the scalability of the algorithms. Moreover, previous attempts at reducing this computational burden have introduced approximations without theoretical justification .

To address this key problem of noisy matrix factorization in a scalable and theoretically sound manner, we propose a divide-and-conquer framework for large-scale matrix factorization. Our framework, entitled Divide-Factor-Combine (DFC), randomly divides the original matrix factorization task into cheaper subproblems, solves those subproblems in parallel using a base matrix factorization algorithm for nuclear norm regularized formulations, and combines the solutions to the subproblems using efficient techniques from randomized matrix approximation. We develop a thoroughgoing theoretical analysis for the DFC framework, linking statistical properties of the underlying matrix to computational choices in the algorithms and thereby providing conditions under which statistical estimation of the underlying matrix is possible. We also present experimental results for several DFC variants demonstrating that DFC can provide near-linear to superlinear speed-ups in practice.

The remainder of the paper is organized as follows. In Sec. 2, we define the setting of noisy matrix factorization and introduce the components of the DFC framework. Secs. 3, 4, and 5 present our theoretical analysis of DFC, along with a new analysis of convex noisy matrix completion and a novel characterization of randomized matrix approximation algorithms. To illustrate the practical speed-up and robustness of DFC, we present experimental results on collaborative filtering, video background modeling, and simulated data in Sec. 6. Finally, we conclude in Sec. 7.

The Divide-Factor-Combine Framework

In this section, we present a general divide-and-conquer framework for scalable noisy matrix factorization. We begin by defining the problem setting of interest.

Our goal is to estimate the low-rank matrix ${\mathbf{L}}_{0}$ from ${\mathcal{P}}_{{\Omega}}({\mathbf{M}})$ with error proportional to the noise level $\Delta\triangleq{\|{{\mathbf{Z}}_{0}}\|}_{F}$. We will focus on two specific instances of this general problem:

Noisy Matrix Completion (MC): $s\triangleq|{\Omega}|$ entries of ${\mathbf{M}}$ are revealed uniformly without replacement, along with their locations. There are no outliers, so that ${\mathbf{S}}_{0}$ is identically zero.

Noisy Robust Matrix Factorization (RMF): ${\mathbf{S}}_{0}$ is identically zero save for $s$ outlier entries of arbitrary magnitude with unknown locations distributed uniformly without replacement. All entries of ${\mathbf{M}}$ are observed, so that ${\mathcal{P}}_{{\Omega}}({\mathbf{M}})={\mathbf{M}}$.

2 Divide-Factor-Combine

The Divide-Factor-Combine (DFC) framework divides the expensive task of matrix factorization into smaller subproblems, executes those subproblems in parallel, and then efficiently combines the results into a final low-rank estimate of ${\mathbf{L}}_{0}$. We highlight three variants of this general framework in Algorithms 1, 2, and 3. These algorithms, which we refer to as DFC-Proj, DFC-RP, and DFC-Nys, differ in their strategies for division and recombination but adhere to a common pattern of three simple steps:

Divide input matrix into submatrices: DFC-Proj and DFC-RP randomly partition ${\mathcal{P}}_{{\Omega}}({\mathbf{M}})$ into $t$ $l$-column submatrices, $\{{\mathcal{P}}_{{\Omega}}({\mathbf{C}}_{1}),\ldots,{\mathcal{P}}_{{\Omega}}({\mathbf{C}}_{t})\}$,For ease of discussion, we assume that $t$ evenly divides $n$ so that $l=n/t$. In general, ${\mathcal{P}}_{{\Omega}}({\mathbf{M}})$ can always be partitioned into $t$ submatrices, each with either $\lfloor n/t\rfloor$ or $\lceil n/t\rceil$ columns. while DFC-Nys selects an $l$-column submatrix, ${\mathcal{P}}_{{\Omega}}({\mathbf{C}})$, and a $d$-row submatrix, ${\mathcal{P}}_{{\Omega}}({\mathbf{R}})$, uniformly at random.

Factor each submatrix in parallel using any base MF algorithm: DFC-Proj and DFC-RP perform $t$ parallel submatrix factorizations, while DFC-Nys performs two such parallel factorizations. Standard base MF algorithms output the following low-rank approximations: $\{\hat{\mathbf{C}}_{1},\ldots,\hat{\mathbf{C}}_{t}\}$ for DFC-Proj and DFC-RP; $\hat{\mathbf{C}}$ and $\hat{\mathbf{R}}$ for DFC-Nys. All matrices are retained in factored form.

Combine submatrix estimates: DFC-Proj generates a final low-rank estimate ${\hat{{\mathbf{L}}}^{proj}}$ by projecting $[\hat{\mathbf{C}}_{1},\ldots,\hat{\mathbf{C}}_{t}]$ onto the column space of $\hat{\mathbf{C}}_{1}$, DFC-RP uses random projection to compute a rank-$k$ estimate ${\hat{{\mathbf{L}}}^{rp}}$ of $[\hat{\mathbf{C}}_{1}\cdots\hat{\mathbf{C}}_{t}]$ where $k$ is the median rank of the returned subproblem estimates, and DFC-Nys forms the low-rank estimate ${\hat{{\mathbf{L}}}^{nys}}$ from $\hat{\mathbf{C}}$ and $\hat{\mathbf{R}}$ via the generalized Nyström method. These matrix approximation techniques are described in more detail in Sec. 2.3.

3 Randomized Matrix Approximations

Underlying the C step of each DFC algorithm is a method for generating randomized low-rank approximations to an arbitrary matrix ${\mathbf{M}}$.

DFC-Proj (Algorithm 1) uses the column projection method of Frieze et al. . Suppose that ${\mathbf{C}}$ is a matrix of $l$ columns sampled uniformly and without replacement from the columns of ${\mathbf{M}}$. Then, column projection generates a “matrix projection” approximation of ${\mathbf{M}}$ via

In practice, we do not reconstruct ${\mathbf{L}}^{proj}$ but rather maintain low-rank factors, e.g., ${\mathbf{U}}_{C}$ and ${\mathbf{U}}_{C}^{\top}{\mathbf{M}}$.

We work with an implementation of a numerically stable variant of this algorithm described in Algorithm $4.4$ of Halko et al. . Moreover, the parameters $p$ and $q$ are typically set to small positive constants , and we set $p=5$ and $q=2$.

The Nyström method was developed for the discretization of integral equations and has since been used to speed up large-scale learning applications involving symmetric positive semidefinite matrices . DFC-Nys (Algorithm 3) makes use of a generalization of the Nyström method for arbitrary real matrices . Suppose that ${\mathbf{C}}$ consists of $l$ columns of ${\mathbf{M}}$, sampled uniformly without replacement, and that ${\mathbf{R}}$ consists of $d$ rows of ${\mathbf{M}}$, independently sampled uniformly and without replacement. Let ${\mathbf{W}}$ be the $d\times l$ matrix formed by sampling the corresponding rows of ${\mathbf{C}}$.This choice is arbitrary: ${\mathbf{W}}$ could also be defined as a submatrix of ${\mathbf{R}}$. Then, the generalized Nyström method computes a “spectral reconstruction” approximation of ${\mathbf{M}}$ via

As with ${\mathbf{M}}^{proj}$, we store low-rank factors of ${\mathbf{L}}^{nys}$, such as ${\mathbf{C}}{\mathbf{V}}_{W}{\mathbf{\Sigma}}_{W}^{+}$ and ${\mathbf{U}}_{W}^{\top}{\mathbf{R}}$.

4 Running Time of DFC

Many state-of-the-art MF algorithms have $\Omega(mnk_{M})$ per-iteration time complexity due to the rank-$k_{M}$ truncated SVD performed on each iteration. DFC significantly reduces the per-iteration complexity to O$(mlk_{C_{i}})$ time for ${\mathbf{C}}_{i}$ (or ${\mathbf{C}}$) and O$(ndk_{R})$ time for ${\mathbf{R}}$. The cost of combining the submatrix estimates is even smaller when using column projection or the generalized Nyström method, since the outputs of standard MF algorithms are returned in factored form. Indeed, if we define $k^{\prime}\triangleq\max_{i}k_{C_{i}}$, then the column projection step of DFC-Proj requires only O$(mk^{\prime 2}+lk^{\prime 2})$ time: O$(mk^{\prime 2}+lk^{\prime 2})$ time for the pseudoinversion of $\hat{\mathbf{C}}_{1}$ and O$(mk^{\prime 2}+lk^{\prime 2})$ time for matrix multiplication with each $\hat{\mathbf{C}}_{i}$ in parallel. Similarly, the generalized Nyström step of DFC-Nys requires only O(l\bar{k}^{2}+d\bar{k}^{2}+\min\mathopen{}\mathclose{{}\left({m,n}}\right)\bar{k}^{2}) time, where \bar{k}\triangleq\max\mathopen{}\mathclose{{}\left({k_{C},k_{R}}}\right).

DFC-RP also benefits from the factored form of the outputs of standard MF algorithms. Assuming that $p$ and $q$ are positive constants, the random projection step of DFC-RP requires O($mkt+mkk^{\prime}+nk$) time where $k$ is the low-rank parameter of ${\mathbf{Q}}$: O($nk$) time to generate ${\mathbf{G}}$, O($mkk^{\prime}+mkt$) to compute ${\mathbf{Y}}$ in parallel, O($mk^{2}$) to compute the SVD of ${\mathbf{Y}}$, and O$(mk^{\prime 2}+lk^{\prime 2})$ time for matrix multiplication with each $\hat{\mathbf{C}}_{i}$ in parallel in the final projection step. Note that the running time of the random projection step depends on $t$ (even when executed in parallel) and thus has a larger complexity than the column projection and generalized Nyström variants. Nevertheless, the random projection step need be performed only once and thus yields a significant savings over the repeated computation of SVDs required by typical base algorithms.

5 Ensemble Methods

Ensemble methods have been shown to improve performance of matrix approximation algorithms, while straightforwardly leveraging the parallelism of modern many-core and distributed architectures . As such, we propose ensemble variants of the DFC algorithms that demonstrably reduce estimation error while introducing a negligible cost to the parallel running time. For DFC-Proj-Ens, rather than projecting only onto the column space of $\hat{\mathbf{C}}_{1}$, we project $[\hat{\mathbf{C}}_{1},\ldots,\hat{\mathbf{C}}_{t}]$ onto the column space of each $\hat{\mathbf{C}}_{i}$ in parallel and then average the $t$ resulting low-rank approximations. For DFC-RP-Ens, rather than projecting only onto a column space derived from a single random matrix ${\mathbf{G}}$, we project $[\hat{\mathbf{C}}_{1},\ldots,\hat{\mathbf{C}}_{t}]$ onto $t$ column spaces derived from $t$ random matrices in parallel and then average the $t$ resulting low-rank approximations. For DFC-Nys-Ens, we choose a random $d$-row submatrix ${\mathcal{P}}_{{\Omega}}({\mathbf{R}})$ as in DFC-Nys and independently partition the columns of ${\mathcal{P}}_{{\Omega}}({\mathbf{M}})$ into $\{{\mathcal{P}}_{{\Omega}}({\mathbf{C}}_{1}),\ldots,{\mathcal{P}}_{{\Omega}}({\mathbf{C}}_{t})\}$ as in DFC-Proj and DFC-RP. After running the base MF algorithm on each submatrix, we apply the generalized Nyström method to each $(\hat{\mathbf{C}}_{i},\hat{\mathbf{R}})$ pair in parallel and average the $t$ resulting low-rank approximations. Sec. 6 highlights the empirical effectiveness of ensembling.

Roadmap of Theoretical Analysis

While DFC in principle can work with any base matrix factorization algorithm, it offers the greatest benefits when united with accurate but computationally expensive base procedures. Convex optimization approaches to matrix completion and robust matrix factorization [e.g., 27, 28, 42] are prime examples of this class, since they admit strong theoretical estimation guarantees but suffer from poor computational complexity due to the repeated and costly computation of truncated SVDs. Sec. 6 will provide empirical evidence that DFC provides an attractive framework to improve the scalability of these algorithms, but we first present a thorough theoretical analysis of the estimation properties of DFC.

Over the course of the next three sections, we will show that the same assumptions that give rise to strong estimation guarantees for standard MF formulations also guarantee strong estimation properties for DFC. In the remainder of this section, we first introduce these standard assumptions and then present simplified bounds to build intuition for our theoretical results and our underlying proof techniques.

Since not all matrices can be recovered from missing entries or gross outliers, recent theoretical advances have studied sufficient conditions for accurate noisy MC and RMF . Informally, these conditions capture the degree to which information about a single entry is “spread out” across a matrix. The ease of matrix estimation is correlated with this spread of information. The most prevalent set of conditions are matrix coherence conditions, which limit the extent to which the singular vectors of a matrix are correlated with the standard basis. However, there exist classes of matrices that violate the coherence conditions but can nonetheless be recovered from missing entries or gross outliers. Negahban and Wainwright define an alternative notion of matrix spikiness in part to handle these classes.

Letting ${\mathbf{e}}_{i}$ be the $i$th column of the standard basis, we define two standard notions of coherence :

1.2 Matrix Spikiness

The matrix spikiness condition of Negahban and Wainwright captures the intuition that a matrix is easier to estimate if its maximum entry is not much larger than its average entry (in the root mean square sense):

We call a matrix $\alpha$-spiky if $\alpha({\mathbf{L}})\leq\alpha$.

Our analysis in Sec. 5 will focus on base MC algorithms that express their estimation guarantees in terms of the $\alpha$-spikiness of the target low-rank matrix ${\mathbf{L}}_{0}$. For such algorithms, lower values of $\alpha$ correspond to better estimation properties.

2 Prototypical Estimation Bounds

We now present a prototypical estimation bound for DFC. Suppose that a base MC algorithm solves the noisy nuclear norm heuristic, studied in Candès and Plan :

and that, for simplicity, ${\mathbf{M}}$ is square. The following prototype bound, derived from a new noisy MC guarantee in Thm. 10, describes the behavior of this estimator under matrix coherence assumptions. Note that the bound implies exact recovery in the noiseless setting, i.e., when $\Delta=0$.

with high probability, where $f$ is a function of $n$.

Now we present a corresponding prototype bound for DFC-Proj, a simplified version of our Cor. 13, under precisely the same coherence assumptions. Notably, this bound i) preserves accuracy with a flexible $(2+\epsilon)$ degradation in estimation error over the base algorithm, ii) allows for speed-up by requiring only a vanishingly small fraction of columns to be sampled (i.e., $l/n\rightarrow 0$) whenever $s=\omega(n\log^{2}(n))$ entries are revealed, and iii) maintains exact recovery in the noiseless setting.

with high probability when the noisy nuclear norm heuristic is used as a base algorithm, where $f$ is the same function of $n$ defined in Proto. 1.

The proof of Proto. 2, and indeed of each of our main DFC results, consists of three high-level steps:

Bound information spread of submatrices: Recall that the F step of DFC operates by applying a base MF algorithm to submatrices. We show that, with high probability, uniformly sampled submatrices are only moderately more coherent and moderately more spiky than the matrix from which they are drawn. This allows for accurate estimation of submatrices using base algorithms with standard coherence or spikiness requirements. The conservation of incoherence result is summarized in Lem. 4, while the conservation of non-spikiness is presented in Lem. 15.

Bound error of submatrix factorizations: The final step combines a master theorem with a base estimation guarantee applied to each DFC subproblem. We study both new (Thm. 10) and established bounds (Thm. 11 and Cor. 17) for MC and RMF and prove that DFC submatrices satisfy the base guarantee preconditions with high probability. We present the resulting coherence-based estimation guarantees for DFC in Cor. 13 and Cor. 14 and the spikiness-based estimation guarantee in Cor. 19.

The next two sections present the main results contributing to each of these proof steps, as well as their consequences for MC and RMF. Sec. 4 presents our analysis under coherence assumptions, while Sec. 5 contains our spikiness analysis.

Coherence-based Theoretical Analysis

We begin our coherence-based analysis by characterizing the behavior of randomized approximation algorithms under standard coherence assumptions. The derived properties will aid us in deriving DFC estimation guarantees. Hereafter, $\epsilon\in(0,1]$ represents a prescribed error tolerance, and $\delta,\delta^{\prime}\in(0,1]$ denote target failure probabilities.

Our first result bounds the $\mu_{0}$ and $\mu_{1}$-coherence of a uniformly sampled submatrix in terms of the coherence of the full matrix. This conservation of incoherence allows for accurate submatrix completion or submatrix outlier removal when using standard MC and RMF algorithms. Its proof is given in Sec. B.

$\mu_{0}({\mathbf{U}}_{L_{C}})=\mu_{0}({\mathbf{U}}_{L})$

$\displaystyle\mu_{0}({\mathbf{V}}_{L_{C}})\leq\frac{\mu_{0}({\mathbf{V}}_{L})}{1-\epsilon/2}$

$\displaystyle\mu_{1}^{2}({\mathbf{L}}_{C})\leq\frac{r\mu_{0}({\mathbf{U}}_{L})\mu_{0}({\mathbf{V}}_{L})}{1-\epsilon/2}$

all hold jointly with probability at least $1-\delta/n$.

1.2 Column Projection Analysis

Our next result shows that projection based on uniform column sampling leads to near optimal estimation in matrix regression when the covariate matrix has small coherence. This statement will immediately give rise to estimation guarantees for column projection and the generalized Nyström method.

with probability at least $1-\delta-0.2$.

A first consequence of Thm. 5 shows that, with high probability, column projection produces an estimate nearly as good as a given rank-$r$ target by sampling a number of columns proportional to the coherence and $r\log n$.

Our result generalizes Thm. 1 of Drineas et al. by providing improved sampling complexity and guarantees relative to an arbitrary low-rank approximation. Notably, in the “noiseless” setting, when ${\mathbf{M}}={\mathbf{L}}$, Cor. 6 guarantees exact recovery of ${\mathbf{M}}$ with high probability. The proof of Cor. 6 is given in Sec. C.

1.3 Generalized Nyström Analysis

Thm. 5 and Cor. 6 together imply an estimation guarantee for the generalized Nyström method relative to an arbitrary low-rank approximation ${\mathbf{L}}$. Indeed, if the matrix of sampled columns is denoted by ${\mathbf{C}}$, then, with appropriately reduced probability, O($\mu_{0}({\mathbf{V}}_{L})r\log n$) columns and O($\mu_{0}({\mathbf{U}}_{C})r\log m$) rows suffice to match the reconstruction error of ${\mathbf{L}}$ up to any fixed precision. The proof can be found in Sec. D.

with probability at least $(1-\delta)(1-\delta^{\prime}-0.2)$.

Like the generalized Nyström bound of Drineas et al. [9, Thm. 4] and unlike our column projection result, Cor. 7 depends on the coherence of the submatrix ${\mathbf{C}}$ and holds only with probability bounded away from 1. Our next contribution shows that we can do away with these restrictions in the noiseless setting, where ${\mathbf{M}}={\mathbf{L}}$.

The proof of Cor. 8, given in Sec. E, adapts a strategy of Talwalkar and Rostamizadeh developed for the analysis of positive semidefinite matrices.

1.4 Random Projection Analysis

We next present an estimation guarantee for the random projection method relative to an arbitrary low-rank approximation ${\mathbf{L}}$. The result implies that using a random matrix with oversampled columns proportional to $r\log(1/\delta)$ suffices to match the reconstruction error of ${\mathbf{L}}$ up to any fixed precision with probability $1-\delta$. The result is a direct consequence of the random projection analysis of Halko et al. [15, Thm. 10.7], and the proof can be found in Sec. F.

Draw an $n\times(r+p)$ standard Gaussian matrix ${\mathbf{G}}$ and define ${\mathbf{Y}}={\mathbf{M}}{\mathbf{G}}$. Then, with probability at least $1-\delta$,

Moreover, define ${\mathbf{L}}^{rp}$ as the best rank-$r$ approximation of ${\mathbf{P}}_{Y}{\mathbf{M}}$ with respect to the Frobenius norm. Then, with probability at least $1-\delta$,

We note that, in contrast to Cor. 6 and Cor. 7, Cor. 9 does not depend on the coherence of ${\mathbf{L}}$ and hence can be fruitfully applied even in the absence of an incoherence assumption. We demonstrate such a use case in Sec. 5.

2 Base Algorithm Guarantees

As prototypical examples of the coherence-based estimation guarantees available for noisy MC and noisy RMF, consider the following two theorems. The first bounds the estimation error of a convex optimization approach to noisy matrix completion, under the assumptions of incoherence and uniform sampling.

entries of ${\mathbf{M}}$ are observed with locations ${\Omega}$ sampled uniformly without replacement. Then, if $m\leq n$ and ${\|{{\mathcal{P}}_{{\Omega}}({\mathbf{M}})-{\mathcal{P}}_{{\Omega}}({\mathbf{L}}_{0})}\|}_{F}\leq\Delta$ a.s., the minimizer $\hat{{\mathbf{L}}}$ of the problem

with probability at least $1-4\log(n)n^{2-2\beta}$ for $c_{e}$ a positive constant.

A similar estimation guarantee was obtained by Candès and Plan under stronger assumptions. We give the proof of Thm. 10 in Sec. J.

The second result, due to Zhou et al. and reformulated for a generic rate parameter $\beta$, as described in Candès et al. [2, Section 3.1], bounds the estimation error of a convex optimization approach to noisy RMF, under the assumptions of incoherence and uniformly distributed outliers.

Suppose that ${\mathbf{L}}_{0}$ is $(\mu,r)$-coherent and that the support set of ${\mathbf{S}}_{0}$ is uniformly distributed among all sets of cardinality $s$. Then, if $m\leq n$ and ${\|{{\mathbf{M}}-{\mathbf{L}}_{0}-{\mathbf{S}}_{0}}\|}_{F}\leq\Delta$ a.s., there is a constant $c_{p}$ such that with probability at least $1-c_{p}n^{-\beta}$, the minimizer $(\hat{{\mathbf{L}}},\hat{{\mathbf{S}}})$ of the problem

satisfies ${\|{{\mathbf{L}}_{0}-\hat{{\mathbf{L}}}}\|}_{F}^{2}+{\|{{\mathbf{S}}_{0}-\hat{{\mathbf{S}}}}\|}_{F}^{2}\leq c_{e}^{\prime 2}mn\Delta^{2}$, provided that

for target rate parameter $\beta>2$, and positive constants $\rho_{r},\rho_{s},$ and $c_{e}^{\prime}$.

3 Coherence Master Theorem

Choose $t=n/l$, $l\geq cr\mu\log(n)\log(2/\delta)/\epsilon^{2}$, where $c$ is a fixed positive constant, and $p\geq 242\ r\log(14/\delta)/\epsilon^{2}$. Under the notation of Algorithms 1 and 2, let $\{{\mathbf{C}}_{0,1},\cdots,{\mathbf{C}}_{0,t}\}$ be the corresponding partition of ${\mathbf{L}}_{0}$. Then, with probability at least $1-\delta$, ${\mathbf{C}}_{0,i}$ is $(\frac{r\mu^{2}}{1-\epsilon/2},r)$-coherent for all $i$, and

where $\hat{{\mathbf{L}}}^{*}$ is the estimate returned by either DFC-Proj or DFC-RP.

Under the notation of Algorithm 3, let ${\mathbf{C}}_{0}$ and ${\mathbf{R}}_{0}$ be the corresponding column and row submatrices of ${\mathbf{L}}_{0}$. If in addition $d\geq cl\mu_{0}(\hat{\mathbf{C}})\log(m)\log(4/\delta)/\epsilon^{2}$, then, with probability at least $(1-\delta)(1-\delta-0.2)$, DFC-Nys guarantees that ${\mathbf{C}}_{0}$ and ${\mathbf{R}}_{0}$ are $(\frac{r\mu^{2}}{1-\epsilon/2},r)$-coherent and that

Remark The DFC-Nys guarantee requires the number of rows sampled to grow in proportion to $\mu_{0}(\hat{\mathbf{C}})$, a quantity always bounded by $\mu$ in our simulations. Here and in the consequences to follow, the DFC-Nys result can be strengthened in the noiseless setting ($\Delta=0$) by utilizing Cor. 8 in place of Cor. 7 in the proof of Thm. 12.

When a target matrix is incoherent, Thm. 12 asserts that – with high probability for DFC-Proj and DFC-RP and with fixed probability for DFC-Nys – the estimation error of DFC is not much larger than the error sustained by the base algorithm on each subproblem. Because Thm. 12 further bounds the coherence of each submatrix, we can use any coherence-based matrix estimation guarantee to control the estimation error on each subproblem. The next two sections demonstrate how Thm. 12 can be applied to derive specific DFC estimation guarantees for noisy MC and noisy RMF. In these sections, we let \bar{n}\triangleq\max\mathopen{}\mathclose{{}\left({m,n}}\right).

4 Consequences for Noisy MC

As a first consequence of Thm. 12, we will show that DFC retains the high-probability estimation guarantees of a standard MC solver while operating on matrices of much smaller dimension. Suppose that a base MC algorithm solves the convex optimization problem of Eq. (4). Then, Cor. 13 follows from the Coherence Master Theorem (Thm. 12) and the base algorithm guarantee of Thm. 10.

Suppose that ${\mathbf{L}}_{0}$ is $(\mu,r)$-coherent and that $s$ entries of ${\mathbf{M}}$ are observed, with locations ${\Omega}$ distributed uniformly. Fix any target rate parameter $\beta>1$. Then, if ${\|{{\mathcal{P}}_{{\Omega}}({\mathbf{M}})-{\mathcal{P}}_{{\Omega}}({\mathbf{L}}_{0})}\|}_{F}\leq\Delta$ a.s., and the base algorithm solves the optimization problem of Eq. (4), it suffices to choose $t=n/l,$

and $p\geq 242\ r\log(14\bar{n}^{2\beta-2})/\epsilon^{2}$ to achieve

${\|{{\mathbf{L}}_{0}-{\hat{{\mathbf{L}}}^{proj}}}\|}_{F}\leq(2+\epsilon)c_{e}\sqrt{mn}\Delta$

${\|{{\mathbf{L}}_{0}-{\hat{{\mathbf{L}}}^{rp}}}\|}_{F}\leq(2+\epsilon)c_{e}\sqrt{mn}\Delta$

${\|{{\mathbf{L}}_{0}-{\hat{{\mathbf{L}}}^{nys}}}\|}_{F}\leq(2+3\epsilon)c_{e}\sqrt{ml+dn}\Delta$

$1-(5t\log(\bar{n})+1)\bar{n}^{2-2\beta}\geq 1-\bar{n}^{3-2\beta}$

$1-(10\log(\bar{n})+2)\bar{n}^{2-2\beta}-0.2$,

respectively, with $c$ as in Thm. 12 and $c_{e}$ as in Thm. 10.

Remark Cor. 13 allows for the fraction of columns and rows sampled to decrease as the number of revealed entries, $s$, increases. Only a vanishingly small fraction of columns ($l/n\to 0$) and rows ($d/\bar{n}\to 0$) need be sampled whenever $s=\omega((m+n)\log^{2}(m+n))$.

To understand the conclusions of Cor. 13, consider the base algorithm of Thm. 10, which, when applied to ${\mathcal{P}}_{{\Omega}}({\mathbf{M}})$, recovers an estimate $\hat{{\mathbf{L}}}$ satisfying ${\|{{\mathbf{L}}_{0}-\hat{{\mathbf{L}}}}\|}_{F}\leq c_{e}\sqrt{mn}\Delta$ with high probability. Cor. 13 asserts that, with appropriately reduced probability, DFC-Proj and DFC-RP exhibit the same estimation error scaled by an adjustable factor of $2+\epsilon$, while DFC-Nys exhibits a somewhat smaller error scaled by $2+3\epsilon$.

The key take-away is that DFC introduces a controlled increase in error and a controlled decrement in the probability of success, allowing the user to interpolate between maximum speed and maximum accuracy. Thus, DFC can quickly provide near-optimal estimation in the noisy setting and exact recovery in the noiseless setting ($\Delta=0)$, even when entries are missing. The proof of Cor. 13 can be found in Sec. H.

5 Consequences for Noisy RMF

Our next corollary shows that DFC retains the high-probability estimation guarantees of a standard RMF solver while operating on matrices of much smaller dimension. Suppose that a base RMF algorithm solves the convex optimization problem of Eq. (5). Then, Cor. 14 follows from the Coherence Master Theorem (Thm. 12) and the base algorithm guarantee of Thm. 11.

Suppose that ${\mathbf{L}}_{0}$ is $(\mu,r)$-coherent with

for a positive constant $\rho_{r}$. Suppose moreover that the uniformly distributed support set of ${\mathbf{S}}_{0}$ has cardinality $s$. For a fixed positive constant $\rho_{s}$, define the undersampling parameter

and fix any target rate parameter $\beta>2$ with rescaling $\beta^{\prime}\triangleq\beta\log(\bar{n})/\log(m)$ satisfying $4\beta_{s}-3/\rho_{s}\leq\beta^{\prime}\leq\beta_{s}$. Then, if ${\|{{\mathbf{M}}-{\mathbf{L}}_{0}-{\mathbf{S}}_{0}}\|}_{F}\leq\Delta$ a.s., and the base algorithm solves the optimization problem of Eq. (5), it suffices to choose $t=n/l$,

and $p\geq 242\ r\log(14\bar{n}^{\beta})/\epsilon^{2}$ to have

${\|{{\mathbf{L}}_{0}-{\hat{{\mathbf{L}}}^{proj}}}\|}_{F}\leq(2+\epsilon)c_{e}^{\prime}\sqrt{mn}\Delta$

${\|{{\mathbf{L}}_{0}-{\hat{{\mathbf{L}}}^{rp}}}\|}_{F}\leq(2+\epsilon)c_{e}^{\prime}\sqrt{mn}\Delta$

${\|{{\mathbf{L}}_{0}-{\hat{{\mathbf{L}}}^{nys}}}\|}_{F}\leq(2+3\epsilon)c_{e}^{\prime}\sqrt{ml+dn}\Delta$

$1-(t(c_{p}+1)+1)\bar{n}^{-\beta}\geq 1-c_{p}\bar{n}^{1-\beta}$

respectively, with $c$ as in Thm. 12 and $\rho_{r},c_{e}^{\prime},$ and $c_{p}$ as in Thm. 11.

Note that Cor. 14 places only very mild restrictions on the number of columns and rows to be sampled. Indeed, $l$ and $d$ need only grow poly-logarithmically in the matrix dimensions to achieve estimation guarantees comparable to those of the RMF base algorithm (Thm. 11). Hence, DFC can quickly provide near-optimal estimation in the noisy setting and exact recovery in the noiseless setting ($\Delta=0)$, even when entries are grossly corrupted. The proof of Cor. 14 can be found in Sec. I.

Theoretical Analysis under Spikiness Conditions

We begin our spikiness analysis by characterizing the behavior of randomized approximation algorithms under standard spikiness assumptions. The derived properties will aid us in developing DFC estimation guarantees. Hereafter, $\epsilon\in(0,1]$ represents a prescribed error tolerance, and $\delta,\delta^{\prime}\in(0,1]$ designates a target failure probability.

Our first lemma establishes that the uniformly sampled submatrices of an $\alpha$-spiky matrix are themselves nearly $\alpha$-spiky with high probability. This property will allow for accurate submatrix completion or outlier removal using standard MC and RMF algorithms. Its proof is given in Sec. K.

1.2 Column Projection Analysis

Our first theorem asserts that, with high probability, column projection produces an approximation nearly as good as a given rank-$r$ target by sampling a number of columns proportional to the spikiness and $r\log(mn)$.

with probability at least $1-\delta$, whenever ${\|{{\mathbf{M}}}\|}_{\infty}\leq\alpha/\sqrt{mn}$.

The proof of Thm. 16 builds upon the randomized matrix multiplication work of Drineas et al. and will be given in Sec. L.

2 Base Algorithm Guarantee

The next result, a reformulation of Negahban and Wainwright [34, Cor. 1], is a prototypical example of a spikiness-based estimation guarantee for noisy MC. Cor. 17 bounds the estimation error of a convex optimization approach to noisy matrix completion, under non-spikiness and uniform sampling assumptions.

entries of ${\mathbf{M}}={\mathbf{L}}_{0}+{\mathbf{Z}}_{0}$ are observed with locations ${\Omega}$ sampled uniformly with replacement, then any solution $\hat{{\mathbf{L}}}$ of the problem

with probability at least 1-c_{2}\operatorname{exp}\mathopen{}\mathclose{{}\left(-c_{3}\log(m+n)}\right) for positive constants $c_{1},c_{2},$ and $c_{3}$.

3 Spikiness Master Theorem

Choose $t=n/l$, $l\geq 13r\alpha^{4}\log(4mn/\delta)/\epsilon^{2}$, and $p\geq 242\ r\log(14/\delta)/\epsilon^{2}$. Under the notation of Algorithms 1 and 2, let $\{{\mathbf{C}}_{0,1},\cdots,{\mathbf{C}}_{0,t}\}$ be the corresponding partition of ${\mathbf{L}}_{0}$. Then, with probability at least $1-\delta$, DFC-Proj and DFC-RP guarantee that ${\mathbf{C}}_{0,i}$ is $(\sqrt{1.25}\alpha)$-spiky for all $i$ and that

whenever ${\|{\hat{\mathbf{C}}_{i}}\|}_{\infty}\leq\sqrt{1.25}\alpha/\sqrt{ml}$ for all $i$.

Remark The spikiness factor of $\sqrt{1.25}$ can be replaced with the smaller term $\sqrt{1+\epsilon/(4\sqrt{r})}$.

When a target matrix is non-spiky, Thm. 18 asserts that, with high probability, the estimation error of DFC is not much larger than the error sustained by the base algorithm on each subproblem. Thm. 18 further bounds the spikiness of each submatrix with high probability, and hence we can use any spikiness-based matrix estimation guarantee to control the estimation error on each subproblem. The next section demonstrates how Thm. 18 can be applied to derive specific DFC estimation guarantees for noisy MC.

4 Consequences for Noisy MC

Our corollary of Thm. 18 shows that DFC retains the high-probability estimation guarantees of a standard MC solver while operating on matrices of much smaller dimension. Suppose that a base MC algorithm solves the convex optimization problem of Eq. (6). Then, Cor. 19 follows from the Spikiness Master Theorem (Thm. 18) and the base algorithm guarantee of Cor. 17.

and $p\geq 242\ r\log(14(m+l)^{c_{3}})/\epsilon^{2}$ to achieve

with respective probability at least 1-(t+1)(c_{2}+1)\operatorname{exp}\mathopen{}\mathclose{{}\left(-c_{3}\log(m+l)}\right), if the base algorithm of Eq. (6) is used with $\lambda=4\nu\sqrt{(m+n)\log(m+n)/s}$.

Remark Cor. 19 allows for the fraction of columns sampled to decrease as the number of revealed entries, $s$, increases. Only a vanishingly small fraction of columns ($l/n\to 0$) need be sampled whenever $s=\omega((m+n)\log^{3}(m+n))$.

To understand the conclusions of Cor. 19, consider the base algorithm of Cor. 17, which, when applied to ${\mathbf{M}}$, recovers an estimate $\hat{{\mathbf{L}}}$ satisfying {\|{{\mathbf{L}}_{0}-\hat{{\mathbf{L}}}}\|}_{F}\leq\sqrt{c_{1}\max\mathopen{}\mathclose{{}\left({\nu^{2},1}}\right)/\beta} with high probability. Cor. 13 asserts that, with appropriately reduced probability, DFC-RP exhibits the same estimation error scaled by an adjustable factor of $2+\epsilon$, while DFC-Proj exhibits at most twice this error plus an adjustable factor of $\epsilon$. Hence, DFC can quickly provide near-optimal estimation for non-spiky matrices as well as incoherent matrices, even when entries are missing. The proof of Cor. 19 can be found in Sec. N.

Experimental Evaluation

We now explore the accuracy and speed-up of DFC on a variety of simulated and real-world datasets. We use the Accelerated Proximal Gradient (APG) algorithm of Toh and Yun as our base noisy MC algorithmOur experiments with the Augmented Lagrange Multiplier (ALM) algorithm of Lin et al. as a base algorithm (not reported) yield comparable relative speedups and performance for DFC. and the APG algorithm of Lin et al. as our base noisy RMF algorithm. We perform all experiments on an x86-64 architecture using a single 2.60 Ghz core and 30GB of main memory. We use the default parameter settings suggested by Toh and Yun and Lin et al. , and measure estimation error via root mean square error (RMSE). To achieve a fair running time comparison, we execute each subproblem in the F step of DFC in a serial fashion on the same machine using a single core. Since, in practice, each of these subproblems would be executed in parallel, the parallel running time of DFC is calculated as the time to complete the D and C steps of DFC plus the running time of the longest running subproblem in the F step. We compare DFC to two baseline methods: the base algorithm APG applied to the full matrix ${\mathbf{M}}$ and Partition, which carries out the D and F steps of DFC-Proj but omits the final C step (projection).

We first explored the estimation error of DFC as a function of $s$, using ($m=10$K, $r=10)$ with varying observation sparsity for MC and ($m=1$K, $r=10)$ with a varying percentage of outliers for RMF. The results are summarized in Figure 1. In both MC and RMF, the gaps in estimation between APG and DFC are small when sampling only 10% of rows and columns. Moreover, of the standard DFC algorithms, DFC-RP performs the best, as shown in Figures 1(a) and (b). Ensembling improves the performance of DFC-Nys and DFC-Proj, as shown in Figures 1(c) and (d), and DFC-Proj-Ens in particular consistently outperforms Partition and DFC-Nys-Ens, slightly outperforms DFC-RP, and matches the performance of APG for most settings of $s$. In practice we observe that ${\mathbf{L}}^{rp}$ equals the optimal (with respect to the spectral or Frobenius norm) rank-$k$ approximation of $[\hat{\mathbf{C}}_{1},\ldots,\hat{\mathbf{C}}_{t}]$, and thus the performance of DFC-RP consistently matches that of DFC-RP-Ens. We therefore omit the DFC-RP-Ens results in the remainder this section.

We next explored the speed-up of DFC as a function of matrix size. For MC, we revealed $4\%$ of the matrix entries and set $r=0.001\cdot m$, while for RMF we fixed the percentage of outliers to $10\%$ and set $r=0.01\cdot m$. We sampled $10\%$ of rows and columns and observed that estimation errors were comparable to the errors presented in Figure 1 for similar settings of $s$; in particular, at all values of $n$ for both MC and RMF, the errors of APG and DFC-Proj-Ens were nearly identical. Our timing results, presented in Figure 2, illustrate a near-linear speed-up for MC and a superlinear speed-up for RMF across varying matrix sizes. Note that the timing curves of the DFC algorithms and Partition all overlap, a fact that highlights the minimal computational cost of the final matrix approximation step.

2 Collaborative Filtering

Collaborative filtering for recommender systems is one prevalent real-world application of noisy matrix completion. A collaborative filtering dataset can be interpreted as the incomplete observation of a ratings matrix with columns corresponding to users and rows corresponding to items. The goal is to infer the unobserved entries of this ratings matrix. We evaluate DFC on two of the largest publicly available collaborative filtering datasets: MovieLens 10Mhttp://www.grouplens.org/ ($m=4$K, $n=6$K, $s>10$M) and the Netflix Prize datasethttp://www.netflixprize.com/ ($m=18$K, $n=480$K, $s>100$M). To generate test sets drawn from the training distribution, for each dataset, we aggregated all available rating data into a single training set and withheld test entries uniformly at random, while ensuring that at least one training observation remained in each row and column. The algorithms were then run on the remaining training portions and evaluated on the test portions of each split. The results, averaged over three train-test splits, are summarized in Table 1. Notably, DFC-Proj, DFC-Proj-Ens, DFC-Nys-Ens, and DFC-RP all outperform Partition, and DFC-Proj-Ens performs comparably to APG while providing a nearly linear parallel time speed-up. Similar to the simulation results presented in Figure 1, DFC-RP performs the best of the standard DFC algorithms, though DFC-Proj-Ens slightly outperforms DFC-RP. Moreover, the poorer performance of DFC-Nys can be in part explained by the asymmetry of these problems. Since these matrices have many more columns than rows, MF on column submatrices is inherently easier than MF on row submatrices, and for DFC-Nys, we observe that $\hat{\mathbf{C}}$ is an accurate estimate while $\hat{\mathbf{R}}$ is not.

3 Background Modeling in Computer Vision

Background modeling has important practical ramifications for detecting activity in surveillance video. This problem can be framed as an application of noisy RMF, where each video frame is a column of some matrix (${\mathbf{M}})$, the background model is low-rank (${\mathbf{L}}_{0})$, and moving objects and background variations, e.g., changes in illumination, are outliers (${\mathbf{S}}_{0})$. We evaluate DFC on two videos: ‘Hall’ ($200$ frames of size $176\times 144)$ contains significant foreground variation and was studied by Candès et al. , while ‘Lobby’ ($1546$ frames of size $168\times 120)$ includes many changes in illumination (a smaller video with $250$ frames was studied by Candès et al. ). We focused on DFC-Proj-Ens, due to its superior performance in previous experiments, and measured the RMSE between the background model estimated by DFC and that of APG. On both videos, DFC-Proj-Ens estimated nearly the same background model as the full APG algorithm in a small fraction of the time. On ‘Hall,’ the DFC-Proj-Ens-5% and DFC-Proj-Ens-0.5% models exhibited RMSEs of $0.564$ and $1.55$, quite small given pixels with $256$ intensity values. The associated running time was reduced from $342.5$s for APG to real-time ($5.2$s for a $13$s video) for DFC-Proj-Ens-0.5%. Snapshots of the results are presented in Figure 3. On ‘Lobby,’ the RMSE of DFC-Proj-Ens-4% was $0.64$, and the speed-up over APG was more than 20X, i.e., the running time reduced from $16557$s to $792$s.

Conclusions

To improve the scalability of existing matrix factorization algorithms while leveraging the ubiquity of parallel computing architectures, we introduced, evaluated, and analyzed DFC, a divide-and-conquer framework for noisy matrix factorization with missing entries or outliers. DFC is trivially parallelized and particularly well suited for distributed environments given its low communication footprint. Moreover, DFC provably maintains the estimation guarantees of its base algorithm, even in the presence of noise, and yields linear to super-linear speedups in practice.

A number of natural follow-up questions suggest themselves. First, can the sampling complexities and conclusions of our theoretical analyses be strengthened? For example, can the $(2+\epsilon)$ approximation guarantees of our master theorems be sharpened to $(1+\epsilon)$? Second, how does DFC perform when paired with alternative base algorithms, having no theoretical guarantees but displaying other practical benefits? These open questions are fertile ground for future work.

Appendix A Proof of Theorem 5: Subsampled Regression under Incoherence

We now give a proof of Thm. 5. While the results of this section are stated in terms of i.i.d. with-replacement sampling of columns and rows, a concise argument due to Hoeffding [16, Sec. 6] implies the same conclusions when columns and rows are sampled without replacement.

Let $\epsilon\in(0,1],$ and define ${\mathbf{V}}_{l}^{\top}={\mathbf{V}}_{L}^{\top}{\mathbf{S}}$ and $\Gamma=({\mathbf{V}}_{l}^{\top}{\mathbf{D}})^{+}-({\mathbf{V}}_{l}^{\top}{\mathbf{D}})^{\top}$. If $l\geq 48r\log(4r/(\beta\delta))/(\beta\epsilon^{2})$ for $\delta\in(0,1]$ then with probability at least $1-\delta$:

Proof By Lem. 20, for all $1\leq i\leq r$,

Proof The proof is identical to that of Thm. 5 of Drineas et al. once Lem. 21 is substituted for Lem. 1 of Drineas et al. . ∎

A typical application of Prop. 22 would involve performing a truncated SVD of ${\mathbf{M}}$ to obtain the statistical leverage scores, ${\|{({\mathbf{V}}_{L})_{(j)}}\|}^{2}$, used to compute the column sampling probabilities of Eq. (8). Here, we will take advantage of the slack term, $\beta$, allowed in the sampling probabilities of Eq. (8) to show that uniform column sampling gives rise to the same estimation guarantees for column projection approximations when ${\mathbf{L}}$ is sufficiently incoherent.

To prove Thm. 5, we first notice that $n\geq r\mu_{0}({\mathbf{V}}_{L})$ and hence

whenever $\beta\geq 1/\mu_{0}({\mathbf{V}}_{L})$. Thus, we may apply Prop. 22 with $\beta=1/\mu_{0}({\mathbf{V}}_{L})\in(0,1]$ and $p_{j}=1/n$ by noting that

for all $j$, by the definition of $\mu_{0}({\mathbf{V}}_{L})$. By our choice of probabilities, ${\mathbf{D}}={\mathbf{I}}\sqrt{n/l}$, and hence

with probability at least $1-\delta-0.2$, as desired.

Appendix B Proof of Lemma 4: Conservation of Incoherence

where the second and third equalities follow from ${\mathbf{U}}_{L}$ having orthonormal columns, the fourth and fifth result from ${\mathbf{\Sigma}}_{L}$ having full rank and ${\mathbf{V}}_{l}$ having full column rank, and the sixth follows from ${\mathbf{V}}_{l}^{\top}$ having full row rank.

where the final equality follows from ${\mathbf{V}}_{l}^{\top}{\mathbf{e}}_{i,l}={\mathbf{V}}_{L}^{\top}{\mathbf{e}}_{i,n}$ for all $1\leq i\leq l$.

Now, defining ${\mathbf{Q}}={\mathbf{V}}_{l}^{\top}{\mathbf{V}}_{l}$ we have

by Hölder’s inequality for Schatten $p$-norms. Since ${\mathbf{V}}_{L}^{\top}{\mathbf{e}}_{i,n}{\mathbf{e}}_{i,n}^{\top}{\mathbf{V}}_{L}$ has rank one, we can explicitly compute its trace norm as ${\|{{\mathbf{V}}_{L}^{\top}{\mathbf{e}}_{i,n}}\|}^{2}={\|{{\mathbf{P}}_{V_{L}}{\mathbf{e}}_{i,n}}\|}^{2}$. Hence,

by the definition of $\mu_{0}$-coherence. The proof of Lemma 21 established that the smallest singular value of $\frac{n}{l}{\mathbf{Q}}={\mathbf{V}}_{l}^{\top}{\mathbf{D}}{\mathbf{D}}{\mathbf{V}}_{l}$ is lower bounded by $1-\frac{\epsilon}{2}$ and hence ${\|{{\mathbf{Q}}^{-1}}\|}_{2}\leq\frac{n}{l(1-\epsilon/2)}$. Thus, we conclude that $\mu_{0}({\mathbf{V}}_{L_{C}})\leq\mu_{0}({\mathbf{V}}_{L})/(1-\epsilon/2)$.

To prove claim $iv$ under Lemma 21, we note that

by Hölder’s inequality for Schatten $p$-norms, the definition of $\mu_{0}$-coherence, and claims $ii$ and $iii$.

Appendix C Proof of Corollary 6: Column Projection under Incoherence

Fix $c=48000/\log(1/0.45)$, and notice that for $n>1$,

Hence $l\geq 3200r\mu_{0}({\mathbf{V}}_{L})\log(16n)(\log(\delta)/\log(0.45))/\epsilon^{2}.$

Now partition the columns of ${\mathbf{C}}$ into $b=\log(\delta)/\log(0.45)$ submatrices, ${\mathbf{C}}=[{\mathbf{C}}_{1},\cdots,{\mathbf{C}}_{b}]$, each with $a=l/b$ columns,For simplicity, we assume that $b$ divides $l$ evenly. and let $[{\mathbf{L}}_{C_{1}},\cdots,{\mathbf{L}}_{C_{b}}]$ be the corresponding partition of ${\mathbf{L}}_{C}$. Since

we may apply Prop. 22 independently for each $i$ to yield

fails to hold, then, for each $i$, Eq. (9) also fails to hold. The desired conclusion therefore must hold with probability at least $1-0.45^{b}=1-\delta$.

Appendix D Proof of Corollary 7: Generalized Nyström Method under Incoherence

With $c=48000/\log(1/0.45)$ as in Cor. 6, we notice that for $m>1$,

for all $m>1$ and $\delta^{\prime}\leq 0.8$. Hence, we may apply Thm. 5 and Cor. 6 in turn to obtain

with probability at least $(1-\delta)(1-\delta^{\prime}-0.2)$ by independence.

Appendix E Proof of Corollary 8: Noiseless Generalized Nyström Method under Incoherence

Next we can apply the first result of Lem. 21 to lower bound the RHSs of Eq. (10) and Eq. (11) by selecting $\epsilon=1$, ${\mathbf{S}}$ such that its diagonal entries equal 1, and $\beta=\frac{1}{\mu_{0}({\mathbf{V}}_{L})}$ for the RHS of Eq. (10) and $\beta=\frac{1}{\mu_{0}({\mathbf{U}}_{L})}$ for the RHS of Eq. (11). In particular, given the lower bounds on $d$ and $l$ in the statement of the corollary, the RHSs are each lower bounded by $\sqrt{1-\delta}$. Furthermore, by the independence of row and column sampling and Eq. (10) and Eq. (11), we see that

which proves the statement of the theorem.

Appendix F Proof of Corollary 9: Random Projection

Our proof rests upon the following random projection guarantee of Halko et al. :

with probability at least $1-5t^{-p}-2e^{-u^{2}/2}$.

Fix $(u,t)=(\sqrt{2\log(7/\delta)},e)$, and note that

since $p\geq\log(7/\delta)$. Hence, Thm. 24 implies that

with probability at least $1-\delta$, where the second inequality follows from ${\|{{\mathbf{M}}-{\mathbf{M}}_{r}}\|}_{2}\leq{\|{{\mathbf{M}}-{\mathbf{M}}_{r}}\|}_{F}\leq{\|{{\mathbf{M}}-{\mathbf{L}}}\|}_{F}$, the third follows from $\sqrt{r+p}\sqrt{p}\leq(p+1)\sqrt{r}$ for all $r$ and $p$, and the final follows from our choice of $p\geq 242\ r\log(7/\delta)/\epsilon^{2}$.

Next, we note, as in the proof of Thm. 9.3 of Halko et al. , that

Combining Eq. (12) with the first statement of the corollary yields the second statement.

Appendix G Proof of Theorem 12: Coherence Master Theorem

by the triangle inequality, and hence it suffices to lower bound {\mathbf{P}}\mathopen{}\mathclose{{}\left({K\cap{\textstyle\bigcap}_{i}A({\mathbf{C}}_{0,i})}}\right). Our choice of $l$, with a factor of $\log(2/\delta)$, implies that each $A({\mathbf{C}}_{0,i})$ holds with probability at least $1-\delta/(2n)$ by Lem. 4, while $K$ holds with probability at least $1-\delta/2$ by Cor. 6. Hence, by the union bound,

An identical proof with Cor. 9 substituted for Cor. 6 yields the random projection result.

G.2 Proof of DFC-Nys Bound

when $K$ holds, by the triangle inequality. Our choices of $l$ and

imply that $A({\mathbf{C}})$ and $A({\mathbf{R}})$ hold with probability at least $1-\delta/(2n)$ and $1-\delta/(4n)$ respectively by Lem. 4, while $K$ holds with probability at least $(1-\delta/2)(1-\delta/4-0.2)$ by Cor. 7. Hence, by the union bound,

Appendix H Proof of Corollary 13: DFC-MC under Incoherence

We begin by proving the DFC-Proj bound. Let $G$ be the event that

$A({\mathbf{X}})$ be the event that a matrix ${\mathbf{X}}$ is $(\frac{r\mu^{2}}{1-\epsilon/2},r)$-coherent, and, for each $i\in\{1,\ldots,t\}$, $B_{i}$ be the event that ${\|{{\mathbf{C}}_{0,i}-\hat{\mathbf{C}}_{i}}\|}_{F}>c_{e}\sqrt{ml}\Delta$.

Hence the Coherence Master Theorem (Thm. 12) guarantees that, with probability at least $1-\bar{n}^{2-2\beta}$, $H$ holds and the event $A({\mathbf{C}}_{0,i})$ holds for each $i$. Since $G$ holds whenever $H$ holds and $B_{i}^{c}$ holds for each $i$, we have

To prove our desired claim, it therefore suffices to show

For each $i$, let $D_{i}$ be the event that $s_{i}<32\mu^{\prime}r(m+l)\beta^{\prime}\log^{2}(m+l)$, where $s_{i}$ is the number of revealed entries in ${\mathbf{C}}_{0,i}$,

By Thm. 10 and our choice of $\beta^{\prime}$,

Further, since the support of ${\mathbf{S}}_{0}$ is uniformly distributed and of cardinality $s$, the variable $s_{i}$ has a hypergeometric distribution with ${\mathbf{E}}(s_{i})=\frac{sl}{n}$ and hence satisfies Hoeffding’s inequality for the hypergeometric distribution [16, Sec. 6]:

Hence, {\mathbf{P}}\mathopen{}\mathclose{{}\left({B_{i}\mid A({\mathbf{C}}_{0,i})}}\right)\leq 4\log(\bar{n})\bar{n}^{2-2\beta}+\bar{n}^{-2\beta} for each $i$, and the DFC-Proj result follows.

Since, $p\geq 242\ r\log(14\bar{n}^{2\beta-2})/\epsilon^{2}$, the DFC-RP bound follows in an identical manner from the Coherence Master Theorem (Thm. 12).

H.2 Proof of DFC-Nys Bound

For DFC-Nys, let $B_{C}$ be the event that ${\|{{\mathbf{C}}_{0}-\hat{\mathbf{C}}}\|}_{F}>c_{e}\sqrt{ml}\Delta$ and $B_{R}$ be the event that ${\|{{\mathbf{R}}_{0}-\hat{\mathbf{R}}}\|}_{F}>c_{e}\sqrt{dn}\Delta$. The Coherence Master Theorem (Thm. 12) and our choice of

guarantee that, with probability at least $(1-\bar{n}^{2-2\beta})(1-\bar{n}^{2-2\beta}-0.2)\geq 1-2\bar{n}^{2-2\beta}-0.2$,

and both $A({\mathbf{C}})$ and $A({\mathbf{R}})$ hold. Moreover, since

reasoning identical to the DFC-Proj case yields {\mathbf{P}}\mathopen{}\mathclose{{}\left({B_{C}\mid A({\mathbf{C}})}}\right)\leq 4\log(\bar{n})\bar{n}^{2-2\beta}+\bar{n}^{-2\beta} and {\mathbf{P}}\mathopen{}\mathclose{{}\left({B_{R}\mid A({\mathbf{R}})}}\right)\leq 4\log(\bar{n})\bar{n}^{2-2\beta}+\bar{n}^{-2\beta}, and the DFC-Nys bound follows as above.

Appendix I Proof of Corollary 14: DFC-RMF under Incoherence

We begin by proving the DFC-Proj bound. Let $G$ be the event that

for the constant $c_{e}^{\prime}$ defined in Thm. 11, $H$ be the event that

$A({\mathbf{X}})$ be the event that a matrix ${\mathbf{X}}$ is $(\frac{r\mu^{2}}{1-\epsilon/2},r)$-coherent, and, for each $i\in\{1,\ldots,t\}$, $B_{i}$ be the event that ${\|{{\mathbf{C}}_{0,i}-\hat{\mathbf{C}}_{i}}\|}_{F}>c_{e}^{\prime}\sqrt{ml}\Delta$.

We may take $\rho_{r}\leq 1$, and hence, by assumption,

Hence the Coherence Master Theorem (Thm. 12) guarantees that, with probability at least $1-\bar{n}^{-\beta}$, $H$ holds and the event $A({\mathbf{C}}_{0,i})$ holds for each $i$. Since $G$ holds whenever $H$ holds and $B_{i}^{c}$ holds for each $i$, we have

To prove our desired claim, it therefore suffices to show

Define \bar{m}\triangleq\max\mathopen{}\mathclose{{}\left({m,l}}\right) and $\beta^{\prime\prime}\triangleq\beta\log(\bar{n})/\log(\bar{m})\leq\beta^{\prime}$. By assumption,

Hence, by Thm. 11 and the definitions of $\beta^{\prime}$ and $\beta^{\prime\prime}$,

where $s_{i}$ is the number of corrupted entries in ${\mathbf{C}}_{0,i}$. Further, since the support of ${\mathbf{S}}_{0}$ is uniformly distributed and of cardinality $s$, the variable $s_{i}$ has a hypergeometric distribution with ${\mathbf{E}}(s_{i})=\frac{sl}{n}$ and hence satisfies Bernstein’s inequality for the hypergeometric [16, Sec. 6]:

for all $0\leq t\leq 3l/n$ and $\sigma^{2}\triangleq\frac{l}{n}(1-\frac{l}{n})\leq\frac{l}{n}$. It therefore follows that

by our assumptions on $s$ and $l$ and the fact that \frac{l}{n}\mathopen{}\mathclose{{}\left(\frac{(1-\rho_{s}\beta^{\prime})}{(1-\rho_{s}\beta_{s})}-1}\right)\leq 3l/n whenever $4\beta_{s}-3/\rho_{s}\leq\beta^{\prime}$. Hence, {\mathbf{P}}\mathopen{}\mathclose{{}\left({B_{i}\mid A({\mathbf{C}}_{0,i})}}\right)\leq(c_{p}+1)\bar{n}^{-\beta} for each $i$, and the DFC-Proj result follows.

Since, $p\geq 242\ r\log(14\bar{n}^{\beta})/\epsilon^{2}$, the DFC-RP bound follows in an identical manner from the Coherence Master Theorem (Thm. 12).

I.2 Proof of DFC-Nys Bound

For DFC-Nys, let $B_{C}$ be the event that ${\|{{\mathbf{C}}_{0}-\hat{\mathbf{C}}}\|}_{F}>c_{e}^{\prime}\sqrt{ml}\Delta$ and $B_{R}$ be the event that ${\|{{\mathbf{R}}_{0}-\hat{\mathbf{R}}}\|}_{F}>c_{e}^{\prime}\sqrt{dn}\Delta$. The Coherence Master Theorem (Thm. 12) and our choice of $d\geq cl\mu_{0}(\hat{\mathbf{C}})\beta\log^{2}(4\bar{n})/\epsilon^{2}$ guarantee that, with probability at least $(1-\bar{n}^{-\beta})(1-\bar{n}^{-\beta}-0.2)\geq 1-2\bar{n}^{-\beta}-0.2$,

and both $A({\mathbf{C}})$ and $A({\mathbf{R}})$ hold. Moreover, since

reasoning identical to the DFC-Proj case yields {\mathbf{P}}\mathopen{}\mathclose{{}\left({B_{C}\mid A({\mathbf{C}})}}\right)\leq(c_{p}+1)\bar{n}^{-\beta} and {\mathbf{P}}\mathopen{}\mathclose{{}\left({B_{R}\mid A({\mathbf{R}})}}\right)\leq(c_{p}+1)\bar{n}^{-\beta}, and the DFC-Nys bound follows as above.

Appendix J Proof of Theorem 10: Noisy MC under Incoherence

In the spirit of Candès and Plan , our proof will extend the noiseless analysis of Recht to the noisy matrix completion setting. As suggested in Gross and Nesme , we will obtain strengthened results, even in the noiseless case, by reasoning directly about the without-replacement sampling model, rather than appealing to a with-replacement surrogate, as done in Recht .

We begin with a theorem providing sufficient conditions for our desired estimation guarantee.

Under the assumptions of Thm. 10, suppose that

Proof We may write $\hat{{\mathbf{L}}}$ as ${\mathbf{L}}_{0}+{\mathbf{G}}+{\mathbf{H}}$, where ${\mathcal{P}}_{{\Omega}}({\mathbf{G}})={\mathbf{G}}$ and ${\mathcal{P}}_{{\Omega}}({\mathbf{H}})=\bf{0}$. Then, under Eq. (13),

Furthermore, by the triangle inequality, $0={\|{{\mathcal{P}}_{{\Omega}}({\mathbf{H}})}\|}_{F}\geq{\|{{\mathcal{P}}_{{\Omega}}{\mathcal{P}}_{T}({\mathbf{H}})}\|}_{F}-{\|{{\mathcal{P}}_{{\Omega}}{\mathcal{P}}_{T^{\bot}}({\mathbf{H}})}\|}_{F}.$ Hence, we have

where the penultimate inequality follows as ${\mathcal{P}}_{{\Omega}}$ is an orthogonal projection operator.

Next we select ${\mathbf{U}}_{\bot}$ and ${\mathbf{V}}_{\bot}$ such that $[{\mathbf{U}}_{L_{0}},{\mathbf{U}}_{\bot}]$ and $[{\mathbf{V}}_{L_{0}},{\mathbf{V}}_{\bot}]$ are orthonormal and \mathopen{}\mathclose{{}\left\langle{\mathbf{U}}_{\bot}{\mathbf{V}}_{\bot}^{\top},{\mathcal{P}}_{T^{\bot}}({\mathbf{H}})}\right\rangle={\|{{\mathcal{P}}_{T^{\bot}}({\mathbf{H}})}\|}_{*} and note that

where the first inequality follows from the variational representation of the trace norm, {\|{{\mathbf{A}}}\|}_{*}=\sup_{{\|{{\mathbf{B}}}\|}_{2}\leq 1}\mathopen{}\mathclose{{}\left\langle{\mathbf{A}},{\mathbf{B}}}\right\rangle, the first equality follows from the fact that \mathopen{}\mathclose{{}\left\langle{\mathbf{Y}},{\mathbf{H}}}\right\rangle=0 for ${\mathbf{Y}}={\mathcal{P}}_{{\Omega}}({\mathbf{Y}})$, the second inequality follows from Hölder’s inequality for Schatten $p$-norms, the third inequality follows from Eq. (14), and the final inequality follows from Eq. (15).

Since ${\mathbf{L}}_{0}$ is feasible for Eq. (4), ${\|{{\mathbf{L}}_{0}}\|}_{*}\geq{\|{\hat{{\mathbf{L}}}}\|}_{*}$, and, by the triangle inequality, ${\|{\hat{{\mathbf{L}}}}\|}_{*}\geq{\|{{\mathbf{L}}_{0}+{\mathbf{H}}}\|}_{*}-{\|{{\mathbf{G}}}\|}_{*}$. Since ${\|{{\mathbf{G}}}\|}_{*}\leq\sqrt{m}{\|{{\mathbf{G}}}\|}_{F}$ and ${\|{{\mathbf{G}}}\|}_{F}\leq{\|{{\mathcal{P}}_{{\Omega}}(\hat{{\mathbf{L}}}-{\mathbf{M}})}\|}_{F}+{\|{{\mathcal{P}}_{{\Omega}}({\mathbf{M}}-{\mathbf{L}}_{0})}\|}_{F}\leq 2\Delta$, we conclude that

for some constant $c_{e}^{\prime\prime}$, by our assumption on $s$. ∎

To show that the sufficient conditions of Thm. 25 hold with high probability, we will require four lemmas. The first establishes that the operator ${\mathcal{P}}_{T}{\mathcal{P}}_{{\Omega}}{\mathcal{P}}_{T}$ is nearly an isometry on $T$ when sufficiently many entries are sampled.

with probability at least $1-2n^{2-2\beta}$ provided that $s>\frac{16}{3}\mu r(n+m)\beta\log(n)$.

The second states that a sparsely but uniformly observed matrix is close to a multiple of the original matrix under the spectral norm.

with probability at least $1-(m+n)^{1-\beta}$ provided that $s>6\beta m\log(m+n).$

The third asserts that the matrix infinity norm of a matrix in $T$ does not increase under the operator ${\mathcal{P}}_{T}{\mathcal{P}}_{{\Omega}}$.

Let ${\mathbf{Z}}\in T$ be a fixed matrix. Then for all $\beta>2$

with probability at least $1-2n^{2-\beta}$ provided that $s>\frac{8}{3}\beta\mu r(m+n)\log(n).$

These three lemmas were proved in Recht [38, Thm. 6, Thm. 7, and Lem. 8] under the assumption that entry locations in ${\Omega}$ were sampled with replacement. They admit identical proofs under the sampling without replacement model by noting that the referenced Noncommutative Bernstein Inequality [38, Thm. 4] also holds under sampling without replacement, as shown in Gross and Nesme .

It suffices to establish Eq. (14) under this batch replacement scheme, as shown in the next lemma.

and hence ${\|{{\mathbf{W}}_{k}}\|}_{F}\leq 2^{-k}{\|{{\mathbf{W}}_{0}}\|}_{F}=2^{-k}\sqrt{r}.$ Since $p\geq\frac{3}{4}\log(n/2)\geq\frac{1}{2}\log_{2}(n/2)\geq\log_{2}\sqrt{32rmn/s}$, ${\mathbf{Y}}\triangleq{\mathbf{Y}}_{p}$ satisfies the first condition of Eq. (14).

The second condition of Eq. (14) follows from the assumptions

for all $k$, since Eq. (17) implies ${\|{{\mathbf{W}}_{k}}\|}_{\infty}\leq 2^{-k}{\|{{\mathbf{U}}_{L_{0}}{\mathbf{V}}_{L_{0}}^{\top}}\|}_{\infty}$, and thus

by our assumption on $q$. The first line applies the triangle inequality; the second holds since ${\mathbf{W}}_{j-1}\in T$ for each $j$; the third follows because ${\mathcal{P}}_{T^{\bot}}$ is an orthogonal projection; and the final line exploits $(\mu,r)$-coherence.

We conclude by bounding the probability of any assumed event failing. Lem. 26 implies that Eq. (13) fails to hold with probability at most $2n^{2-2\beta}$. For each $k$, Eq. (16) fails to hold with probability at most $2n^{2-2\beta}$ by Lem. 26, Eq. (17) fails to hold with probability at most $2n^{2-2\beta}$ by Lem. 28, and Eq. (18) fails to hold with probability at most $(m+n)^{1-2\beta}$ by Lem. 27. Hence, by the union bound, the conclusion of Thm. 25 holds with probability at least

Appendix K Proof of Lemma 15: Conservation of Non-Spikiness

where $\{j_{1},\dots,j_{l}\}$ are random indices drawn uniformly and without replacement from $\{1,\dots,n\}$. Hence, we have that

Since ${\|{{\mathbf{L}}^{(j)}}\|}^{4}\leq m^{2}{\|{{\mathbf{L}}}\|}_{\infty}^{4}$ for all $j\in\{1,\dots,n\}$, Hoeffding’s inequality for sampling without replacement [16, Sec. 6] implies

with probability at least $1-\delta$. Since, ${\|{{\mathbf{L}}_{C}}\|}_{\infty}\leq{\|{{\mathbf{L}}}\|}_{\infty}$ almost surely, we have that

with probability at least $1-\delta$ as desired.

Appendix L Proof of Theorem 16: Column Projection under Non-Spikiness

We now give a proof of Thm. 16. While the results of this section are stated in terms of i.i.d. with-replacement sampling of columns and rows, a simple argument due to [16, Sec. 6] implies the same conclusions when columns and rows are sampled without replacement.

Our proof builds upon two key results from the randomized matrix approximation literature. The first relates column projection to randomized matrix multiplication:

The second allows us to bound ${\|{{\mathbf{A}}{\mathbf{A}}^{\top}-(n/l){\mathbf{G}}{\mathbf{G}}^{\top}}\|}_{F}$ in probability when entries are bounded:

Under our assumption, ${\|{{\mathbf{M}}}\|}_{\infty}$ is bounded by $\alpha/\sqrt{mn}$. Hence, Lem. 31 with ${\mathbf{A}}={\mathbf{M}}$ and ${\mathbf{B}}={\mathbf{M}}^{\top}$ guarantees

with probability at least $1-\delta$, by our choice of $l$.

with probability at least $1-\delta$, as desired.

Appendix M Proof of Theorem 18: Spikiness Master Theorem

Define $A({\mathbf{X}})$ as the event that a matrix ${\mathbf{X}}$ is $(\alpha\sqrt{1+\epsilon/(4\sqrt{r})})$-spiky. Since $\sqrt{1+\epsilon/(4\sqrt{r})}\leq\sqrt{1.25}$ for all $\epsilon\in(0,1]$ and $r\geq 1$, ${\mathbf{X}}$ is $(\sqrt{1.25}\alpha)$-spiky whenever $A({\mathbf{X}})$ holds.

by the triangle inequality, and hence it suffices to lower bound {\mathbf{P}}\mathopen{}\mathclose{{}\left({H\cap{\textstyle\bigcap}_{i}A({\mathbf{C}}_{0,i})}}\right).

so that each event $A({\mathbf{C}}_{0,i})$ also holds with probability at least $1-\delta/(2n)$.

Appendix N Proof of Corollary 19: Noisy MC under Non-Spikiness

We begin by proving the DFC-Proj bound. Let $G$ be the event that

$A({\mathbf{X}})$ be the event that a matrix ${\mathbf{X}}$ is $(\sqrt{1.25}\alpha)$-spiky, and, for each $i\in\{1,\ldots,t\}$, $B_{i}$ be the event that {\|{{\mathbf{C}}_{0,i}-\hat{\mathbf{C}}_{i}}\|}_{F}^{2}>(l/n)c_{1}\max\mathopen{}\mathclose{{}\left({({l/}{n})\nu^{2},1}}\right)/\beta.

By definition, ${\|{\hat{\mathbf{C}}_{i}}\|}_{\infty}\leq\sqrt{1.25}\alpha/\sqrt{ml}$ for all $i$. Furthermore, we have assumed that

Hence the Spikiness Master Theorem (Thm. 18) guarantees that, with probability at least 1-\operatorname{exp}\mathopen{}\mathclose{{}\left(-c_{3}\log(m+l)}\right), $H$ holds and the event $A({\mathbf{C}}_{0,i})$ holds for each $i$. Since $G$ holds whenever $H$ holds and $B_{i}^{c}$ holds for each $i$, we have

To prove our desired claim, it therefore suffices to show

Further, since the support of ${\mathbf{S}}_{0}$ is uniformly distributed and of cardinality $s$, the variable $s_{i}$ has a hypergeometric distribution with ${\mathbf{E}}(s_{i})=\frac{sl}{n}$ and hence satisfies Hoeffding’s inequality for the hypergeometric distribution [16, Sec. 6]:

Combined with Eq. (N.1), this yields {\mathbf{P}}\mathopen{}\mathclose{{}\left({B_{i}\mid A({\mathbf{C}}_{0,i})}}\right)\leq(c_{2}+1)\operatorname{exp}\mathopen{}\mathclose{{}\left(-c_{3}\log(m+l)}\right) for each $i$, and the DFC-Proj result follows.

N.2 Proof of DFC-RP Bound

Since $p\geq 242\ r\log(14(m+l)^{c_{3}})/\epsilon^{2}$, the DFC-RP bound follows in an identical manner from the Spikiness Master Theorem (Thm. 18).