Maximum-Volume Nonnegative Matrix Factorization

Technical Summary: Maximum-Volume Nonnegative Matrix Factorization

Problem Statement
Nonnegative Matrix Factorization (NMF) is a widely used technique for decomposing a nonnegative data matrix $X \in \mathbb{R}^{m \times n}$ into two lower-dimensional nonnegative factors, $W \in \mathbb{R}^{m \times r}$ and $H \in \mathbb{R}^{r \times n}$, such that $X \approx WH$. In applications like hyperspectral unmixing (HU), $W$ represents spectral signatures (endmembers) and $H$ represents abundances. To ensure unique and interpretable solutions, volume-based regularization is often employed. The standard approach, Minimum-Volume NMF (MinVol NMF), minimizes the volume of the simplex spanned by $W$. However, the authors identify two significant weaknesses in MinVol NMF, particularly in noisy settings:

1. Bias and Rank Deficiency: The trade-off between data fitting and volume minimization can induce bias, leading to rank-deficient solutions where useful endmembers are shrunk to zero (e.g., due to low magnitude) to reduce volume, even at the cost of increased reconstruction error.
2. Lack of Sparsity Control: Minimizing the volume of $W$ does not directly control the sparsity of $H$. In noisy scenarios, shrinking the volume of $W$ does not guarantee that data points will lie on the facets of the convex hull, meaning it fails to consistently promote sparse abundance vectors.

Methodology
The paper proposes Maximum-Volume NMF (MaxVol NMF), a dual approach to MinVol NMF. Instead of minimizing the volume of $W$, MaxVol NMF maximizes the volume of the factor $H$.

• Theoretical Foundation: In the noiseless case ($X=WH$), minimizing $\det(W^\top W)$ is mathematically equivalent to maximizing $\det(HH^\top)$. Thus, MaxVol NMF shares the same identifiability conditions as MinVol NMF under the Sufficiently Scattered Condition (SSC).
• Optimization Formulation: In the presence of noise, the problem is formulated as:
  $$\min_{W,H} \frac{1}{2}\|X - WH\|_F^2 - \lambda \log \det(HH^\top + \delta I)$$
  subject to $W \ge 0$ and $H \in \Delta^{r \times n}$ (columns of $H$ sum to one). Unlike MinVol NMF, the $\log \det$ term here penalizes rank deficiency in $H$, ensuring $H$ remains full rank.
• Algorithms: The authors propose two algorithms to solve this non-convex problem:
  1. Adaptive Accelerated Gradient Descent: An adaptation of existing methods that approximates local Lipschitzness using previous iterates to compute step sizes.
  2. Alternating Direction Method of Multipliers (ADMM): This reformulates the problem by introducing an auxiliary variable $Y = HH^\top$. To handle the non-Lipschitz gradient of the objective with respect to $H$, the authors derive a Bregman surrogate based on a quartic norm kernel. This allows for a closed-form update step within the ADMM framework.
• Normalized Variant (N-MaxVol NMF): The authors observe that as the penalty parameter $\lambda \to \infty$, standard MaxVol NMF forces $H$ into a "hard clustering" state where clusters are of equal size. To mitigate this, they introduce N-MaxVol NMF, which maximizes the volume of the row-wise normalized $H$ (denoted $\tilde{H}$). This variant removes the simplex constraint on $H$, allows for uneven cluster sizes, and creates a continuum between standard NMF and Orthogonal NMF (ONMF).

Key Contributions

1. Dual Formulation: The paper establishes MaxVol NMF as a viable dual to MinVol NMF, proving it is identifiable under the same conditions in the noiseless case.
2. Algorithmic Development: Two distinct algorithms are proposed to solve the MaxVol NMF objective, with the ADMM approach utilizing a novel Bregman surrogate to handle the specific non-smoothness of the log-determinant term.
3. Theoretical Insight on Sparsity and Clustering: The authors demonstrate that MaxVol NMF naturally promotes sparse solutions for $H$ without inducing the rank-deficiency issues seen in MinVol NMF. They further characterize the asymptotic behavior of MaxVol NMF as a hard clustering mechanism and propose N-MaxVol NMF to allow for soft clustering and uneven cluster sizes.
4. Empirical Validation: Extensive experiments on synthetic data and real hyperspectral datasets (Samson, Moffett, Urban, Jasper) show that N-MaxVol NMF generally outperforms both standard NMF and MinVol NMF, particularly in extracting sparse, physically meaningful endmembers and abundances.

Results

• Synthetic Data: N-MaxVol NMF outperforms MinVol NMF when the abundance matrix $H$ is not stochastic (i.e., when lighting conditions vary), while MaxVol NMF performs best when $H$ is stochastic. Crucially, MaxVol NMF avoids the rank-deficient solutions that plague MinVol NMF.
• Hyperspectral Unmixing:
  • On the Samson and Moffett datasets, N-MaxVol NMF successfully separates water, soil, and tree with spectral signatures closer to ground truth than MinVol NMF.
  • On the Urban dataset, the model effectively distinguishes between materials (e.g., asphalt vs. dirt, grass vs. dry grass) by adjusting the rank $r$.
  • On the Jasper dataset, known for difficulty in separating water and road, the authors show that increasing the rank $r$ in N-MaxVol NMF allows for the identification of mixed endmembers (e.g., a "tree+soil" component), thereby improving the separation of water and road without compromising other factors.
• Algorithm Performance: The ADMM algorithm with the Bregman surrogate generally converges faster and to lower error than the adaptive gradient method on synthetic and Moffett data, though it incurs higher computational cost per iteration.

Significance
The paper claims that MaxVol NMF offers a robust alternative to the widely used MinVol NMF, specifically addressing the critical issues of bias-induced rank deficiency and the inability to explicitly control sparsity in noisy environments. By introducing the normalized variant (N-MaxVol NMF), the authors provide a flexible framework that bridges standard NMF and Orthogonal NMF, offering better performance in hyperspectral unmixing tasks. The work highlights that maximizing the volume of the abundance matrix $H$ is a more effective strategy for extracting sparse, interpretable decompositions than minimizing the volume of the basis matrix $W$. The authors note that while N-MaxVol NMF shows superior empirical results, its theoretical identifiability remains an open question for future research.