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

arXiv: https://arxiv.org/abs/2403.18517 · HTML: https://mlsanity.com/paper/2403.18517/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 84 references that are in the map.
- First posted on arXiv 27 Mar 2024.

## Builds on (most cited first, 18 of 18)

- [In Search of the Real Inductive Bias: On the Role of Implicit Regularization in Deep Learning](https://mlsanity.com/paper/1412.6614/) (2014)
- [TensorLy: Tensor Learning in Python](https://mlsanity.com/paper/1610.09555/) (2016)
- [SLOPE - Adaptive variable selection via convex optimization](https://mlsanity.com/paper/1407.3824/) (2014)
- [Celer: a Fast Solver for the Lasso with Dual Extrapolation](https://mlsanity.com/paper/1802.07481/) (2018)
- [On Representer Theorems and Convex Regularization](https://mlsanity.com/paper/1806.09810/) (2018)
- [A unifying representer theorem for inverse problems and machine learning](https://mlsanity.com/paper/1903.00687/) (2019)
- [Deep Learning Meets Sparse Regularization: A Signal Processing Perspective](https://mlsanity.com/paper/2301.09554/) (2023)
- [Efficient Nonnegative Tucker Decompositions: Algorithms and Uniqueness](https://mlsanity.com/paper/1404.4412/) (2014)
- [Algorithms for Nonnegative Matrix Factorization with the Kullback-Leibler Divergence](https://mlsanity.com/paper/2010.01935/) (2020)
- [Equi-normalization of Neural Networks](https://mlsanity.com/paper/1902.10416/) (2019)
- [An AO-ADMM approach to constraining PARAFAC2 on all modes](https://mlsanity.com/paper/2110.01278/) (2021)
- [Multiplicative Updates for NMF with β-Divergences under Disjoint Equality Constraints](https://mlsanity.com/paper/2010.16223/) (2020)
- [Uncovering audio patterns in music with Nonnegative Tucker Decomposition for structural segmentation](https://mlsanity.com/paper/2104.08580/) (2021)
- [Joint Majorization-Minimization for Nonnegative Matrix Factorization with the β-divergence](https://mlsanity.com/paper/2106.15214/) (2021)
- [Tensor Balancing on Statistical Manifold](https://mlsanity.com/paper/1702.08142/) (2017)
- [Identifiability of Complete Dictionary Learning](https://mlsanity.com/paper/1808.08765/) (2018)
- [Majorization-minimization for Sparse Nonnegative Matrix Factorization with the β-divergence](https://mlsanity.com/paper/2207.06316/) (2022)
- [Nonnegative Tucker Decomposition with Beta-divergence for Music Structure Analysis of Audio Signals](https://mlsanity.com/paper/2110.14434/) (2021)

## Built on by (most cited first, 2 of 2)

- [Structured Variational D-Decomposition for Accurate and Stable Low-Rank Approximation](https://mlsanity.com/paper/2506.08535/) (2025)
- [Fast and Accurate SVD-Type Updating in Streaming Data](https://mlsanity.com/paper/2509.02840/) (2025)

## Abstract (arXiv)

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 ℓpp-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.