Escaping Local Minima in Non-Convex Inverse Problems

49 concepts50 papers1 proposal

When reconstructing a signal from physical measurements, we are solving an inverse problem. If the measurement process is linear and clean, the optimization landscape is convex—a smooth, predictable bowl where every local step downward leads directly to the global optimum.

However, many real-world sensing modalities are fundamentally non-linear. When we lose phase information, quantize measurements to single bits, or try to separate mixed signals, the mathematical landscape warps. It becomes non-convex, jagged, and populated with false valleys—local minima—where standard optimization algorithms get trapped, resulting in corrupted or entirely incorrect reconstructions.

To solve these problems reliably, we must understand why these traps form and how modern algorithmic frameworks either bypass, smooth, or break through them.


The Geometry of the Trap

Why do physical inverse problems naturally generate non-convex landscapes? The complexity typically stems from three structural archetypes:

1. Lost Phase Information (Quadratic Measurements)

In fields like X-ray crystallography or astronomy, sensors record only the intensity (magnitude) of a signal, discarding its phase. Mathematically, this means our observations $y$ relate to the hidden signal $x$ via quadratic equations: $y = |Ax|^2$.

As noted by Netrapalli et al. and Maillard et al., this squaring operation introduces a fundamental symmetry ambiguity (e.g., $x$ and $-x$ yield identical measurements). This splits the optimization landscape into multiple symmetric valleys separated by high ridges and saddle points, creating numerous opportunities for iterative solvers to stall.

2. Bilinear Interactions (The Chicken-and-Egg Problem)

In blind deconvolution or unlabeled sensing, we must recover two interacting unknowns simultaneously—such as a signal and the unknown physical distortions of the sensor itself.

Because the objective function depends on the product of two unknowns ($x \times h$), the landscape is bi-convex but globally non-convex. As Aghasi et al. and Wright et al. demonstrate, this coupling causes features to overlap and distort the error surface, trapping standard alternating minimization algorithms in spurious local optima where the two variables are incorrectly aligned.

3. Periodic and Quantized Distortions

When signals pass through periodic non-linearities (like sinusoidal wave modulations) or cheap 1-bit analog-to-digital converters, the loss surface becomes highly jagged or fragmented into flat plateaus.

Work by Soltani et al. shows that periodic observations create infinite repeating local minima, while Eamaz et al. point out that coarse quantization destroys the smooth gradient information needed for algorithms to navigate toward the true signal.


Strategy 1: Convex Relaxations (Flattening the Landscape)

The most radical way to escape a jagged landscape is to change the landscape entirely. Instead of optimizing over the original non-convex space, we can "relax" the problem into a higher-dimensional convex space where local minima cannot exist.

Non-Convex Landscape:   \___/  \___/  \___/  (Trapped in local minima)
                                 v
Convex Relaxation:      \_________________/  (Single global optimum)

For the phase retrieval problem, the PhaseCut framework developed by Waldspurger et al. and further analyzed by Fogel et al. reformulates the quadratic objective as a complex semidefinite program. By lifting the problem into a matrix space, the jagged error surface is flattened into a perfectly convex bowl, guaranteeing that any standard descent method will find the global solution.

Similarly, for bilinear inversion, the $\ell_1$-BranchHull framework introduced by Aghasi et al. bypasses non-convex traps by working directly within a convexified parameter space, providing rigorous recovery guarantees without requiring sensitive initial guesses.


Strategy 2: Exploiting Benign Geometry and Smart Initialization

Convex relaxations are mathematically elegant, but lifting problems into higher dimensions is computationally expensive. If we want to solve the non-convex problem directly in its natural parameter space, we must exploit benign geometry.

Many non-convex landscapes are not uniformly terrible. Often, they possess a wide, clean "basin of attraction" around the true global minimum. If an algorithm can land inside this basin, the problem behaves locally as if it were convex.

               Saddle Point
                  _/\_
                 /    \
  Local Minimum /      \   Basin of Attraction
      \___/____/        \________\___/________/
                                Global Minimum

Spectral Initialization

To find this basin, researchers use spectral methods to construct a highly educated first guess. Netrapalli et al. proved that a spectral initialization provides a provable guarantee of landing within the basin of attraction for alternating minimization algorithms, ensuring subsequent steps converge to the true signal.

Global Convergence from Random Guesses

Remarkably, a precise statistical analysis can sometimes reveal that the landscape is globally benign. Chen et al. proved that for phase retrieval, vanilla gradient descent can succeed even when initialized completely at random.

Using a "leave-one-out" statistical analysis, the authors demonstrated that the underlying loss surface has a unique structure: all local minima are actually global minima, and every single saddle point possesses a direction of negative curvature. Because there are no true local traps, standard gradient descent can naturally slide past saddle points and find the global solution.

Furthermore, Maunu et al. showed that accelerated gradient methods benefit from an implicit regularization that naturally keeps the optimization path bounded within these well-behaved geometric regions.


Strategy 3: Dynamic Landscape Smoothing and Algorithmic Kicks

When the physical sensing model is too complex to guarantee a benign geometry, the algorithm must actively manipulate the landscape or use physical constraints to break out of stagnation.

Curvature-Guided Smoothing

When tracking overlapping signals with complex phase and amplitude variations, the error surface is riddled with narrow, steep traps. To counter this, Dutta et al. developed a Curvature-guided Langevin Monte Carlo method.

By calculating the local curvature of the landscape on the fly, the algorithm adaptively smooths out narrow local minima while preserving the broad valleys that lead to the global optimum, allowing the solver to glide through otherwise impassable terrain.

Weaponizing Physical Artifacts

In optical imaging, iterative algorithms often stall due to the "twin-image" problem—a mathematical artifact where a mirror image of the signal creates a persistent local minimum.

Instead of trying to avoid this trap, Areeba Fatima demonstrated that an algorithm can mathematically exploit the structure of this twin-image artifact to deliver a calculated "kick" to the optimization process. This intentional disruption forces the stalled solver out of the local minimum, clearing the path to high-fidelity phase reconstruction.

Key Foundational Work

Solving Inverse Problems with Piecewise Linear Estimators: From Gaussian Mixture Models to Structured Sparsity (2010) — contributed 1 concept elements to this direction.
Restricted Isometry Property and lp sparse recovery failure (2009) — contributed 1 concept elements to this direction.
Statistical Mechanical Analysis of a Typical Reconstruction Limit of Compressed Sensing (2010) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_non_convex_optimization_landscape_local__ab9f5ab9,
  title = {non-convex optimization landscape (local minima entrapment)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-convex-optimization-landscape-local-minima-entrapment/rdr_ab9f5ab90a2a41eca88c29e830203fc2},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_non_convex_optimization_landscape_local__ab9f5ab9_v1,
  title = {non-convex optimization landscape (local minima entrapment)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-convex-optimization-landscape-local-minima-entrapment/rdr_ab9f5ab90a2a41eca88c29e830203fc2/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake