Papers › Denoising modulo samples: k-NN regression and tightness of SDP relaxation
Denoising modulo samples: k-NN regression and tightness of SDP relaxation
Michaël Fanuel, Hemant Tyagi
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]ᵈ →ℝ, suppose we are given the samples yᵢ = (f(xᵢ) + ηᵢ)1; i=1,…,n where ηᵢ denotes noise. Assuming ηᵢ are zero-mean i.i.d Gaussian's, and xᵢ's form a uniform grid, we derive a two-stage algorithm that recovers estimates of the samples f(xᵢ) with a uniform error rate O((logn/n)^(1/(d+2))) holding with high probability. The first stage involves embedding the points on the unit complex circle, and obtaining denoised estimates of f(xᵢ)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ᵢ) 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ᵢ'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.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Tasks
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections