Where Convex Lifting Breaks: Phase Retrieval with Shuffled Detectors

Phase retrieval means recovering a signal from intensity-only measurements, where each detector records $|a_i^* x|^2$ and the phase is lost. Its best-understood convex method, PhaseLift, works by "lifting" the unknown vector into a matrix. Every published guarantee assumes we know which detector produced which reading. In tiled detectors, fiber bundles, unsynchronized sensor arrays and jittered scans, that bookkeeping is partly lost: readings arrive shuffled within groups whose internal order is unknown. We propose to study phase retrieval when this correspondence is unknown, inside a structure we call a bipartite correspondence graph. The graph has one node per reading and one per detector, and an edge wherever that detector could have produced that reading. The case has a clean property. If you relax the unknown assignment to a doubly stochastic matrix (a nonnegative matrix whose rows and columns each sum to one) and lift the signal as PhaseLift does, the joint problem stays linear in both unknowns. The whole thing becomes one convex program.

Our core claim is that this convex program has an exactly characterizable bias, and that the shape of the correspondence graph controls it. By the Birkhoff–von Neumann theorem and the classical Hardy–Littlewood–Pólya majorization theorem, the relaxed assignment can be eliminated. What remains is PhaseLift with each equality constraint replaced by a majorization constraint, a requirement that predicted readings be an "averaged" version of the observed ones within each connected component of the graph. This tells us exactly when the relaxation collapses to an uninformative, high-rank average, which is the "convexity trap" that Graph Matching: Relax at Your Own Risk proved for graph matching. It also tells us how to escape the trap: with a non-convex refinement that seeks the corners of a permutohedron, the polytope whose vertices are all reorderings of the observed readings, warm-started from the biased convex solution. This ports their FAQ:D* principle from permutations to matrix lifting.

Core Claim

Let $y \in \mathbb{R}^m$ be the observed readings, $\mathcal{A}(X)_i = \mathrm{Tr}(a_i a_i^* X)$ the lifted measurement map, $X \succeq 0$ the lifted signal (ideally $xx^*$), and $D$ a doubly stochastic matrix supported on the edges of the correspondence graph $G$. The joint relaxation is

$$\min_{X \succeq 0,\; D} \ \mathrm{Tr}(X) \quad \text{s.t.} \quad D^\top y = \mathcal{A}(X),\ \ D \ge 0,\ D\mathbf{1}=D^\top\mathbf{1}=\mathbf{1},\ D_{ij}=0 \text{ for } (i,j)\notin G .$$

The constraint is linear in $(D, X)$ jointly, so this is a single semidefinite program. Suppose $G$ splits into complete bipartite blocks $B_1,\dots,B_K$ of size $s$; this is the "tile-swap" model. A vector $v$ equals $D^\top y$ for some doubly stochastic $D$ exactly when $v$ is majorized by $y$, meaning $v$ lies in the permutohedron of $y$. The program is therefore equivalent to

$$\min_{X \succeq 0} \ \mathrm{Tr}(X) \quad \text{s.t.} \quad \mathcal{A}_{B_k}(X) \prec y_{B_k}\ \ \text{for } k=1,\dots,K,$$

where $\prec$ means "has the same sum and is majorized by." Majorization is convex, because it is expressed through sums of the $j$ largest entries.

Two predictions follow. In the full-shuffle case ($s=m$) with Gaussian sensing, $\sum_i a_i a_i^* \approx m I$. The sum constraint then pins $\mathrm{Tr}(X)$ to nearly the same value for every feasible point, so trace minimization barely selects anything. A nearly isotropic $X \propto I$ is feasible, because its predicted readings are nearly constant and so majorized by any $y$ with the right sum. The relaxation should therefore return a diffuse high-rank matrix: a provable trap. As $s \to 1$, majorization becomes equality and we recover PhaseLift, which PhaseLift proves exact for $m \ge c_0 n \log n$ Gaussian measurements. Between these extremes lies a transition governed by the component structure of $G$, not by $m$ alone. Mapping that transition, theoretically where possible and empirically everywhere, is the first deliverable.

The same picture suggests the escape. All vertices of the permutohedron, and only those, satisfy $\|v\|_2 = \|y\|_2$; interior points have strictly smaller norm. Adding the non-convex requirement $\|\mathcal{A}_{B_k}(X)\|^2 = \|y_{B_k}\|^2$, or penalizing its violation, gives an "indefinite" problem whose optima sit at true reorderings, analogous to Lyzinski et al.'s indefinite graph-matching relaxation. As in their analysis, it should have many local minima. As in their FAQ:D* strategy, the convex solution $(D^*, X^*)$ should be an informative starting point even though it is wrong.

Relation to Prior Work

Three works motivate the gap. Graph Matching: Relax at Your Own Risk, with the solver from Fast Approximate Quadratic Programming for Graph Matching, proves that convex relaxation of permutations lands in the interior of the polytope of doubly stochastic matrices while the indefinite relaxation finds vertices. They also show that warm-starting the latter from the former works best on C. elegans and Wikipedia graphs. Their theory covers correlated Bernoulli graphs. We carry the convex-versus-indefinite contrast into a lifted, quadratic forward model, where the bias admits an exact majorization description instead of a probabilistic one. Compressed sensing with unknown sensor permutation treats linear measurements under unknown permutation. It reports that relaxing then projecting "fails to identify the correct permutation in most cases" and that exact branch-and-bound stays tractable only up to $M = 14$ sensors. We study the phaseless version, where the lifting adds a second relaxation, and we restrict the shuffle through a graph so that larger problems remain meaningful.

On the phase retrieval side, PhaseLift and Phase retrieval for imaging problems supply the lifting machinery. The latter's PhaseCut and its two-mask molecular diffraction experiments give us a structured measurement setting. Both assume known correspondence. Phase Retrieval for Binary Signals: Box Relaxation and Uniqueness is the closest positive result: it uses an extreme-point argument to show a box relaxation is exact for binary signals. Our majorization argument is in the same spirit, but here it shows the opposite, a relaxation that is provably loose, together with how loose. Phase Retrieval using Alternating Minimization constrains the design. Its guarantees need a spectral initialization built from $\sum_i y_i a_i a_i^*$, which cannot be formed when the pairing of $y_i$ with $a_i$ is unknown. Initialization is the crux of the shuffled problem, and that is where the convex stage earns its keep.

Bipartite structure appears in prior phase retrieval as a designed code. PhaseCode and Fast and Robust Compressive Phase Retrieval with Sparse-Graph Codes engineer the measurement graph so a peeling decoder succeeds. In our setting the bipartite graph is given by the physics of the uncertainty, and we ask how its shape controls a convex relaxation. On the Expressive Power of GNNs to Solve Linear SDPs represents a semidefinite program as a variable–constraint bipartite graph, meaning variable nodes linked to the constraint nodes they appear in, and learns to predict its relaxed solution. That paper never asks whether the relaxed solution is the right target. We reuse its representation only in a secondary arm, and our main thrust is precisely the question it leaves open.

Research Program

The theoretical arm proves the majorization equivalence for general bipartite $G$, using the fact that perfect-matching polytopes of bipartite graphs are exactly the doubly stochastic matrices supported on $G$. It proves the full-shuffle trap for Gaussian sensing: the isotropic point is feasible, and its trace is within a vanishing factor of the true trace. It then works toward sufficient conditions for exactness in terms of block size $s$ and $m/n$. Each block contributes one exact linear constraint (its sum) plus majorization slack, which suggests a heuristic that exactness needs roughly $m/s$ on the order of $n \log n$. We treat this only as a hypothesis to test, since the block-sum sensing matrices have rank $s$ rather than one.

The algorithmic arm builds three stages. The first is a convex stage solving the majorization program with a first-order splitting solver, feasible for $n$ up to roughly 64–128. The second is a rounding stage: take the top eigenvector of $X^*$, then match readings to detectors within each component by sorting, since one-dimensional assignment reduces to sorting. The third is an indefinite stage. It drops the lift, parameterizes $x$ directly, and alternates two steps: a Frank-Wolfe-style assignment update on $G$, using linear assignment within components, and a gradient phase-retrieval step on $x$. It starts from the convex solution, following FAQ:D*. Only the third stage scales beyond the lifted sizes, which is why the warm start must prove informative.

A secondary, explicitly optional arm tests whether a bipartite message-passing network over reading and detector nodes can predict the soft assignment $D^*$ without solving the semidefinite program. That would remove the lifting cost from the warm start. We keep it secondary because Qian and Morris show that predicting full semidefinite solutions needs expensive higher-order networks. Predicting only $D$ is closer to an assignment problem, and whether that is easier is an empirical question.

Baselines

The naive reference ignores the shuffle. It runs PhaseLift, and gradient phase retrieval, as if the readings were correctly labeled. This shows how much damage a given correspondence graph does at all. The opposite reference is an oracle that knows the true assignment and runs PhaseLift. Its success rate is the ceiling every method is judged against.

Relax-then-round is our own convex stage followed by eigenvector extraction and per-block sorting. It is the direct analogue of the two-step strategy that Emiya et al. found to fail for linear sensing. We include it because our theory predicts exactly where it fails: when blocks are large relative to $m/n$.

The strongest practical competitor is alternating sort-and-solve. It alternates between matching readings to predicted intensities by sorting within components and running a phase-retrieval step on $x$. A close cousin is gradient descent on the sorted loss $\sum_k \|\mathrm{sort}(y_{B_k}) - \mathrm{sort}(|A_{B_k}x|^2)\|^2$. Both are cheap, exploit the same structure we do, and differ from our method only in initialization. A second strong competitor relaxes the assignment with entropic optimal transport, iterating Sinkhorn steps on $G$, and optimizes $x$ end to end. For small problems ($m \le 14$, following Emiya et al.'s scalability limit), we add exact branch-and-bound over assignments. This gives the true optimum and lets us measure each heuristic's optimality gap.

The key ablation runs the identical indefinite stage from three starts: random restarts, the doubly stochastic barycenter, and the convex solution $(D^*, X^*)$. All competitors get the same measurements, the same wall-clock budget (restart-based methods get as many restarts as fit in our total time, including the semidefinite solve), and the same hyperparameter search budget on held-out instances.

No reported result found on Lacuna for shuffled or unassigned phase retrieval, so there is no published number to beat. The relevant published anchors are qualitative. PhaseLift's exactness bound $m \ge c_0 n \log n$ is given without a numeric constant (PhaseLift). For permuted linear sensing, convex relaxation plus projection "fails to identify the correct permutation in most cases," while branch-and-bound explores 0.05% of the $10!$ space at $M=10$ (Compressed sensing with unknown sensor permutation). Beating the strongest baseline means a statistically clear gain in exact-recovery rate, with relative error below $10^{-3}$ up to global phase, at matched compute, in the intermediate-block-size regime our theory identifies. Restart-based alternation should need many more restarts than fit in the budget to match it.

Why not just…?

Why not just alternate sorting and phase retrieval with random restarts? This is the most serious threat. If the non-convex landscape is benign once assignments are restricted to small blocks, restarts will match us and the convex stage is unnecessary overhead. Our theory says the convex stage matters only in a band of block sizes: below it PhaseLift-like behavior makes everything easy, and above it even the convex solution carries little signal. The restart-matched ablation settles this directly. If restarts match the convex warm start across the whole phase diagram, we will report that, and the contribution reduces to the bias characterization itself.

Why not just relax the assignment with Sinkhorn and train end to end? Entropic transport plans on $G$ are interior points of the same polytope our theory describes. With a non-vanishing entropy term they are pulled toward the barycenter, which is the trap we predict. Annealing the entropy is effectively a homotopy toward the indefinite problem from a particular start. We include annealed Sinkhorn as a baseline, so the experiment shows whether its implicit start is better or worse than $D^*$.

Why not just solve the convex relaxation and project? For full shuffles our equivalence predicts that the projected solution is essentially uncorrelated with the truth. That matches Emiya et al.'s finding for linear sensing and Lyzinski et al.'s for graph matching. The interesting question is where projection does work, and the phase diagram over block size and $m/n$ answers it rather than assuming it.

Why not just learn the solver with a bipartite graph network? On the Expressive Power of GNNs to Solve Linear SDPs reports that standard message-passing networks "failed to even overfit the training data" on semidefinite programs. Its expressive alternative costs $O(n^3)$ per layer. More fundamentally, a network trained to imitate the relaxed solution inherits its bias. We therefore use learning only to predict the warm start, and judge it by downstream recovery after the indefinite stage, not by imitation loss.

Proposed Experiments

The main synthetic suite uses complex Gaussian signals with $n \in \{32, 64, 128\}$, $m/n$ from 2 to 12, and correspondence graphs of three kinds. Block graphs have $s \in \{1, 2, 4, \dots, m\}$. Banded "jitter" graphs let each reading come from one of its $k$ nearest detectors on a ring or grid. Random sparse bipartite graphs have matched degree. For each configuration we record five quantities. These are the eigenvalue ratio $\lambda_2/\lambda_1$ of $X^*$, which measures how far the relaxation is from rank one, and the gap between $\mathrm{Tr}(X^*)$ and $\|x\|^2$. We also record exact-recovery rate, relative error up to global phase, and the fraction of correct correspondences.

The first decisive check is whether recovery depends on the graph's component structure rather than on $m$ alone. Block and banded graphs with equal total edge count but different component sizes should produce different phase transitions. The second is whether the full-shuffle case shows the predicted near-isotropic $X^*$. The third is whether the warm start helps most exactly where $X^*$ is high-rank but its top eigenvector still correlates with $x$ above chance.

A small-scale suite with $m \le 14$ compares every method against branch-and-bound optima, in the style of Emiya et al.'s testbed adapted to intensities. A structured suite uses coded-diffraction measurements with two random masks, following the setup in Phase retrieval for imaging problems, on downsampled patterns of the small molecules used there (caffeine, cocaine). It simulates detector tiles whose placement is unknown, with Poisson noise at several levels. Here the Gaussian intuition behind the trap no longer applies, because $\sum_i a_i a_i^*$ is not close to a multiple of the identity. This tests whether the majorization view still predicts which tile sizes are recoverable.

The proposal fails if any of three things holds: component structure does not predict the transition, the convex warm start never beats matched-compute restarts, or the structured suite contradicts the trap predictions. Each outcome is informative about where convex lifting can and cannot carry correspondence uncertainty.