PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Guoqing Zhang, Zhaixin Chen

arXiv:2608.13922v1cs.LGstat.ML

TL;DR

High-dimensional changepoint detection is challenging for nonparametric distributional changes, especially dependence and interactions beyond coordinate means. This paper encodes degree-two density information as matrix means, scans low-rank matrix CUSUMs, and reports accurate detection with refined median error 0 and 72% exact recovery in experiments.

  • Problem

    High-dimensional distributional changes can involve dependence, marginal shape, or interactions while coordinate means remain unchanged, making density estimation and unrestricted second-order scans difficult.

  • Method

    The method encodes degree-two density projections as symmetric matrix means and detects changes using rank-truncated matrix CUSUMs with cross-fitted scalar refinement.

  • Results

    Refined LR-D2 achieved median error 0, 72% exact recovery, and error at most 4 in 94% of randomized runs, while mean CUSUM never fell within 4.

  • Takeaways & Limitations

    The representation is useful for high-dimensional dependence changes generated by a small number of interaction directions and separates detection, isolation, and local refinement.

  • Takeaways & Limitations

    The method cannot detect density changes orthogonal to all degree-at-most-two polynomials, and its exact theory assumes low-rank projected jumps.

Abstract

from arXiv · show

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.

1 INTRODUCTION

The paper detects high-dimensional distributional changes by encoding degree-two density information as matrix means, then using low-rank matrix CUSUMs to capture interaction changes beyond coordinate mean shifts. It establishes localization and detection guarantees, extends to multiple changes and dependent data, and introduces cross-fitted refinement with near-minimax localization.

  • Representation: Degree-two density information is encoded isometrically in a symmetric (d + 1) × (d + 1) matrix mean, avoiding direct density estimation.The representation retains coordinate means, marginal quadratic components, and pairwise interactions through a single-observation feature map H2.
  • Low-rank detection: Low-rank truncation denoises matrix CUSUMs when the projected distributional jump is low rank, including dense interaction patterns that are not coordinate-sparse.The matrix dimension grows linearly with d, while retained rank controls effective stochastic complexity.
  • Theory: Every population matrix CUSUM on a one-change interval is a positive scalar multiple of the same jump matrix, yielding an exact linear localization margin.The paper combines this population structure with a deterministic low-rank perturbation inequality and matrix Bernstein concentration.
  • Theory: The leading normalized CUSUM noise scales as sqrt(rd log(nd)) in operator norm, with signal requirement ∆κ2 ≳ rd log(nd) up to constants and lower-order terms.The stated result holds under a bounded-density condition.
  • Multiple changes and refinement: SEEDED-LR-D2 recovers multiple changes by induction, while REFINE-LR-D2 cross-fits direction learning and localization to achieve near-minimax κ−2 localization.The induction maintains active balanced isolating intervals and selects the shortest active interval containing exactly one change.

2 DEGREE-TWO DENSITY REPRESENTATION

The section encodes the degree-at-most-two density projection through the matrix mean M(f) = E_f H_2(X), with normalization chosen to preserve an isometric relationship. This reduction makes matrix-mean estimation sufficient for the represented information, while densities sharing the same degree-two projection remain indistinguishable.

  • Representation: The degree-at-most-two projection is represented using Legendre-polynomial features under the uniform measure on [-1,1]^d.The squared L2 norms of the first Legendre polynomials are 1, 1/3, and 1/5.
  • Representation: Defining M(f) = E_f H_2(X) turns estimation of the projected density into estimation of a matrix mean.The normalization accounts for the double occurrence of off-diagonal entries in the Frobenius norm.
  • Identifiability limitation: The representation is limited to degree-two information: if P_2(f − g) = 0, degree-two features cannot distinguish f and g at the population level.This limitation follows directly from the isometric reduction.
  • Change-point model: For piecewise-constant independent observations, changes are described by segment matrices M_k and jumps D_k = M_k − M_{k−1}, with magnitude κ_k = ∥D_k∥_F.The model has ordered change points η_0 = 0 < η_1 < · · · < η_K < η_{K+1} = n and segment densities f_k.

3 LOW-RANK MATRIX CUSUM

The method scans rank-r-truncated matrix CUSUM scores, whose population objective has a tent shape around a single change. This structure yields a linear localization margin, while deterministic low-rank perturbation control accounts for approximation error.

  • Rank-r matrix CUSUM: The scan score applies a best rank-r approximation that retains the r eigencomponents with largest absolute eigenvalues of a symmetric matrix.This defines the low-rank truncation used in the scan.
  • Population objective: For a single change, all candidate population matrices share the same singular vectors and rank, while the population coefficient rises to the change and then decreases.The resulting population objective is tent-shaped around the change point.
  • Illustration: In a d = 100 Gaussian-copula example, the rank-two empirical score follows the population tent despite unchanged coordinate means and marginal distributions.Only dependence between the first two coordinates changes, making the change invisible to mean-based summaries.
  • Population objective: The exact linear margin after the change is proportional to (t −s)κ^2, providing the basis for localization.Here κ = ∥D∥F for the projected jump D = M1 − M0.
  • Perturbation control: A deterministic low-rank perturbation inequality controls the truncation step, while the approximation-tail term for an approximately rank-r jump is given separately.The tail contribution is stated in Section C.1.

4 MULTIPLE CHANGES AND CROSS-FITTED REFINEMENT

The multiple-change procedure uses seeded, shortest-above-threshold intervals with interval deletion to preserve isolating intervals during recursion. A cross-fitted refinement then uses a pilot-fold rank-r direction and held-out data to reduce localization to a scalar mean-change problem.

  • Seeded low-rank detection: Seeded detection scans dyadic intervals with half-length spacing and restricts candidates to each interval’s central half.Intervals have lengths h ∈ {m, 2m, 4m, ...}, with candidate locations between s + h/4 and e − h/4.
  • Seeded low-rank detection: The procedure repeatedly selects the shortest interval above threshold, reports its candidate, and deletes that entire interval from further recursion.The containing active component is replaced by the nonempty components on either side of the selected interval.
  • Seeded low-rank detection: Interval deletion makes induction transparent: an interval containing one change and shorter than ∆ cannot remove another change.This supports exact recovery by preserving separation from additional changes during recursion.
  • Cross-fitted refinement: Cross-fitted refinement expands each selected interval to a one-change window, splits observations by parity, and scans the pilot fold for a normalized rank-r CUSUM maximizer.Disjoint outer anchor blocks estimate the left and right projected means before the central search.
  • Cross-fitted refinement: The pilot direction is independent of held-out noise, and conditional on alignment, localization reduces to a scalar mean change with effective jump at least a constant fraction of κk.This reduction uses the held-out fold for localization after learning the direction on the pilot fold.

5 THEORY

The theory establishes uniform low-rank CUSUM control, exact recovery of multiple changes, and cross-fitted localization with near-optimal κ^-2 accuracy. It also extends the recovery induction to geometrically β-mixing observations.

  • Uniform CUSUM control: Uniform CUSUM control supports low-rank scanning over O(n log(n/m)) seeded intervals.The stochastic bound’s leading term does not grow with interval length because the CUSUM weights have squared sum one.
  • Multiple-change recovery: Under m ≤ ∆/8, rank(Dk) ≤ r, and a suitable threshold, SEEDED-LR-D2 returns exactly K intervals in one-to-one correspondence with the true changes.Each selected interval contains exactly one change, has length at most ∆/4, and its maximizer satisfies |b̂k − ηk| ≤ ∆/4.
  • Cross-fitted localization: Cross-fitted refinement removes the non-minimax factor and achieves eOP(κ^-2) localization in the usual small-jump regime.The pilot fold learns the changing direction, while the other fold performs scalar localization; the direction condition holds when the pilot population CUSUM maximum is at least 8εr.
  • Temporal dependence: For uniformly geometrically β-mixing observations, dependent matrix Bernstein control replaces λm with λmix, and the deterministic recovery induction carries over.The replacement incorporates a dependent variance proxy and a logarithmic mixing penalty.

6 EXPERIMENTS

Experiments show LR-D2 detects dependence-only changes across dimensions, recovers multiple changes accurately, and performs strongly on sign-randomized 128-feature human-activity data.

  • Dimension scaling: LR-D2 remains near the oracle pair projection as dimension increases from d ∈{20, 50, 100, 200} in Gaussian-copula dependence-change experiments.Only the dependence between coordinates 1 and 2 changes, while coordinate means and marginals remain unchanged; the projected jump is rank two.
  • Multiple changes: SEEDED-LR-D2 estimates K = 3 every time across 12 replications, with median Hausdorff error 2 before and 1 after refinement.All refined estimates are within 10 time points, with mean runtime 8.93 seconds.
  • UCI human activity, 128 features: Refined LR-D2 achieves median error 0, exact recovery rate 72%, and error at most 4 in 94% of randomized 128-feature human-activity runs.Independent row-wise Rademacher signs eliminate first moments while preserving all degree-two products; mean CUSUM has median error 256 and never falls within 4.

7 DISCUSSION AND LIMITATIONS

The paper frames degree-two projection as a structured matrix-mean representation for dependence changes, while clarifying its detectability limits, low-rank assumptions, and dependence-theory scope.

  • Contributions: Degree-two projection converts broad nonparametric changes into a structured matrix-mean problem, especially for dependence changes driven by a few interaction directions.The framework separates detecting a signal, isolating each change, and achieving the optimal local rate.
  • Limitations: The method cannot detect density changes orthogonal to all degree-at-most-two polynomials, while higher-degree extensions require tensor structure or another finite feature family.Its detection scope is intentionally limited to changes represented by the chosen feature family.
  • Limitations: Exact theory assumes low-rank projected jumps; approximate rank creates a singular-value-tail bias.The limitation is explicit rather than hidden in the analysis.
  • Limitations: The sharp refinement theorem assumes independent observations, whereas the current dependent theory directly covers the preliminary matrix scan and m.Thus, the strongest refinement guarantee has narrower dependence coverage than the initial scan theory.

ETHICS STATEMENT

The work uses public or synthetic data for methodological evaluation and does not infer sensitive personal attributes. A missed change concerns only the chosen degree-two representation, not equality of the underlying distributions.

  • Data use: The UCI human-activity data serve only as a methodological benchmark, with no attempt to infer sensitive personal attributes.The study uses public or synthetic data.
  • Interpretation: A failure to detect a change does not establish that the two underlying distributions are identical.The method tests only the selected degree-two representation.

REPRODUCIBILITY STATEMENT

The appendices provide complete proofs and implementation details, while fixed-seed supplementary code reproduces every reported table and figure; UCI data are referenced but not redistributed.

  • REPRODUCIBILITY STATEMENT: Appendices include complete proofs, feature normalization, pseudocode, simulation distributions, tuning rules, and additional numerical summaries.These materials document both theoretical results and implementation choices.
  • REPRODUCIBILITY STATEMENT: Fixed-seed supplementary code generates every reported table and figure, while documenting the public UCI data source and expected file layout without redistributing the data.The UCI dataset itself is not included.

AI USE STATEMENT … J.2 SINGLE-CHANGE GAUSSIAN-COPULA EXPERIMENT

The paper develops and validates a degree-two matrix-feature approach to high-dimensional changepoint detection, with proofs covering representation, concentration, low-rank localization, multiple changes, dependence, and minimax limits. Implementation and experiments show practical computation and improved refinement behavior for dependence changes invisible to marginal means.

  • AI USE STATEMENT: AI-assisted methodology, proofs, code, experiments, numerical interpretation, citations, and manuscript editing were independently reviewed and verified by the authors.The authors retain responsibility for the final content.
  • A DEGREE-TWO REPRESENTATION: COMPLETE CALCULATIONS; A.1 ORTHOGONAL PROJECTION COEFFICIENTS; 2. This gives; A.2 PROOF OF THE ISOMETRY; A.3 ENVELOPE AND ISOTROPIC SECOND MOMENT: The degree-two density projection is encoded by a fixed symmetric feature matrix whose expectation can be estimated by an ordinary sample mean.The construction uses orthogonal polynomial identities under the product uniform measure, while bounded-density assumptions enter the independent-observation concentration theory.
  • B POPULATION MATRIX CUSUM ON A ONE-CHANGE INTERVAL; C LOW-RANK PERTURBATION AND APPROXIMATE RANK; C.1 APPROXIMATELY LOW-RANK JUMPS: The population matrix-CUSUM score is uniquely maximized at a nonzero change, while rank-r truncation preserves the signal with an approximation term that becomes zero for rank-r jumps.Approximately low-rank jumps add deterministic, location-dependent bias rather than altering the stochastic analysis.
  • D UNIFORM OPERATOR-NORM CONTROL: Uniform operator-norm control is obtained through matrix Bernstein bounds over seeded multiscale candidate triples, supporting the low-rank score analysis.The scanned family has O(n) triples per dyadic scale and O(log(n/m)) scales.
  • E SEEDED GEOMETRY AND THE MULTIPLE-CHANGE INDUCTION: The seeded narrowest-over-threshold procedure uses balanced isolating intervals and an induction preserving active components around undetected changes, recovering K changes with |b̂_k−η_k| ≤∆/4.An undetected change generates an isolating interval when m ≤∆/8, and the algorithm cannot terminate while one remains.
  • F PRELIMINARY LOCALIZATION FROM THE EXACT MARGIN; G CROSS-FITTED REFINEMENT; G.1 PILOT DIRECTION ALIGNMENT; G.2 ANCHOR MEANS AND LEAST-SQUARES DRIFT; G.3 A MAXIMAL BERNSTEIN LINE-CROSSING BOUND: The global CUSUM maximizer provides preliminary isolation but is not automatically rate-optimal, motivating cross-fitted direction learning and scalar refinement via anchor-based least-squares drift.Pilot alignment requires sufficient signal, and the held-out direction satisfies δV ≥κ/2 before maximal Bernstein line-crossing control is applied.
  • H MINIMAX LOCALIZATION LOWER BOUND; I UNIFORM GEOMETRIC β-MIXING EXTENSION: The lower-bound construction uses a rank-two dependence jump with κ=|θ| and Le Cam testing at h=⌊c1θ^-2⌋, while geometric β-mixing transfers the deterministic localization arguments under a uniform mixing event.The mixing extension requires no global stationarity of the piecewise-distribution sequence.
  • J IMPLEMENTATION AND EXPERIMENTAL DETAILS; J.1 FEATURE COMPUTATION AND SCAN COMPLEXITY; J.2 SINGLE-CHANGE GAUSSIAN-COPULA EXPERIMENT: Feature computation costs O(qd^2), partial eigensolvers can reduce spectral work to approximately O(rd^2), and a Gaussian-copula experiment changes only dependence while refinement reduces large-error tails at d=100 and d=200.The experiment uses ρ=0.85, n=60d, 50 replications, odd/even cross-fitting, and an oracle baseline based on 3X1X2.

J.3 MULTIPLE-CHANGE EXPERIMENT · J.4 UCI HUMAN ACTIVITY RECOGNITION EXPERIMENT · J.5 REPRODUCTION COMMANDS

The multiple-change experiment accurately localized all three changes with low runtime, while the UCI-HAR setup tests dependence changes after eliminating first-moment information. Reproduction scripts regenerate the synthetic and human-activity experiments and their reported outputs.

  • J.3 MULTIPLE-CHANGE EXPERIMENT: The threshold 30 is a fixed reproducibility choice rounded above six independent null-scan maxima, not a formal finite-sample level guarantee.The theorem supplies an analytic separation condition, while applications can use a larger null bootstrap.
  • J.3 MULTIPLE-CHANGE EXPERIMENT: All 12 refined outputs place every estimated change within 10 observations of its matched truth, with mean end-to-end runtime of 8.93 seconds.The summary covers 12 independent replications and uses Hausdorff errors in original time units.
  • J.4 UCI HUMAN ACTIVITY RECOGNITION EXPERIMENT: The UCI HAR experiment uses 128 highest-pooled-variance coordinates from 561 smartphone features, retaining WALKING and WALKING DOWNSTAIRS activities.It samples 400 rows with replacement from each activity and independently Rademacher-sign-symmetrizes every row, making the population first moment exactly zero.
  • J.4 UCI HUMAN ACTIVITY RECOGNITION EXPERIMENT: UCI-HAR localization is evaluated over 50 randomized replications with d = 128 and n = 800.The experiment is based on the two selected activities after sign symmetrization.
  • J.5 REPRODUCTION COMMANDS: The supplementary source provides code/simulations.py and code/har experiment.py for reproducing the synthetic and UCI-HAR experiments.Synthetic experiments are regenerated with python code/simulations.py --out results.
  • J.5 REPRODUCTION COMMANDS: For UCI HAR, users download and concatenate official train/test files before running python code/har experiment.py --x X all.txt --y y all.txt.The command uses --out results --reps 50 --dimension 128 --segment-size 400, and scripts write replication CSVs, summaries, and manuscript figures.
Loading 2608.13922v1…