This work introduces Divide-Factor-Combine (DFC), a parallel divide-andconquer framework for noisy matrix factorization. DFC divides a large-scale matrix factorization task into smaller subproblems, solves each subproblem in parallel using an arbitrary base matrix factorization algorithm, and combines the subproblem solutions using techniques from randomized matrix approximation. Our experiments with collaborative filtering, video background modeling, and simulated data demonstrate the near-linear to super-linear speed-ups attainable with this approach. Moreover, our analysis shows that DFC enjoys high-probability recovery guarantees comparable to those of its base algorithm. Notation For M ∈ R m×n , we define M (i) as the ith row vector and M ij as the ijth entry. If rank(M) = r, we write the compact singular value decomposition (SVD) of M as where Σ M is diagonal and contains the r non-zero singular values of M, and U M ∈ R m×r and V M ∈ R n×r are the corresponding left and right singular vectors of M. We define M + = V M Σ −1 M U ⊤ M as the Moore-Penrose pseudoinverse of M and P M = MM + as the orthogonal projection onto the column space of M. We let · 2 , · F , and · * respectively denote the spectral, Frobenius, and nuclear norms of a matrix and let · represent the ℓ 2 norm of a vector. In this section, we present our divide-and-conquer framework for scalable noisy matrix factorization. We begin by defining the problem setting of interest. In the setting of noisy matrix factorization, we observe a subset of the entries of a matrix M = L 0 + S 0 + Z 0 ∈ R m×n , where L 0 has rank r ≪ m, n, S 0 represents a sparse matrix of outliers of arbitrary magnitude, and Z 0 is a dense noise matrix. We let Ω represent the locations of the observed entries and P Ω be the orthogonal projection onto the space of m × n matrices with support Ω, so that Our goal is to recover the low-rank matrix L 0 from P Ω (M) with error proportional to the noise level ∆ Z 0 F . We will focus on two specific instances of this general problem: • Noisy Matrix Completion (MC): s |Ω| entries of M are revealed uniformly without replacement, along with their locations. There are no outliers, so that S 0 is identically zero. • Noisy Robust Matrix Factorization (RMF): S 0 is identically zero save for s outlier entries of arbitrary magnitude with unknown locations distributed uniformly without replacement. All entries of M are observed, so that P Ω (M) = M. Algorithms 1 and 2 summarize two canonical examples of the general Divide-Factor-Combine framework that we refer to as DFC-PROJ and DFC-NYS. Each algorithm has three simple steps: (D step) Divide input matrix into submatrices: DFC-PROJ randomly partitions P Ω (M) into t lcolumn submatrices, {P Ω (C 1 ), . . . , P Ω (C t )} 1 , while DFC-NYS selects an l-column submatrix, P Ω (C), and a d-row submatrix, P Ω (R), uniformly at random. (F step) Factor each submatrix in parallel using any base MF algorithm: DFC-PROJ performs t parallel submatrix factorizations, while DFC-NYS performs two such parallel factorizations. Standard base MF algorithms output the low-rank approximations {Ĉ 1 , . . . ,Ĉ t } for DFC-PROJ andĈ, andR for DFC-NYS. All matrices are retained in factored form. DFC-PROJ generates a final low-rank estimateL proj by projecting [Ĉ 1 , . . . ,Ĉ t ] onto the column space ofĈ 1 , while DFC-NYS forms the lowrank estimateL nys fromĈ andR via the generalized Nyström method. These matrix approximation techniques are described in more detail in Section 2.3. Our divide-and-conquer algorithms rely on two methods that generate randomized low-rank approximations to an arbitrary matrix M from submatrices of M.
Mackey et al. REF introduces a Divide-Factor-Combine (DFC) framework, in which the expensive task of matrix factorization is randomly divided into smaller subproblems.
Divide-and-Conquer Matrix Factorization
ArXiv
ArXiv
Computer Science