Alternating Least Squares (ALS)

ALS is a block coordinate descent method. It optimizes a non-convex objective by iteratively fixing one block of variables (e.g., the user factor matrix) and solving for the other block (e.g., the item factor matrix) in a convex least squares problem. This alternation between two (or more) sets of variables transforms a complex joint optimization into a sequence of simpler, tractable subproblems.

When one set of factors is held fixed, the optimization problem for the other set becomes a linear least squares regression. This subproblem is convex and has a closed-form solution via the normal equations: (X^T X + λI) * Factor = X^T R, where X is the fixed factor matrix, R is the observed data, and λ is a regularization term. This guarantees a unique, optimal solution for each half-step.

A key efficiency of ALS, particularly for collaborative filtering, is that the least squares problems for different users or items become independent when one factor matrix is fixed. For example, when solving for user factors, the updates for each user depend only on their rated items and the fixed item factors. This allows for embarrassingly parallel computation across users or items, making ALS highly scalable in distributed systems like Apache Spark.

ALS almost always incorporates L2 regularization (Tikhonov regularization) in its least squares solves. This is critical to:

• Prevent overfitting in sparse data scenarios (e.g., user-item matrices with few observations).
• Ensure the matrix X^T X is invertible (by adding λI), guaranteeing numerical stability.
• Control the magnitude of the learned latent factors, improving generalization.

ALS is naturally suited for matrix completion tasks with missing entries, such as recommendation systems. The objective function typically sums only over observed entries, ignoring missing values. During each alternating step, the algorithm solves for factors using only the available data, effectively learning latent representations from incomplete information.

While foundational for matrix factorization, the ALS framework extends to tensor factorization models like CPD and Tucker decomposition. The principle remains the same: alternate between fixing all but one factor matrix (or core tensor), solving a linear least squares problem for the unfixed mode. This makes ALS a versatile workhorse for multi-way data analysis.

ALS performs non-linear dimensionality reduction by learning a compressed, latent representation of high-dimensional data. This is applied beyond recommendations to general feature extraction tasks.

• Interpretable Latent Spaces: The learned factor matrices can represent abstract features (e.g., 'comedy factor', 'action factor' for movies) that describe the original data.
• Data Imputation: Can fill in missing values in an incomplete data matrix as a byproduct of the factorization process.
• Use Case: Reducing a massive user-by-product purchase matrix into dense user preference vectors and product attribute vectors for downstream clustering or classification.

ALS generalizes to tensor factorization (e.g., via CP or Tucker decomposition) for analyzing multi-dimensional arrays. This is crucial for data with more than two modes (e.g., user × item × time × location).

• Higher-Order ALS (HOOI): An ALS variant used for Tucker decomposition, alternating between optimizing the core tensor and each factor matrix.
• Applications:
  • Temporal Recommendations: Incorporating time to model evolving user preferences.
  • Sensor Data Analysis: Decomposing data from a network of sensors across time and location.
  • Neuroimaging: Factorizing brain activity data across space, time, and experimental conditions.

ALS is employed in matrix completion problems, such as reconstructing a full matrix from a small subset of observed entries, under a low-rank assumption. It is also a core solver in Robust PCA variants.

• Mechanism: Minimizes a loss (often Frobenius norm) between observed entries and the low-rank model's predictions, often with regularization (L2 norm) to prevent overfitting.
• Robust PCA Extension: Can be adapted to decompose a matrix into Low-Rank + Sparse components, separating the principal structure from outliers or corruptions.
• Real-World Example: Filling in missing values in a customer-product sales matrix after a server outage, or removing shadows and specularities from a series of video frames.

ALS underpins several classic embedding techniques that learn dense vector representations for discrete entities like words or nodes in a graph.

• GloVe (Global Vectors for Word Representation): The GloVe model uses a weighted least squares objective to factorize the log-co-occurrence matrix of words, which is optimized via ALS-like methods.
• Graph Factorization: For an adjacency matrix or a matrix of node proximities (e.g., Personalized PageRank), ALS can factorize it to produce low-dimensional node embeddings.
• Advantage: Provides a deterministic optimization path compared to stochastic gradient descent (SGD) used in methods like Word2Vec, often leading to more stable embeddings.

The ALS algorithm is chosen for its computational efficiency and scalability in specific problem settings, which defines its core use cases.

• Closed-Form Solutions: Each sub-problem (solving for one factor matrix while holding others fixed) often reduces to a ridge regression problem with a closed-form solution, enabling fast iterations.
• Avoids Gradient Descent Pitfalls: Unlike SGD, ALS does not require tuning a learning rate and is less sensitive to initialization for well-conditioned problems.
• Memory Efficiency: For sparse input matrices, the normal equations can be constructed very efficiently, requiring computation only on observed data.
• Limitation: Can be slower than SGD on very dense problems or when the factor matrices are extremely wide.

Singular Value Decomposition (SVD) is the foundational matrix factorization that decomposes any matrix A into three constituent matrices: A = U Σ V^T. Here, U and V are orthogonal matrices containing the left and right singular vectors, and Σ is a diagonal matrix of singular values. This decomposition is exact and reveals the intrinsic geometric structure of the matrix. It is the theoretical bedrock for low-rank approximation, where Truncated SVD retains only the top-k singular values to create a compressed, optimal rank-k approximation as per the Eckart–Young Theorem.

Matrix Factorization is the general family of techniques that express a data matrix as a product of two or more lower-dimensional factor matrices. The goal is to discover latent features that explain the observed data.

• Core Concept: Given a matrix R (e.g., user-item ratings), find matrices P and Q such that R ≈ P Q^T.
• ALS Application: ALS is a specific, highly effective optimization method for solving this non-convex problem by alternately fixing P or Q and solving a convex least-squares subproblem.
• Use Cases: Beyond recommendation systems, it is used in topic modeling, word embeddings, and collaborative filtering.

Non-Negative Matrix Factorization (NMF) is a constrained variant of matrix factorization where the factor matrices are required to have only non-negative entries. This constraint leads to parts-based representations, as additive combinations of basis vectors, which are often more interpretable (e.g., facial features from image data, topics from text). While ALS can be adapted for NMF by incorporating non-negativity constraints in the least-squares subproblems (often via projected gradient steps), specialized multiplicative update rules are also common. NMF highlights how factorization objectives are shaped by domain-specific constraints.

Tensor Factorization generalizes matrix factorization to multi-way arrays (tensors), essential for modeling higher-order interactions (e.g., user-item-context).

• Key Formats: Includes Canonical Polyadic Decomposition (CPD) and Tucker Decomposition.
• ALS Role: ALS is the workhorse algorithm for fitting these models. The algorithm alternates by fixing all but one factor matrix (or the core tensor in Tucker) and solving a linear least-squares problem to update the free factor. This makes ALS scalable for high-dimensional, sparse tensor data common in real-world applications.

Regularized Least Squares is the core subproblem solved at each step of the ALS algorithm. When ALS fixes one set of factors, updating the other reduces to a linear regression problem of the form: min ||Xw - y||² + λ||w||², where λ is a regularization parameter (e.g., for L2 regularization).

• Purpose: Regularization (ridge regression) prevents overfitting, especially critical in collaborative filtering where data is extremely sparse.
• Efficiency: Because the design matrix X has a specific structure (e.g., block-diagonal when factors are fixed), this system can be solved very efficiently, often in parallel, which is key to ALS's performance.

Stochastic Gradient Descent (SGD) is the primary alternative optimization algorithm to ALS for matrix and tensor factorization. It operates by iteratively updating parameters using the gradient computed from a single data point or a small mini-batch.

• ALS vs. SGD: ALS uses full-data steps per alternation, which can be faster on smaller, dense problems or when parallelization is straightforward. SGD is often more efficient for extremely large-scale, sparse datasets (e.g., web-scale recommendations) due to its low per-iteration cost.
• Hybrid Approaches: Modern large-scale systems may use SGD for initial rapid convergence and switch to ALS for fine-tuning, or use distributed variants of both.