Efficient Algorithms for Regularized Nonnegative Scale-invariant Low-rank Approximation Models
This work addresses practical issues in dimensionality reduction for interpretable data analysis, offering theoretical insights and efficient algorithms, though it is incremental in extending existing regularization methods.
The paper tackled the challenge of selecting regularizers and hyperparameters in nonnegative low-rank approximation models by studying a scale-invariant model, revealing an implicit regularization effect that balances solutions and aids in algorithm design, and proposed a Majorization-Minimization algorithm with convergence guarantees for handling various regularized models.
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 $\ell_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.