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

Fanuel, Michaël; Tyagi, Hemant

Type de document :

Compte-rendu et recension critique d'ouvrage

DOI :

10.1093/imaiai/iaab022

Titre :

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

Auteur(s) :

Fanuel, Michaël [Auteur]
Department of Electrical Engineering [KU Leuven] [KU-ESAT]
Tyagi, Hemant [Auteur]
MOdel for Data Analysis and Learning [MODAL]

Titre de la revue :

Information and Inference

Éditeur :

Oxford University Press (OUP)

Date de publication :

2021-10-13

ISSN :

2049-8764

Discipline(s) HAL :

Mathématiques [math]/Statistiques [math.ST]

Résumé en anglais : [en]

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 → R, suppose we are ...
Lire la suite >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 → R, suppose we are given the samples y_i = (f (x_i) + η_i) mod 1; i = 1,. .. , 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((log n / 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_i) mod 1 via a kNN (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 [7] 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.Lire moins >

Langue :

Anglais

Vulgarisation :

Non

Collections :

Laboratoire Paul Painlevé - UMR 8524

Source :

Harvested from HAL

Fichiers

document
Accès libre
Accéder au document

kNN_SDP_mod1.pdf
Accès libre
Accéder au document

Denoising modulo samples: k-NN regression ... BibTeX CSV Excel RIS

Fichiers

Denoising modulo samples: k-NN regression ...

BibTeX

CSV

Excel

RIS