PaperlayerView exact revision on arXiv

Source-linked AI summary

Matrix Completion and Low-Rank SVD via Fast Alternating Least Squares

Trevor Hastie, Rahul Mazumder, Jason Lee, Reza Zadeh

arXiv:1410.2596v1stat.MEstat.ML

TL;DR

Matrix completion requires scalable methods for incomplete, potentially very large matrices, while nuclear-norm regularization and maximum-margin factorization use different algorithms. The paper combines their ideas in softImpute-ALS, which uses alternating ridge regressions and sparse-plus-low-rank representations. It establishes convergence properties and reports superior performance on simulated and real examples, including Netflix data, while noting that fixed points need not minimize the convex problem when the rank is too small.

  • Problem

    Large matrix completion is computationally challenging, and existing nuclear-norm and maximum-margin approaches use different procedures with distinct efficiency limitations.

  • Method

    The paper combines softImpute and MMMF through alternating ridge regressions on a filled matrix, exploiting sparse-plus-low-rank structure and warm starts.

  • Results

    The algorithm converges to a first-order stationary point at rate O(1/K), produces decreasing objective values for the convex problem, and demonstrates superior performance on simulated and real examples.

  • Takeaways & Limitations

    softImpute-ALS provides an efficient matrix-completion and factorization approach for very large problems when the solution rank is manageably low.

  • Takeaways & Limitations

    A fixed point of softImpute-ALS need not minimize the convex problem when r is smaller than the rank of its optimal solution.

Abstract

from arXiv · show

The matrix-completion problem has attracted a lot of attention, largely as a result of the celebrated Netflix competition. Two popular approaches for solving the problem are nuclear-norm-regularized matrix approximation (Candes and Tao, 2009, Mazumder, Hastie and Tibshirani, 2010), and maximum-margin matrix factorization (Srebro, Rennie and Jaakkola, 2005). These two procedures are in some cases solving equivalent problems, but with quite different algorithms. In this article we bring the two approaches together, leading to an efficient algorithm for large matrix factorization and completion that outperforms both of these. We develop a software package "softImpute" in R for implementing our approaches, and a distributed version for very large matrices using the "Spark" cluster programming environment.

1 Introduction

The paper combines nuclear-norm matrix completion and maximum-margin matrix factorization into softImpute-ALS, an efficient approach for large matrix completion. It uses filled-in matrices, alternating ridge regressions, and sparse-plus-low-rank structure to improve computational efficiency while retaining convergence to the nuclear-norm solution for sufficiently large rank.

  • Existing approaches: Nuclear-norm completion iterates between imputing missing entries and computing a soft-thresholded SVD.Soft-thresholding replaces each singular value d_i with (d_i − λ)+, producing low-rank solutions when λ is large.
  • Computational advantages: The method exploits sparse-plus-low-rank structure, making storage and left or right matrix multiplications efficient.This structure is central to scaling the algorithm to large incomplete matrices.
  • Existing approaches: Maximum-margin matrix factorization uses alternating least squares, with each factor update decomposing into separate ridge regressions.Missing entries are omitted from the corresponding regressions, so different rows or columns require different regression problems.
  • Proposed approach: The proposed softImpute-ALS algorithm combines ideas from softImpute and MMMF while replacing the filled matrix at each step using the latest factor estimate.The authors report that the hybrid algorithm tends to be faster than either approach alone.
  • Proposed approach: A complete filled matrix lets the ridge regression operator be computed once and applied simultaneously to all columns or rows.This reduces the computation of an update over ALS by a factor of r.
  • Results and scope: The paper establishes convergence to the solution of the nuclear-norm problem for sufficiently large rank and demonstrates performance on simulated, real, and Netflix examples.It also presents software implementations, including an R package and a distributed approach for very large matrices.

2 Rank-restricted Soft SVD

This section develops a rank-restricted SVD algorithm for a fully observed matrix, characterizes its solution through the SVD of X, and connects it to matrix factorization. The alternating ridge-regression procedure maintains an SVD-form representation, iterates until convergence, and can produce a reduced-rank SVD efficiently, including for sparse or distributed matrices.

  • Problem characterization: Theorems establish the solution for a fully observed matrix and relate the rank-restricted problem to the corresponding matrix factorization problem.The first theorem gives an SVD-based solution, while the second connects it with factorized variables.
  • Problem characterization: The rank-restricted optimization problem is nonconvex in Z when r < min(m, n), but its solution can be characterized using the SVD of X.The unrestricted analogue is convex in Z, whereas the rank-restricted case is handled through singular-value characterization.
  • Problem characterization: The solution can have rank less than r, depending on the shrinkage parameter and the singular values.The section explicitly notes that neither theorem requires the resulting solution to attain rank r.
  • Algorithm: Algorithm 2.1 alternates multiresponse ridge regressions for B and A, with each update implemented as matrix multiplication followed by coordinate-wise shrinkage.After each regression, the factors are recomputed in orthogonal SVD form before the next update.
  • Algorithm: The algorithm repeats the alternating updates until AB^T converges, and step (7) applies a final SVD and singular-value shrinkage to clean up the rank.The convergence change can be evaluated through a relative Frobenius-norm calculation that is not expensive to compute.
  • Computational properties: A reduced-rank SVD of X is available from the solution, with rank determined by λ; sparse multiplication and distributed matrix chunking support large-scale computation.The singular values require correction by adding λ, and empirical evidence indicates faster computation than without shrinkage, with greater accuracy emphasis on larger singular values.

3 softImpute-ALS Algorithm

softImpute-ALS adapts alternating ridge regression to incomplete matrices by updating a sparse-plus-low-rank filled matrix from the current factors. It maintains an SVD-form factorization, repeats efficient updates to convergence, and finishes with soft-thresholding.

  • Algorithm definition: softImpute-ALS is a rank-restricted efficient maximum-margin matrix factorization algorithm for matrices with observed entries indexed by Ω.The factor matrices have at most rank r.
  • Imputation and representation: At each iteration, the algorithm updates the filled matrix using the current factor estimates and represents it in sparse-plus-low-rank form.This avoids explicitly forming the dense filled matrix while preserving efficient multiplication.
  • Initialization: The algorithm initializes orthogonal factors with identity scaling and can alternatively start from a prior solution as a warm start.Warm starts are explicitly supported by the initialization procedure.
  • Alternating updates: Given one factor, the algorithm solves for the other by alternating ridge regression and updates its orthogonal factors and diagonal scaling.The same procedure is applied symmetrically with X^T when updating A from B.
  • Finalization: After repeating the alternating updates until convergence, the algorithm computes an SVD and applies coordinate-wise soft-thresholding to the singular values.The final step reveals exact zeros and cleans up the rank.
  • Practical use and guarantees: The output can be passed to softImpute as a warm start, which typically makes the R implementation exit almost immediately.The paper discusses the lack of optimality guarantees for fixed points in terms of the convex criterion.

4 Theoretical Results

Theoretical analysis shows that softImpute-ALS decreases its objectives, converges to stationary points at rate O(1/K), and can certify when a stationary point solves the convex problem. These guarantees have scope limits: fixed points need not be convex optima when the factor rank is too small, and factor iterates are nonunique or potentially unbounded under reparameterization.

  • Algorithmic interpretation: softImpute-ALS is an EM- or MM-style procedure that alternates factor minimization of surrogate upper bounds.Each imputation step constructs an upper bound for the training-error term before minimizing with respect to one factor.
  • Descent property: Theorem 3 establishes that softImpute-ALS monotonically decreases the factorized objective F(Ak, Bk) at every iteration.The decrease follows from successive updates of A and B.
  • Convergence rates: O(1/K) is the convergence rate for reaching a first-order stationary point, requiring at most K = O(1/ϵ) iterations to obtain ηk* ≤ ϵ.The rate holds for any λ ≥ 0, while the constants and observed speed depend on λ.
  • Asymptotic convergence: Every limit point of the iterates is a stationary point of problem (6) when λ > 0.A fixed point is characterized by zero update progress, and the algorithm’s limit points satisfy first-order stationarity.
  • Limitations and representation: The algorithm’s nuclear-norm objective values decrease, but factor representations can remain nonunique and updates can become unbounded without changing the objective.The reparameterization in (48) decreases the ridge regularization term, while orthogonal invariance prevents uniqueness of the factors.
  • Relation to the convex problem: A fixed point need not minimize the convex nuclear-norm problem (1) when the factor rank r is smaller than the optimal solution’s rank.The analysis gives necessary and sufficient conditions, checkable through a structured low-rank SVD, for a stationary point to solve problem (1).
  • Computational complexity: One softImpute-ALS iteration costs O(2r|Ω| + mr^2 + 3nr^2 + r^3), while one ALS iteration costs O(2|Ω|r^2 + mr^3 + nr^3).Thus ALS uses r times more flops per iteration, despite potentially decreasing its criterion more per iteration.

5 Experiments

The experiments compare ALS, softImpute-ALS, and softImpute on simulated, MovieLens, and Netflix data. softImpute-ALS consistently offers the strongest computational performance, while shrinkage improves Netflix test error and reduces overfitting.

  • 5.1 Timing experiments: The simulations use Gaussian factor models with true ranks 50, 100, and 100, while 70–90% of entries are missing.MovieLens 100K contains 100K ratings and is 93% missing.
  • 5.1 Timing experiments: softImpute-ALS wins handily over ALS and softImpute across four timing experiments.The datasets include three simulations of increasing size and MovieLens 100K.
  • 5.1 Timing experiments: Although softImpute-ALS uses more iterations than ALS, its iterations are cheaper by a factor O(r).ALS can make bigger gains per iteration, but each ALS iteration costs more.
  • 5.1 Timing experiments: softImpute-ALS outperforms softImpute because softImpute spends substantial time on its early SVD before warm starts become effective.Warm starts accelerate later softImpute iterations, but it does not catch up in the reported experiments.
  • 5.2 Netflix Competition Data: On Netflix, shrinkage yields a best test-set RMSE of 0.943, a 1% improvement over the Cinematch score.The reported improvement is somewhat below the prize-winning improvement of 10%.
  • 5.2 Netflix Competition Data: On Netflix and MovieLens 10M, softImpute-ALS reaches a solution close to the minimum in about 1/4 the time required by ALS.The comparison uses early stopping because highly accurate solutions were unnecessary for these applications.

6 R Package softImpute

The softImpute R package implements both softImpute algorithms for large matrices and supports sparse representations, preprocessing, prediction, and low-rank SVD computation.

  • 6 R Package softImpute: The R package implements softImpute and softImpute-ALS for fitting matrix-completion models.It is available on CRAN.
  • 6 R Package softImpute: Sparse-matrix formats allow the package to accommodate large matrices when the number of missing entries is correspondingly large.The package also provides centering, scaling, and prediction functions.
  • 6 R Package softImpute: The svd.als function computes a low-rank SVD of a large sparse matrix with row and/or column centering.The package documentation provides additional implementation details.

7 Distributed Implementation

The distributed softimpute-ALS implementation partitions sparse matrix data across machines while replicating the current model, enabling computation proportional to nonzeros and available CPU cores when memory permits.

  • Distributed architecture: The Spark implementation splits the input matrix and its transpose row-by-row across machines while keeping the current model in memory on each machine.The model must fit in memory.
  • Performance evaluation: Runtime is proportional to the number of nonzeros divided by the number of CPU cores, subject to the model fitting in memory.Experiments used an Amazon EC2 cluster with 10 slaves and one master, each machine having 16 CPU cores and 30 GB of RAM.
  • Distributed architecture: Each iteration broadcasts one model copy per machine, allowing cores to share local model memory while processing separate input partitions.This reduces RAM usage particularly on machines with many cores.
  • Implementation: The multByXstar method performs Algorithm 4.1 line 3 by multiplying X* by C, while multByXstarTranspose performs line 5.Afterward, machines send their computed portions of A.
  • Performance evaluation: The experiments report distributed softimpute-ALS running times for matrices up to 10 times larger than the Netflix prize matrix.The Netflix matrix contains 17,770 rows, 480,189 columns, and 100,480,507 nonzeros.

8 Centering and Scaling

The paper introduces a missing-data method for simultaneously centering and scaling rows and columns, learning transformation parameters iteratively for use in matrix completion.

  • Goal and model: The centering-and-scaling procedure targets observed matrix entries whose rows and columns should simultaneously have mean zero and variance one.The method is designed for very large, sparse matrices.
  • Parameterization: The representation is non-unique unless location and scale constraints are imposed, such as zero-mean effects and normalized overall scale.The paper notes that this refinement is suppressed because it is not an issue for the presented use.
  • Goal and model: Unlike a similar complete-data algorithm, this method handles missing data and learns centering/scaling parameters so completed standardized predictions can be transformed back.The latter feature matters when reversing transformations after estimating missing entries.
  • Sparse implementation: For complete sparse matrices, centering can be represented in sparse-plus-low-rank form, preserving efficient left and right multiplication.Missing entries are represented as NAs in the full matrix.
  • Estimation algorithm: The algorithm iteratively solves four estimating-equation systems until row and column mean and variance conditions are simultaneously satisfied.The equations include row and column centering and variance conditions.
  • Convergence: Experiments suggest that the residual diagnostic R converges to zero very quickly, perhaps at a linear rate, although general convergence guarantees are absent.Convergence is guaranteed in certain restricted cases, including column-only transformations and centering-only settings.

9 Discussion

The discussion presents softImpute-ALS as a scalable matrix-completion algorithm that combines filled-in matrix updates with alternating least squares, trading per-step strength for speed.

  • Discussion: The proposed method targets very large matrix-completion problems when the solution rank is manageably low.Its design addresses computational weaknesses identified in ALS and softImpute.
  • Discussion: softImpute-ALS replaces separate missingness-dependent ALS regressions with one simultaneous regression on a complete filled-in matrix.The individual steps may be weaker than ALS steps, but the speed advantage more than compensates.
  • Discussion: softImpute-ALS fills in the matrix during each alternating step while computing the SVD, avoiding repeated SVDs on far-from-optimal early imputations.The paper states that it reaches the solution sought by softImpute with far fewer iterations.
  • Discussion: The distributed implementation can scale softImpute to large problems given sufficiently large computing infrastructure.The paper describes this as an extremely efficient distributed implementation.
  • Convergence analysis: The convergence proof uses ridge-regression inequalities and alternating updates to establish progress toward fixed-point behavior.The proof separately analyzes A and B updates before combining them.
  • Convergence analysis: If the update measure Δ is zero, the objective values remain unchanged, and the nesting property implies that the current iterate is a fixed point.The argument applies analogously to both factor updates.

A.0.3 Proof of Theorem 4

The proof establishes convergence of the objective sequence and uses summed descent inequalities to derive a finite-time convergence rate for the algorithm.

  • Proof of Theorem 4: The theorem proof is completed after combining the summed inequality with the monotone objective behavior and the derived convergence bound.The displayed proof concludes immediately afterward.
  • Proof of Theorem 4: The objective sequence F(Ak, Bk) is decreasing and bounded below, so it converges to a finite limit f∞.The proof also establishes ηk → 0.
  • Proof of Theorem 4: The resulting convergence rate is O(1/K), where K denotes the number of algorithm iterations.The rate is stated for convergence to a first-order stationary point in the paper’s theorem summary.

A.0.4 Proof of Corollary 1

The proof derives convergence-rate bounds under the stated assumptions and compares proximity measures, including the special case λ = 0.

  • The analysis derives a bound using the alternative proximity measure on the step-sizes.
  • The convergence-rate discussion contrasts the main bounds with the case λ = 0.
  • The quantities k A_k bound local Lipschitz constants for the gradients of Q_A(Z|A_k, B_k) and Q_B(Z|A_{k+1}, B_k).
  • These bounds lead to convergence-rate bounds on the partial gradients of F(A, B).

A.0.5 Proof of Theorem 5

The proof shows that, when λ > 0, the iterate sequence is bounded and its limit points are fixed points and first-order stationary points of problem (6). It further establishes uniqueness of the corresponding limit point across subsequences.

  • When λ > 0, the sequence of iterates is bounded and therefore has a limit point.
  • Every limit point is a fixed point of Algorithm 4.1 and a first-order stationary point of problem (6).
  • Although the full sequence need not have a unique limit point, each limit point of B_k has the same corresponding limit point of A_k.
  • The subsequence argument establishes uniqueness of the associated A_k limit point when B_k converges, with the analogous conclusion for the other sequence.
  • For fully observed, very sparse matrices, the algorithm can represent the data as a sparse-plus-low-rank object instead of explicitly applying centering operations.
Loading 1410.2596v1…