Efficient Algorithms for Regularized Nonnegative Scale-invariant
  Low-rank Approximation Models
Jeremy E. Cohen Valentin Leplat
Regularized nonnegative low-rank approximations such as sparse Nonnegative
Matrix Factorization or sparse Nonnegative Tucker Decomposition are an
important branch of dimensionality reduction models with enhanced
interpretability. However, from a practical perspective, the choice of
regularizers and regularization coefficients, as well as the design of
efficient algorithms, is challenging because of the multifactor nature of these
models and the lack of theory to back these choices. This paper aims at
improving upon these issues. By studying a more general model called the
Homogeneous Regularized Scale-Invariant, we prove that the scale-invariance
inherent to low-rank approximation models causes an implicit regularization
with both unexpected beneficial and detrimental effects. This observation
allows to better understand the effect of regularization functions in low-rank
approximation models, to guide the choice of the regularization
hyperparameters, and to design balancing strategies to enhance the convergence
speed of dedicated optimization algorithms. Some of these results were already
known but restricted to specific instances of regularized low-rank
approximations. We also derive a generic Majorization Minimization algorithm
that handles many regularized nonnegative low-rank approximations, with
convergence guarantees. We showcase our contributions on sparse Nonnegative
Matrix Factorization, ridge-regularized Canonical Polyadic decomposition and
sparse Nonnegative Tucker Decomposition.