Denoising modulo samples: k-NN regression and tightness of SDP relaxation

DOI10.1093/IMAIAI/IAAB022zbMATH Open1494.94007arXiv2009.04850OpenAlexW3207395252MaRDI QIDQ5095265FDOQ5095265

Authors: Michaël Fanuel, Hemant Tyagi 

Publication date: 5 August 2022

Published in: Information and Inference: A Journal of the IMA (Search for Journal in Brave)

Abstract: Many modern applications involve the acquisition of noisy modulo samples of a function $f$, with the goal being to recover estimates of the original samples of $f$. For a Lipschitz function $f:[0,1{]}^{d}omathbbR$, suppose we are given the samples $$ where $et{a}_i$ denotes noise. Assuming $et{a}_i$ are zero-mean i.i.d Gaussian's, and $x_i$'s form a uniform grid, we derive a two-stage algorithm that recovers estimates of the samples $f(x_i)$ with a uniform error rate $O((fraclognn{)}^{frac1d+2})$ holding with high probability. The first stage involves embedding the points on the unit complex circle, and obtaining denoised estimates of $$ via a $k$NN (nearest neighbor) estimator. The second stage involves a sequential unwrapping procedure which unwraps the denoised mod $1$ estimates from the first stage. The estimates of the samples $f(x_i)$ can be subsequently utilized to construct an estimate of the function $f$, with the aforementioned uniform error rate. Recently, Cucuringu and Tyagi proposed an alternative way of denoising modulo $1$ data which works with their representation on the unit complex circle. They formulated a smoothness regularized least squares problem on the product manifold of unit circles, where the smoothness is measured with respect to the Laplacian of a proximity graph $G$ involving the $x_i$'s. This is a nonconvex quadratically constrained quadratic program (QCQP) hence they proposed solving its semidefinite program (SDP) based relaxation. We derive sufficient conditions under which the SDP is a tight relaxation of the QCQP. Hence under these conditions, the global solution of QCQP can be obtained in polynomial time.

Full work available at URL: https://arxiv.org/abs/2009.04850

Recommendations

• Provably robust estimation of modulo 1 samples of a smooth function with applications to phase unwrapping
• Near-optimal bounds for phase synchronization
• Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
• Nonconvex phase synchronization
• Random sampling and approximation of signals with bounded derivatives

zbMATH Keywords

denoisingnon-parametric regressionphase unwrappingmodulo samples

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08) Sampling theory in information and communication theory (94A20)

Cited In (4)

• Title not available (Why is that?)
• Provably robust estimation of modulo 1 samples of a smooth function with applications to phase unwrapping
• A unified approach to synchronization problems over subgroups of the orthogonal group
• MDL Denoising Revisited

This page was built for publication: Denoising modulo samples: \(k\)-NN regression and tightness of SDP relaxation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5095265)