Poisson Nonnegative Low-Rank Approximation by Rescaled Alternating Projections

Many datasets are nonnegative counts: words per document, photons per pixel, sales per store per day. Two families of methods compress such matrices, and they make incompatible choices. Exponential-family PCA, which generalizes PCA to count or binary data by fitting a low-rank matrix inside a nonlinear link function, gets the noise model right. The matrix of predicted means it produces, however, is not low-rank and has no singular value spectrum. Direct nonnegative low-rank approximation seeks one matrix that is both nonnegative and low-rank, rather than a product of two nonnegative factors. It gets the structure right and keeps an explicit spectrum, but it measures error by squared distance, which is the wrong loss for counts. We propose to fit a single nonnegative, rank-$r$ matrix of Poisson means by minimizing generalized Kullback–Leibler (KL) divergence, the Poisson likelihood loss. Every step of the algorithm is still one truncated singular value decomposition (SVD) followed by an elementwise clip.

This is possible because of one fact. Both constraints, "rank at most $r$" and "entries nonnegative," are unchanged when rows and columns are multiplied by positive numbers. Suppose the curvature of the Poisson loss is approximated by a row-times-column profile. The profile comes from the closed-form rank-1 KL fit, which is row sums times column sums over the total, the same scaling used in correspondence analysis. Under that approximation, each local quadratic subproblem becomes an ordinary spherical least-squares problem in rescaled coordinates, and the rescaling commutes with both projections. In the rescaled space the noise is roughly unit-variance, so the analytic Bayesian singular value shrinkage of Nakajima et al. can replace hard truncation and choose the rank automatically.

Core Claim

The problem is

$$\min_{X}\ \sum_{ij}\big(X_{ij}-A_{ij}\log X_{ij}\big)\quad\text{s.t.}\quad X\ge 0,\ \operatorname{rank}(X)\le r,$$

where $A$ is the observed $m\times n$ count matrix and $X$ is the matrix of Poisson means. The Poisson curvature at entry $ij$ is $A_{ij}/X_{ij}^2$, and its Fisher-information version is $1/X_{ij}$. Neither is constant, which is exactly the obstacle that Fast Variational Bayesian Inference for Non-Conjugate Matrix Factorization Models calls unsolved. We replace the weights with $w_{ij}=1/(\rho_i\gamma_j)$, where $\rho_i\gamma_j$ is a rank-one fit to the current $X$ (at initialization, row sums times column sums of $A$ over the total). Write $D_\rho=\mathrm{diag}(\rho)$ and $D_\gamma=\mathrm{diag}(\gamma)$. The weighted quadratic step then becomes

$$\min_{Y\in\mathcal{C}} \big\|Y - D_\rho^{-1/2}\,Z\,D_\gamma^{-1/2}\big\|_F^2,\qquad X = D_\rho^{1/2}\,Y\,D_\gamma^{1/2},$$

where $Z$ is the scoring-step target, the current $X$ plus the weighted residual. The constraint set $\mathcal{C}$ is again "rank $\le r$ and entrywise $\ge$ a floor." Truncated SVD and clipping in $Y$-space are therefore exact projections for the reweighted problem, not heuristics.

A backtracking line search on the true KL objective makes each outer step a descent step, even though the separable weight is only an approximation to the curvature. The floor is set proportional to $\rho_i\gamma_j$. It keeps $X_{ij}>0$ wherever $A_{ij}>0$, which avoids infinite KL, and it allows exact zeros in the data. The closed-form rank-1 KL approach cannot handle zeros.

What is new is the combination of three things: a direct, factor-free nonnegative low-rank approximation, the Poisson likelihood, and SVD-exact inner steps under heterogeneous row and column noise.

Relation to Prior Work

Three papers supply the method.

  • Nonnegative low rank matrix approximation for nonnegative matrices introduced direct nonnegative low-rank approximation (NLRM), solved by alternating SVD truncation and clipping under squared loss. It names KL divergence as open work. We keep its projection structure and change the loss and the geometry the projections live in.
  • $e$PCA showed that homogenizing Poisson noise before spectral shrinkage is fast: 14 seconds against 3 hours for iterative likelihood fitting. It is one-shot, does not enforce nonnegativity, and needs a hand-set rank. We reuse its homogenization idea inside an iterative likelihood-descent loop.
  • Global Analytic Solution for Variational Bayesian Matrix Factorization and On Bayesian PCA give closed-form shrinkage that zeros out irrelevant singular values. It is valid only under spherical Gaussian noise, which our rescaling approximately produces.

Two papers are the closest competitors and define the novelty boundary.

  • Seeger and Bouchard reduce Poisson and Bernoulli factorization to Gaussian subproblems solved by that shrinkage. Their approach needs a single constant curvature, works in the natural-parameter space with a softplus link, and does not enforce nonnegativity. Our separable weights are strictly more general than constant curvature, and our low-rank structure is on the means.
  • Fast Rank-1 NMF for Missing Data with KL Divergence gives a closed form under KL for rank 1 only, and requires strictly positive entries. We use its full-data rank-1 formula as the variance profile, not as the answer.

Two lines of work motivate the proposal rather than supply it.

Research Program

We will build the rescaled alternating-projection solver for Poisson direct nonnegative low-rank approximation and analyze it in three parts.

The first part is a descent and fixed-point analysis. We will show that fixed points satisfy first-order stationarity of the true KL problem restricted to the rank-$r$ manifold whenever the clip is inactive. We will also characterize the error introduced by the separable weight approximation in terms of how far $X$ is from rank one in the multiplicative sense.

The second part is an automatic-rank variant. It replaces truncation with the analytic Bayesian matrix factorization shrinkage in rescaled coordinates. We will test whether it recovers the true rank of Poisson-noised low-rank means, which neither Simple Exponential Family PCA nor Bayesian Exponential Family PCA does without iterative expectation-maximization or Monte Carlo sampling.

The third part is an extension to missing entries. We will fill unobserved cells with the current $X$ at each outer step, using the sparse-plus-low-rank matrix products Seeger and Bouchard use, so that the SVD stays cheap.

We will not claim exactness for Bernoulli data. An upper bound of 1 on the means is not invariant under row and column scaling, so that case is future work.

Baselines

The naive reference point is one-shot correspondence-analysis-style scaling, then truncated SVD, then clipping at zero. It is our first iteration with no loop. It is the fastest thing a practitioner would try, and it isolates whether the iterative likelihood refinement matters.

The strongest factorized competitor is KL-divergence nonnegative matrix factorization with multiplicative updates and HALS-style solvers, the family evaluated in the NLRM paper. It is run with multiple random restarts, matched rank, and a wall-clock budget equal to ours. No reported result found on Lacuna for KL-NMF on these benchmarks; the NLRM paper reports only that NLRM beat A-MU, HALS, A-HALS, PG and A-PG in relative residual under squared loss, without scalar values in the file. Beating it means lower training KL at equal rank. It also means equal or better held-out Poisson log-likelihood on masked entries at equal or lower wall-clock time.

The strongest spectral competitor is $e$PCA with its best rank, clipped to nonnegative. The file reports its runtime advantage (14 s against 3 h for iterative methods) but no likelihood figure.

The Euclidean direct method is NLRM itself (squared loss, same rank, same iteration budget). Beating it means better held-out Poisson likelihood and lower recovery error to the true means on synthetic data.

For natural-parameter models we compare against Collins-style Poisson exponential-family PCA with a log link, and against Seeger–Bouchard constant-curvature variational inference with a softplus link. The file notes that Seeger–Bouchard beat MAP on Bus Stops at 90% missing, with no scalar reported. These baselines test whether low rank in the means or low rank in the natural parameters fits real counts better.

Two ablations isolate the key ingredient. The first replaces the separable weight with a single constant weight, which is our algorithm without rescaling. The second replaces the scoring step with the unweighted NLRM step. For automatic rank, the baseline is cross-validated hard truncation.

All methods get the same data, the same held-out mask, identical rank grids, and the same hyperparameter search budget.

Why not just…?

Why not just run KL-NMF with multiplicative updates? This is the real threat. It already minimizes the same loss with nonnegative factors. The case for our method rests on three claims.

  • The set of nonnegative products is smaller than the set of nonnegative rank-$r$ matrices, and Song and Ng saw this reduce the achievable residual under squared loss.
  • Our solution comes with an ordered singular spectrum.
  • Our method avoids restart-dependent local optima.

If the KL gap turns out negligible on real text and image counts, the contribution shrinks to speed, spectrum, and automatic rank, and we will report it that way. The residual-versus-rank curves on CBCL faces and TDT2 settle the question.

Why not just homogenize once, take an SVD, and clip, as correspondence analysis or $e$PCA would? This is our first iterate. If it already reaches the converged KL within noise, the iterative loop is unnecessary. The one-shot ablation measures this directly on synthetic data where the true means are highly non-separable, which is where we expect the rank-one variance profile to be most wrong.

Why not transform counts (square root or Anscombe) and run Euclidean NLRM? Squaring back a low-rank square-root matrix destroys low rank in the means. The transform also only stabilizes variance approximately at low counts, and $e$PCA documents that Gaussian treatment of photon-limited data produces noisy components. We include this transform as a baseline and compare held-out likelihood.

Why not factor natural parameters with log-link exponential-family PCA? It models a different structure: multiplicative, low-rank log-rates. Mohamed et al. report that it overfits as rank grows. Which structure fits real counts is an empirical question, and the held-out comparison answers it per dataset.

Proposed Experiments

Synthetic data. We use Song and Ng's synthetic sizes ($100\times80$, $200\times160$, $500\times400$, true ranks 10, 20, 40), but draw Poisson observations from the nonnegative low-rank means at several intensity levels. Metrics are relative error to the true means, training KL, rank recovered by the shrinkage variant, and runtime.

Real data. We use the CBCL faces ($361\times2429$) treated as intensities; term-document counts from TDT2, Reuters21578 and 20Newsgroups, taken from the ARkNLS benchmarks; Rossmann store sales; and the Bus Stops, Antenna and Print Jobs count logs at 50% and 90% missingness. Metrics are held-out Poisson log-likelihood on random masks, training KL, wall-clock time, and the proportion of the spectrum captured by the top components.

Decisive checks. Three results decide whether the idea holds.

  • Rescaled iteration must beat the one-shot scaled SVD and the constant-weight ablation on held-out likelihood. If it does not, the separable-curvature step is not earning its place.
  • At equal rank, our method must reach lower KL than best-of-restarts KL-NMF on at least the image and text data. If it does not, the direct formulation offers no fit advantage under KL.
  • The shrinkage variant must recover the true rank on synthetic Poisson data across intensities, comparable to the Gaussian case where the analytic solution zeroed components 11 through 30 for true rank 10. The file quotes this recovery and the 0.05 s against 86 s runtime for the Gaussian analytic method.