Denoising modulo samples: k-NN regression and tightness of SDP relaxation
arXiv:2009.04850
Abstract
Many modern applications involve the acquisition of noisy modulo samples of a function , with the goal being to recover estimates of the original samples of . For a Lipschitz function , suppose we are given the samples where denotes noise. Assuming are zero-mean i.i.d Gaussian's, and 's form a uniform grid, we derive a two-stage algorithm that recovers estimates of the samples with a uniform error rate holding with high probability. The first stage involves embedding the points on the unit complex circle, and obtaining denoised estimates of via a NN (nearest neighbor) estimator. The second stage involves a sequential unwrapping procedure which unwraps the denoised mod estimates from the first stage. The estimates of the samples can be subsequently utilized to construct an estimate of the function , with the aforementioned uniform error rate. Recently, Cucuringu and Tyagi proposed an alternative way of denoising modulo 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 involving the '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.
(i) 38 pages, 6 figures (ii) Revised the manuscript after receiving reviews (iii) Removed Theorem 3(2) and Corollary 3 due to inaccuracies in the proof, main results are unchanged (iv) Added Appendix B (v) Added Section 2.5 for estimating f (Theorem 5)