论文标题
降级模量样品：K-NN的回归和SDP松弛的紧密度
Denoising modulo samples: k-NN regression and tightness of SDP relaxation
论文作者
论文摘要
许多现代应用程序涉及收购功能$ f $的嘈杂模型样本，目的是收回对$ f $的原始样品的估计。对于LipsChitz函数$ f：[0,1]^d \ to \ mathbb {r} $，假设我们得到了样本$ y_i =（f（x_i） +η_i）\ bmod 1; \ quad i = 1，\ dots，n $其中$η_i$表示噪声。假设$η_i$是零均值的i.i.d高斯和$ x_i $的形成一个均匀的网格，我们得出了一个两阶段的算法，可以恢复对样品的估计$ f（x_i）$，并带有均匀的错误率$ o $ o（\ frac {\ frac {\ log n} $ n} $ 2}具有很高的概率。第一阶段涉及将点嵌入单位复杂圆上，并通过$ k $ nn（最近的邻居）估计器获得$ f（x_i）\ bmod 1 $ 1 $ $ f（x_i）\ bmod的估计值。第二阶段涉及一个连续包装过程，该过程将拆开的Denoised mod $ 1 $估计从第一阶段估算。样品的估计值$ f（x_i）$随后可用于构建功能$ f $的估计，并使用上述均匀错误率。 最近，Cucuringu和Tyagi提出了一种替代方法，以降级模量$ 1 $数据，该数据与他们在单位复杂圆圈上的表示。他们在单位圆的产品歧管上制定了平滑度正则最小二乘问题，在该圆圈的产品歧管上，相对于涉及$ x_i $的接近图$ g $的拉普拉斯（Laplacian）的平滑度。这是一个非convex二次约束二次程序（QCQP），因此他们提出了解决基于半决赛程序（SDP）的放松。我们得出了足够的条件，SDP是QCQP的紧密放松。因此，在这些条件下，可以在多项式时间内获得QCQP的全局溶液。
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) + η_i)\bmod 1; \quad i=1,\dots,n$ where $η_i$ denotes noise. Assuming $η_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((\frac{\log n}{n})^{\frac{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_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.
