Sum-of-Norms Regularized Nonnegative Matrix Factorization.

Area of Science:

• Machine Learning
• Data Analysis
• Signal Processing

Background:

• Nonnegative matrix factorization (NMF) is a widely used dimensionality reduction technique.
• Determining the optimal rank (nonnegative rank) for NMF is computationally challenging (NP-hard) and often relies on heuristics.
• Existing methods lack automatic rank estimation, requiring manual parameter tuning.

Purpose of the Study:

• To propose an approximation method for estimating the nonnegative rank on the fly during NMF.
• To introduce the Sum-of-Norm (SON) regularization for rank reduction in NMF.
• To develop an efficient algorithm for solving the proposed SON-NMF problem.

Main Methods:

• The Sum-of-Norm (SON) regularization is incorporated into NMF to promote pairwise similarity and reduce matrix rank.
• A first-order Block Coordinate Descent (BCD) algorithm is proposed to efficiently solve the nonconvex, nonsmooth SON-NMF problem.
• Graph-theoretic arguments are used to analyze the computational complexity of SON-NMF.

Main Results:

• SON-NMF successfully estimates the correct nonnegative rank from data without prior knowledge or parameter tuning across various datasets.
• The proposed BCD algorithm offers a low per-iteration cost for solving SON-NMF.
• SON-NMF demonstrates robustness in handling rank-deficient matrices and detecting weak components.

Conclusions:

• SON-NMF provides an effective and automated approach for nonnegative rank determination in NMF.
• The method shows promise for applications requiring automatic rank estimation, such as hyperspectral imaging, where it addresses spectral variability.