Difference-map algorithm
It is a meta-algorithm in the sense that it is built from more basic algorithms that perform projections onto constraint sets.
From a mathematical perspective, the difference-map algorithm is a dynamical system based on a mapping of Euclidean space.
[2] Since these applications include NP-complete problems, the scope of the difference map is that of an incomplete algorithm.
Iterative methods, in general, have a long history in phase retrieval and convex optimization.
The use of this style of algorithm for hard, non-convex problems is a more recent development.
should not be equal to 0 but can have either sign; optimal values depend on the application and are determined through experimentation.
, the equality implies that we have found a common element to the two constraint sets.
Incomplete algorithms, such as stochastic local search, are widely used for finding satisfying truth assignments to boolean formulas.
The structure of the 2-SAT formula can be recovered when these variables are arranged in a table: Rows are the clauses in the 2-SAT formula and literals corresponding to the same boolean variable are arranged in columns, with negation indicated by parentheses.
Examples: It is a straightforward exercise to check that both of the projection operations described minimize the Euclidean distance between input and output values.
Moreover, if the algorithm succeeds in finding a point x that lies in both constraint sets, then we know that (i) the clauses associated with x are all TRUE, and (ii) the assignments to the replicas are consistent with a truth assignment to the original boolean variables.
To run the algorithm one first generates an initial point x0, say Using β = 1, the next step is to compute PB(x0) : This is followed by 2PB(x0) - x0, and then projected onto the other constraint, PA(2PB(x0) - x0) : Incrementing x0 by the difference of the two projections gives the first iteration of the difference map, D(x0) = x1 : Here is the second iteration, D(x1) = x2 : This is a fixed point: D(x2) = x2.
In the simple 2-SAT example above, the norm of the difference-map increment Δ decreased monotonically to zero in three iterations.
This contrasts with the behavior of Δ when the difference map is given a hard instance of 3-SAT, where it fluctuates strongly prior to the discovery of the fixed point.
As a dynamical system the difference map is believed to be chaotic, and that the space being searched is a strange attractor.
In phase retrieval a signal or image is reconstructed from the modulus (absolute value, magnitude) of its discrete Fourier transform.
For example, the source of the modulus data may be the Fraunhofer diffraction pattern formed when an object is illuminated with coherent light.
The projection to the Fourier modulus constraint, say PA, is accomplished by first computing the discrete Fourier transform of the signal or image, rescaling the moduli to agree with the data, and then inverse transforming the result.
This is a projection, in the sense that the Euclidean distance to the constraint is minimized, because (i) the discrete Fourier transform, as a unitary transformation, preserves distance, and (ii) rescaling the modulus (without modifying the phase) is the smallest change that realizes the modulus constraint.
To recover the unknown phases of the Fourier transform the difference map relies on the projection to another constraint, PB.
