📊 statistics

Change point analysis of high-dimensional data using random projections

This paper proposes a novel change point detection method for high-dimensional data that leverages random projections to reduce dimensionality, combines univariate test results via multiple comparison techniques, and utilizes the mode of repeated estimates to improve stability and accuracy.

Original authors: Yi Xu, Yeonwoo Rho

Published 2026-03-04

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yi Xu, Yeonwoo Rho

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find the exact moment a quiet room suddenly starts playing loud music. Now, imagine that instead of just listening to one speaker, you are monitoring 1,000 different speakers all at once, and they are all whispering, shouting, or humming in different languages. This is the challenge of analyzing high-dimensional data: finding a specific "change" (like a shift in temperature or a stock market crash) when you have thousands of variables screaming at you simultaneously.

This paper by Yi Xu and Yeonwoo Rho proposes a clever, "lazy" (in a good way) solution to this problem using Random Projections.

Here is the breakdown of their method using simple analogies:

1. The Problem: The "Needle in a Haystack"

In the past, statisticians tried to analyze all 1,000 speakers at once. This is like trying to hear a single conversation in a crowded stadium by listening to the roar of the whole crowd. It's computationally heavy, and if you try to simplify the crowd by picking just one "best" speaker (a method called Functional Principal Component Analysis), you might accidentally pick a speaker who isn't talking about the music shift at all. You lose the signal.

2. The Solution: The "Flashlight in the Dark"

The authors suggest a different approach. Instead of trying to understand the whole stadium, imagine you have a flashlight that can shine a beam of light in a random direction.

The Random Projection: You shine your flashlight in a random direction across the crowd. You only listen to the sound that hits that specific beam.
The Magic: Even though the beam is random, if the "music shift" is happening, it will likely be loud enough to be heard in that beam.
The Catch: If you only shine the flashlight once, you might get unlucky and shine it in a direction where the music shift is silent. You might miss the change.

3. The Strategy: The "Crowdsourced Detective"

To fix the "unlucky beam" problem, the authors suggest a two-step process:

Step A: The Ensemble (Shine the light many times)
Instead of shining the flashlight once, you shine it 200 times in 200 different random directions.

For each beam, you ask a simple question: "Did the sound change here?"
Since you are doing this 200 times, even if 190 beams miss the signal, the 10 beams that do catch the signal will scream "YES!"

Step B: The Vote (Combining the results)
You take the 200 answers and combine them. If even a few of them say "Yes, there was a change," you trust the group. This is like asking 200 people in a room, "Did you hear a noise?" If 10 people say yes, you know something happened, even if the other 190 didn't hear it.

4. The "Wobbly" Estimate: Finding the True Spot

Here is the tricky part. Because the flashlight directions are random, the exact moment you think the noise started might jump around.

Run 1: You think the music started at 2:00 PM.
Run 2: You think it started at 2:05 PM.
Run 3: You think it started at 1:55 PM.

This is called variability. To solve this, the authors suggest doing the whole experiment 1,000 times.

If you do it 1,000 times, you might get 2:00 PM ten times, 2:05 PM five times, and 1:55 PM three times.
The Mode (the most frequent answer) is your best guess. It's like asking a crowd of 1,000 people to guess a number; the number that appears most often is usually the right one.

5. Real-World Example: The Australian Thermometer

The authors tested this on temperature data from 8 Australian cities.

The Old Way: Trying to analyze the complex weather patterns of all cities at once is hard and often misses the exact year the climate shifted.
The New Way: They used their "random flashlight" method. They found that for most cities, the method consistently pointed to a specific year (like 1972 for Sydney).
The Result: For some cities, the "flashlight" kept pointing to different years, suggesting the temperature didn't just jump one day; it slowly drifted over time. This nuance is something the old methods often miss.

Why is this a big deal?

It's Simple: You don't need to be a math genius to understand the logic. It turns a super-hard 1,000-dimensional problem into 200 easy 1-dimensional problems.
It's Robust: It doesn't matter if you pick the "wrong" random direction; you just pick more directions until you find the right one.
It's Fast: It avoids the heavy computer processing required by older, complex methods.

In a nutshell: When you are drowning in data, don't try to drink the ocean. Just take a few random sips. If enough of those sips taste like salt, you know you're in the ocean. And if you take enough sips, you can pinpoint exactly where the water got salty.

1. Problem Statement

The paper addresses the challenge of detecting a single change point in the mean vector of high-dimensional time series data ( $p$ -dimensional, where $p$ can be large or infinite).

Context: Modern applications in neuroscience, finance, and climate science generate high-dimensional or functional data.
Limitations of Existing Methods:
- Projection-based methods (e.g., FPC): Rely on selecting specific directions (like Principal Components). If the change vector is orthogonal to these directions, the method fails to detect the change.
- Fully functional methods: Require smoothness assumptions and basis function selection, which can be computationally expensive or sensitive to smoothing parameters.
- Multivariate statistics: Often require estimating large covariance matrices, self-normalization, or bootstrapping, and assume independence across dimensions.
Goal: Develop a method that avoids the pitfalls of specific direction selection, does not require smoothness assumptions, and remains computationally feasible without estimating high-dimensional covariance matrices.

2. Methodology

The authors propose a Random Projection (RP) based change point detection framework. The core idea is to project high-dimensional data into a one-dimensional space multiple times, apply univariate tests, and aggregate the results.

The Algorithm (Two-Step Process)

Step 1: Random Projections (RP)
- The $p$ -dimensional time series $X_t$ is projected onto $k$ random directions $d_1, \dots, d_k$ to create $k$ univariate time series $y_{t,r}$ .
- The projection is defined as $y_{t,r} = \frac{1}{\sqrt{k}} x_t^T d_r$ .
- Direction Generation: The authors follow Achlioptas (2003) using "sparse random projections" where entries are drawn from a distribution: $\{ \sqrt{3}, 0, -\sqrt{3} \}$ with probabilities $\{1/6, 2/3, 1/6\}$ . This balances computational speed and stability.
- Number of Projections ( $k$ ): Simulations suggest $k=200$ is sufficient for high accuracy, even though theoretical bounds (Johnson-Lindenstrauss) might suggest higher numbers.
Step 2: Univariate Testing and Aggregation
- Univariate Test: A standard CUSUM (Cumulative Sum) test or a Weighted CUSUM test is applied to each of the $k$ projected series.
- P-value Combination: The $k$ $k$ resulting p-values are combined to test the global null hypothesis ( $H_0$ $H_{0}$ : no change).
  - The paper evaluates several combination methods: Bonferroni, Benjamini-Hochberg (BH), Harmonic Mean p-value (HMP), and Cauchy Combination Test (CCT).
  - Recommendation: Bonferroni and BH are preferred for better size control and straightforward identification of significant tests.
- Change Point Estimation:
  - The method identifies the projection $r$ that yields the smallest adjusted p-value (most significant change).
  - The estimated change point $\hat{z}^*$ is the location of the maximum CUSUM statistic within that specific projection.

Handling Variability

Since random projections introduce variability in the estimated location, the authors propose a repetition strategy:

Repeat the entire RP-CUSUM-aggregation procedure $M$ times (e.g., $M=1000$ ).
Report the mode of the estimated change points across repetitions as the final estimate. This stabilizes the result and filters out outliers caused by "unlucky" random directions.

3. Key Contributions

Novel Framework: Introduces a method that aggregates multiple random projections rather than relying on a single optimal direction (like FPC) or a single random projection (previous benchmarks).
Avoidance of Covariance Estimation: Unlike many multivariate CUSUM methods, this approach does not require estimating the $p \times p$ covariance matrix, avoiding issues with high dimensionality ( $p > n$ ) and complex dependence structures.
No Smoothness Assumption: Unlike fully functional methods, it does not require the underlying signal to be smooth or the selection of basis functions.
Practical Stability Mechanism: Proposes the use of the mode of repeated estimates to mitigate the inherent randomness of the projection step.
Comprehensive Simulation Guide: Provides empirical guidelines for parameter selection (number of projections $k$ , trimming parameters, and combination methods) across various signal-to-noise ratios and break function complexities.

4. Simulation Results

The authors conducted extensive simulations comparing their method (RP-Bonf, RP-BH) against:

FPC-based methods (Aue et al., Berkes et al.).
Optimal projection methods (Wang and Samworth).
Fully functional methods (Aue et al., Dette et al.).

Key Findings:

Power and Size: The RP method generally demonstrates superior size control (Type I error) and power compared to existing methods, particularly when the change function is non-constant (spread across multiple basis functions).
Robustness: When the change is orthogonal to the leading principal components (a failure case for FPC), the RP method successfully detects the change because it explores random directions.
Parameter $k$ : $k=200$ random projections provided a good balance between computational efficiency and estimation accuracy (RMSE). Increasing $k$ beyond 200 yielded diminishing returns.
Combination Methods: Bonferroni and BH provided the best balance of power and size control. HMP and CCT showed higher power but struggled with size control (over-rejection) in some settings.
Location Accuracy:
- For non-constant breaks ( $m > 1$ ), RP methods achieved the most accurate location estimates (lowest RMSE).
- For constant breaks ( $m=1$ ), RP methods were comparable to other methods but showed higher variability, reinforcing the need for the repetition/mode strategy.
Repetition Strategy: Repeating the procedure 1000 times and taking the mode significantly reduced the variability of the location estimate, often outperforming single-run estimates of other methods.

5. Real-World Application

The method was applied to daily minimum temperature data from eight Australian weather stations (spanning ~100 years).

Setup: Data was aggregated into yearly sequences with $p=365$ (daily observations).
Execution: The RP-Bonf method was repeated 1000 times per station.
Results:
- For stations like Sydney, Hobart, and Gayndah, the distribution of estimated change points formed a sharp peak, indicating a stable, reproducible change year (e.g., 1972 for Sydney).
- For other stations, the distribution was multimodal, suggesting either multiple change points or a gradual transition, which the method successfully highlighted.
Conclusion: The application demonstrated the method's ability to provide stable, interpretable results in real-world climate data.

6. Significance and Limitations

Significance: The paper offers a computationally efficient, conceptually simple, and robust solution for high-dimensional change point detection. It bridges the gap between univariate tools and high-dimensional data without the heavy computational cost of multivariate covariance estimation.
Limitations:
- The current scope is limited to single change point detection.
- The method relies on the assumption that the change is not perfectly orthogonal to all random projections (which is highly probable with enough projections).
Future Work: The authors plan to extend the framework to detect multiple change points using binary segmentation.

In summary, this paper establishes Random Projections + Univariate CUSUM + P-value Aggregation + Repetition (Mode) as a powerful, state-of-the-art approach for detecting structural breaks in high-dimensional time series.