Averaged Templates and the All-or-Nothing Cliff in Sparse Non-Negative Factorization

Non-negative matrix factorization (NMF) explains a data matrix of energies, counts or intensities as a sum of a few non-negative "parts." Examples are the spectral template of a note times its on/off pattern in time, or a facial feature times the images it appears in. Practitioners know a failure mode well. On hard, noisy problems, NMF often returns components that are blurred averages of the true parts rather than garbage. Separately, theorists have found an all-or-nothing phase transition in sparse high-dimensional estimation. Below a critical signal-to-noise ratio (SNR), the best possible estimator learns essentially nothing. Just above it, the estimator recovers essentially everything. This proposal argues that the two phenomena are the same thing, seen from different sides.

We claim that non-negativity splits recovery into two channels. The first is an aggregate channel: the total energy, which comes from the strictly positive mean of the factors. It is recovered smoothly at low SNR. The second is a parts channel: which component is which. It keeps an all-or-nothing cliff. Efficient algorithms, pulled by the positive mean, do not stall at the zero solution as they do in sign-symmetric problems. They stall at a fixed point where all components equal the averaged template. We call this the permutation-symmetric fixed point, since it treats every component identically. That fixed point is the blurred-template failure. We will derive both thresholds for a doubly non-negative, asymmetric model, prove the parts cliff in a restricted regime, and test whether standard NMF solvers fall into the same trap.

Core Claim and Why It Is Not Already Done

The model is

$$V = \sqrt{\lambda/n}\, W H + Z,$$

where $W \in \mathbb{R}_{\ge 0}^{F\times K}$ and $H \in \mathbb{R}_{\ge 0}^{K\times T}$ have i.i.d. Bernoulli–exponential entries (nonzero with probability $\rho_W$ or $\rho_H$, going to zero). Here $Z$ is Gaussian noise, $\lambda$ is the SNR, $K$ is fixed, and $F, T, n \to \infty$ at fixed aspect ratios.

Write $\bar W, \bar H$ for the entrywise means. Then $WH$ splits into a rank-one mean term $\bar W \bar H\, \mathbf{1}\mathbf{1}^\top$-type component plus a centered rank-$K$ remainder. The mean term carries the aggregate. The remainder carries the identity of the parts, up to the permutation symmetry among the $K$ components.

Our prediction has three parts. First, the aggregate is estimable with smoothly decaying error once $\lambda$ exceeds a spectral level. Second, the parts have normalized minimum mean-squared error (MMSE) that jumps from 1 to 0 at an information-theoretic threshold $\lambda_{\text{it}}$. We expect this threshold to scale like the sparse spiked thresholds, of order $|\ln\rho|/\rho$. Third, message passing leaves the permutation-symmetric fixed point only above a much larger $\lambda_{\text{alg}}$.

The closest work each covers only a piece of this.

All-or-nothing statistical and computational phase transitions in sparse spiked matrix estimation proves the cliff at $\lambda \approx 4|\ln\rho|/\rho$ and the message-passing threshold $\lambda \approx 1/(e\rho^2)$ for a symmetric rank-one spike. That paper already includes a non-negative Bernoulli prior. This matters: it tells us non-negativity alone does not destroy the cliff at rank one. Our contribution is the rank-$K$, asymmetric case, where the positive means of $K$ components stack into a shared direction. That creates the aggregate/parts split and the symmetric trap, neither of which exists at rank one.

Phase Transitions in Sparse PCA observes that non-zero-mean signals have no undetectable phase. This appears to contradict the cliff. We reconcile the two: detection becomes easy, but identification of the parts does not.

Nonnegative Sparse PCA with Provable Guarantees shows non-negative PCA is NP-hard through copositivity. That is a worst-case statement. Our average-case analysis says where the hardness actually sits in a planted model.

Subspace clustering in high-dimensions and Low-rank matrix reconstruction and clustering via approximate message passing study low-rank factorization with one-hot or sparse centroids. Neither constrains both factors to be non-negative.

Sparse nonnegative deconvolution for compressive calcium imaging studies convex conic phase transitions, not the MMSE cliff, and treats the NMF step heuristically.

The file thus motivates a resolution of an open tension. Lesieur et al. suggest that the positive mean helps algorithms. Asteris et al. suggest that non-negativity adds hardness. Our split predicts both are right, about different channels.

Research Program

The analysis uses approximate message passing (AMP), an iterative algorithm whose error at each step is tracked exactly in high dimensions by a scalar recursion called state evolution. It also uses the replica method from statistical physics, which computes limiting mutual information.

The theoretical part has three pieces. First, we write the replica-symmetric free energy and the state evolution for the model above, using the bilinear message-passing algorithm BiG-AMP from Bilinear Generalized Approximate Message Passing with non-negative scalar priors. We parameterize the overlaps so that the mean direction and the centered permutation-breaking directions are tracked separately. This separation is what makes the permutation-symmetric fixed point visible as a distinct solution of state evolution, rather than something averaged away.

Second, we attempt a rigorous proof of the parts cliff for fixed $K$ and sublinear sparsity. The route combines the I-MMSE relation with the adaptive interpolation used in the rank-one sparse spiked paper, extended to rectangular spikes, and with the area-theorem argument of The All-or-Nothing Phenomenon in Sparse Linear Regression. Where rigor stalls, we state the result as a replica prediction and check it numerically.

Third, we compare one-sided priors against sign-symmetric priors with the same sparsity. This comparison measures whether non-negativity changes $\lambda_{\text{it}}$ or $\lambda_{\text{alg}}$ beyond a lower-order correction. We expect little change to $\lambda_{\text{it}}$ as $\rho \to 0$, because the centering shift is of order $\rho$. We expect the main effect to be on which fixed point traps the algorithm.

The empirical part checks that these asymptotic statements describe what practitioners actually run: Lee–Seung multiplicative updates from Algorithms for Non-negative Matrix Factorization and alternating non-negative least squares, at finite sizes and with structured dictionaries.

Baselines

The naive reference is the trivial estimator that outputs the prior mean. By construction it has parts-MMSE equal to 1, and it defines the "nothing" level.

A second weak reference is truncated singular value decomposition: take the top-$K$ singular vectors, flip signs to maximize positivity, and zero out negative entries. It is run on identical matrices with no tuning beyond sign choice. Beating it means lower parts-MSE at matched $\lambda$.

The practical competitors are Lee–Seung multiplicative updates, with Frobenius loss per Algorithms for Non-negative Matrix Factorization, and alternating non-negative least squares. Each gets the same number of random restarts and the same wall-clock budget as our message-passing runs, and the best restart is selected by reconstruction loss, never by ground truth.

The strongest existing method is BiG-AMP with non-negative priors and its expectation-maximization wrapper, which tunes prior and noise parameters, from Bilinear Generalized Approximate Message Passing. Its parametric variant, Parametric Bilinear Generalized Approximate Message Passing, reports empirical recovery down to the counting bound $M \approx 2K$ in blind deconvolution. On related real data, AMP-based clustering beat K-means++ in loss in 48 of 50 ORL face trials, as reported in Low-rank matrix reconstruction and clustering via approximate message passing. No reported result was found on Lacuna for BiG-AMP's MMSE-versus-SNR curve on sparse doubly non-negative factorization. Our own runs of it are therefore the reference.

Our methodological claim is not to beat BiG-AMP. The claim is to predict exactly where it fails and why. The test is whether its empirical transition sits at our predicted $\lambda_{\text{alg}}$ within finite-size error, and whether its failed runs sit at the permutation-symmetric fixed point.

The key ablation isolates the mean. We run BiG-AMP with a sign-symmetric Bernoulli–Laplace prior of matched sparsity and variance on data generated from the same prior. We also run it on non-negative data after subtracting the empirical rank-one mean. If the aggregate/parts split is real, the centered run shows the classical zero fixed point instead of the averaged-template fixed point. It should also have a comparable parts threshold.

A second ablation initializes BiG-AMP with a small oracle overlap in the centered directions only. If state evolution is right, this should let it escape the symmetric trap below $\lambda_{\text{alg}}$ but above $\lambda_{\text{it}}$.

Why not just…?

Why not just subtract the mean and reuse known sparse PCA theory? This is the most serious alternative, and we expect it to be partly correct. Our own prediction is that, as $\rho \to 0$, the parts threshold matches that of the centered problem. If the centered-ablation experiment confirms this, then for the information-theoretic question, non-negativity is simply "a mean plus a known problem." That is a useful negative result against the belief that non-negativity makes sparse recovery statistically easier. What centering does not give is the rectangular rank-$K$ doubly-sparse threshold. Phase Transitions in Sparse PCA treats symmetric models. Nor does centering explain what uncentered solvers actually converge to. The ablation settles how much of the proposal survives this objection.

Why not just use multiplicative updates with many restarts? Restarts help only if some basin reaches the planted solution in feasible time. Our state evolution predicts that between $\lambda_{\text{it}}$ and $\lambda_{\text{alg}}$ the averaged-template basin dominates. We test this directly by tracking the fraction of restarts that exceed a parts-overlap threshold as $n$ grows at fixed $\lambda$. Under our hypothesis this fraction shrinks with $n$. If it does not shrink, our hardness claim is wrong for these solvers.

Why not use convex relaxation with nuclear norm plus $\ell_1$? Parametric Bilinear Generalized Approximate Message Passing reports that lifting-based convex methods fail before the counting bound and carry polynomial blow-up in dimension. The calcium imaging work Sparse nonnegative deconvolution for compressive calcium imaging characterizes convex transitions through statistical dimension, which is a different and weaker boundary. We include nuclear-norm minimization at small sizes only, to place it on the phase diagram.

Why not just truncate SVD? Orthogonal singular vectors mix parts with cancelling signs, and Asteris et al. show this produces diffuse components on CBCL faces. More precisely, SVD's top direction is the mean. Truncation therefore also lands on an averaged template, which makes it a useful sanity check that the trap is not specific to AMP.

Proposed Experiments

The first experiment is synthetic phase diagrams over $(\lambda, \rho)$ for $K \in \{2,4,8\}$ and sizes $F = T$ from 500 to 8000. We plot aggregate-MSE and parts-MSE, the latter after optimal permutation matching and mean removal, against theory. The decisive checks are three. The parts transition width must shrink with size while the aggregate curve stays smooth. BiG-AMP's empirical threshold must track the predicted $\lambda_{\text{alg}}$. The ratio $\lambda_{\text{alg}}/\lambda_{\text{it}}$ must grow as $\rho$ decreases, and we will compare how it grows against the rank-one $1/(e\rho^2)$ versus $4|\ln\rho|/\rho$ gap.

The second experiment is semi-synthetic planting with structured, non-random dictionaries. We use a dictionary learned from the CBCL faces used in Nonnegative Sparse PCA with Provable Guarantees, and individual source magnitude spectrograms from the BSS Oracle music set used in Reverberant Audio Source Separation via Sparse and Low-Rank Modeling. These are combined with sparse random activations and Gaussian noise at controlled $\lambda$. The check is qualitative but falsifiable. Below the predicted algorithmic threshold, the components returned by multiplicative updates and BiG-AMP should have high cosine similarity to the averaged template and low similarity to individual parts. Above it, the pattern should flip abruptly. The source-separation quality reported there, about 2 dB SDR gain for SSLR over SSRA, is not directly comparable, so we report our own SDR curves against $\lambda$.

If the synthetic cliff appears but structured dictionaries show a smooth transition, that tells us correlation in real templates destroys all-or-nothing behavior. This would be an informative outcome for applied NMF in its own right.