Random sampling and approximation of signals with bounded derivatives

Abstract Approximation of analog signals from noisy samples is a fundamental, but nevertheless difficult problem. This paper addresses the problem of approximating functions in Hγ,Ω $H_{\gamma , \varOmega }$ from randomly chosen samples, where Hγ,Ω={f∣f is continuous on Ω‾,and ∥Df∥L∞(Ω)≤γ∥f∥L∞(Ω)}. $$ H_{\gamma , \varOmega }= \bigl\{ f \mid f\mbox{ is continuous on } \overline{\varOmega }, \mbox{and } \|D f\|_{L_{\infty }(\varOmega )} \le \gamma \|f\|_{L_{\infty }(\varOmega ) } \bigr\} . $$ We are concerned with the probability that functions in Hγ,Ω $H_{\gamma , \varOmega }$ can be approximated from the noisy samples stably and how they can be approximated. By calculating the upper bound of the covering number of a subset of Hγ,Ω $H_{\gamma , \varOmega }$ and using the uniform law of large numbers, we conclude that functions in Hγ,Ω $H_{\gamma , \varOmega }$ can be recovered stably with overwhelming probability provided that the sampling noise satisfies some mild conditions and the sampling size is sufficiently large. Furthermore, an ℓ∞ $\ell _{\infty }$-regularized least squares model is proposed to approximate functions from noisy samples. The alternating direction method of multipliers (ADMM) algorithm is then applied to solve the model. In the end, numerical experiments are presented and discussed to illustrate the efficiency of our method