Deriving Frobenius Multiplicative Updates

From Reconstruction Error to an Update

Non-negative matrix factorization (NMF) represents a nonnegative data matrix \(V\) approximately as the product of two nonnegative factors, \(W\) and \(H\). The Frobenius multiplicative updates turn the reconstruction objective into simple elementwise rescalings. Their derivation matters: the numerator and denominator are determined by the gradient, and the formulas apply only when their denominators are well-defined.

Let \(V\) have \(m\) rows and \(n\) columns, and choose a factorization rank \(r\). Thus \(W\) is \(m\times r\), \(H\) is \(r\times n\), and \(WH\) approximates \(V\). The entries of \(V\), \(W\), and \(H\) are assumed to be finite and nonnegative. With one factor held fixed, the Frobenius objective is a differentiable least-squares function of the other factor; jointly, it is generally nonconvex.

The multiplicative formulas are applied in alternating blocks: first update \(W\) with the current \(H\) fixed, then update \(H\) using the updated \(W\). All matrix products inside each ratio are ordinary matrix products. The division and multiplication between corresponding entries are elementwise.

Gradients and the KKT Connection

For fixed \(H\), differentiating the objective with respect to \(W\) gives \(WHH^{T}-VH^{T}\). For fixed \(W\), the gradient with respect to \(H\) is \(W^{T}WH-W^{T}V\). Each gradient has a nonnegative term and a subtracted nonnegative term when the factors and data are nonnegative.

These gradients follow by differentiating the squared residual, or by expanding the loss and collecting terms. For example, as a function of \(W\), the terms that depend on \(W\) are \(\frac{1}{2}\operatorname{tr}(W^{T}WHH^{T})-\operatorname{tr}(W^{T}VH^{T})\). Differentiating these terms gives \(WHH^{T}-VH^{T}\). The corresponding expansion in \(H\) gives the second gradient above.

The KKT conditions for a nonnegative minimization problem require a zero gradient at a strictly positive coordinate; at a coordinate equal to zero, the gradient must be nonnegative. In the positive interior, setting the gradients to zero gives the balance between the two nonnegative terms. The multiplicative updates use this balance to rescale each current entry by the ratio of its subtracted gradient term to its other term.

In the \(W\) formula, \(H\) is held fixed. In the \(H\) formula, \(W\) is held fixed; in an alternating iteration, use the newly updated \(W\). A zero gradient at a positive entry means numerator and denominator agree there, so the corresponding ratio is one. This explains the stationary-point motivation for the formulas. It does not make either formula a direct solution of the whole joint optimization problem.

A useful equivalent view is a diagonally scaled gradient step. For example, the \(W\) update is \(W_{ik}-(W_{ik}/(WHH^{T})_{ik})(\nabla_W F)_{ik}\), when the denominator is positive. Substituting the gradient simplifies this expression to the multiplicative ratio. This representation explains the algebra, but by itself is not a proof of convergence or of decrease in the objective.

Matrix Updates Worked Through

For a matrix update, it is useful to compute the numerator and denominator separately, check their dimensions, and then apply the ratio entry by entry. If \(V\) is \(m\times n\), then \(VH^{T}\) and \(WHH^{T}\) are both \(m\times r\), matching \(W\). Likewise, \(W^{T}V\) and \(W^{T}WH\) are both \(r\times n\), matching \(H\).

Conditions, Diagnostics, and Alternatives

The data must be nonnegative for the stated nonnegative factorization model, and all entries being updated must have positive denominators. Strictly positive initial factors are a sufficient condition for positive denominators when the matrices have nonzero dimensions. If a denominator is zero, the displayed ratio is undefined; the formula must not be applied blindly. Implementations need to detect such cases and use a suitable safeguard or initialization strategy.

For a reliable calculation, check that the products have the expected dimensions, that numerator and denominator entries are nonnegative, and that each denominator used is positive. After an update, verify that the factors remain nonnegative and that the residual \(V-WH\) is computed in the stated order. For a numerical implementation, monitor the objective and inspect whether values become non-finite or the factors become numerically extreme. Such checks can reveal programming errors, poor numerical behavior, or a mismatch between the data and the assumed objective.

The updates are motivated by the gradient decomposition and KKT stationarity, but those facts do not imply that the joint problem is convex or that a particular result is a global minimum. Different starting factors may lead to different outcomes. Moreover, the ratio formulas are not the only way to handle the nonnegativity constraints. Projected gradient methods use gradient steps followed by constraint handling, while alternating nonnegative least squares focuses on block subproblems. These are alternatives, not additional steps in the multiplicative derivation.

A common mistake is to treat the numerator and denominator as interchangeable gradient terms and update \(H\) using an old \(W\) after the intended alternating step has already updated \(W\). The correction is to follow the declared sequence: compute and apply the \(W\) update with \(H\) fixed; then recompute the \(H\) numerator and denominator using the new \(W\). Another mistake is to claim that a stationary-point argument proves an update decreases the objective. The gradient/KKT connection motivates the formula, but a separate argument is needed for claims about objective behavior.