PaperlayerView exact revision on arXiv

Source-linked AI summary

On Sample Complexity Bounds for Frequency-Domain System Identification

Arya Honarpisheh, Mario Sznaier

arXiv:2610.31960v1eess.SYcs.SY

TL;DR

Frequency-domain system identification often has only a bound on measurement-noise magnitude rather than detailed statistical information. This paper analyzes consistent interpolatory algorithms and derives worst-case and stochastic error bounds. For equally spaced samples the worst-case excess above the noise level has tight rate Θ(N^-2), while stochastic rates depend on noise concentration near the boundary and need not be exact from the available bounds.

  • Problem

    When noise distributions are not fully known but their magnitude is bounded, the accuracy of frequency-domain system identification needs bounds that account for that limited information.

    Source: §1 · p. 1, §3 · p. 2

  • Method

    The paper bounds consistency-set radius and diameter for interpolatory identification, treating both worst-case noise and bounded stochastic noise.

    Source: §3 · p. 2

  • Results

    For equally spaced samples, the worst-case consistency-set radius approaches the noise level at the tight rate Θ(N^-2), while stochastic bounds can converge to zero at rates dependent on boundary concentration.

    Source: §1 · pp. 1–2, §7 · p. 7

  • Takeaways & Limitations

    Bounded stochastic noise can permit high-probability error bounds below the noise level and converging to zero, with the rate depending on its distribution near the noise-set boundary.

    Source: §1 · p. 2, §7 · p. 7

    For uniform disk noise, the upper and lower bounds do not establish the exact stochastic convergence rate.

    Source: §5.1 · p. 6

Abstract

from arXiv · show

We study the sample complexity of frequency-domain system identification with bounded measurement noise. We focus on interpolatory identification algorithms, which return models consistent with both the data and a priori constraints. For equally spaced samples, we sharpen previous worst-case bounds on the consistency-set radius. Its excess above the noise level decays as $N^{-2}$, where $N$ is the number of samples, and a matching lower bound shows that this rate is tight. We then examine whether bounded stochastic noise allows identification below the noise level. We show that high-probability error bounds can converge to zero. Their convergence rate depends on how strongly the noise distribution is concentrated near the boundary of the noise set. For example, noise uniformly distributed on a disk gives an upper bound of order $(\log N/N)^{2/3}$. Numerical experiments examine these convergence rates and the effect of the noise distribution on the identification error.

1. INTRODUCTION

The paper sharpens worst-case consistency-set bounds for equally spaced frequency samples and studies when bounded stochastic noise permits error bounds to converge below the noise level. The stochastic rate depends on how noise is concentrated near the boundary of its noise set.

1. INTRODUCTION

  • Bounded-noise identification uses a consistency set of systems compatible with prior assumptions and measurements, whose geometry determines fundamental performance limits.The approach has a history in robust and worst-case identification, including H∞ system theory and set-membership estimation.Source: §1 · p. 1
  • Prior work spans bounded-noise sample-complexity results, broader convex noise sets, and frequency-domain methods using interpolatory algorithms or repeated noisy measurements.Examples include Zeng et al. (2025), Xu and Li (2025), Chen et al. (1995), and Honarpisheh and Sznaier (2025).Source: §1 · p. 1
  • For equally spaced samples, the consistency-set radius approaches the noise level at the tight rate Θ(N^-2).The paper gives an O(N^-2) upper bound and a matching lower bound.Source: §1 · pp. 1–2
  • Under bounded stochastic noise, high-probability bounds can converge to zero, with rates depending on boundary concentration; uniform disk noise has an upper bound O((log N/N)^(2/3)).A lower bound for uniform disk noise shows that the deterministic quadratic rate need not extend to this setting.Source: §1 · p. 2

2. NOTATION

The notation defines the complex-domain spaces and quantities used to describe transfer functions and sets of transfer functions.

2. NOTATION

  • Dρ denotes the open disk of radius ρ in the complex plane, and H∞,ρ contains transfer functions analytic on Dρ with finite norm.For ρ = 1, the paper writes H∞; for ρ > 1, the norm is the maximum magnitude on the unit circle.Source: §2 · p. 2
  • For a set of transfer functions, the paper defines its diameter and radius; a minimizing center is called a Chebyshev center and need not belong to the set.The cited passages introduce these set quantities and the center terminology.Source: §2 · p. 2

3. PROBLEM FORMULATION

The formulation connects frequency samples, bounded noise, and prior system constraints to consistent identification and its worst-case or high-probability error. It asks how sample number and placement affect accuracy, including whether stochastic bounds can fall below the noise level.

3. PROBLEM FORMULATION

  • Measurements are samples of a fixed SISO LTI system's frequency response plus noise bounded in magnitude by ε.The system belongs to a prior class with exponentially decaying impulse responses; the sample frequencies are distinct and have a defined maximum separation.Source: §3 · p. 2
  • The consistency set contains prior-admissible systems whose sampled responses differ from the measurements by allowed noise, and an interpolatory algorithm returns a member of that set.For real impulse responses, samples on [0, π] can be completed by conjugation; N counts samples on the full unit circle.Source: §3 · p. 2
  • For each measurement vector, the local identification error lies between the consistency-set radius and diameter, with the diameter at most twice the radius.The global worst-case error and the radius and diameter of information are introduced as performance quantities.Source: §3 · p. 2
  • In the stochastic setting, bounded noise is random while the true system is fixed, and a high-probability diameter bound also bounds every consistent algorithm's identification error.The probability is over the noise vector, which is bounded almost surely.Source: §3 · p. 2
  • The objective is to relate frequency-sample number and placement to guaranteed accuracy, bounding worst-case error and stochastic consistency-set diameter.The stochastic analysis asks when bounds can fall below the noise level and how rates depend on the noise distribution and confidence level.Source: §3 · p. 2

4. WORST-CASE IDENTIFICATION BOUNDS

For equally spaced samples, the worst-case consistency-set radius approaches the noise level with a tight Θ(N^-2) excess. The resulting bounds apply to every consistent identification algorithm and also characterize the noiseless and high-noise regimes.

4.1 Consistency sets and identification error

  • The zero-measurement consistency set T(0) reduces the error analysis to bounding the largest H∞ norm compatible with the sampled noise constraints.Its radius is tied to the diameter of information, avoiding a supremum over measurement vectors.Source: §4 · pp. 2–3, §4.1 · p. 3

4.3 Lower bound on r(T (0))

  • For 0<ε<K, equally spaced samples make r(T(0)) approach ε with tight Θ(N^-2) excess.The constructed lower bound matches the upper-bound rate.Source: §4.1 · p. 3, §4.3 · p. 5

4.2 Upper bound on r(T (0))

  • A second-derivative estimate bounds the response increase between samples by a term proportional to Δ^2, yielding an O(N^-2) upper-bound rate on an equally spaced grid.The proof compares a response maximum with a nearby sample; rotating the response makes its real part stationary at the maximum.Source: §4.2 · pp. 3–4

4.3 Lower bound on r(T (0))

  • A finite-impulse-response system with a peak halfway between samples gives the matching lower bound because the nearest samples miss the peak by Θ(N^-2).For zero noise, the bounds give the exact radius on the specified grid.Source: §4.3 · pp. 4–5

4.4 Global identification error

  • The stated inequality is LN ≤ E(A) ≤ 2UN, with LN and UN defined in (28) and (21), respectively.Source: §4.4 · p. 5
  • At ε=0, E(A)=Θ(ρ^-N); for 0<ε<K, ε+Θ(N^-2) ≤ E(A) ≤ 2ε+Θ(N^-2).When ε≥K, the bounds reduce to K ≤ E(A) ≤ 2K, and increasing sample count cannot improve them.Source: §4.4 · p. 5

5. STOCHASTIC IDENTIFICATION BOUNDS

For equally spaced samples, stochastic high-probability diameter bounds can fall below the noise level and converge to zero, with rates tied to noise mass near the boundary. For uniform disk noise, the available lower and upper bounds leave the exact convergence rate unresolved.

5. STOCHASTIC IDENTIFICATION BOUNDS

  • For uniform disk noise, every high-probability diameter bound is at least order N^-1, ruling out o(N^-1) convergence to zero.The deterministic bound approaches 2ε at rate O(N^-2), but that rate cannot generally extend to convergence to zero.Source: §5 · p. 6

5.1 A stochastic upper bound

  • Under Assumption A3, b_N(δ)=min{2U_N, 2V_N(s)} is a high-probability diameter bound for equally spaced samples.The theorem requires independent, circularly symmetric noise at interior sampled frequencies and positive probability of noise magnitudes arbitrarily close to ε.Source: §5.1 · p. 6
  • When q(0)=Prη{|η_n|=ε}>0, the passage specifies choosing s=0, but the supplied excerpt does not state the resulting bound or conclusion.Here q(0) is defined as Prη{|η_n|=ε}.Source: §5.1 · p. 6
  • If q(s)≥c_β(s/ε)^β for β>0, the bound is O((ln(N/δ)/N)^(2/(1+2β))).For uniform disk noise, β=1, giving O((ln(N/δ)/N)^(2/3)).Source: §5.1 · p. 6
  • The stochastic convergence rate depends on how quickly q(s) decreases as s approaches zero, and the uniform-disk bounds do not establish the exact rate.For uniform disk noise, the upper bound is O((ln(N/δ)/N)^(2/3)), while the lower bound is Ω(N^-1).Source: §5.1 · p. 6

6. NUMERICAL EXAMPLES

The experiments examine error decay with more frequency samples and compare noise distributions. The observed curves track the predicted sampling rates, with faster decay for fixed-magnitude noise than for uniform disk noise at larger sample counts.

6.1 Effect of the number of frequency samples

  • With ε=0.70, mean error closely follows the N^-2 reference over N=32–80.The experiment uses 100 independent noise realizations at each sample count.Source: §6.1 · p. 7

6. NUMERICAL EXAMPLES

  • The experiments use a central Nevanlinna–Pick interpolant after correcting measurements to be consistent with the prior and noise bound.The first experiment uses a fourth-order system; the distribution comparison uses a first-order system.Source: §6.1 · p. 7, §6.2 · p. 7

6.2 Effect of the noise distribution

  • For uniform disk noise, error closely follows the N^-2/3 reference; fixed-magnitude noise decays faster and lies closer to N^-2 at larger N.The comparisons use ε=0.50 and omit logarithmic factors from the reference rates.Source: §6.2 · p. 7, Figure 2 · p. 7

7. CONCLUSION

The paper establishes a tight quadratic rate for the worst-case consistency-set radius above the noise level and shows that stochastic bounds can converge below it. Stochastic rates depend on noise concentration near the noise-set boundary.

7. CONCLUSION

  • For zero measurements, the consistency-set radius converges to the noise level at the tight quadratic rate Θ(N^-2).The work improves previous worst-case bounds.Source: §7 · p. 7
  • For bounded stochastic noise, high-probability bounds can decrease below the noise level and converge to zero.Their convergence rate depends on concentration of the noise distribution near the boundary of the noise set.Source: §7 · p. 7
  • Future work will sharpen stochastic bounds to close the upper–lower rate gap and use uncertainty bounds in robust controller design.Source: §7 · p. 7

Appendix A. PROOF OF LEMMA 2

The proof applies Ruscheweyh’s inequality to a normalized analytic function, then differentiates the frequency response to obtain derivative bounds. These bounds support the second-derivative estimate used in the proof.

Appendix A. PROOF OF LEMMA 2

  • Ruscheweyh’s inequality is applied to f(w)=H(ρw)/K at w=z/ρ to obtain derivative bounds.Source: Appendix A · p. 8
  • Differentiating F(θ)=H(e^jθ) gives F′(θ)=jzH′(z) and F′′(θ)=−zH′(z)−z^2H′′(z).Source: Appendix A · p. 8
  • The triangle inequality combines the two derivative bounds to yield inequality (19).Source: Appendix A · p. 8

Appendix B. PROOF OF THEOREM 3

The proof establishes a stochastic lower bound by constructing two constant systems that can remain consistent together, forcing the consistency-set diameter to be large.

Appendix B. PROOF OF THEOREM 3

  • For interior samples, joint consistency requires noise in the lens formed by radius-ε disks centered at a and −a.For uniform disk noise, the lens probability is its area divided by πε²; at real endpoints the event probability is 1 − a/ε.Source: Appendix B · p. 8
  • When both H+ and H− are consistent, the consistency-set diameter is at least 2a.The candidates are the constant systems H±(z) = ±a.Source: Appendix B · p. 8
  • bN(δ) ≥ 2 min{K, εxN(δ)} follows because a smaller bound would be violated with probability greater than δ.The argument lets a vary toward min{K, εxN(δ)} from below.Source: Appendix B · p. 8

Appendix C. PROOF OF THEOREM 4

The proof combines a high-probability search for suitable nearby noise samples with a Taylor bound to control every consistent model's error and the consistency-set diameter.

Appendix C. PROOF OF THEOREM 4

  • With probability at least 1 − δ, every frequency and phase direction has a nearby grid point whose noise is close to the disk boundary and has the required phase.The selected index may depend on the frequency, angle, and direction.Source: Appendix C · p. 8
  • The proof uses this sample to combine a Taylor argument with the noise-boundary and phase conditions, yielding the per-model error bound VN(s).The Taylor argument controls response variation near its maximum; the noise sample is supplied by Lemma 3.Source: Appendix C · pp. 9–10
  • For the consistency set T(y), taking the supremum over H1 and H2 yields diameter d(T(y)) at most min{2UN, 2VN(s)}, combining the stated deterministic and model-distance bounds.Source: Appendix C · p. 10
  • If q(0) > 0, setting s = 0 makes the first term of VN(s) vanish and leaves an O(Λ²/N²) rate.This is the rate stated for part (a).Source: Appendix C · p. 10
Loading 2610.31960v1…