About the Book
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.
Table of Contents:
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.
Review :
'Veit Elser's groundbreaking work on phase retrieval fundamentally altered the course of my research, directing it toward the study of the celebrated Douglas-Rachford algorithm, particularly in challenging scenarios where problems are nonconvex or without solutions. His book, Solving Problems with Projections, is poised to transform many lives. It masterfully combines cutting-edge research, textbook clarity, and engaging historical anecdotes. Elser's lucid and thought-provoking writing style will engage students, researchers, and projection enthusiasts alike. He generously shares his deep, implementable insights into his innovative Reflect-Reflect-Relax and Divide-and-Concur algorithms, empowering readers to find solutions for tough problems. This book is a brilliant, indispensable, compelling, and highly enjoyable read for anyone passionate about mathematics, physics, and the art of problem-solving.' Heinz Bauschke, SIAM Fellow and Professor of Mathematics, The University of British Columbia, Canada
'The book starts with an algorithm for phase retrieval–loosely, the problem of recovering entries of some arrays of complex numbers only knowing their absolute values. It is a variant of von Neumann's idea of alternating projections back and forth between sets A and B in a high-dimensional space, which incorporates potential for chaotic behavior. The subtlety and power of this idea leads to a fantastic tour through a wide range of increasingly demanding problems, including sudoku, geometry ('kissing spheres,' NP-hard tiling questions), Boolean satisfiability, quantum state tomography, mixed-integer linear programming, and neural network convergence. The choice of how the problem is set up can require cleverness, and this book is a grand 'User's Guide' to using these powerful and creative techniques, and it is filled with engaging and useful exercises that cover a broad spectrum of difficulty and application areas.' Joe Buhler, University of Minnesota, USA
'Elser's book is a tour-de-force, full of clever and original ideas for solving a wide variety of practical problems and entertaining puzzles. The arc of the book mirrors the general method presented, as new insights are successively revealed, until the reader has reached ultimate enlightenment. Extensive exercises challenge and engage the reader, to foster an understanding of how to implement these powerful algorithms. If you are a computer scientist, physicist, or applied mathematician, you should read this book!' Jonathan Yedidia, Senior Director of AI Research, Analog Devices, Boston, USA
'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
