Source-linked AI summary
A Flexible and Efficient Algorithmic Framework for Constrained Matrix and Tensor Factorization
Kejun Huang, Nicholas D. Sidiropoulos, Athanasios P. Liavas
TL;DR
Constrained matrix and tensor factorization needs a unified way to handle varied factor constraints and loss functions. The paper proposes AO-ADMM, combining alternating optimization with ADMM subproblem updates, and reports broad applicability, stationary-point convergence, and ALS-like efficiency in case studies. Its general-loss formulation can require recomputing an additional large matrix product, and the completion experiments are intended to explore formulations rather than identify the best recommender method.
Problem
Existing constrained factorization methods usually handle only a few specialized constraints, while varied loss functions and tensor models require a unified framework.
Method
AO-ADMM combines alternating optimization for factor updates with ADMM subproblem solvers to accommodate diverse constraints, regularizers, and loss functions.
Results
AO-ADMM is reported to outperform prior algorithms, converge to a stationary point, and achieve ALS-like per-iteration complexity across studied factorization cases.
Takeaways & Limitations
Case studies and real-data experiments support AO-ADMM as a broadly applicable framework for non-negative factorization, constrained completion, and dictionary learning.
Takeaways & Limitations
For general losses, auxiliary variables require recomputing a large matrix product in every ADMM iteration, and completion experiments were not designed to find the best recommender method.
Abstract
from arXiv · showhide
We propose a general algorithmic framework for constrained matrix and tensor factorization, which is widely used in signal processing and machine learning. The new framework is a hybrid between alternating optimization (AO) and the alternating direction method of multipliers (ADMM): each matrix factor is updated in turn, using ADMM, hence the name AO-ADMM. This combination can naturally accommodate a great variety of constraints on the factor matrices, and almost all possible loss measures for the fitting. Computation caching and warm start strategies are used to ensure that each update is evaluated efficiently, while the outer AO framework exploits recent developments in block coordinate descent (BCD)-type methods which help ensure that every limit point is a stationary point, as well as faster and more robust convergence in practice. Three special cases are studied in detail: non-negative matrix/tensor factorization, constrained matrix/tensor completion, and dictionary learning. Extensive simulations and experiments with real data are used to showcase the effectiveness and broad applicability of the proposed framework.
1 Introduction
Constrained matrix and tensor factorization lacks a unified framework for combining diverse factor constraints and loss functions. The paper proposes AO-ADMM, which combines alternating optimization with ADMM to provide broad modeling flexibility while retaining efficient factor updates.
- Constrained factorization is widely used, but existing methods typically support only one or a few specialized constraints and require redesign when new constraints are added.
- Non-negativity, sparsity, simplex constraints, missing-value losses, and robust l1 losses motivate a framework that handles both factor constraints and non-least-squares objectives.
- AO-ADMM updates each factor through ADMM within an outer alternating-optimization framework, accommodating many constraints and loss functions.
- AO-ADMM is reported to outperform prior algorithms for constrained matrix and tensor factorization under nonparametric latent-factor constraints.
- AO-ADMM converges to a stationary point of the original NP-hard problem while supporting broad constraint and regularization choices at essentially ALS-like complexity.
- The framework targets matrix and tensor models including PARAFAC or canonical polyadic decomposition, with factor matrices associated with tensor modes.
2 Alternating Optimization Framework: Preliminaries
The factorization problem is formulated as a regularized, generally non-convex optimization problem and solved by cyclic factor updates. The framework combines AO or BCD-style outer updates with efficient least-squares and ADMM-compatible subproblem structure.
- The general objective combines a loss function l(·) with factor regularizers r_d(H_d), which can encode hard constraints through +∞ values.
- The multilinear factorization problem is generally non-convex and often NP-hard, so AO cyclically updates one factor at a time; ALS is its unconstrained least-squares special case.
- For fixed factors, each least-squares subproblem is convex, and shared Gram matrices enable Cholesky reuse across multiple solves, reducing computational cost.
- Tensor ALS updates exploit structured Gram matrices and efficient computations that avoid explicitly forming the Khatri-Rao product or mode-d matricization.
- Classical BCD decreases the objective monotonically and, under convex unique subproblems and bounded iterates, has stationary limit points.
- Proximal regularization can make convex BCD subproblems strongly convex and uniquely solvable, supporting convergence to a stationary point for bounded sequences.
3 Solving the Sub-problems Using ADMM
ADMM solves each constrained factor-update subproblem, extending alternating least squares to general constraints and loss functions. Caching, proximal operators, and warm starts make these updates practical, while general losses introduce additional computation and may sacrifice linear convergence.
- ADMM subproblems: The factor-update subproblem is formed from Y and W, with auxiliary variables enforcing H = ˜H^T for ADMM splitting.The same formulation applies to matrix factors and tensor matricizations, without necessarily forming the matricizations or Khatri-Rao products explicitly.
- ADMM subproblems: ADMM solves each alternating factor-update subproblem, allowing constraints to be handled through proximity or projection operators.For many common constraints, these updates are element-wise and cost O(kn) flops.
- Efficient implementation: Caching W^T Y and the Cholesky factorization of W^T W + ρI reduces each ˜H update to forward and backward substitutions costing O(k^2n).The cached quantities are reused throughout the ADMM iterations.
- Constraint handling: Non-negativity uses projection by zeroing negative entries, while Lasso uses element-wise soft thresholding and can extend to structured sparsity.Simplex constraints use a randomized linear-time projection, and smoothness regularization exploits a fixed-bandwidth system with O(kn) computation.
- Efficiency and convergence: With good initialization, regularized least-squares updates usually require 5–10 ADMM iterations initially and soon reduce to one iteration, giving ALS-order complexity.The pre-calculation costs O(k^2m + k^3) flops for the Cholesky decomposition and O(mnk) flops to form F.
- General loss: General losses can be handled by auxiliary variables, but may lose ADMM’s linear convergence and require recomputing W^T(˜Y + V) at every inner iteration.The authors moderate this cost by controlling the maximum number of ADMM iterations; least-squares updates avoid the repeated large multiplication.
4 Summary of the Proposed Algorithm
The proposed algorithm uses ADMM as the inner solver within cyclic alternating optimization. Each factor update is warm-started from its previous factor and dual variable, with separate procedures for least-squares and general-loss objectives.
- Warm starts: Each factor update is initialized with its previous factor and dual variable, so the outer AO loop naturally warm-starts the inner ADMM iteration.The previous iterate is expected to be close to the current subproblem solution, keeping the optimality gap small.
- Factor updates: For each factor, the algorithm forms Y = Y^(d) and W = ⊙_{j≠d} H_j, without necessarily constructing W explicitly.The same factor-update structure is used for the least-squares and general-loss branches.
11 else
The general-loss branch updates the factor, dual, auxiliary, and auxiliary-dual variables with warm starts, and may update the penalty parameter µ.
- General-loss branch: The general-loss update uses Alg. 2 to update H_d, U_d, ˜Y^(d), and V^(d) from their previous values.This branch is selected after forming the factor-specific Y and W quantities.
- Parameter update: The penalty parameter µ is updated when necessary during the general-loss factor-update cycle.The algorithm refers to equation (14) for this update.
20 end
The framework addresses implementation, convergence, and scalability through auxiliary-variable storage choices, proximal regularization, and bounded-iterate assumptions. Under the stated boundedness condition, AO-ADMM converges to a stationary point, while general-loss updates trade extra computation for broader loss flexibility.
- Implementation and scalability: Auxiliary variables can be replicated across tensor matricizations to save computation, but storing multiple data and auxiliary copies may be unrealistic for large datasets.Sparse-data implementations can therefore require scalability-aware storage strategies.
- Regularization: Proximal regularization can improve outer AO convergence and condition inner ADMM subproblems, especially for general losses without strong convexity.The paper presents this regularization as beneficial for both optimization levels.
- Convergence: If the AO-ADMM sequence is bounded, the algorithm converges to a stationary point of the original factorization problem.The convergence proposition relies explicitly on boundedness of the generated sequence.
- Convergence assumptions: For unconstrained PARAFAC, small Frobenius-norm regularization can ensure bounded iterates when diverging components might otherwise occur.This regularization is described as having a small weight.
- Computational cost: ADMM and AO have the same per-iteration complexity as unconstrained alternating least squares when the number of inner ADMM iterations is small.The dominant computations are data-structure-specific products such as W^T Y or (⊙_{j≠d} H_j)^T Y^(d).
- General-loss implementation: A least-squares initialization followed by general-loss optimization can save substantial computation because general-loss updates repeatedly calculate W^T(˜Y + V).The paper recommends first running Alg. 3 with Alg. 1, then using those estimates to initialize Alg. 2.
5 Case Studies and Numerical Results
The case studies evaluate AO-ADMM across non-negative factorization, completion, and dictionary learning, showing broad applicability and competitive or superior performance. Experiments cover synthetic and real matrix and tensor data, with practical mechanisms supporting efficient updates.
- Experimental scope: AO-ADMM is evaluated on non-negative matrix factorization, non-negative PARAFAC, matrix/tensor completion, and dictionary learning.The experiments include synthetic data and real datasets such as Extended Yale B, TDT2, CT, Facebook Wall Posts, Amino acids fluorescence, MovieLens, and MNIST.
- Non-negative factorization: AO-ADMM combines cached factorization, warm starts, and ADMM subproblem updates to support efficient constrained factorization.The method is especially suited to repeated NNLS instances and can incorporate regularization and constraints within the subproblems.
- Non-negative factorization: AO-based methods attain smaller fitting errors than direct ADMM on synthetic NMF data, while AO-ADMM provides the most efficient per-iteration complexity.This comparison is based on 100 Monte Carlo trials with 2000 × 2000 data matrices and rank 100.
- Non-negative factorization: AO-ADMM outperforms all other algorithms in all considered synthetic non-negative PARAFAC cases.The tensor experiments use 3-way tensors with dimensions 500 × 500 × 500, rank 100, and 100 Monte Carlo trials.
- Completion: In matrix completion, non-negativity reduces over-fitting at higher ranks, while the fitting criterion has little apparent effect on performance.Adding biases yields a best-case rank-4 prediction MAE below 0.69, approximately 6% better than the best reported result in.
- Completion: The completion study uses AO-ADMM to explore alternative formulations rather than to claim the best recommender-system method.The authors present this as a scope boundary and emphasize rapid testing of models for specific applications.
- Dictionary learning: For dictionary learning, column-norm constraints couple dictionary variables, but the AO-ADMM ADMM subroutine handles this coupling directly.The MNIST experiment imposes non-negativity on both dictionary and sparse coefficients and trains a 100-atom dictionary.
6 Conclusion
AO-ADMM is a flexible framework for constrained matrix and tensor factorization, combining AO and ADMM to support varied constraints and loss functions. Its efficiency, universality, convergence properties, and empirical case studies support broad applicability.
- AO-ADMM combines alternating optimization with ADMM-based factor updates for matrix and tensor factorization under varied constraints and loss functions.
- Cached computations and AO-provided warm starts give each iteration complexity similar to unconstrained ALS while reducing inner and outer iterations.
- ADMM enables efficient handling of non-least-squares terms, non-parametric constraints, and regularization penalties through proximity operators.
- AO ensures monotone loss decrease, while generalized block coordinate descent results guarantee convergence to a stationary point.
- Case studies in non-negative factorization, constrained completion, and dictionary learning with real-data experiments corroborate the framework's main claims.
- The framework is presented as plug-and-play support for exploring constraints, loss functions, and matrix or tensor co-factorization models.