Solving Problems with Projections
From Phase Retrieval to Packing

This book introduces a novel method for tackling complex problems by combining projections to pairs of constraints.

Veit Elser (Author)

9781009475525, Cambridge University Press

Hardback, published 19 June 2025

388 pages
25 x 17.7 x 2.7 cm, 0.84 kg

'Reader! There are algorithms undreamt of in your philosophy. They project and reflect, divide and concur. They solve Sudoku, help spheres kiss, and see the shapes of proteins without a microscope. They are simple yet chaotic, they work really well, and you need to learn about them! Be prepared: Veit Elser will teach you to think about problems and solutions in a beautiful new way.' Cris Moore, Santa Fe Institute, USA

It is a curious fact that even notoriously difficult computational problems can be expressed in the form of a high-dimensional Venn diagram, where solutions lie in the overlap of a pair of remarkably simple sets, A and B. The simplicity of these sets enables operations called projections that locate the nearest point of A, or B, starting anywhere within the high-dimensional space.  This book introduces a novel method for tackling complex problems that exploits projections and the two-set structure, offering an effective alternative to traditional, gradient-based approaches. Beginning with phase retrieval, where A and B address the properties of an image and its Fourier transform, it progresses to more diverse challenges, such as sphere packing, origami design, sudoku and tiling puzzles, data dimension reduction, and neural network training. The text presents a detailed description of this powerful and original approach and is essential reading for physicists and applied mathematicians.

1. Origins
2. Bipartisanship
3. Conspiracy theory
4. Projections
5. Reflect-reflect-relax
6. The user's guide
7. Divide and concur
8. Your turn
Notes
References
Index.

Subject Areas: Statistical physics [PHS]