Lattice partition recovery with dyadic CART

arXiv2105.13504MaRDI QIDQ6368761

Author name not available (Why is that?)

Publication date: 27 May 2021

Abstract: We study piece-wise constant signals corrupted by additive Gaussian noise over a $d$-dimensional lattice. Data of this form naturally arise in a host of applications, and the tasks of signal detection or testing, de-noising and estimation have been studied extensively in the statistical and signal processing literature. In this paper we consider instead the problem of partition recovery, i.e.~of estimating the partition of the lattice induced by the constancy regions of the unknown signal, using the computationally-efficient dyadic classification and regression tree (DCART) methodology proposed by citep{donoho1997cart}. We prove that, under appropriate regularity conditions on the shape of the partition elements, a DCART-based procedure consistently estimates the underlying partition at a rate of order $sigm{a}^2{k}^{*}log(N)/kapp{a}^2$, where $k^{*}$ is the minimal number of rectangular sub-graphs obtained using recursive dyadic partitions supporting the signal partition, $sigm{a}^2$ is the noise variance, $kappa$ is the minimal magnitude of the signal difference among contiguous elements of the partition and $N$ is the size of the lattice. Furthermore, under stronger assumptions, our method attains a sharper estimation error of order $sigm{a}^{2}log(N)/kapp{a}^2$, independent of $k^{*}$, which we show to be minimax rate optimal. Our theoretical guarantees further extend to the partition estimator based on the optimal regression tree estimator (ORT) of cite{chatterjee2019adaptive} and to the one obtained through an NP-hard exhaustive search method. We corroborate our theoretical findings and the effectiveness of DCART for partition recovery in simulations.

Has companion code repository: https://github.com/hernanmp/partition_recovery

This page was built for publication: Lattice partition recovery with dyadic CART

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6368761)