Home / Curated / Algorithms / Lee-Seung Multiplicative Updates

Lee-Seung Multiplicative Updates

Algorithms AIMech:LeeSeungMultiplicativeUpdates DRAFT

Aliases: Lee-Seung NMF Updates

The Lee-Seung block multiplicative algorithms for nonnegative matrix factorization, using objective-specific elementwise factor rescaling to reduce squared reconstruction error or generalized KL divergence with the other factor held fixed.

Identity Notes & Concept Scope Scoped to Equations 4-5 and their auxiliary-function derivations in Lee and Seung, NIPS 2000. This is a particular family of fitting rules, distinct from the general NMF factorization, every multiplicative optimizer, generic EM and the fixed-prior Iterated Wiener Filter. An update of one entire factor block is different from simultaneously changing both factors from stale values. Four candidate identities were compared against all 442 pinned AIO IDs, labels and scoped synonyms and 450 preceding native IDs, names and aliases, with no normalized match. Ignored/hidden full-checkout searches returned the same 106 matched-line set in each checkout after the prior merge. All matched excerpts from 76 files were read; they are discovery context, not existing concept records. The semantic search covered all pinned labels and scoped synonyms and returned 212 rows: 205 byte-equivalent prior readings and seven additional rows, all inspected. Twenty-three annotated AIO nodes with outgoing edges comprise 21 unchanged prior readings and two new inspections. Thirty contextual YAMLs, including seven native neighbors, comprise 25 unchanged prior readings and five complete new readings. This absence assessment is bounded to the pinned snapshot and inspected maintained corpus.

Claims & Grounded Evidence

3 Claims

Mechanism #squared-error-update

For squared error and well-defined positive denominators, update H elementwise as H <- H*(W^T V)/(W^T W H) with W fixed. Update W analogously as W <- W*(V H^T)/(W H H^T) with H fixed, evaluating each block rule against its current other factor. Multiplication and division of corresponding entries are elementwise. The proof uses a quadratic auxiliary function whose diagonal curvature majorizes W^T W, with current positive coordinates required in its displayed derivation.

supports Source: Algorithms for Non-negative Matrix Factorization · Locator: Section 4, Equation 4, PDF p. 3; Section 6, Lemma 2 and Equations 12-19, PDF pp. 4-5

Mechanism #divergence-update

For generalized KL divergence, H_aμ is multiplied by [sum_i W_ia V_iμ/(WH)_iμ]/[sum_i W_ia], and W_ia by [sum_μ H_aμ V_iμ/(WH)_iμ]/[sum_μ H_aμ], with the other block fixed. Jensen majorization of the negative logarithm gives the source auxiliary function. With valid ratios and the stated domain, exact minimization of each auxiliary does not increase the corresponding objective. These are two objective-specific rules, not a universal multiplicative update for arbitrary losses.

supports Source: Algorithms for Non-negative Matrix Factorization · Locator: Section 4, Equation 5, PDF p. 3; Section 6, Lemma 3 and Equations 20-33, PDF pp. 5-6

Limitation #descent-boundaries

Monotone objective values do not alone prove convergence of factor matrices to a local minimum. In a curator scalar example V=1 and W=H=0.5, updating both factors simultaneously from their old values sets both to 2 and raises squared error from 0.5625 to 9. A separate fixed-W example W=[[1,0],[1,1]], V=[1,2]^T and H=[1.5,0]^T is unchanged by the H rule, although the zero coordinate has half-squared-error derivative -0.5 and increasing it lowers the loss. This is a zero-locked nonoptimal block state with positive denominators, not a claim about an inspected author implementation.

supports Source: Algorithms for Non-negative Matrix Factorization · Locator: Sections 4 and 6-7, PDF pp. 3-7; curator finite counterexamples to unrestricted update and local-optimum interpretations

⚠️ Curated Limitations & Negative Results

The rules require defined denominators and an explicit zero policy. The proof for positive current coordinates does not automatically cover arbitrary boundary initializations; multiplicative zeros may remain locked.
Sequential block descent is not a license to update both blocks from stale factors. Arbitrary epsilon denominators, clipping, approximate updates or added penalties change the algorithm and require separate analysis.
The objective is generally nonconvex jointly in W and H. Descent, bounded objective values and an auxiliary-function proof do not establish unique factors, a global optimum or the source discussion’s unrestricted local-optimum guarantee.
Finite arithmetic verifies selected update and boundary claims; no author software, empirical model fitting or benchmark was executed.

Artificial Intelligence Ontology (AIO) Grounding

Mapped AIO Classes

AIO Target Class	Mapping Relation	Mapping Rationale
`AIO:UnsupervisedLearning` Unsupervised Learning	related_match	These algorithms fit additive latent factors from a supplied data matrix without target labels. The AIO target is a learning task, so the relationship does not assert algorithm/task equivalence or subclass membership.

Evidence Sources & Primary Literature

1 Source

Source ID	Publication / Document	Type / Access	Reference & Checksum
`method-source`	Algorithms for Non-negative Matrix Factorization Daniel D. Lee, H. Sebastian Seung	primary paper full_text	ID: https://papers.nips.cc/paper_files/paper/2000/hash/f9d1152547c0bde01830b7e8bd60024c-Abstract.html sha256:d943865213cb…

Curation Provenance

Curator: Codex

Method: ai_assisted

Model: GPT-6

Created: 2026-10-12T01:49:01Z

Updated: 2026-10-12T01:49:01Z

Source File: data/curated/LeeSeungMultiplicativeUpdates.yaml