Convex and Semi-Nonnegative Matrix Factorizations

article2010TPAMI1,409 citations

Introduces Semi-NMF and Convex-NMF to enable nonnegative matrix factorization on mixed-sign data and kernel spaces while establishing theoretical and practical connections to K-means clustering.

Listen

Organizations frequently analyze complex, high-dimensional datasets such as text, system logs, and scientific measurements to group related items and identify underlying patterns. While standard Nonnegative Matrix Factorization (NMF) offers interpretable, parts-based representations, its practical utility has been restricted because it requires all input data to be strictly nonnegative. Many common analytical workflows, however, rely on centered, normalized, or mixed-sign data where standard NMF fails. The article resolves this limitation by developing and evaluating new matrix factorization frameworks—specifically Semi-NMF and Convex-NMF—that accept mixed-sign data while maintaining the nonnegativity and interpretability of factor outputs.

The research demonstrates that these methods can be computed efficiently through iterative multiplicative updating algorithms with guaranteed convergence to local minima. To evaluate performance and practical utility, the article compares the new methods against standard NMF, traditional Singular Value Decomposition (SVD), and standard K-means clustering across synthetic datasets and seven real-world datasets spanning document collections, system log messages, and physical measurements.

The findings establish three principal results: First, all matrix factorization variants consistently outperformed standard K-means clustering in clustering accuracy across every tested dataset, improving accuracy by roughly 5 to 17 percentage points in real-world scenarios. Second, Semi-NMF and Convex-NMF successfully operated directly on mixed-sign data without requiring artificial data shifting, which was shown to degrade clustering accuracy and sparsity. Third, Convex-NMF naturally produced highly sparse indicator factors (reducing non-zero elements to roughly 49% to 64%) and generated basis factors that closely align with true cluster centroids, unlike Semi-NMF or SVD.

These results provide senior stakeholders and data science teams with more reliable and interpretable alternatives to standard clustering algorithms, especially for non-spherical data clusters where standard K-means fails. Additionally, Convex-NMF enables non-linear "kernelized" factorizations because its updates depend solely on inner products of data points. For operational deployments, technical teams should consider Semi-NMF when raw clustering accuracy on mixed-sign data is paramount, and Convex-NMF when human interpretability, sparsity, and centroid discovery are critical priorities. Future work should explore optimal initialization strategies and broader non-linear kernel applications across large-scale industrial datasets.

Decision-makers should note that, like K-means and Expectation-Maximization algorithms, these multiplicative updates guarantee convergence only to local rather than global optima. Nevertheless, repeated experimental runs demonstrate high stability and consistent clustering results across varied initializations, providing strong confidence in their practical application.

basis vector data points matrix factorizations semi-nonnegative matrix factorization convex non-negative matrix factorization non-negative matrix factorization

Ding et al (2010).pdf

Paper: Algorithms for Non-negative Matrix Factorization, Daniel D. Lee et al. (2000). It introduces the classical non-negative matrix factorization formulation and multiplicative update rules that this paper adapts and generalizes to unconstrained and convex basis settings.
Paper: K-means clustering via principal component analysis, C. Ding et al. (2004). It establishes the foundational theoretical connections between matrix factorizations, low-rank approximations, and continuous relaxations of K-means clustering.
Paper: Kernel k-means: spectral clustering and normalized cuts, Inderjit S. Dhillon et al. (2004). It provides the mathematical equivalence between kernel clustering and spectral graph cuts necessary for understanding how Convex NMF operates in non-linear kernel spaces.
Paper: Document clustering based on non-negative matrix factorization, Wei Xu et al. (2003). It demonstrates how non-negative factor matrices directly provide cluster membership indicators, motivating the semi-nonnegative relaxation for clustering mixed-sign data.
Paper: Concept Decompositions for Large Sparse Text Data Using Clustering, I. Dhillon et al. (2004). It introduces concept decompositions where basis vectors are restricted to convex combinations of data points, directly prefiguring the Convex NMF constraint.
Paper: Non-negative Matrix Factorization with Sparseness Constraints, Patrik O. Hoyer (2004). It formalizes explicit sparsity analysis and constraints in matrix factorization algorithms, providing the baseline context for analyzing solution sparseness.

Paper: Graph Regularized Nonnegative Matrix Factorization for Data Representation, Deng Cai et al. (2011). It extends matrix factorization representations by incorporating graph affinity regularizers to capture manifold geometry alongside parts-based decompositions.
Paper: Online Learning for Matrix Factorization and Sparse Coding, Julien Mairal et al. (2010). It scales matrix factorization and sparse coding formulations, including non-negative variants, to massive streaming datasets via online stochastic optimization.
Paper: Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization, Martin Jaggi (2013). It develops projection-free conditional gradient algorithms for convex and low-rank matrix optimization problems with structured sparsity constraints.

Cover for Convex and Semi-Nonnegative Matrix Factorizations

Abstract

We present several new variations on the theme of nonnegative matrix factorization (NMF). Considering factorizations of the form X = FG^T, we focus on algorithms in which G is restricted to contain nonnegative entries, but allow the data matrix X to have mixed signs, thus extending the applicable range of NMF methods. We also consider algorithms in which the basis vectors of F are constrained to be convex combinations of the data points. This is used for a kernel extension of NMF. We provide algorithms for computing these new factorizations and we provide supporting theoretical analysis. We also analyze the relationships between our algorithms and clustering algorithms, and consider the implications for sparseness of solutions. Finally, we present experimental results that explore the properties of these new methods.

Topics

basis vector data points matrix factorizations non-negative matrix factorization

Keywords

semi-nonnegative matrix factorization convex non-negative matrix factorization non-negative matrix factorization positive matrix factorization spectral clustering singular value decomposition principal component analysis latent Dirichlet allocation EM algorithm

I. Introduction
II. Semi-NMF and Convex-NMF
A. Semi-NMF
B. Convex-NMF
C. An Illustration
III. Algorithms and Analysis
A. Algorithm for Semi-NMF
B. Algorithm for Convex-NMF
C. Some generic properties of NMF algorithms
IV. Sparsity of Convex-NMF
V. Additional Remarks
A. Kernel-NMF
B. Cluster-NMF
C. Relation to relaxed K-means clustering
VI. Experiments
A. Synthetic dataset
B. Real life datasets
C. Shifting mixed-sign data to nonnegative
D. Flexibility of NMF
VII. Conclusions
Acknowledgments
References

Knowls

Knowl 1 — Semi-Nonnegative Matrix Factorization (Semi-NMF)
model/method
Semi-Nonnegative Matrix Factorization (Semi-NMF) is a matrix approximation technique designed for data matrices containing mixed positive and negative values. Given an input matrix $X \in \mathbb{R}^{p \times n}$ , where $p$ is the feature dimension and $n$ is the number of data samples, Semi-NMF factorizes $X$ into a low-rank product:

$X \approx F G^T$

where $F \in \mathbb{R}^{p \times k}$ is an unconstrained basis matrix whose elements may be positive or negative, and $G \in \mathbb{R}^{n \times k}_+$ is an indicator matrix strictly constrained to contain nonnegative entries ( $G_{ik} \ge 0$ ).

The formulation is motivated as a continuous relaxation of $K$ -means clustering. In $K$ -means, data vectors are approximated by cluster centroids $F = (f_1, \dots, f_k)$ with hard binary cluster assignments $G \in \{0, 1\}^{n \times k}$ . Semi-NMF relaxes the discrete assignment constraint to continuous nonnegative memberships $G_{ik} \in [0, \infty)$ , accommodating mixed-sign cluster centroids and soft cluster memberships.

The factorization is computed by minimizing the Frobenius norm squared residual:

$J_{\text{Semi-NMF}} = \|X - F G^T\|^2 = \mathrm{Tr}(X^T X - 2 X^T F G^T + G F^T F G^T) \quad \text{subject to} \quad G \ge 0$

where $\|\cdot\|$ denotes the matrix Frobenius norm and $\mathrm{Tr}(\cdot)$ denotes the matrix trace.
Knowl 2 — Convex Nonnegative Matrix Factorization (Convex-NMF)
model/method
Convex Nonnegative Matrix Factorization (Convex-NMF) constrains the basis vectors $F = (f_1, \dots, f_k) \in \mathbb{R}^{p \times k}$ of a matrix factorization $X \approx F G^T$ to lie within the subspace spanned by the columns of the input data matrix $X \in \mathbb{R}^{p \times n}$ , specifically as nonnegative convex combinations of the data samples:

$f_\ell = \sum_{i=1}^n X_i W_{i\ell} = X w_\ell \quad \Longleftrightarrow \quad F = X W$

where $W \in \mathbb{R}^{n \times k}_+$ is a nonnegative weight matrix ( $W_{i\ell} \ge 0$ ) and $w_\ell$ is its $\ell$ -th column vector.

The complete factorization model is defined as:

$X \approx X W G^T$

where $X \in \mathbb{R}^{p \times n}$ can have mixed signs or be purely nonnegative, $W \in \mathbb{R}^{n \times k}_+$ , and $G \in \mathbb{R}^{n \times k}_+$ is the cluster indicator matrix ( $G_{ik} \ge 0$ ).

The factor matrices are estimated by solving:

$J_{\text{Convex-NMF}} = \|X - X W G^T\|^2 = \mathrm{Tr}(X^T X - 2 G^T X^T X W + W^T X^T X W G^T G) \quad \text{subject to} \quad W \ge 0, \, G \ge 0$

where $\|\cdot\|$ is the Frobenius norm. Restricting basis vectors to convex combinations of data points ensures that the basis vectors capture centroid-like representations and naturally drives both factor matrices $W$ and $G$ toward sparse solutions.
Knowl 3 — Alternating Multiplicative Optimization Algorithm for Semi-NMF
algorithm
Semi-NMF minimizes $J = \|X - F G^T\|^2$ subject to $G \ge 0$ , where $X \in \mathbb{R}^{p \times n}$ , $F \in \mathbb{R}^{p \times k}$ , and $G \in \mathbb{R}^{n \times k}_+$ . For any matrix $A$ , its positive and negative components are separated as $A^+ = (|A| + A)/2$ and $A^- = (|A| - A)/2$ , such that $A = A^+ - A^-$ and $A^+, A^- \ge 0$ .
Input: Data matrix $X \in \mathbb{R}^{p \times n}$ , rank $k$ , maximum iterations $m$
Output: Unconstrained basis matrix $F \in \mathbb{R}^{p \times k}$ , nonnegative indicator matrix $G \in \mathbb{R}^{n \times k}_+$
Initialize $G$ by performing K-means clustering on $X$ to obtain cluster indicators $H \in \{0, 1\}^{n \times k}$
$G \leftarrow H + 0.2 E$ , where $E \in \mathbb{R}^{n \times k}$ is a matrix of all ones
for iteration $= 1$ to $m$ do
     $F \leftarrow X G (G^T G)^{-1}$
    for $i = 1$ to $n$ and $j = 1$ to $k$ do
         $G_{ij} \leftarrow G_{ij} \sqrt{\frac{(X^T F)^+_{ij} + [G (F^T F)^-]_{ij}}{(X^T F)^-_{ij} + [G (F^T F)^+]_{ij}}}$
    end for
end for
return $F, G$
The update for $F$ is the closed-form global minimizer for fixed $G$ ; if $G^T G$ is singular, the Moore-Penrose pseudoinverse is utilized. The multiplicative update for $G$ ensures monotonic non-increase of the residual error $\|X - F G^T\|^2$ and converges to a Karush-Kuhn-Tucker (KKT) stationary point. The computational complexity is $O(m(pnk + nk^2))$ for updating $F$ and $O(m(npk + k p^2 + n^2 k))$ for updating $G$ , with $m \approx 100$ iterations typically required for convergence.
Knowl 4 — Alternating Multiplicative Optimization Algorithm for Convex-NMF
algorithm
Convex-NMF solves $\min_{W \ge 0, G \ge 0} \|X - X W G^T\|^2$ for a data matrix $X \in \mathbb{R}^{p \times n}$ , combination matrix $W \in \mathbb{R}^{n \times k}_+$ , and cluster indicator matrix $G \in \mathbb{R}^{n \times k}_+$ . The positive and negative decompositions are defined by $A^+ = (|A| + A)/2$ and $A^- = (|A| - A)/2$ .
Input: Data matrix $X \in \mathbb{R}^{p \times n}$ , rank $k$ , maximum iterations $m$
Output: Nonnegative combination matrix $W \in \mathbb{R}^{n \times k}_+$ , nonnegative indicator matrix $G \in \mathbb{R}^{n \times k}_+$
Initialize $G$ and $W$ from K-means:
    Run K-means on $X$ to get indicators $H \in \{0, 1\}^{n \times k}$ and cluster sizes $n_1, \dots, n_k$
     $D_n \leftarrow \text{diag}(n_1, \dots, n_k)$
     $G \leftarrow H + 0.2 E$ , where $E \in \mathbb{R}^{n \times k}$ is a matrix of all ones
     $W \leftarrow (H + 0.2 E) D_n^{-1}$
for iteration $= 1$ to $m$ do
    for $i = 1$ to $n$ and $j = 1$ to $k$ do
         $G_{ij} \leftarrow G_{ij} \sqrt{\frac{[(X^T X)^+ W]_{ij} + [G W^T (X^T X)^- W]_{ij}}{[(X^T X)^- W]_{ij} + [G W^T (X^T X)^+ W]_{ij}}}$
    end for
    for $i = 1$ to $n$ and $j = 1$ to $k$ do
         $W_{ij} \leftarrow W_{ij} \sqrt{\frac{[(X^T X)^+ G]_{ij} + [(X^T X)^- W G^T G]_{ij}}{[(X^T X)^- G]_{ij} + [(X^T X)^+ W G^T G]_{ij}}}$
    end for
end for
return $W, G$
Alternatively, if an existing Semi-NMF solution $(F, G)$ is available, $G$ is initialized as $G + 0.2E$ and $W$ is initialized as $W^+ + 0.2E \langle W^+ \rangle$ , where $W = G(G^T G)^{-1}$ and $\langle A \rangle = \sum_{ij} |A_{ij}| / \|A\|_0$ . The alternating update rules guarantee monotonic descent of $\|X - X W G^T\|^2$ toward a KKT fixed point. Precomputing $X^T X$ requires $O(n^2 p)$ operations; per iteration, updating $G$ costs $O(2 n^2 k + n k^2)$ and updating $W$ costs $O(2 n^2 k + 2 n k^2)$ across $m \approx 100$ iterations.
Knowl 5 — Intrinsic Sparsity of Convex-NMF via Spectral Projection
theoretical result
Convex-NMF factors $W \in \mathbb{R}^{n \times k}_+$ and $G \in \mathbb{R}^{n \times k}_+$ naturally converge to highly sparse representations without explicit $\ell_1$ or sparsity penalty terms.

Let $X = U \Sigma V^T$ be the singular value decomposition of $X \in \mathbb{R}^{p \times n}$ , where $X^T X = \sum_i \sigma_i^2 v_i v_i^T$ . The Convex-NMF optimization problem can be reformulated as:

$\min_{W \ge 0, \, G \ge 0} \|X - X W G^T\|^2 = \min_{W \ge 0, \, G \ge 0} \sum_{i} \sigma_i^2 \|v_i^T (I - W G^T)\|^2$

For the unweighted identity matrix approximation $\min_{W \ge 0, G \ge 0} \|I - W G^T\|^2$ with $W, G \in \mathbb{R}^{n \times K}_+$ , the exact global minimizers under nonnegativity constraints are $W = G = \text{any } K \text{ distinct columns of } (e_1, \dots, e_n)$ , where $e_k$ are the standard basis vectors. These solutions are the sparsest possible rank- $K$ nonnegative matrices.

In Convex-NMF, the singular values $\sigma_i^2$ act as weights across principal components:
1. The projection of $(I - W G^T)$ onto leading principal components (large $\sigma_i$ ) is heavily penalized, strongly enforcing sparsity in the principal subspace.
2. The slower the singular values $\sigma_i$ decrease, the sparser the resulting factor matrices $W$ and $G$ .
3. When $n > p$ , Convex-NMF has $2kn$ parameters whereas Semi-NMF has $kp + kn$ parameters. Because Convex-NMF is a constrained specialization of Semi-NMF, the apparent overparameterization is resolved by driving a large proportion of the entries in $W$ and $G$ to zero.
Knowl 6 — Kernel Nonnegative Matrix Factorization (Kernel-NMF)
model/method
Let $\phi: \mathbb{R}^p \to \mathcal{H}$ map input data points into an implicit, potentially infinite-dimensional Hilbert feature space $\mathcal{H}$ , forming the mapped data matrix $\phi(X) = (\phi(x_1), \dots, \phi(x_n))$ . Standard NMF and Semi-NMF cannot be computed directly in $\mathcal{H}$ because the basis factors depend explicitly on the mapped coordinates. Convex-NMF enables kernelization by expressing the basis factors as convex combinations of mapped data samples:

$\phi(X) \approx \phi(X) W G^T$

with $W \in \mathbb{R}^{n \times k}_+$ and $G \in \mathbb{R}^{n \times k}_+$ .

The reconstruction error objective depends entirely on inner products via the kernel Gram matrix $K = \phi(X)^T \phi(X) \in \mathbb{R}^{n \times n}$ where $K_{ij} = \langle \phi(x_i), \phi(x_j) \rangle$ :

$J_{\text{Kernel-NMF}} = \|\phi(X) - \phi(X) W G^T\|^2 = \mathrm{Tr}(K - 2 G^T K W + W^T K W G^T G)$

The multiplicative updates for Kernel-NMF are computed directly using $K$ :

$G_{ik} \leftarrow G_{ik} \sqrt{\frac{[K^+ W]_{ik} + [G W^T K^- W]_{ik}}{[K^- W]_{ik} + [G W^T K^+ W]_{ik}}}$

$W_{ik} \leftarrow W_{ik} \sqrt{\frac{[K^+ G]_{ik} + [K^- W G^T G]_{ik}}{[K^- G]_{ik} + [K^+ W G^T G]_{ik}}}$

where $K^+ = (|K| + K)/2$ and $K^- = (|K| - K)/2$ . This formulation extends nonnegative matrix factorization to nonlinear subspaces in exact analogy to Kernel PCA and Kernel $K$ -means.
Knowl 7 — Cluster Nonnegative Matrix Factorization (Cluster-NMF)
model/method
Cluster Nonnegative Matrix Factorization (Cluster-NMF) is a compact factorization model parameterized entirely by a single nonnegative cluster indicator matrix $G \in \mathbb{R}^{n \times k}_+$ .

In Convex-NMF, when $G$ represents posterior cluster probabilities, the cluster centroids can be written as $f_k = X g_k / n_k$ , where $n_k$ is the number of points in cluster $k$ , giving $F = X G D_n^{-1}$ with $D_n = \text{diag}(n_1, \dots, n_k)$ . Substituting this into $X \approx F G^T$ yields $X \approx X G D_n^{-1} G^T$ . Absorbing the diagonal normalization $D_n^{-1/2}$ directly into $G$ produces the model:

$X \approx X G G^T$

where $G \in \mathbb{R}^{n \times k}_+$ with $G_{ik} \ge 0$ .

The objective function is the Frobenius norm squared reconstruction error:

$J_{\text{Cluster-NMF}} = \|X - X G G^T\|^2 = \mathrm{Tr}(X^T X - 2 G^T X^T X G + G^T X^T X G G^T G) \quad \text{subject to} \quad G \ge 0$

By eliminating the auxiliary basis matrix $F$ and combination weights $W$ , Cluster-NMF directly optimizes cluster indicators within a unified matrix factorization framework.
Knowl 8 — Equivalence of Orthogonally Constrained NMF Variants to K-Means Clustering
theoretical result
When the cluster indicator matrix $G \in \mathbb{R}^{n \times k}_+$ is constrained to be orthogonal ( $G^T G = I$ ), Nonnegative Matrix Factorization (NMF), Semi-NMF, Convex-NMF, Cluster-NMF, and Kernel-NMF are all mathematically equivalent relaxations of $K$ -means clustering.

Because nonnegativity ( $G \ge 0$ ) and orthogonality ( $G^T G = I$ ) together force each row of $G$ to contain exactly one nonzero entry, $G$ behaves as a strict discrete cluster assignment matrix:
1. For NMF, Semi-NMF, and Convex-NMF, optimizing over $F$ yields $F = X G$ . Substituting $F$ into $\|X - F G^T\|^2$ gives $J = \mathrm{Tr}(X^T X - G^T X^T X G)$ .
2. For Cluster-NMF, $\|X - X G G^T\|^2$ simplifies directly to $\mathrm{Tr}(X^T X - G^T X^T X G)$ when $G^T G = I$ .
3. For Kernel-NMF with kernel matrix $K = \phi(X)^T \phi(X)$ , setting $\partial J / \partial W = 0$ yields $K G = K W$ , reducing the objective to $J = \mathrm{Tr}(K - G^T K G)$ .
In all five formulations, minimizing the reconstruction error under $G^T G = I$ reduces to the trace maximization:

$\max_{G \ge 0, \, G^T G = I} \mathrm{Tr}(G^T K G)$

where $K = X^T X$ for linear factorizations or $K = \phi(X)^T \phi(X)$ for Kernel-NMF. This trace maximization is identical to standard (and kernel) $K$ -means clustering. When the orthogonality constraint $G^T G = I$ is removed, these NMF variants function as soft, continuous relaxations of $K$ -means clustering.

Knowl 9 — Benchmark Comparison of Clustering Accuracy, Factor Sparsity, and Orthogonality

data/table

Clustering accuracy, sparsity of $G$ , and deviation from orthogonality were evaluated across seven benchmark datasets: five nonnegative document/log corpora (Reuters, URCS, WebKB4, Log, WebAce) and two mixed-sign datasets from the UCI repository (Ionosphere, Wave). Results are averages over 10 runs per algorithm. Accuracy is measured using ground-truth class labels by computing the confusion matrix and optimizing the diagonal permutation sum. Sparsity of $G$ is the percentage of elements $\ge 0.001 \times (\text{column mean})$ , where lower values indicate greater sparsity. Deviation from orthogonality is the average off-diagonal element of $D^{-1/2} (G^T G) D^{-1/2}$ where $D = \text{diag}(G^T G)$ .

Dataset	Reuters	URCS	WebKB4	Log	WebAce	Ionosphere	Wave
Data sign	$+$	$+$	$+$	$+$	$+$	$\pm$	$\pm$
Instances ( $n$ )	2900	476	4199	1367	2340	351	5000
Classes ( $k$ )	10	4	4	9	20	2	2
Clustering Accuracy
K-means	0.4448	0.4250	0.3888	0.6876	0.4001	0.4217	0.5018
NMF	0.4947	0.5713	0.4218	0.7805	0.4761	–	–
Semi-NMF	0.4867	0.5628	0.4378	0.7385	0.4162	0.5947	0.5896
Convex-NMF	0.4789	0.5340	0.4358	0.7257	0.4086	0.5470	0.5738
Sparsity (% non-zeros in $G$ , lower is sparser)
Semi-NMF	0.9720	0.9688	0.9993	0.9104	0.9543	0.8177	0.9747
Convex-NMF	0.6152	0.6448	0.5976	0.5070	0.6427	0.4986	0.4861
Deviation from Orthogonality
Semi-NMF	0.6578	0.5527	0.7785	0.5924	0.7253	0.9069	0.5461
Convex-NMF	0.1979	0.1948	0.1146	0.4815	0.5072	0.1604	0.2793

The empirical findings demonstrate:

All matrix factorization models outperform $K$ -means clustering across all seven datasets.
On nonnegative data, standard NMF produces slightly higher accuracy, while Semi-NMF and Convex-NMF yield competitive performance with enhanced centroid interpretability.
On mixed-sign datasets where standard NMF cannot run, Semi-NMF and Convex-NMF achieve strong accuracy ( $0.5470$ -- $0.5947$ ).
Convex-NMF produces significantly sparser indicators ( $48.61$ %-- $64.48$ % non-zeros vs. $81.77$ %-- $99.93$ % for Semi-NMF) and markedly lower deviation from orthogonality ( $0.1146$ -- $0.5072$ vs. $0.5461$ -- $0.9069$ ), indicating sharp, near-disjoint cluster assignments.

Knowl 10 — Performance Degradation from Nonnegative Shifting of Mixed-Sign Data
empirical result
To apply standard nonnegative factorization methods to mixed-sign data $X \in \mathbb{R}^{p \times n}$ , a common heuristic is to shift all data entries by adding a constant scalar $c = |\min_{ij} X_{ij}|$ so that all matrix entries become nonnegative ( $X + c E \ge 0$ ).

Empirical evaluation demonstrates that shifting mixed-sign data leads to notable degradation in clustering accuracy and factor sparsity compared to directly applying Semi-NMF and Convex-NMF to the unshifted data:
- Wave dataset ( $n = 5000, k = 2$ ):
  - Semi-NMF clustering accuracy drops from $0.590$ (unshifted) to $0.503$ (shifted).
  - Convex-NMF clustering accuracy drops from $0.5738$ (unshifted) to $0.5297$ (shifted).
  - Convex-NMF factor density (percentage of nonzero elements in $G$ ) worsens from $0.4861$ ( $48.61\%$ ) to $0.586$ ( $58.6\%$ ).
- Ionosphere dataset ( $n = 351, k = 2$ ):
  - Semi-NMF clustering accuracy drops from $0.729$ (unshifted) to $0.647$ (shifted).
  - Convex-NMF clustering accuracy drops from $0.6877$ (unshifted) to $0.618$ (shifted).
  - Convex-NMF factor density worsens from $0.498$ ( $49.8\%$ ) to $0.829$ ( $82.9\%$ ).
Shifting mixed-sign data matrices introduces artificial distortion, confirming the utility of direct Semi-NMF and Convex-NMF formulations for unshifted mixed-sign data.

Coverage note — Derivations and proofs of convergence theorems and auxiliary functions (Theorems 1, 6 and Propositions 2–5, 7–8) were omitted per instructions; qualitative 2D and 3D synthetic visual demonstrations (Figures 1 and 2) were omitted in favor of the complete benchmark table.

References

1.D. Lee and H. S. Seung, “Learning the parts of objects by non-negative matrix factorization,” Nature, vol. 401, pp. 788–791, 1999.
2.——, “Algorithms for non-negative matrix factorization,” in Advances in Neural Information Processing Systems 13. Cambridge, MA: MIT Press, 2001.
3.P. Paatero and U. Tapper, “Positive matrix factorization: A non-negative factor model with optimal utilization of error estimates of data values,” Environmetrics, vol. 5, pp. 111–126, 1994.
4.Y.-L. Xie, P. Hopke, and P. Paatero, “Positive matrix factorization applied to a curve resolution problem,” Journal of Chemometrics, vol. 12, no. 6, pp. 357–364, 1999.
5.S. Li, X. Hou, H. Zhang, and Q. Cheng, “Learning spatially localized, parts-based representation,” in Proc. IEEE Conf. Computer Vision and Pattern Recognition, 2001, pp. 207–212.
6.M. Cooper and J. Foote, “Summarizing video using non-negative similarity matrix factorization,” in Proc. IEEE Workshop on Multimedia Signal Processing, 2002, pp. 25–28.
7.W. Xu, X. Liu, and Y. Gong, “Document clustering based on non-negative matrix factorization,” in Proc. ACM Conf. Research development in IR(SIRGIR), 2003, pp. 267–273.
8.V. P. Pauca, F. Shahnaz, M. Berry, and R. Plemmons, “Text mining using non-negative matrix factorization,” in Proc. SIAM Int'l conf on Data Mining, 2004, pp. 452–456.
9.J.-P. Brunet, P. Tamayo, T. Golub, and J. Mesirov, “Metagenes and molecular pattern discovery using matrix factorization,” Proc. Nat'l Academy of Sciences USA, vol. 102, no. 12, pp. 4164–4169, 2004.
10.H. Kim and H. Park, “Sparse non-negative matrix factorizations via alternating nonnegativity-constrained least squares for microarray data analysis,” Bioinformatics, vol. 23, no. 12, pp. 1495–1502, 2007.
11.D. Greene, G. Cagney, N. Krogan, and P. Cunningham, “Ensemble non-negative matrix factorization methods for clustering protein-protein interactions,” Bioinformatics, vol. 24, no. 15, pp. 1722–1728, 2008.
12.I. Dhillon and S. Sra, “Generalized nonnegative matrix approximations with Bregman divergences,” in Advances in Neural Information Processing Systems 17. MIT Press, 2005.
13.C. Ding, T. Li, and W. Peng, “Nonnegative matrix factorization and probabilistic latent semantic indexing: Equivalence, chi-square statistic, and a hybrid method,” Proc. National Conf. Artificial Intelligence, 2006.
14.F. Sha, L. K. Saul, and D. D. Lee, “Multiplicative updates for nonnegative quadratic programming in support vector machines,” in Advances in Neural Information Processing Systems 15. Cambridge, MA: MIT Press, 2003.
15.N. Srebro, J. Rennie, and T. Jaakkola, “Maximum margin matrix factorization,” in Advances in Neural Information Processing Systems. Cambridge, MA: MIT Press, 2005.
16.P. O. Hoyer, “Non-negative matrix factorization with sparseness constraints,” J. Machine Learning Research, vol. 5, pp. 1457–1469, 2004.
17.M. Berry, M. Browne, A. Langville, P. Pauca, and R. Plemmons, “Algorithms and applications for approximate nonnegative matrix factorization,” To Appear in Computational Statistics and Data Analysis, 2006.
18.T. Li and S. Ma, “IFD: Iterative feature and data clustering,” in Pro. SIAM Int'l conf. on Data Mining (SDM 2004), 2004, pp. 472–476.
19.T. Li, “A general model for clustering binary data.” in KDD, 2005, pp. 188–197.
20.C. Ding, X. He, and H. Simon, “On the equivalence of nonnegative matrix factorization and spectral clustering.” Proc. SIAM Data Mining Conf, 2005.
21.E. Gaussier and C. Goutte, “Relation between PLSA and NMF and implications,” in Proc. of ACM SIGIR conference. New York, NY, USA: ACM Press, 2005, pp. 601–602.
22.T. Hofmann, “Probabilistic latent semantic indexing,” in Proceedings of ACM Conf. on Research and Development in Information Retrieval (SIGIR), 1999, pp. 50–57.
23.D. Blei, A. Ng, and M. Jordan, “Latent Dirichlet allocation,” Journal of Machine Learning Research, vol. 3, pp. 993–1022, 2003.
24.M. Girolami and K. Kaban, “On an equivalence between PLSI and LDA,” Proc. ACM Conf. Research and Develop. Info. Retrieval (SIGIR), 2003.
25.D. Lee and H. S. Seung, “Unsupervised learning by convex and conic coding,” in Advances in Neural Information Processing Systems 9. Cambridge, MA: MIT Press, 1997.
26.L. Xu and M. Jordan, “On convergence properties of the EM algorithm for gaussian mixtures,” Neural Computation, pp. 129–151, 1996.
27.C. Boutsidis and E. Gallopoulos, “SVD based initialization: A head start for nonnegative matrix factorization,” Pattern Recogn., vol. 41, no. 4, pp. 1350–1362, 2008.
28.D. Donoho and V. Stodden, “When does non-negative matrix factorization give a correct decomposition into parts?” in Advances in Neural Information Processing Systems 16. Cambridge, MA: MIT Press, 2004.
29.A. D’Aspremont, L. E. Ghaoui, M. I. Jordan, and G. R. G. Lanckriet, “A direct formulation for sparse PCA using semidefinite programming,” to appear in SIAM Review, 2006.
30.H. Zou, T. Hastie, and R. Tibshirani, “Sparse principal component analysis,” J. Computational and Graphical Statistics, vol. 15, pp. 265–286, 2006.
31.Z. Zhang, H. Zha, and H. Simon, “Low-rank approximations with sparse factors II: Penalized methods with discrete Newton-like iterations,” SIAM J. Matrix Analysis Applications, vol. 25, pp. 901–920, 2004.
32.H. Zha, C. Ding, M. Gu, X. He, and H. Simon, “Spectral relaxation for K-means clustering,” Advances in Neural Information Processing Systems 14 (NIPS’01), pp. 1057–1064, 2002.
33.C. Ding and X. He, “K-means clustering and principal component analysis,” Int’l Conf. Machine Learning (ICML), 2004.

Citation

MLA

Ding, C. H. Q., et al. “Convex and Semi-Nonnegative Matrix Factorizations”. IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 32, no. 1, 2010, pp. 45–55, https://doi.org/10.1109/TPAMI.2008.277.

APA

Ding, C. H. Q., Tao Li, & Jordan, M. I. (2010). Convex and Semi-Nonnegative Matrix Factorizations. IEEE Transactions on Pattern Analysis and Machine Intelligence, 32(1), 45–55. https://doi.org/10.1109/TPAMI.2008.277

Chicago

Ding, C. H. Q., Tao Li, and M. I. Jordan. 2010. “Convex and Semi-Nonnegative Matrix Factorizations”. IEEE Transactions on Pattern Analysis and Machine Intelligence 32 (1): 45–55. https://doi.org/10.1109/TPAMI.2008.277.

Harvard

Ding, C.H.Q., Tao Li and Jordan, M.I. (2010) “Convex and Semi-Nonnegative Matrix Factorizations”, IEEE Transactions on Pattern Analysis and Machine Intelligence, 32(1), pp. 45–55. Available at: https://doi.org/10.1109/TPAMI.2008.277.

Vancouver

1. Ding CHQ, Tao Li, Jordan MI (2010) Convex and Semi-Nonnegative Matrix Factorizations. IEEE Transactions on Pattern Analysis and Machine Intelligence 32:45–55

BibTeX

@article{Ding_2010, title={Convex and Semi-Nonnegative Matrix Factorizations}, volume={32}, ISSN={0162-8828}, url={http://dx.doi.org/10.1109/TPAMI.2008.277}, DOI={10.1109/tpami.2008.277}, number={1}, journal={IEEE Transactions on Pattern Analysis and Machine Intelligence}, publisher={Institute of Electrical and Electronics Engineers (IEEE)}, author={Ding, C.H.Q. and Tao Li and Jordan, M.I.}, year={2010}, month=Jan, pages={45–55} }

Metadata:Crossref

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

Convex and Semi-Nonnegative Matrix Factorizations

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Semi-Nonnegative Matrix Factorization (Semi-NMF)

Knowl 2 — Convex Nonnegative Matrix Factorization (Convex-NMF)

Knowl 3 — Alternating Multiplicative Optimization Algorithm for Semi-NMF

Knowl 4 — Alternating Multiplicative Optimization Algorithm for Convex-NMF

Knowl 5 — Intrinsic Sparsity of Convex-NMF via Spectral Projection

Knowl 6 — Kernel Nonnegative Matrix Factorization (Kernel-NMF)

Knowl 7 — Cluster Nonnegative Matrix Factorization (Cluster-NMF)

Knowl 8 — Equivalence of Orthogonally Constrained NMF Variants to K-Means Clustering

Knowl 9 — Benchmark Comparison of Clustering Accuracy, Factor Sparsity, and Orthogonality

Knowl 10 — Performance Degradation from Nonnegative Shifting of Mixed-Sign Data

References

Citation

BibTeX

Access the Paper