PaperlayerView exact revision on arXiv

Source-linked AI summary

Sparse and Unique Nonnegative Matrix Factorization Through Data Preprocessing

Nicolas Gillis

arXiv:1204.2436v1stat.MLmath.NAmath.OC

TL;DR

NMF is useful for sparse, part-based representations but is often ill-posed because many equivalent factorizations exist. The paper preprocesses the nonnegative input using an inverse-positive transformation to produce sparser, more well-posed problems. Under separability the preprocessing is optimal, and in the exact rank-three case it makes the set of optimal solutions finite.

  • Problem

    NMF can have many equivalent factorizations, while practical optimization is difficult because the objective is NP-hard and standard algorithms generally guarantee only stationary-point convergence.

  • Method

    The paper preprocesses M as P(M)=MQ using an inverse-positive matrix Q, choosing the transformation so the result is nonnegative and sparse.

  • Results

    Under Donoho–Stodden separability, preprocessing is optimal because it identifies the convex-hull vertices of M, and for exact rank-three matrices it makes the set of optimal NMF solutions finite.

  • Takeaways & Limitations

    The approach provides a preprocessing-based route to sparser and more well-posed NMF problems without adding constraints directly to the NMF model.

  • Takeaways & Limitations

    Optimizing over inverse-positive matrices appears difficult, and the paper notes that the complexity of this problem lacks rigorous analysis.

Abstract

from arXiv · show

Nonnegative matrix factorization (NMF) has become a very popular technique in machine learning because it automatically extracts meaningful features through a sparse and part-based representation. However, NMF has the drawback of being highly ill-posed, that is, there typically exist many different but equivalent factorizations. In this paper, we introduce a completely new way to obtaining more well-posed NMF problems whose solutions are sparser. Our technique is based on the preprocessing of the nonnegative input data matrix, and relies on the theory of M-matrices and the geometric interpretation of NMF. This approach provably leads to optimal and sparse solutions under the separability assumption of Donoho and Stodden (NIPS, 2003), and, for rank-three matrices, makes the number of exact factorizations finite. We illustrate the effectiveness of our technique on several image datasets.

1 Introduction

NMF represents nonnegative data through additive combinations of nonnegative basis elements, but its equivalent factorizations make interpretation and optimization difficult. The paper proposes preprocessing the input matrix to obtain sparser, more well-posed NMF problems while preserving nonnegativity and column-space structure.

  • NMF motivation: NMF approximates a nonnegative matrix M with nonnegative factors U and V, yielding additive, part-based representations of data columns.The columns of U act as basis elements, while V supplies nonnegative combination weights.
  • NMF motivation: NMF is used across applications including hyperspectral imaging, text mining, clustering, air emission control, blind source separation, and music analysis.
  • Challenges: Equivalent factorizations can change the supports of U and V, making topic or feature interpretations dependent on the chosen solution.For document data, these supports indicate word-topic and topic-document assignments.
  • Existing approaches: Standard approaches impose sparsity, minimum-volume, or orthogonality constraints, but these modify the NMF model through penalties or structural restrictions.
  • Proposed approach: The proposed method preprocesses M into a sparser matrix while preserving nonnegativity and its column space, motivated by NMF’s geometric interpretation.The preprocessing is P(M)=MQ, where Q is inverse-positive, and NMFs can be transferred back to M.
  • Main guarantees: The preprocessing is proved well-defined, invariant to column permutation and scaling, and optimal under Donoho–Stodden separability; for exact rank-three matrices, it yields finitely many solutions.

2 Non-Uniqueness, Geometry and Sparsity

NMF has a geometric formulation in which exact factorizations correspond to nested polytopes, clarifying how sparsity can restrict the solution set. The paper derives uniqueness conditions from supports and shows that preprocessing can strengthen well-posedness in specific cases.

  • Geometry and non-uniqueness: When U is rank-deficient, the associated nested polytope has redundant-dimensional structure, allowing infinitely many convex representations for interior points.
  • Geometry and non-uniqueness: Under full-rank conditions, uniqueness is equivalent to the absence of non-monomial transformations preserving nonnegativity and to uniqueness of the corresponding nested-polytope solution.
  • Uniqueness conditions: If r columns of θ(M) coincide with r distinct vertices of the simplex intersected with the column space, the exact NMF is unique.
  • Uniqueness conditions: A column containing r−1 zeros whose corresponding rows have distinct sparsity patterns identifies a vertex of the relevant polytope.
  • Uniqueness conditions: If M has r nonzero columns satisfying that zero-pattern condition and rank(M)=rank+(M)=r, then its NMF is unique.
  • Examples and limits: For 3-by-3 rank-three matrices, the only matrices with a unique exact NMF are monomial matrices; other matrices admit at least two distinct exact factorizations.
  • Sparsity and geometry: Sparser matrices place more data points on the boundary of the outer simplex, reducing the freedom available to construct nested polytopes.
  • Examples and limits: Many zero entries are not necessary for uniqueness, because positive matrices can also have unique NMF; nevertheless, each factor support must avoid containment by another.

3 Preprocessing for More Well-Posed and Sparser NMF

The preprocessing seeks a sparse nonnegative matrix M′=MQ using an inverse-positive Q, so NMF of M′ can be transferred back to M while retaining nonnegativity and controlling approximation error.

  • Preprocessing formulation: The method searches for an inverse-positive matrix Q such that M′=MQ is nonnegative and sparse, making the resulting NMF problem more well posed.The preprocessing is designed to preserve nonnegative factorizability while reducing redundant information in the input matrix.
  • Preprocessing formulation: Any NMF M′≈UV′ of the preprocessed matrix yields an NMF M≈UV of the original matrix with V=V′Q−1≥0.Exactness transfers directly when the NMF of M′ is exact, although the converse need not hold.
  • Preprocessing formulation: The residual satisfies ||M−UV||F≤||M′−UV′||F||Q−1||2, quantifying how preprocessing affects approximation quality.The bound follows by expressing the original residual as the preprocessed residual multiplied by Q−1.
  • Optimization: The optimization replaces the combinatorial ℓ0 objective with an ℓ2-based constrained linear least-squares formulation, while enforcing nonnegativity of MQ and structural constraints on B.Without the spectral-radius constraint, the formulation has O(n^2) variables and O(n^2+mn) constraints.
  • M-matrix restriction: Inverse-positive matrices are difficult to optimize over directly, so the method restricts Q to Z-matrices of the form Q=sI−B with B≥0 and ρ(B)<s.Inverse-positive Z-matrices are M-matrices, which supplies the tractable structural restriction used by the preprocessing.
  • Optimization: Setting s=1 and Q=I−B with zero diagonal yields the restricted feasible set Q_n⊂IP_n used for preprocessing.The normalization fixes scaling freedom, while the diagonal restriction avoids degenerate rescaling of equivalent solutions.
  • Spectral-radius constraint: If columns of M are not mutually proportional, every optimum of the relaxed problem automatically satisfies ρ(B*)<1; repeated columns can instead eliminate components and lower rank.Thus, repetitions in the dataset are the stated setting in which the relaxed approach may fail.

4 Properties of the Preprocessing

The preprocessing operator is well-defined, invariant to column permutation and scaling, and improves NMF identifiability while preserving key rank and factorization properties. Under separability it recovers sparse optimal bases, while rank-three instances have finitely many exact solutions, although symmetry can still produce non-uniqueness.

  • General Properties: The preprocessing operator P is well-defined and preserves the matrix rank while not decreasing nonnegative rank.Its construction also maintains a correspondence between feasible solutions before and after preprocessing.
  • General Properties: P is invariant to permutation and scaling of the columns of M.Equivalently, preprocessing commutes with multiplication by a monomial matrix.
  • General Properties: When columns of θ(M) are distinct, every optimal B* satisfies ρ(B*) < 1, making Q = I − B* inverse-positive.The result follows from the geometry and uniqueness of Euclidean projection onto a convex set.
  • Recovery under Separability: Under separability, preprocessing identifies r columns forming a sparse optimal basis whose normalized convex hull contains conv(θ(M)); for rank two, this basis is always optimal.The result does not require M to be full rank.
  • Uniqueness and Robustness Through Preprocessing: Preprocessing makes the corresponding NMF problem more well posed by reducing allowable solutions while preserving the nonnegative rank.Any NMF of the preprocessed matrix maps to an NMF of M, whereas the converse need not hold.
  • Uniqueness and Robustness Through Preprocessing: Preprocessing improves robustness because exact factors of the preprocessed matrix remain optimal for perturbations E whose column space lies in col(M) and preserve nonnegativity.For positive M and sufficiently small perturbations, the required containment condition holds.
  • Uniqueness and Robustness Through Preprocessing: For rank-three matrices, the preprocessed exact NMF problem has finitely many solutions, with at most m + n solutions under the stated vertex condition.In symmetric examples, preprocessing can reduce a two-dimensional solution set to eight points, but uniqueness is not guaranteed.

5 Preprocessing in Practice

The preprocessing is implemented through independent constrained least-squares problems, with computational cost scaling differently in the matrix dimensions. Practical refinements rescale columns and relax nonnegativity for noisy, sparse inputs while preserving rank when a spectral-radius condition holds.

  • Problem (3.5) decouples into n independent constrained least-squares problems, one for each column of M.
  • O(n^4.5) is the theoretical total computational cost when interior-point methods solve the n subproblems.Each subproblem has n variables and m+n constraints, with complexity O(n^3.5).
  • In practice, computational time is linear in m and of order n^3 in n, below the expected O(n^4.5).The experiments used randomly generated matrices and MATLAB implementations.
  • On a standard machine, n cannot be much larger than 1000, whereas m can be comparatively large; parallel architecture could enable larger problems.
  • Column rescaling matches preprocessed-column norms to the original data, preserving inverse-positivity while giving columns comparable importance in the objective.This is especially relevant when outliers would otherwise receive disproportionate weight.
  • For noisy and sparse inputs, the method relaxes nonnegativity using 0 < ϵ ≪ 1, but requires ρ(B*ϵ) < 1 to preserve rank and recover M.The unrelaxed technique can be sensitive to small positive entries.

6 Application to Image Processing

The image experiments combine preprocessing with standard NMF and compare it against ordinary and sparsity-penalized NMF. Pre-NMF produces sparse, part-based decompositions competitively, with lower initialization sensitivity but substantial preprocessing cost for large datasets.

  • The evaluation compares NMF, Pre-NMF, and sparse NMF using relative error, sparsity, and improved error after fixing the learned zero pattern.All methods use matched initialization and A-HALS-based evaluation procedures.
  • Pre-NMF preprocesses M, factors the rescaled result, and then recomputes V to minimize reconstruction error for the original matrix.Negative entries in the preprocessed matrix are retained to preserve column space and promote sparse NMF solutions.
  • 810 CBCL images required less than three hours of preprocessing, or about 10–15 seconds per image, after retaining every third image from the 2429-image dataset.The full dataset would make preprocessing substantially slower because the cost scales as O(n^4.5).
  • Preprocessing highlights localized facial parts such as eyes, eyebrows, glasses, noses, mouths, and mustaches by removing combinations of other images.Parts that differ substantially from the rest of the dataset are better preserved.
  • Pre-NMF performs competitively with sparse NMF across cases, achieving similar relative error at similar sparsity levels and comparable part-based decompositions.
  • For 100 initializations, Pre-NMF(0.01) had sparsity variance 8.69 10^-7 versus 1.31 10^-3 for sNMF(0.01), indicating lower initialization sensitivity.After removing three sNMF outliers, its sparsity variance remained higher at 3.23 10^-6.

7 Conclusion and Further Research

The paper preprocesses nonnegative data matrices with inverse-positive transformations to make NMF problems more well posed and their solutions sparser. It establishes optimality under separability, finite exact factorizations for rank-three matrices, empirical effectiveness, and a substantial computational-cost limitation.

  • Contribution: The preprocessing computes an inverse-positive Q so P(M)=MQ is sparse and nonnegative, while preserving rank under nonrepeated convex-hull vertices.The approach is well-defined and invariant to column permutation and scaling.
  • Theoretical guarantees: Under Donoho–Stodden separability, preprocessing is optimal because it identifies the vertices of the convex hull of M's columns.This gives the strongest supported optimality guarantee in the conclusion.
  • Theoretical guarantees: Any rank-two matrix satisfies separability, while exact rank-three preprocessing makes the set of optimal NMF solutions finite.The authors conjecture generic uniqueness and extension to higher-rank matrices.
  • Experiments: Experiments on facial and hyperspectral images found the relaxed preprocessing effective, competitive with ℓ1-penalized sparse NMF, and robust to high sparsity.The relaxed method allows nonnegative-input constraints to be loosened, producing sparser preprocessed matrices and NMF solutions.
  • Limitations and further research: O(n^4.5) computational cost limits preprocessing to fewer than 1000 columns for a few hours on a standard laptop.The paper suggests faster solvers and subset-based heuristics as possible remedies; using k columns could reduce complexity to O(nk^3.5).
  • Limitations and further research: The method does not modify some matrices whose NMF is nonunique, motivating broader classes of inverse-positive preprocessing transformations.The authors argue that larger classes could produce sparser data and more well-posed NMF problems.

A Proof for Theorem 9

The proof analyzes how the function f_k changes as a boundary point moves around polygon P. Between contact change points, f_k is either constant or strictly convex, because its construction composes component functions with those properties.

  • Conclusion of proof: The function f_k is continuous and piecewise constant or strictly convex, with changes occurring only at contact change points.This is the central property established by the theorem's proof.
  • Geometric construction: The proof tracks boundary points x(t_i), polygon sides, and intersections with Q, whose changes determine contact change points.The relevant configurations change when a point crosses a vertex of P or a segment intersection with Q changes sides.
  • Geometric construction: There are at most m vertex-related changes from P and at most n side-related changes from Q.P has at most m vertices, while Q has at most n vertices and therefore at most n sides.
  • Piecewise behavior: When q lies on the same side as x(t_1) or x(t_2), f_k is constant until the next contact change point.These are the first two geometric cases in the proof.
  • Piecewise behavior: When q lies in the interior of P, similarity of triangles yields a strictly convex increasing component function.The proof establishes strict convexity through the positivity of the relevant geometric quantities and second derivative.
  • Conclusion of proof: Each component g_i is constant or strictly convex and increasing, so their composition makes f_k constant if any component is constant and strictly convex otherwise.The final expression is f_k(t_1)=c_k+(g_k∘g_{k−1}∘···∘g_1)(t_1).
Loading 1204.2436v1…