Space-Alternating Generalized Expectation Maximization
Algorithms AIMech:SpaceAlternatingGeneralizedExpectationMaximization DRAFT
Aliases: SAGE Algorithm, Space-Alternating GEM
A generalized expectation-maximization method that updates selected parameter blocks using block-specific hidden-data spaces or valid objective-improvement surrogates, refreshing the conditional expectation or surrogate at the current estimate before the next block.
Identity Notes & Concept Scope
Fessler-Hero SAGE is an optimization method, distinct from AIMech:SparseAdditiveGenerativeModel, which already owns the bare SAGE alias. Qualified algorithm aliases are used here. The 1994 hidden-data construction and 1995 penalized/surrogate extension belong to this method family; SAGE1/2/3 Poisson choices are variants, not separate records. Unlike ordinary frozen-Q ECM, the construction refreshes each selected-block surrogate; AECM is a broader cycle/constraint framework. All 442 pinned AIO labels/scoped synonyms and 466 preceding native IDs, names and aliases were compared. The sole normalized search-term collision, bare SAGE, identifies the existing sparse additive text model; the new optimization method uses qualified aliases. Ignored-inclusive fixed-string searches of both full checkouts returned 436 and 459 line instances. Context windows for all 143 distinct normalized matched texts were inspected; duplicate ledger/review mentions, unrelated environment strings and the stochastic-EM lead do not establish these four method identities. All 225 semantic label/synonym rows and 17 annotated AIO nodes with outgoing edges were inspected; sixteen nodes were byte-verified unchanged after prior reading and UncertaintyBias was newly read. Thirty-one contextual YAMLs comprise 17 AIO and 14 native records, with 27 verified prior readings and four full new readings; the existing sparse text SAGE was also reread. Absence is bounded to this pin, maintained corpus and inspected neighborhood.
Claims & Grounded Evidence
4 Claims
Mechanism
#admissible-hidden-block
For active block S, keep the complementary parameters fixed at their current values. An admissible hidden space factors p(y,x;theta)=p(y|x;theta_complement)p(x;theta), with the observation channel independent of theta_S. Increase the conditional expected log p(x;theta) minus the penalty over that block, then carry the updated parameter forward and recompute for the next block. Different blocks need not combine into one common complete-data space. The 1995 extension uses the same block-ascent logic through a surrogate whose improvement lower-bounds actual objective improvement.
Mechanism
#poisson-current-projections
For Poisson means m_n=sum_j a_nj lambda_j+r_n with nonnegative coefficients, hold other coordinates at their current values. A valid shift z_k gives hidden means a_nk(lambda_k+z_k) and residual means r_n+sum_(j!=k)a_nj lambda_j-a_nk z_k. With e_k=sum_n a_nk y_n/m_n and positive a_dotk=sum_n a_nk, the unpenalized update is max((lambda_k+z_k)e_k/a_dotk-z_k,0). SAGE2 uses min_(a_nk>0)r_n/a_nk; SAGE3 can use min_(a_nk>0)(r_n+other current contributions)/a_nk. Freeze this shift within the block, update projected means immediately, and refresh the next block. A positive shift can revive an initially zero coordinate.
Limitation
#penalty-and-convergence-conditions
Valid block surrogates establish objective ascent, while parameter convergence needs additional conditions on curvature, continuity, bounded level sets and repeated coordinate coverage. The 1995 proof must be read with the author corrections: the mixed derivative is continuous in both arguments, and the final Lemma 6 argument is restricted to surrogates separable in their first argument. Its general statement is therefore not used as an unrestricted convergence guarantee for coupled multivariate block surrogates.
Limitation
#published-rate-and-scheduling-corrections
The 1994 statement suggesting restoration of old other-pixel estimates is superseded by the 1995 current-coordinate algorithm. The 1994 Theorem 2 proof incorrectly assumes real Gauss-Seidel eigenvalues; the author restricts that proof to the case in which a maximum-magnitude eigenvalue is real. This correction is a limitation of the proof, not by itself a counterexample to every speed comparison.
⚠️ Curated Limitations & Negative Results
- Strict concavity alone does not ensure uniformly positive Hessian curvature. The cited convergence conditions, boundary behavior and surrogate separability must be checked for the specific problem.
- The source’s Gaussian residual update in the 1994 author copy PDF 8 prints a plus sign after initializing residual=y-A theta. Maintaining that residual instead requires subtracting A times the parameter increment. This curator-identified sign inconsistency is checked in the saved finite example and is separate from the published author errata.
- Positive shift values require valid nonnegative hidden and residual means; zero measurement sensitivities are excluded from the minima and a zero column sum cannot use the displayed update. Penalized updates must optimize the penalty-aware surrogate, not blindly reuse the unpenalized formula.
- The 1995 errata also correct squared triangle-inequality terms, the factor in J, the sign in Eq 38 and the limiting subscript in Lemma 6. Neither objective ascent nor symmetry of a Hessian establishes a universal rate or global optimum.
- Both full papers and relevant author errata were inspected. Finite examples check scheduling, projection bookkeeping, boundary revival, a penalized scalar root and the Gaussian sign/eigenvalue issues; no author implementation, phantom study or clinical reconstruction was reproduced.
Artificial Intelligence Ontology (AIO) Grounding
Mapped AIO Classes
| AIO Target Class | Mapping Relation | Mapping Rationale |
|---|---|---|
AIO:MachineLearningTask
Machine Learning Task
|
related_match | This deterministic likelihood-fitting algorithm learns model parameters from data. The inspected AIO target denotes a learning process/task, so this is algorithm-to-task relatedness without an is-a or equivalence assertion. Statistical latent-data augmentation does not identify the pinned transformation-based DataAugmentation term. |
Evidence Sources & Primary Literature
3 Sources| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
method-source
|
Jeffrey A. Fessler, Alfred O. Hero
|
primary paper
full_text
|
ID: 10.1109/78.324732
sha256:3c3c323ebf2e…
|
penalized-source
|
Jeffrey A. Fessler, Alfred O. Hero III
|
primary paper
full_text
|
ID: 10.1109/83.465106
sha256:cc84e4a7f5b6…
|
author-errata
|
Jeffrey A. Fessler
|
official documentation
documentation
|
sha256:26b604621e35…
|
Curation Provenance
Curator: Codex
Method: ai_assisted
Model: GPT-6
Created: 2026-10-12T03:40:12Z
Updated: 2026-10-12T03:45:56Z