Title :

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

Author(s) :

Cucuringu, Mihai [Auteur]
University of Oxford
Tyagi, Hemant [Auteur]
MOdel for Data Analysis and Learning [MODAL]

Journal title :

Journal of Machine Learning Research

Pages :

1−77

Publisher :

Microtome Publishing

Publication date :

2020-01-01

ISSN :

1532-4435

English keyword(s) :

quadratically constrained quadratic programming (QCQP)
trust-region sub-problem
angular embedding
phase unwrapping
semidefinite programming
angular synchronization

HAL domain(s) :

Statistiques [stat]
Statistiques [stat]/Autres [stat.ML]

English abstract : [en]

Consider an unknown smooth function $f : [0, 1]^d → R$, and assume we are given $n$ noisy mod 1 samples of $f , i.e., y_i = (f (x_i) + η_i) $mod 1, for $x_i \in [0, 1]^d$ , where $η_i$ denotes the noise. Given the samples ...
Show more >Consider an unknown smooth function $f : [0, 1]^d → R$, and assume we are given $n$ noisy mod 1 samples of $f , i.e., y_i = (f (x_i) + η_i) $mod 1, for $x_i \in [0, 1]^d$ , where $η_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) mod 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.Show less >

Language :

Anglais

Popular science :

Non

Collections :

• Laboratoire Paul Painlevé - UMR 8524

Source :

Harvested from HAL