Homogenized Alternating Projections for Nonnegative Low-Rank Count Matrices

Many data matrices hold counts: words per document, photons per pixel, bus-card taps per stop and hour. A common way to denoise or compress them is to find a low-rank matrix of expected counts. That matrix should satisfy two plain conditions. Every entry must be nonnegative, because it is a Poisson rate. The fit should also be judged by Poisson likelihood rather than squared error, because a cell with a mean of 100 is naturally much noisier than a cell with a mean of 1. Existing tools each give up one of these. Direct nonnegative low-rank approximation keeps the first condition. It searches for a single matrix $X$ that is both rank $r$ and entrywise nonnegative, without splitting it into two factors, but it works only under squared error (Song & Ng; Song, Ng & Jiang). Song and Ng name the Kullback–Leibler (KL) divergence, which is the Poisson loss, as open future work. Exponential-family PCA keeps the second condition. It fits the Poisson likelihood but has no nonnegativity constraint and usually relies on slow iterations (Collins et al.).

We propose a way to get both at once. The key is an observation about rescaling. If every row of a matrix is multiplied by one positive number and every column by another, two properties are preserved: the rank, and whether the entries are nonnegative. So a Poisson fit whose per-entry weights factor into a row term times a column term can be solved in rescaled coordinates. There it becomes an ordinary squared-error problem, which the existing fast nonnegative low-rank solver handles unchanged. The rescaling weights come from the simplest Poisson model, the closed-form rank-1 fit. After rescaling, the noise is roughly equal across entries. This also lets a random-matrix noise threshold choose the rank automatically.

Core Claim

Consider a nonnegative count matrix $A \in \mathbb{R}^{m\times n}$ with observed entries $\Omega$. The target problem is

$$\min_{X \in \mathcal{M}_r \cap \mathcal{M}_n} \sum_{(i,j)\in\Omega} \big( X_{ij} - A_{ij}\log X_{ij} \big),$$

where $\mathcal{M}_r$ is the set of rank-$r$ matrices and $\mathcal{M}_n$ is the set of entrywise nonnegative matrices.

We replace this Poisson objective with a Fisher-scoring surrogate. A Fisher-scoring surrogate is a weighted squared error whose weights are the inverse variances at the current estimate. We restrict the weights to a separable form, $w_{ij} = 1/(\rho_i \gamma_j)$, with positive row scales $\rho_i$ and column scales $\gamma_j$. The surrogate becomes $\|D_\rho^{-1/2}(X - Z)D_\gamma^{-1/2}\|_F^2$. Here $Z$ is a working response matrix, and missing cells are filled in with the current estimate as in expectation–maximization.

Let $\tilde X = D_\rho^{-1/2} X D_\gamma^{-1/2}$ and $\tilde Z = D_\rho^{-1/2} Z D_\gamma^{-1/2}$. Positive diagonal scaling maps $\mathcal{M}_r \cap \mathcal{M}_n$ onto itself. Each surrogate step is therefore exactly the problem of finding the nearest rank-$r$ nonnegative matrix to $\tilde Z$ in squared error, which is what the tangent-space alternating projection method (TAP) solves.

For the initial scales we use the Poisson rank-1 maximum-likelihood fit $\rho_i\gamma_j = (\text{row}_i \cdot \text{col}_j)/\text{total}$. This is the independence model, and it is also the closed form that Ghalamkari & Sugiyama derive for rank-1 KL factorization. Our construction uses their rank-1 solution as the scaling for a rank-$r$ problem, rather than trying to extend the closed form beyond rank 1.

The empirical claim concerns three quantities: held-out Poisson deviance, rank recovery, and runtime. At matched rank, we expect the resulting estimator to beat squared-error TAP and KL nonnegative matrix factorization (NMF) on deviance. We expect the Marčenko–Pastur edge of the rescaled matrix to recover the true rank in synthetic tests. We expect runtime to stay within a small constant factor of TAP.

Relation to Prior Work

The method draws on three lines of work.

  • Mechanism. Song, Ng & Jiang supply the inner solver. TAP alternates between the rank-$r$ manifold and the nonnegative cone, needs only a $2r\times 2r$ SVD per step, and converges linearly near a solution. We reuse it without modification and change only the geometry it runs in.
  • Rescaling and rank rule. $e$PCA supplies the idea of homogenization, meaning rescaling so that noise variance is equal across entries, and of shrinking eigenvalues with the Marčenko–Pastur law. $e$PCA works on the covariance of fully observed data, requires the rank to be fixed by hand, and enforces no nonnegativity. We apply homogenization to the matrix itself inside an iterative likelihood fit. This allows missing entries and gives a data-driven rank.
  • Bounding idea and its open problem. Seeger & Bouchard turn Poisson and Bernoulli likelihoods into Gaussian surrogate problems that can be solved by SVD, using a quadratic bound with a single constant curvature. They list heteroskedastic curvature as open, and their factors are unconstrained. The separable-curvature structure proposed here is one answer to that open problem, and it is the specific ingredient that keeps each step SVD-shaped under a nonnegativity constraint.
  • Rank selection. The Gaussian analyses of Nakajima et al. motivate choosing rank from a noise-edge threshold. We use that threshold only as a rank rule, not as a Bayesian posterior.

One paper constrains the design. Nonnegative Low-rank Matrix Recovery Can Have Spurious Local Minima shows that factored nonnegative recovery has boundary traps that overparameterization does not remove. Our method avoids factors, but the intersection $\mathcal{M}_r\cap\mathcal{M}_n$ is not convex, so we claim no global guarantee. We will measure the spread of outcomes across random starts instead of assuming it is small.

We also want to be precise about what "interpretable" means here. The output has an ordered singular spectrum and nonnegative rates. Its singular vectors are not nonnegative parts in the NMF sense.

Research Program

Algorithm. The algorithm has an outer loop and an inner loop.

  • Outer loop. Each pass recomputes three things: the working response, the separable weights, and the rescaled matrix. The weights come from the best rank-1 fit to the current inverse-variance matrix $1/X_{ij}$, with a small floor on $X_{ij}$ so that cells with zero counts stay finite. This handles exact zeros, which A1GM cannot.
  • Inner loop. A few TAP iterations run in rescaled coordinates.
  • Safeguard. A step is accepted only if the true Poisson objective decreases. Otherwise the step is damped. This makes the objective monotone even though the separable surrogate is not a strict upper bound.

Rank selection. The rank is set by counting singular values of the rescaled, observed-entry-corrected matrix that lie above the Marčenko–Pastur edge. The aspect ratio in that calculation is adjusted for the observed fraction of entries.

Analysis. We will analyze two questions:

  1. How much Poisson deviance is lost by restricting weights to separable form rather than using full per-entry weights. We will bound this by how far the true inverse-variance matrix is from rank 1.
  2. When the surrogate fixed point coincides with a stationary point of the constrained Poisson problem. We will establish this under the same local conditions TAP uses.

Extension. The same construction applies to any exponential family whose variance depends only on the mean, for example the Gamma family with variance $\propto \mu^2$. We treat this as secondary.

Baselines

The naive reference points are two.

  • Independence model. The rank-1 closed-form Poisson fit, which A1GM (Ghalamkari & Sugiyama) computes with missing data. Any method that cannot beat it on held-out deviance has learned nothing beyond row and column totals.
  • Truncated SVD then clip. Rank-$r$ truncated SVD of the raw counts, followed by setting negative entries to zero.

The strongest direct competitor on the "nonnegative rank-$r$ matrix" question is squared-error TAP (Song, Ng & Jiang). It solves exactly our constraint set, only with the wrong loss. On TDT2 it reports clustering accuracy of 61.3% and normalized mutual information (NMI) of 0.728. On Yale B it reports face-recognition accuracy of about 76.8%, against about 65–72% for NMF methods. Beating it means two things. On TDT2 we must match or exceed 61.3% / 0.728 under the same clustering protocol, with the same rank and k-means applied to the leading singular vectors. We must also achieve lower held-out Poisson deviance at every tested rank. Beating it on deviance alone, while losing on clustering, would count as a partial result.

The strongest competitor on the "Poisson fit" question is KL-NMF with multiplicative updates. It is also nonnegative and rank-$r$, but it is restricted to nonnegative rank $r$, which is a smaller set than ours. We run it with 10 random restarts and give it the same wall-clock budget as our method. The comparison is held-out deviance at matched rank.

Seeger & Bouchard with clipping is the strongest exponential-family SVD-based method. We run its public formulation with constant curvature, followed by clipping. For their Bus Stops, Antenna and Print Jobs benchmarks the file gives no log-loss numbers ("no reported result found on Lacuna for Poisson log-loss on Bus Stops/Antenna/Print Jobs"). We therefore rerun it ourselves on identical train/test masks.

Ablations isolate the proposal's ingredients:

  • Constant curvature. Replace the separable weights with a single constant curvature, which is Seeger–Bouchard-style bounding inside TAP. This tests whether heteroskedastic weighting matters.
  • No cone step. Drop the nonnegativity projection, which gives a homogenized rank-$r$ Poisson fit. This tests whether the constraint costs likelihood.
  • Fixed rank. Replace the Marčenko–Pastur rule with a rank chosen on a validation set. This tests the rank rule.

Fairness. All methods get the same data splits and the same hyperparameter budget of 20 configurations each. We report wall-clock time on one machine.

Why not just…?

Why not just apply a variance-stabilizing transform (Anscombe's square root) and run squared-error TAP? This is the most serious threat. At moderate and high counts it approximately homogenizes Poisson noise with no new machinery. It fails, as is well known, in the low-count regime that dominates sparse text and event data. It also distorts the rank: the square root of a rank-$r$ matrix is not rank $r$, so the low-rank structure is imposed in the wrong space. We include Anscombe+TAP as a baseline and sweep the mean intensity of synthetic data from 0.1 to 100 counts per cell. If Anscombe+TAP matches us above roughly 5 counts per cell and loses only below that, we will report the method as a low-count tool rather than a general one.

Why not just use KL-NMF? KL-NMF already produces nonnegative rank-$r$ Poisson means. It searches only nonnegative factorizations, whose feasible set is strictly smaller than $\mathcal{M}_r\cap\mathcal{M}_n$. Its factored form is also where the boundary traps of Nonnegative Low-rank Matrix Recovery Can Have Spurious Local Minima appear. On squared error, Song and Ng report lower residuals for the direct formulation than for five NMF solvers on CBCL faces. The file gives no exact values, so this supports the direction but does not settle it. The matched-rank deviance comparison and the restart-spread measurement will settle it. If KL-NMF ties us, the remaining advantages are the ordered spectrum and the automatic rank rule, and we will say so.

Why not just run $e$PCA and clip? Clipping destroys the low rank. $e$PCA also needs fully observed data and a hand-set rank. The fair version of this idea is to use $e$PCA as the starting point for our method. We test it that way, and we also compare against $e$PCA+clip alone on fully observed photon maps, where $e$PCA reports 14 seconds against 3 hours for iterative exponential-family PCA.

Proposed Experiments

Synthetic tests. We generate Poisson matrices with known nonnegative rank-$r$ means, with $r \in \{2,5,10\}$. We vary intensity, missing fraction from 0 to 90%, and imbalance between component magnitudes, which is the regime where the spurious-minima paper predicts traps. The decisive checks are held-out deviance, the rate of exact rank recovery by the Marčenko–Pastur rule, and the variance of the final objective across 20 random starts.

Real data. Five datasets cover the regimes of interest:

  • TDT2 and the NIPS word-count corpus: clustering accuracy and NMI plus held-out deviance, compared directly with TAP's reported 61.3% / 0.728.
  • Bus Stops, Antenna and Print Jobs with 90% of entries masked: completion deviance.
  • MTSLibrary: runtime against A1GM and KL-weighted NMF.
  • Simulated low-photon diffraction maps in the style of the $e$PCA experiments: denoising mean squared error.

What would falsify the idea. The central idea fails if the constant-curvature ablation performs as well as separable weights. It also fails if Anscombe+TAP matches us across the intensity sweep. In either case the rescaling argument would not be what makes the method work.