High-dimensional nonparametric changepoint detection via low-rank degree-two density projection

# High-Dimensional Nonparametric Change-Point Detectionvia Low-Rank Degree-Two Density Projection
Source: [https://arxiv.org/html/2608.13922](https://arxiv.org/html/2608.13922)
Guoqing ZhangAffiliation:Operations Research ProgramAffiliation:North Carolina State UniversityAffiliation:Raleigh, NC, USAEmail:[Gzhang25@ncsu\.edu](mailto:)Zhaixin ChenAffiliation:H\. Milton Stewart School of ISyEAffiliation:Georgia Institute of TechnologyAffiliation:Atlanta, GA, USAEmail:[zxchen08@gatech\.edu](mailto:)

###### Abstract

Detecting distributional changes in high dimension is difficult when neither the pre\-change nor post\-change density is parametrically specified\. We introduce a representation\-based approach that retains all degree\-at\-most\-two density information while replacing density estimation by matrix mean estimation\. For observations in\[−1,1\]d\[\-1,1\]^\{d\}, a symmetric feature matrixH2​\(X\)∈ℝ\(d\+1\)×\(d\+1\)H\_\{2\}\(X\)\\in\\mathbb\{R\}^\{\(d\+1\)\\times\(d\+1\)\}is constructed so thatM⁡\(f\)=𝔼f​H2​\(X\)M\(f\)=\\mathbb\{E\}\_\{f\}H\_\{2\}\(X\)is an isometric encoding of the degree\-two orthogonal projection of the density\. We scan matrix CUSUMs after rank\-rrtruncation, exploiting the low rank of the projected jump rather than sparsity of individual coordinates\. The resultingLR\-D2estimator has a tent\-shaped population objective and a nonasymptotic operator\-norm analysis whose leading stochastic term scales asr​d​log⁡\(n​d\)\\sqrt\{rd\\log\(nd\)\}\. For multiple changes, we give a seeded narrowest\-over\-threshold procedure and prove exact recovery by an induction that preserves an isolating interval for every undetected change\. A cross\-fitted scalar refinement learns the changing low\-rank direction on one fold and localizes on the other, attainingO~ℙ​\(κ−2\)\\widetilde\{O\}\_\{\\mathbb\{P\}\}\(\\kappa^\{\-2\}\)error; a matching Le Cam lower bound shows optimality up to logarithms\. A geometricallyβ\\beta\-mixing extension follows from a dependent matrix Bernstein inequality\. Experiments with ambient dimension up to200200, a three\-changed=100d=100sequence, and a128128\-feature human\-activity benchmark show that the method remains computationally practical and accurately detects pure dependence changes that are invisible to mean CUSUMs\.

## 1Introduction

A change point is a time at which the law generating a sequence changes\. In modern applications, the observation at each time can be a high\-dimensional vector and the change need not be a mean shift: dependence, marginal shape, or interactions may change while every coordinate mean remains fixed\. Classical multivariate procedures then face two simultaneous obstacles\. First, direct nonparametric density estimation is subject to the curse of dimensionality\. Second, an unrestricted second\-order change containsΘ⁡\(d2\)\\Theta\(d^\{2\}\)coordinates, so a Frobenius scan can aggregate overwhelming noise even when the scientifically meaningful change is low\-dimensional\.

We address these obstacles through a fixed representation of the density\. Relative to the uniform measure on\[−1,1\]d\[\-1,1\]^\{d\}, the degree\-two projection contains coordinate means, marginal quadratic components, and pairwise interactions\. With an appropriate normalization, all these coefficients form a symmetric\(d\+1\)×\(d\+1\)\(d\+1\)\\times\(d\+1\)matrixM⁡\(f\)M\(f\)\. Crucially, there is a single\-observation feature mapH2H\_\{2\}satisfying

M⁡\(f\)=𝔼f​H2​\(X\),‖M⁡\(f\)−M⁡\(g\)‖F=‖P2​\(f−g\)‖L2\.M\(f\)=\\mathbb\{E\}\_\{f\}H\_\{2\}\(X\),\\qquad\\left\\lVert M\(f\)\-M\(g\)\\right\\rVert\_\{\\mathrm\{F\}\}=\\left\\lVert P\_\{2\}\(f\-g\)\\right\\rVert\_\{L^\{2\}\}\.Thus a nonparametric change visible to the degree\-two projection becomes a matrix\-mean change, without estimating either density\. When the projected jump matrix is low rank, rank truncation denoises the matrix CUSUM while preserving its population signal\.

This viewpoint differs from coordinate sparsity\. A dense correlation pattern generated by a few latent interaction directions may have many nonzero entries but small rank\. It also provides a concrete representation\-learning interpretation:H2H\_\{2\}is a deterministic second\-order feature map, and the data select the changing subspace through a local eigendecomposition\. The matrix dimension grows only linearly withdd, and the retained rank controls the effective stochastic complexity\.

#### Contributions\.

Our main contributions are fourfold\.

1. 1\.We derive an exact isometric matrix encoding of the degree\-two density projection and show that, on any interval containing one change, every population matrix CUSUM is a positive scalar multiple of the same jump matrix\. The resulting squared population score has an exact linear localization margin\.
2. 2\.We prove a deterministic low\-rank perturbation inequality and combine it with matrix Bernstein concentration\. Under a bounded\-density condition, the leading normalized CUSUM noise isOℙ​\(d​log⁡\(n​d\)\)O\_\{\\mathbb\{P\}\}\(\\sqrt\{d\\log\(nd\)\}\)in operator norm, yielding the signal requirementΔ​κ2≳r​d​log⁡\(n​d\)\\Delta\\kappa^\{2\}\\gtrsim rd\\log\(nd\)up to constants and lower\-order terms\.
3. 3\.We proposeSeeded\-LR\-D2, a multiscale interval\-deletion algorithm\. Its multiple\-change theorem is proved by induction: no\-change intervals are inactive, every remaining change has an active balanced isolating interval, and the shortest active interval contains exactly one change\. We then introduceRefine\-LR\-D2, a cross\-fitted direction\-and\-localization step with near\-minimaxκ−2\\kappa^\{\-2\}error\.
4. 4\.We provide reproducible synthetic and semi\-synthetic experiments\. The estimator is run atd∈\{20,50,100,200\}d\\in\\\{20,50,100,200\\\}, detects three changes in ad=100d=100sequence, and processes a128128\-feature UCI human\-activity task\. These settings directly test the claimed high\-dimensional operating regime\.

#### Related work\.

High\-dimensional mean\-change methods exploit sparse projections or sparsified segmentation\([15](https://arxiv.org/html/2608.13922#bib.bib15);[5](https://arxiv.org/html/2608.13922#bib.bib5);[6](https://arxiv.org/html/2608.13922#bib.bib6)\)\. Nonparametric multivariate and functional change\-point methods include kernel, graph, and local\-neighborhood constructions\([9](https://arxiv.org/html/2608.13922#bib.bib9);[8](https://arxiv.org/html/2608.13922#bib.bib8);[13](https://arxiv.org/html/2608.13922#bib.bib12);[12](https://arxiv.org/html/2608.13922#bib.bib13);[2](https://arxiv.org/html/2608.13922#bib.bib1)\)\. Our method is complementary: it is nonparametric at the density level but targets changes identifiable through a prescribed polynomial projection, with low matrix rank as the structural regularizer\. For multiple changes we use ideas from wild, narrowest\-over\-threshold, and seeded binary segmentation\([7](https://arxiv.org/html/2608.13922#bib.bib7);[4](https://arxiv.org/html/2608.13922#bib.bib4);[10](https://arxiv.org/html/2608.13922#bib.bib10)\)\. The two\-stage localization architecture and induction\-based consistency argument are also related to recent functional\-regression change\-point analysis\([11](https://arxiv.org/html/2608.13922#bib.bib11)\)\. Matrix concentration is based on[14](https://arxiv.org/html/2608.13922#bib.bib14); the dependent extension uses[3](https://arxiv.org/html/2608.13922#bib.bib3)\.

## 2Degree\-two density representation

### 2\.1An isometric feature matrix

Letμ=Unif⁡\(\[−1,1\]d\)\\mu=\\operatorname\{Unif\}\(\[\-1,1\]^\{d\}\)and letf=d​P/d​μf=dP/d\\mu\. Define the first Legendre polynomials

p0​\(x\)=1,p1​\(x\)=x,p2​\(x\)=3​x2−12,p\_\{0\}\(x\)=1,\\qquad p\_\{1\}\(x\)=x,\\qquad p\_\{2\}\(x\)=\\frac\{3x^\{2\}\-1\}\{2\},whose squaredL2​\(μ\)L^\{2\}\(\\mu\)norms are11,1/31/3, and1/51/5\. The degree\-at\-most\-two projection is

P2​f​\(x\)=1\+∑j=1daj​xj\+∑j=1dbj​p2​\(xj\)\+∑1≤i<j≤dγi​j​xi​xj,P\_\{2\}f\(x\)=1\+\\sum\_\{j=1\}^\{d\}a\_\{j\}x\_\{j\}\+\\sum\_\{j=1\}^\{d\}b\_\{j\}p\_\{2\}\(x\_\{j\}\)\+\\sum\_\{1\\leq i<j\\leq d\}\\gamma\_\{ij\}x\_\{i\}x\_\{j\},\(1\)whereaj=3​𝔼f​Xja\_\{j\}=3\\mathbb\{E\}\_\{f\}X\_\{j\},bj=5​𝔼f​p2​\(Xj\)b\_\{j\}=5\\mathbb\{E\}\_\{f\}p\_\{2\}\(X\_\{j\}\), andγi​j=9​𝔼f​\(Xi​Xj\)\\gamma\_\{ij\}=9\\mathbb\{E\}\_\{f\}\(X\_\{i\}X\_\{j\}\)\.

Forx∈\[−1,1\]dx\\in\[\-1,1\]^\{d\}, define the symmetric matrixH2​\(x\)∈ℝ\(d\+1\)×\(d\+1\)H\_\{2\}\(x\)\\in\\mathbb\{R\}^\{\(d\+1\)\\times\(d\+1\)\}by

\[H2​\(x\)\]00\\displaystyle\[H\_\{2\}\(x\)\]\_\{00\}=1,\\displaystyle=1,\[H2​\(x\)\]0​j=\[H2​\(x\)\]j​0\\displaystyle\[H\_\{2\}\(x\)\]\_\{0j\}=\[H\_\{2\}\(x\)\]\_\{j0\}=3​xj6,\[H2​\(x\)\]j​j=5​p2​\(xj\),\\displaystyle=\\frac\{3x\_\{j\}\}\{\\sqrt\{6\}\},\\qquad\[H\_\{2\}\(x\)\]\_\{jj\}=\\sqrt\{5\}\\,p\_\{2\}\(x\_\{j\}\),\[H2​\(x\)\]i​j=\[H2​\(x\)\]j​i\\displaystyle\[H\_\{2\}\(x\)\]\_\{ij\}=\[H\_\{2\}\(x\)\]\_\{ji\}=3​xi​xj2,i<j\.\\displaystyle=\\frac\{3x\_\{i\}x\_\{j\}\}\{\\sqrt\{2\}\},\\qquad i<j\.\(2\)SetM⁡\(f\)=𝔼f​H2​\(X\)M\(f\)=\\mathbb\{E\}\_\{f\}H\_\{2\}\(X\)\. The normalization accounts for the double occurrence of off\-diagonal entries in the Frobenius norm\.

###### Proposition 2\.1\(Isometric representation\)\.

For any densitiesf,gf,gwith respect toμ\\mu,

‖M⁡\(f\)−M⁡\(g\)‖F=‖P2​\(f−g\)‖L2​\(μ\)\.\\left\\lVert M\(f\)\-M\(g\)\\right\\rVert\_\{\\mathrm\{F\}\}=\\left\\lVert P\_\{2\}\(f\-g\)\\right\\rVert\_\{L^\{2\}\(\\mu\)\}\.Moreover,‖H2​\(x\)‖op≤3​d\\left\\lVert H\_\{2\}\(x\)\\right\\rVert\_\{\\mathrm\{op\}\}\\leq 3dfor allxx, and𝔼μ​\[H2​\(X\)2\]=\(1\+d/2\)​Id\+1\\mathbb\{E\}\_\{\\mu\}\[H\_\{2\}\(X\)^\{2\}\]=\(1\+d/2\)I\_\{d\+1\}\.

The proof is a direct orthogonality calculation and is given in[AppendixA](https://arxiv.org/html/2608.13922#A1)\. The first identity is the core reduction: estimatingP2​fP\_\{2\}fis equivalent to estimating a matrix mean\. It also makes the limitation explicit\. IfP2​\(f−g\)=0P\_\{2\}\(f\-g\)=0, no method using only degree\-two features can distinguishffandggat the population level\.

### 2\.2Piecewise distributions and projected jumps

LetX1,…,Xn∈\[−1,1\]dX\_\{1\},\\ldots,X\_\{n\}\\in\[\-1,1\]^\{d\}be independent for the main theory\. There are change points

0=η0<η1<⋯<ηK<ηK\+1=n0=\\eta\_\{0\}<\\eta\_\{1\}<\\cdots<\\eta\_\{K\}<\\eta\_\{K\+1\}=nand segment densitiesf0,…,fKf\_\{0\},\\ldots,f\_\{K\}such thatXi∼fkX\_\{i\}\\sim f\_\{k\}forηk<i≤ηk\+1\\eta\_\{k\}<i\\leq\\eta\_\{k\+1\}\. Write

Mk=M⁡\(fk\),Dk=Mk−Mk−1,κk=‖Dk‖F\.M\_\{k\}=M\(f\_\{k\}\),\\qquad D\_\{k\}=M\_\{k\}\-M\_\{k\-1\},\\qquad\\kappa\_\{k\}=\\left\\lVert D\_\{k\}\\right\\rVert\_\{\\mathrm\{F\}\}\.We assumerank⁡\(Dk\)≤r\\operatorname\{rank\}\(D\_\{k\}\)\\leq rand define

κ=mink⁡κk,Δ=min1≤k≤K\+1⁡\(ηk−ηk−1\)\.\\kappa=\\min\_\{k\}\\kappa\_\{k\},\\qquad\\Delta=\\min\_\{1\\leq k\\leq K\+1\}\(\\eta\_\{k\}\-\\eta\_\{k\-1\}\)\.The rank assumption concerns the change, not the segment matrices themselves\. For example, changing the dependence of one coordinate pair produces a rank\-two symmetric jump even whenddis large\.

## 3Low\-rank matrix CUSUM

On an interval\(s,e\]\(s,e\]and candidate splits<t<es<t<e, define

M^Ls,e​\(t\)\\displaystyle\\widehat\{M\}\_\{L\}^\{s,e\}\(t\)=1t−s​∑i=s\+1tH2​\(Xi\),\\displaystyle=\\frac\{1\}\{t\-s\}\\sum\_\{i=s\+1\}^\{t\}H\_\{2\}\(X\_\{i\}\),M^Rs,e​\(t\)\\displaystyle\\widehat\{M\}\_\{R\}^\{s,e\}\(t\)=1e−t​∑i=t\+1eH2​\(Xi\),\\displaystyle=\\frac\{1\}\{e\-t\}\\sum\_\{i=t\+1\}^\{e\}H\_\{2\}\(X\_\{i\}\),Δ^CUs,e​\(t\)\\displaystyle\\widehat\{\\Delta\}\_\{\\mathrm\{CU\}\}^\{s,e\}\(t\)=\(t−s\)​\(e−t\)e−s​\{M^Rs,e​\(t\)−M^Ls,e​\(t\)\}\.\\displaystyle=\\sqrt\{\\frac\{\(t\-s\)\(e\-t\)\}\{e\-s\}\}\\left\\\{\\widehat\{M\}\_\{R\}^\{s,e\}\(t\)\-\\widehat\{M\}\_\{L\}^\{s,e\}\(t\)\\right\\\}\.\(3\)LetA\(r\)A\_\{\(r\)\}denote a best rank\-rrapproximation ofAA, obtained by retaining therreigencomponents with largest absolute eigenvalues for symmetricAA\. Our scan score is

W^rs,e​\(t\)=‖\(Δ^CUs,e​\(t\)\)\(r\)‖F\.\\widehat\{W\}\_\{r\}^\{s,e\}\(t\)=\\left\\lVert\\bigl\(\\widehat\{\\Delta\}\_\{\\mathrm\{CU\}\}^\{s,e\}\(t\)\\bigr\)\_\{\(r\)\}\\right\\rVert\_\{\\mathrm\{F\}\}\.\(4\)
Suppose\(s,e\]\(s,e\]contains one changebbfromM0M\_\{0\}toM1M\_\{1\}and writeD=M1−M0D=M\_\{1\}\-M\_\{0\},κ=‖D‖F\\kappa=\\left\\lVert D\\right\\rVert\_\{\\mathrm\{F\}\}\. The population CUSUM has the exact form

ΔCUs,e​\(t\)=𝔼​Δ^CUs,e​\(t\)=abs,e​\(t\)​D,\\Delta\_\{\\mathrm\{CU\}\}^\{s,e\}\(t\)=\\mathbb\{E\}\\widehat\{\\Delta\}\_\{\\mathrm\{CU\}\}^\{s,e\}\(t\)=a\_\{b\}^\{s,e\}\(t\)D,\(5\)where

abs,e​\(t\)=\{e−be−s​t−se−t,t<b,\(b−s\)​\(e−b\)e−s,t=b,b−se−s​e−tt−s,t\>b\.a\_\{b\}^\{s,e\}\(t\)=\\begin\{cases\}\\dfrac\{e\-b\}\{\\sqrt\{e\-s\}\}\\sqrt\{\\dfrac\{t\-s\}\{e\-t\}\},&t<b,\\\\\[4\.73611pt\] \\sqrt\{\\dfrac\{\(b\-s\)\(e\-b\)\}\{e\-s\}\},&t=b,\\\\\[4\.73611pt\] \\dfrac\{b\-s\}\{\\sqrt\{e\-s\}\}\\sqrt\{\\dfrac\{e\-t\}\{t\-s\}\},&t\>b\.\\end\{cases\}\(6\)Hence all candidate population matrices share the same singular vectors and rank\. The coefficient increases tobband decreases afterward\. More strongly,

‖ΔCUs,e​\(b\)‖F2−‖ΔCUs,e​\(t\)‖F2=\{\(e−b\)​\(b−t\)e−t​κ2,t<b,\(b−s\)​\(t−b\)t−s​κ2,t\>b\.\\left\\lVert\\Delta\_\{\\mathrm\{CU\}\}^\{s,e\}\(b\)\\right\\rVert\_\{\\mathrm\{F\}\}^\{2\}\-\\left\\lVert\\Delta\_\{\\mathrm\{CU\}\}^\{s,e\}\(t\)\\right\\rVert\_\{\\mathrm\{F\}\}^\{2\}=\\begin\{cases\}\\dfrac\{\(e\-b\)\(b\-t\)\}\{e\-t\}\\kappa^\{2\},&t<b,\\\\\[4\.30554pt\] \\dfrac\{\(b\-s\)\(t\-b\)\}\{t\-s\}\\kappa^\{2\},&t\>b\.\\end\{cases\}\(7\)This exact linear margin drives localization\.[Figure1](https://arxiv.org/html/2608.13922#S3.F1)illustrates that the rank\-two empirical score follows the population tent in ad=100d=100dependence\-change example\.

Figure 1:Population and empirical rank\-two degree\-two CUSUM scores for oned=100d=100Gaussian\-copula change\. Coordinate means and marginal distributions are unchanged; only the dependence of the first two coordinates changes\.The low\-rank step is controlled by a deterministic inequality\.

###### Proposition 3\.1\(Low\-rank perturbation\)\.

IfA^=A\+E\\widehat\{A\}=A\+E, then

‖A^\(r\)−A‖F≤‖A−A\(r\)‖F\+2​2​r​‖E‖op\.\\left\\lVert\\widehat\{A\}\_\{\(r\)\}\-A\\right\\rVert\_\{\\mathrm\{F\}\}\\leq\\left\\lVert A\-A\_\{\(r\)\}\\right\\rVert\_\{\\mathrm\{F\}\}\+2\\sqrt\{2r\}\\left\\lVert E\\right\\rVert\_\{\\mathrm\{op\}\}\.Consequently, on a one\-change interval withrank⁡\(D\)≤r\\operatorname\{rank\}\(D\)\\leq r,

‖\(Δ^CUs,e​\(t\)\)\(r\)−abs,e​\(t\)​D‖F≤cr​r​‖ECUs,e​\(t\)‖op,cr=2\+2,\\left\\lVert\\bigl\(\\widehat\{\\Delta\}\_\{\\mathrm\{CU\}\}^\{s,e\}\(t\)\\bigr\)\_\{\(r\)\}\-a\_\{b\}^\{s,e\}\(t\)D\\right\\rVert\_\{\\mathrm\{F\}\}\\leq c\_\{r\}\\sqrt\{r\}\\left\\lVert E\_\{\\mathrm\{CU\}\}^\{s,e\}\(t\)\\right\\rVert\_\{\\mathrm\{op\}\},\\qquad c\_\{r\}=2\+\\sqrt\{2\},whereECU=Δ^CU−ΔCUE\_\{\\mathrm\{CU\}\}=\\widehat\{\\Delta\}\_\{\\mathrm\{CU\}\}\-\\Delta\_\{\\mathrm\{CU\}\}\.

The approximation\-tail term for an approximately rank\-rrjump is stated in[SectionC\.1](https://arxiv.org/html/2608.13922#A3.SS1)\.

## 4Multiple changes and cross\-fitted refinement

### 4\.1Seeded interval deletion

Fix a minimum scalemm\. For dyadic lengthsh∈\{m,2​m,4​m,…\}h\\in\\\{m,2m,4m,\\ldots\\\}, form intervals of lengthhhwhose starting points are spaced byh/2h/2; denote the collection byℐm\\mathcal\{I\}\_\{m\}\. OnI=\(s,e\]I=\(s,e\], candidates are restricted to its central half,𝒯I=\{t:s\+h/4≤t≤e−h/4\}\\mathcal\{T\}\_\{I\}=\\\{t:s\+h/4\\leq t\\leq e\-h/4\\\}\. Let

b^I∈arg​maxt∈𝒯I⁡W^rs,e​\(t\),S^I=W^rs,e​\(b^I\)\.\\widehat\{b\}\_\{I\}\\in\\operatorname\*\{arg\\,max\}\_\{t\\in\\mathcal\{T\}\_\{I\}\}\\widehat\{W\}\_\{r\}^\{s,e\}\(t\),\\qquad\\widehat\{S\}\_\{I\}=\\widehat\{W\}\_\{r\}^\{s,e\}\(\\widehat\{b\}\_\{I\}\)\.The interval\-deletion procedure in[Algorithm1](https://arxiv.org/html/2608.13922#alg1)repeatedly takes the shortest interval above threshold and removes that whole interval from further recursion\. Removing an interval rather than splitting exactly atb^I\\widehat\{b\}\_\{I\}makes the induction transparent: once the chosen interval is known to contain one change and to be shorter thanΔ\\Delta, it cannot remove another change\.

Algorithm 1Seeded\-LR\-D2: seeded low\-rank degree\-two detection1:Data

X1:nX\_\{1:n\}, rank

rr, minimum scale

mm, threshold

τ\\tau
2:Form

ℐm\\mathcal\{I\}\_\{m\}and compute

\(b^I,S^I\)\(\\widehat\{b\}\_\{I\},\\widehat\{S\}\_\{I\}\)for all

I∈ℐmI\\in\\mathcal\{I\}\_\{m\}
3:Initialize active component list

𝒞←\{\(0,n\]\}\\mathcal\{C\}\\leftarrow\\\{\(0,n\]\\\}and output

ℬ^←∅\\widehat\{\\mathcal\{B\}\}\\leftarrow\\varnothing
4:whilesome

I∈ℐmI\\in\\mathcal\{I\}\_\{m\}is contained in a component in

𝒞\\mathcal\{C\}and

S^I\>τ\\widehat\{S\}\_\{I\}\>\\taudo

5:Choose a shortest such

I∗=\(s∗,e∗\]I^\{\*\}=\(s^\{\*\},e^\{\*\}\]; append

\(I∗,b^I∗\)\(I^\{\*\},\\widehat\{b\}\_\{I^\{\*\}\}\)to

ℬ^\\widehat\{\\mathcal\{B\}\}
6:Replace the containing component

\(a,c\]\(a,c\]by the nonempty components

\(a,s∗\]\(a,s^\{\*\}\]and

\(e∗,c\]\(e^\{\*\},c\]
7:endwhile

8:return

ℬ^\\widehat\{\\mathcal\{B\}\}

### 4\.2Cross\-fitted local refinement

A selected intervalIk=\(sk,ek\]I\_\{k\}=\(s\_\{k\},e\_\{k\}\]identifies one change but need not provide the optimal rate\. We expand it to a one\-change window and split the observations by parity\. On the pilot fold, scan the window and normalize the rank\-rrCUSUM at its maximizer:

V^k=\(Δ^CUpilot\)\(r\)‖\(Δ^CUpilot\)\(r\)‖F\.\\widehat\{V\}\_\{k\}=\\frac\{\(\\widehat\{\\Delta\}\_\{\\mathrm\{CU\}\}^\{\\mathrm\{pilot\}\}\)\_\{\(r\)\}\}\{\\left\\lVert\(\\widehat\{\\Delta\}\_\{\\mathrm\{CU\}\}^\{\\mathrm\{pilot\}\}\)\_\{\(r\)\}\\right\\rVert\_\{\\mathrm\{F\}\}\}\.On the held\-out fold, projectZi=⟨H2​\(Xi\),V^k⟩Z\_\{i\}=\\left\\langle H\_\{2\}\(X\_\{i\}\),\\widehat\{V\}\_\{k\}\\right\\rangle\. Disjoint outer anchor blocks estimate the left and right projected means,μ^L,k\\widehat\{\\mu\}\_\{L,k\}andμ^R,k\\widehat\{\\mu\}\_\{R,k\}\. Over the central search region, define

Qk​\(t\)=∑i≤t\(Zi−μ^L,k\)2\+∑i\>t\(Zi−μ^R,k\)2,η~k∈arg​mint⁡Qk​\(t\)\.Q\_\{k\}\(t\)=\\sum\_\{i\\leq t\}\(Z\_\{i\}\-\\widehat\{\\mu\}\_\{L,k\}\)^\{2\}\+\\sum\_\{i\>t\}\(Z\_\{i\}\-\\widehat\{\\mu\}\_\{R,k\}\)^\{2\},\\qquad\\widetilde\{\\eta\}\_\{k\}\\in\\operatorname\*\{arg\\,min\}\_\{t\}Q\_\{k\}\(t\)\.\(8\)The pilot direction and held\-out noise are independent\. Conditional on a well\-aligned direction, the problem reduces to a scalar mean change whose effective jump is at least a constant fraction ofκk\\kappa\_\{k\}\.

## 5Theory

Assume throughout this section that every segment density is bounded byLLrelative toμ\\mu\. Let𝒢\\mathcal\{G\}be all triples\(s,t,e\)\(s,t,e\)scanned by the seeded collection and set

ℓ𝒢,δ=log⁡2​\(d\+1\)​\|𝒢\|δ,λm​\(δ\)=2​L​\(1\+d/2\)​ℓ𝒢,δ\+8​d​ℓ𝒢,δm\.\\ell\_\{\\mathcal\{G\},\\delta\}=\\log\\frac\{2\(d\+1\)\|\\mathcal\{G\}\|\}\{\\delta\},\\qquad\\lambda\_\{m\}\(\\delta\)=\\sqrt\{2L\(1\+d/2\)\\ell\_\{\\mathcal\{G\},\\delta\}\}\+\\frac\{8d\\ell\_\{\\mathcal\{G\},\\delta\}\}\{\\sqrt\{m\}\}\.For half\-overlapping dyadic intervals,\|𝒢\|=O⁡\(n​log⁡\(n/m\)\)\|\\mathcal\{G\}\|=O\(n\\log\(n/m\)\)\.

###### Theorem 5\.1\(Uniform CUSUM and low\-rank control\)\.

With probability at least1−δ1\-\\delta,

sup\(s,t,e\)∈𝒢‖ECUs,e​\(t\)‖op≤λm​\(δ\)\.\\sup\_\{\(s,t,e\)\\in\\mathcal\{G\}\}\\left\\lVert E\_\{\\mathrm\{CU\}\}^\{s,e\}\(t\)\\right\\rVert\_\{\\mathrm\{op\}\}\\leq\\lambda\_\{m\}\(\\delta\)\.On every scanned interval containing one change with rank at mostrr,

supt∈𝒯I\|W^rs,e​\(t\)−abs,e​\(t\)​κ\|≤εr,εr=cr​r​λm​\(δ\)\.\\sup\_\{t\\in\\mathcal\{T\}\_\{I\}\}\\left\|\\widehat\{W\}\_\{r\}^\{s,e\}\(t\)\-a\_\{b\}^\{s,e\}\(t\)\\kappa\\right\|\\leq\\varepsilon\_\{r\},\\qquad\\varepsilon\_\{r\}=c\_\{r\}\\sqrt\{r\}\\lambda\_\{m\}\(\\delta\)\.

The first term inλm\\lambda\_\{m\}is≍L​d​log⁡\(n​d/δ\)\\asymp\\sqrt\{Ld\\log\(nd/\\delta\)\}and does not grow with interval length because the CUSUM weights have squared sum one\. The second term is the bounded\-summand correction and is lower order whenm≫d​log⁡\(n​d\)m\\gg d\\log\(nd\)\.

###### Theorem 5\.2\(Exact multiple\-change recovery by induction\)\.

Supposem≤Δ/8m\\leq\\Delta/8,rank⁡\(Dk\)≤r\\operatorname\{rank\}\(D\_\{k\}\)\\leq r, and the threshold satisfies

r​λm​\(δ\)<τ<Δ8​2​κ−εr\.\\sqrt\{r\}\\lambda\_\{m\}\(\\delta\)<\\tau<\\frac\{\\sqrt\{\\Delta\}\}\{8\\sqrt\{2\}\}\\kappa\-\\varepsilon\_\{r\}\.\(9\)Then, on the event of[Theorem5\.1](https://arxiv.org/html/2608.13922#S5.Thmtheorem1),Seeded\-LR\-D2returns exactlyKKintervals\. They are in one\-to\-one correspondence with the true change points; every selected interval contains exactly oneηk\\eta\_\{k\}and has length at mostΔ/4\\Delta/4\. In particular, its recorded maximizer satisfies\|b^k−ηk\|≤Δ/4\|\\widehat\{b\}\_\{k\}\-\\eta\_\{k\}\|\\leq\\Delta/4\.

The proof, in[AppendixE](https://arxiv.org/html/2608.13922#A5), follows the requested induction\. At each stage: \(i\) an interval with no remaining change has score belowτ\\tau; \(ii\) every remaining change has a balanced isolating seeded interval of length in\[Δ/8,Δ/4\]\[\\Delta/8,\\Delta/4\]whose score exceedsτ\\tau; and \(iii\) the shortest active interval is therefore shorter thanΔ\\Deltaand must contain exactly one change\. Deleting it leaves every other change at least3​Δ/43\\Delta/4from the new component boundary, preserving the induction hypothesis\.

###### Corollary 5\.3\(Preliminary localization on a one\-change window\)\.

Let\(s,e\]\(s,e\]contain one changebb, letN=e−sN=e\-s, and supposebband all candidates are at leastα​N\\alpha Nfrom the endpoints\. Under the uniform event and exact rank,

\|b^−b\|≤2​crα​N​r​λm​\(δ\)κ\.\|\\widehat\{b\}\-b\|\\leq\\frac\{2c\_\{r\}\}\{\\alpha\}\\frac\{\\sqrt\{Nr\}\\,\\lambda\_\{m\}\(\\delta\)\}\{\\kappa\}\.

This rate is sufficient to isolate changes but is not generally minimax\. The refinement removes the factorN\\sqrt\{N\}\.

For the refinement, assume that for every deterministicVVwith‖V‖F=1\\left\\lVert V\\right\\rVert\_\{\\mathrm\{F\}\}=1, the centered scalar projectionξ=⟨H2​\(X\)−Mk,V⟩\\xi=\\left\\langle H\_\{2\}\(X\)\-M\_\{k\},V\\right\\ranglesatisfies the Bernstein moment\-generating\-function condition

log⁡𝔼​eλ​ξ≤λ2​ν22​\(1−B​\|λ\|\),\|λ\|<B−1\.\\log\\mathbb\{E\}e^\{\\lambda\\xi\}\\leq\\frac\{\\lambda^\{2\}\\nu^\{2\}\}\{2\(1\-B\|\\lambda\|\)\},\\qquad\|\\lambda\|<B^\{\-1\}\.\(10\)In particular, for independent projections this implies

ℙ⁡\(\|∑i=1qξi\|≥x\)≤2​exp​\[−c​min​\{x2q​ν2,xB\}\],\\mathbb\{P\}\\\!\\left\(\\left\|\\sum\_\{i=1\}^\{q\}\\xi\_\{i\}\\right\|\\geq x\\right\)\\leq 2\\exp\\left\[\-c\\min\\left\\\{\\frac\{x^\{2\}\}\{q\\nu^\{2\}\},\\frac\{x\}\{B\}\\right\\\}\\right\],\(11\)as well as the maximal line\-crossing inequality used in the proof\. Bounded observations always give conservative parameters of orderdd; for independent sub\-Gaussian coordinates, quadratic\-form concentration can make them dimension\-free up to constants\.

###### Theorem 5\.4\(Cross\-fitted localization\)\.

Consider a one\-change refinement window with pure outer anchor blocks of sizeqq\. Suppose the pilot fold yields‖V^‖F=1\\left\\lVert\\widehat\{V\}\\right\\rVert\_\{\\mathrm\{F\}\}=1and⟨D,V^⟩≥κ/2\\left\\langle D,\\widehat\{V\}\\right\\rangle\\geq\\kappa/2\. If

q≥C⁡\(ν2κ2\+Bκ\)​log⁡Kδ,q\\geq C\\left\(\\frac\{\\nu^\{2\}\}\{\\kappa^\{2\}\}\+\\frac\{B\}\{\\kappa\}\\right\)\\log\\frac\{K\}\{\\delta\},then, simultaneously for allKKwindows, with probability at least1−δ1\-\\delta,

\|η~k−ηk\|≤C⁡\(ν2κk2\+Bκk\)​log⁡Kδ\+1\.\|\\widetilde\{\\eta\}\_\{k\}\-\\eta\_\{k\}\|\\leq C\\left\(\\frac\{\\nu^\{2\}\}\{\\kappa\_\{k\}^\{2\}\}\+\\frac\{B\}\{\\kappa\_\{k\}\}\\right\)\\log\\frac\{K\}\{\\delta\}\+1\.\(12\)Moreover, the direction condition holds whenever the pilot population CUSUM at its maximizer is at least8​εr8\\varepsilon\_\{r\}\.

The extra11accounts for mapping the parity fold back to the original time index\. In the usual small\-jump regime the first term dominates, givingO~ℙ​\(κk−2\)\\widetilde\{O\}\_\{\\mathbb\{P\}\}\(\\kappa\_\{k\}^\{\-2\}\)\.

###### Theorem 5\.5\(Minimax lower bound\)\.

There are constantsc,c0\>0c,c\_\{0\}\>0such that, for0<κ≤c00<\\kappa\\leq c\_\{0\}and a single change separated from the endpoints by at leastc​κ−2c\\kappa^\{\-2\},

infη^supP∈𝒫⁡\(κ\)𝔼P​\|η^−η⁡\(P\)\|≥cκ2,\\inf\_\{\\widehat\{\\eta\}\}\\sup\_\{P\\in\\mathcal\{P\}\(\\kappa\)\}\\mathbb\{E\}\_\{P\}\|\\widehat\{\\eta\}\-\\eta\(P\)\|\\geq\\frac\{c\}\{\\kappa^\{2\}\},where𝒫⁡\(κ\)\\mathcal\{P\}\(\\kappa\)is a class of densities on\[−1,1\]d\[\-1,1\]^\{d\}whose degree\-two jump has Frobenius normκ\\kappaand rank two\.

The construction usesfθ​\(x\)=1\+3​θ​x1​x2f\_\{\\theta\}\(x\)=1\+3\\theta x\_\{1\}x\_\{2\}, for which the jump matrix has rank two and Frobenius norm\|θ\|\|\\theta\|\. Moving the change byhhalters the likelihood in onlyhhobservations and gives KL divergenceO⁡\(h​θ2\)O\(h\\theta^\{2\}\); Le Cam’s method withh≍θ−2h\\asymp\\theta^\{\-2\}proves the result\.

#### Temporal dependence\.

IfZi=H2​\(Xi\)−𝔼​H2​\(Xi\)Z\_\{i\}=H\_\{2\}\(X\_\{i\}\)\-\\mathbb\{E\}H\_\{2\}\(X\_\{i\}\)is uniformly geometricallyβ\\beta\-mixing and‖Zi‖op≤Bd\\left\\lVert Z\_\{i\}\\right\\rVert\_\{\\mathrm\{op\}\}\\leq B\_\{d\}, the weighted CUSUM is a dependent self\-adjoint matrix sum\. The Bernstein inequality of[3](https://arxiv.org/html/2608.13922#bib.bib3)yields a replacementλmmix\\lambda\_\{m\}^\{\\mathrm\{mix\}\}involving its dependent variance proxy and a logarithmic mixing penalty\. Since[Theorem5\.2](https://arxiv.org/html/2608.13922#S5.Thmtheorem2)is deterministic conditional on uniform CUSUM control, the entire induction carries over after replacingλm\\lambda\_\{m\}byλmmix\\lambda\_\{m\}^\{\\mathrm\{mix\}\}; see[AppendixI](https://arxiv.org/html/2608.13922#A9)\.

## 6Experiments

All experiments use the sameH2H\_\{2\}implementation and symmetric eigentruncation\. The preliminary scans use the odd observations; the even observations are reserved for refinement\. Full settings, seeds, and additional tables are in[AppendixJ](https://arxiv.org/html/2608.13922#A10)\.

#### Dimension scaling\.

We generate Gaussian\-copula observations with uniform marginals\. Only the dependence between coordinates11and22changes, from copula correlation00to0\.850\.85atn/2n/2; all coordinate means and marginals remain unchanged\. The projected jump is rank two\. We setn=60​dn=60dand run5050replications ford∈\{20,50,100,200\}d\\in\\\{20,50,100,200\\\}\. The median absolute errors are reported in[Table1](https://arxiv.org/html/2608.13922#S6.T1)and[Figure2](https://arxiv.org/html/2608.13922#S6.F2)\.LR\-D2remains near the oracle pair projection, whereas the unregularized full degree\-two score degrades withddand mean CUSUM is uninformative\. Atd=200,n=12000d=200,n=12000, the refined median error is44and the mean runtime for the complete five\-method replicate is0\.920\.92seconds on the evaluation machine\.

Table 1:Median absolute localization error over5050single\-change replications\. “Full D2” uses the Frobenius norm without rank truncation; “Oracle” knows the affected interaction\.Figure 2:Median single\-change error versus ambient dimension\. Sample size scales asn=60​dn=60d\. The low\-rank estimator remains stable throughd=200d=200, while the full degree\-two and mean scans accumulate high\-dimensional noise\.
#### Multiple changes ind=100d=100\.

We usen=24000n=24000and changes at\(6000,12000,18000\)\(6000,12000,18000\), alternating the first\-pair copula correlation between0\.950\.95and−0\.95\-0\.95\. A threshold of3030is rounded above the maximum of six independent null scans\. Across1212replications,Seeded\-LR\-D2estimatesK=3K=3every time\. The median Hausdorff error is22before and11after refinement; all refined estimates are within1010time points, and mean runtime is8\.938\.93seconds\.

#### UCI human activity, 128 features\.

From the UCI smartphone activity data\([1](https://arxiv.org/html/2608.13922#bib.bib2)\), we take400400walking and400400walking\-downstairs observations and select the128128highest\-variance features\. An independent Rademacher sign is applied to every row, eliminating first moments while preserving all degree\-two products\. Over5050randomized replications, refinedLR\-D2has median error00, exact recovery rate72%72\\%, and error at most44in94%94\\%of runs\. Full D2 has median00but does not benefit from rank regularization; mean CUSUM has median error256256and never falls within44\.

## 7Discussion and limitations

Degree\-two projection turns a broad class of nonparametric changes into a structured matrix\-mean problem\. The representation is especially useful when a high\-dimensional dependence change is generated by a small number of interaction directions\. The multiple\-change induction and cross\-fitted refinement separate three tasks that are often conflated: detecting a signal, isolating each change, and obtaining the optimal local rate\.

The method intentionally does not detect every possible density change\. A change orthogonal to all degree\-at\-most\-two polynomials is invisible, and higher\-degree extensions require tensor structure or another finite feature family\. Exact theory assumes low\-rank projected jumps; approximate rank introduces a transparent singular\-value\-tail bias\. The sharp refinement theorem is stated for independent observations, while the current dependent theory directly covers the preliminary matrix scan and multiple\-change induction\. Finally, the empirical study is designed to validate scaling and identifiability rather than claim dominance on every change\-point benchmark\. Richer learned feature maps and adaptive rank selection are important next steps\.

## Ethics statement

This work develops a statistical method and uses public or synthetic data\. The UCI human\-activity data are used only for a methodological benchmark; no attempt is made to infer sensitive personal attributes\. Failure to detect a change should not be interpreted as evidence that two underlying distributions are identical, because the method tests only the chosen degree\-two representation\.

## Reproducibility statement

The appendices give complete proofs of all stated results, the exact feature normalization, pseudocode, simulation distributions, tuning rules, and additional numerical summaries\. The supplementary code generates every reported table and figure from fixed seeds\. The UCI data are not redistributed; the code documents the public source and expected file layout\.

## AI use statement

Generative AI tools \(OpenAI GPT\-5\.6 Pro\) were used to help formalize parts of the methodology, formulate and check mathematical claims, assist with proof development, design and implement synthetic and UCI\-HAR experiments, interpret numerical outputs, and edit and format the manuscript\. All AI\-assisted derivations, code, numerical results, citations, and prose were reviewed by the authors, who take responsibility for the final content and for independently verifying it before submission\.

## References

- D\. Anguita, A\. Ghio, L\. Oneto, X\. Parra, and J\. L\. Reyes\-OrtizA public domain dataset for human activity recognition using smartphones\.InEuropean Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning,pp\. 437–442\.Cited by:[§J\.4](https://arxiv.org/html/2608.13922#A10.SS4.p1.1),[§6](https://arxiv.org/html/2608.13922#S6.SS0.SSS0.Px3.p1.1)\.
- Aueet al\.\(2018\)A\. Aue, G\. Rice, and O\. SönmezDetecting and dating structural breaks in functional data without dimension reduction\.Journal of the Royal Statistical Society: Series B80\(3\),pp\. 509–529\.Cited by:[§1](https://arxiv.org/html/2608.13922#S1.SS0.SSS0.Px2.p1.1)\.
- Bannaet al\.\(2016\)M\. Banna, F\. Merlevède, and P\. YoussefBernstein\-type inequality for a class of dependent random matrices\.Random Matrices: Theory and Applications5\(2\),pp\. 1650006\.Cited by:[Appendix I](https://arxiv.org/html/2608.13922#A9.p3.1),[§1](https://arxiv.org/html/2608.13922#S1.SS0.SSS0.Px2.p1.1),[§5](https://arxiv.org/html/2608.13922#S5.SS0.SSS0.Px1.p1.1)\.
- Baranowskiet al\.\(2019\)R\. Baranowski, Y\. Chen, and P\. FryzlewiczNarrowest\-over\-threshold detection of multiple change points and change\-point\-like features\.Journal of the Royal Statistical Society: Series B81\(3\),pp\. 649–672\.Cited by:[§1](https://arxiv.org/html/2608.13922#S1.SS0.SSS0.Px2.p1.1)\.
- Cho and Fryzlewicz \(2015\)H\. Cho and P\. FryzlewiczMultiple\-change\-point detection for high dimensional time series via sparsified binary segmentation\.Journal of the Royal Statistical Society: Series B77\(2\),pp\. 475–507\.Cited by:[§1](https://arxiv.org/html/2608.13922#S1.SS0.SSS0.Px2.p1.1)\.
- Enikeeva and Harchaoui \(2019\)F\. Enikeeva and Z\. HarchaouiHigh\-dimensional change\-point detection with sparse alternatives\.The Annals of Statistics47\(4\),pp\. 2051–2079\.Cited by:[§1](https://arxiv.org/html/2608.13922#S1.SS0.SSS0.Px2.p1.1)\.
- Fryzlewicz \(2014\)P\. FryzlewiczWild binary segmentation for multiple change\-point detection\.The Annals of Statistics42\(6\),pp\. 2243–2281\.Cited by:[§1](https://arxiv.org/html/2608.13922#S1.SS0.SSS0.Px2.p1.1)\.
- Grettonet al\.\(2012\)A\. Gretton, K\. M\. Borgwardt, M\. J\. Rasch, B\. Schölkopf, and A\. SmolaA kernel two\-sample test\.Journal of Machine Learning Research13,pp\. 723–773\.Cited by:[§1](https://arxiv.org/html/2608.13922#S1.SS0.SSS0.Px2.p1.1)\.
- Harchaoui and Cappé \(2007\)Z\. Harchaoui and O\. CappéRetrospective multiple change\-point estimation with kernels\.InIEEE/SP Workshop on Statistical Signal Processing,pp\. 768–772\.Cited by:[§1](https://arxiv.org/html/2608.13922#S1.SS0.SSS0.Px2.p1.1)\.
- Kovácset al\.\(2023\)S\. Kovács, P\. Bühlmann, H\. Li, and A\. MunkSeeded binary segmentation: a general methodology for fast and optimal changepoint detection\.Biometrika110\(1\),pp\. 249–256\.Cited by:[§1](https://arxiv.org/html/2608.13922#S1.SS0.SSS0.Px2.p1.1)\.
- Kumaret al\.\(2024\)S\. Kumar, H\. Xu, H\. Cho, and D\. WangEstimation and inference for change points in functional regression time series\.External Links:2405\.05459Cited by:[§1](https://arxiv.org/html/2608.13922#S1.SS0.SSS0.Px2.p1.1)\.
- Madrid Padillaet al\.\(2022a\)C\. M\. Madrid Padilla, D\. Wang, Z\. Zhao, and Y\. YuChange\-point detection for sparse and dense functional data in general dimensions\.InAdvances in Neural Information Processing Systems,Vol\.35,pp\. 37121–37133\.Cited by:[§1](https://arxiv.org/html/2608.13922#S1.SS0.SSS0.Px2.p1.1)\.
- Madrid Padillaet al\.\(2022b\)O\. H\. Madrid Padilla, Y\. Yu, D\. Wang, and A\. RinaldoOptimal nonparametric multivariate change point detection and localization\.IEEE Transactions on Information Theory68\(3\),pp\. 1922–1944\.Cited by:[§1](https://arxiv.org/html/2608.13922#S1.SS0.SSS0.Px2.p1.1)\.
- Tropp \(2012\)J\. A\. TroppUser\-friendly tail bounds for sums of random matrices\.Foundations of Computational Mathematics12\(4\),pp\. 389–434\.Cited by:[Appendix D](https://arxiv.org/html/2608.13922#A4.p2.3.1),[§1](https://arxiv.org/html/2608.13922#S1.SS0.SSS0.Px2.p1.1)\.
- Wang and Samworth \(2018\)T\. Wang and R\. J\. SamworthHigh dimensional change point estimation via sparse projection\.Journal of the Royal Statistical Society: Series B80\(1\),pp\. 57–83\.Cited by:[§1](https://arxiv.org/html/2608.13922#S1.SS0.SSS0.Px2.p1.1)\.

## Appendix ADegree\-two representation: complete calculations

This section proves[Proposition2\.1](https://arxiv.org/html/2608.13922#S2.Thmtheorem1)and records the identities used by the concentration argument\. Throughout,μ\\muis the product uniform probability measure on\[−1,1\]d\[\-1,1\]^\{d\}\.

### A\.1Orthogonal projection coefficients

The one\-dimensional Legendre polynomials used in the paper satisfy

∫p02​d​μ1=1,∫p12​d​μ1=13,∫p22​d​μ1=15,\\int p\_\{0\}^\{2\}\\,d\\mu\_\{1\}=1,\\qquad\\int p\_\{1\}^\{2\}\\,d\\mu\_\{1\}=\\frac\{1\}\{3\},\\qquad\\int p\_\{2\}^\{2\}\\,d\\mu\_\{1\}=\\frac\{1\}\{5\},and distinct polynomials amongp0,p1,p2p\_\{0\},p\_\{1\},p\_\{2\}are orthogonal\. Becauseμ\\muis a product measure, an orthogonal basis for the total\-degree\-at\-most\-two subspace is

1,\{xj\}j=1d,\{p2​\(xj\)\}j=1d,\{xi​xj\}1≤i<j≤d\.1,\\quad\\\{x\_\{j\}\\\}\_\{j=1\}^\{d\},\\quad\\\{p\_\{2\}\(x\_\{j\}\)\\\}\_\{j=1\}^\{d\},\\quad\\\{x\_\{i\}x\_\{j\}\\\}\_\{1\\leq i<j\\leq d\}\.Iff=d​P/d​μf=dP/d\\mu, the coefficient of a basis elementϕ\\phiin the orthogonal projection is⟨f,ϕ⟩/‖ϕ‖22=𝔼f​ϕ​\(X\)/‖ϕ‖22\\langle f,\\phi\\rangle/\\\|\\phi\\\|\_\{2\}^\{2\}=\\mathbb\{E\}\_\{f\}\\phi\(X\)/\\\|\\phi\\\|\_\{2\}^\{2\}\. This gives

aj=3​𝔼f​Xj,bj=5​𝔼f​p2​\(Xj\),γi​j=9​𝔼f​\(Xi​Xj\),a\_\{j\}=3\\mathbb\{E\}\_\{f\}X\_\{j\},\\qquad b\_\{j\}=5\\mathbb\{E\}\_\{f\}p\_\{2\}\(X\_\{j\}\),\\qquad\\gamma\_\{ij\}=9\\mathbb\{E\}\_\{f\}\(X\_\{i\}X\_\{j\}\),and proves \([1](https://arxiv.org/html/2608.13922#S2.E1)\)\.

The expectation matrixM⁡\(f\)=𝔼f​H2​\(X\)M\(f\)=\\mathbb\{E\}\_\{f\}H\_\{2\}\(X\)has entries

M\(f\)00=1,M\(f\)0​j=aj6,M\(f\)j​j=bj5,M\(f\)i​j=γi​j3​2\(i<j\)\.M\(f\)\_\{00\}=1,\\qquad M\(f\)\_\{0j\}=\\frac\{a\_\{j\}\}\{\\sqrt\{6\}\},\\qquad M\(f\)\_\{jj\}=\\frac\{b\_\{j\}\}\{\\sqrt\{5\}\},\\qquad M\(f\)\_\{ij\}=\\frac\{\\gamma\_\{ij\}\}\{3\\sqrt\{2\}\}\\quad\(i<j\)\.\(13\)Thus the apparently nonparametric objectP2​fP\_\{2\}fis estimated by the ordinary sample mean of a fixed matrix\-valued feature map\.

### A\.2Proof of the isometry

###### Proof of the first assertion in[Proposition2\.1](https://arxiv.org/html/2608.13922#S2.Thmtheorem1)\.

By orthogonality,

‖P2​f‖L2​\(μ\)2=1\+∑j=1daj23\+∑j=1dbj25\+∑i<jγi​j29\.\\left\\lVert P\_\{2\}f\\right\\rVert\_\{L^\{2\}\(\\mu\)\}^\{2\}=1\+\\sum\_\{j=1\}^\{d\}\\frac\{a\_\{j\}^\{2\}\}\{3\}\+\\sum\_\{j=1\}^\{d\}\\frac\{b\_\{j\}^\{2\}\}\{5\}\+\\sum\_\{i<j\}\\frac\{\\gamma\_\{ij\}^\{2\}\}\{9\}\.\(14\)Using \([13](https://arxiv.org/html/2608.13922#A1.E13)\) and remembering that every off\-diagonal entry occurs twice in the Frobenius norm,

‖M⁡\(f\)‖F2\\displaystyle\\left\\lVert M\(f\)\\right\\rVert\_\{\\mathrm\{F\}\}^\{2\}=1\+2​∑j=1daj26\+∑j=1dbj25\+2​∑i<jγi​j218\\displaystyle=1\+2\\sum\_\{j=1\}^\{d\}\\frac\{a\_\{j\}^\{2\}\}\{6\}\+\\sum\_\{j=1\}^\{d\}\\frac\{b\_\{j\}^\{2\}\}\{5\}\+2\\sum\_\{i<j\}\\frac\{\\gamma\_\{ij\}^\{2\}\}\{18\}=1\+∑j=1daj23\+∑j=1dbj25\+∑i<jγi​j29\.\\displaystyle=1\+\\sum\_\{j=1\}^\{d\}\\frac\{a\_\{j\}^\{2\}\}\{3\}\+\\sum\_\{j=1\}^\{d\}\\frac\{b\_\{j\}^\{2\}\}\{5\}\+\\sum\_\{i<j\}\\frac\{\\gamma\_\{ij\}^\{2\}\}\{9\}\.The same calculation applied to the coefficient differences offfandggproves

‖M⁡\(f\)−M⁡\(g\)‖F2=‖P2​\(f−g\)‖L2​\(μ\)2\.\\left\\lVert M\(f\)\-M\(g\)\\right\\rVert\_\{\\mathrm\{F\}\}^\{2\}=\\left\\lVert P\_\{2\}\(f\-g\)\\right\\rVert\_\{L^\{2\}\(\\mu\)\}^\{2\}\.∎

### A\.3Envelope and isotropic second moment

###### Lemma A\.1\(Uniform matrix envelope\)\.

For everyx∈\[−1,1\]dx\\in\[\-1,1\]^\{d\},

‖H2​\(x\)‖op≤‖H2​\(x\)‖F≤3​d\.\\left\\lVert H\_\{2\}\(x\)\\right\\rVert\_\{\\mathrm\{op\}\}\\leq\\left\\lVert H\_\{2\}\(x\)\\right\\rVert\_\{\\mathrm\{F\}\}\\leq 3d\.Consequently, for any densityff,‖M⁡\(f\)‖op≤3​d\\\|M\(f\)\\\|\_\{\\mathrm\{op\}\}\\leq 3dand‖H2​\(X\)−M⁡\(f\)‖op≤6​d\\\|H\_\{2\}\(X\)\-M\(f\)\\\|\_\{\\mathrm\{op\}\}\\leq 6dalmost surely\.

###### Proof\.

Since\|p2​\(x\)\|≤1\|p\_\{2\}\(x\)\|\\leq 1on\[−1,1\]\[\-1,1\], direct summation gives

‖H2​\(x\)‖F2\\displaystyle\\left\\lVert H\_\{2\}\(x\)\\right\\rVert\_\{\\mathrm\{F\}\}^\{2\}≤1\+2​d​96\+5​d\+2​\(d2\)​92\\displaystyle\\leq 1\+2d\\frac\{9\}\{6\}\+5d\+2\\binom\{d\}\{2\}\\frac\{9\}\{2\}=1\+8​d\+92​d​\(d−1\)≤9​d2,\\displaystyle=1\+8d\+\\frac\{9\}\{2\}d\(d\-1\)\\leq 9d^\{2\},for everyd≥1d\\geq 1\. Jensen’s inequality gives‖M⁡\(f\)‖op≤𝔼f​‖H2​\(X\)‖op≤3​d\\\|M\(f\)\\\|\_\{\\mathrm\{op\}\}\\leq\\mathbb\{E\}\_\{f\}\\\|H\_\{2\}\(X\)\\\|\_\{\\mathrm\{op\}\}\\leq 3d, and the centered bound follows by the triangle inequality\. ∎

###### Lemma A\.2\(Exact reference second moment\)\.

IfX∼μX\\sim\\mu, then

𝔼μ​\[H2​\(X\)2\]=\(1\+d2\)​Id\+1\.\\mathbb\{E\}\_\{\\mu\}\[H\_\{2\}\(X\)^\{2\}\]=\\left\(1\+\\frac\{d\}\{2\}\\right\)I\_\{d\+1\}\.

###### Proof\.

Write indices as0,1,…,d0,1,\\ldots,d\. For the\(0,0\)\(0,0\)entry,

𝔼​\(H22\)00=1\+∑j=1d32​𝔼​Xj2=1\+d2\.\\mathbb\{E\}\(H\_\{2\}^\{2\}\)\_\{00\}=1\+\\sum\_\{j=1\}^\{d\}\\frac\{3\}\{2\}\\mathbb\{E\}X\_\{j\}^\{2\}=1\+\\frac\{d\}\{2\}\.Forj≥1j\\geq 1,

𝔼​\(H22\)j​j\\displaystyle\\mathbb\{E\}\(H\_\{2\}^\{2\}\)\_\{jj\}=32​𝔼​Xj2\+5​𝔼​p2​\(Xj\)2\+∑k≠j92​𝔼​\(Xj2​Xk2\)\\displaystyle=\\frac\{3\}\{2\}\\mathbb\{E\}X\_\{j\}^\{2\}\+5\\mathbb\{E\}p\_\{2\}\(X\_\{j\}\)^\{2\}\+\\sum\_\{k\\neq j\}\\frac\{9\}\{2\}\\mathbb\{E\}\(X\_\{j\}^\{2\}X\_\{k\}^\{2\}\)=12\+1\+d−12=1\+d2\.\\displaystyle=\\frac\{1\}\{2\}\+1\+\\frac\{d\-1\}\{2\}=1\+\\frac\{d\}\{2\}\.Every off\-diagonal entry has expectation zero\. For example,\(H22\)0​j\(H\_\{2\}^\{2\}\)\_\{0j\}is a sum of terms proportional toXjX\_\{j\},Xj​p2​\(Xj\)X\_\{j\}p\_\{2\}\(X\_\{j\}\), orXj​Xk2X\_\{j\}X\_\{k\}^\{2\}, all of which have zero expectation\. Forj≠kj\\neq k, every term in\(H22\)j​k\(H\_\{2\}^\{2\}\)\_\{jk\}contains an odd power of eitherXjX\_\{j\}orXkX\_\{k\}\. Independence and symmetry of the coordinates complete the proof\. ∎

Iff≤Lf\\leq Lrelative toμ\\mu, the last lemma implies the Loewner bound

𝔼f​\[H2​\(X\)2\]=∫H2​\(x\)2​f​\(x\)​𝑑μ​\(x\)⪯L⁡\(1\+d2\)​Id\+1\.\\mathbb\{E\}\_\{f\}\[H\_\{2\}\(X\)^\{2\}\]=\\int H\_\{2\}\(x\)^\{2\}f\(x\)\\,d\\mu\(x\)\\preceq L\\left\(1\+\\frac\{d\}\{2\}\\right\)I\_\{d\+1\}\.\(15\)This is the point at which the bounded\-density assumption enters the simple independent\-observation theory\.

## Appendix BPopulation matrix CUSUM on a one\-change interval

Suppose\(s,e\]\(s,e\]contains exactly one changebb, with matrix meansM0M\_\{0\}beforebbandM1M\_\{1\}afterbb, and putD=M1−M0D=M\_\{1\}\-M\_\{0\}\.

###### Proof of \([5](https://arxiv.org/html/2608.13922#S3.E5)\)–\([6](https://arxiv.org/html/2608.13922#S3.E6)\)\.

Ift<bt<b, the left empirical mean is unbiased forM0M\_\{0\}, while the right mean has expectation

b−te−t​M0\+e−be−t​M1\.\\frac\{b\-t\}\{e\-t\}M\_\{0\}\+\\frac\{e\-b\}\{e\-t\}M\_\{1\}\.Therefore

𝔼⁡\(M^R−M^L\)=e−be−t​D,\\mathbb\{E\}\(\\widehat\{M\}\_\{R\}\-\\widehat\{M\}\_\{L\}\)=\\frac\{e\-b\}\{e\-t\}D,and multiplication by the CUSUM normalizer gives the first branch of \([6](https://arxiv.org/html/2608.13922#S3.E6)\)\. Ift\>bt\>b, the right mean is unbiased forM1M\_\{1\}, while

𝔼​M^L=b−st−s​M0\+t−bt−s​M1,\\mathbb\{E\}\\widehat\{M\}\_\{L\}=\\frac\{b\-s\}\{t\-s\}M\_\{0\}\+\\frac\{t\-b\}\{t\-s\}M\_\{1\},so the difference equals\(b−s\)​D/\(t−s\)\(b\-s\)D/\(t\-s\)\. The caset=bt=bis immediate\. All three coefficients are positive\. ∎

Fort<bt<b,abs,e​\(t\)2a\_\{b\}^\{s,e\}\(t\)^\{2\}is a positive constant times\(t−s\)/\(e−t\)\(t\-s\)/\(e\-t\)and is strictly increasing intt\. Fort\>bt\>b, it is a positive constant times\(e−t\)/\(t−s\)\(e\-t\)/\(t\-s\)and is strictly decreasing\. Thus the population score has a unique maximizer atbbwheneverD≠0D\\neq 0\.

###### Lemma B\.1\(Exact squared margin\)\.

For everys<t<es<t<e, the margin in \([7](https://arxiv.org/html/2608.13922#S3.E7)\) holds\.

###### Proof\.

Fort<bt<b,

\(abs,e​\(b\)\)2−\(abs,e​\(t\)\)2\\displaystyle\(a\_\{b\}^\{s,e\}\(b\)\)^\{2\}\-\(a\_\{b\}^\{s,e\}\(t\)\)^\{2\}=\(b−s\)​\(e−b\)e−s−\(e−b\)2​\(t−s\)\(e−s\)​\(e−t\)\\displaystyle=\\frac\{\(b\-s\)\(e\-b\)\}\{e\-s\}\-\\frac\{\(e\-b\)^\{2\}\(t\-s\)\}\{\(e\-s\)\(e\-t\)\}=\(e−b\)​\(b−t\)e−t\.\\displaystyle=\\frac\{\(e\-b\)\(b\-t\)\}\{e\-t\}\.Fort\>bt\>b, the symmetric calculation gives\(\(b−s\)​\(t−b\)\)/\(t−s\)\(\(b\-s\)\(t\-b\)\)/\(t\-s\)\. Multiplication by‖D‖F2\\\|D\\\|\_\{F\}^\{2\}proves the claim\. ∎

Two useful consequences are worth recording\. Ifb−s,e−b≥α⁡\(e−s\)b\-s,e\-b\\geq\\alpha\(e\-s\)and the candidate set is also restricted to the same interior region, then

‖ΔCUs,e​\(b\)‖F2−‖ΔCUs,e​\(t\)‖F2≥α​\|t−b\|​κ2\.\\left\\lVert\\Delta\_\{\\mathrm\{CU\}\}^\{s,e\}\(b\)\\right\\rVert\_\{\\mathrm\{F\}\}^\{2\}\-\\left\\lVert\\Delta\_\{\\mathrm\{CU\}\}^\{s,e\}\(t\)\\right\\rVert\_\{\\mathrm\{F\}\}^\{2\}\\geq\\alpha\|t\-b\|\\kappa^\{2\}\.\(16\)Also,

‖ΔCUs,e​\(b\)‖F=\(b−s\)​\(e−b\)e−s​κ≤e−s2​κ\.\\left\\lVert\\Delta\_\{\\mathrm\{CU\}\}^\{s,e\}\(b\)\\right\\rVert\_\{\\mathrm\{F\}\}=\\sqrt\{\\frac\{\(b\-s\)\(e\-b\)\}\{e\-s\}\}\\,\\kappa\\leq\\frac\{\\sqrt\{e\-s\}\}\{2\}\\kappa\.\(17\)

## Appendix CLow\-rank perturbation and approximate rank

###### Proof of[Proposition3\.1](https://arxiv.org/html/2608.13922#S3.Thmtheorem1)\.

LetB=A^\(r\)B=\\widehat\{A\}\_\{\(r\)\}and letAr=A\(r\)A\_\{r\}=A\_\{\(r\)\}\. SinceBBis a best rank\-rrapproximation toA^=A\+E\\widehat\{A\}=A\+Ein Frobenius norm,

‖A\+E−B‖F2≤‖A\+E−Ar‖F2\.\\\|A\+E\-B\\\|\_\{F\}^\{2\}\\leq\\\|A\+E\-A\_\{r\}\\\|\_\{F\}^\{2\}\.After cancellation,

‖A−B‖F2≤‖A−Ar‖F2\+2​⟨E,B−Ar⟩\.\\\|A\-B\\\|\_\{F\}^\{2\}\\leq\\\|A\-A\_\{r\}\\\|\_\{F\}^\{2\}\+2\\langle E,B\-A\_\{r\}\\rangle\.\(18\)The matrixB−ArB\-A\_\{r\}has rank at most2​r2r, hence

\|⟨E,B−Ar⟩\|\\displaystyle\|\\langle E,B\-A\_\{r\}\\rangle\|≤‖E‖op​‖B−Ar‖∗≤2​r​‖E‖op​‖B−Ar‖F\\displaystyle\\leq\\\|E\\\|\_\{\\mathrm\{op\}\}\\\|B\-A\_\{r\}\\\|\_\{\*\}\\leq\\sqrt\{2r\}\\\|E\\\|\_\{\\mathrm\{op\}\}\\\|B\-A\_\{r\}\\\|\_\{F\}≤2​r​‖E‖op​\(‖B−A‖F\+‖A−Ar‖F\)\.\\displaystyle\\leq\\sqrt\{2r\}\\\|E\\\|\_\{\\mathrm\{op\}\}\\bigl\(\\\|B\-A\\\|\_\{F\}\+\\\|A\-A\_\{r\}\\\|\_\{F\}\\bigr\)\.Setx=‖B−A‖Fx=\\\|B\-A\\\|\_\{F\},a=‖A−Ar‖Fa=\\\|A\-A\_\{r\}\\\|\_\{F\}, andu=2​r​‖E‖opu=\\sqrt\{2r\}\\\|E\\\|\_\{\\mathrm\{op\}\}\. Equation \([18](https://arxiv.org/html/2608.13922#A3.E18)\) givesx2≤a2\+2​u​\(x\+a\)x^\{2\}\\leq a^\{2\}\+2u\(x\+a\), equivalently\(x−u\)2≤\(a\+u\)2\(x\-u\)^\{2\}\\leq\(a\+u\)^\{2\}\. Thusx≤a\+2​ux\\leq a\+2u, proving

‖A^\(r\)−A‖F≤‖A−A\(r\)‖F\+2​2​r​‖E‖op\.\\\|\\widehat\{A\}\_\{\(r\)\}\-A\\\|\_\{F\}\\leq\\\|A\-A\_\{\(r\)\}\\\|\_\{F\}\+2\\sqrt\{2r\}\\\|E\\\|\_\{\\mathrm\{op\}\}\.ForA=abs,e​\(t\)​DA=a\_\{b\}^\{s,e\}\(t\)Dwithrank⁡\(D\)≤r\\operatorname\{rank\}\(D\)\\leq r, the approximation term vanishes\. Since2​2≤2\+22\\sqrt\{2\}\\leq 2\+\\sqrt\{2\}, the displayed one\-change bound in the main text follows\. ∎

### C\.1Approximately low\-rank jumps

Define the rank\-rrtail

ρr​\(D\)=‖D−D\(r\)‖F\.\\rho\_\{r\}\(D\)=\\\|D\-D\_\{\(r\)\}\\\|\_\{F\}\.Becauseabs,e​\(t\)\>0a\_\{b\}^\{s,e\}\(t\)\>0,\(abs,e​\(t\)​D\)\(r\)=abs,e​\(t\)​D\(r\)\(a\_\{b\}^\{s,e\}\(t\)D\)\_\{\(r\)\}=a\_\{b\}^\{s,e\}\(t\)D\_\{\(r\)\}\. Therefore the preceding proof gives

‖\(Δ^CUs,e​\(t\)\)\(r\)−abs,e​\(t\)​D‖F≤abs,e​\(t\)​ρr​\(D\)\+2​2​r​‖ECUs,e​\(t\)‖op\.\\left\\\|\\bigl\(\\widehat\{\\Delta\}\_\{\\mathrm\{CU\}\}^\{s,e\}\(t\)\\bigr\)\_\{\(r\)\}\-a\_\{b\}^\{s,e\}\(t\)D\\right\\\|\_\{F\}\\leq a\_\{b\}^\{s,e\}\(t\)\\rho\_\{r\}\(D\)\+2\\sqrt\{2r\}\\\|E\_\{\\mathrm\{CU\}\}^\{s,e\}\(t\)\\\|\_\{\\mathrm\{op\}\}\.\(19\)In particular,

\|W^rs,e​\(t\)−abs,e​\(t\)​κ\|≤abs,e​\(t\)​ρr​\(D\)\+2​2​r​‖ECUs,e​\(t\)‖op\.\\left\|\\widehat\{W\}\_\{r\}^\{s,e\}\(t\)\-a\_\{b\}^\{s,e\}\(t\)\\kappa\\right\|\\leq a\_\{b\}^\{s,e\}\(t\)\\rho\_\{r\}\(D\)\+2\\sqrt\{2r\}\\\|E\_\{\\mathrm\{CU\}\}^\{s,e\}\(t\)\\\|\_\{\\mathrm\{op\}\}\.\(20\)Thus approximate rank contributes a deterministic, location\-dependent bias rather than changing the stochastic analysis\. On a no\-change interval, the sharper identity

‖E\(r\)‖F≤r​‖E‖op\\\|E\_\{\(r\)\}\\\|\_\{F\}\\leq\\sqrt\{r\}\\\|E\\\|\_\{\\mathrm\{op\}\}\(21\)holds because the retainedrrsingular values are each bounded by‖E‖op\\\|E\\\|\_\{\\mathrm\{op\}\}\.

## Appendix DUniform operator\-norm control

LetYi=H2​\(Xi\)−𝔼​H2​\(Xi\)Y\_\{i\}=H\_\{2\}\(X\_\{i\}\)\-\\mathbb\{E\}H\_\{2\}\(X\_\{i\}\)\. For a fixed triple\(s,t,e\)\(s,t,e\), writenL=t−sn\_\{L\}=t\-s,nR=e−tn\_\{R\}=e\-t, andN=e−sN=e\-s\. Then

ECUs,e​\(t\)=∑i=s\+1ewis,e​\(t\)​Yi,E\_\{\\mathrm\{CU\}\}^\{s,e\}\(t\)=\\sum\_\{i=s\+1\}^\{e\}w\_\{i\}^\{s,e\}\(t\)Y\_\{i\},\(22\)where

wis,e​\(t\)=\{−nRN​nL,s<i≤t,nLN​nR,t<i≤e\.w\_\{i\}^\{s,e\}\(t\)=\\begin\{cases\}\-\\sqrt\{\\dfrac\{n\_\{R\}\}\{Nn\_\{L\}\}\},&s<i\\leq t,\\\\\[5\.16663pt\] \\phantom\{\-\}\\sqrt\{\\dfrac\{n\_\{L\}\}\{Nn\_\{R\}\}\},&t<i\\leq e\.\\end\{cases\}\(23\)Direct calculation gives

∑i=s\+1ewi2=1,wmax:=maxi⁡\|wi\|=nmaxN​nmin\.\\sum\_\{i=s\+1\}^\{e\}w\_\{i\}^\{2\}=1,\\qquad w\_\{\\max\}:=\\max\_\{i\}\|w\_\{i\}\|=\\sqrt\{\\frac\{n\_\{\\max\}\}\{Nn\_\{\\min\}\}\}\.\(24\)
###### Proposition D\.1\(Pointwise matrix Bernstein bound\)\.

Suppose the observations are independent and every segment density is bounded byLL\. Letp=d\+1p=d\+1andu\>0u\>0\. For a fixed triple\(s,t,e\)\(s,t,e\),

ℙ\{∥ECUs,e\(t\)∥op\>2​L​\(1\+d/2\)​u\+4dwmaxu\}≤2pe−u\.\\mathbb\{P\}\\left\\\{\\\|E\_\{\\mathrm\{CU\}\}^\{s,e\}\(t\)\\\|\_\{\\mathrm\{op\}\}\>\\sqrt\{2L\(1\+d/2\)u\}\+4dw\_\{\\max\}u\\right\\\}\\leq 2pe^\{\-u\}\.\(25\)

###### Proof\.

For an observation in segmentkk,

𝔼​Yi2=𝔼​H2​\(Xi\)2−Mk2⪯𝔼​H2​\(Xi\)2⪯L⁡\(1\+d/2\)​I\\mathbb\{E\}Y\_\{i\}^\{2\}=\\mathbb\{E\}H\_\{2\}\(X\_\{i\}\)^\{2\}\-M\_\{k\}^\{2\}\\preceq\\mathbb\{E\}H\_\{2\}\(X\_\{i\}\)^\{2\}\\preceq L\(1\+d/2\)Iby \([15](https://arxiv.org/html/2608.13922#A1.E15)\)\. Therefore the matrix variance parameter of the weighted sum is at most

v=‖∑iwi2​𝔼​Yi2‖op≤L⁡\(1\+d/2\)​∑iwi2=L⁡\(1\+d/2\)\.v=\\left\\\|\\sum\_\{i\}w\_\{i\}^\{2\}\\mathbb\{E\}Y\_\{i\}^\{2\}\\right\\\|\_\{\\mathrm\{op\}\}\\leq L\(1\+d/2\)\\sum\_\{i\}w\_\{i\}^\{2\}=L\(1\+d/2\)\.By[LemmaA\.1](https://arxiv.org/html/2608.13922#A1.Thmtheorem1), each summand satisfies‖wi​Yi‖op≤6​d​wmax=:R\\\|w\_\{i\}Y\_\{i\}\\\|\_\{\\mathrm\{op\}\}\\leq 6dw\_\{\\max\}=:R\. The self\-adjoint matrix Bernstein inequality\([14](https://arxiv.org/html/2608.13922#bib.bib14)\)yields

ℙ\{‖∑iwiYi‖op\>2​v​u\+23Ru\}≤2pe−u\.\\mathbb\{P\}\\left\\\{\\left\\\|\\sum\_\{i\}w\_\{i\}Y\_\{i\}\\right\\\|\_\{\\mathrm\{op\}\}\>\\sqrt\{2vu\}\+\\frac\{2\}\{3\}Ru\\right\\\}\\leq 2pe^\{\-u\}\.SubstitutingvvandRRproves \([25](https://arxiv.org/html/2608.13922#A4.E25)\)\. ∎

###### Proof of[Theorem5\.1](https://arxiv.org/html/2608.13922#S5.Thmtheorem1)\.

For every candidate in the central half of an interval,nL,nR≥N/4n\_\{L\},n\_\{R\}\\geq N/4andnmax≤3​N/4n\_\{\\max\}\\leq 3N/4\. Hence

wmax≤3N≤2N\.w\_\{\\max\}\\leq\\sqrt\{\\frac\{3\}\{N\}\}\\leq\\frac\{2\}\{\\sqrt\{N\}\}\.All scanned intervals haveN≥mN\\geq m, so[PropositionD\.1](https://arxiv.org/html/2608.13922#A4.Thmtheorem1)withu=ℓ𝒢,δ=log⁡\(2​\(d\+1\)​\|𝒢\|/δ\)u=\\ell\_\{\\mathcal\{G\},\\delta\}=\\log\(2\(d\+1\)\|\\mathcal\{G\}\|/\\delta\)gives, for a fixed candidate,

‖ECUs,e​\(t\)‖op≤2​L​\(1\+d/2\)​ℓ𝒢,δ\+8​d​ℓ𝒢,δm\.\\\|E\_\{\\mathrm\{CU\}\}^\{s,e\}\(t\)\\\|\_\{\\mathrm\{op\}\}\\leq\\sqrt\{2L\(1\+d/2\)\\ell\_\{\\mathcal\{G\},\\delta\}\}\+\\frac\{8d\\ell\_\{\\mathcal\{G\},\\delta\}\}\{\\sqrt\{m\}\}\.A union bound over𝒢\\mathcal\{G\}proves the first statement\. On a one\-change interval, combine this event with[Proposition3\.1](https://arxiv.org/html/2608.13922#S3.Thmtheorem1)and the reverse triangle inequality\. This gives the score deviationεr=cr​r​λm​\(δ\)\\varepsilon\_\{r\}=c\_\{r\}\\sqrt\{r\}\\lambda\_\{m\}\(\\delta\)\. On a no\-change interval, \([21](https://arxiv.org/html/2608.13922#A3.E21)\) gives the sharper score boundr​λm​\(δ\)\\sqrt\{r\}\\lambda\_\{m\}\(\\delta\)\. ∎

The cardinality used above is modest\. There areO⁡\(n/h\)O\(n/h\)intervals of lengthhhand at mosthhcandidate splits per interval, henceO⁡\(n\)O\(n\)triples per scale\. Summing overO⁡\(log⁡\(n/m\)\)O\(\\log\(n/m\)\)dyadic scales gives

\|𝒢\|=O⁡\(n​log⁡\(n/m\)\)\.\|\\mathcal\{G\}\|=O\\bigl\(n\\log\(n/m\)\\bigr\)\.\(26\)

## Appendix ESeeded geometry and the multiple\-change induction

For a fully discrete construction, takemmto be a positive multiple of four and use dyadic lengthshj=2j​mh\_\{j\}=2^\{j\}mnot exceedingnn\. At lengthhh, include all intervals

Ih,q=\(qh2,qh2\+h\]whose endpoints lie in\[0,n\]\.I\_\{h,q\}=\\left\(q\\frac\{h\}\{2\},\\ q\\frac\{h\}\{2\}\+h\\right\]\\quad\\text\{whose endpoints lie in \}\[0,n\]\.\(27\)If a user\-specifiedmmis not a multiple of four, it can be rounded to an adjacent admissible integer; changing all constants by at most an additive two handles the finitely many boundary lattice points\. We state the exact geometric argument for \([27](https://arxiv.org/html/2608.13922#A5.E27)\)\.

###### Lemma E\.1\(Balanced seeded interval\)\.

Let\(a,c\]\(a,c\]be an active component and letb∈\(a,c\)b\\in\(a,c\)satisfymin⁡\(b−a,c−b\)≥h\\min\(b\-a,c\-b\)\\geq h\. Then there is an intervalI=\(s,e\]I=\(s,e\]of the form \([27](https://arxiv.org/html/2608.13922#A5.E27)\), contained in\(a,c\]\(a,c\], such that

e−s=h,b−s≥h/4,e−b≥h/4\.e\-s=h,\\qquad b\-s\\geq h/4,\\qquad e\-b\\geq h/4\.

###### Proof\.

The central halves

\[q​h/2\+h/4,q​h/2\+3​h/4\],q∈ℤ,\\left\[qh/2\+h/4,\\ qh/2\+3h/4\\right\],\\qquad q\\in\\mathbb\{Z\},tile the real line: the right endpoint of one is the left endpoint of the next\. Chooseqqwhose central half containsbb\. Thenbbis at leasth/4h/4from each endpoint ofIh,qI\_\{h,q\}and at most3​h/43h/4from each endpoint\. Sincebbis at leasthhfromaaandcc, the interval is contained in\(a,c\]\(a,c\]\. ∎

###### Lemma E\.2\(An undetected change generates an active isolating interval\)\.

Assume the uniform event of[Theorem5\.1](https://arxiv.org/html/2608.13922#S5.Thmtheorem1)\. Suppose an undetected changeηk\\eta\_\{k\}lies in an active component and is at least3​Δ/43\\Delta/4from both component boundaries\. Ifm≤Δ/8m\\leq\\Delta/8, then there is a seeded intervalIIcontained in that component with

Δ8≤\|I\|<Δ4,\\frac\{\\Delta\}\{8\}\\leq\|I\|<\\frac\{\\Delta\}\{4\},which contains onlyηk\\eta\_\{k\}, places it in the central half, and satisfies

S^I≥Δ8​2​κ−εr\.\\widehat\{S\}\_\{I\}\\geq\\frac\{\\sqrt\{\\Delta\}\}\{8\\sqrt\{2\}\}\\kappa\-\\varepsilon\_\{r\}\.

###### Proof\.

Lethhbe the first dyadic length2j​m2^\{j\}mthat is at leastΔ/8\\Delta/8\. Thenh<Δ/4h<\\Delta/4\(with equality allowed only in an immaterial endpoint case\)\. Since3​Δ/4≥h3\\Delta/4\\geq h,[LemmaE\.1](https://arxiv.org/html/2608.13922#A5.Thmtheorem1)provides a contained interval with left and right lengths at leasth/4h/4\. Its length is less than the minimal spacing, so it contains no other change\. At the true split,

aηks,e​\(ηk\)=\(ηk−s\)​\(e−ηk\)h≥h4≥Δ8​2\.a\_\{\\eta\_\{k\}\}^\{s,e\}\(\\eta\_\{k\}\)=\\sqrt\{\\frac\{\(\\eta\_\{k\}\-s\)\(e\-\\eta\_\{k\}\)\}\{h\}\}\\geq\\frac\{\\sqrt\{h\}\}\{4\}\\geq\\frac\{\\sqrt\{\\Delta\}\}\{8\\sqrt\{2\}\}\.The one\-change score deviation in[Theorem5\.1](https://arxiv.org/html/2608.13922#S5.Thmtheorem1)completes the proof\. ∎

###### Proof of[Theorem5\.2](https://arxiv.org/html/2608.13922#S5.Thmtheorem2)\.

We prove the following invariant by induction over the number of selected intervals\.

*Invariant\.*The active components are disjoint and contain exactly the undetected change points\. Every undetected change is at least3​Δ/43\\Delta/4from the two boundaries of its active component\.

At initialization, consecutive true change points and the global endpoints are separated by at leastΔ\\Delta, so the invariant holds\. Assume it holds before an iteration\.

First, an interval contained in an active component but containing no undetected change has zero population CUSUM\. By \([21](https://arxiv.org/html/2608.13922#A3.E21)\) and the uniform event, its score is at mostr​λm​\(δ\)<τ\\sqrt\{r\}\\lambda\_\{m\}\(\\delta\)<\\tau; it cannot be active\.

Second, every undetected change has an active isolating interval of length belowΔ/4\\Delta/4by[LemmaE\.2](https://arxiv.org/html/2608.13922#A5.Thmtheorem2)and the upper threshold inequality in \([9](https://arxiv.org/html/2608.13922#S5.E9)\)\. Hence the algorithm cannot stop while an undetected change remains\.

Third, letI∗=\(s∗,e∗\]I^\{\*\}=\(s^\{\*\},e^\{\*\}\]be a shortest active interval\. It is no longer than one of the isolating intervals, so\|I∗\|<Δ/4\|I^\{\*\}\|<\\Delta/4\. The first step shows that it contains an undetected change, and minimal spacing shows that it contains exactly one, sayηj\\eta\_\{j\}\. DeletingI∗I^\{\*\}therefore removes exactly this change\.

It remains to verify the invariant for the two new components\. Consider the nearest remaining change on the left, if it exists\. Sinces∗<ηjs^\{\*\}<\\eta\_\{j\}andηj−s∗<\|I∗\|<Δ/4\\eta\_\{j\}\-s^\{\*\}<\|I^\{\*\}\|<\\Delta/4,

s∗−ηj−1=\(ηj−ηj−1\)−\(ηj−s∗\)\>Δ−Δ4=3​Δ4\.s^\{\*\}\-\\eta\_\{j\-1\}=\(\\eta\_\{j\}\-\\eta\_\{j\-1\}\)\-\(\\eta\_\{j\}\-s^\{\*\}\)\>\\Delta\-\\frac\{\\Delta\}\{4\}=\\frac\{3\\Delta\}\{4\}\.The right side is identical\. All other component boundaries are unchanged\. Thus the invariant is preserved\.

Each iteration removes exactly one change, and the algorithm cannot terminate early\. It therefore performs exactlyKKiterations\. Every selected interval has length belowΔ/4\\Delta/4and contains its matched change, so its recorded maximizer, which also lies in the interval, obeys\|b^k−ηk\|≤Δ/4\|\\widehat\{b\}\_\{k\}\-\\eta\_\{k\}\|\\leq\\Delta/4\. ∎

The threshold interval is nonempty under the explicit signal condition

Δ8​2​κ\>\(cr\+1\)​r​λm​\(δ\)\.\\frac\{\\sqrt\{\\Delta\}\}\{8\\sqrt\{2\}\}\\kappa\>\(c\_\{r\}\+1\)\\sqrt\{r\}\\lambda\_\{m\}\(\\delta\)\.\(28\)Ignoring constants and the bounded\-summand correction, this isΔ​κ2≳r​L​d​log⁡\(n​d/δ\)\\Delta\\kappa^\{2\}\\gtrsim rLd\\log\(nd/\\delta\)\.

## Appendix FPreliminary localization from the exact margin

###### Proof of[Corollary5\.3](https://arxiv.org/html/2608.13922#S5.Thmtheorem3)\.

WriteW⁡\(t\)=‖ΔCUs,e​\(t\)‖FW\(t\)=\\\|\\Delta\_\{\\mathrm\{CU\}\}^\{s,e\}\(t\)\\\|\_\{F\}andW^​\(t\)=W^rs,e​\(t\)\\widehat\{W\}\(t\)=\\widehat\{W\}\_\{r\}^\{s,e\}\(t\)\. On the uniform event,supt\|W^​\(t\)−W⁡\(t\)\|≤εr\\sup\_\{t\}\|\\widehat\{W\}\(t\)\-W\(t\)\|\\leq\\varepsilon\_\{r\}\. Sinceb^\\widehat\{b\}maximizesW^\\widehat\{W\},

W⁡\(b\)−W⁡\(b^\)≤2​εr\.W\(b\)\-W\(\\widehat\{b\}\)\\leq 2\\varepsilon\_\{r\}\.\(29\)The interior exact margin \([16](https://arxiv.org/html/2608.13922#A2.E16)\) and the fact thatW⁡\(b^\)≤W⁡\(b\)W\(\\widehat\{b\}\)\\leq W\(b\)imply

W⁡\(b\)−W⁡\(b^\)\\displaystyle W\(b\)\-W\(\\widehat\{b\}\)=W​\(b\)2−W​\(b^\)2W⁡\(b\)\+W⁡\(b^\)\\displaystyle=\\frac\{W\(b\)^\{2\}\-W\(\\widehat\{b\}\)^\{2\}\}\{W\(b\)\+W\(\\widehat\{b\}\)\}≥α​\|b^−b\|​κ22​W​\(b\)\.\\displaystyle\\geq\\frac\{\\alpha\|\\widehat\{b\}\-b\|\\kappa^\{2\}\}\{2W\(b\)\}\.Combining this inequality with \([29](https://arxiv.org/html/2608.13922#A6.E29)\) and the peak bound \([17](https://arxiv.org/html/2608.13922#A2.E17)\) yields

\|b^−b\|≤4​εr​W​\(b\)α​κ2≤2​εr​Nα​κ=2​crα​N​r​λm​\(δ\)κ\.\|\\widehat\{b\}\-b\|\\leq\\frac\{4\\varepsilon\_\{r\}W\(b\)\}\{\\alpha\\kappa^\{2\}\}\\leq\\frac\{2\\varepsilon\_\{r\}\\sqrt\{N\}\}\{\\alpha\\kappa\}=\\frac\{2c\_\{r\}\}\{\\alpha\}\\frac\{\\sqrt\{Nr\}\\lambda\_\{m\}\(\\delta\)\}\{\\kappa\}\.∎

This calculation explains why a global CUSUM maximizer is an effective isolator but not automatically rate\-optimal: the uniform error is compared with a score margin rather than with a local likelihood increment\. The refinement below performs the latter comparison after learning a one\-dimensional changing direction\.

## Appendix GCross\-fitted refinement

We make the scalar condition used in the main theorem explicit\. Conditional on any deterministic matrixVVwith‖V‖F=1\\\|V\\\|\_\{F\}=1, let

ξi​\(V\)=⟨H2​\(Xi\)−Mk,V⟩F\\xi\_\{i\}\(V\)=\\langle H\_\{2\}\(X\_\{i\}\)\-M\_\{k\},V\\rangle\_\{F\}on a pure segmentkk\. Assume the Bernstein moment\-generating\-function bound

log⁡𝔼​exp⁡\{λ​ξi​\(V\)\}≤λ2​ν22​\(1−B​\|λ\|\),\|λ\|<B−1\.\\log\\mathbb\{E\}\\exp\\\{\\lambda\\xi\_\{i\}\(V\)\\\}\\leq\\frac\{\\lambda^\{2\}\\nu^\{2\}\}\{2\(1\-B\|\\lambda\|\)\},\\qquad\|\\lambda\|<B^\{\-1\}\.\(30\)It implies \([11](https://arxiv.org/html/2608.13922#S5.E11)\) and its maximal, line\-crossing form\. Independent bounded projections satisfy \([30](https://arxiv.org/html/2608.13922#A7.E30)\) with conservative parameters depending on the envelope; sharper distributional assumptions can yield smallerν\\nuandBB\.

### G\.1Pilot direction alignment

###### Lemma G\.1\(Normalization preserves the jump direction\)\.

LetA=a​DA=aDwitha\>0a\>0,‖D‖F=κ\\\|D\\\|\_\{F\}=\\kappa, and suppose‖A^r−A‖F≤ϵ\\\|\\widehat\{A\}\_\{r\}\-A\\\|\_\{F\}\\leq\\epsilonanda​κ≥3​ϵa\\kappa\\geq 3\\epsilon\. Then, forV=A^r/‖A^r‖FV=\\widehat\{A\}\_\{r\}/\\\|\\widehat\{A\}\_\{r\}\\\|\_\{F\},

⟨D,V⟩F≥κ2\.\\langle D,V\\rangle\_\{F\}\\geq\\frac\{\\kappa\}\{2\}\.

###### Proof\.

By Cauchy–Schwarz and the triangle inequality,

⟨D,V⟩F\\displaystyle\\langle D,V\\rangle\_\{F\}=a​κ2\+⟨D,A^r−A⟩F‖A^r‖F\\displaystyle=\\frac\{a\\kappa^\{2\}\+\\langle D,\\widehat\{A\}\_\{r\}\-A\\rangle\_\{F\}\}\{\\\|\\widehat\{A\}\_\{r\}\\\|\_\{F\}\}≥κ​a​κ−ϵa​κ\+ϵ≥κ2\.\\displaystyle\\geq\\kappa\\frac\{a\\kappa\-\\epsilon\}\{a\\kappa\+\\epsilon\}\\geq\\frac\{\\kappa\}\{2\}\.∎

LetS=maxt⁡‖ΔCU​\(t\)‖FS=\\max\_\{t\}\\\|\\Delta\_\{\\mathrm\{CU\}\}\(t\)\\\|\_\{F\}be the pilot population peak and lett^\\widehat\{t\}maximize the pilot empirical score\. Uniform score errorϵ\\epsilongives

‖ΔCU​\(t^\)‖F≥W^​\(t^\)−ϵ≥W^​\(b\)−ϵ≥S−2​ϵ\.\\\|\\Delta\_\{\\mathrm\{CU\}\}\(\\widehat\{t\}\)\\\|\_\{F\}\\geq\\widehat\{W\}\(\\widehat\{t\}\)\-\\epsilon\\geq\\widehat\{W\}\(b\)\-\\epsilon\\geq S\-2\\epsilon\.IfS≥8​ϵS\\geq 8\\epsilon, then the population signal att^\\widehat\{t\}is at least6​ϵ6\\epsilon, and[LemmaG\.1](https://arxiv.org/html/2608.13922#A7.Thmtheorem1)applies\. This proves the final assertion of[Theorem5\.4](https://arxiv.org/html/2608.13922#S5.Thmtheorem4)withϵ=εr\\epsilon=\\varepsilon\_\{r\}\.

### G\.2Anchor means and least\-squares drift

Condition on the pilot fold and hence on a directionVVsatisfyingδV:=⟨D,V⟩F≥κ/2\\delta\_\{V\}:=\\langle D,V\\rangle\_\{F\}\\geq\\kappa/2\. The held\-out scalar sequence has meansμ0=⟨M0,V⟩F\\mu\_\{0\}=\\langle M\_\{0\},V\\rangle\_\{F\}andμ1=⟨M1,V⟩F\\mu\_\{1\}=\\langle M\_\{1\},V\\rangle\_\{F\}, withμ1−μ0=δV\\mu\_\{1\}\-\\mu\_\{0\}=\\delta\_\{V\}\. Let the two pure anchor estimates be

μ^L=μ0\+uL,μ^R=μ1\+uR,δ^=μ^R−μ^L\.\\widehat\{\\mu\}\_\{L\}=\\mu\_\{0\}\+u\_\{L\},\\qquad\\widehat\{\\mu\}\_\{R\}=\\mu\_\{1\}\+u\_\{R\},\\qquad\\widehat\{\\delta\}=\\widehat\{\\mu\}\_\{R\}\-\\widehat\{\\mu\}\_\{L\}\.By \([30](https://arxiv.org/html/2608.13922#A7.E30)\), for an absolutec\>0c\>0,

ℙ\{\|uL\|\>δV/8\}∨ℙ\{\|uR\|\>δV/8\}≤2exp\[−cqmin\{δV2ν2,δVB\}\]\.\\mathbb\{P\}\\\{\|u\_\{L\}\|\>\\delta\_\{V\}/8\\\}\\vee\\mathbb\{P\}\\\{\|u\_\{R\}\|\>\\delta\_\{V\}/8\\\}\\leq 2\\exp\\left\[\-cq\\min\\left\\\{\\frac\{\\delta\_\{V\}^\{2\}\}\{\\nu^\{2\}\},\\frac\{\\delta\_\{V\}\}\{B\}\\right\\\}\\right\]\.\(31\)On the event

𝒜=\{\|uL\|∨\|uR\|≤δV/8\},\\mathcal\{A\}=\\\{\|u\_\{L\}\|\\vee\|u\_\{R\}\|\\leq\\delta\_\{V\}/8\\\},\(32\)we have3​δV/4≤δ^≤5​δV/43\\delta\_\{V\}/4\\leq\\widehat\{\\delta\}\\leq 5\\delta\_\{V\}/4\.

Letη\\etabe the held\-out\-fold change location\. Ift=η\+m\>ηt=\\eta\+m\>\\eta, only themmpost\-change observations betweenη\+1\\eta\+1andttswitch from the right loss to the left loss\. WritingZi=μ1\+ξiZ\_\{i\}=\\mu\_\{1\}\+\\xi\_\{i\}there,

Q⁡\(η\+m\)−Q⁡\(η\)\\displaystyle Q\(\\eta\+m\)\-Q\(\\eta\)=∑i=η\+1η\+m\{\(Zi−μ^L\)2−\(Zi−μ^R\)2\}\\displaystyle=\\sum\_\{i=\\eta\+1\}^\{\\eta\+m\}\\\{\(Z\_\{i\}\-\\widehat\{\\mu\}\_\{L\}\)^\{2\}\-\(Z\_\{i\}\-\\widehat\{\\mu\}\_\{R\}\)^\{2\}\\\}=m​δ^​\(δV−uL−uR\)\+2​δ^​∑i=η\+1η\+mξi\.\\displaystyle=m\\widehat\{\\delta\}\(\\delta\_\{V\}\-u\_\{L\}\-u\_\{R\}\)\+2\\widehat\{\\delta\}\\sum\_\{i=\\eta\+1\}^\{\\eta\+m\}\\xi\_\{i\}\.\(33\)Similarly, fort=η−m<ηt=\\eta\-m<\\etaand pre\-change centered errors,

Q⁡\(η−m\)−Q⁡\(η\)=m​δ^​\(δV\+uL\+uR\)−2​δ^​∑i=η−m\+1ηξi\.Q\(\\eta\-m\)\-Q\(\\eta\)=m\\widehat\{\\delta\}\(\\delta\_\{V\}\+u\_\{L\}\+u\_\{R\}\)\-2\\widehat\{\\delta\}\\sum\_\{i=\\eta\-m\+1\}^\{\\eta\}\\xi\_\{i\}\.\(34\)On𝒜\\mathcal\{A\}, both deterministic drifts are at least9​m​δV2/169m\\delta\_\{V\}^\{2\}/16\. Thus a candidate at distancemmcan beat the true split only if a centered partial sum crosses a line of slope at least3​δV/83\\delta\_\{V\}/8\.

### G\.3A maximal Bernstein line\-crossing bound

###### Lemma G\.2\(Positive\-drift localization bound\)\.

Under \([30](https://arxiv.org/html/2608.13922#A7.E30)\), there are absolute constantsc,C\>0c,C\>0such that, for everyh≥1h\\geq 1,

ℙ⁡\{∃m≥h:\|∑i=1mξi\|≥c​m​δV\}≤2​exp⁡\[−hC⁡\(ν2/δV2\+B/δV\)\]\.\\mathbb\{P\}\\left\\\{\\exists m\\geq h:\\left\|\\sum\_\{i=1\}^\{m\}\\xi\_\{i\}\\right\|\\geq cm\\delta\_\{V\}\\right\\\}\\leq 2\\exp\\left\[\-\\frac\{h\}\{C\(\\nu^\{2\}/\\delta\_\{V\}^\{2\}\+B/\\delta\_\{V\}\)\}\\right\]\.\(35\)

###### Proof\.

For the lower crossing, apply \([30](https://arxiv.org/html/2608.13922#A7.E30)\) to−ξi\-\\xi\_\{i\}\. Chooseλ=c0​min⁡\{δV/ν2,1/B\}\\lambda=c\_\{0\}\\min\\\{\\delta\_\{V\}/\\nu^\{2\},1/B\\\}for a sufficiently small numericalc0c\_\{0\}\. The exponential process

exp\{−λ∑i=1mξi−mψ\(−λ\)\},ψ\(−λ\)=log𝔼e−λ​ξi,\\exp\\left\\\{\-\\lambda\\sum\_\{i=1\}^\{m\}\\xi\_\{i\}\-m\\psi\(\-\\lambda\)\\right\\\},\\qquad\\psi\(\-\\lambda\)=\\log\\mathbb\{E\}e^\{\-\\lambda\\xi\_\{i\}\},is a nonnegative supermartingale\. The chosenλ\\lambdaensures

λ​c​δV−ψ⁡\(−λ\)≥c1​min⁡\{δV2ν2,δVB\}\.\\lambda c\\delta\_\{V\}\-\\psi\(\-\\lambda\)\\geq c\_\{1\}\\min\\left\\\{\\frac\{\\delta\_\{V\}^\{2\}\}\{\\nu^\{2\}\},\\frac\{\\delta\_\{V\}\}\{B\}\\right\\\}\.If−∑i=1mξi≥cmδV\-\\sum\_\{i=1\}^\{m\}\\xi\_\{i\}\\geq cm\\delta\_\{V\}for somem≥hm\\geq h, the supermartingale is at least the exponential ofhhtimes the last display\. Ville’s inequality bounds the crossing probability by that reciprocal\. Apply the same argument toξi\\xi\_\{i\}and use a union bound\. Finally,

\[min⁡\{δV2ν2,δVB\}\]−1=max⁡\{ν2δV2,BδV\}≤ν2δV2\+BδV\.\\left\[\\min\\left\\\{\\frac\{\\delta\_\{V\}^\{2\}\}\{\\nu^\{2\}\},\\frac\{\\delta\_\{V\}\}\{B\}\\right\\\}\\right\]^\{\-1\}=\\max\\left\\\{\\frac\{\\nu^\{2\}\}\{\\delta\_\{V\}^\{2\}\},\\frac\{B\}\{\\delta\_\{V\}\}\\right\\\}\\leq\\frac\{\\nu^\{2\}\}\{\\delta\_\{V\}^\{2\}\}\+\\frac\{B\}\{\\delta\_\{V\}\}\.∎

###### Proof of[Theorem5\.4](https://arxiv.org/html/2608.13922#S5.Thmtheorem4)\.

Conditional on all pilot directions, apply \([31](https://arxiv.org/html/2608.13922#A7.E31)\) to the2​K2Kanchor blocks\. The stated lower bound onqq, with a sufficiently large constant, makes the probability that any anchor event fails at mostδ/2\\delta/2becauseδV≥κ/2\\delta\_\{V\}\\geq\\kappa/2\.

On the joint anchor event, \([33](https://arxiv.org/html/2608.13922#A7.E33)\)–\([34](https://arxiv.org/html/2608.13922#A7.E34)\) and[LemmaG\.2](https://arxiv.org/html/2608.13922#A7.Thmtheorem2)imply, for eachkk,

ℙ\{\|η~k−ηk\|\>hk∣pilot,𝒜\}≤δ2​K\\mathbb\{P\}\\\{\|\\widetilde\{\\eta\}\_\{k\}\-\\eta\_\{k\}\|\>h\_\{k\}\\mid\\text\{pilot\},\\mathcal\{A\}\\\}\\leq\\frac\{\\delta\}\{2K\}when

hk=C⁡\(ν2δV,k2\+BδV,k\)​log⁡Kδ\.h\_\{k\}=C\\left\(\\frac\{\\nu^\{2\}\}\{\\delta\_\{V,k\}^\{2\}\}\+\\frac\{B\}\{\\delta\_\{V,k\}\}\\right\)\\log\\frac\{K\}\{\\delta\}\.A union bound andδV,k≥κk/2\\delta\_\{V,k\}\\geq\\kappa\_\{k\}/2yield \([12](https://arxiv.org/html/2608.13922#S5.E12)\), up to a change in the absolute constant\. Passing from a parity\-fold index to the original time scale multiplies the fold error by at most two and introduces at most one rounding unit; the factor two is absorbed intoCCand the additive unit is displayed explicitly\. ∎

## Appendix HMinimax localization lower bound

###### Proof of[Theorem5\.5](https://arxiv.org/html/2608.13922#S5.Thmtheorem5)\.

It is enough to construct a rank\-two subfamily\. Ford≥2d\\geq 2, let

fθ​\(x\)=1\+3​θ​x1​x2,\|θ\|≤16\.f\_\{\\theta\}\(x\)=1\+3\\theta x\_\{1\}x\_\{2\},\\qquad\|\\theta\|\\leq\\frac\{1\}\{6\}\.\(36\)This is a density relative toμ\\mubecause it integrates to one and is bounded below by1/21/2\. Its coordinate marginals are uniform\. Moreover,

𝔼fθ​\(X1​X2\)=3​θ​𝔼μ​X12​𝔼μ​X22=θ3\.\\mathbb\{E\}\_\{f\_\{\\theta\}\}\(X\_\{1\}X\_\{2\}\)=3\\theta\\mathbb\{E\}\_\{\\mu\}X\_\{1\}^\{2\}\\mathbb\{E\}\_\{\\mu\}X\_\{2\}^\{2\}=\\frac\{\\theta\}\{3\}\.Thus the only changing entries ofM⁡\(fθ\)−M⁡\(f0\)M\(f\_\{\\theta\}\)\-M\(f\_\{0\}\)are\(1,2\)\(1,2\)and\(2,1\)\(2,1\), each equal toθ/2\\theta/\\sqrt\{2\}\. The jump has rank two and Frobenius norm\|θ\|\|\\theta\|\.

For\|u\|≤1/2\|u\|\\leq 1/2,\(1\+u\)​log⁡\(1\+u\)≤u\+C​u2\(1\+u\)\\log\(1\+u\)\\leq u\+Cu^\{2\}\. Takingu=3​θ​X1​X2u=3\\theta X\_\{1\}X\_\{2\}and using𝔼μ​u=0\\mathbb\{E\}\_\{\\mu\}u=0gives

KL⁡\(fθ,f0\)=∫fθ​log⁡fθ​𝑑μ≤C​θ2\.\\operatorname\{KL\}\(f\_\{\\theta\},f\_\{0\}\)=\\int f\_\{\\theta\}\\log f\_\{\\theta\}\\,d\\mu\\leq C\\theta^\{2\}\.\(37\)Choose two sequence models with change locationsη0\\eta\_\{0\}andη1=η0\+h\\eta\_\{1\}=\\eta\_\{0\}\+h, usingf0f\_\{0\}before the change andfθf\_\{\\theta\}after it\. Their joint laws differ in onlyhhobservations, so

KL⁡\(P0,P1\)≤C​h​θ2\.\\operatorname\{KL\}\(P\_\{0\},P\_\{1\}\)\\leq Ch\\theta^\{2\}\.Takeh=⌊c1​θ−2⌋h=\\lfloor c\_\{1\}\\theta^\{\-2\}\\rfloorwithc1c\_\{1\}small enough that this KL divergence is at most1/81/8, and place both locations at leasthhfrom the endpoints\. Pinsker’s inequality givesTV⁡\(P0,P1\)≤1/4\\operatorname\{TV\}\(P\_\{0\},P\_\{1\}\)\\leq 1/4\. The two\-point Le Cam bound then yields, for every estimator,

maxj∈\{0,1\}⁡𝔼Pj​\|η^−ηj\|\\displaystyle\\max\_\{j\\in\\\{0,1\\\}\}\\mathbb\{E\}\_\{P\_\{j\}\}\|\\widehat\{\\eta\}\-\\eta\_\{j\}\|≥h2​infϕ\{P0​\(ϕ=1\)\+P1​\(ϕ=0\)\}\\displaystyle\\geq\\frac\{h\}\{2\}\\inf\_\{\\phi\}\\\{P\_\{0\}\(\\phi=1\)\+P\_\{1\}\(\\phi=0\)\\\}≥h2​\(1−TV⁡\(P0,P1\)\)≥c​h≥c′θ2\.\\displaystyle\\geq\\frac\{h\}\{2\}\(1\-\\operatorname\{TV\}\(P\_\{0\},P\_\{1\}\)\)\\geq ch\\geq\\frac\{c^\{\\prime\}\}\{\\theta^\{2\}\}\.Since the projected jump size isκ=\|θ\|\\kappa=\|\\theta\|, the asserted lower bound follows\. ∎

## Appendix IUniform geometricβ\\beta\-mixing extension

The population calculations use only linearity of expectation and are unchanged under temporal dependence\. Dependence changes only the control of the centered weighted sum\.

LetZi=H2​\(Xi\)−𝔼​H2​\(Xi\)Z\_\{i\}=H\_\{2\}\(X\_\{i\}\)\-\\mathbb\{E\}H\_\{2\}\(X\_\{i\}\)and suppose the triangular array is uniformly absolutely regular:

supnsup1≤j≤n−hβ\(σ\(Zi:i≤j\),σ\(Zi:i≥j\+h\)\)≤e−cβ​\(h−1\),h≥1,\\sup\_\{n\}\\sup\_\{1\\leq j\\leq n\-h\}\\beta\\bigl\(\\sigma\(Z\_\{i\}:i\\leq j\),\\sigma\(Z\_\{i\}:i\\geq j\+h\)\\bigr\)\\leq e^\{\-c\_\{\\beta\}\(h\-1\)\},\\qquad h\\geq 1,\(38\)with‖Zi‖op≤Bd\\\|Z\_\{i\}\\\|\_\{\\mathrm\{op\}\}\\leq B\_\{d\}almost surely\. For a fixed triple, putAj=ws\+js,e​\(t\)​Zs\+jA\_\{j\}=w\_\{s\+j\}^\{s,e\}\(t\)Z\_\{s\+j\},j=1,…,Nj=1,\\ldots,N\. Deterministic measurable transformations cannot increase absolute\-regularity coefficients, so the sequenceAjA\_\{j\}satisfies \([38](https://arxiv.org/html/2608.13922#A9.E38)\)\. Also

λmax​\(Aj\)≤Bd​wmax\.\\lambda\_\{\\max\}\(A\_\{j\}\)\\leq B\_\{d\}w\_\{\\max\}\.Define the dependent variance proxy

vs,e,t2=sup∅≠J⊆\{1,…,N\}1\|J\|​λmax​𝔼​\(∑j∈JAj\)2\.v\_\{s,e,t\}^\{2\}=\\sup\_\{\\varnothing\\neq J\\subseteq\\\{1,\\ldots,N\\\}\}\\frac\{1\}\{\|J\|\}\\lambda\_\{\\max\}\\mathbb\{E\}\\left\(\\sum\_\{j\\in J\}A\_\{j\}\\right\)^\{2\}\.\(39\)It retains the lagged cross\-moments that vanish under independence\.

A direct two\-sided consequence of Theorem 1 of[3](https://arxiv.org/html/2608.13922#bib.bib3)is that, for a universalC\>0C\>0,

ℙ\{∥ECUs,e\(t\)∥op≥x\}≤2\(d\+1\)exp\[−C​x2N​vs,e,t2\+cβ−1​Bd2​wmax2\+x​Bd​wmax​γ​\(cβ,N\)\],\\mathbb\{P\}\\\{\\\|E\_\{\\mathrm\{CU\}\}^\{s,e\}\(t\)\\\|\_\{\\mathrm\{op\}\}\\geq x\\\}\\leq 2\(d\+1\)\\exp\\left\[\-\\frac\{Cx^\{2\}\}\{Nv\_\{s,e,t\}^\{2\}\+c\_\{\\beta\}^\{\-1\}B\_\{d\}^\{2\}w\_\{\\max\}^\{2\}\+xB\_\{d\}w\_\{\\max\}\\gamma\(c\_\{\\beta\},N\)\}\\right\],\(40\)where

γ⁡\(c,N\)=log⁡Nlog⁡2​max⁡\{2,32​log⁡Nc​log⁡2\}\.\\gamma\(c,N\)=\\frac\{\\log N\}\{\\log 2\}\\max\\left\\\{2,\\frac\{32\\log N\}\{c\\log 2\}\\right\\\}\.\(41\)The same variance proxy appears for−Aj\-A\_\{j\}, which justifies the factor two\.

For a finite scan set𝒢\\mathcal\{G\}, defineλmmix​\(δ\)\\lambda\_\{m\}^\{\\mathrm\{mix\}\}\(\\delta\)as any valuexxfor which the right\-hand side of \([40](https://arxiv.org/html/2608.13922#A9.E40)\) is at mostδ/\|𝒢\|\\delta/\|\\mathcal\{G\}\|uniformly over\(s,t,e\)∈𝒢\(s,t,e\)\\in\\mathcal\{G\}\. Then

ℙ\{sup\(s,t,e\)∈𝒢∥ECUs,e\(t\)∥op≤λmmix\(δ\)\}≥1−δ\.\\mathbb\{P\}\\left\\\{\\sup\_\{\(s,t,e\)\\in\\mathcal\{G\}\}\\\|E\_\{\\mathrm\{CU\}\}^\{s,e\}\(t\)\\\|\_\{\\mathrm\{op\}\}\\leq\\lambda\_\{m\}^\{\\mathrm\{mix\}\}\(\\delta\)\\right\\\}\\geq 1\-\\delta\.\(42\)Every argument in[AppendicesC](https://arxiv.org/html/2608.13922#A3),[E](https://arxiv.org/html/2608.13922#A5)and[F](https://arxiv.org/html/2608.13922#A6)is deterministic conditional on such a uniform event\. Therefore the low\-rank score bound, the full multiple\-change induction, and the preliminary localization result hold verbatim after replacingλm\\lambda\_\{m\}byλmmix\\lambda\_\{m\}^\{\\mathrm\{mix\}\}\. No global stationarity of the piecewise\-distribution sequence is required for this transfer; the uniform mixing condition is imposed directly on the centered array\.

## Appendix JImplementation and experimental details

### J\.1Feature computation and scan complexity

The code never constructs a density estimate\. For a blockX∈ℝq×dX\\in\\mathbb\{R\}^\{q\\times d\}, it forms the lower\-right part of∑iH2​\(Xi\)\\sum\_\{i\}H\_\{2\}\(X\_\{i\}\)through a matrix multiplication plus a diagonal correction\. This costsO⁡\(q​d2\)O\(qd^\{2\}\)arithmetic\. A naive full prefix array costsO⁡\(n​d2\)O\(nd^\{2\}\)memory\. The multiple\-change implementation instead stores prefix matrices only at interval endpoints and coarse candidate locations, reducing memory toO⁡\(\|𝒫\|​d2\)O\(\|\\mathcal\{P\}\|d^\{2\}\)for a selected index set𝒫\\mathcal\{P\}\.

A dense symmetric eigendecomposition costsO⁡\(d3\)O\(d^\{3\}\)per scanned candidate and is used in the released reference code for numerical robustness atd≤200d\\leq 200\. An implementation needing only the largestrreigenvalues in magnitude can use a Lanczos\-type partial eigensolver, reducing the dominant per\-candidate spectral cost to approximatelyO⁡\(r​d2\)O\(rd^\{2\}\)matrix\-vector work\. In the large multiple\-change experiment, each interval is first scanned on at most 80 coarse candidates, and only selected intervals receive an exact local rescan\. The theory is stated for the full central candidate grid; the coarse\-to\-fine implementation is a computational approximation\.

All reported timings are single\-process wall\-clock measurements in Python/NumPy on an Intel Xeon Platinum 8573C virtual machine\. The environment used Python 3\.13, NumPy 2\.3, SciPy 1\.17, pandas 2\.2, and Matplotlib 3\.10\.

### J\.2Single\-change Gaussian\-copula experiment

For correlationρ\\rho, generate a bivariate standard normal pair\(G1,G2\)\(G\_\{1\},G\_\{2\}\)with correlationρ\\rhoand set

X1=2​Φ​\(G1\)−1,X2=2​Φ​\(G2\)−1\.X\_\{1\}=2\\Phi\(G\_\{1\}\)\-1,\\qquad X\_\{2\}=2\\Phi\(G\_\{2\}\)\-1\.All remaining coordinates are independentUnif⁡\[−1,1\]\\operatorname\{Unif\}\[\-1,1\]\. The marginals are uniform for everyρ\\rho, so all coordinate means and all marginal quadratic coefficients are unchanged\. Only the\(1,2\)\(1,2\)interaction changes\. Its projected jump has rank two and Frobenius norm equal to the Spearman correlation

κ=ρS=6π​arcsin⁡\(ρ/2\)\\kappa=\\rho\_\{S\}=\\frac\{6\}\{\\pi\}\\arcsin\(\\rho/2\)when the correlation changes from00toρ\\rho\. We useρ=0\.85\\rho=0\.85, a change atn/2n/2,n=60​dn=60d, and 50 independent replications\.

The odd observations are used for the preliminary direction scan and the even observations for local refinement\. Candidate scans use at most 250 evenly spaced coarse points \(200 atd=200d=200\), followed by an exact scan in the neighboring coarse cell\. The held\-out scalar least\-squares objective uses the first and last 20% of the fold as anchors\. The oracle baseline knows the affected scalar feature3​X1​X23X\_\{1\}X\_\{2\}\. The Gaussian\-copula density is not uniformly bounded at all corners for nonzeroρ\\rho; this experiment is therefore a stress test beyond the simple bounded\-density sufficient condition used for[Theorem5\.1](https://arxiv.org/html/2608.13922#S5.Thmtheorem1)\.

Table 2:Complete single\-change summary over 50 replications\.P≤4P\_\{\\leq 4\}is the proportion with absolute error at most four andP0P\_\{0\}is exact recovery\.The large standard deviations for a few preliminary settings reflect rare pilot scans that lock onto a distant noise peak\. The cross\-fitted refinement substantially reduces this tail atd=100d=100andd=200d=200; at the smallest two dimensions, its independent held\-out noise can slightly increase the median even while reducing some large errors\. This is why the paper reports both stages rather than asserting uniform finite\-sample improvement\.

### J\.3Multiple\-change experiment

We used=100d=100,n=24000n=24000, change points\(6000,12000,18000\)\(6000,12000,18000\), and copula\-correlation states\(0\.95,−0\.95,0\.95,−0\.95\)\(0\.95,\-0\.95,0\.95,\-0\.95\)\. Each projected jump is rank two\. The training\-fold minimum interval length is 700\. The threshold 30 is a fixed reproducibility choice rounded above the maxima of six independent null scans:

29\.076,28\.607,29\.517,28\.672,28\.850,29\.776\.29\.076,\\ 28\.607,\\ 29\.517,\\ 28\.672,\\ 28\.850,\\ 29\.776\.This small calibration is not presented as a formal finite\-sample level guarantee; the theorem instead supplies an analytic separation condition, and a larger null bootstrap can be used in applications\.

Table 3:Multiple\-change summary over 12 independent replications\. Errors are Hausdorff distances in original time units\.All 12 refined outputs place every estimated change within 10 observations of its matched truth\. Mean end\-to\-end runtime is 8\.93 seconds\.

### J\.4UCI Human Activity Recognition experiment

The public UCI HAR data contain 561 precomputed smartphone features in\[−1,1\]\[\-1,1\]\([1](https://arxiv.org/html/2608.13922#bib.bib2)\)\. We concatenate the official train and test partitions, retain activity labels 1 \(WALKING\) and 3 \(WALKING\_DOWNSTAIRS\), and choose the 128 coordinates of largest pooled variance\. In every replication, 400 rows are sampled with replacement from each activity\. Each row is multiplied by an independent Rademacher sign\. The population first moment of the sign\-symmetrized distribution is exactly zero, while every degree\-two product is unchanged because the sign squares to one\. Hence the benchmark isolates a non\-mean distribution shift\.

Table 4:UCI\-HAR localization over 50 randomized replications,d=128d=128andn=800n=800\.
### J\.5Reproduction commands

The supplementary source containscode/simulations\.pyandcode/har\_experiment\.py\. From the source root, regenerate the synthetic experiments with

> python code/simulations\.py \-\-out results \-\-single\-reps 50 \-\-multiple\-reps 12 \-\-seed 250813

For UCI HAR, first download the public archive, concatenate the official train and test feature/label files, and run

> python code/har\_experiment\.py \-\-x X\_all\.txt \-\-y y\_all\.txt \-\-out results \-\-reps 50 \-\-dimension 128 \-\-segment\-size 400

The scripts write raw replication\-level CSV files, summaries, and all figures used in the manuscript\.