Introduction
Curve registration is a fundamental problem in signal processing and statistics, appearing in diverse applications such as medical imaging (e.g., aligning ECG signals) and computer vision (e.g., matching SIFT descriptors). The core task involves determining whether two observed signals are identical up to a spatial transformation, such as a horizontal shift. This paper establishes the fundamental statistical limits for this problem, specifically focusing on the "shifted curve model."
In this model, a researcher observes two noisy signals and must decide if one is simply a shifted version of the other. The primary challenge lies in the unknown shift, which acts as a "nuisance parameter." If the shift were known, the problem would reduce to standard signal detection. However, because the shift must be accounted for or estimated, the statistical complexity increases. This research derives the minimax separation rate—the minimum distance required between two curves to reliably distinguish them—and proposes an adaptive testing procedure that remains effective even when the underlying signal smoothness is unknown.
The Shifted Curve Model
The author treats the problem using a Gaussian sequence model, analyzing the signals through their Fourier coefficients. The model assumes that we observe two signals, where the difference between them is obscured by Gaussian noise with variance $\sigma^2$.
The statistical task is framed as a hypothesis test:
- Null Hypothesis ($H_0$): The two signals are identical up to some unknown horizontal shift $\tau$.
- Alternative Hypothesis ($H_1$): The signals are separated by at least some distance $\rho$ in the $l_2$ norm, regardless of the shift.
The goal is to find the smallest $\rho$ (the separation rate) for which a test can successfully distinguish these hypotheses with high probability.
Methodology
1. The Test Statistic
The paper introduces a test statistic, $\lambda_\sigma(N)$, based on the minimum distance between the Fourier coefficients of the two signals across all possible shifts $\tau$. This approach is essentially a generalized likelihood ratio test adapted for the Fourier domain.
2. Nonadaptive and Adaptive Testing
Initially, the author develops a test for scenarios where the "smoothness" of the signal (defined by Sobolev balls of order $s$) is known. However, in practical applications, the smoothness parameter $s$ is rarely available. To address this, the paper proposes an adaptive procedure. This method employs a "Bonferroni" approach, running a collection of tests over a grid of potential smoothness parameters and selecting the maximum. The research demonstrates that this adaptive approach achieves the optimal rate without prior knowledge of the signal's regularity.
3. Minimax Lower Bounds
To ensure the proposed tests are optimal, the author utilizes information-theoretic arguments to establish lower bounds. These bounds prove that if the distance between curves is smaller than the derived rate, the sum of Type I (false alarm) and Type II (missed detection) errors will inevitably approach 1, rendering any statistical test no better than a random guess.
Key Insights: The "Price" of the Shift
The most significant finding of this work is the quantification of the "cost" of registration. The unknown shift introduces a logarithmic penalty to the separation rate. Specifically, the rate is proportional to:
$$(\sigma^2 \sqrt{\log \sigma^{-1}})^{2s/(4s+1)}$$
In standard signal detection problems where no shift is present, the $\sqrt{\log \sigma^{-1}}$ factor is absent. This term represents the inherent statistical cost of not knowing the registration parameter. The problem is characterized as "semiparametric" because it involves both a finite-dimensional nuisance parameter (the shift) and an infinite-dimensional functional parameter (the curve itself). The results show that the shift cannot be estimated with enough precision to ignore its impact on the overall testing rate.
Conclusion
This paper provides the theoretical "speed limits" for curve registration algorithms. It proves that both the nonadaptive and adaptive tests are asymptotically minimax optimal as the noise level $\sigma$ approaches zero.
While the results are mathematically rigorous, they do have limitations. The focus is primarily asymptotic, and the model assumes the noise variance $\sigma^2$ is known. Furthermore, the study is limited to horizontal shifts. Future research may extend these minimax results to more complex deformations, such as non-linear time-warping, scaling, or rotations, providing a broader framework for signal comparison in high-noise environments.
Summary updated