PaperlayerView exact revision on arXiv

Source-linked AI summary

Separable Nonnegative Matrix Factorization Using Powered Ratio-of-Norms Regularization

Matthew McCarver, Jing Qin

arXiv:2608.28799v1math.NAcs.LGmath.OC

TL;DR

SNMF anchor selection is challenged by scale-sensitive regularization and the need to promote sparsity or low-rankness. The paper introduces powered ratio-of-norms models and DCA/ADMM solvers, with experiments showing generally more reliable ADMM recovery and a favorable accuracy-cost balance for entrywise ℓ1 regularization. The analysis is limited by exact-subproblem assumptions and sensitivity to parameter selection in challenging noise regimes.

  • Problem

    SNMF must identify anchor columns while regularizers promote sparsity or low-rankness without confusing extreme columns with interior points under varying data scales.

  • Method

    The paper develops powered ratio-of-norms SNMF models using entrywise ℓ1 or nuclear norms, solved by DCA- and ADMM-based algorithms.

  • Results

    ADMM-based methods generally provide more reliable recovery than DCA, while the entrywise ℓ1 formulation balances accuracy and computational cost.

  • Takeaways & Limitations

    The experiments support powered ratio-of-norms regularization for basis identification and feature selection on synthetic and hand gesture datasets.

  • Takeaways & Limitations

    The analysis assumes exact subproblem solutions, while numerical performance remains sensitive to parameter selection in challenging noise regimes.

Abstract

from arXiv · show

Separable nonnegative matrix factorization (SNMF) has been widely used for low-rank representation and clustering of nonnegative data, owing to its ability to produce part-based and interpretable decompositions. In particular, SNMF is closely related to graph clustering and community detection. To enhance sparsity and identifiability of the learned factors, we propose an $\ell_1^p/\ell_2$-regularized SNMF model based on a powered ratio-of-norms regularizer. The resulting formulation is nonconvex and nonsmooth, which poses significant challenges for optimization. To address this, we develop efficient algorithms based on the difference-of-convex function algorithm (DCA) and the alternating direction method of multipliers (ADMM). The proposed methods decompose the original problem into tractable subproblems, leveraging closed-form proximal operators associated with the powered norm terms. We establish descent and limiting criticality properties for the DCA scheme and convergence under standard assumptions for the ADMM scheme. Extensive numerical experiments on synthetic datasets and hand gesture classification tasks demonstrate that the proposed approach achieves competitive or improved performance in anchor identification and classification accuracy compared with existing SNMF methods, while maintaining competitive computational efficiency.

1 Introduction

SNMF selects anchor columns through sparse or low-rank representations, but scale-sensitive convex regularizers can confuse extreme columns with interior points. The paper proposes powered ratio-of-norms regularization with DCA- and ADMM-based algorithms, evaluated on synthetic and hand gesture data.

  • SNMF identifies a subset of data columns as anchors representing the extreme points of the data geometry.
  • Scale-sensitive ℓ1 and nuclear-norm regularizers may fail to distinguish extreme columns from interior points when data magnitudes vary.
  • The proposed powered ratio-of-norms regularizer uses entrywise ℓ1 or nuclear norms to enhance sparsity and low-rankness.
  • DCA and ADMM algorithms solve the resulting models, with DCA used for p = 1 and ADMM supporting p ∈{1, 2, 3, 4}.
  • Experiments compare identification accuracy and runtime on synthetic datasets and evaluate hand gesture classification against related SNMF approaches.

2 Preliminaries

The paper defines powered ratio-of-norms regularizers using entrywise ℓ1 or nuclear norms, linking them to sparsity and low-rank structure. It analyzes their geometry, scale behavior, semi-algebraicity, and proximal operators used by the algorithms.

  • The powered ratio-of-norms regularizer uses a general matrix norm, with entrywise ℓ1 and nuclear-norm forms promoting sparsity and low-rank structure, respectively.
  • For normalized matrices, the nuclear-norm regularizer equals 1 exactly at rank one, while the entrywise ℓ1 regularizer equals 1 exactly for one nonzero entry.
  • The regularizer scales as Rp(cX) = |c|^(p−1)Rp(X), so scale invariance holds only when p = 1.
  • Its level sets remain concentrated along coordinate axes, preserving a sparsity-promoting geometry whose shape changes with p.
  • For integer p ≥1, both entrywise ℓ1- and nuclear-norm versions are semi-algebraic, supporting convergence analysis.
  • Closed-form proximal operators for the powered entrywise ℓ1 term are available only for p ∈{1, 2, 3, 4}, motivating the paper’s restriction to these powers.

3 Proposed Methods

The proposed SNMF models use powered ratio-of-norms regularization and solve the resulting nonconvex problems with DCA- and ADMM-based schemes. The algorithms provide conditional criticality or convergence guarantees under stated assumptions, while implementation uses approximate constrained proximal updates and post-processing for anchor selection.

  • Model formulation: The models use powered ratio-of-norms regularization to promote sparsity and low-rankness in SNMF.The regularizer supports entrywise ℓ1 and nuclear-norm choices in the numerator.
  • DCA formulation: A fractional-programming characterization motivates the parametric DC formulation, but the algorithm solves the resulting parametric DC subproblem rather than the fractional problem directly.The parametric coefficient is recomputed from the current iterate.
  • DCA algorithm: The DCA scheme uses inner ADMM iterations with least-squares and proximal subproblems, including a factorization-based solve whose post-factorization cost is O(n^2).The method introduces an auxiliary copy for the nonsmooth constrained term and solves the X-subproblem in closed form after factorization.
  • DCA algorithm: The constrained proximal update is solved exactly in the theoretical descent result but approximated by unconstrained proximal evaluation followed by projection in numerical experiments.The projection composition is not generally equal to the exact constrained proximal map.
  • Convergence analysis: Under exact inner solves and standard boundedness, descent, and relative-error assumptions, the algorithms have conditional limiting-criticality or primal-dual convergence guarantees.The DCA result is conditional on convergence of the iterate and parameter sequences, while the ADMM result uses the KL property.
  • ADMM algorithm: The ADMM scheme introduces auxiliary variables to separate the regularizer and constraint, producing tractable subproblems including a least-squares Y-update.The X-subproblem further decouples numerator, denominator, and indicator terms through auxiliary variables.

4 Numerical Experiments

The experiments evaluate anchor identification on synthetic data and feature selection for hand-gesture classification. Across noisy synthetic and grayscale image settings, ADMM-P is consistently strong, while entrywise regularization generally offers better computational efficiency.

  • Experimental setup: The study compares Algorithms 1–2 with SPA, FGNSR, MERIT, VCA, and XRAY using success rate, MRSA, RAE, runtime, and classification accuracy.Synthetic experiments use noise-free and noisy Type 1 midpoint and Type 2 Dirichlet data; image experiments evaluate binary and grayscale hand-gesture features.
  • Synthetic data: Type 1 midpoint data are challenging because non-anchor columns lie exactly between pairs of anchor columns, whereas Type 2 data use Dirichlet mixtures.Both synthetic datasets have rank r = 10 and are evaluated under controlled noise constructions.
  • Noise-free data: ADMM-P achieves exact noise-free recovery on Type 1 for p ≥2 and on Type 2 for most tested p values, while DCA performs poorly on the more challenging Type 1 data.DCA perfectly recovers Type 2 under both regularizers but reaches 0.68 under Rp,1 and 0 under Rp,∗ on Type 1.
  • Noisy data: ADMM-P maintains a perfect Type 1 success rate across ε ∈[10^-2, 1] with Rp,1, while baseline methods fail or degrade at lower noise levels.Under Rp,∗, ADMM-P remains nearly perfect, but nuclear-norm variants incur substantially higher runtime because of the SVD subproblem.
  • Noisy data: On Type 2 data, methods remain near unity until ε ≈0.3, while Rp,1 runtimes stay below 0.4s and Rp,∗ variants reach up to ≈2.7s.The synthetic results support improved noise robustness on midpoint geometries, with entrywise regularization providing comparable accuracy at lower computational cost.
  • Hand gesture classification: On grayscale features, ADMM-P reaches 0.87–0.90 for HOG and 0.84–0.86 for LBP, generally outperforming the baselines across factorization ranks.For HOG, the proposed methods exceed the full-feature SVM baseline of 0.84 for r ≥260; proposed-method runtimes range from approximately 26 to 70 seconds.

5 Discussion

The discussion examines parameter selection, ablations, computational cost, and high-noise behavior. It emphasizes how the powered ratio framework varies with p and how the grayscale experiments report tuned parameters, accuracies, and runtimes.

  • Discussion scope: The discussion studies Bayesian parameter selection, algorithm ablations, per-iteration cost, and a limitation of the high-noise synthetic results.The design parameters include the numerator power p, inner and outer iteration budgets J and K, and matrix dimensions.
  • Parameter selection: Table 6 reports the best parameters for selected p values on grayscale data with the Rp,1(X) regularizer.The table is part of the grayscale experimental analysis.
  • Performance and cost: Table 7 reports grayscale classification accuracies for the Rp,1(X) regularizer, while Table 8 reports the corresponding runtimes in seconds.Together, the tables support comparison of predictive performance and computational cost.

5.1 Parameter Selection via Bayesian Optimization

Bayesian optimization tunes algorithm parameters across data types, noise levels, and regularizers, but Type 1 experiments require post-hoc regime-specific selection at high noise and use transductive feature selection for classification.

  • Tuning setup: Bayesian optimization tunes DCA and ADMM-P parameters over logarithmic ranges for synthetic and hand gesture experiments.The tuned parameters differ by algorithm and include regularization, penalty, and algorithm-specific ADMM parameters.
  • Tuning setup: For synthetic recovery, tuning conditions include data type, noise level, regularizer, and ADMM-P power p.DCA uses p = 1, whereas ADMM-P considers p ∈{1, 2, 3, 4}.
  • Synthetic experiments: 20 noise-specific Bayesian optimization runs evaluate mean exact-recovery error before the resulting parameter vectors are tested across the full noise sweep.The recovered and ground-truth index sets define the exact-recovery objective.
  • Hand gesture experiments: Hand gesture tuning varies dataset, feature type, regularizer, target rank, and ADMM-P power, using SVM classification error because ground-truth anchors are unavailable.Feature selection is performed on the complete feature matrix before the train/test splits, yielding a transductive protocol.

5.2 Ablation Studies

The ablations examine power, iteration budgets, matrix size, and regularizer choice. ADMM-P is generally robust and accurate, while p = 4 can be fragile and the nuclear-norm regularizer is more sensitive and computationally costly.

  • Power parameter: Under Rp,1, p ∈{2, 3} maintains success rates near 1 across the noise sweep, including the transition band near ε ≈0.2–0.3.p = 1 and p = 4 show sharp dips near ε ≈0.2 before recovering.
  • Power parameter: Under Rp,∗, p ∈{1, 2, 3} remains near 1 across the noise sweep, whereas p = 4 exhibits a fragile dip near ε ≈0.2–0.3.Increasing p beyond 3 provides no benefit under either regularizer and begins to hurt under Rp,∗.
  • Iteration budgets: ADMM-P with Rp,1 maintains near-perfect accuracy across nearly all tested inner and outer iteration budgets, including J = 1 and K = 5.DCA is more sensitive, with accuracy declining after about 10 inner iterations and oscillating across early outer iterations.
  • Iteration budgets: With Rp,∗, ADMM-P reaches perfect accuracy after only a few outer iterations but is more sensitive to the inner budget, especially for p = 1 and J ≤10.The nuclear-norm regularizer introduces greater sensitivity to inner iterations.
  • Iteration budgets: Across both regularizers, p = 2 is uniformly stable, while DCA requires more careful tuning with J ≈10 and K ∈[10, 50].ADMM-P tolerates J as small as 1 and K as small as 5 in the tested settings.
  • Matrix size: For Type 2 data, 100 × 200 instances achieve the highest accuracy, followed by medium and 30 × 60 instances, under both regularizers.The reported ordering is attributed to increased measurement information as the problem size grows.
  • Matrix size: As matrix size increases, Rp,1 remains computationally inexpensive, whereas the SVD required by Rp,∗ becomes the dominant expense.The accuracy and runtime results favor Rp,1 for balancing recovery accuracy and computational cost.

5.3 Computational Complexity

The per-iteration cost is governed mainly by the regularizer: Rp,1 uses quadratic-cost proximal updates, whereas Rp,∗ requires cubic-cost SVD computations, in addition to projection costs.

  • Per-iteration costs: Projecting an n × n matrix onto Ω costs O(n^2 log n), while Rp,1 and Rp,∗ proximal updates cost O(n^2) and O(n^3), respectively.The cubic Rp,∗ cost comes from an SVD.
  • Algorithmic costs: Algorithm 1 additionally requires one O(n^3) Cholesky factorization, while its inner iterations include updates costing O(n^2), O(n^3), O(n^2 log n), and O(n^2) depending on the step.The outer α-update costs O(n^2) for Rp,1 and O(n^3) for Rp,∗.
  • Runtime implications: Both algorithms share the same asymptotic per-inner-iteration cost under each regularizer, so observed runtime differences primarily reflect constant factors and iteration counts.The larger-size runtime gap is consistent with the higher asymptotic cost of the SVD-based Rp,∗ update.

6 Conclusions

The paper introduces powered ratio-of-norms SNMF with DCA and ADMM algorithms and evaluates it on synthetic and hand gesture data. ADMM-based methods generally recover anchors more reliably, while Rp,1 balances accuracy and computational cost.

  • Contributions: The work introduces powered ratio-of-norms regularization with entrywise ℓ1 and nuclear-norm variants for separable nonnegative matrix factorization.The resulting models are nonconvex, and DCA- and ADMM-based algorithms are developed to solve them.
  • Conclusions: ADMM-based methods generally provide more reliable recovery than DCA, while the entrywise ℓ1 formulation offers a favorable balance between accuracy and computational cost.The experiments cover basis identification and feature selection.
  • Conclusions: Recovery performance and robustness depend on the power parameter p, and the analysis relies on standard exact-subproblem assumptions while challenging-noise performance remains parameter-sensitive.These conclusions identify both a design factor and a scope boundary for the reported results.
Loading 2608.28799v1…