Citation and evidence

Alternating least squares

19 min full readUpdated 17 references

This article's verification

Report a problem with this article

Edit article
More

Use this article

Raw MarkdownExplore connections

Improve this page

Revision historyDiscuss this article

Topics

AlgorithmsMachine LearningTraining & Optimization

Cite this article

Alternating least squares (ALS) is an iterative method for fitting a product of two or more factor matrices to data by holding all but one factor fixed, solving the resulting linear least squares problem for the free factor exactly, and cycling through the factors until the fit stops improving. It is widely used in recommender systems to train matrix factorization models for collaborative filtering: the user-item matrix is approximated as the product of a user factor matrix and an item factor matrix, and ALS alternates between solving for every user vector and solving for every item vector.[1][16] The same alternating scheme is the main algorithm for computing the CANDECOMP/PARAFAC tensor decomposition, a version of it underlies several nonnegative matrix factorization algorithms, and it has been analyzed as a method for low-rank matrix completion.[4][6][7]

Fitting two factor matrices at once is a non-convex problem, but once one of them is fixed the objective becomes quadratic in the other and can be minimized in closed form.[1] Because each user's (or item's) subproblem is independent of every other user's, the updates parallelize naturally, an advantage that Koren, Bell and Volinsky singled out; ALS is the collaborative filtering algorithm in Apache Spark's MLlib library.[1][9] Two papers from 2008 shaped its use in recommendation: ALS with weighted-λ-regularization (ALS-WR), developed at HP Labs for the Netflix Prize, and the implicit-feedback formulation of Hu, Koren and Volinsky, described in detail in the article on weighted alternating least squares.[2][3]

History

Alternating least squares was in use in psychometrics and multiway data analysis long before the Netflix Prize. In their 2009 survey of tensor decompositions, Tamara Kolda and Brett Bader describe ALS as the main algorithm for the CANDECOMP/PARAFAC (CP) decomposition and trace it to the original 1970 papers by J. Douglas Carroll and Jih-Jie Chang and by Richard Harshman.[4] The psychometrics literature of the 1970s used the name explicitly: Jan de Leeuw, Forrest Young and Yoshio Takane published "An Alternating Least Squares Method with Optimal Scaling Features" for additive models of qualitative data in Psychometrika in 1976.[5] In 1980 Kroonenberg and De Leeuw developed an ALS algorithm called TUCKALS3 for the Tucker decomposition of three-way arrays.[4] For nonnegative matrix factorization, Paatero and Tapper's original 1994 algorithm for positive matrix factorization was a constrained ALS method.[6]

During the Netflix Prize, ALS was one of three classes of methods (with restricted Boltzmann machines and nearest-neighbor models) whose variants were blended into the 107-model solution with which Robert Bell, Yehuda Koren and Chris Volinsky's BellKor team won the 2007 Progress Prize, according to Zhou and colleagues.[2] In 2008 Yunhong Zhou, Dennis Wilkinson, Robert Schreiber and Rong Pan of HP Labs published ALS-WR, a parallel ALS algorithm they designed for the competition.[2] The same year Yifan Hu, Yehuda Koren and Chris Volinsky adapted ALS to implicit feedback such as television viewing data, where the objective covers every user-item pair.[3] A 2009 IEEE Computer article by Koren, Robert Bell and Volinsky on matrix factorization for recommenders presented ALS and stochastic gradient descent as the two approaches to learning such models.[1]

YearWorkContribution
1970Carroll and Chang; HarshmanALS for the CP (CANDECOMP/PARAFAC) tensor decomposition[4]
1976de Leeuw, Young and TakaneALS method with optimal scaling for qualitative data[5]
1980Kroonenberg and De LeeuwTUCKALS3, an ALS algorithm for the Tucker decomposition[4]
1994Paatero and TapperConstrained ALS for positive (nonnegative) matrix factorization[6]
2008Zhou, Wilkinson, Schreiber and PanALS-WR, parallel ALS for the Netflix Prize[2]
2008Hu, Koren and VolinskyALS for implicit feedback with confidence weights[3]
2008Kim and ParkAlternating nonnegativity-constrained least squares (ANLS) for NMF[6]
2013Jain, Netrapalli and SanghaviRecovery guarantees for alternating minimization in matrix completion[7]
2015Hastie, Mazumder, Lee and ZadehsoftImpute-ALS for matrix completion and low-rank SVD[8]
2021Rendle, Krichene, Zhang and KorenRe-tuned implicit ALS on item recommendation benchmarks; iALS++ solver[16][17]

Expanded article table

The matrix factorization problem

In the recommender setting, a partially observed ratings matrix $R$ has an entry $r_{ij}$ for each rating that user $i$ gave item $j$, and $\Omega$ is the set of observed pairs. Each user gets a latent vector $u_i \in \mathbb{R}^k$ and each item a latent vector $v_j \in \mathbb{R}^k$, and a rating is predicted by their dot product $\hat r_{ij} = u_i^\top v_j$.[2] The vectors are found by minimizing the regularized squared error over the observed entries:

min⁡U,V∑(i,j)∈Ω(rij−ui⊤vj)2+λ(∑i∥ui∥2+∑j∥vj∥2)\min_{U,V} \sum_{(i,j)\in\Omega} \left(r_{ij} - u_i^\top v_j\right)^2 + \lambda\left(\sum_i \lVert u_i\rVert^2 + \sum_j \lVert v_j\rVert^2\right)

Here $\lambda$ controls the strength of the regularization penalty, which keeps the many free parameters from overfitting a sparse matrix.[1][2] Zhou and colleagues noted that the singular value decomposition, which gives the best low-rank approximation of a fully observed matrix, cannot be computed directly when most entries are missing; in the Netflix data about 1.1% of the possible ratings were known.[2] Because both $U$ and $V$ are unknown, the objective is not convex.[1]

The algorithm

Alternating updates

ALS removes the non-convexity one block at a time. With every item vector fixed, the objective splits into one independent regularized least squares problem per user; with every user vector fixed, it splits into one per item. Each step solves its subproblems exactly, so the objective cannot increase from one step to the next.[1] Zhou and colleagues gave the procedure as four steps:[2]

  1. Initialize the item matrix, using each item's average rating for the first feature and small random numbers for the rest.
  2. Fix the item matrix and solve for the user matrix by minimizing the sum of squared errors.
  3. Fix the user matrix and solve for the item matrix in the same way.
  4. Repeat steps 2 and 3 until a stopping criterion is met.

Setting the gradient with respect to one user vector to zero gives its normal equations. If $V_{\Omega_i}$ holds the vectors of the $n_i$ items that user $i$ rated and $r_i$ holds those ratings, then

ui=(VΩi⊤VΩi+λniI)−1VΩi⊤ri,u_i = \left(V_{\Omega_i}^\top V_{\Omega_i} + \lambda n_i I\right)^{-1} V_{\Omega_i}^\top r_i,

where $I$ is the $k \times k$ identity matrix; the item update has the same form with the roles of users and items swapped.[2] Every update therefore needs only the factor vectors of the entries that user or item touches and the solution of a small $k \times k$ linear system. Zhou and colleagues stopped iterating once a full round of updates improved the error on Netflix's probe set by less than 0.0001.[2]

Weighted-λ-regularization (ALS-WR)

The $n_i$ in the equation above comes from ALS-WR. Instead of one penalty for every vector, Zhou and colleagues multiplied the penalty on each user vector by the number of ratings that user gave and the penalty on each item vector by the number of ratings that item received:[2]

f(U,V)=∑(i,j)∈Ω(rij−ui⊤vj)2+λ(∑ini∥ui∥2+∑jmj∥vj∥2)f(U,V) = \sum_{(i,j)\in\Omega} \left(r_{ij} - u_i^\top v_j\right)^2 + \lambda\left(\sum_i n_{i}\lVert u_i\rVert^2 + \sum_j m_{j}\lVert v_j\rVert^2\right)

with $n_i$ the number of ratings by user $i$ and $m_j$ the number of ratings of item $j$. They reported that, after trying several regularization matrices, this weighting worked best, and that in their experiments it did not overfit as they increased the number of features or iterations; they left an explanation of that behaviour as an open question.[2] Apache Spark's ALS applies the same scaling and says it makes the regularization parameter less dependent on dataset size, so a value tuned on a sample can be reused on the full data.[9]

Convergence

Each ALS step minimizes the objective exactly over one block of variables, so the objective decreases monotonically until it converges.[1][3] A decreasing objective does not by itself mean that the factors reach a global minimum. In the two-block case, Kim and Park point to a result of Grippo and Sciandrone: any limit point of the iterates is a stationary point as long as each subproblem is solved to optimality, even when the subproblem solutions are not unique.[6] For CP tensor decomposition, Kolda and Bader note that ALS can take many iterations, is guaranteed neither to reach a global minimum nor even a stationary point, and can produce a final answer that depends heavily on the starting point.[4]

ALS for explicit ratings: the Netflix Prize

ALS-WR was built for the Netflix Prize data: more than 100 million ratings from over 480,000 users on nearly 18,000 movies, with the goal of improving on the root mean squared error of 0.9514 scored by Netflix's own CineMatch system.[2] The HP Labs team ran parallel Matlab on a 30-processor Linux cluster. With 100 latent features, one full update of both factor matrices took 2.5 hours on a single processor and about 5 minutes on 30 processors, and broadcasting the factor matrices took less than 5% of the running time.[2]

Configuration (Zhou et al.)Test RMSE
ALS with a single (unweighted) λ0.9184
ALS-WR, 50 features0.9114
ALS-WR, 150 features0.9066
ALS-WR, 500 features, global bias shift0.9000
ALS-WR, 1,000 features0.8985
Linear blend of ALS-WR, kNN and RBM0.8952

Expanded article table

The 1,000-feature model's 0.8985 was a 5.56% improvement over CineMatch, and blending it with a k-nearest neighbors model and a restricted Boltzmann machine gave 5.91%.[2] The authors observed that the same objective had been optimized with gradient descent by Salakhutdinov and colleagues, and that using ALS let them fit far more latent features (1,000 instead of 40).[2] In a later theoretical paper, Jain, Netrapalli and Sanghavi described alternating minimization as a major component of the winning entry in the Netflix Prize.[7]

ALS for implicit feedback

Many recommender systems have only implicit feedback, such as purchase history, watching habits or browsing activity, rather than explicit ratings.[3] Hu, Koren and Volinsky split each raw observation $r_{ui}$ into a binary preference $p_{ui}$ (1 if the user consumed the item at all) and a confidence $c_{ui} = 1 + \alpha r_{ui}$, and minimized a confidence-weighted error over every user-item pair:[3]

min⁡x,y∑u,icui(pui−xu⊤yi)2+λ(∑u∥xu∥2+∑i∥yi∥2)\min_{x,y} \sum_{u,i} c_{ui}\left(p_{ui} - x_u^\top y_i\right)^2 + \lambda\left(\sum_u \lVert x_u\rVert^2 + \sum_i \lVert y_i\rVert^2\right)

With $m \cdot n$ terms, which they noted can reach a few billion, the loss rules out methods such as stochastic gradient descent that loop over individual terms.[3] ALS still works because of an algebraic shortcut. The user update is $x_u = (Y^\top C^u Y + \lambda I)^{-1} Y^\top C^u p(u)$, and since $Y^\top C^u Y = Y^\top Y + Y^\top (C^u - I) Y$, the shared $Y^\top Y$ can be computed once per sweep while the correction term involves only the $n_u$ items the user actually interacted with. One sweep over all users then costs $O(f^2 N + f^3 m)$, where $f$ is the number of latent factors and $N$ the number of non-zero observations, so the running time is linear in the size of the input.[3] The authors reported that $\alpha = 40$ produced good results in their experiments, gave typical values of $f$ between 20 and 200, and found that about 10 sweeps were typical.[3]

This method has several names. Rendle and colleagues call it iALS and note that WRMF, WMF and WALS refer to the same algorithm, since the original paper did not name it.[16] Spark's ALS switches to this variant when implicitPrefs is set.[9] Its loss function, confidence schemes and later refinements are covered in weighted alternating least squares.

ALS compared with stochastic gradient descent

Koren, Bell and Volinsky described two ways to minimize the factorization objective. Stochastic gradient descent, popularized for the Netflix Prize by Simon Funk, loops over the observed ratings and nudges the two vectors involved in each one. They wrote that SGD is in general easier and faster than ALS, but that ALS is favorable in at least two cases: when the system can use parallelization, because every item vector is computed independently of the other item vectors and every user vector independently of the other user vectors, and when the data are implicit, because looping over every training case is impractical when the training set cannot be treated as sparse.[1]

AspectALSSGD
UpdateExact least squares solve for one factor matrix with the other fixed[1]Gradient step after each training rating[1]
Assessment by Koren, Bell and VolinskyFavorable for parallel systems and implicit data[1]Generally easier and faster[1]
Implicit feedback over all user-item pairsTractable with the Gram-matrix shortcut[3]Prevented by the number of terms[3]

Expanded article table

Practitioners also mix the two. Engineers at Facebook reported that their matrix factorization framework could run several iterations of SGD followed by a single ALS iteration, which improved offline metrics on some datasets.[12]

Scaling and implementations

Distributed ALS

The independence of the per-row solves makes ALS easy to distribute. Zhou and colleagues kept two distributed copies of the ratings matrix, one partitioned by users and one by items; each worker solved for its own block of vectors, and the results were then gathered so that every worker held a full copy of the opposite factor matrix for the next step.[2]

Apache Spark's MLlib uses ALS as its collaborative filtering algorithm. Its user guide lists the main parameters as the number of blocks that users and items are partitioned into, the rank, the maximum number of iterations, the regularization parameter, implicitPrefs, alpha and nonnegative; the rank and the iteration limit default to 10.[9] The source code solves each least squares subproblem with a Cholesky solver, or with a nonnegative least squares solver when nonnegativity is requested. It shuffles the ratings once before iterating and precomputes which users need which item factors (and the reverse), so that each factor vector is sent to a given worker at most once per iteration.[10] For users or items absent from the training data the model predicts NaN by default, and a coldStartStrategy of "drop" removes those rows, which the documentation recommends for cross-validation.[9] In July 2014 Databricks reported running 10 iterations of MLlib's ALS on 50 nodes over 3.5 billion ratings (100 copies of an Amazon reviews dataset) in 40 minutes with an optimization for MLlib 1.1, down from 90 minutes in MLlib 1.0.[11]

Facebook described a different layout in 2015. Its average collaborative filtering dataset had 100 billion ratings, more than a billion users and millions of items, and the network traffic of sending feature vectors along every rating was the main bottleneck. Its implementation on Apache Giraph placed the workers in a circle and rotated the items around it, and on the Amazon-derived benchmark this rotational hybrid approach was about 10 times faster, measured in total CPU minutes, than the standard approach implemented in Spark MLlib, with the same quality of results. The team used regularization based on user and item degrees to deal with numerical problems on items with very many ratings, and also implemented the implicit-feedback ALS algorithm.[12]

Single-machine solvers

The Python library implicit provides multi-threaded ALS for implicit feedback, written in Cython with OpenMP and with custom CUDA kernels for GPU training; its ALS follows Hu, Koren and Volinsky together with "Applications of the Conjugate Gradient Method for Implicit Feedback Collaborative Filtering" by Gábor Takács, István Pilászy and Domonkos Tikk.[13][15] Instead of solving each user's $f \times f$ system exactly, an answer that the next ALS iteration overwrites anyway, the conjugate gradient variant takes a few steps toward the solution starting from the previous value. The library's author, Ben Frederickson, reported in 2016 that with three conjugate gradient steps per iteration his code ran 3 times as fast with 50 factors and 19 times as fast with 250 factors, and that after about 10 iterations the loss was basically identical to that of the Cholesky solver.[14]

The cost of the exact solve grows with the cube of the embedding dimension. Rendle, Krichene, Zhang and Koren noted that coordinate descent variants (iCD) lower that dependence to quadratic, but found them poorly suited to modern processors: they can be an order of magnitude slower than a careful iALS implementation at about 100 dimensions and only pull ahead at about 1,000.[17] Their iALS++ solver, which optimizes over subspaces of the embedding, was reported to be an order of magnitude faster than iCD at both small and large dimensions and to fit 1,000-dimensional embeddings on MovieLens 20M or the Million Song Dataset in a few minutes.[17]

Beyond recommender systems

Tensor decompositions

The CP decomposition writes a tensor as a sum of rank-one tensors, for a third-order tensor $\mathcal{X} \approx \sum_{r=1}^{R} a_r \circ b_r \circ c_r$, with the vectors collected into factor matrices $A$, $B$ and $C$. ALS fixes $B$ and $C$ to solve for $A$, then fixes $A$ and $C$ to solve for $B$, then solves for $C$, and repeats. Each subproblem is a linear least squares problem whose solution needs the pseudoinverse of only an $R \times R$ matrix.[4] Kolda and Bader call ALS the "workhorse" algorithm for CP. They also summarize a comparison by Tomasi and Bro in which derivative-based methods that optimize all factor matrices at once had generally better convergence properties than ALS but cost more in memory and time.[4] For the Tucker decomposition they describe a line of ALS algorithms running from TUCKALS3 to the higher-order orthogonal iteration (HOOI).[4]

Nonnegative matrix factorization

Nonnegative matrix factorization (NMF) looks for factors with no negative entries, and many NMF algorithms are two-block coordinate descent methods that alternate between the two factors. Kim and Park's NMF/ANLS solves each block as a nonnegativity-constrained least squares problem with a fast active set method, and they stress that solving each subproblem to optimality matters for convergence to a stationary point.[6]

Matrix completion

Low-rank matrix completion asks for a low-rank matrix that matches a sample of observed entries, the abstract form of the ratings problem. Jain, Netrapalli and Sanghavi gave one of the first theoretical analyses of alternating minimization for matrix completion and for matrix sensing. They showed that it succeeds under conditions similar to the now-standard ones under which earlier work had made these problems tractable, and that its guaranteed convergence to the true matrix is geometric, faster than existing results.[7] Hastie, Mazumder, Lee and Zadeh combined nuclear-norm-regularized approximation and maximum-margin matrix factorization into a fast ALS algorithm for matrix completion and low-rank SVD, released as the R package softImpute with a distributed version for Spark.[8]

Limitations and reception

Jain and colleagues note that the overall factorization problem is non-convex and that, before their work, alternating minimization had been used largely as a heuristic whose only guarantees were of convergence to local minima; for CP decomposition Kolda and Bader note that the final answer can depend heavily on the starting guess.[7][4] The exact solve in each update costs time cubic in the number of latent factors, and later work proposed conjugate gradient, coordinate descent and subspace solvers to reduce that cost.[3][14][17]

By the early 2020s implicit ALS was one of the most commonly used baselines in recommender system research, but several studies reported that it lagged newer methods such as autoencoders and item-based models on top-n recommendation. Rendle, Krichene, Zhang and Koren revisited four of those benchmarks and found that with careful manual tuning, rather than off-the-shelf automated hyperparameter search, iALS was highly competitive and outperformed every other method on at least half of the comparisons.[16] They attributed the earlier poor results to the difficulty of tuning baselines.[16]

Continue reading

More from See also

More to read

Topics:AlgorithmsMachine LearningTraining & Optimization

References

  1. ^1 ^2 ^3 ^4 ^5 ^6 ^7 ^8 ^9 ^10 ^11 ^12 ^13Yehuda Koren, Robert Bell, Chris Volinsky. "Matrix Factorization Techniques for Recommender Systems". Computer (IEEE Computer Society), vol. 42, no. 8, August 2009, pp. 30-37. doi.org/...MC.2009.263
  2. ^1 ^2 ^3 ^4 ^5 ^6 ^7 ^8 ^9 ^10 ^11 ^12 ^13 ^14 ^15 ^16 ^17Yunhong Zhou, Dennis Wilkinson, Robert Schreiber, Rong Pan. "Large-Scale Parallel Collaborative Filtering for the Netflix Prize". Algorithmic Aspects in Information and Management (AAIM 2008), Lecture Notes in Computer Science, Springer, 2008, pp. 337-348. doi.org/...978-3-540-68880-8_32
  3. ^1 ^2 ^3 ^4 ^5 ^6 ^7 ^8 ^9 ^10 ^11 ^12Yifan Hu, Yehuda Koren, Chris Volinsky. "Collaborative Filtering for Implicit Feedback Datasets". 2008 Eighth IEEE International Conference on Data Mining (ICDM), December 2008, pp. 263-272. doi.org/...ICDM.2008.22
  4. ^1 ^2 ^3 ^4 ^5 ^6 ^7 ^8 ^9 ^10Tamara G. Kolda, Brett W. Bader. "Tensor Decompositions and Applications". SIAM Review, vol. 51, no. 3, 2009, pp. 455-500. doi.org/...07070111X
  5. ^1 ^2Jan de Leeuw, Forrest W. Young, Yoshio Takane. "Additive Structure in Qualitative Data: An Alternating Least Squares Method with Optimal Scaling Features". Psychometrika, vol. 41, no. 4, December 1976, pp. 471-503. doi.org/...BF02296971
  6. ^1 ^2 ^3 ^4 ^5 ^6Hyunsoo Kim, Haesun Park. "Nonnegative Matrix Factorization Based on Alternating Nonnegativity Constrained Least Squares and Active Set Method". SIAM Journal on Matrix Analysis and Applications, vol. 30, no. 2, 2008, pp. 713-730. doi.org/...07069239X
  7. ^1 ^2 ^3 ^4 ^5Prateek Jain, Praneeth Netrapalli, Sujay Sanghavi. "Low-rank Matrix Completion using Alternating Minimization". Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC), 2013; arXiv:1212.0467, December 2012. arxiv.org/...1212.0467
  8. ^1 ^2Trevor Hastie, Rahul Mazumder, Jason D. Lee, Reza Zadeh. "Matrix Completion and Low-Rank SVD via Fast Alternating Least Squares". Journal of Machine Learning Research, vol. 16, 2015, pp. 3367-3402. jmlr.org/...hastie15a
  9. ^1 ^2 ^3 ^4 ^5Apache Spark. "Collaborative Filtering". Spark MLlib documentation, accessed November 2026. spark.apache.org/...ml-collaborative-filtering
  10. ^Apache Spark. "ALS.scala" (org.apache.spark.ml.recommendation). Apache Spark source code on GitHub, accessed November 2026. github.com/...ALS.scala
  11. ^Burak Yavuz, Reynold Xin. "Scalable Collaborative Filtering with Apache Spark MLlib". Databricks blog, 2014-07-23. databricks.com/...ative-filtering-with-spark-mllib
  12. ^1 ^2Aleksandar Ilic, Maja Kabiljo. "Recommending items to more than a billion people". Engineering at Meta, 2015-06-02. engineering.fb.com/...o-more-than-a-billion-people
  13. ^Ben Frederickson. "Implicit: Fast Python Collaborative Filtering for Implicit Datasets". GitHub repository README, accessed November 2026. github.com/...implicit
  14. ^1 ^2Ben Frederickson. "Faster Implicit Matrix Factorization". benfrederickson.com, 2016-12-12. benfrederickson.com/...plicit-matrix-factorization
  15. ^Gábor Takács, István Pilászy, Domonkos Tikk. "Applications of the conjugate gradient method for implicit feedback collaborative filtering". Proceedings of the Fifth ACM Conference on Recommender Systems (RecSys 2011), pp. 297-300. doi.org/...2043932.2043987
  16. ^1 ^2 ^3 ^4 ^5Steffen Rendle, Walid Krichene, Li Zhang, Yehuda Koren. "Revisiting the Performance of iALS on Item Recommendation Benchmarks". arXiv:2110.14037, October 2021; Proceedings of the 16th ACM Conference on Recommender Systems (RecSys 2022). arxiv.org/...2110.14037
  17. ^1 ^2 ^3 ^4Steffen Rendle, Walid Krichene, Li Zhang, Yehuda Koren. "iALS++: Speeding up Matrix Factorization with Subspace Optimization". arXiv:2110.14044, October 2021. arxiv.org/...2110.14044

Improve this article

Add missing citations, update stale details, or write a clearer explanation. Anyone can edit: changes go live when you publish, and every edit is checked by an editor.

1 revision · v1 · 3,701 words · full history

Fact-checks are independent of edits: a reviewer re-verifies the article against its sources and stamps the date. How we verify

Research and drafting on this wiki are AI-assisted, under named human editorial standards. How AI is used here

Reviewer note: Independent fact-check before publication on November 18, 2026: 74 claims checked against 17 cited and independent sources; 0 material and 5 minor corrections applied before publication.

Cite this page: AI Wiki. "Alternating least squares." aiwiki.ai, updated 18 Nov 2026, fact-checked 18 Nov 2026. CC BY 4.0. https://aiwiki.ai/wiki/alternating_least_squares

Edit article