PaperlayerView exact revision on arXiv

Source-linked AI summary

Minimax hypothesis testing for curve registration

Olivier Collier

arXiv:1109.1244v2math.ST

TL;DR

The paper asks how to perform goodness-of-fit testing for shifted curve registration when the shift and signal smoothness create a composite, semiparametric problem. It develops nonadaptive and adaptive testing procedures based on tuning and Bonferroni aggregation. The procedures attain minimax separation rates up to possible logarithmic factors, while the exact role of the logarithmic factor remains unresolved.

  • Problem

    Goodness-of-fit testing for the shifted curve model is difficult because the null is composite and semiparametric, and the shift parameter may not be uniformly consistently estimated.

  • Method

    The paper constructs a nonadaptive generalized-likelihood-ratio procedure with a smoothness-dependent tuning parameter, then aggregates tests across tuning values using a Bonferroni procedure for adaptation.

  • Results

    The nonadaptive and adaptive procedures achieve asymptotic minimax separation rates up to possible logarithmic factors, uniformly over families of Sobolev balls.

  • Takeaways & Limitations

    The shifted-curve testing problem has a minimax rate matching the signal-detection lower-bound order up to a possible logarithmic penalty, and adaptive testing remains rate optimal up to that factor.

  • Takeaways & Limitations

    A gap remains between the lower and upper bounds, so the logarithmic factor may or may not belong to the true minimax separation rate.

Abstract

from arXiv · show

This paper is concerned with the problem of goodness-of-fit for curve registration, and more precisely for the shifted curve model, whose application field reaches from computer vision and road traffic prediction to medicine. We give bounds for the asymptotic minimax separation rate, when the functions in the alternative lie in Sobolev balls and the separation from the null hypothesis is measured by the l2-norm. We use the generalized likelihood ratio to build a nonadaptive procedure depending on a tuning parameter, which we choose in an optimal way according to the smoothness of the ambient space. Then, a Bonferroni procedure is applied to give an adaptive test over a range of Sobolev balls. Both achieve the asymptotic minimax separation rates, up to possible logarithmic factors.

Introduction

The paper studies goodness-of-fit testing for shifted curve registration, motivated by noisy signals sharing a common pattern and applications such as computer vision and medicine. It formulates the problem in a Gaussian sequence model and evaluates procedures through asymptotic minimax separation rates.

  • Curve registration: Curve registration concerns noisy, distorted signals that share a common structure, with horizontal shifts providing a tractable deformation model.The paper notes applications including electrocardiogram interpretation and matching image descriptors.
  • Curve registration: Testing the shifted curve model can be central because estimation methods depend on the assumed deformation structure.
  • Shifted curve model: The shifted-curve problem is represented through Fourier coefficients, where a shift induces phase changes and the null tests whether the resulting pseudo-distance is zero.
  • Shifted curve model: The Gaussian sequence formulation uses independent complex Gaussian noise variables with known noise level σ.
  • Testing framework: The alternative restricts the signals to a Sobolev ball and separates them from the null by a distance at least Cρσ.
  • Minimax testing: Minimax testing characterizes the smallest separation permitting consistent tests while controlling first- and second-kind errors over composite parameter sets.

Composite null hypothesis testing

The shifted-curve problem has a composite, semiparametric null hypothesis that differs from standard signal-detection settings and complicates minimax testing. The paper develops nonadaptive and adaptive procedures whose separation rates are minimax-optimal up to possible logarithmic factors, while noting a gap between the lower and upper bounds.

  • Composite null hypothesis: The shifted-curve model involves a composite null hypothesis that is neither linear nor convex, so assumptions from earlier nonparametric-null tests do not apply.
  • Adaptive testing: The minimax approach requires choosing tests according to the smoothness class, motivating adaptive testing over smoothness sets such as [s1, s2] and [L1, L2].
  • Adaptive testing: Using the most constraining smoothness enables adaptation but causes a significant efficiency loss when the tested parameters are smoother.
  • Adaptive testing: A generalized maximum-likelihood procedure is used to construct both nonadaptive and adaptive minimax tests, with adaptive testing paying a possible noise-dependent factor.
  • Composite null hypothesis: The problem is qualitatively different because the null is both composite and semiparametric, and the finite-dimensional parameter may not be uniformly consistently estimated.
  • Minimax rates: An adaptive test is minimax rate optimal up to a possible logarithmic factor uniformly over Sobolev balls, but the paper acknowledges a gap between its lower and upper bounds.

Organization of the paper

The paper develops a nonadaptive testing procedure, analyzes its statistic under the null and alternative, optimizes its tuning parameter, and establishes lower-bound context for near-minimax performance.

  • Organization of the paper: The paper is organized around a nonadaptive procedure, an adaptive adjustment, minimax performance statements, and supporting proofs and lemmas.The model is discussed separately, while theorem proofs and their lemmas appear in later sections.
  • Nonadaptive procedure: The nonadaptive test uses standardized estimators of the pseudo-distance d(c, c#) and rejects when λσ(N) exceeds a threshold q.The tuning parameter N and threshold q determine the testing procedure.
  • Performance analysis: Under H0, λσ(Nσ) is bounded in probability, whereas under the alternative the statistic becomes much larger under a condition on ρσ.These two behaviors justify selecting a constant rejection threshold and yield the desired power.
  • Optimality and scope: The paper derives a lower bound and notes that the optimized constant C is specific to the test rather than claimed minimax-optimal.The lower-bound argument supports rate analysis, while the constant optimization is procedure-specific.
  • Tuning and rate: The heuristic balances bounded and perturbative terms to determine the optimal order of Nσ and a minimization problem for the constant C.The best rate is achieved when Nσ is of order ρ∗.

2. Adaptive testing procedure

The adaptive procedure removes dependence on the unknown smoothness and radius by maximizing tests over a carefully chosen set of tuning parameters, while retaining the nonadaptive separation rate uniformly over a smoothness range.

  • Motivation: The adaptive problem arises because the nonadaptive test requires the smoothness s and radius L, which are impractical to specify in advance.The procedure therefore targets independence from s and L.
  • Adaptive construction: The proposed test depends only on the interval [s1, s2], not on the actual s or L, and achieves the same separation rate as the known-parameter test.The rate holds uniformly over Sobolev classes with s in [s1, s2] and L in compact subsets of R+.
  • Adaptive construction: A Bonferroni maximum over tests with several tuning parameters replaces the single nonadaptive choice of Nσ(s, L).The construction changes Nσ(s, L) to Nσ(s) and considers the maximum over the resulting tests.
  • Tuning grid: The tuning-parameter set must be small enough to control the first-kind error but rich enough to approximate all Nσ(s) over the target smoothness interval.Each selected N covers a short range of smoothness values around a corresponding S.
  • Result: The adaptive test retains the nonadaptive rate because the null maximum has loglog-order, which is negligible relative to the perturbative term.Thus, the adaptive maximization does not deteriorate the test's performance.

3. Lower bound for the minimax rate

The paper establishes a lower bound for shifted-curve testing by reducing it to classical signal detection, showing that the asymptotic minimax separation rate is at least σ4s/4s+1. The section also discusses model extensions, assumptions, and alternative estimators.

  • The shifted-curve problem is compared with classical signal detection, whose lower-bound results can be transferred to the shifted model.The comparison uses Sobolev alternatives with l2 separation from zero.
  • Theorem 3 relates the minimax testing problems for the shifted-curve and classical signal-detection models.The infima are taken over all tests of level α in the respective models.
  • The asymptotic minimax separation rate for the shifted-curve problem is not smaller than σ4s/4s+1.This lower bound follows by exploiting nonasymptotic results for the classical model.
  • The theoretical analysis is conducted for the Gaussian sequence model, with an analogous regression procedure available for deterministic equidistant designs when s > 1/2.The regression extension relies on asymptotic equivalence, while the noise variance is not assumed known in practice.
  • A plug-in variance estimator is expected to preserve rate-optimality, while unequal variances, dilatations, and weighted estimators require adaptations.The paper states that a similar plug-in result is believed to hold in this setup and that replacing σ by max(σ, σ#) handles unequal variances.

From classical signal detection to shift testing

A natural strategy is to estimate the shift and then apply classical signal-detection methods, but the paper explains why this approach fails. Shift nonidentifiability makes perturbative analysis unavoidable and may increase the minimax separation rate.

  • Estimating the shift first and applying classical signal-detection methods is proposed as an initial strategy.
  • The strategy fails because no consistent shift estimator can generally be obtained, including cases where the shift is not identifiable.The resulting uncertainty requires accounting for every possible shift.
  • Shift uncertainty entails a supplementary factor in the minimax separation rate.The paper presents this as a consequence of the unavoidable perturbative term.

Future research

Future work could extend the simple shifted-curve model to signals that are both shifted and dilated. The central open issue is whether the dilatation parameter can be estimated consistently.

  • The authors propose studying curve registration when signals are shifted and dilated.This would extend the current shifted-only model through a pseudo-distance.
  • The key unresolved issue is consistent estimation of the dilatation parameter.

5. Proof of Theorem 1

The proof establishes the asymptotic level of the test and then analyzes its second-kind error. It uses a shift representation under the null, inequalities, Berry–Esseen bounds, and a decomposition into terms of different orders.

  • Under the null, the proof introduces a real number τ ∗ satisfying c#j = eijτ ∗cj for every j ≥1.The dependence of τ ∗ on c and c# is suppressed.
  • Berry-Esseen’s inequality is used to show that the asymptotic first-kind error does not exceed the prescribed level α.The proof concludes that the test has the desired asymptotic level.
  • The second-kind error is studied by decomposing λσ(Nσ) into several terms and controlling their respective orders of magnitude.
  • The proof introduces notation and constants before separating the different terms for independent analysis.The constants include c′ and ǫ in addition to cs,L.
  • The resulting bounds are handled through successive probability estimates and applications of Lemmas 1 and 2.The displayed proof steps separately study the relevant probability terms.

6. Proof of Theorem 2

The proof establishes that the test’s first- and second-kind errors converge to zero as σ tends to zero, using Gaussian approximation and bounds involving the tuning parameters. It also approximates the smoothness parameter s by S with a logarithmic accuracy sufficient for the argument.

  • The first-kind error of the test ˜ψσ converges to 0.
  • Berry-Esseen’s inequality supplies bounds whose right-hand sides converge to 0 as σ tends to zero.
  • The second-kind error of the test converges to 0.
  • The proof controls another term using Lemma 3, with a right-hand side that again converges to 0 as σ tends to zero.

7. Proof of Theorem 3

The proof reduces testing in the shifted curve model to a corresponding test in the classical model. The constructed classical test is measurable with respect to the observed sequence and has no larger first- or second-kind errors.

  • A randomized test in the shifted curve model is converted into a classical-model test with smaller first- and second-kind errors.
  • The classical test is defined by integrating the original test over independent Gaussian noise.
  • The resulting test is measurable with respect to Y and therefore constitutes a test for the classical model.
  • When c# = 0, the classical procedure is interpreted within the shifted curve model because d(c, c#) = ∥c∥2.
  • A similar inequality holds for the second-kind error.

8. Lemmas

The lemmas provide the technical ingredients for controlling Gaussian quadratic expressions, smoothness approximations, and error bounds used in the theorem proofs. They include Gaussian comparison results, Berman’s formula, Berry-Esseen’s inequality, and Sobolev-ball calculations.

  • Lemmas 1–3: Lemma 1 bounds separated Sobolev-ball elements when the truncation level satisfies N + 1 ≥ cρ−1/s.
  • Lemmas 2–3: Lemmas 2 and 3 control expressions involving independent complex Gaussian variables and vectors from Fs,L.
  • Gaussian bounds: Lemma 4 provides a Gaussian-process bound for sums involving independent complex Gaussian variables.
  • Gaussian bounds: Lemma 5 is proved using Berman’s formula after computing the derivatives of the relevant functions.
  • Smoothness approximation: Lemma 6 justifies approximating the smoothness parameter s by S over a positive interval.
  • Gaussian approximation: Berry-Esseen’s inequality supplies Gaussian approximation bounds, including a specialized case for centered Gaussian quadratic variables.
Loading 1109.1244v2…