2021/10/21 by Yi Yu, Oscar Hernán Madrid Padilla, Yu, Yi +3 · 1 citation
Biochemistry, Genetics and Molecular Biology · Mathematics · #FOS: Mathematics #Gene expression and cancer classification #Statistical Methods and Bayesian Inference #Statistical Methods and Inference #Statistics Theory (math.ST)
paper · doi:10.48550/arxiv.2110.10989
openalex publication_date 2021/10/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
We consider a graph-structured change point problem in which we observe a random vector with piecewise constant but unknown mean and whose independent, sub-Gaussian coordinates correspond to the n nodes of a fixed graph. We are interested in the localisation task of recovering the partition of the nodes associated to the constancy regions of the mean vector. When the partition S consists of only two elements, we characterise the difficulty of the localisation problem in terms of four key parameters: the maximal noise variance σ2, the size Δ of the smaller element of the partition, the magnitude κ of the difference in the signal values across contiguous elements of the partition and the sum of the effective resistance edge weights |∂r(S)| of the corresponding cut -- a graph theoretic quantity quantifying the size of the partition boundary. In particular, we demonstrate an information theoretical lower bound implying that, in the low signal-to-noise ratio regime κ2 Δσ-2 |∂r(S)|-1 \lesssim 1, no consistent estimator of the true partition exists. On the other hand, when κ2 Δσ-2 |∂r(S)|-1 \gtrsim ζn log\r(|E|)\, with r(|E|) being the sum of effective resistance weighted edges and ζn being any diverging sequence in n, we show that a polynomial-time, approximate ℓ0-penalised least squared estimator delivers a localisation error -- measured by the symmetric difference between the true and estimated partition -- of order κ-2 σ2 |∂r(S)| log\r(|E|)\. Aside from the log\r(|E|)\ term, this rate is minimax optimal. Finally, we provide discussions on the localisation error for more general partitions of unknown sizes.