When applying nonnegative matrix factorization (NMF), generally the rank
parameter is unknown. Such rank in NMF, called the nonnegative rank, is usually
estimated heuristically since computing the exact value of it is NP-hard. In
this work, we propose an approximation method to estimate such rank while
solving NMF on-the-fly. We use sum-of-norm (SON), a group-lasso structure that
encourages pairwise similarity, to reduce the rank of a factor matrix where the
rank is overestimated at the beginning. On various datasets, SON-NMF is able to
reveal the correct nonnegative rank of the data without any prior knowledge nor
tuning.
SON-NMF is a nonconvx nonsmmoth non-separable non-proximable problem, solving
it is nontrivial. First, as rank estimation in NMF is NP-hard, the proposed
approach does not enjoy a lower computational complexity. Using a
graph-theoretic argument, we prove that the complexity of the SON-NMF is almost
irreducible. Second, the per-iteration cost of any algorithm solving SON-NMF is
possibly high, which motivated us to propose a first-order BCD algorithm to
approximately solve SON-NMF with a low per-iteration cost, in which we do so by
the proximal average operator. Lastly, we propose a simple greedy method for
post-processing.
SON-NMF exhibits favourable features for applications. Beside the ability to
automatically estimate the rank from data, SON-NMF can deal with rank-deficient
data matrix, can detect weak component with small energy. Furthermore, on the
application of hyperspectral imaging, SON-NMF handle the issue of spectral
variability naturally.

通过使用非负矩阵分解和 sum-of-norm 方法，本文提出了一种自动估计数据非负秩和处理光谱变异的 SON-NMF 算法。