Isolating the hard core of phaseless inference: the phase selection formulation

Abstract Real-valued phase retrieval is a non-convex continuous inference problem, where a high-dimensional signal is reconstructed from a dataset of signless linear measurements. Focusing on the noiseless case, we aim to disentangle the two distinct subtasks in the phase retrieval problem: the hard combinatorial problem of retrieving the missing signs of the measurements and the nested convex problem of regressing the input–output observations to recover the hidden signal. To this end, we introduce and analytically characterize a two-level formulation of the problem, called ‘phase selection’. Within the replica theory framework, we perform a large deviation analysis to characterize the minimum mean squared error achievable with different estimations for the hidden signs. Moreover, we study the free-energy landscape of the problem when both levels are optimized simultaneously, as a function of the dataset size. At low temperatures, in proximity to the Bayes-optimal (BO) threshold, previously derived in the context of phase retrieval, we detect the coexistence of two free-energy branches, one connected to the random initialization condition and a second to the signal. We derive the phase diagram for a first-order transition after which the two branches merge. Interestingly, introducing an L 2 regularization in the regression subtask can anticipate the transition to lower dataset sizes, at the cost of a bias in the signal reconstructions, which can be removed by annealing the regularization intensity. Finally, we study the inference performance of three meta-heuristics in the context of phase selection: simulated annealing, approximate message passing and Langevin dynamics on the continuous relaxation of the sign variables. With simultaneous annealing of the temperature and the L 2 regularization, they are shown to approach the BO sample efficiency.