The Finite Primitive Basis Theorem for Computational Imaging: Formal Foundations of the OperatorGraph Representation

This paper establishes the Finite Primitive Basis Theorem, proving that any computational imaging forward model can be constructively approximated by a minimal, typed directed acyclic graph composed of exactly 11 canonical primitives, thereby providing the mathematical foundation for a unified Physics World Model framework.

The Gist

Imagine you are trying to describe every possible way a camera works. You have a camera that takes pictures of the human body (MRI), one that sees through fog (radar), one that uses X-rays (CT scan), and even one that looks at the quantum state of atoms.

Traditionally, scientists treat each of these cameras as a completely unique, magical black box. To fix a bug in an MRI, you need a specialist who only knows MRI code. To build a new type of camera, you have to write all the math from scratch. It's like having a different language for every single tool in a toolbox.

This paper says: "Stop. We can speak one universal language for all of them."

Here is the simple breakdown of what the author, Chengshuai Yang, discovered.

1. The "Lego" Discovery

The author proves that every single imaging system in existence (from hospital scanners to scientific microscopes) is actually just a specific arrangement of 11 basic building blocks.

Think of these 11 blocks as the "Lego bricks" of physics. No matter how complex the final machine is, it is just these 11 bricks snapped together in a specific order.

2. The 11 Magic Bricks

Instead of writing complex equations for every new camera, you just need to know how to use these 11 primitives:

1. Propagate: Moving a wave through empty space (like light traveling from a star to your eye).
2. Modulate: Putting a mask or pattern over the light (like a stencil).
3. Project: Flattening a 3D object into a 2D shadow (like a shadow puppet).
4. Encode: Turning spatial information into a frequency code (like how MRI machines "listen" to atoms).
5. Convolve: Blurring or sharpening an image (like a lens focusing light).
6. Accumulate: Adding things up (like counting how many photons hit a sensor over time).
7. Detect: Turning a physical wave into a digital number (the moment the camera "clicks").
8. Sample: Picking out specific pieces of data (like taking a few pixels from a huge photo).
9. Disperse: Spreading things out by color or wavelength (like a prism turning white light into a rainbow).
10. Scatter: Bouncing things off each other and changing their energy (like a billiard ball hitting another).
11. Transform: Applying a simple math rule to every pixel individually (like making a photo "brighter" or "darker" everywhere at once).

3. The "Recipe" (The DAG)

The paper introduces a concept called a Directed Acyclic Graph (DAG). In simple terms, this is just a flowchart or a recipe.

• The Old Way: Every camera had its own secret recipe written in a different language.
• The New Way: Every camera is just a flowchart made of the 11 Lego bricks.
  • Example: A CT scanner is just: Project (take a shadow) $\rightarrow$ Detect (measure it) $\rightarrow$ Transform (fix the math).
  • Example: An MRI is: Modulate (spin the atoms) $\rightarrow$ Encode (listen to the signal) $\rightarrow$ Sample (pick data points) $\rightarrow$ Detect.

Because they all use the same 11 bricks, you can now write one computer program that understands any camera. If you want to fix a bug in an MRI, you can use the same tools you use to fix a CT scanner.

4. Why This is a Big Deal

The author didn't just guess this; they proved it mathematically.

• It's Complete: You can build any imaging system with these 11 bricks. You don't need a 12th brick.
• It's Minimal: If you remove even one of the 11 bricks, you can no longer build certain cameras. For example, if you remove "Scatter," you can't build a Compton camera (used for nuclear imaging). If you remove "Project," you can't build a CT scanner.
• It Handles the Weird Stuff: Even the most complicated, non-linear physics (like when light bends in strange ways or quantum effects kick in) can be broken down into these bricks. The "non-linear" parts are just special cases of the "Transform" brick or a loop of the "Scatter" and "Propagate" bricks.

5. The Real-World Impact

Imagine if every car manufacturer had to invent their own engine, transmission, and steering wheel from scratch. Now imagine someone proves that every car in the world is actually just a different arrangement of 11 standard parts.

• For Doctors: They could use the same software to calibrate an MRI, a CT scan, and a new experimental scanner.
• For Engineers: Designing a new camera becomes as easy as snapping Lego bricks together. You don't need to invent new math; you just pick the right 11 bricks and connect them.
• For AI: Artificial Intelligence can learn to "see" using this universal language, making it much easier to train AI to diagnose diseases across different types of medical scans.

The Bottom Line

This paper is the "Periodic Table of Elements" for imaging. It tells us that the universe of cameras isn't a chaotic mess of unique inventions. It is a structured, finite system built from exactly 11 fundamental physical operations. Once you know the 11, you can understand, build, and fix any imaging system in the world.

Technical Summary

1. Problem Statement

Computational imaging forward models (mapping physical scenes to measurements) are traditionally implemented as monolithic, modality-specific codes (e.g., separate codebases for MRI, CT, and coded aperture cameras). This fragmentation hinders the sharing of diagnostic tools, calibration algorithms, and reconstruction pipelines across different imaging modalities. While previous frameworks attempted to unify these via Directed Acyclic Graphs (DAGs), there was no formal proof that a finite, domain-independent set of primitive operators could represent all imaging modalities (linear and nonlinear) with bounded error. The central question addressed is: Is there a minimal, universal library of physical operators sufficient to construct an $\epsilon$-approximate forward model for any imaging system?

2. Methodology

The paper establishes a rigorous mathematical framework to answer this question through the following steps:

• Definition of the Operator Class ($\mathcal{C}_{img}$): The authors define a precise class of imaging forward models that includes all clinical, scientific, and industrial modalities. This class allows for finite sequential-parallel compositions of operators that are either bounded linear or Lipschitz-continuous pointwise nonlinear. It accommodates various physical carriers (photons, electrons, spins, acoustic waves, particles) and regimes (including relativistic and quantum).
• The Primitive Library ($\mathcal{B}$): The authors propose a library of 11 canonical primitives that serve as the nodes in a typed DAG. These are:
  1. Propagate ($P$): Free-space wave propagation (angular spectrum).
  2. Modulate ($M$): Element-wise multiplication (masks, sensitivities).
  3. Project ($\Pi$): Line-integral projection (Radon transform).
  4. Encode ($F$): Fourier encoding (k-space sampling).
  5. Convolve ($C$): Spatial convolution (PSFs).
  6. Accumulate ($\Sigma$): Summation over axes (spectral/temporal integration).
  7. Detect ($D$): Carrier-to-measurement conversion (5 canonical response families: linear, log, sigmoid, intensity-square, coherent).
  8. Sample ($S$): Index-set selection (undersampling).
  9. Disperse ($W$): Wavelength-dependent spatial shift.
  10. Scatter ($R$): Direction/energy change (inelastic scattering).
  11. Transform ($\Lambda$): Pointwise nonlinear functions (attenuation, phase wrapping, saturation).
• Constructive Proof: The authors prove the Finite Primitive Basis Theorem by decomposing any $H \in \mathcal{C}_{img}$ into six structural physics stages (Propagation, Elastic Interaction, Inelastic Scattering, Pointwise Nonlinearity, Encoding/Projection, Detection). They provide six "Realization Lemmas" showing that each stage can be represented by one or a finite composition of the 11 primitives with bounded approximation error.
• Minimality Proof: They prove that the library is minimal; removing any single primitive renders at least one specific modality unrepresentable within the error bounds.
• Nonlinearity Analysis: The paper categorizes all imaging nonlinearities into two types: Pointwise (handled by $\Lambda$) and Self-consistent iterations (e.g., multiple scattering, handled by unrolling linear primitives like $P$ and $R$).

3. Key Contributions

• The Finite Primitive Basis Theorem (Theorem 24): A formal proof that every imaging forward model in $\mathcal{C}_{img}$ admits an $\epsilon$-approximate representation as a typed DAG using exactly 11 primitives.
• Proof of Minimality (Proposition 31): Demonstration that the library of 11 primitives is necessary; no subset can represent the full scope of imaging modalities.
• Unified Nonlinearity Framework: A structural classification showing that all imaging nonlinearities fall strictly into pointwise functions or iterative linear compositions, eliminating the need for arbitrary neural network approximators.
• Extension Protocol: A formal procedure for adding new primitives if a modality is encountered that cannot be represented by the current library, ensuring the framework remains future-proof.
• OperatorGraph Intermediate Representation (IR): A formal definition of a typed DAG where edges carry physical metadata (shape, units, dtype), enabling modality-agnostic algorithm design.

4. Results

• Empirical Validation: The theorem was tested on 31 linear modalities (including CASSI, MRI, CT, Ptychography, OCT, and Electron Ptychography).
  • Fidelity: All modalities achieved a mean relative fidelity error ($e_{img}$) of < 0.01 (often $< 10^{-3}$).
  • Complexity: The decompositions required at most 5 operator nodes and a graph depth of 5, well within the prescribed bounds ($N_{max}=20, D_{max}=10$).
• Nonlinear Validation: Constructive DAG decompositions were provided for 9 nonlinear modalities (e.g., Polychromatic CT with beam hardening, Phase-wrapped MRI, Nonlinear Ultrasound). These were successfully represented using the $\Lambda$ primitive or unrolled linear iterations.
• Closure Test: A "held-out" test confirmed that new modalities (like Compton scattering) could be integrated. Initially, Compton scattering failed with the 9-primitive library ($e_{img} = 0.34$), necessitating the addition of the Scatter ($R$) primitive, which then brought the error below 0.01.
• Basis Saturation: The growth of the primitive library saturated at 11 primitives after analyzing 40 modalities, confirming the theoretical prediction that no new fundamental physics stages exist beyond the six identified categories.

5. Significance

• Mathematical Foundation for Physics World Models: The paper provides the theoretical bedrock for the "Physics World Models" (PWM) framework, enabling the creation of universal imaging algorithms that are not tied to specific hardware.
• Interoperability: By reducing all imaging systems to a common set of 11 primitives, the framework allows for the seamless transfer of reconstruction algorithms, calibration tools, and diagnostic logic across vastly different modalities (e.g., from MRI to X-ray CT).
• Efficiency and Interpretability: Unlike universal approximators (like deep neural networks) which are black boxes, this approach uses physically typed primitives, ensuring physical interpretability and computational efficiency.
• Completeness: The proof that the library is both sufficient and minimal suggests that the "alphabet" of computational imaging is finite and complete, implying that future imaging modalities will likely be compositions of existing physics rather than requiring fundamentally new mathematical operators.

In summary, this paper transforms computational imaging from a collection of ad-hoc, modality-specific implementations into a unified, mathematically rigorous discipline governed by a finite basis of physical operators.