Nonnegative approximations of nonnegative tensors

Lek-Heng Lim; Pierre Comon

Source-linked AI summary

Nonnegative approximations of nonnegative tensors

Lek-Heng Lim, Pierre Comon

arXiv:0903.4530v2Mar 26, 2009math.NAcs.IR

TL;DR

The paper studies whether nonnegative tensors admit best low-rank approximations, a question motivated by nonnegative PARAFAC and its probabilistic naïve Bayes interpretation. It proves existence of optimal solutions under any norm and, under a mild assumption, for Bregman divergences, while ruling out parafac degeneracy in the nonnegative setting.

Problem
For tensors of order k ≥3, best low-rank approximations may fail to exist, creating an ill-posed approximation problem despite nonnegative PARAFAC’s applications.
Method
The paper analyzes nonnegative outer-product decompositions using compact sublevel sets and norm equivalence, extending the argument to suitable Bregman divergences.
Results
Nonnegative approximation problems attain global optima, and nonnegative border rank coincides with nonnegative rank; parafac degeneracy does not occur for nonnegative approximations.
Takeaways & Limitations
Nonnegative PARAFAC is well-posed across norm choices, with the result covering commonly used sum-of-squares and Kullback-Leibler losses.
Takeaways & Limitations
The general Bregman-divergence extension requires a mild assumption, and existence cannot be expected when the relevant domain is not closed.

Abstract

from arXiv · show

We study the decomposition of a nonnegative tensor into a minimal sum of outer product of nonnegative vectors and the associated parsimonious naive Bayes probabilistic model. We show that the corresponding approximation problem, which is central to nonnegative PARAFAC, will always have optimal solutions. The result holds for any choice of norms and, under a mild assumption, even Bregman divergences.

1. Dedication

The article is dedicated to Richard Allan Harshman and is organized around two of his best-known works, parafac and lsi, while addressing two questions he posed.

The article honors late colleague Richard Allan Harshman.
Its structure centers on Harshman’s parafac and lsi work and answers two questions attributed to him.
The intended readership is technometrics.

2. Introduction

The introduction frames low-rank tensor approximation as a generalization of matrix factorization whose existence issues become difficult at order k ≥3. It presents nonnegative approximations as a setting where optimal solutions are guaranteed under broad proximity measures.

The introduction situates the topic within tensor decomposition’s history from Hitchcock through algebraic complexity, statistics, and quantum computing.
The classical CANDECOMP/PARAFAC model seeks an optimal rank-r approximation using scalar weights and vector factors.
For k ≥3, a global minimizer of the rank-r approximation problem may not exist, making the problem ill-posed.
Nonnegativity is motivated by applications such as chemometrics and by additive representations without cancellations.
Nonnegative tensor factorization generalizes nonnegative matrix factorization to higher-order tensors.
Nonnegative PARAFAC always has a solution for continuous proximity measures satisfying mild conditions, including norms and some Bregman divergences.

3. Tensors as hypermatrices

This section introduces tensors as elements of tensor-product spaces represented by hypermatrices, then develops rank, outer products, and several norms. It emphasizes that finite-dimensional norm equivalence makes the convergence results norm-independent.

An order-k tensor belongs to a tensor product of k vector spaces and can be represented as a d1 × ··· × dk array.
Hypermatrices carry tensor-product algebraic structure beyond their interpretation as numerical arrays.
A rank-1 tensor is an outer product, while tensor rank is the minimum number of rank-1 terms in a sum representing the tensor.
The E-, F-, and G-norms correspond to l1-, l2-, and l∞-norms after flattening a tensor into a vector.
The E-norm is especially natural for nonnegative tensors because normalized entries can be interpreted as probability values.
All norms on these finite-dimensional tensor spaces are equivalent, so the paper’s convergence results apply to any norm.

4. Nonnegative decomposition of nonnegative tensors

The paper connects nonnegative tensor decompositions with parsimonious naïve Bayes models and shows how nonnegative factors can be normalized probabilistically. The decomposition parallels matrix SVD while replacing orthogonal factors with simplex-valued factors.

A parsimonious naïve Bayes model yields a joint probability tensor with a nonnegative rank-revealing decomposition.
A nonnegative tensor decomposes into weighted outer products of nonnegative vectors, with the smallest number of terms defining nonnegative rank.
After E-norm normalization, the vector factors can be placed in unit simplices and the weights represent mixture probabilities.
Unlike SVD, the simplex-valued factors in the nonnegative decomposition are not orthogonal.
The parsimonious requirement sets the number of hidden states to the nonnegative rank, making the hidden variable minimally supported.
For k = 2, the model becomes Hofmann’s probabilistic latent semantic indexing, while the tensor case extends the same probabilistic structure.

5. Nonexistence of globally optimal solution for real and complex tensor approximations

For tensors of order three or higher, best rank-r approximations may not exist, making the optimization problem ill-posed. The section constructs an explicit real and complex example exhibiting parafac degeneracy.

5. Nonexistence of globally optimal solution for real and complex tensor approximations: Best rank-r approximations for tensors of order three or higher need not exist.The infimum may fail to be attained by any rank-r decomposition.
5. Nonexistence of globally optimal solution for real and complex tensor approximations: Bini, Capovani, Lotti, and Romani’s matrix-multiplication construction yields an explicit example of this nonexistence.The construction applies over both the real and complex numbers.
5. Nonexistence of globally optimal solution for real and complex tensor approximations: The example uses linearly independent vectors x1, x2, x3, x4 and defines Aε through ε-dependent outer-product terms.The construction assumes n ≥ 4 and works over R^n or C^n.
5. Nonexistence of globally optimal solution for real and complex tensor approximations: The sequence Aε converges to A as ε → 0 even though each summand becomes unbounded in magnitude.This behavior is the parafac degeneracy phenomenon.
5. Nonexistence of globally optimal solution for real and complex tensor approximations: The constructed tensor A has rank at least 6, while rank-5 approximants can approach it arbitrarily closely.Consequently, the rank-5 approximation infimum is zero but is not attained.

6. Existence of globally optimal solution for nonnegative tensor approximations

Imposing nonnegativity restores existence of best rank-r tensor approximations. The proof uses coercivity and compact sublevel sets, and the result extends from the E-norm to arbitrary norms.

6. Existence of globally optimal solution for nonnegative tensor approximations: The proof establishes that the nonnegative parafac loss function has compact sublevel sets and therefore attains its infimum.The feasible parameter domain is closed but unbounded; boundedness of sublevel sets supplies the missing compactness.
6. Existence of globally optimal solution for nonnegative tensor approximations: For nonnegative approximants, the E-norm of each normalized rank-1 term equals its coefficient δq.This identity drives the contradiction used to prove boundedness of sublevel sets.
6. Existence of globally optimal solution for nonnegative tensor approximations: Unit-norm factor vectors and a separate magnitude coefficient prevent rescaling from producing diverging factors with an unchanged outer product.Without this normalization, positive scalings whose product is one would defeat the coercivity argument.
6. Existence of globally optimal solution for nonnegative tensor approximations: Nonnegative rank is upper semicontinuous, and nonnegative border rank coincides with nonnegative rank.These equivalent characterizations connect approximation existence with closure of bounded nonnegative-rank sets.
6. Existence of globally optimal solution for nonnegative tensor approximations: The existence result holds for any norm because all norms on the finite-dimensional tensor space induce the same topology.Thus parafac degeneracy does not occur for nonnegative approximations of nonnegative tensors, despite not being reducible simply to cancellation.

7. Br`egman divergences

The section examines nonnegative tensor approximation under Bregman divergences, which are important proximity measures but need not be metrics. Under closed-domain conditions, the approximation problem attains a solution.

Motivation: Bregman divergences generalize proximity measures beyond norms and are important in nonnegative matrix and tensor decompositions.They may have information-theoretic or probabilistic interpretations and need not be symmetric or satisfy the triangle inequality.
Problem: The paper asks whether nonnegative tensor approximation under a Bregman divergence always has a solution.The formulation minimizes Dϕ(A, X) over X in ri(Ω) with rank+(X) ≤ r.
Limitation: In general, existence cannot be guaranteed because the relative interior ri(Ω) is not closed.The paper gives an example illustrating this boundary-related failure.
Result: Proposition 7.2 establishes attainment when Ω is closed and convex, A belongs to Ω, and the feasible subset K of ri(Ω) is closed.The result applies to the Bregman divergence defined from a strictly convex, continuous function ϕ that is continuously differentiable on ri(Ω).
Proof idea: The proof restricts the optimization to a compact sublevel set, where continuity ensures that the infimum is attained.The argument uses boundedness of Bregman sublevel sets and closedness of the relevant rank-constrained feasible intersection.
Generalization: The existence argument extends to any proximity measure that is continuous and coercive on a closed feasible subset.Showing those properties is usually the main work for a particular measure.

8. Aside: norm-regularized and orthogonal approximations

The aside explains that orthogonal and norm-regularized tensor approximations have optimal solutions because their continuous objectives are minimized over compact feasible sets. This contrasts with the more difficult nonnegative tensor approximation setting.

Overview: Orthogonal and norm-regularized approximations have optimal solutions through compactness of their feasible sets and continuity of their objectives.The paper notes that this existence argument is simpler than for nonnegative tensor approximation.
Orthogonal approximations: Orthonormal loading constraints bound the coefficients and produce a compact feasible region for orthogonal PARAFAC.The region is [−∥A∥F, ∥A∥F]^r × O(d1, r) × · · · × O(dk, r).
Orthogonal approximations: Orthogonal PARAFAC therefore always has a globally optimal solution.This follows from minimizing a continuous objective over the compact constrained region.
Norm-regularized approximations: Norm regularization adds terms proportional to the squared 2-norms of the loading factors.Under regularity conditions, the regularized formulation is equivalent to equality-constrained optimization on compact spheres.
Norm-regularized approximations: Norm-regularized PARAFAC always has a globally optimal solution, and the same approach can apply to other regularizations.Compactness of the equality-constrained feasible set guarantees attainment of the continuous objective.