Efficient Algorithms for Regularized Nonnegative Scale-invariant Low-rank Approximation Models

2024/03/27 by Jérémy E. Cohen, Cohen, Jeremy E., Valentin Leplat +1 · 3 citations
Computer Science · Engineering · Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Medical Image Segmentation Techniques #Numerical Analysis (math.NA) #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Statistical and numerical algorithms

paper · pdf · doi:10.48550/arxiv.2403.18517

openalex publication_date 2024/03/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Regularized nonnegative low-rank approximations, such as sparse Nonnegative Matrix Factorization or sparse Nonnegative Tucker Decomposition, form an important branch of dimensionality reduction models known for their enhanced interpretability. From a practical perspective, however, selecting appropriate regularizers and regularization coefficients, as well as designing efficient algorithms, remains challenging due to the multifactor nature of these models and the limited theoretical guidance available. This paper addresses these challenges by studying a more general model, the Homogeneous Regularized Scale-Invariant model. We prove that the scale-invariance inherent to low-rank approximation models induces an implicit regularization effect that balances solutions. This insight provides a deeper understanding of the role of regularization functions in low-rank approximation models, informs the selection of regularization hyperparameters, and enables the design of balancing strategies to accelerate the empirical convergence of optimization algorithms. Additionally, we propose a generic Majorization-Minimization (MM) algorithm capable of handling ℓ_p^p-regularized nonnegative low-rank approximations with non-Euclidean loss functions, with convergence guarantees. Our contributions are demonstrated on sparse Nonnegative Matrix Factorization, ridge-regularized Nonnegative Canonical Polyadic Decomposition, and sparse Nonnegative Tucker Decomposition.

Cited by

• Fast and Accurate SVD-Type Updating in Streaming Data
• Goal-Oriented Low-Rank Tensor Decompositions for Numerical Simulation Data
• Structured Variational D-Decomposition for Accurate and Stable Low-Rank Approximation

Related

• Sharper Bounds for Regularized Data Fitting
• Low Rank Regularization: A Review
• On solving a rank regularized minimization problem via equivalent factorized column-sparse regularized models
• Regularized Weighted Low Rank Approximation
• Low-Rank Factorization for Rank Minimization with Nonconvex Regularizers