Denoising modulo samples: k-NN regression and tightness of SDP relaxation. (13th October 2021)

• Record Type: Journal Article
• Authors: Fanuel, Michaël; Tyagi, Hemant
• Is Part Of: Information and inference. Volume 11:Number 2(2022)
• Page Start: 637
• Page End: 677
• Publication Date: 2021-10-13
• Subjects: modulo samples -- denoising -- phase unwrapping -- non-parametric regression; Mathematical models -- Periodicals; 519.605
• DOI: 10.1093/imaiai/iaab022
• Languages: English
• ISSNs: 2049-8764

Abstract

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 \to {{\mathbb{R}}}$, suppose we are given the samples $y_i = (f(x_i) + \eta _i)\bmod 1; \quad i=1, \dots, n$, where $\eta _i$ denotes noise. Assuming $\eta _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\big(\big(\frac{\log n}{n}\big)^{\frac{1}{d+2}}\big)$ holding with high probability. The first stage involves embedding the points on the unit complex circle, and obtaining denoised estimates of $f(x_i)\bmod 1$ 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.