Monotonicity and Zero Locking in Multiplicative Updates

Why Monotonicity and Zero Entries Matter

For nonnegative matrix factorization (NMF), multiplicative updates are attractive partly because they preserve nonnegativity and have simple elementwise formulas. But “multiplicative” does not by itself guarantee that every implementation decreases reconstruction error. The guarantee depends on the objective, the update, and conditions that keep the ratios well-defined. A second feature of the same formulas is more consequential: an entry that is exactly zero stays zero, even when making it positive could improve the fit.

This tutorial considers the Frobenius reconstruction objective and its standard multiplicative updates. The introductory material on Non-Negative Matrix Factorization establishes the factorization setting; here the focus is what the updates do to the objective and to entries near zero.

Definition: Let \(V\in\mathbb{R}_{+}^{m\times n}\) be a nonnegative data matrix, and let \(W\in\mathbb{R}_{+}^{m\times r}\) and \(H\in\mathbb{R}_{+}^{r\times n}\) be nonnegative factors. The Frobenius reconstruction objective is \(F(W,H)=\frac{1}{2}\|V-WH\|_F^2\). A multiplicative update replaces an entry by its current value times a nonnegative ratio. For fixed \(W\), the standard update for \(H\) is \(H\leftarrow H\odot (W^\top V)/(W^\top W H)\); for fixed \(H\), the update for \(W\) is \(W\leftarrow W\odot (V H^\top)/(W H H^\top)\). Products and divisions in these updates are elementwise.

An alternating sweep updates \(H\) using the current \(W\), then updates \(W\) using the new \(H\). Each step holds one factor fixed. The monotonicity result below concerns these exact formulas for the stated objective; it does not assert that their joint nonconvex optimization finds a global minimum.

Why an Update Does Not Increase the Objective

First consider an \(H\) update with \(W\) fixed. Write \(h\) for one column of \(H\), \(v\) for the corresponding column of \(V\), \(A=W^\top W\), and \(b=W^\top v\). The part of the objective involving this column is \(f(h)=\frac{1}{2}\|v-Wh\|_2^2\). Its gradient is \(Ah-b\), and its Hessian is \(A\). Because \(A\) is positive semidefinite, \(f\) is a convex quadratic in \(h\). The update is nevertheless not obtained by unconstrained minimization of this quadratic; its descent property follows from an auxiliary quadratic that majorizes it at the current iterate.

Theorem: Suppose \(V,W,H\) are nonnegative, the current entries of \(H\) are strictly positive, and each denominator \((W^\top W H)_{ak}\) used in its update is positive. Then the standard \(H\) update does not increase \(F(W,H)\). The corresponding statement holds for the \(W\) update when its current entries and update denominators are positive. Thus, when both updates satisfy these conditions, an alternating sweep does not increase the objective.

Here is the justification for the \(H\) step. For a current column \(h'\) with strictly positive entries and \(Ah'\) strictly positive, define the diagonal matrix \(D\) by \(D_{aa}=(Ah')_a/h'_a\). For any vector \(z\), nonnegativity of the entries of \(A\) gives

z^\top(D-A)z = \frac{1}{2}\sum_{a,b} A_{ab}h'_a h'_b \left(\frac{z_a}{h'_a}-\frac{z_b}{h'_b}\right)^2 \geq 0.

Therefore \(D-A\) is positive semidefinite. Since \(f\) is quadratic, its exact expansion around \(h'\) is \(f(h)=f(h')+\nabla f(h')^\top(h-h')+\frac{1}{2}(h-h')^\top A(h-h')\). Replacing \(A\) in the final term by \(D\) gives an upper bound, equal to \(f\) at \(h=h'\). This upper-bound function is an auxiliary function: it touches \(f\) at the current point and is nowhere below \(f\).

Minimizing that auxiliary quadratic coordinate by coordinate gives \(h_a=h'_a-(Ah'-b)_a/D_{aa}=h'_a b_a/(Ah')_a\). Since \(b=W^\top v\) is nonnegative, this is precisely the nonnegative multiplicative update. The updated value minimizes the upper bound, so the objective at the updated point is no greater than the upper bound there, which is no greater than its value at the old point:

f(h_{\text{new}})\leq G(h_{\text{new}},h') \leq G(h',h')=f(h').

The \(W\) result follows by the same argument with the roles of the factors transposed. A consequence is that the objective values across valid updates form a nonincreasing sequence bounded below by zero. That fact implies convergence of the objective values, but not necessarily convergence of the factors, convergence to a unique solution, or attainment of a global minimum.

Worked Example: Checking One \(H\) Update

Consider one hypothetical sample with \(v=(2,2)^\top\), a fixed factor \(W=(1,2)^\top\), and current coefficient \(h=0.5\). The dimensions and nonnegativity conditions are satisfied. The update numerator is \(W^\top v=1(2)+2(2)=6\), and the denominator is \(W^\top W h=(1^2+2^2)(0.5)=2.5\), which is positive. Therefore

h_{\text{new}}=0.5\frac{6}{2.5}=1.2.

Before the update, the reconstruction is \((0.5,1)^\top\), so \(F=\frac{1}{2}[(2-0.5)^2+(2-1)^2]=\frac{1}{2}(2.25+1)=1.625\). After the update, the reconstruction is \((1.2,2.4)^\top\), giving \(F=\frac{1}{2}[(2-1.2)^2+(2-2.4)^2]=\frac{1}{2}(0.64+0.16)=0.4000\). The computed objective decreases from \(1.625\) to \(0.4000\).

Zero Locking: A Structural Consequence

If a current entry \(H_{ak}\) is zero and its update ratio is finite, then \(H_{ak}^{\text{new}}=0\) times that ratio, which is still zero. Repeating the update cannot make that entry positive. The same applies to entries of \(W\). This property is called zero locking. It is distinct from an entry merely becoming very small: a positive value can still change, whereas an exact zero cannot regrow under the ordinary multiplicative formula.

This matters because nonnegativity constraints allow zero entries, but zero may not be appropriate for a particular factor entry. A bad initialization, rounding to zero, or an update with a zero numerator can prevent the algorithm from exploring solutions that use that entry. A zero is not automatically a certificate that the best fit requires the corresponding component to be absent.

Worked Example: A Locked Entry Restricts the Fit

Suppose a hypothetical fixed factor and target are \(W=\begin{pmatrix}1&1\\0&1\end{pmatrix}\) and \(v=(2,1)^\top\), with current \(h=(0,1)^\top\). These are nonnegative, and the update denominators are positive: \(W^\top W h=(1,2)^\top\). The numerator is \(W^\top v=(2,3)^\top\). Applying the update gives

h_{\text{new}} = \begin{pmatrix}0\\1\end{pmatrix} \odot \begin{pmatrix}2/1\\3/2\end{pmatrix} = \begin{pmatrix}0\\1.5\end{pmatrix}.

The first entry remains zero despite its positive ratio. The old reconstruction is \(Wh=(1,1)^\top\), so its objective is \(\frac{1}{2}[(2-1)^2+(1-1)^2]=0.5000\). The new reconstruction is \((1.5,1.5)^\top\), with objective \(\frac{1}{2}[(2-1.5)^2+(1-1.5)^2]=0.2500\). The fit improves, but the locked entry still prevents an exact representation: \(h=(1,1)^\top\) would give \(Wh=(2,1)^\top=v\) and objective zero.

In this example the zero is well-defined under the update because the denominator for that entry is positive. In other cases, a zero entry can coincide with a zero denominator, producing an undefined \(0/0\) ratio. Such cases need explicit handling; one must not assume the formula itself defines a valid update there.

Positive Floors: Useful Safeguard, Different Algorithm

A common practical safeguard is to replace each factor entry below a chosen \(\varepsilon>0\) with \(\varepsilon\), or to initialize entries at least that large. Keeping entries strictly positive can reduce the chance of zero locking and help avoid some zero denominators. But flooring is an additional operation, not part of the multiplicative update covered by the monotonicity proof. It can change the reconstruction and increase the objective. Likewise, adding a small constant to the numerator or denominator changes the update formula, so the same proof does not automatically apply.

Worked Example: A Floor Can Increase Reconstruction Error

Let the hypothetical one-row data be \(V=(1)\), with fixed \(W=(1,1)\) and \(H=(0,1)^\top\). The reconstruction is exactly \(1\), so \(F=\frac{1}{2}(1-1)^2=0\). The \(H\) update has numerator \(W^\top V=(1,1)^\top\) and denominator \(W^\top W H=(1,1)^\top\). It leaves \(H=(0,1)^\top\) unchanged, with objective zero. Now apply a floor \(\varepsilon=0.1\), making \(H=(0.1,1)^\top\). The reconstruction becomes \(1.1\), and

F_{\text{floored}}=\frac{1}{2}(1-1.1)^2 =\frac{1}{2}(0.01)=0.005.

The floor has increased the objective from \(0\) to \(0.005\). The example also shows why a positive floor should not be described as preserving monotonicity just because it prevents exact zeros.

Diagnostics, Alternatives, and Limitations

For a run intended to use the standard Frobenius updates, compute the objective after each \(H\) update and each \(W\) update, or at least after every full sweep. Under the conditions of the theorem, it should not increase, apart from small discrepancies due to floating-point arithmetic. A noticeable increase calls for checking that the code uses the stated objective and update, that the factors are nonnegative, and that the updates use the intended current factor values. Also inspect denominators for zeros or extreme small values: adding an undocumented constant can hide a division problem while changing the method.

If a floor is applied, record both the objective before and after flooring. A floor should be chosen with the scale of the factors in mind: a fixed numerical threshold can have very different effects for differently scaled data or factors. A constrained block minimization approach is a different alternative: if it genuinely minimizes the same objective over the nonnegative values of one factor while the other is fixed, that block step cannot increase the objective. It avoids the specific multiplicative zero-locking rule, but requires solving a different subproblem. Neither approach removes NMF's broader limitations: the joint objective is nonconvex, and a descent guarantee alone does not identify a globally best or uniquely interpretable factorization.

Common pitfall: “The update is monotone, so flooring small entries is also monotone.” The proof applies to the stated update under its conditions. Replacing zero entries by positive values changes the factors, and can raise the objective; evaluate the objective after the floor rather than assuming the original guarantee still holds.

Check Your Understanding

Answer each question, then compare your reasoning with the solutions below.

For fixed \(W\), why does the auxiliary-function argument require positive current entries and positive update denominators?
If \(H_{ak}=0\) and the update ratio is finite and positive, what is \(H_{ak}^{\text{new}}\)? Can later ordinary multiplicative updates make it positive?
With \(V=(2)\), \(W=(1)\), and current \(H=(1)\), calculate the updated \(H\) and the objective before and after the update.
Does a nonincreasing sequence of objective values establish that the factors have reached a global minimum? Explain.

Solutions. (1) Positivity makes the diagonal majorizer \(D_{aa}=(Ah')_a/h'_a\) well-defined, and positive denominators make the multiplicative ratios defined. (2) The new entry is \(0\) times the ratio, hence \(0\); ordinary multiplicative updates cannot make it positive. (3) The numerator and denominator are both \(2\) and \(1\), respectively, so \(H_{\text{new}}=1(2/1)=2\). The objectives are \(F_{\text{old}}=\frac{1}{2}(2-1)^2=0.5000\) and \(F_{\text{new}}=\frac{1}{2}(2-2)^2=0\). (4) No. The objective values can converge while the factors do not converge to a unique solution, and descent in a nonconvex problem does not establish a global minimum.