High-Dimensional Nonparametric Change-Point Detection via Low-Rank Degree-Three Density Projection

Guoqing Zhang; Zhaixin Chen

cs.LGAug 16, 2026

High-Dimensional Nonparametric Change-Point Detection via Low-Rank Degree-Three Density Projection

Authors: Guoqing Zhang, Zhaixin Chen

Organizations: Operations Research Program North Carolina State University Raleigh, NC, USA · H. Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology Atlanta, GA, USA

Abstract

Distributional changes can be invisible to means and covariances yet appear in skewness, asymmetric interactions, or other third-order structure. We develop a nonparametric change-point method that retains every degree-at-most-three coefficient of a density while avoiding direct density estimation. For observations in $[-1,1]^d$ , we construct a symmetric order-three Legendre feature tensor $H_3(X)\in\Sym^3(\R^{d+1})$ such that $A(f)=\E_fH_3(X)$ is an exact isometric encoding of the degree-three density projection: $\|A(f)-A(g)\|_{\F}=\|P_3(f-g)\|_{L^2}$ . Instead, fixed tensor contractions are degree-three polynomial chaoses with $ψ_{2/3}$ tails. The two terms have the characteristic order-three tensor scaling and match the powers in sharp concentration results for simple random tensors. For a coordinate-orthogonal specialization, the bound improves to $\sqrt{\log d}$ and enables a prefix-sum implementation in hundreds of dimensions. We derive the exact population tent shape and localization margin, introduce a seeded shortest-interval algorithm with a padded local recentering step, and prove exact recovery by induction: null recursive segments remain inactive, every undetected change retains a balanced isolating interval, and the shortest active seed contains exactly one change before recentering. A two-way cross-fitted scalar refinement attains $O_{\Pp}(κ^{-2})$ localization in the small-jump regime, matching a Le Cam lower bound on a pure cubic family whose degree-two projection jump is exactly zero. Reproducible experiments at $d\in\{20,50,100,200\}$ and a three-change $d=100$ sequence demonstrate the intended high-dimensional regime without materializing a $(d+1)^3$ tensor.

Figures & tables

Polynomial term	Multiset	Permutations	Tensor entry
$1$	$\{0,0,0\}$	$1$	$1$
$a_{j}x_{j}$	$\{0,0,j\}$	$3$	$a_{j}/3$
$b_{j}p_{2}(x_{j})$	$\{0,j,j\}$	$3$	$b_{j}/\sqrt{15}$
$\gamma_{ij}x_{i}x_{j}$	$\{0,i,j\}$	$6$	$\gamma_{ij}/(3\sqrt{6})$
$c_{j}p_{3}(x_{j})$	$\{j,j,j\}$	$1$	$c_{j}/\sqrt{7}$
$\eta_{ij}p_{2}(x_{i})x_{j}$	$\{i,i,j\}$	$3$	$\eta_{ij}/(3\sqrt{5})$

Table 1: Entries of

A(f)

in terms of the conventional unnormalized polynomial coefficients. Every listed value is assigned to all distinct permutations of the indicated multiset.

$d$	$n$	LR-D3 pre.	LR-D3 ref.	all cubic	degree two	mean	runtime (s)
20	1200	34	32	48	462	324	0.009
50	3000	24	42	52	1222	753	0.021
100	6000	37	38	132	2496	2004	0.090
200	12000	34	30	52	5040	3417	0.339

Table 2: Median absolute localization error over

30

replications. Runtime is the mean wall-clock time for computing all listed methods on one replication.

Figure 1: Median single-change localization error. The structured degree-three methods and oracle remain stable as

d

grows, while procedures with zero population signal drift over an

O(n)

range. The unregularized all-cubic score pays for all

d

coordinates.

Figure 2: Population and diagonal-odeco degree-three CUSUM scores for a

d=100

pure cubic change at

400

Figure 3: Preliminary and refined estimates over

30

replications of the

d=100

three-change experiment. Dashed lines mark the true changes.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 4: At

d=100,n=800

, the unregularized implicit full-tensor score is dominated by tensor noise, while the diagonal-odeco score tracks the population tent. This behavior is consistent with the

d^{3/2}/\sqrt{n}

CUSUM term in Equation 24 .

$d$	$n$	Method	Median	Mean	$q_{0.9}$
20	1200	LR-D3 preliminary	34	88.33	268.4
20	1200	LR-D3 refined	32	81.33	288.6
20	1200	All cubic diagonal	48	119.87	303.6
20	1200	Full degree two	462	420.80	504.0
20	1200	Mean CUSUM	324	319.20	493.2
20	1200	Oracle cubic	30	70.27	251.6

Appendix

Table 3: Median, mean, and

90\%

quantile of absolute localization error over

30

replications.

Explore similar work

High-dimensional nonparametric changepoint detection via low-rank degree-two density projection
Aug 14, 2026Guoqing Zhang, Zhaixin ChenDistribution Shift Detection Change-Point Detection
Operations Research Program North Carolina State University Raleigh, NC, USA · H. Milton Stewart School of ISyE Georgia Institute of Technology Atlanta, GA, USA
Locally Private Parametric Methods for Change-Point Detection
Feb 14, 2026Anuj Kumar Yadav, Cemre Cadir, Yanina Y. Shkel +1Change-Point Detection Differential Privacy
School of Computer and Communication Sciences, École Polytechnique Fédérale de Lausanne (EPFL), Vaud, Switzerland.
High-Dimensional Online Change Point Detection with Adaptive Thresholding and Interpretability
Sep 21, 2026Sven Jacob, Bardh Prenkaj, Weijia Shao +1Change-Point Detection Sliced Wasserstein Distance
Federal Institute for Occupational Safety and Health, Dresden · Technical University of Munich, Munich Center for Machine Learning · Sapienza University of Rome

Aug 14, 2026, cs.LGJ/K move · Enter open · S save

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

Guoqing Zhang, Zhaixin Chen

Operations Research Program North Carolina State University Raleigh, NC, USA · H. Milton Stewart School of ISyE Georgia Institute of Technology Atlanta, GA, USA

Distribution Shift Detection Change-Point Detection

Open paper AskPDF arXiv

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

, a symmetric feature matrix

H_2(X)\in\R^{(d+1)\times(d+1)}

is constructed so that

M(f)=\E_f H_2(X)

is an isometric encoding of the degree-two orthogonal projection of the density. We scan matrix CUSUMs after rank-

r

truncation, exploiting the low rank of the projected jump rather than sparsity of individual coordinates. The resulting \LRD{} estimator has a tent-shaped population objective and a nonasymptotic operator-norm analysis whose leading stochastic term scales as

\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, attaining

\widetilde O_{\Pp}(κ^{-2})

error; a matching Le Cam lower bound shows optimality up to logarithms. A geometrically

β

-mixing extension follows from a dependent matrix Bernstein inequality. Experiments with ambient dimension up to

200

, a three-change

d=100

sequence, and a

128

-feature human-activity benchmark show that the method remains computationally practical and accurately detects pure dependence changes that are invisible to mean CUSUMs.

Abstract

Explore similar work

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

Locally Private Parametric Methods for Change-Point Detection

High-Dimensional Online Change Point Detection with Adaptive Thresholding and Interpretability