Source-linked AI summary
On Tensors, Sparsity, and Nonnegative Factorizations
Eric C. Chi, Tamara G. Kolda
TL;DR
The paper addresses multilinear modeling of sparse count data, where Poisson variation better describes observed zeros than a Gaussian assumption. It develops CP-APR using majorization-minimization, connects it to Lee-Seung updates, prevents convergence to non-KKT points, and establishes convergence under stated conditions.
Problem
Sparse count data are better modeled with Poisson variation than Gaussian variation because Poisson models better explain the zeros encountered in sparse data.
Method
The paper develops CP-APR, a nonnegative CP factorization method whose subproblems are solved by majorization-minimization and whose single-inner-iteration case reduces to Lee-Seung KL updates.
Results
CP-APR converges to a KKT point under strict blockwise convexity and exact subproblem minimization, while its zero-avoidance adjustment prevents convergence to non-KKT points.
Takeaways & Limitations
Multiple inner iterations accelerate convergence, and CP-APR provides an implementation of KL-divergence-based factorization for large-scale sparse tensors.
Takeaways & Limitations
Open questions related to rank remain among the paper's most challenging issues.
Abstract
from arXiv · showhide
Tensors have found application in a variety of fields, ranging from chemometrics to signal processing and beyond. In this paper, we consider the problem of multilinear modeling of sparse count data. Our goal is to develop a descriptive tensor factorization model of such data, along with appropriate algorithms and theory. To do so, we propose that the random variation is best described via a Poisson distribution, which better describes the zeros observed in the data as compared to the typical assumption of a Gaussian distribution. Under a Poisson assumption, we fit a model to observed data using the negative log-likelihood score. We present a new algorithm for Poisson tensor factorization called CANDECOMP-PARAFAC Alternating Poisson Regression (CP-APR) that is based on a majorization-minimization approach. It can be shown that CP-APR is a generalization of the Lee-Seung multiplicative updates. We show how to prevent the algorithm from converging to non-KKT points and prove convergence of CP-APR under mild conditions. We also explain how to implement CP-APR for large-scale sparse tensors and present results on several data sets, both real and simulated.
1. Introduction.
The paper develops a descriptive nonnegative tensor factorization framework for sparse count data, using Poisson likelihood rather than least squares and introducing CP-APR with convergence safeguards and sparse-data support.
- The model uses a nonnegative R-component CANDECOMP/PARAFAC decomposition with normalized factor columns and nonnegative component weights.
- Poisson variation is preferred for sparse counts because it better explains zero observations than Gaussian variation; the resulting objective is KL divergence, equivalent to negative log-likelihood up to a constant.
- CP-APR fits the nonnegative Poisson tensor model by alternating Poisson regression and majorization-minimization, while reducing to Lee-Seung KL updates with one inner iteration.
- A zero-avoidance adjustment prevents convergence to non-stationary points, and exact subproblem solutions yield convergence even for sparse inputs and boundary solutions.
- The paper addresses efficient large-scale sparse implementation and reports experiments on real and simulated data, extending prior LS- and KL-based methods.
2. Notation and Preliminaries.
The preliminaries define tensor notation and motivate Poisson modeling for count data, then connect Poisson maximum likelihood to KL divergence and introduce CP-APR's alternating optimization structure.
- Notation: Scalars, vectors, matrices, tensors, norms, outer products, elementwise operations, Khatri-Rao multiplication, and tensor matricization receive explicit notation.
- The Poisson Distribution: A Poisson random variable takes nonnegative integer values, with equal mean and variance, making variance increase with the count mean.
- The Poisson Distribution: For small means, Gaussian variables can take negative values whereas Poisson variables remain count-valued; the distributions agree more closely at larger means.
- KL Divergence: Maximizing the likelihood of observed counts produces KL divergence as the negative log-likelihood, apart from an omitted constant term.
- KL Divergence: The sparse-data formulation adopts the convention 0 · log(μ) = 0 for μ ≥ 0 to handle zero observations when parameters may also be zero.
- CP-APR: CP-APR alternates optimization over factor matrices while holding the others fixed, solving each subproblem with a majorization-minimization algorithm.
3. CP-APR: Alternating Poisson Regression.
CP-APR models the nonnegative CP factors through alternating block optimization, with feasibility and convergence monitored using KKT conditions. Under strict block convexity and exact subproblem minimization, limit points satisfy the KKT conditions.
- Optimization problem: The feasible model imposes nonnegative factors with stochastic columns, while the objective is restricted to models with finite value.The objective is infinite when a positive count is assigned zero model intensity.
- Alternating optimization: CP-APR optimizes the Poisson objective by alternating over factor-matrix blocks while handling scaling through nonnegative block variables.The weights can be absorbed into one mode, yielding M^(n) = B^(n)Π^(n) and a nonnegative subproblem variable.
- Assumptions: Assumption 3.2 requires sufficiently distributed, linearly independent nonzero observations so each block subproblem is strictly convex.The condition implies at least R relevant nonzeros for each indexed row and places limits on how sparse the data can be for the desired rank.
- Convergence conditions: The matrix Φ^(n) provides the block gradient relation and yields a KKT-based convergence test using elementwise complementarity residuals.For λ > 0, feasibility together with |min(A^(n), E − Φ^(n))| ≤ τ characterizes approximate convergence.
- Convergence theory: Under strict block convexity and exact minimization of every block subproblem, every limit point with λ* > 0 is a KKT point.The theorem provides the main convergence result for the idealized CP-APR algorithm; exact subproblem solution is not generally available in practice.
4. Solving the CP-APR Subproblem via Majorization-Minimization.
CP-APR solves each alternating subproblem with majorization-minimization: a separable surrogate replaces the original objective, enabling analytic updates and convergence to the global block minimizer under stated initialization conditions.
- Majorization-minimization: Majorization-minimization replaces a difficult objective with simpler surrogate problems that majorize the original function and are easier to minimize.The surrogate preserves equality at the current iterate and produces non-increasing objective values.
- Surrogate subproblem: The chosen majorization makes the subproblem completely separable across individual entries of B and gives a unique analytic global minimum.The resulting update is expressed through B*Φ, where Φ depends on B.
- MM updates: The MM iteration updates B by B^(k+1) = B^(k) * Φ(B^(k)), preserving nonnegativity when initialized nonnegative.The gradient satisfies ∇f(B) = E − Φ(B), which supports efficient stopping rules.
- Convergence conditions: The MM objective decreases monotonically, but this property alone does not ensure convergence to the desired global subproblem minimizer.The convergence guarantee requires additional conditions on the starting point.
- Convergence conditions: With Assumption 4.2 and a finite nonnegative starting point satisfying the stated positivity condition, the MM iterates converge to the global minimizer.The analysis also allows iterates on or near the boundary, unlike prior results requiring strict positivity.
- Implementation: The detailed implementation adds inadmissible-zero avoidance to prevent multiplicative updates from becoming stuck at an incorrect zero.The correction adjusts problematic zero or near-zero entries before the multiplicative-update phase.
5. CP-APR Implementation Details.
CP-APR connects to Lee-Seung updates through its inner-loop length and adds safeguards for inadmissible zeros. Its sparse implementation avoids dense tensor and model storage by operating only on observed nonzeros.
- Relationship to multiplicative updates: With one inner subproblem iteration, CP-APR reduces to the Lee-Seung multiplicative-update algorithm for KL divergence.Multiple inner iterations instead solve the subproblem more fully and are shown to accelerate the method.
- Inadmissible zeros: Multiplicative updates can leave entries stuck at zero, including zeros that violate KKT conditions and therefore are inadmissible.Some zeros are valid solutions, so the implementation must distinguish admissible from inadmissible zeros.
- Inadmissible zeros: CP-APR corrects inadmissible zeros by moving zero or near-zero entries into the interior before multiplicative updates, with the adjustment controlled by κ.If iterates later produce inadmissible zeros, the method restarts; the approach is incorporated directly into the multiplicative-update scheme.
- Algorithm parameters: The detailed algorithm exposes outer and inner iteration limits, KKT tolerance, zero-avoidance parameters, and divide-by-zero safeguards.The implementation uses kmax, ℓmax, τ, κ, κtol, and ϵ as user-defined or example parameters.
- Design trade-off: Avoiding all zeros would eliminate the possibility of sparse factor matrices, so CP-APR uses targeted correction instead.The implementation preserves valid zeros while addressing only those that can prevent stationarity.
- Stopping criteria: The implementation checks convergence by verifying that factor matrices remain unchanged and all subproblems have converged, rather than recomputing the expensive global test each loop.This uses the fact that converged iterates stop changing.
- Sparse implementation: Sparse storage requires only (N + 1) · nnz(X) memory for X, while selected model quantities require (R + 1)P additional storage.The method computes only model values aligned with nonzeros in X and stores selected rows of Π instead of dense M or Π.
6. Numerical Results for CP-APR.
Experiments evaluate CP-APR on simulated sparse count data and real Enron and SIAM tensors. The results support KL-divergence fitting, demonstrate the inadmissible-zero fix, and show interpretable factorizations.
- Simulated sparse data: The simulated tensor contains 10 factors and varies from 480,000 to 24,000 observations, spanning 0.1% to 0.005% density.The absolute minimum implied by the stated assumption is 10,000 observations.
- Objective-function comparison: Table 6.1 compares Lee-Seung and CP-ALS under least squares with Lee-Seung and CP-APR under KL divergence using FMS and correctly identified columns.Results are means over 10 problems; FMS ranges from 0 to 1, with 1 ideal, while 10 correctly identified columns is ideal.
- Misconvergence correction: The inadmissible-zero correction makes the CP-APR sequence converge, whereas the uncorrected run appears stuck at a non-KKT point.The comparison uses κ = 0 versus κ = 10^-10; the offending zero has partial derivative −0.0016 although it should be nonnegative.
- Inner iterations: Table 6.2 evaluates CP-APR with ℓmax values 1, 5, and 10 on 100 sparse problem instances to assess convergence acceleration.ℓmax = 1 corresponds to the Lee-Seung algorithm, and the experiments track multiplicative updates and related convergence behavior.
- Real-data factorizations: On real data, CP-APR produces interpretable Enron communication components and SIAM term-author-journal components, including journal, topic, and author subgroups.The SIAM tensor has 64,133 nonzeros and 0.017% density; its tenth component corresponds to SIAM Review introductions.
- Overall comparison: For Poisson-generated sparse count data, KL-divergence methods such as CP-APR recover the true CP model more reliably than least-squares methods.This conclusion is stated for data generated via a Poisson process and contrasts KL divergence with Gaussian-motivated least squares.
7. Conclusions & Future Work.
CP-APR extends Lee–Seung KL-divergence updates with multiple inner iterations and sparse-tensor implementation, while providing convergence guarantees under stated regularity conditions. The paper identifies convergence speed, tunable factor sparsity, rank selection, and inference as open issues.
- Conclusions: CP-APR extends the Lee–Seung KL-divergence method with multiple inner iterations, which can accelerate convergence.The method remains simple to implement aside from sparse-implementation details.
- Conclusions: The convergence analysis applies to sparse count data when regularity conditions ensure sufficient tensor density and dispersed nonzeros.The proofs use a Gauss-Seidel approach and permit substituting another subproblem solver for MM.
- Future Work: Faster convergence remains a practical limitation because CP-APR can require many iterates despite inexpensive multiplicative updates.Replacing the MM subproblem solver is proposed as one acceleration direction.
- Future Work: CP-APR may produce naturally sparse factors, but their sparsity level is not currently tunable through an ℓ1 penalty.The paper also identifies missing-data extensions as future work.
- Future Work: Rank selection and uncertainty quantification for fitted factors, especially zero or near-zero entries, remain open research questions.The authors specifically ask whether sparse-count structure can support rank criteria and confidence intervals.
Appendix A. Notation Details.
The appendix defines tensor operations, notation, and the boundedness properties used in the convergence analysis. It establishes bounds on model weights over objective-function level sets and proves compactness of their convex hull.
- Notation: An outer product of N vectors forms an N-way tensor, with entries obtained by multiplying corresponding vector elements.For example, (a ◦ b ◦ c)_ijk = a_i b_j c_k.
- Notation: Elementwise tensor multiplication and division operate entry by entry on same-sized tensors or matrices.The resulting tensor retains the operands’ dimensions.
- Notation: The Khatri-Rao product combines same-column matrices of sizes I1 × R and I2 × R into a matrix of size I1I2 × R.The appendix also relates this construction to Kronecker products.
- Notation: Mode-n matricization unfolds a tensor into an In × Jn matrix, where Jn is the product of the other mode sizes.Tensor multi-indices are mapped to matrix coordinates under this unfolding.
- Boundedness: For a fixed objective level, the summed factor weights e^Tλ are bounded above and below by positive constants.The proof uses the scalar function g(α) = α − ϑ log(α) to exclude both α approaching zero and α becoming unbounded.
- Compactness: The objective is bounded on the convex hull of its level set, which supports the later compactness argument.The proof combines continuity with closedness and boundedness properties.
Appendix C. Deriving the MM updates.
The appendix derives CP-APR’s MM updates and analyzes their convergence through strict majorization, unique subproblem minimizers, compact level sets, and fixed-point arguments. Proper initialization prevents inadmissible zeros and yields KKT-optimal limits.
- MM Updates: The MM derivation majorizes each CP-APR subproblem and reduces the update to a uniquely solvable elementwise minimization.Strict convexity gives a unique global minimizer, including the zero-valued case.
- MM Updates: The update construction treats boundary anchor points explicitly because earlier Lee–Seung proofs did not rigorously handle admissible boundary cases.The appendix develops lemmas for update existence and values on the nonnegative boundary.
- Convergence: A continuous objective-decreasing iterative map on a compact level set has limit points that are fixed points, with successive-iterate distance converging to zero.This general result underpins the convergence analysis of the MM iterations.
- Convergence: The MM map converges because its level set is compact and only finitely many fixed points arise from the finite number of possible zero patterns.Eventually, the iterates remain in one fixed-point neighborhood.
- KKT Conditions: Appropriate initialization prevents convergence to non-KKT points by ruling out inadmissible zeros that violate stationarity.The argument relies on positive iterates and continuity of the update map near the limit.
- KKT Conditions: Under the theorem’s assumptions, the limiting point satisfies nonnegativity, nonnegative gradient, and complementary-slackness conditions, making it the global minimum of the strictly convex subproblem.The result follows because the converged point is a fixed point of the MM map.
Appendix F. Additional Enron results.
Appendix F presents the four Enron factorization components omitted from Figure 6.2. Figure F.1 shows these remaining components.
- Figure F.1 illustrates the four components omitted from Figure 6.2.
- These results supplement the six components shown in Figure 6.2.
- The appendix reports the remaining components from factorizing the Enron data.