In many modern sensing problems—from imaging black holes to reconstructing the shape of a protein—we cannot measure the signal of interest directly. Instead, we capture indirect, often non-linear observations like the intensity of a light wave or the magnitude of a Fourier transform. Mathematically, these problems are framed as finding a signal that minimizes the "misfit" between our model and the data.
However, these objective functions are almost always non-convex. In a convex world, any local valley is the lowest point in the entire landscape. In the non-convex world of signal recovery, the landscape is a jagged mountain range filled with "spurious local minima"—false solutions that look like the target but are physically incorrect.
The Trap of Local Minima
The fundamental challenge in non-convex recovery is stagnation. As Pengwen Chen, Albert Fannjiang, and Gi-Ren Liu observe in Phase Retrieval with One or Two Diffraction Patterns by Alternating Projection with Null Initialization, iterative algorithms frequently stall because they lack the "global view" to see that a better solution exists elsewhere.
This isn't just a theoretical nuisance; it’s a physical bottleneck. In seismic imaging, Björn Engquist and Yunan Yang describe this as "cycle-skipping" in Seismic Imaging and Optimal Transport. When an algorithm tries to match two waves, it might align the wrong peaks, getting trapped in a local minimum because the point-by-point distance ($L^2$ norm) doesn't understand the global structure of the signal.
Escaping the Traps via Initialization
If the landscape is full of traps, the simplest solution is to start the search as close to the "global valley" as possible. This has led to a surge in specialized initialization strategies.
In Optimal Rates of Convergence for Noisy Sparse Phase Retrieval via Thresholded Wirtinger Flow, T. Tony Cai and Xiaodong Li demonstrate that a "spectral initialization"—using the eigenvectors of the data matrix—can place the algorithm within the "basin of attraction" of the true signal. Once inside this basin, the problem behaves locally like a convex one, allowing simple gradient-based methods to converge to the global optimum.
Designing Benign Landscapes
A more radical approach is to change the landscape itself. Researchers are increasingly looking for conditions under which the optimization landscape is "benign"—meaning all local minima are actually global minima.
Lingzhou Xue, Zheng Zhong, and Zhong Zheng explore this in Smoothed Robust Phase Retrieval. By applying smoothing techniques to the loss function, they can mathematically prove that the landscape becomes free of spurious local minima, allowing gradient descent to succeed from any random starting point.
Similarly, Tyler Maunu and Martin Molina-Fructuoso show in Acceleration and Implicit Regularization in Gaussian Phase Retrieval that certain algorithms possess "implicit regularization." The algorithm's own path through the landscape keeps it away from "nasty" regions (like saddle points or negative curvature) and guides it toward the global solution.
Lifting and Convex Relaxation
When the non-convexity is too severe to navigate, researchers sometimes "lift" the problem into a higher-dimensional space where it becomes convex.
In Blind Deconvolution using Convex Programming, Ali Ahmed 0004 and Justin Romberg show that the non-linear problem of separating two unknown signals can be recast as a linear matrix recovery problem. By solving for a matrix rather than a vector, they transform a heuristic-driven search into a principled convex optimization with rigorous guarantees of success. Henrik Ohlsson uses a similar "lifting" logic in Quadratic Basis Pursuit to handle second-order non-linearities.
Why It Works: The Geometry of Information
The recurring insight across these 142 papers is that the difficulty of the optimization landscape is tied to the sample complexity. As K.Y. Liu and Lei Wu detail in The Local Landscape of Phase Retrieval Under Limited Samples, when we have very few measurements, the landscape is "broken"—it loses local convexity even near the target.
However, as we add more data or incorporate structural priors like sparsity—as seen in Hadamard Wirtinger Flow for Sparse Phase Retrieval by Patrick Rebeschini and Fan Wu 0010—the "spurious" valleys begin to disappear. The research direction is moving toward a unified theory: identifying the exact point where the geometry of the data makes the non-convexity of the problem vanish.