The solver that knows no symmetry

The formula that has the answer already ends by naming three descendants of the tangent formula and lists all three under not owned. The last of them is four lines long:

compute a map, reverse the sign of everything below a small threshold, transform back, keep the new phases and the measured amplitudes, repeat.

It has no triplets in it, no probability distribution, no starting set, and no space group. It was published in 2004 by Gábor Oszlányi and András Sütő, and it works. This is what owning it means.

The whole algorithm #

A diffraction experiment measures intensities, so the phases are lost and half of every measurement is thrown away before it is written down. Every method of getting them back works by imposing something known about the density that the amplitudes alone do not enforce.

Charge flipping imposes almost nothing, and that is the surprise. In outline:

1. Take the measured amplitudes with whatever phases are in hand — random ones, to begin with — and transform to a map.
2. Wherever the map is below a small positive threshold δ, reverse its sign. Everything above δ is left exactly as it is.
3. Transform the flipped map back, and keep only its phases.
4. Put the measured amplitudes back on those phases, and go round again.

The only fact about matter anywhere in that loop is in step two: electron density is positive, so a region where the map is near zero or negative is a region where the map is wrong, and turning it upside down is a crude way of saying so. There is no atomicity, no resolution assumption, no chemistry, and — the point this essay is named for — no symmetry.

One detail in the data matters and is easy to get wrong. The reflection at zero angle is not measured by any experiment, and it is left free here: the transform of the flipped map supplies it afresh each cycle. Supplying it instead pins the map’s mean and the iteration converges to something with the right average density and no contrast.

An agreement figure that is perfect when nothing happens #

The natural way to watch such an iteration is the R-factor between the amplitudes the current map produces and the amplitudes that were measured. That number has to be taken at the right moment, and the wrong moment is very inviting.

Taken after the amplitudes are imposed, the R-factor is identically zero for ever, because imposing them is precisely what makes the two agree. A solver watching that number would report perfect convergence from its first cycle for ever.

The refusal that guards it is sharper than a comment and worth stating as a result in its own right. Run the same loop with flipping switched off, so that the iteration is the identity map. Every cycle reproduces the measured amplitudes exactly, so R is zero at every cycle — and the map is noise. An agreement figure is evidence about the step that was taken and about nothing else, and here is a case where a perfect one accompanies a complete failure.

The one threshold on this site #

Everything else this collection decides is decided in integers. A pattern has a symmetry or it does not; a lattice permits a five-fold rotation or it does not; a set of translations closes or it does not. δ is different. It is a real parameter, the algorithm’s behaviour depends on it, and no principle picks a value.

Near-symmetry, and the tolerance that is not here sets out what to do in that situation: the moment a threshold is introduced, the answer stops being a fact about the object and becomes a fact about the threshold as well — so the dependence is measured and published rather than a working value being quoted.

The window is narrow and it is a window rather than a direction, which is the interesting shape. Too small a δ flips almost nothing and the iteration is nearly the identity — the failure above, approached continuously. Too large a δ flips almost everything, including the peaks that are the structure, and each cycle destroys what the last one built. The value has to be small enough to leave the peaks alone and large enough to matter, and there is no way to know in advance where that is except by trying.

The threshold is measured here in units of the map’s own standard deviation, which is the only scale the calculation has: the amplitudes arrive on an arbitrary scale, and a threshold in absolute units would be a statement about the units.

The group comes back out #

The algorithm is run in P1. It imposes no operation, treats every reflection as independent, and is told nothing about the arrangement that produced the data. The structures it is given here are not in P1 at all.

This is the move this collection makes in every pattern figure, pointed in an unusual direction. Ordinarily a pattern is generated from a group, the group is forgotten, and the detector rediscovers it. Here the group was never in the calculation at all: it was in the amplitudes, and the solver — which cannot see it and does not use it — produced a map that has it.

Two details keep that from being a trick.

The peaks have to be moved to their own centroid first. A symmetry element is somewhere rather than nowhere, and the solved map sits at whatever origin the iteration wandered into; a detector that looks only for operations about the origin finds nothing in a perfectly correct answer. That is the same fact the normaliser essays are about, met from the other side.

And the detector needs a tolerance, so the answer needs a control. A map on a grid locates a peak no better than a grid step, so the exact detector used everywhere else on this site does not apply and the one with a tolerance does. A generous tolerance manufactures symmetry — which is exactly what near-symmetry measures — so the census includes a structure built with no symmetry at all, and it reports one operation at every tolerance on the ladder. Without that row the other three would prove nothing.

What it does not need, compared with what came before #

The methods this rung sits above need a great deal more.

The tangent formula needs normalised structure factors, which needs a scale and a temperature factor, which needs Wilson statistics; it needs triplets, which needs a resolution good enough for atomicity; it needs an origin fixed by hand, because a phase set does not fix its own origin and a search that does not fix one is searching a continuum of equivalent answers; and it needs a figure of merit to rank many starts, because most of them fail.

Charge flipping needs the amplitudes and a threshold. It fixes no origin — it wanders to one and stays there, which is why every comparison here is minimised over origin and handedness. It ranks nothing, because it does not need many starts. It is told no symmetry, which is why it can be run on a structure whose space group is not yet known, and that is its practical advantage over everything before it: a structure determination usually begins by guessing the space group from the systematic absences, and a wrong guess is a wrong answer arrived at with confidence.

Why alternating between two spaces works at all #

The two constraints in this problem live in different places, and neither is expressible where the other is.

In the map, the useful facts are local: density is positive, structures are made of atoms, most of the cell is empty. Saying any of that about a transform takes an infinite number of coupled conditions.

In the transform, the useful fact is that the amplitudes are known and the phases are not. Saying that about a map is equally hopeless.

So an algorithm that alternates can impose each constraint where it costs nothing, and this is the shape of every modern solver. Charge flipping is the minimal member of the family — its real-space step is the crudest imaginable — which is what makes it a good object to compute with, and its success is evidence that the real content of the method is the alternation rather than the sophistication of either half.

What the iteration is actually doing #

The loop has a fixed point that is not the answer, and understanding why it is escaped is most of the intuition available about the method.

Set the phases to the true ones and the map is the structure: positive peaks on an empty background, with nothing at all below the threshold except the small ripples that a truncated sum leaves — the ones a resolution-limited map always carries. Flipping inverts those ripples and leaves the peaks, which changes the transform slightly, and the phases that come back are almost the ones that went in. The true solution is very nearly stationary, which is what makes it a place the iteration can rest.

Start instead from random phases and the map is noise of both signs, half of it below the threshold. Flipping inverts that half, and the flipped map is not noise: it is noise with a bias towards positive values, because the operation cannot produce anything below −δ. That bias is a weak push towards a positive density, and it is the entire driving force. Each cycle adds a little of it, and after some tens of cycles the peaks that survive are the ones consistent with all the amplitudes at once.

The R-factor curve above records that as a fall and then a plateau, and the plateau’s height is worth a word. It settles at about a third rather than at zero, because the map is on a coarse grid and the data are truncated, so the density the iteration can represent is not the density that produced the amplitudes. A structure is nevertheless recovered to within a grid step. The plateau’s level says nothing about whether the structure is right — only the fall does, and only comparison with the true atoms settles the rest.

What is being imposed, and where #

It is worth setting out the two constraints as a pair, because the algorithm is nothing but their alternation and the asymmetry between them is the whole reason it works.

The amplitude constraint is exact, hard, and lives in reciprocal space. Each measured |F| is a number the answer must reproduce, and imposing it is one division per reflection. It is also incomplete: infinitely many maps have the right amplitudes, and the set of them is enormous.

The density constraint is approximate, soft, and lives in real space. “Density is positive” is true; “everything below δ is wrong and should be negated” is not a theorem about anything — it is a nudge in the direction of positivity that happens to be cheap to apply and happens to have a fixed point near the answer.

An algorithm that alternates between a hard constraint in one space and a soft one in the other is a projection method, and this collection has met the structure before without naming it: solving from the vector set alternates between the Patterson map and the superposition condition, and the tangent formula alternates between phases and their relations without ever leaving reciprocal space — which is why it has nowhere to put a statement about the map.

The reason the soft constraint may be crude is that it is applied hundreds of times. A single flip moves the map a little way towards positivity; a hundred and fifty of them, each followed by an exact reimposition of the amplitudes, accumulate into a strong condition. That is a general principle of such methods and it is the one thing about charge flipping that transfers: the useful constraint is not the sophisticated one, it is the one that can be applied cheaply enough to be applied often.

Where the exactness stops #

Computed here: amplitudes from a small structure with the zero-angle reflection withheld; the iteration itself; the R-factor before imposition, cycle by cycle, with the identity iteration as a control; the agreement between the final map’s peaks and the atoms, minimised over origin and handedness and reported in grid steps; the success rate at eight thresholds from four starts each; and the operations detected in four solved maps at six tolerances, with a symmetry-free control.

Not claimed: that this is how a structure is solved. The data here are exact amplitudes from point atoms with no noise, no absorption, no missing reflections and no disorder, and every one of those is a real obstacle. A hundred and fifty cycles on a twelve-atom cell is a demonstration of a mechanism.

And the threshold remains a threshold. The window measured above is a property of these data at this resolution. It is not a value to carry to another structure, which is why the figure reports a curve rather than a number.

Who found it, and when #

Oszlányi and Sütő published charge flipping in 2004 in Acta Crystallographica, in a paper four pages long, and the reception was some disbelief: the method has no free parameters beyond the threshold, uses no chemical knowledge, and outperformed established direct methods on structures that had defeated them. It was extended to powder data, to incommensurate structures — where the extra dimension makes it periodic and the same iteration runs in superspace — and to electron diffraction within a few years.

The precedents are older and come from outside crystallography: Gerchberg and Saxton’s algorithm for electron microscopy in 1972 and Fienup’s for optical phase retrieval in 1982 alternate between two spaces in exactly this way. What was new in 2004 was the flipping step, which is a much weaker constraint than the ones those methods use and turns out to be enough.

Where the ladder goes next #

Back, to what this replaced. Three phases that do not move when the origin does is the invariant everything statistical is built on, and the formula that has the answer already is the method that has it as a fixed point and cannot find it.

Sideways, to the map that needs no phases at all: the Patterson, and solving from the vector set, which is the pre-computational answer to the same question.

And to the reason the symmetry recovered above is worth having. The reflections that are not there is how a space group is normally assigned, where the experiment runs out is why the assignment is sometimes ambiguous — and a solver that needs no assignment at all is a way past both.

The structures it made solvable #

Knowing no symmetry sounds like a cost the method pays for its simplicity. It is the reason the method was adopted, and the cases that show why are the ones no earlier solver could reach.

An incommensurately modulated structure has no three-dimensional space group, so every method requiring one is inapplicable to it as written. Its description lives in four dimensions or more, where the unknown is not a set of atomic positions but the shape of an atomic surface — a continuous object, with far more parameters than a list of coordinates.

Charge flipping does not care. The loop is a Fourier transform, a threshold and a sign change, and every one of those runs in any number of dimensions on any lattice. Run it in superspace with the measured main reflections and satellites, and what comes back is a density in four dimensions whose atomic surfaces are read off directly rather than modelled.

That was the method’s first striking success and it is what established it. The same applies to quasicrystals, whose six-dimensional descriptions are worse in the same way, and to structures whose space group is in doubt — since a solver that assumes none cannot be misled by a wrong one.

The general shape is worth extracting. Every method that uses symmetry buys a smaller problem and pays by needing to be told which symmetry. A method that uses none has a larger problem and no such dependency, and where the symmetry is unknown, absent, or in more dimensions than three, the second trade is the better one.