PaperlayerView exact revision on arXiv

Source-linked AI summary

Using Underapproximations for Sparse Nonnegative Matrix Factorization

Nicolas Gillis, François Glineur

arXiv:0902.1060v2math.OC

TL;DR

Factor sparsity is important in practice because it reduces storage needs for basis elements and weights and improves interpretation, especially in classification and clustering. The paper uses underapproximation with Lagrangian relaxation to solve NMF recursively. The approach provides sparse part-based representations with low reconstruction error that are comparable to or sometimes superior to standard Sparse NMF techniques.

  • Problem

    Factor sparsity is important in practice because it reduces storage needs for basis elements and weights and improves interpretation, especially in classification and clustering.

    Source: §1 · p. 3

  • Method

    The paper uses underapproximation with Lagrangian relaxation to solve NMF recursively.

    Source: §1 · p. 4, §2.1 · p. 4, §3 · p. 9

  • Results

    The approach provides sparse part-based representations with low reconstruction error that are comparable to or sometimes superior to standard Sparse NMF techniques.

    Source: §1 · p. 4

  • Takeaways & Limitations

    The underapproximation approach offers an alternative for obtaining sparse representations in NMF.

    Source: §1 · p. 4

    Algorithm L-NMU convergence is not theoretically guaranteed, and its solutions may violate the underapproximation constraint; a quadratic-programming step can make them feasible.

    Source: §3.2 · p. 12

Abstract

from arXiv · show

Nonnegative Matrix Factorization consists in (approximately) factorizing a nonnegative data matrix by the product of two low-rank nonnegative matrices. It has been successfully applied as a data analysis technique in numerous domains, e.g., text mining, image processing, microarray data analysis, collaborative filtering, etc. We introduce a novel approach to solve NMF problems, based on the use of an underapproximation technique, and show its effectiveness to obtain sparse solutions. This approach, based on Lagrangian relaxation, allows the resolution of NMF problems in a recursive fashion. We also prove that the underapproximation problem is NP-hard for any fixed factorization rank, using a reduction of the maximum edge biclique problem in bipartite graphs. We test two variants of our underapproximation approach on several standard image datasets and show that they provide sparse part-based representations with low reconstruction error. Our results are comparable and sometimes superior to those obtained by two standard Sparse Nonnegative Matrix Factorization techniques.

1 Introduction

NMF approximates a nonnegative data matrix with low-rank nonnegative factors, whose constraints typically induce sparsity. The paper introduces an underapproximation approach for sparse NMF and reports that its representations are comparable to or sometimes better than standard sparse NMF methods.

1 Introduction

  • NMF approximates a nonnegative input matrix using low-rank nonnegative factors, with nonnegative weights yielding an additive, part-based reconstruction.For face images, basis elements can represent features such as eyes, noses, and lips.Source: §1 · p. 2
  • NMF’s nonnegativity constraints typically produce sparse factors with relatively many zero entries.The introduction attributes this tendency to stationary points typically lying on the boundary of the feasible domain.Source: §1 · p. 3
  • Sparsity reduces storage requirements and can improve factor interpretability, especially in classification and clustering.The introduction contrasts this with PCA, which does not naturally generate sparse factors.Source: §1 · p. 3
  • NMF has higher approximation error than unconstrained low-rank approximation at a given rank and is NP-hard, unlike PCA’s polynomial-time solution.The introduction notes that these drawbacks also apply to sparse-emphasizing alternatives such as SPCA.Source: §1 · p. 3
  • The paper introduces an underapproximation-based approach to obtain sparse NMF solutions and reports comparable or sometimes superior results to standard Sparse NMF techniques.The approach uses Lagrangian relaxation to solve NMF recursively.Source: §1 · p. 4

2 Nonnegative Matrix Underapproximation

Nonnegative Matrix Underapproximation (NMU) constrains the factor product to stay below the input, enabling recursive factor extraction with nonnegative residuals. The section relates this constraint to sparse, localized representations and proves NMU NP-hard for any factorization rank.

2.1 A recursive approach

  • NMU adds the constraint VW ≤ M, so subtracting each rank-one factor leaves a nonnegative residual for the next recursive step.Repeated rank-one underapproximations build a higher-rank factorization.Source: §2.1 · p. 4
  • On the swimmer dataset, NMU produces sparser basis elements that isolate single body parts, while NMF basis elements mix several limbs.Figure 2 compares sample images with the NMF and NMU bases for r = 8.Source: §2.1 · p. 5, Figure 2 · p. 5

2.2 Sparsity

  • For a rank-one underapproximation, the factor sparsities sum to at least the input matrix’s sparsity.Residual sparsity is nondecreasing across recursive steps; for a locally optimal rank-one underapproximation, the residual restricted to the factor supports has a zero in every row and column.Source: §2.2 · pp. 5–6

2.3 Related work

  • Earlier work studied rank-one underapproximation for particular objectives, convex initialization, or rank splitting, while another recursive method approximated nearly rank-one submatrices.The cited rank-splitting and submatrix-location problems are NP-hard, and the latter algorithm is not globally optimal.Source: §2.3 · pp. 6–7

2.4 Complexity

  • NMU is NP-hard for any factorization rank, via a reduction from the maximum edge biclique problem in bipartite graphs.For rank one, optimal underapproximations of binary matrices yield binary optimal solutions to the biclique problem.Source: §2.4 · pp. 7–8

3 An algorithm for NMU based on Lagrangian relaxation

L-NMU uses Lagrangian relaxation to approximately solve the NP-hard underapproximation problem, as a recursive approach to NMF. It alternates factor updates with multiplier updates, but is not guaranteed to converge to an optimal dual solution.

3 An algorithm for NMU based on Lagrangian relaxation

  • L-NMU approximately solves the NP-hard underapproximation problem through Lagrangian relaxation, as a recursive technique for NMF.The method is intended to produce sparse solutions.Source: §3 · p. 9
  • The Lagrangian dual maximizes a concave function over a convex set and supplies a lower bound on the optimal NMU value.The bound is described as hopefully tight.Source: §3 · p. 9

3.1 Solving the Lagrangian relaxation problem

  • For fixed multipliers, the relaxed subproblem becomes nonnegative factorization of M − Λ, which may contain negative entries.The algorithm uses HALS, alternately updating columns of V and rows of W with closed-form solutions.Source: §3.1 · p. 10
  • HALS initialization is scale-sensitive: if the initial product greatly exceeds M, updates can zero factors, causing rank deficiency and numerical problems.Scaling the initial matrices is recommended.Source: §3.1 · p. 10

3.2 Update of the multipliers Λ

  • Because the relaxed subproblem is NP-hard, L-NMU performs a fixed number of HALS updates between multiplier updates and has no guarantee of dual optimality.The authors report that this procedure produces satisfactory solutions in practice.Source: §3.2 · pp. 11–12
  • L-NMU may return factors that violate the underapproximation constraint, but a convex quadratic program involving V can repair feasibility.Replacing V with the QP solution yields a feasible pair (V, W).Source: §3.2 · p. 12
  • Applying exact multiplier-update rules directly to V and W is inefficient: constrained quadratic programs are costly, and iterates can become trapped at low-rank, overly sparse boundary solutions.The paper notes this behavior also for HALS-type updates without a prespecified sparsity pattern.Source: §3.2 · p. 12
  • For very sparse inputs, storing the potentially dense m × n multiplier matrix Λ makes L-NMU poorly suited to the setting.The authors note that exploiting the input sparsity pattern can reduce computational cost.Source: §3.2 · pp. 12–13

4 Numerical tests on image datasets

The experiments compare NMU with sparse NMF methods to assess whether its greater sparsity is worth the reconstruction-accuracy trade-off. They describe two comparison methods and report sparsity using two measures.

4 Numerical tests on image datasets

  • The experiments compare NMU with two sparse NMF techniques because a direct NMU–NMF comparison juxtaposes greater sparsity against lower approximation error.The aim is to assess whether NMU's sparsity improvement is worth its reconstruction-accuracy loss.Source: §4 · p. 13

4.1 Sparse NMF

  • Hoyer's method enforces explicit factor sparsity at each iteration by projection and reduces approximation error using projected-gradient and multiplicative updates.The experiments use the author's MATLAB code.Source: §4.1 · p. 13
  • The experiments report sparsity using both the standard indicator and Hoyer's measure.Hoyer's measure assigns full sparsity to a vector with one nonzero entry and treats equal-valued entries as completely dense.Source: §4.1 · p. 13
  • The second comparison method adds l1-norm penalty terms to the objective to induce sparser solutions.The passage presents this as an alternative to enforcing sparsity at every iteration.Source: §4.1 · p. 14

F + µV ||V ||1 + µW ||W||1, (sNMF)

The experiments compare global and recursive NMU with standard and sparse NMF methods, including comparisons at matched sparsity. Results vary by dataset: NMU often yields more localized or sparser parts, while reconstruction-error trade-offs depend on the data and underapproximation constraint.

F + µV ||V ||1 + µW ||W||1, (sNMF)

  • sNMF adds l1 penalties for the factors to induce sparsity; its penalty parameters require selection, unlike methods that set sparsity a priori.The experiments use HALS for sNMF and adjust the penalty parameters during iterations to approach target sparsity.Source: F + µV ||V ||1 + µW ||W||1, (sNMF) · p. 14, §4.4 · p. 15

4.2 Tested algorithms

  • The experiments compare NMF, G-NMU, R-NMU, sNMF, and Hoyer, with PCA as a reference, and match sparse baselines to each NMU variant’s sparsity.Hoyer’s sparsity could be matched only for the sparser NMU factor; sNMF’s penalty parameters were adaptively adjusted toward target sparsity.Source: §4.2 · p. 14, §4.4 · p. 15

4.3 Iteration limits and CPU time

  • Iteration limits roughly equalize CPU time across methods, except Hoyer, which receives a longer run because equal-time results were too poor to compare meaningfully.On CBCL, 600 HALS iterations took about 80 seconds, while 1,000 Hoyer iterations took about 260 seconds.Source: §4.3 · pp. 14–15

4.5 CBCL Face Database

  • On CBCL faces, G-NMU, R-NMU, and sNMF produce sparser, more part-based representations than NMF; R-NMU extracts a dense mean face before progressively sparser complementary parts.Figure 3 compares NMF, G-NMU, R-NMU, and sNMF at G-NMU’s sparsity.Source: §4.5 · p. 15, Figure 3 · p. 16
  • On CBCL, after refining solutions with fixed zero patterns, NMU’s error is close to sNMF and Hoyer and not far from denser NMF, making its sparsity–error trade-off worthwhile.Before refinement, G-NMU has three-quarters zero entries and error 8.12→12.45; at similar sparsity, sNMF and Hoyer report errors of 8.68 and 9.33, but direct comparison is qualified by NMU’s underapproximation constraint.Source: Table 1 · p. 16, §4.5 · p. 17

4.6 Swimmer Database

  • For swimmer images, the two NMU variants extract independent parts, whereas NMF and sNMF generate combinations of them.Figure 4 compares the basis elements from NMF, G-NMU, R-NMU, and sNMF at R-NMU’s sparsity.Source: §4.6 · p. 17, Figure 4 · p. 18

4.7 Hubble Space Telescope Spectral Images

  • On Hubble images, where rank-8 NMF is nearly exact, G-NMU is basically equivalent to NMF, while R-NMU gives the sparsest solution and identifies telescope parts missed by other methods.R-NMU first extracts a global telescope image, then its constituent parts.Source: §4.7 · pp. 17–18, Figure 6 · p. 19, Table 3 · p. 19

4.8 Kuls Illuminated Faces

  • On Kuls illuminated faces, R-NMU extracts a global face followed by complementary lighting-direction parts, while matched-sparsity sNMF has slightly better error but only two well-identified components.The R-NMU sequence is global, then lighting from the right, left, bottom, and top.Source: §4.8 · p. 20, Table 4 · p. 20

5 Conclusion

NMU is an NP-hard underapproximation problem addressed with a Lagrangian-relaxation algorithm. Tested variants offer sparse, part-based representations with reconstruction error comparable to or sometimes better than two standard sparse factorization techniques, with distinct trade-offs between G-NMU and R-NMU.

5 Conclusion

  • NMU is NP-hard, and the paper proposes a Lagrangian-relaxation algorithm to find approximate solutions.NMU is introduced to support solving NMF recursively; its NP-hardness is shown using equivalence with the maximum-edge biclique problem.Source: §5 · p. 20
  • The two tested NMU variants offer a good sparsity–approximation-error compromise, comparable or sometimes superior to two standard sparse matrix factorization techniques.The variants were tested on several standard image datasets after suitable post-processing.Source: §5 · p. 20
  • G-NMU focuses on sparse factors with small reconstruction error, while R-NMU typically yields sparser, more part-based factors at a moderate reconstruction-error increase.R-NMU's increase is attributed to its greedy approach.Source: §5 · p. 20
  • R-NMU's recursion lets users stop when reconstruction error is satisfactory, avoiding recomputation when considering a higher-rank factorization.This is useful when the factorization rank is not fixed in advance.Source: §5 · pp. 20–21
Loading 0902.1060v2…