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

DOI10.1093/IMAIAI/IAAB022MaRDI QIDQ5095265zbMATH OpenOpenAlexFDO

Publication date 5 August 2022

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

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

denoising non-parametric regression phase unwrapping modulo samples

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)

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} o m a t h b b R

, suppose we are given the samples

where

e t a_{i}

denotes noise. Assuming

e t 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 ((f r a c l o g n n)^{f r a c 1 d + 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.

Recommendations

Cited in

(4)

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)