Provably robust estimation of modulo 1 samples of a smooth function with applications to phase unwrapping

Mihai Cucuringu, Hemant TyagiJMLR 2020 · OpenReview

TL;DR

This paper introduces a novel, provably robust method for estimating smooth functions from noisy "modulo 1" measurements, a common challenge in fields like phase unwrapping. Their approach, based on angular embeddings and a trust-region subproblem, offers theoretical guarantees and strong empirical performance, even under high noise levels.

What Problem Does This Paper Address?

Many scientific and engineering applications involve estimating an underlying smooth signal, $f$, from noisy measurements. A particular challenge arises when the measurements are not direct observations of $f$, but rather $f$ modulo some value (here, modulo 1). This "modulo 1" constraint is common in applications like:

  • Self-reset Analog-to-Digital Converters (ADCs): These devices have voltage limits and "wrap around" the signal, effectively producing modulo measurements.
  • Phase Unwrapping: In fields like radar interferometry (InSAR), MRI, and optics, signals often represent phase information that is inherently periodic, meaning measurements are effectively modulo $2\pi$. Recovering the true, continuous phase from these wrapped measurements is crucial.

The core problem is to recover the original, smooth function $f$ from these noisy, wrapped measurements, ensuring the estimation process is robust to noise and produces smooth outputs. Existing methods often struggle with high noise levels or lack theoretical guarantees.

Methods

The paper proposes a two-stage approach:

  1. Denoising Stage (Core Contribution):
    • Angular Embedding: The noisy modulo 1 samples ($y_i$) are mapped to the unit circle in the complex plane ($z_i = \exp(2\pi i y_i)$). This is a key insight: even if two points are far apart in the real domain (due to wrapping), their angular representations remain close if the underlying function is smooth.
  2. Smoothness Regularized Least-Squares: This leads to a quadratically constrained quadratic program (QCQP) where variables are constrained to lie on the unit circle.
  3. Trust-Region Subproblem (TRS) Relaxation: To efficiently solve the QCQP, the authors relax the unit circle constraint to a sphere constraint, transforming the problem into a standard trust-region subproblem. This relaxation is solvable efficiently.
  4. Theoretical Guarantees: The paper provides provable robustness guarantees against various noise models (arbitrary bounded, Bernoulli-Uniform, Gaussian), which are claimed to be the first of their kind for this problem.
  5. Unwrapping Stage:
    • Quotient Tracker (QT) Method: A simple sequential method that checks for large differences between consecutive denoised modulo 1 samples to infer quotient changes. This method is shown to be sensitive to noise.
  6. Ordinary Least-Squares (OLS) Method: A more robust approach that directly estimates the function values by solving a least-squares problem based on differences between nearby samples. This is the method used in conjunction with their QCQP denoising stage.

They also explore alternative denoising formulations using Riemannian optimization on manifolds, including a Burer-Monteiro approach for a semidefinite programming (SDP) relaxation.

Datasets

The paper primarily uses synthetic datasets for evaluation. They consider:

  • Univariate (d=1) synthetic data: Generated using the function $f(x) = 4x \cos^2(2\pi x) - 2 \sin^2(2\pi x)$.
  • Multivariate (d=2) synthetic data: Generated using $f(x, y) = 6xe^{-x^2-y^2}$.
  • Real-world elevation maps: Data from InSAR, specifically around Mount Vesuvius, Etna, and Mont Blanc, are used to demonstrate applications in 2D phase unwrapping.

No new benchmarks are introduced; instead, existing datasets and synthetic setups are used to compare against prior work.

Key Insights and Ideas

  • Angular Embedding for Modulo Data: The core insight is that mapping modulo data to the unit circle effectively linearizes the problem in a way that preserves smoothness information, making it amenable to standard optimization techniques. This is crucial because direct manipulation of modulo data is inherently non-linear and difficult.
  • TRS Relaxation for Robustness: Relaxing the non-convex unit circle constraint to a sphere constraint transforms the problem into a well-studied trust-region subproblem. This allows for efficient and provably robust solutions, especially under noise.
  • Theoretical Guarantees for Modulo Denoising: The paper's claim of providing the first theoretical guarantees for denoising modulo samples is significant. This moves beyond empirical performance to offer a deeper understanding of the method's reliability.
  • Two-Stage Approach Effectiveness: The combination of their QCQP denoising with a simple OLS unwrapping stage proves effective, particularly at high noise levels where simpler methods fail.

Key Results

  • Provable Robustness: The proposed QCQP method, when combined with OLS unwrapping, demonstrates provable robustness to arbitrary bounded, Bernoulli-Uniform, and Gaussian noise models.
  • High Performance at High Noise: Numerical experiments show that their method (QCQP) performs well even at high noise levels, significantly outperforming simpler methods like OLS and a prior method (BKR) in such scenarios. For instance, in the Gaussian noise model, iQCQP (an iterated version of their method) shows surprisingly good performance at very high noise levels ($\sigma = 0.17$).
  • Scalability for 2D Phase Unwrapping: For 2D applications like InSAR, their Manopt-Phases approach (using Riemannian optimization) can handle real-world data with up to a million sample points in under 10 seconds, achieving near-perfect solutions.
  • Comparison with Prior Work: The paper shows that their QCQP and iQCQP methods generally outperform OLS and the approach by Bhandari et al. (2017) (BKR), especially at higher noise levels.

Limitations and Future Work

  • Unwrapping Stage Robustness: While their denoising stage is robust, the paper acknowledges that the simple OLS unwrapping method can be sensitive to noise. They suggest exploring more sophisticated unwrapping algorithms or methods based on group synchronization as future work.
  • Computational Complexity for High Dimensions: The theoretical bounds for multivariate functions show an exponential dependence on the dimension $d$ (the "curse of dimensionality"), suggesting that performance might degrade for very high-dimensional problems. However, they note that applications often involve small $d$ (e.g., $d=2,3$).
  • Iterated QCQP (iQCQP): The paper introduces an iterated version (iQCQP) that sometimes yields better results than the basic QCQP, but its behavior is noted to be dependent on parameter choices and can oscillate. Further investigation into iQCQP's properties is suggested.
  • Patch-Based Methods: Exploring a patch-based divide-and-conquer strategy for graph decomposition is suggested for potentially improved performance.
  • TV Norm Regularization: Investigating a variation of their objective function that incorporates a Total Variation (TV) norm is proposed, which could be beneficial for preserving sharp discontinuities.
  • Single-Stage Method: Developing a "single-stage method" that directly outputs denoised estimates of the original real-valued samples is mentioned as a future research direction.
  • Regression Problem: Learning a smooth, robust estimate of the underlying modulo 1 function or the original function from noisy samples is posed as an interesting question.

Summary updated

Abstract

Consider an unknown smooth function $f: [0,1]^d \rightarrow \mathbb{R}$, and assume we are given $n$ noisy mod 1 samples of $f$, i.e., $y_i = (f(x_i) + \eta_i) \bmod 1$, for $x_i \in [0,1]^d$, where $\eta_i$ denotes the noise. Given the samples $(x_i,y_i)_{i=1}^{n}$, our goal is to recover smooth, robust estimates of the clean samples $f(x_i) \bmod 1$. We formulate a natural approach for solving this problem, which works with angular embeddings of the noisy mod 1 samples over the unit circle, inspired by the angular synchronization framework. This amounts to solving a smoothness regularized least-squares problem -- a quadratically constrained quadratic program (QCQP) -- where the variables are constrained to lie on the unit circle. Our proposed approach is based on solving its relaxation, which is a trust-region sub-problem and hence solvable efficiently. We provide theoretical guarantees demonstrating its robustness to noise for adversarial, as well as random Gaussian and Bernoulli noise models. To the best of our knowledge, these are the first such theoretical results for this problem. We demonstrate the robustness and efficiency of our proposed approach via extensive numerical simulations on synthetic data, along with a simple least-squares based solution for the unwrapping stage, that recovers the original samples of $f$ (up to a global shift). It is shown to perform well at high levels of noise, when taking as input the denoised modulo $1$ samples. Finally, we also consider two other approaches for denoising the modulo 1 samples that leverage tools from Riemannian optimization on manifolds, including a Burer-Monteiro approach for a semidefinite programming relaxation of our formulation. For the two-dimensional version of the problem, which has applications in synthetic aperture radar interferometry (InSAR), we are able to solve instances of real-world data with a million sample points in under 10 seconds, on a personal laptop.
BibTeX
@article{cucuringu2020provably,
  author = {Mihai Cucuringu and Hemant Tyagi},
  title = {{Provably robust estimation of modulo 1 samples of a smooth function with applications to phase unwrapping}},
  journal = {J. Mach. Learn. Res.},
  year = {2020},
  url = {https://openreview.net/forum?id=lQhQJOQB5-O},
}
Figure