Minimax Lower Bounds for $\mathcal{H}_\infty$-Norm Estimation
This work addresses the efficiency of norm estimation for robust control applications, providing theoretical lower bounds that are incremental to existing knowledge in the field.
The paper tackles the problem of estimating the H-infinity norm of linear time-invariant systems from noisy measurements, proving lower bounds that show norm estimation is no more efficient than model identification for passive sampling and at most a factor of log(r) more efficient for active sampling, with experiments showing a simple non-adaptive estimator is competitive with state-of-the-art adaptive algorithms.
The problem of estimating the $\mathcal{H}_\infty$-norm of an LTI system from noisy input/output measurements has attracted recent attention as an alternative to parameter identification for bounding unmodeled dynamics in robust control. In this paper, we study lower bounds for $\mathcal{H}_\infty$-norm estimation under a query model where at each iteration the algorithm chooses a bounded input signal and receives the response of the chosen signal corrupted by white noise. We prove that when the underlying system is an FIR filter, $\mathcal{H}_\infty$-norm estimation is no more efficient than model identification for passive sampling. For active sampling, we show that norm estimation is at most a factor of $\log{r}$ more sample efficient than model identification, where $r$ is the length of the filter. We complement our theoretical results with experiments which demonstrate that a simple non-adaptive estimator of the norm is competitive with state-of-the-art adaptive norm estimation algorithms.