# Lattice partition recovery with dyadic CART

arXiv: https://arxiv.org/abs/2105.13504 · HTML: https://mlsanity.com/paper/2105.13504/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 44 references that are in the map.
- First posted on arXiv 27 May 2021.

## Builds on (most cited first, 15 of 15)

- [Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices](https://mlsanity.com/paper/1402.1267/) (2014)
- [Univariate Mean Change Point Detection: Penalization, CUSUM and Optimality](https://mlsanity.com/paper/1810.09498/) (2018)
- [Optimal Change-Point Detection and Localization](https://mlsanity.com/paper/2010.11470/) (2020)
- [Computational and Statistical Boundaries for Submatrix Localization in a Large Noisy Matrix](https://mlsanity.com/paper/1502.01988/) (2015)
- [Optimal Estimation and Completion of Matrices with Biclustering Structures](https://mlsanity.com/paper/1512.00150/) (2015)
- [Adaptive Estimation of Multivariate Piecewise Polynomials and Bounded Variation Functions by Optimal Decision Trees](https://mlsanity.com/paper/1911.11562/) (2019)
- [False discovery rate smoothing](https://mlsanity.com/paper/1411.6144/) (2014)
- [Bayesian and Maximum Likelihood Estimation for Gaussian Processes on an Incomplete Lattice](https://mlsanity.com/paper/1402.4281/) (2014)
- [Object Detection and Classification in Occupancy Grid Maps using Deep Convolutional Networks](https://mlsanity.com/paper/1805.08689/) (2018)
- [Approximate l0-penalized estimation of piecewise-constant signals on graphs](https://mlsanity.com/paper/1703.01421/) (2017)
- [Submatrix localization via message passing](https://mlsanity.com/paper/1510.09219/) (2015)
- [A Fast and Flexible Algorithm for the Graph-Fused Lasso](https://mlsanity.com/paper/1505.06475/) (2015)
- [A Multiscale Scan Statistic for Adaptive Submatrix Localization](https://mlsanity.com/paper/1906.08884/) (2019)
- [Segmentation of high dimensional means over multi-dimensional change points and connections to regression trees](https://mlsanity.com/paper/2105.10017/) (2021)
- [Distribution-free Detection of a Submatrix](https://mlsanity.com/paper/1604.07449/) (2016)

## Built on by (most cited first, 2 of 2)

- [Variance estimation in graphs with the fused lasso](https://mlsanity.com/paper/2207.12638/) (2022)
- [Piecewise Polynomial Regression of Tame Functions via Integer Programming](https://mlsanity.com/paper/2311.13544/) (2023)

## Abstract (arXiv)

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 citepdonoho1997cart. 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 σ2 k^* log (N)/kappa2, where k^* is the minimal number of rectangular sub-graphs obtained using recursive dyadic partitions supporting the signal partition, σ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 σ2log(N)/kappa2, 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 citechatterjee2019adaptive 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.