On Detecting Regularity of Functions: A Probabilistic Analysis

AbstractWe study the problem of detecting the regularity degree deg(ƒ) = max{k: k ≤ r, ƒ ∈ Ck} of functions based on a finite number of function evaluations. Since it is impossible to find deg(ƒ) for any function ƒ, we analyze this problem from a probabilistic perspective. We prove that when the class of considered functions is equipped with a Wiener-type probability measure, one can compute deg(ƒ) exactly with super exponentially small probability of failure. That is, we propose an algorithm which, given n function values at equally spaced points, might propose a value different than deg(ƒ) only with probability O((n−1 ln n)(n − r)/4). Hence, regularity detection is easy in the probabilistic setting even though it is unsolvable in the worst case setting