Motivation
Nonnegative matrix factorization asks for additive components that reconstruct nonnegative measurements. A definition of the objective is only a beginning: a student must also know how to produce factors, why an update is sensible and what a stopping rule actually establishes. Nonnegativity introduces a boundary, so an unconstrained gradient equation cannot characterize every optimum.
Multiplicative updates are appealing because a positive coefficient stays positive and no learning rate appears explicitly. Their descent proof nevertheless depends on a specific upper bound. Multiplying by a ratio of positive and negative gradient terms is not a universal recipe for safe optimization. We derive the bound and identify exactly where nonnegative data, positive current coefficients and nonzero denominators enter.
We then compare the method with alternating nonnegative least squares. Each block problem is convex even though the joint factorization is not. This alternative can move away from a bad zero coefficient and gives a natural test based on constrained first-order conditions. Neither method makes component count, unique interpretation or global optimality automatic.
Definitions
Definition 6.1.1
(Euclidean NMF and its block quadratic)
For and a chosen inner dimension , find and minimizing
For one column with fixed, write , , and . Its gradient is . At a nonnegative block minimizer, , and for every coordinate.
The last conditions are the Karush–Kuhn–Tucker, or KKT, conditions for this orthant-constrained convex quadratic. They are sufficient as well as necessary for a block optimum. A positive coefficient must have zero gradient; a zero coefficient may have positive gradient because decreasing it is infeasible. A negative gradient at zero reveals a feasible direction that improves the fit.
Concept lensGeometric
Nonnegative least squares as projection onto a cone
The set is the convex cone generated by the columns of . The block problem asks for the Euclidean projection of onto it. The KKT conditions say the same thing geometrically: the residual has nonpositive inner product with every column of , and is orthogonal to each column whose coefficient is positive.
Definition 6.1.2
(An auxiliary function majorizes the objective)
A function is an auxiliary function for if for feasible , with equality at . Minimizing while holding fixed yields
Unlike EM's lower bound for a log likelihood being maximized, this is an upper bound for a loss being minimized. The shared logic is a bound that touches at the current iterate. Here all updates within one block use the same old block. Changing entries sequentially while using a partly updated ratio is a different algorithm unless its own coordinate argument is supplied.
Theorem/Proposition
Theorem 6.1.3
(A valid multiplicative block update)
Suppose has no zero columns and . Then is entrywise nonnegative and . The update
is nonnegative and satisfies . If every , the new vector is strictly positive. Therefore positive and nonnegative with no zero rows or columns permit indefinitely repeated positive alternating multiplicative steps.
The full matrix steps are
where products and ratios outside ordinary matrix multiplication are entrywise. The second step uses the new and the old . Each block decreases or preserves the same objective. Updating both factors simultaneously from old ratios is not covered by this alternating proof.
Theorem 6.1.4
(Nonnegative least-squares optimality and projected descent)
For fixed , the KKT conditions above characterize global minimizers of over . Let . The projected-gradient block update
has nonincreasing objective and obeys . The maximum is coordinatewise. If , the block objective is constant and this step is unnecessary.
This theorem gives a complete inner iteration for a nonnegative least-squares, or NNLS, block. One may run it until a stated KKT residual is small, then solve the analogous row problems for with fixed. Exact block minimization is one option; a finite number of proven descent steps is another. Both are distinct from blindly clipping an unconstrained least-squares answer.
Proof sketch or proof idea
Proof
(The diagonal quadratic majorizer)
Since is quadratic, its exact expansion at is
Put and replace by in the last term to define . To prove the upper bound, for arbitrary expand
The equality follows by expanding both squares and using symmetry of . Nonnegativity uses its entrywise signs; positive semidefiniteness of alone would not justify this particular sum. Also because a nonzero column of gives and .
The strictly convex diagonal surrogate has unconstrained minimizer , whose th entry is . Since , this minimizer is feasible, proving descent by the auxiliary-function chain. Applying the same proof to every column gives the update. Transposing the factorization interchanges the roles of and and proves the step. Positivity of both factors together with nonzero rows and columns of keeps all update numerators positive.
Proof X-ray
A descent proof does not prove convergence of factors
The objective sequence is nonincreasing and bounded below by zero, so its values converge. This descent argument does not bound factor magnitudes: multiplying one column of by and dividing the corresponding row of by leaves their product unchanged. Nor does a fixed zero necessarily satisfy KKT conditions. Claims about convergence to a stationary point or a local minimum need additional analysis beyond this upper-bound argument.
Proof
(KKT conditions and a projected step)
Necessity follows by perturbing a positive coordinate in either direction and a zero coordinate only upward. For sufficiency, if satisfies KKT, then for every feasible ,
The first term equals because , and is nonnegative. Thus no other feasible vector improves the block loss.
For projected descent, minimizes over the orthant. Its variational inequality at the feasible competitor gives . Since , the exact quadratic expansion bounds the loss increase above by . Combining the two inequalities proves the stated decrease. A fixed projected step is equivalent to the block KKT conditions, including boundary coordinates.
A practical alternating NNLS solver initializes nonnegative factors, optimizes columns of with the proven projected steps, and then optimizes rows of analogously. A unit step divided by a valid upper bound for is also safe if the proof is adjusted to that bound. Report the objective, factor normalization convention, number of iterations and a KKT residual such as the norm of for each block. An unchanged loss to a few decimal places is a weaker stopping test, especially near a boundary or in a poorly scaled factorization.
Zero data need not be disguised by numerical constants. A column of that is identically zero has an exact best coefficient column equal to zero for every fixed nonnegative dictionary. It can be removed before a strictly positive multiplicative run and restored afterward as a zero column of coefficients. Similarly, a zero measurement row can be reconstructed exactly by a zero row of the dictionary. This preprocessing changes the applicability of the positive-iteration theorem in a transparent way. It does not justify setting arbitrary interior zeros in the factors: those can lock coordinates that should participate in the fit. A zero dictionary column contributes nothing to the product and needs explicit reinitialization or removal if it is to become useful.
Scale also affects how a stopping residual should be read. Two factorizations can have identical products yet very different coefficient magnitudes, so an absolute gradient tolerance without a normalization convention can be misleading. Normalize nonzero dictionary columns when comparing runs and rescale the coefficient rows inversely; then record a tolerance relative to a stated data scale. This is an interpretation rule rather than an extra convergence theorem. Different initializations can still converge to different products, and comparing only their iteration counts ignores both final reconstruction quality and the effort spent on each block solve. For a chosen inner dimension, report these quantities together before attributing a better representation to a particular algorithm.
Worked examples
Worked example 6.1.5
(A multiplicative update with an exact optimum)
Let , and . Then , , and the multiplicative ratios are two and three. The new coefficient is , reducing from to zero. Here the quadratic is already separable and the majorizer equals the original loss. Such one-step success is special; a nonorthogonal dictionary couples coefficients.
Worked example 6.1.6
(Coupling makes ordinary gradient splitting insufficient)
Take , and . Then , and . The update gives . Its reconstruction is , so the residual is and , compared with . The exact NNLS solution is with zero loss. Descent is substantial but does not finish the coupled problem in one step.
Worked example 6.1.7
(A projected step can activate a zero coordinate)
With the same , start at . The gradient is . The largest eigenvalue of is . One projected step therefore makes the first coefficient , leaving the second at . The boundary coordinate correctly activates because its gradient is negative. Multiplicative updating keeps that coordinate at zero as long as its ratio is finite, even though moving upward improves the loss.
Common mistakes
Counterexample mode
A zero-locked multiplicative fixed point need not be optimal
For and , the vector has positive denominators . Its multiplicative update is itself: zero times remains zero and the second ratio equals one. But its gradient is , violating KKT. Its loss is , whereas has zero loss. This disproves any unrestricted assertion that every nonnegative fixed point of the multiplicative formula is stationary. The strict-positivity hypotheses in the majorizer iteration are doing real work.
Common mistake
(Clipping an unconstrained solution changes coupled residuals)
For a coupled dictionary, replacing negative least-squares coefficients by zero need not solve NNLS, because remaining coefficients may need to change. Similarly, replacing every denominator by a denominator plus a tiny constant changes the update and invalidates the exact majorizer identity unless a new proof is supplied. Zero data rows or columns should be handled explicitly, or by an NNLS method that admits boundary states. Numerical safeguards need a stated mathematical interpretation.
History of an idea
The auxiliary-function route
Lee and Seung's NIPS 2000 paper presents Euclidean and divergence-based multiplicative algorithms using auxiliary functions. This unit proves the Euclidean descent claim under explicit conditions and distinguishes convergence of objective values from stronger conclusions about factor sequences. The divergence objective requires a different auxiliary function and is not proved here.
Summary
The multiplicative ratio minimizes a specific diagonal quadratic upper bound. Its validity depends on signs, positive current coefficients and nonzero denominators. Alternating NNLS instead solves convex constrained blocks and can activate zero coordinates. Both approaches require an explicit stopping criterion and careful interpretation: decreasing reconstruction error does not establish unique factors, a globally optimal factorization or a statistically justified inner dimension.
Exercises
Quick check
(Verify the second worked example by multiplying the new coefficient vector by and computing both objective values exactly.)
Keep fifteenths for the first reconstructed coordinate.
Solution · Answer
. Subtracting gives . Its squared norm is , so the half-squared loss is . Initially and the residual is , giving loss one. The strict decrease is consistent with the majorizer proof.
Quick check
(Prove that the KKT conditions hold at for the coupled example. Explain why this certifies a block optimum but not a general theorem of joint NMF optimality.)
Compute the reconstruction and gradient with W fixed.
Solution · Answer
, so the gradient is zero. The coefficients are positive and complementarity holds. By the convex quadratic proof this is a global minimizer of the fixed- problem; here zero reconstruction loss also happens to attain the joint lower bound zero. In general a positive-loss NNLS block optimum says nothing about a different dictionary , and alternating block optimality does not certify global optimality of the joint nonconvex problem.
Quick check
(Take with columns and , and target . Find the unconstrained least-squares coefficients, clip them, and compare with the true NNLS solution.)
On the boundary where the first coefficient is zero, optimize the second coefficient again.
Solution · Answer
The unconstrained exact solution is . Clipping gives , reconstruction and loss . For , minimize , giving and loss . At , the residual is and gradient , satisfying all KKT conditions. This certifies the NNLS solution and demonstrates the need to reoptimize after imposing the boundary.
Quick check
(Explain why normalizing each nonzero column of and rescaling the corresponding row of preserves the reconstruction. Does it prove uniqueness or global optimality?)
Use a positive diagonal matrix between the two factors.
Solution · Answer
For positive diagonal , and both factors remain nonnegative. Choosing makes every nonzero column have unit norm and rescales its row of coefficients inversely. Zero columns need a separate convention because their norm cannot be inverted. This removes one scale ambiguity but leaves permutation and possibly further factorization ambiguities. It changes no reconstruction loss and supplies no proof that the current product is globally best.