The Library
Lattice partition recovery with dyadic CART
Tools
Tools
Tools
Padilla, Oscar Hernan Madrid, Yu, Yi and Rinaldo, Alessandro (2022) Lattice partition recovery with dyadic CART. In: NeurIPS : 35th Conference on Neural Information Processing Systems, Virtual, 6-14 Dec 2022. Published in: Advances in Neural Information Processing Systems (NeurIPS 2021), 31 pp. 26143-26155. ISBN 9781713845393.
An open access version can be found in:
Official URL: https://proceedings.neurips.cc/paper/2021/hash/dba...
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 [14]. 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 σ2k∗ log(N)/κ2, where k∗ is the minimal number of rectangular sub-graphs obtained using recursive dyadic partitions supporting the signal partition, σ2 is the noise variance, κ 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 σ2 log(N)/κ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 [12] 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.
| Item Type: | Conference Item (Paper) | ||||||
|---|---|---|---|---|---|---|---|
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Statistics | ||||||
| Series Name: | NeurIPS Proceedings | ||||||
| Journal or Publication Title: | Advances in Neural Information Processing Systems (NeurIPS 2021) | ||||||
| ISBN: | 9781713845393 | ||||||
| Official Date: | 2022 | ||||||
| Dates: |
|
||||||
| Volume: | 31 | ||||||
| Page Range: | pp. 26143-26155 | ||||||
| Article Number: | 1049-5258 | ||||||
| Status: | Peer Reviewed | ||||||
| Publication Status: | Published | ||||||
| Access rights to Published version: | Open Access (Creative Commons) | ||||||
| RIOXX Funder/Project Grant: |
|
||||||
| Conference Paper Type: | Paper | ||||||
| Title of Event: | NeurIPS : 35th Conference on Neural Information Processing Systems | ||||||
| Type of Event: | Conference | ||||||
| Location of Event: | Virtual | ||||||
| Date(s) of Event: | 6-14 Dec 2022 | ||||||
| Related URLs: | |||||||
| Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
