Math 2.0

Optics, electromagnetic theory Definition

Gerchberg–Saxton algorithm

Builds on Discrete Fourier transformArgument of a complex number

Definition

Let N≥1N \ge 1, let ℱ\mathcal{F} be the unitary discrete Fourier transform on ℂN\C^N, and let a,b∈[0,∞)Na, b \in [0, \infty)^N be given amplitudes. For z∈ℂz \in \C, let ph⁡(z)=z/∣z∣\operatorname{ph}(z) = z / \abs{z} if z≠0z \ne 0 and ph⁡(0)=1\operatorname{ph}(0) = 1, applied entrywise to vectors. The Gerchberg–Saxton algorithm starts from a phase vector p0∈ℂNp_0 \in \C^N with ∣(p0)j∣=1\abs{(p_0)_j} = 1 for all jj. For k=0,1,2,…k = 0, 1, 2, \dots it computes:

  1. gk=a⊙pkg_k = a \odot p_k, where ⊙\odot is the entrywise product;
  2. Gk=ℱgkG_k = \mathcal{F} g_k and Gk′=b⊙ph⁡(Gk)G'_k = b \odot \operatorname{ph}(G_k);
  3. gk′=ℱ−1Gk′g'_k = \mathcal{F}^{-1} G'_k and pk+1=ph⁡(gk′)p_{k+1} = \operatorname{ph}(g'_k).

It stops after a fixed number of steps or when the error Ek=∥∣ℱgk∣−b∥E_k = \norm{\abs{\mathcal{F} g_k} - b} is small.

Remarks

The aim is a vector gg with ∣g∣=a\abs{g} = a and ∣ℱg∣=b\abs{\mathcal{F} g} = b entrywise. The map ph⁡\operatorname{ph} keeps the argument of each entry and sets its modulus to 11. Each step projects onto the set of vectors with the prescribed amplitude in one of the two planes. Since ℱ\mathcal{F} is unitary, the error EkE_k does not increase from one step to the next. It need not tend to 00: the iteration can stagnate at a vector that does not solve the problem.

Example: take N=1N = 1, where ℱ\mathcal{F} is the identity, and a=b=(1)a = b = (1). Then g0=p0g_0 = p_0 already satisfies both constraints, and E0=0E_0 = 0.

Non-example: for N=1N = 1 with a=(1)a = (1) and b=(2)b = (2), no vector satisfies both constraints, and the iterates stay at error Ek=1E_k = 1. So a run of the algorithm does not certify that a solution exists.

Reading path

To understand this page from the ground up, read these 14 pages in order. The foundations come first.

Show the path as a graph
Complex exponential, concept, no evidence levelComplex exponentialconceptComplex numbers, object, no evidence levelComplex numbersobjectReal numbers, object, no evidence levelReal numbersobjectRoot of unity, concept, no evidence levelRoot of unityconceptSet bounded above, definition, no evidence levelSet bounded abovedefinitionReal and imaginary parts, definition, no evidence levelReal and imaginary pa…definitionDiscrete Fourier transform, definition, no evidence levelDiscrete Fourier tran…definitionSupremum, definition, no evidence levelSupremumdefinitionCompleteness axiom, statement, no evidence levelCompleteness axiomstatementExistence of square roots of nonnegative reals, statement, no evidence levelExistence of square r…statementSquare root, definition, no evidence levelSquare rootdefinitionModulus of a complex number, definition, no evidence levelModulus of a complex …definitionArgument of a complex number, definition, no evidence levelArgument of a complex…definitionGerchberg–Saxton algorithm, definition, no evidence levelGerchberg–Saxton algo…definition
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Complex exponential concept
  2. Complex numbers object
  3. Real numbers object
  4. Root of unity concept
  5. Set bounded above definition
  6. Real and imaginary parts definition
  7. Discrete Fourier transform definition
  8. Supremum definition
  9. Completeness axiom statement
  10. Existence of square roots of nonnegative reals statement
  11. Square root definition
  12. Modulus of a complex number definition
  13. Argument of a complex number definition
  14. Gerchberg–Saxton algorithm definition

Further reading

  1. Web https://en.wikipedia.org/wiki/Gerchberg%E2%80%93Saxton_algorithm
About this page
TagA9F03FK1BJ
URIm2://A9F03FK1BJ
Kinddefinition
WritingW0 stub
MSC78A46, 65T50
DefinesGerchberg–Saxton algorithm
UsesDiscrete Fourier transform, Argument of a complex number
Changed3 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)
  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.