- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper studies how to detect and locate one change in the distribution of independent observations. For each possible position of the change, the method compares averages before and after that position. To do that, the paper uses functions derived from diffusion and distances to selected anchored points. The largest result across all positions and all groups of measurements is described using common random permutations. The main idea is that including information about a change is not enough. A method can still have low quality if most of the variance comes from quantities unrelated to that change. The authors then propose predicting the distances from the diffusion measurements and then using the remaining part of those distances and under a precise condition, this preserves the difference between the two distributions while reducing variance.
Critical strengths
Strengths. The statistical construction is good. The permutation procedure accounts for the search over both possible change positions and different measurements. The paper also explains when quantities fitted using all observations can be reused after permutation and the experiments compare methods on the same generated samples and report uncertainty from repeated simulation.
The interpretation of signal strength is interesting. Equation (9) expresses the leading signal as the fraction of total variance explained by the difference between the two parts of the sequence. This explains well why a kernel that can distinguish every pair of distributions may nevertheless perform poorly with a limited number of observations.
The circle example makes this explanation concrete. Removing variation unrelated to the change increases the leading signal by a significant factor and this is a factor for the theoretical signal.
Finally, the authors are honest and report cases where their method performs worse. Adding distances reduces power in one torus experiment. Wasserstein distance performs better in a circle concentration experiment, and Energy detects some changes more often. This reporting helps readers understand the limits of their theory
Critical weaknesses
My main concerns are the following.
-
The practical benefit of the regression step remains unclear to me as the explicit guarantee applies when the retained diffusion measurements have the same expectations before and after the change. Under this condition, the regression preserves the difference in mean distances while reducing variance. This is a sufficient condition for the stated gain, but to me not a necessary condition for every possible improvement. The main example places the change at frequency 3 while retaining only frequencies 1 and 2 in the diffusion measurements. It demonstrates the proposed mechanism correct but, the main experiments use a much richer Nyström approximation, with a higher rank. The simpler Band method is also competitive as it separates frequencies into groups and divides each group by its own variance. At frequency 3, it reaches the same power as the regression method, (0.996). These results support the importance of treating variation at different frequencies separately. They provide less evidence that regressing distances on diffusion measurements is the preferred solution.
-
Adding distances provides little improvement in the main experiments. Indeed, in Table 5, the method using distances does not show a clear advantage over the method using diffusion alone. It seems that the combined procedure usually performs similarly to diffusion alone. Thus, stronger evidence is needed to support the practical value of combining diffusion measurements with distances. Evaluating the distances after regression in these same experiments would be particularly informative.
-
Some pertinent direct comparisons are missing. I would use a Gaussian kernel on the usual vector representation of the observations, with several kernel widths. This would help determine whether the improvement comes from using the intrinsic geometry or from comparing several scales. Methods that rescale the calculated coordinates using their full covariance matrix are also relevant.
-
The applications are not yet demonstrated. All experiments use synthetic data on the circle, sphere, or torus. The motivating examples in the introduction include wind observations and sequences of covariance matrices, where dependence between successive observations can be important but the current theoretical guarantees assume independent observations. The synthetic experiments respect this assumption, but the connection to the motivating applications therefore remains narrow. An application to real observations would help.
Important : the presentation could also be more focused because the main ideas are obscured by very dense terminology and several additional results
Questions for authors
- Which theoretical results do you point as the main new contributions beyond permutation, cumulative sum, and regression ? 2.Does replacing the original distances by the remaining distances after regression improve the main experiments on the circle, sphere, and torus ? 3.How does the method compare with a Gaussian kernel using several widths, and with rescaling based on the full covariance matrix? 4.When should a practitioner choose the regression method rather than the simpler Band method?
- What are the total computation times for the main experiments?
7 comments
W2. The role of distances is to supply complementary contrasts outside a computed finite diffusion span. Exact heat kernel parametrizes the infinite representation; it does not guarantee that a finite approximation retains every contrast or weights it effectively. The third harmonic example demonstrates this distinction directly: H2 has zero population contrast, while the distance dictionary has a nonzero contrast that becomes effective after regression. Consequently, the residual distance construction detects a change that the retained diffusion channel alone cannot detect consistently through its mean contrast.
The additional ordinary directional mixture study provides another, more modest example of distance complementarity. With the fixed H2 representation, adding raw distances increases power from 0.436 to 0.468 in the clean weak mixture setting and from 0.362 to 0.396 with common measurement noise; the paired gains are 0.032 and 0.034. Residualization gives 0.418 and 0.350 in those same cells, underscoring that the value of distances and the benefit of projecting them are distinct questions.
This is also why raw distances and residual distances should be distinguished in the original study. The primary multiscale Nyström Combined method adds raw distances to a much richer Nyström representation. The rich-representation results show that the raw distance channel usually contributes little in those designs. It also reveals a genuine search cost: for the strongest torus dependence change, Heat has power 0.734 and Combined 0.668 because the additional channel contributes no new rejecting samples while increasing the joint threshold.
The following comparison uses the submitted implementation with 500 new paired replications per condition at and 199 common permutations. It replaces raw distances by residuals against a basis of the retained diffusion span. The submitted Heat/Combined powers for these three conditions are 0.068/0.068, 0.238/0.226 and 0.092/0.088; the independent rerun below evaluates all additional methods on common samples.
| Original-design condition | Heat | Raw Combined | Residual Combined | Exact Gaussian5 | Rank64 white |
|---|---|---|---|---|---|
| Circle shape, middle | 0.066 | 0.066 | 0.066 | 0.068 | 0.064 |
| Sphere shape, middle | 0.266 | 0.256 | 0.266 | 0.284 | 0.692 |
| Torus dependence, middle | 0.062 | 0.060 | 0.062 | 0.058 | 0.362 |
Exact Gaussian5 uses full ambient Gaussian Gram matrices at , where is the pooled median squared ambient distance. Rank64 white retains the leading 64 pooled principal coordinates of the concatenated heat/distance features and rescales them to unit covariance. Every method calibrates its complete split search with the same permutations. Rank64 white has higher power than Combined in the sphere and torus rows (0.692 versus 0.256 and 0.362 versus 0.060), showing the value of covariance weighting in these designs. The folded-embedding comparison in W3 examines a separate role for intrinsic geometry.
We ran a fine-scale change experiment using the original multiscale Nyström implementation. The two segment densities on the known unit circle are , with 1000 observations and a change at observation 500. Every method uses the same observations and 199 common permutations, trim 0.10, and nominal level 0.05. The five diffusion-time multipliers, rank cap 128 and 64 distance landmarks are unchanged; residualization uses a numerical basis of the retained diffusion span. The representation receives neither the changing frequency nor its amplitude. The Gaussian comparison uses the standard unit-circle embedding and nine bandwidths. The table reports 500 independent repetitions per setting.
Here the covariance control uses the unnormalized joint heat/distance coordinates with , where is their total number.
| Setting | Heat | Combined | Residual Combined | Unnormalized covariance ridge | Gaussian (9 scales) |
|---|---|---|---|---|---|
| Uniform null | 0.066 | 0.066 | 0.066 | 0.048 | 0.066 |
| , | 0.054 | 0.054 | 0.732 | 0.048 | 0.054 |
| , | 0.056 | 0.056 | 1.000 | 0.082 | 0.054 |
| , | 0.042 | 0.042 | 1.000 | 0.060 | 0.042 |
At , , residualization raises power from 0.056 to 1.000, and at , , from 0.042 to 1.000. This provides a multiscale Nyström example in which distance residuals retain a fine-scale contrast while regression removes variation shared with diffusion. Together with the coarse-scale results above, it identifies when residualization is useful. (revised Section 4.2, Table 4 and Appendix B.7, Table 12).
Continued in the next part
W3. We compared the original multiscale Heat and Combined procedures with exact ambient Gaussian kernels and a full-covariance scan. For a known unit-speed circle embedding
the derivative has norm one and the last coordinate pair identifies the angle. The round case is , , which has the same chord distances as the standard unit circle. Intrinsic arc distances and the heat kernel are unchanged. At , locations separated intrinsically by are only apart in the ambient space. This isolates the value of the supplied intrinsic metric.
The pre/post laws are and . For and change fraction 0.5, C and H are the original Combined and Heat scans; G9 is the exact nine-width Gaussian, WG9 applies it after pooled ambient whitening, and UG9 applies it after recovering the known circle coordinates. Block-normalized covariance ridge first normalizes each heat/distance block to unit pooled trace and jointly calibrates ridge factors .
| Signal / embedding | C | H | G9 | WG9 | UG9 | Block-normalized covariance ridge |
|---|---|---|---|---|---|---|
| Null, round | 0.044 | 0.046 | 0.046 | 0.048 | 0.046 | 0.042 |
| Null, folded | 0.044 | 0.046 | 0.044 | 0.046 | 0.046 | 0.042 |
| , round | 0.788 | 0.792 | 0.794 | 0.700 | 0.794 | 0.480 |
| , folded | 0.788 | 0.792 | 0.068 | 0.576 | 0.794 | 0.480 |
| , folded | 0.994 | 0.994 | 0.096 | 0.966 | 0.994 | 0.924 |
The geometric representation raises power from 0.068 to 0.788 relative to the nine-width ambient Gaussian in the folded case, and from 0.576 to 0.788 relative to its ambient-whitened version. The geometry-assisted Gaussian reaches 0.794, showing that supplying the same geometric preprocessing can also make that baseline competitive. Heat and Combined perform similarly here; their shared gain comes from the intrinsic representation.
The Gaussian kernels are , where is the pooled median squared distance and . Each method calibrates the entire declared scale-and-split search using the same 199 permutations. The ridge-regularized full-covariance scan is our implementation of the reviewer's suggested covariance rescaling: joint coordinates are transformed by an estimated covariance with ridge regularization for numerical stability. It is distinct from ambient-coordinate whitening. On the rich features, the unnormalized ridge rule has null 0.050 and powers 0.108/0.460/0.908 at ; the stronger block-normalized three-ridge control has null 0.042 and powers 0.118/0.480/0.924.
For the restricted Fourier comparisons, the Fourier covariance-ridge benchmark uses H2 at time and 16 distance landmarks, with and trace normalization after transformation. In the mixed-harmonic comparison, residual distances have null 0.042, power 0.986 and unconditional MAE 0.0306; the Fourier covariance-ridge scan has null 0.052, power 0.946 and MAE 0.0389. For the weak ordinary mixture, the same covariance benchmark has power 0.504 clean, 0.408 with wrapped noise, and 0.400 under 5% uniform contamination at change fraction 0.30. The covariance benchmark is stronger than raw augmentation in the clean and noisy weak-mixture cells (0.504 versus 0.468 and 0.408 versus 0.396); raw augmentation is stronger under contamination (0.428 versus 0.400).
Continued in the next part
Thank you for your time and valuable comments.
W1. The regression step addresses a specific statistical obstacle: a distance feature can contain a change omitted by a finite diffusion representation, while most of its variance repeats directions already represented by diffusion. Adding that feature makes the change visible, but does not necessarily make its signal large enough to detect. For feature mean contrast δ=PΨ−QΨ and change fraction θ, the leading trace-standardized signal is
θEP∣Ψ−PΨ∣2+(1−θ)EQ∣Ψ−QΨ∣2+θ(1−θ)∣δ∣2θ(1−θ)∣δ∣2.
This is the fraction of pooled feature variance explained by the change.
The paper contains a direct ablation of this obstacle. In the third-harmonic experiment, all methods use the same samples and permutations, and their feature rules are fixed across the tested frequencies:
The residual versus raw power gain is 0.942. The explicit circle calculation explains its magnitude: projection removes approximately 98.6% of the distance variance, preserves the changing third harmonic contrast, and increases the population signal slope from approximately 0.00037 to 0.0258, a factor of 69.1. H6 already contains the changing harmonic and has the same number of scalar coordinates as the residual construction, yet its power is 0.170. Thus neither raw distance augmentation nor increasing the representation size reproduces the improvement. The regression is a substantive variance allocation step in this construction.
Zero diffusion contrast is a sufficient condition for the stated gain; the general tradeoff also allows nonzero diffusion contrast. The general pooled-regression calculation gives
\qquad v_\perp=\operatorname{tr}\\!\left(\Sigma_{FF}-\Sigma_{FH}\Sigma_{HH}^{-1}\Sigma_{HF}\right).$$ Writing $v_F=\operatorname{tr}(\Sigma_{FF})$, the residual channel has a larger population signal slope precisely when $$\frac{\\|\delta_F-B_H\delta_H\\|^2}{\\|\delta_F\\|^2} > \frac{v_\perp}{v_F},$$ provided $\delta_F\ne0$ and both variances are positive. In words, the proportion of squared contrast retained must exceed the proportion of variance retained. This criterion allows $\delta_H\ne0$ and makes explicit the tradeoff that the zero-contrast example isolates. Because the original diffusion channels are retained, the invertible transformation $(H,F)\mapsto(H,F-B_H H)$ also preserves the existence of a nonzero joint mean contrast. This preserves retained information and consistency under the stated assumptions; finite-sample power also depends on variance allocation and joint calibration. A concrete extension illustrates this point. For balanced circle distributions $$p_\pm(x)=\frac{1\pm\\{0.10\cos x+0.35\cos(3x)\\}}{2\pi},$$ with the same H2 span and 16 equally spaced distance landmarks, the diffusion contrast is nonzero. Applying the residual contrast and covariance formulas above gives raw and residual distance slopes of 0.002836 and 0.025759, respectively, a **9.08-fold increase**. Projection removes some distance contrast, but removes a much larger proportion of its variance. In the mixed-harmonic experiment, the raw and residual combinations have powers **0.186 and 0.986**, respectively. Band also has power 0.986. The full-covariance comparison appears in W3 below. This extends the evidence beyond the sufficient zero diffusion contrast condition and shows how regression implements effective variance allocation. Band's strong performance supports the same signal and variance explanation. It offers an economical solution when useful spectral groups are available: at the third harmonic it achieves the same power in 5.9 ms versus 7.2 ms for residualization, and at the fourth harmonic it performs better (0.344 versus 0.072). Pooled regression offers a complementary implementation that uses a selected feature span and a distance dictionary without requiring a prescribed frequency partition. Its fitted values are invariant to an invertible change of basis within the diffusion span. We recommend Band when an interpretable spectral partition is available, and residual distances when complementary distance contrasts coexist with substantial variation predictable from the retained span. The theory and experiments support this conditional recommendation. (revised Section 3.2, Section 4.2 and Proposition D.1). Continued in the next part