Phase Retrieval for Binary Signals: Box Relaxation and Uniqueness

Wing Hong Wong, Yifei Lou, Tieyong Zeng

Introduction

Phase retrieval (PR) is a fundamental problem in signal processing and physics, particularly in fields such as X-ray crystallography, astronomy, and optics. The challenge lies in recovering a signal $x$ from the magnitude of its Fourier Transform, $|Fx|$, while the phase information is lost. This problem is notoriously difficult due to its non-convex nature and inherent ambiguities—multiple distinct signals can often produce the same Fourier magnitude through spatial shifts or conjugate inverses.

To navigate these challenges, researchers typically rely on regularization or specific signal constraints. This paper investigates the theoretical foundations of these constraints, specifically focusing on binary signals. The authors provide two major contributions: a proof that common gradient-based regularizations are redundant in the context of phase retrieval, and a demonstration that a simple box relaxation is theoretically equivalent to a hard binary constraint.

The Redundancy of Smoothness Regularization

A common strategy in optimization is to apply gradient-based regularization, such as minimizing the $L_2$ norm of the signal's derivative ($\|\nabla^n x\|_2$), to encourage smoothness and narrow the solution space. However, this paper presents a surprising characterization theorem: the $L_2$ norm of any $n$-th order derivative of a signal is entirely determined by its Fourier magnitude.

Mathematically, if two signals share the same Fourier magnitude, they must also share the same gradient norms. Consequently, while these regularization terms might assist an optimizer in navigating the loss landscape, they cannot resolve fundamental ambiguities or change the set of valid solutions. This finding suggests that for phase retrieval, smoothness constraints do not provide the additional information researchers often assume they do.

Box Relaxation and the Binary Constraint

When dealing with binary signals (where $x \in \{0, 1\}^N$), practitioners often use a "box relaxation," treating the discrete values as a continuous range between 0 and 1 ($x \in [0, 1]^N$). The authors provide a theoretical justification for this practice. Using the Krein-Milman Theorem, they prove that the extreme points of the feasible set for the box-relaxed problem are indeed binary.

Theorem 4.1 (Equivalence Theorem) formally establishes that the box-relaxed PR problem is equivalent to the binary PR problem. This means that any signal within the unit box that matches the Fourier magnitude of a binary signal must itself be binary. This "tightness" of the relaxation ensures that the continuous optimization does not introduce "fuzzy" or false solutions that deviate from the binary requirement.

Denoising via Integer Rounding

Building on the properties of binary signals, the authors propose a novel denoising scheme. Because binary signals consist only of 0s and 1s, their periodic autocorrelation coefficients must be integers. This observation leads to a "rounding-based" algorithm for handling noisy data:

  1. Estimation: Estimate the autocorrelation from the noisy Fourier magnitudes.
  2. Rounding: Round the resulting autocorrelation coefficients to the nearest integers.
  3. Optimization: Solve the PR problem using these cleaned, integer-valued measurements via the Alternating Direction Method of Multipliers with a box constraint (ADMMB).

Experimental Results and SNR Bounds

The authors validated their theory using synthetic numerical simulations on binary vectors of lengths $N=50$ and $N=100$ with varying sparsity levels. The results demonstrated that the proposed rounding scheme significantly outperforms naive ADMM approaches, particularly in high-noise environments (low Signal-to-Noise Ratio).

Key findings from the simulations include:

  • Uniqueness Safe Zones: Binary signals with very high or very low sparsity (specifically $\|x\|_0 \le 3$ or $\ge N-3$) are more likely to be uniquely recovered up to trivial ambiguities.
  • SNR Thresholds: The authors derived a theoretical bound for safe denoising: $SNR_{dB} > 10 \log_{10}(64) + 30 \log_{10}\|x\|_0$. This bound confirms that sparser signals are more robust to noise, a trend reflected in the experimental success rates.

Conclusion

This research clarifies the role of regularization in phase retrieval and provides a robust theoretical framework for binary signal recovery. By proving the equivalence of box relaxation and the binary constraint, and by leveraging the integer nature of binary autocorrelations, the authors offer a more effective path for denoising in practical applications. While the current study is limited to one-dimensional signals, it sets the stage for future extensions into 2D image reconstruction and a deeper analysis of oversampled Fourier transforms.

Summary updated

Abstract

Recovering a signal from its Fourier magnitude is referred to as phase retrieval, which occurs in different fields of engineering and applied physics. This paper gives a new characterization of the phase retrieval problem. Particularly useful is the analysis revealing that the common gradient-based regularization does not restrict the set of solutions to a smaller set. Specifically focusing on binary signals, we show that a box relaxation is equivalent to the binary constraint for Fourier-types of phase retrieval. We further prove that binary signals can be recovered uniquely up to trivial ambiguities under certain conditions. Finally, we use the characterization theorem to develop an efficient denoising algorithm.
BibTeX
@misc{wong2019phase,
  author = {Wing Hong Wong and Yifei Lou and Tieyong Zeng},
  title = {{Phase Retrieval for Binary Signals: Box Relaxation and Uniqueness}},
  year = {2019},
  eprint = {1904.10157},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1904.10157},
}
Figure