Ning Hao of University of Arizona : Shifted Maximum Subarrays

Posted by Yichao Wu , part of the Statistics and Data Science Seminar.

At

Sept. 30, 2026, 4:30 p.m.

In

636 SEO

Abstract

Detecting a localized change in a sequence is a fundamental problem in statistics, with applications in genomics and signal processing. Classical scan statistics search over all possible intervals, but exhaustive computation requires quadratic time, creating a bottleneck for long sequences and resampling-based inference. In this talk, I will present an approach based on the shifted maximum subarray (SMS) problem: finding the contiguous segment with the largest sum after subtracting a common shift from every observation. As the shift varies, the optimal segment traces a solution path with a useful geometric structure. We characterize this path and show that it contains the maximizing intervals for classical scan statistics used in signal detection and epidemic change-point analysis. This connection leads to an exact algorithm whose computational cost depends on the number of distinct solutions along the path. Numerical studies show that this number is typically small, yielding substantial speedups and nearly linear running time in the settings examined. I will discuss the underlying geometry and open questions about the computation complexity.