Anatoli Juditsky
email: anatoli.juditsky@imag.fr

Arkadi Nemirovski
email: nemirovs@isye.gatech.edu

Nonparametric Denoising of Signals with Unknown Local Structure, I: Oracle Inequalities

Keywords: Nonparametric denoising, oracle inequalities, adaptive filtering

We consider the problem of pointwise estimation of multi-dimensional signals s, from noisy observations (y τ ) on the regular grid Z d . Our focus is on the adaptive estimation in the case when the signal can be well recovered using a (hypothetical) linear filter, which can depend on the unknown signal itself.

The basic setting of the problem we address here can be summarized as follows: suppose that the signal s is "well-filtered", i.e. there exists an adapted time-invariant linear filter q * T with the coefficients which vanish outside the "cube" {0, ..., T } d which recovers s 0 from observations with small mean-squared error. We suppose that we do not know the filter q * , although, we do know that such a filter exists. We give partial answers to the following questions:

-is it possible to construct an adaptive estimator of the value s 0 , which relies upon observations and recovers s 0 with basically the same estimation error as the unknown filter q * T ?

-how rich is the family of well-filtered (in the above sense) signals?

We show that the answer to the first question is affirmative and provide a numerically efficient construction of a nonlinear adaptive filter. Further, we establish a simple calculus of "well-filtered" signals, and show that their family is quite large: it contains, for instance, sampled smooth signals, sampled modulated smooth signals and sampled harmonic functions.

Introduction

In this paper, we focus on the problem of denoising of multi-dimensional signals. Let F = (Ω, Σ, P ) be a probability space. We consider the problem of recovering unknown random field (s τ = s τ (ξ)) τ ∈Z d ξ∈Ω over Z d from noisy observations

y τ = s τ + e τ . (1)
It is convenient for us to assume that both the signal (s τ ) and the noises are complex-valued. Besides this, we assume that the field (e τ ) of observation noises is independent of (s τ ) and is of the form e τ = σǫ τ , where (ǫ τ ) are independent of each other standard Gaussian complex-valued variables; the adjective "standard" means that ℜ(ǫ τ ), ℑ(ǫ τ ) are independent of each other N(0, 1) random variables. Our focus here is at estimating the value s t of signal at a given location t ∈ Z d .

The above problem is "classical" in statistical estimation and signal processing, and as such, has received much attention. In particular, linear estimators (referred as linear filters in the signal processing community) are widely used in the statistical literature. To be more precise, suppose that our aim is to recover the value s 0 of the signal at zero given observations (y τ ) on the box O T = {τ ∈ Z d : |τ j | ≤ T, 1 ≤ j ≤ d}. We call the estimation ŝ of s 0 linear if it is of the form ŝℓ = τ ∈O T q τ y τ for some q ∈ C(O T ), where C(O T ) is the set of complex-valued fields q = {q τ , τ ∈ O T } over O T .

The simplicity of linear estimators is responsible for their popularity in statistical signal processing. Another outstanding feature of such estimators is their minimax property. Suppose that the a priori information resumes to the fact that (s τ ) belongs to some convex compact set which is symmetric with respect to zero, let us call it S. One of the most renown results of estimation theory (see, for instance, [START_REF] Ibragimov | Nonparametric estimation of the value of a linear functional in Gaussian white noise[END_REF][START_REF] Donoho | Renormalization exponents and optimal poinwise rates of convergence[END_REF][START_REF] Donoho | Statistical estimation and optimal recovery[END_REF]) states that the linear minimax estimator is, in a certain sense, an optimal estimator of s 0 in our problem. Indeed, consider the following linear minimax estimation strategy: let q (T ) * be the optimal solution 1 to the problem 1 For evident reasons such a solution exists in the situation we are interested in. (here E s stands for the expectation with respect to the distribution of (y τ ) which corresponds to the underlying signal s). The linear minimax estimator ŝ * ℓ of s 0 is defined by ŝ * ℓ = τ ∈Oτ q (T ) * ,τ y τ .

Then

max s∈S E s (s 0 -ŝ * ℓ ) 2 ≤ C inf ŝ max s∈S E s (s 0 -ŝ) 2 ,
where the infimum in the right-hand side is taken over all possible estimators of s 0 from observations (y τ ) and C is a moderate absolute constant (e.g., C ≤ 1.25). In other words, the linear estimator ŝℓ is a (almost) minimax estimator of s 0 . We would like to stress the exceptional power of the above result -we only need S to be convex and compact for the linear estimator to be minimax optimal. The evident downside of using linear minimax estimators is that the a priori information about the set S of signals should be as precise as possible to achieve descent estimation accuracy. There was a significant research on adaptive estimation in the above setting (cf [START_REF] Cai | Adaptive estimation of linear functionals under different performance measures[END_REF][START_REF] Cai | On adaptive estimation of linear functionals[END_REF]). Those techniques allow to choose the "best" in a certains sense set which contains the signal from special finite families of convex sets. Another "classical" approach to adaptation for linear estimators has been developed in [START_REF] Lepski | On a problem of adaptive estimation in Gaussian white noise[END_REF][START_REF] Lepski | Asymptotically minimax adaptive estimation I: Upper bounds. Optimally adaptive estimates[END_REF][START_REF] Lepski | Asymptotically minimax adaptive estimation. II. Statistical model without optimal adaptation[END_REF][START_REF] Lepski | Optimal pointwise adaptive methods in nonparametric estimation[END_REF][START_REF] Tsybakov | Pointwise and sup norm sharp adaptive estimation of functions on the Sobolev classes[END_REF]. In the latter approach the "form" of the filter q (T ) is considered as given in advance (no information about sets of signals is used in this case), and the parameter T (the "window width") is selected adaptively to achieve the best bias/variance tradeoff. Recently, more general adaptation techniques has been studied in [START_REF] Lepski | Adaptive nonparametric estimation of smooth multivariate functions[END_REF][START_REF] Goldenshluger | Structural adaptation via Lp-norm oracle inequalities[END_REF], which allow to choose the best estimator from special finite families of available linear estimators.

The problem we are interested in here, when posed informally, is as follows: if we consider the form of the filter as a "free parameter", is it possible to provide an estimation procedure which is adaptive with respect to this parameter? In other words, suppose that a "good" filter q the estimation method for which this factor is not too large. Let us consider, for instance, the following question:

(?) Suppose that know that the (deterministic or random) signal (s τ ) τ ∈Z d ≡ (s τ (ξ)) τ ∈Z d ξ∈Ω underlying observations (1) can be recovered from these observations "at a parametric rate" by "linear time-invariant filtering": for a given T , there exists (unknown in advance) filter q (T ) * which recovers s 0 via O(T d ) observations around zero such that

E    |s 0 - τ ∈O T q (T ) * ,τ y τ | 2    ≤ O(σ 2 T -d ). ( 2
)
Can we mimic this filter?

We show that the answer to the question (?) is positive. Namely, whenever a discrete time signal (that is, a signal defined on a regular discrete grid) is well-filtered, i.e., can be recovered from its noisy observations at a parametric rate by a linear time-invariant filter, we can recover this signal at a "nearly parametric" rate without a priori knowledge of the associated filter.

Several points should be stressed in the above claim. First, we are able to mimic only ideal filters q (T ) * of small l 2 -norm. Indeed, the relation (2) implies that the stochastic term of the error

E τ ∈O T q (T ) * ,τ e τ 2 is bounded with O(σ 2 T -d ), which is conceivable only if |q (T ) * | 2 = O(T -d/2
). This constraint is crucial, as the price for adaptation becomes prohibitive when the l 2 -norm of the ideal filter is much larger than O(T -d/2 ). Though this assumption seems quite restrictive, the family of well-filtered signals is quite wide. As we shall see later, this family contains also "highly oscillating" sampled modulated smooth signals, sampled harmonic functions, etc.

In this paper we also treat the problem of adaptive prediction, when we are interested in recovering of a discrete time signal at a point t ∈ Z d via noisy observations taken at the points {τ ∈ Z d : t j -T ≤ τ j ≤ t j -κ} "preceding" the point t, with a given in advance "forecast horizon" κ ≥ 0.

The rest of our paper is organized as follows. In Section 2 we give a formal definition of a well-filtered (well-predicted) signal on a d-dimensional regular grid (the latter, w.l.o.g., is normalized to be Z d ), and then show in Section 3 demonstrate that such a signal can be recovered at a nearly parametric rate without a priori knowledge of the corresponding "good filter" (Theorems 4 and 5). The underlying estimation routines (i.e., "Algorithm A" of Section 3.1 and "Algorithm B" of Section 3.2) constitute a substantial extension of the procedures proposed in [START_REF] Nemirovski | On forecast under uncertainty[END_REF] and [START_REF] Nemirovski | Denoising signals of unknown local structure Medallion Lecturer of IMS[END_REF]. In Section 4.1, we demonstrate that the family of well-filtered signals is pretty wide -it contains a wide spectrum of "basic functions" (for example, exponential polynomials) and is closed with respect to a number of basic operations, including modulation, taking linear combinations and tensor products.

To make the exposition more readable, all proofs are collected in the appendix.

The denoising procedures, described in this paper constitute the basic bricks of the construction of adaptive estimators of locally well-filtered signals, which we describe in the companion paper [START_REF] Juditsky | Nonparametric denoising of signals of unknown local structure, II: nonparametric regression estimation[END_REF]. The results of [START_REF] Juditsky | Nonparametric denoising of signals of unknown local structure, II: nonparametric regression estimation[END_REF] extend to the wide classes of modulated signals the results of [START_REF] Pinsker | Learning algorithm for nonparametric filtering[END_REF][START_REF] Donoho | Wavelet shrinkage: Asymptopia? (with discussion and reply by the authors)[END_REF][START_REF] Juditsky | Wavelet estimators: Adapting to unknown smoothness[END_REF][START_REF] Goldenshluger | On spatially adaptive estimation of nonparametric regression[END_REF] on spatial adaptive estimates of signals with inhomogeneous smoothness.

Problem statement

In order to proceed we need some notations. Fields over Z d . Let C(Z d ) be the linear space of complex-valued fields r = • We call a filter r polynomial, if the corresponding Laurent sum is a polynomial (i.e., if the entries r τ vanish when any of τ j < 0, j = 1, ..., d). The set of all polynomials is denoted P (Z d ). For integers k, T , 0 ≤ k ≤ T , we denote by P k T (Z d ) the subspace of P (Z d ) formed by polynomials r for which the entries r τ vanish outside the set k ≤ τ j ≤ T , j = 1, ..., d.

{r τ : τ ∈ Z d } over Z d . • Given nonnegative integer T and p ∈ [1, ∞], we define semi-norms | • | T,p on C(Z d ) by |r| T,p = |τ |≤T |r τ | p 1/p , |τ | = max{|τ 1 |, ...,
• We denote by ∆ j , j = 1, ..., d, the "basic shift operators" on C(Z d ):

(∆ j r) τ 1 ,...,τ d = r τ 1 ,...,τ j-1 ,τ j -1,τ j+1 ,...,τ d .
Further, we use the notation ∆ -1 j for the inverse of ∆ j :

(∆ -1 j r) τ 1 ,...,τ d = r τ 1 ,...,τ j-1 ,τ j +1,τ j+1 ,...,τ d .

• Finally, we define the output of a filter r, the input to the filter being a field

x ∈ C(Z d ), as the field r(∆)x ≡ r(∆ 1 , ∆ 2 , ..., ∆ d )x, so that (r(∆)x) t = τ r τ x t-τ .
Fourier transform. Let T be a nonnegative integer, let Γ T be the set of roots of 1 of the degree 2T + 1, and let C(Γ d T ) be the space of complex-valued functions on Γ

d T ≡ (Γ T ) d . • We define the Fourier transform F T : C(Z d ) → C(Γ d T ) as (F T r)(µ) = 1 (2T +1) d/2 |τ |≤T r τ µ τ 1 1 ...µ τ d d ≡ 1 (2T +1) d/2 r(µ), r ∈ C T (Z d ), where µ ∈ Γ d T . Note that r τ = 1 (2T +1) d/2 µ∈Γ d T (F T r)(µ)µ -τ 1 1 ...µ -τ d d , ∀(τ : |τ | ≤ T ).
The Fourier transform allows to equip C(Z d ) with semi-norms coming from the standard p-norms on C(Γ d T ):

|r| * T,p = |F T r| p ≡    µ∈Γ d T |(F T r)(µ)| p    1/p
, with the standard interpretation of the right hand side for p = ∞.

Now it is time to give a precise meaning to the basic question (?) of Introduction. In order to do this, we should specify our a priori knowledge of the constant factor hidden in O(•) and on the ranges on values of T and τ where (2) holds true.

Nice signals

Since the observation noises are independent of (s τ ), we have

E |s τ -(q(∆)y) τ | 2 = 2σ 2 |q| 2 2 + E ξ |s τ (ξ) -(q(∆)s(ξ)) τ | 2 ;
(3) therefore in order to ensure (2), both terms in the right hand side of the latter inequality should be of order of T -d . This observation motivates the following

= q (T ) ∈ C T (Z d ), |q| 2 ≤ ρ (2T +1) d/2
, which reproduces (s τ ) in the box {τ : |τ -t| ≤ L} with the mean square error not exceeding θ(2T + 1) -d/2 :

max τ :|τ -t|≤L E |s τ -(q(∆)s) τ | 2 1/2 ≤ θ(2T + 1) -d/2 . ( 4
)
(2) [well-filtered signals] We say that (s τ ) is well-filtered, with the parameters θ, ρ, L, at the point t (we use the notation: (s τ ) ∈ F t L (θ, ρ)), if, for every integer T , 0 ≤ T ≤ L, (s τ ) is T -well-filtered, with the parameters θ, ρ, L, at t.

In the above definition we were focusing on the case of de-noising -recovering a well-filtered signal (s) at a point t ∈ Z d via a given number observations "around" this point. 2 Another interesting problem is that of prediction, where the goal is to recover s t via observations y τ "preceding by a given horizon κ ∈ Z + " the point t, i.e., observations with τ j ≤ t j -κ, j = 1, ..., d.

Definition 2 Let θ ≥ 0, ρ ≥ 1 be reals, let T 0 ≥ κ be nonnegative integers, L be a nonnegative integer or +∞, and let t ∈ Z d . Finally, let (s τ ) τ ∈Z d ≡ (s τ (ξ)) τ ∈Z d ξ∈Ω be a random field on Z d .

(1) [T -well-predicted signals] Let T be a nonnegative integer. We say that (s τ ) is T -well predicted with the parameters θ, ρ, κ, L, at the point t (notation:

(s τ ) ∈ Q t κ,L (θ, ρ, T )), if there exists a filter q = q (T ) ∈ P κ T (Z d ), |q| 2 ≤ ρ (2T +1) d/2
, which reproduces (s τ ) in the box {τ : |τ -t| ≤ L} with the mean square error not exceeding θ(2T + 1) -d/2 :

max τ :|τ -t|≤L E |s τ -(q(∆)s) τ | 2 1/2 ≤ θ(2T + 1) -d/2 . ( 5
)
(2) [well-predicted signals] We say that (s τ ) is well-predicted, with the parameters θ, ρ, κ, T 0 , L, at the point t (notation: (s τ ) ∈ P t κ,T 0 ,L (θ, ρ)), if, for every integer T , T 0 ≤ T ≤ L, (s τ ) is T -well-predicted, with the parameters θ, ρ, κ, L, at t. Remark 3 Note that the quantitative description of a well-predicted field, when compared with the description of a well-filtered field, involves an extra parameter T 0 -the smallest "window width" starting with which a possibility to predict s t is postulated. In the case of well-filtered fields, this width is just 0, in full accordance with the fact that in the de-noising problem every signal is 0-well-filtered, at every point t, with parameters θ = 0, ρ = 1, L = ∞ due to the existence of the trivial "single-point" filter q(z) ≡ 1.

In the sequel, we qualify as nice a signal which fulfils the requirements of Definition 2 or 1 above. The filters q (T ) associated, in the sense of the above definitions, with a nice signal (s τ ) as to filters certifying the "niceness" ("wellfilterability" of "well-predictability") of the signal. We are about to demonstrate that in the framework, suggested by the above definitions, the answer to the question (?) is affirmative.I.e., a signal which is nice (T -well-filtered or T -well-predicted, with parameters θ, ρ, L = 3T ) at a point t can be recovered at this point "at a nearly parametric rate" with no a priori knowledge of the corresponding "good filter"; all we should know in advance are the parameters ρ and T .

Main result

We start the recovering routine for the adaptive filtering problem.

Adaptive filtering

The estimator we intend to use is as follows: Algorithm A: Given a setup (ρ ≥ 1, T ) and a point t ∈ Z d , we build an estimation s t [T, y] of s t via observations (y τ ), |τ -t| ≤ 4T , as follows:

(1) When T = 0, we merely set s t [0, y] = y t (2) When T > 0, we set s t [T, y] = ( φ t (∆)y) t , where φ t ∈ C 2T (Z 2 ) is an optimal solution to the following optimization problem:

min φ∈C 2T (Z d ) |∆ -t 1 1 ...∆ -t d d (1 -φ(∆))y| * 2T,∞ J(φ,y t 4T ) : |φ| * 2T,1 ≤ 2 d/2 ρ 2 (2T + 1) -d/2 , (6)
where y t L = {y τ : |t -τ | ≤ L} .

Note that the objective in ( 6) is affected only by observations y t 4T , so that our algorithm recovers s t via (8T + 1) d observations "around" the point t.

Theorem 4 Assume that the signal (s τ ) underlying observations (1) is Twell-filtered, with parameters θ, ρ, L ≥ 3T : (s τ ) ∈ S t L (θ, ρ, T ) with L ≥ 3T . Then the mean square error of the estimate s t [T, •] of s t yielded by Algorithm A with setup (ρ, T ) can be bounded from above as follows:

E | s t [T, y] -s t | 2 1/2 ≤ c(d)ρ 3 θ + σρ ln(2T + 1) + 1 (2T + 1) d/2 , c(d) = 3(2 d + 2 3d-1 ). ( 7
)
In particular, if (s τ ) is well-filtered, with the parameters θ, ρ, L, at a point t, then for every integer T , 0 ≤ T ≤ ⌊L/3⌋, the accuracy of the estimate s t [T, y] of s t yielded by Algorithm A can be bounded by [START_REF] Cai | On adaptive estimation of linear functionals[END_REF]. Finally, in the case of deterministic (s), we have

|s t -s t [T, y]| ≤ c(d)ρ 3 [θ + σρΘ t T ] (2T + 1) -d/2 , Θ t T = σ -1 max τ :|τ |≤2T |∆ τ 1 -t 1 1 ...∆ τ d -t d d e| * 2T,∞ . (8)
Comments: note that Theorem 4 gives an affirmative answer to the question (?). Indeed, let a signal (s τ ) admit, for some T , a filter-type estimate sτ = (q * (∆)y) τ with "window width" T (i.e., with q * ∈ C T (Z d )) and with the mean square error which, in an O(T )-neighborhood of a point t, is of the "parametric" order O σ(2T + 1) -d/2 : max

τ :|τ -t|≤3T E |s τ -sτ | 2 ≤ κ 2 ≡ σ 2 µ 2 (2T + 1) d/2 (9)
with some known µ ≥ 1. We do not know what is this estimate, although do know that it exists (i.e., know the associated T, µ), and we want to recover s t from observations y t 4T nearly as well as if we were using our hypothetic estimate st . Theorem 4 says that Algorithm A basically achieves this goal. Indeed, from (3), [START_REF] Donoho | Ideal spatial adaptation via wavelet shrinkage[END_REF]

it follows that |q * | 2 ≤ µ (2T +1) d/2 and (s τ ) ∈ S t
3T (σµ, µ, T ). Applying Theorem 4 with ρ = µ, θ = σµ, L = 3T , we conclude that with the estimate yielded by Algorithm A, the mean square error of recovering s t does not exceed O(1)µ 3 1 + ln(2T + 1) κ. We see that as far as the dependence on "observation time" T d is concerned, the estimate yielded by Algorithm A is just by a logarithmic in T factor worse than the estimate st we wish to mimic. In the literature on nonparametric estimation the bounds as in Theorem 4 are often referred to as oracle inequalities. Since the pioneering work [START_REF] Akaike | Information theory and an extension of the maximum likelihood principle[END_REF] a number of oracle inequalities have been established for a wide variety of estimation problems (cf. the papers [19], [START_REF] Barron | Risk bounds for model selection via penalization[END_REF], [START_REF] Birgé | An alternative point of view on Lepski's method[END_REF], [START_REF] Birgé | Gaussian model selection[END_REF], [START_REF] Donoho | Ideal spatial adaptation via wavelet shrinkage[END_REF], [START_REF] Donoho | Wavelet shrinkage: Asymptopia?[END_REF], [START_REF] Cai | Adaptive wavelet estimation: A block thresholding and oracle inequality approach[END_REF] among many others). In that context one refer to the filter q, which certifies the niceness of the signal, as the oracle, and the bound [START_REF] Cai | On adaptive estimation of linear functionals[END_REF] describes the ability of a particular adaptive method (Algorithm A above) to reproduce the oracle.

Note that the "upper bound" of Theorem 4 may be compared to the lower bound of Theorem 2 of [START_REF] Juditsky | Oracle Inequalities for adaptive filtering problem[END_REF] for the 1-dimensional situation. The latter result states that one can exhibit a family of signals which 1) each member of the family can be recovered with the rate O( σρ √ T ) using the corresponding certifying filter; 2) the rate of estimation of signals from the family using the observation (1) is at best O σρ 2 ln T T . In other words, it states that the factor ρ ln(2T + 1) is an unavoidable "price" for adaptation. When comparing the result of Theorem 4 to that lower bound, we observe an extra factor ρ 2 ≥ 1 in the corresponding upper bound [START_REF] Cai | On adaptive estimation of linear functionals[END_REF]. By now we do not know if this extra factor can be completely eliminated. Nevertheless, in light of these results, we can claim that recovering of signals with certifying filter of large l 2 -norm is a rather desperate task -the price for adaptation is then proportional to ρ ≫ 1 in this case.

Adaptive prediction

We now turn to the problem of adaptive prediction. The predictor we intend to use is as follows:

Algorithm B: Given a setup (ρ ≥ 1, κ, T ) and a point t ∈ Z d , we build a prediction s t [κ, T, y] of s t via observations (y τ ), κ ≤ t j -τ j ≤ 4T , j = 1, ..., d, as s t [κ, T, y] = ( ψ t (∆)y) t , where ψ t ∈ P κ 2T (Z 2
) is an optimal solution to the following optimization problem:

min ψ∈C κ 2T (Z d ) |∆ -t 1 1 ...∆ -t d d (1 -ψ(∆))y| * 2T,∞ J(ψ,y t κ,4T ) : |ψ| * 2T,1 ≤ 2 d/2 ρ 2 (2T + 1) d/2 ; (10)
where y t κ,L = {y τ : κ ≤ t j -τ j ≤ L, j = 1, ..., d} . Note that the objective in ( 10) is affected only by observations y t κ,4T , so that our algorithm recovers s t via (4T -κ + 1) d observations "around" the point t.

Theorem 5 Assume that the signal (s τ ) underlying observations (1) is Twell-predicted, with parameters θ, ρ, κ, L ≥ 3T : (s τ ) ∈ Q t κ,L (θ, ρ, T ) with L ≥ 3T . Then the mean square error of the estimate s t [κ, T, •] of s t , provided by Algorithm B with setup (ρ, κ, T ), can be bounded from above as follows:

E | s t [κ, T, y] -s t | 2 1/2 ≤ c(d)ρ 3 θ + σρ ln(2T + 1) + 1 (2T + 1) d/2 , c(d) = 3(2 d + 2 3d-1 ). (11)
In particular, if (s τ ) is well-predicted, with the parameters θ, ρ, κ, T 0 , L, at a point t, then for every integer T , T 0 ≤ T ≤ ⌊L/3⌋, the accuracy of the estimate s t [κ, T, y] of s t yielded by Algorithm B can be bounded by [START_REF] Donoho | Wavelet shrinkage: Asymptopia?[END_REF].

Finally, in the case of deterministic (s), we have

|s t -s t [T, y]| ≤ c(d)ρ 3 [θ + σρΘ t T ] (2T + 1) -d/2 , Θ t T = σ -1 max τ :|τ |≤2T |∆ τ 1 -t 1 1 ...∆ τ d -t d d e| * 2T,∞ . (12)
The proof of Theorem 5 is identical to that of Theorem 4.

Families of nice signals

When applying Algorithms A, B and Theorems 4, 5, the crucial question is how to recognize niceness. We are about to give a partial answer to this question. I. "Scale" of nice signals. We start with the following evident observation:

Calculus of nice signals

ρ ′ ≥ ρ, θ ′ ≥ θ, L ′ ≤ L ⇒ F t L (θ, ρ) ⊂ F t L ′ (θ ′ , ρ ′ ) and ρ ′ ≥ ρ, θ ′ ≥ θ, κ ′ ≤ κ, T ′ 0 ≥ T 0 , L ′ ≤ L ⇒ P t κ,T 0 ,L (θ, ρ) ⊂ P t κ ′ ,T ′ 0 ,L ′ (θ ′ , ρ ′ ). II.
Taking linear combinations. Our next observation is that a linear combination of "good" signals is again good, with properly updated parameters: Proposition 6 (i) Let (s j τ ) ∈ F t L (θ j , ρ j ), and let λ j ∈ C be random variables independent of (s j ) and such that E{|λ j | 2 } < ∞, j = 1, ..., m. Then

(s τ ≡ m j=1 λ j s j τ ) ∈ F t L + (θ + , ρ + ), θ + = (2m -1) d/2 2 m-1 ρ 1 ...ρ m m j=1 θ j [E{|λ j | 2 }] 1/2 ρ j , ρ + = (2m -1) d/2 2 m ρ 1 ...ρ m , L + = ⌊L/2⌋. (13)
In the case of m = 1, one can set

ρ + = ρ 1 , θ + = |λ 1 |θ 1 , L + = L.
The filters certifying the well-filterability of (s τ ) can be chosen to be independent of the coefficients λ j .

(ii) Let (s j τ ) ∈ P t κ j ,T j 0 ,L (θ j , ρ j ), j = 1, ..., m, and let λ j ∈ C be random variable independent of (s j ) and such that E{|λ j | 2 } < ∞, j = 1, ..., m. Then

(s τ ≡ m j=1 λ j s j τ ) ∈ P t κ + ,L + (θ + , ρ + ), θ + = (2m -1) d/2 2 m-1 ρ 1 ...ρ m m j=1 θ j [E{|λ j | 2 }] 1/2 ρ j , ρ + = (2m -1) d/2 2 m ρ 1 ...ρ m , κ + = min 1≤j≤m κ j , T + 0 = m max 1≤j≤m T j 0 , L + = ⌊L/2⌋. (14)
In the case of m = 1, one can set

ρ + = ρ 1 , θ + = |λ 1 |θ 1 , κ + = κ, T + 0 = T 0 , L + = L.
The filters certifying the well-predictability of (s τ ) can be chosen to be independent of the coefficients λ j .

III. Modulation and conjugation. Next we notice that the families of nice signals are closed w.r.t. "modulation" and conjugation:

Proposition 7 (i) Let (s τ ) ∈ F t L (θ, ρ), and let ω ∈ R d , φ ∈ R be determin- istic. Then the signal ( s τ = exp{i[ω T τ + φ]}s τ ) τ ∈Z d belongs to F t L (θ, ρ) along with (s τ ), and the signal (s τ = s τ ) τ (a is the complex conjugate of a ∈ C) belongs to F t L (θ, ρ). (ii) Let (s τ ) ∈ P t κ,T 0 ,L (θ, ρ), and let ω ∈ R d , φ ∈ R be deterministic. Then the signal ( s τ = exp{i[ω T τ + φ]}s τ ) τ ∈Z d also belongs to P t κ,T 0 ,L (θ, ρ)
, and the signal (s τ = s τ ) τ belongs to P t κ,T 0 ,L (θ, ρ).

IV. Lifting. We are about to show that a nice signal in a dimension d ≤ d + can be viewed as a nice signal, with properly updated parameters, in a dimension d + > d:

Proposition 8 (i) Let 1 ≤ d ≤ d +
, and let (s τ ) τ ∈Z d be a signal which is wellfiltered, with parameters θ, ρ, L, at a point t ∈ Z d . Then the signal (s + τ 1 ,...,τ d + = s τ 1 ,...,τ d ) is well-filtered, with the parameters θ + = (2L + 1)

(d + -d)/2 θ, ρ + = ρ, L + = L at every point t + ∈ Z d + such that (t + 1 , ..., t + d ) = t. (ii) Let 1 ≤ d ≤ d + ,
and let (s τ ) τ ∈Z d be a signal which is well-predictable, with parameters θ, ρ, κ, T 0 , L, at a point t ∈ Z d . Then the signal

(s + τ 1 ,...,τ d + = s τ 1 ,...,τ d ) is well-predictable, with the parameters θ + = (2L + 1) (d + -d)/2 θ, ρ + = (2κ + 1) (d + -d)/2 ρ, κ + = κ, T + 0 = T 0 , L + = L, at every point t + ∈ Z d + such that (t + 1 , ..., t + d ) = t. V. "Tensor product". Let d = d ′ + d ′′ with positive integers d ′ , d ′′ , so that Z d = Z d ′ × Z d ′′ . Given random fields (s ′ τ ′ (ξ)) τ ′ ∈Z d ′ ξ , (s ′′ τ ′′ (ξ)) τ ′′ ∈Z d ′′ ξ
, we define their tensor product as the field (s

τ (ξ) = s ′ τ ′ (ξ)s ′′ τ ′′ (ξ)) τ =(τ ′ ,τ ′′ )∈Z d ξ . Proposition 9 (i) Let (s ′ τ ′ (ξ)) τ ′ ∈Z d ′ ξ ∈ F t ′ L (0, ρ ′ ), (s ′′ τ ′′ (ξ)) τ ′′ ∈Z d ′′ ξ ∈ F t ′′ L (0, ρ ′′ ). Then (s τ ) ∈ F (t ′ ,t ′′ ) L (0, ρ ′ ρ ′′ ). (ii) Let (s ′ τ ′ (ξ)) τ ′ ∈Z d ′ ξ ∈ P t ′ κ,T 0 ,L (0, ρ ′ ), (s ′′ τ ′′ (ξ)) τ ′′ ∈Z d ′′ ξ ∈ P t ′′ κ,T 0 ,L (0, ρ ′′ ). Then (s τ ) ∈ P (t ′ ,t ′′ ) κ,T 0 ,L (0, ρ ′ ρ ′′ ).
s τ = M ℓ=1 c ℓ τ α(ℓ) exp{ω T (ℓ)τ }, (15)
where ω(ℓ) and α(ℓ) are deterministic, and c ℓ may be random. Given an exponential polynomial (s τ ) on Z d , we define its partial sizes N j , j = 1, ..., d, as follows: let m j be the maximum of the degrees α j (ℓ), ℓ = 1, ..., M, of the variable τ j in the monomials of the sum [START_REF] Ibragimov | Nonparametric estimation of the value of a linear functional in Gaussian white noise[END_REF], and M j be the number of distinct from each other complex numbers among the "partial frequencies" ω j (ℓ): 15) is, by definition, the integer (m j + 1)M j . For example, with all frequencies equal to 0, an exponential polynomial becomes an algebraic polynomial, and its j-th size is by 1 larger than the degree of the polynomial w.r.t. j-th variable τ j .

M j = Card O j , O j = {ω j (ℓ) : 1 ≤ ℓ ≤ M}. The j-th partial size N j (s) of exponential polynomial (
Proposition 10 Let (s τ ) be an exponential polynomial on Z d of partial sizes N 1 , ..., N d . Then for all t ∈ Z d one has

(s τ ) ∈ F t ∞ (0, ρ d (N 1 , ..., N d )), ρ d (N 1 , ..., N d ) = d j=1 [(2N j -1) 1/2 2 3N j /2 ], (16)
and the filters q (T ) certifying this inclusion can be chosen to be dependent solely on T and on the collection of d sets O j = {ω j (ℓ) : 1 ≤ ℓ ≤ M} of partial frequencies.

Remark 11 A major shortcoming of ( 16) is a dramatic growth of ρ d (N, N, ..., N) with N and d. In several important cases, better bounds for ρ can be found. For example, an algebraic polynomial of degree m in every variable

p τ = α≥0,|α|≤m c α τ α (17)
belongs to F t ∞ (0, (16m) d ) for every t, and the filters q (T ) certifying this inclusion can be chosen to depend solely on T, d, m.

II. Solutions to homogeneous difference equations and harmonic functions.

Consider a difference operator D:

(Df ) τ = k ℓ=1 w ℓ f τ -α(ℓ) ; (18)
here α(1), ..., α(k) ∈ Z d and w 1 , ..., w k ∈ C. For a positive integer N and t ∈ Z d , let

B t N = {τ ∈ Z d | |τ -t| ≤ N}, B t N (D) = {τ ∈ B t N | τ + α(ℓ) ∈ B t N , ℓ = 1, ..., k}, H t N (D) = {(s) ∈ C(Z d ) | s τ = (Ds) τ ∀τ ∈ B t N (D)}.
For example, with

(Df ) τ = 1 2d i=1,...,d ǫ=±1 f τ 1 ,...,τ i-1 ,τ i +ǫ,τ i+1 ,...,τ d , (19)
the linear space H t N (D) is the space of fields which are "discrete harmonic" on

B t N , that is, s τ = 1 2d i=1,...,d ǫ=±1 s τ 1 ,...,τ i-1 ,τ i +ǫ,
k ℓ=1 ρ ℓ ≤ 1; (b) k ℓ=1 ρ ℓ α(ℓ) = 0. ( (a)
) 20
For example, the averaging operator (19) and its degrees are regular. It turns out that the solutions of homogeneous difference equations with regular difference operators are well-filtered:

Proposition 12 Let D be a regular difference operator. Then there exists a constant c = c(D) > 0 such that

∀N > 0 : H t N (D) ⊂ F t ⌊cN ⌋ (0, c -1 ). ( 21
)
As a nontrivial application example for Proposition 12, consider the families of random fields defined as follows. Let d ≤ 4, M be a positive integer, and R be a positive real. Consider the family H + (M) of all deterministic continuous functions f on R d which are harmonic in the interior of the box

D 0 2M = {x ∈ R d : |x j | ≤ 2M, j ≤ d}: d j=1 ∂ 2 ∂x 2 j f (x) = 0, x ∈ intD 0
2M . Now let H + (M, R) be the family of random functions f such that all realizations of a function belong to H + (M) and, besides this, E{ f 2 ∞,2M } ≤ R 2 , where f ∞,2M is the uniform norm on D 0 2M . Restricting functions f from H + (M, R) on Z d , we get a family of random fields H(M, R) on Z d . Proposition 13 Let d ≤ 4, M be a positive integer and R > 0 be a real. For an appropriately chosen absolute constant c > 0, for all deterministic fields

(s τ ) ∈ H(M, R) one has |t| ≤ cM, L ≤ cM ⇒ (s τ ) ∈ F t L (c -1 R, c -1 ), ( 22
)
and the filters q (T ) certifying the above inclusion can be chosen depending solely on d, T .

Basic example of well-predicted signal: quasi-stable exponential polynomial

Let us define a quasi-stable exponential polynomial (s τ ) on Z d as an exponential polynomial

s τ = M ℓ=1 c ℓ τ α(ℓ) exp{ω T (ℓ)τ } (23)
where all partial frequencies ω j (ℓ) satisfy the restriction ℜ(ω j (ℓ)) ≤ 0. For example, an algebraic polynomial (partial frequencies are zero) and a trigonometric polynomial (partial frequencies are imaginary) are quasi-stable.

Proposition 14 Let (s τ ) be a quasi-stable exponential polynomial on Z d of partial sizes N 1 , ..., N d . Then for every integer κ ≥ 0 and all t ∈ Z d one has

(s τ ) ∈ P t κ,T 0 ,∞ (0, ρ κ,d (N 1 , ..., N d )), ρ κ,d (N 1 , ..., N d ) = d j=1 [(2N j -1) 1/2 2 N j (max[2, 2κ + 1]) N j /2 ], T 0 = κ max 1≤j≤d N j (24)
and the filters q (T ) certifying this inclusion can be chosen to be depending solely on T, κ and on the collection of d sets O j = {ω j (ℓ) : 1 ≤ ℓ ≤ M} of partial frequencies.

Appendix

Preliminaries

Norm relations. Let us list several evident relations between the introduced semi-norms on C(Z d ).

• [Parseval equality]: (r, s) T ≡ t:|t|≤T r t s t = µ∈Γ d T (F T r)(µ)(F T s)(µ) ≡ F T r, F T s T , ( 25
)
where a is the complex conjugate of a ∈ C; in particular,

|r| T,2 = |r| * T,2 ; (26)
A useful corollary of Parseval's equality combined with the fact that |q| * T,p = |q| * T,p is the relation

|t|≤T a t b t ≤ |a| * T,1 |b| * T,∞ . (27)
•

• [Relations between | • | and | • | * ]: for p, q ∈ [1, ∞] one has |r| * T,p ≤ (2T + 1) d[(1/p-1/2) + +(1/2-1/q) + ] |r| T,q , a + = max[a, 0]; (29) ord(r) + ord(s) ≤ T ⇒ |r(z 1 , ..., z d )s(z 1 , ..., z d )| * T,p ≤ |r| 1 |s| * T,p . (28)
Useful fact. In the sequel, we need the following simple and well-known fact:

Lemma 15 Let f j = ξ j + iη j , 0 ≤ j < N, be a sequence of N standard Gaussian complex-valued random variables, not necessarily independent of each other. Then

[E{ max 0≤j<N |f j | 2 }] 1/2 ≤ √ 2 ln N + 2; P { max 0≤j<N |f j | > u + √ 2 ln N } ≤ exp{-u 2 /2} ∀u ≥ 0. ( 31
)
Proof. We have

ψ(r) ≡ P { max 0≤j<N |f j | > r} ≤ min[1, N exp{-r 2 /2}] ⇒ P { max 0≤j<N |f j | > u + √ 2 ln N} ≤ N exp{-(u + √ 2 ln N ) 2 /2} ≤ exp{-u 2 /2}; E{ max 0≤j<N |f j | 2 } = - ∞ 0 r 2 dψ(r) = 2 ∞ 0 rψ(r)dr ≤ 2 √ 2 ln N 0 rdr +2N ∞ √ 2 ln N r exp{-r 2 /2}dr = 2 ln N + 2. 2

Proof of Theorem 4

W.l.o.g., we may assume that t = 0. We denote by q * the filter associated with (s τ ) via the description of the inclusion (s τ ) ∈ S 0 3T (θ, ρ, T ). Let us set

|q * | 2 = ρ(2T + 1) -d/2 ; κ = θ(2T + 1) -d/2 [ ρ ≤ ρ] , (32)
so that s = q * (∆)s ⇒ max

τ :|τ |≤3T E{|s τ -sτ | 2 } ≤ κ 2 . (33)
Finally, let

Θ T = max τ :|τ |≤2T |∆ τ 1 1 ...∆ τ d d e| * 2T,∞ , (34)
and let φ be the optimal solution, used in Algorithm A, of the optimization problem (6). 1 0 . We start with simple technical lemma:

Lemma 16 Let r(z 1 , ..., z d ) = (q * (z 1 , ..., z d )) 2 . Then r ∈ C 2T (Z d ) possesses the following properties:

|r| 2 ≤ |r| * 2T,1 ≤ 2 d/2 ρ 2 (2T + 1) -d/2 ; ( 35
)
|r| 1 ≤ ρ 2 ; (36) E{|(1 -r(∆))s| 2 2T,2 } 1/2 ≤ κ( ρ + 1)(4T + 1) d/2 ; (37) |(1 -r(∆))y| * 2T,∞ ≤ |(1 -r(∆))s| 2T,2 + (1 + ρ 2 )Θ T (38) E |(1 -r(∆))y| * 2T,∞ 2 1/2 ≤ σ(1 + ρ 2 ) 4d ln(4T + 1) + 2 +κ( ρ + 1)(4T + 1) d/2 . (39)
(40)

Proof. (35):

We have

|r| * 2T,1 = µ∈Γ d 2T |r(µ)| (4T +1) d/2 = µ∈Γ d 2T |q * (µ)| 2 (4T +1) d/2 = (4T + 1) d/2 µ∈Γ d 2T q * (µ) (4T +1) d/2 2 = (4T + 1) d/2 (|q * | * 2T,2 ) 2 = (4T + 1) d/2 |q * | 2 2T,2 ≤ 2 d/2 ρ 2 (2T + 1) -d/2 . Since |r| 2 = |r| 2T,2 = |r| * 2T,2 ≤ |r| * 2T,1 , (35) follows. (36): We clearly have |r| 1 ≤ |q * | 2 1 ≤ ((2T + 1) d/2 |q * | 2 ) 2 = ρ 2 . ( 37
): Let h = (1 -q * (∆)
)s, so that by virtue of (s τ ) ∈ S 0 (θ, ρ, T ) and in view of the origin of q * we have max

τ :|τ |≤3T E{|h τ | 2 } ≤ κ 2 . ( 41
)
Setting g = (1 -r(∆))s, we have

g τ = ((1 + q * (∆))(1 -q * (∆))s) τ = ((1 + q * (∆))h) τ = h τ + (q * (∆)h) τ ⇒ |g τ | ≤ |h τ | + |q * | 2 |∆ -τ 1 1 ...∆ -τ d d h| T,2 ⇒ (E{|g τ | 2 }) 1/2 ≤ (E{|h τ | 2 }) 1/2 + |q * | 2 τ ′ :|τ ′ -τ |≤T E{|h τ -τ ′ | 2 } 1/2
; applying (41) and taking into account that |q * | 2 = ρ(2T + 1) -d/2 , we come to max

τ :|τ |≤3T E{|((1 -r(∆))s) τ | 2 } ≤ [κ( ρ + 1)] 2 , (42)
and (37) follows.

(38), (39): We have

|(1 -r(∆))y| * 2T,∞ ≤ |(1 -r(∆))s| * 2T,∞ + |(1 -r(∆))e| * 2T,∞ ≤ |(1 -r(∆))s| * 2T,2 + |(1 -r(∆))e| * 2T,∞ = |(1 -r(∆))s| 2T,2 + |(1 -r(∆))e| * 2T,∞ ≤ |(1 -r(∆))s| 2T,2 + |e| * 2T,∞ + τ :|τ |≤2T |r τ ||∆ τ 1 1 ...∆ τ d d e| * 2T,∞ ≤ |(1 -r(∆))s| 2T,2 + (1 + |r| 1 ) max τ :|τ |≤2T |∆ τ 1 1 ...∆ τ d d e| * 2T,∞ .
The resulting inequality combines with (36) to yield (38). Further, from the resulting inequality and (37) it follows that

E |(1 -r(∆))y| * 2T,∞ 2 1/2 ≤ κ( ρ + 1)(4T + 1) d/2 + (1 + |r| 1 ) E max τ :|τ |≤2T |∆ τ 1 1 ...∆ τ d d e| * 2T,∞ 2 Θ 2 T 1/2 ≤ κ( ρ + 1)(4T + 1) d/2 + (1 + ρ 2 ) (E{Θ 2 T }) 1/2
(we have used (36)). To derive (39) from the resulting inequality, it remains to note that

E{Θ 2 T } 1/2 ≤ σ 4d ln(4T + 1) + 2. ( 43
)
Indeed, the coordinates of the Fourier transform of ∆ τ 1 1 ...∆ τ d d e are, up to factor σ, standard complex-valued Gaussian random variables, so that σ -2 Θ 2 T is the maximum of squared modulae of (4T + 1) 2d of these variables; therefore E{Θ 2 T } ≤ σ 2 (4d ln(4T + 1) + 2) by Lemma 15. 2 2 0 . We now study the properties of the solution φ of problem [START_REF] Cai | Adaptive estimation of linear functionals under different performance measures[END_REF].

Lemma 17 One has

| φ| 2T,2 ≤ 2 d/2 ρ 2 (2T + 1) -d/2 ;
(44)

|(1 -φ(∆))e| * 2T,∞ ≤ (1 + 2 d ρ 2 )Θ T ; (45) E |(1 -φ(∆))e| * 2T,∞ 2 1/2
≤ σ(1 + 2 d ρ 2 ) 4d ln(4T + 1) + 2;

(46)

|(1 -φ(∆))s| * 2T,∞ ≤ |(1 -r(∆))s| 2T,2 + 2(1 + 2 d ρ 2 )Θ T ; (47) E |(1 -φ(∆))s| * 2T,∞ 2 1/2 ≤ 2σ(1 + 2 d ρ 2 ) 4d ln(4T + 1) + 2 +κ( ρ + 1)(4T + 1) d/2 . ( 48
) Proof. ( 44
): | φ| 2T,2 = | φ| * 2T,2 ≤ | φ| * 2T,1 ≤ 2 d/2 ρ 2 (2T + 1) -d/2
, (the concluding inequality comes from the fact that φ is feasible for (6)). (45), (46): We have

|(1 -φ(∆))e| * 2T,∞ ≤ (1 + | φ| 2T,1 ) max τ :|τ |≤2T |∆ τ 1 1 ...∆ τ d d e| * 2T,∞ ≤ 1 + (4T + 1) d/2 | φ| 2T,2 max τ :|τ |≤2T |∆ τ 1 1 ...∆ τ d d e| * 2T,∞ ≤ (1 + 2 d ρ 2 ) max τ :|τ |≤2T |∆ τ 1 1 ...∆ τ d d e| * 2T,∞
(we have used (44)). The resulting inequality implies that

E |(1 -φ(∆))e| * 2T,∞ 2 1/2 ≤ (1 + 2 d ρ 2 ) E max τ :|τ |≤2T |∆ τ 1 1 ...∆ τ d d e| * 2T,∞ 2 1/2
≤ (1 + 2 d ρ 2 )σ 4d ln(4T + 1) + 2

(we have used (43)).

(48), (48): Note that the polynomial r defined in Lemma 16 is a feasible solution of the optimization problem ( 6) by the first relation in ( 35), so that the optimal value in the problem does not exceed J(r, y 0 4T ). It follows that

(a) J( φ, y 0 4T ) ≤ J(r, y 0 4T ) ⇒ (b) |(1 -φ(∆))y| * 2T,∞ ≤ |(1 -r(∆))y| * 2T,∞ ⇒ (c) |(1 -φ(∆))s| * 2T,∞ ≤ |(1 -φ(∆))e| * 2T,∞ + |(1 -r(∆))y| * 2T,∞ ⇒ (d) E |(1 -φ(∆))s| * 2T,∞ 2 1/2 ≤ E |(1 -φ(∆))e| * 2T,∞ 2 1/2 + E |(1 -r(∆))y| * 2T,∞ 2 1/2
Relation (47) follows from (c) combined with ( 38) and (45) (recall that ρ ≤ ρ). Relation (48) follows from (d) combined with ( 46) and (39). 2 3 0 . Our next step is to prove Lemma 18 One has

(1 -r(∆))(1 -φ(∆))s 0 ≤ |((1 -r(∆))s) 0 | +2 d/2 ρ 2 (2T + 1) -d/2 |(1 -r(∆))s| 2T,2 ;
(49)

E (1 -r(∆))(1 -φ(∆))s 0 2 1/2 ≤ κ( ρ + 1)(2 d ρ 2 + 1). ( 50
)
Proof. We have

(1 -r(∆))(1 -φ(∆))s 0 ≤ |((1 -r(∆))s) 0 | + φ(∆)(1 -r(∆))s 0 ≤ |((1 -r(∆))s) 0 | + | φ| 2T,2 |(1 -r(∆))s| 2T,2 ≤ |((1 -r(∆))s) 0 | + 2 d/2 ρ 2 (2T + 1) -d/2 |(1 -r(∆))s| 2T,2 [see (44)]
as required in (49). From the resulting inequality it follows that

E (1 -r(∆))(1 -φ(∆))s 0 2 1/2 ≤ E |((1 -r(∆))s) 0 | 2 1/2 +2 d/2 ρ 2 (2T + 1) -d/2 E |(1 -r(∆))s| 2 2T,2 1/2 ≤ κ( ρ + 1) + 2 d/2 ρ 2 (2T + 1) -d/2 E |(1 -r(∆))s| 2 2T,2 1/2 [see (42)] ≤ κ( ρ + 1) + 2 d/2 ρ 2 (2T + 1) -d/2 κ( ρ + 1)(4T + 1) d/2 [see (37)]
and (50) follows. 2 4 0 . Now we are able to complete the proof of Theorem 4. The error of the estimate s at the point t = 0 is

s 0 -s 0 = s 0 -( φ(∆)y) 0 = (1 -φ(∆))s 0 -φ(∆)e 0 ≡ ǫ (1) 0 + ǫ (2) 0 , ǫ (1) τ = (1 -φ(∆))s τ , ǫ (2) τ = φ(∆)e τ . ( 51
)
Setting f τ = e -τ , we have

|ǫ (2) 0 | = τ :|τ |≤2T φ τ e -τ ≤ | φ| * 2T,1 |f | * 2T,∞ [see (27)] ≤ 2 d/2 ρ 2 (2T + 1) -d/2 |f | * 2T,∞ , [since φ is feasible for (6)]
whence, by definition of Θ T ,

|ǫ (2) 0 | ≤ 2 d/2 ρ 2 (2T + 1) -d/2 Θ T . (52)
Applying (43), we derive from the latter inequality that

E |ǫ (2) 0 | 2 1/2 ≤ 2 d/2 σρ 2 (2T + 1) -d/2 2d ln(4T + 1) + 2. ( 53
)
We further have

|ǫ (1) 0 | = (1 -φ(∆))s 0 ≤ r(∆)(1 -φ(∆))s 0 + (1 -r(∆))(1 -φ(∆))s 0 ≤ a |r| * 2T,1 |(1 -φ(∆))s| * 2T,∞ + (1 -r(∆))(1 -φ(∆))s 0 ≤ b 2 d/2 ρ 2 (2T + 1) -d/2 |(1 -φ(∆))s| * 2T,∞ + (1 -r(∆))(1 -φ(∆))s 0 ( 54
)
(the inequality a is given by ( 27), and b follows from the feasibility of φ for ( 6)), whence

E |ǫ (1) 0 | 2 1/2 ≤ 2 d/2 ρ 2 (2T + 1) -d/2 E (1 -φ(∆))s * 2T,∞ 2 1/2 + E (1 -r(∆)(1 -φ(∆))s 0 2 1/2 ≤ 2 d/2 ρ 2 (2T + 1) -d/2 2 d σ(1 + 2 d ρ 2 ) 4d ln(4T + 1) + 2 +κ( ρ + 1)(4T + 1) d/2 + κ( ρ + 1)(2 d ρ 2 + 1) (55)
(see ( 48), ( 50)). Combining ( 51), ( 53), ( 55), we finally get

E |s 0 -s 0 | 2 1/2 ≤ 2 d/2 σρ 2 (2T + 1) -d/2 2d ln(4T + 1) + 2 +2 d/2 ρ 2 (2T + 1) -d/2 2 d σ(1 + 2 d ρ 2 ) 4d ln(4T + 1) + 2 +κ( ρ + 1)(4T + 1) d/2 + κ( ρ + 1)(2 d ρ 2 + 1). ( 56
)
Recalling that ρ ≤ ρ, κ = θ(2T + 1) -d/2 and that ρ ≥ 1, ( 7) follows. Now assume that (s) is deterministic. In this case, from (54) combined with (47) and ( 49) implies that

|ǫ (1) 0 | ≤ 2 1+d/2 ρ 2 (2T + 1) -d/2 |(1 -r(∆))s| 2T,2 +2 1+d/2 ρ 2 (1 + 2 d ρ 2 )(2T + 1) -d/2 Θ T + |((1 -r(∆))s) 0 | , (57)
while from (37), (42) it follows that

|(1 -r(∆))s| 2T,2 ≤ κ( ρ + 1)(4T + 1) d/2 ≤ 2 d/2 θ(1 + ρ), |((1 -r(∆))s) 0 | ≤ κ(1 + ρ) ≤ θ(1 + ρ)(2T + 1) -d/2 . (58) Therefore (57) implies that |ǫ (1) 0 | ≤ 3 3+d ρ 3 [θ + ρΘ T ] (2T + 1) -d/2 . ( 59
)
Combining this relation with ( 52) and (51), we arrive at (8). 2

Proof of Proposition 6

In the proofs to follow, we focus on the case of well-filtered signals; the reasoning in the case of well-predicted signals is completely similar.

The case of m = 1 is evident. Now let m ≥ 2, let T + be an integer, 0 ≤ T + ≤ L + , and let T = ⌊m -1 T + ⌋. Since s j ∈ F t L (θ, ρ) and clearly T ≤ L, there exist filters q j such that (a) : ord(q j ) ≤ T ; (b) :

|q j | 2 ≤ ρ j (2T + 1) -d/2 ; (c) : |q j | 1 = |q j | T,1 ≤ (2T + 1) d/2 |q j | 2 ≤ ρ j ; (d) : [E {|s j τ -(q j (∆)s j ) τ | 2 }] 1/2 ≤ θ j (2T + 1) -d/2 ∀(τ : |τ -t| ≤ L). ( 60
)
Now let filter q be defined by

1 -q(z) = m j=1
(1 -q j (z)), z = (z 1 , ..., z d ).

Observe that

ord(q) ≤ mT ≤ T + . ( 61
)
Note that

|q| 2 ≤ 2 m ρ 1 ...ρ m (2T + 1) -d/2 ≤ (2m -1) d/2 2 m ρ 1 ...ρ m (2T + + 1) -d/2 . ( 62
)
Indeed, we clearly have

|q(z)| 2 = m ℓ=1 (-1) ℓ+1 1≤j 1 <j 2 <...<j ℓ ≤m q j 1 (z)q j 2 (z)...q j ℓ (z) 2 ≤ m ℓ=1 1≤j 1 <j 2 <...<j ℓ ≤m |q j 1 (z)q j 2 (z)...q j ℓ (z)| 2 ≤ a m ℓ=1 1≤j 1 <j 2 <...<j ℓ ≤m ρ j 1 ρ j 2 ...ρ j ℓ (2T +1) d/2 ≤ [(1 + ρ 1 )...(1 + ρ m ) -1](2T + 1) -d/2 ≤ b 2 m ρ 1 ...ρ m (2T + 1) -d/2 (a is by (60.b -c) since |u(z)v(z)| 2 ≤ |u| 1 |v| 2 , |u(z)v(z)| 1 ≤ |u| 1 |v| 1 ], b is due to ρ j ≥ 1)
, as required in (62). Further, by (60.c), for the filters

Q j (z) =   j-1 ℓ=1 (1 -q ℓ (z))     m ℓ=j+1 (1 -q ℓ (z))   one has |Q j | 1 ≤ (1 + ρ 1 )...(1 + ρ j-1 )(1 + ρ j+1 )...(1 + ρ m ) ≤ 2 m-1 ρ 1 ...ρ m ρ j . (63)
Now let τ ∈ Z d be such that |τ -t| ≤ L + . We have

E |(1 -q(∆))s) τ | 2 1/2 =   E      m j=1 λ j 1 -q(∆))s j τ 2         1/2 ≤ m j=1 E λ j 1 -q(∆))s j τ 2 1/2 = a m j=1 [E{|λ j | 2 }] 1/2 E 1 -q(∆))s j τ 2 1/2 ≤ m j=1 [E{|λ j | 2 }] 1/2 E Q j (∆)(1 -q j (∆))s j τ 2 1/2 ≤ b m j=1 [E{|λ j | 2 }] 1/2 |Q j | 1 max τ ′ :|τ ′ -τ |≤(m-1)T E (1 -q j (∆))s j τ ′ 2 1/2 ≤ 2 m-1 ρ 1 ...ρ m (2T 1) -d/2 m j=1 θ j [E{|λ j | 2 }] 1/2 ρ j ≤   (2m -1) d/2 2 m-1 ρ 1 ...ρ m m j=1 θ j [E{|λ j | 2 }] 1/2 ρ j   (2T + + 1) -d/2
where a is due to independence of λ j and (s j ) and b follows from (63), (60.d), and since

|τ ′ -τ | ≤ (m -1)T, |τ -t| ≤ L + ⇒ |τ ′ -t| ≤ L + + T + ≤ L.
Combining the resulting inequality, (61), (62) and taking into account that T + ∈ {0, 1, ..., L + } is arbitrary, we conclude that s ∈ F t L + (θ + , ρ + ). Note that by construction, the filters certifying the latter inclusion are independent of λ j . 2

Proof of Proposition 7

(i): Let T ≤ L, and let q be such that

ord(q) ≤ T, |q| 2 ≤ ρ (2T +1) d/2 , max τ :|τ -t|≤L E |((1 -q(∆))s) τ | 2 1/2 ≤ θ (2T +1) d/2 . (64) Let us set q τ = exp{iω T τ }q τ , τ ∈ Z d . Then ord( q) ≤ T , | q| 2 = |q| 2 and ((1 -q(∆)) s) τ = exp{i[ω T τ + φ]}s τ - τ ′ (exp{iω T τ ′ }q τ ′ )(exp{i[ω T (τ -τ ′ ) + φ]}s τ -τ ′ ) = exp{i[ω T τ + φ]} ((1 -q(∆))s) τ ,
so that (64) remains valid when q, (s) are replaced with q, ( s). Thus, ( s) ∈ F t L (θ, ρ). (i) is proved; (ii) is evident. 2

Proof of Proposition 8

Let T ≤ L, and let q = (q τ ) τ ∈Z d be such that ord(q) ≤ T ,

|q| 2 ≤ ρ(2T + 1) -d/2 , E |((1 -q(∆))s) τ | 2 1/2 ≤ θ(2T + 1) -d/2 ∀(τ ∈ Z d : |τ -t| ≤ L). Setting q + τ 1 ,...,τ d + = (2T +1) -(d + -d) q τ 1 ,...,τ d , we clearly have ord(q + ) ≤ T , |q + | 2 ≤ ρ(2T + 1) -d + /2 and E (1 -q + (∆))s + τ 2 1/2 ≤ θ(2T + 1) -d/2 ∀(τ ∈ Z d + : |τ -t + | ≤ L).
It remains to note that θ(2T + 1) -d/2 ≤ θ + (2T + 1) -d + /2 for 0 ≤ T ≤ L. 2

Proof of Proposition 9

Let T ≤ L, and let

q ′ ∈ C T (Z d ′ ), q ′′ ∈ C T (Z d ′′ ) be such that (a) : |q ′ | 2 ≤ ρ ′ (2T + 1) -d ′ /2 , |q ′′ | 2 ≤ ρ ′′ (2T + 1) -d ′′ /2 , s ′ τ ′ (ξ) = ν ′ s ′ τ ′ -ν ′ q ′ ν ′ , |τ ′ -t ′ | ≤ L, s ′′ τ ′′ (ξ) = ν ′′ s ′′ τ ′′ -ν ′′ q ′′ ν ′′ , |τ ′′ -t ′′ | ≤ L . ( 65
) Let q(z 1 , ..., z d ) = q ′ (z 1 , ..., z d ′ )q ′′ (z d ′ +1 , ..., z d ), so that q ∈ C T (Z d ), |q| 2 = |q ′ | 2 |q ′′ | 2 ≤ ρ ′ ρ ′′ (2T + 1) -d/2 (66) (see (65.a)). Now let τ = (τ ′ , τ ′′ ) be such that |τ -(t ′ , t ′′ )| ≤ L. We have (q(∆)s(ξ)) τ = (ν ′ ,ν ′′ )∈Z d ′ ×Z d ′′ s ′ τ ′ -ν ′ (ξ)s ′′ τ ′′ -ν ′′ (ξ)q ′ ν ′ q ′′ ν ′′ = ν ′ ∈Z d ′ s ′ τ ′ -ν ′ q ′ ν ′ s ′′ τ ′′ (ξ) = s ′ τ ′ (ξ)s ′′ τ ′′ (ξ) = s (τ ′ ,τ ′′ ) ,
which combines with (66) to yield that (s τ ) ∈ F (t ′ ,t ′′ ) L (0, ρ ′ ρ ′′ ). 2

Proof of Proposition 10

We start with the following two evident facts:

Lemma 19 Let (s j ) ∈ C(Z d ) be deterministic fields belonging to F t L (θ, ρ), j = 1, 2, ... such that s j τ → s τ , j → ∞, for every τ ∈ Z d . Then (s) ∈ F t L (θ, ρ).
Indeed, for every T , 0 ≤ T ≤ L, the filters q j,T ∈ C T (Z d ) which certify the inclusions (s j ) ∈ F t L (θ, ρ) satisfy |q j,T | 2 ≤ ρ(2T + 1) -d/2 and therefore have a limiting point

q T ∈ C T (Z d ) with |q j | 2 ≤ ρ(2T + 1) -d/2 . The filters {q T } 0≤T ≤L clearly certify the inclusion (s) ∈ F t L (θ, ρ). 2
Lemma 20 For every t ∈ Z, the univariate exponential field

(s τ = exp{ωτ }), ω ∈ C, belongs to F t ∞ (0, √ 2).
Indeed, assuming ℜ(ω) ≥ 0 and given T ≥ 0, let us set q(z)

= 1 T +1 [1 + exp{-ω}z -1 + exp{-2ω}z -2 + ... + exp{-T ω}z -T ]. Then q ∈ C T (Z), |q| 2 = (T +1) -1/2 ≤ 2 1/2 (2T +1) -1/2 ,
while clearly q(∆)s ≡ s. In the case of ℜ(ω) < 0, the same reasoning holds true for q(z)

= 1 T +1 [1 + exp{ω}z + exp{2ω}z 2 + ... + exp{T ω}z T ]. 2
To complete the proof, we need the following fact: Lemma 21 Let (s τ ) be a "simple" exponential polynomial -a deterministic exponential polynomial of the form

(s τ ) = M ℓ=1 c ℓ exp{ω T (ℓ)τ }. Then ∀t ∈ Z d : (s τ ) ∈ F t ∞ (0, ρ d (N 1 , ..., N d )), (67)
where ρ d (•, ..., •) is given by ( 16) and N 1 , ..., N d are the partial sizes of the polynomial. Besides this, the filters q (T ) certifying the above inclusion can be chosen to depend solely on T and on the collection of the d sets O j = {ω j (ℓ) : ℓ = 1, ..., M}.

Lemma 21 ⇒ Proposition 10: Assume first that the coefficients c ℓ in (15) are deterministic. Since every one of the univariate functions

f (t) = t k , 0 ≤ k ≤ m,
is, uniformly on compact sets, the limit, as ǫ → +0, of appropriate linear combinations of the m + 1 exponents exp{-kǫ}, the exponential polynomial [START_REF] Ibragimov | Nonparametric estimation of the value of a linear functional in Gaussian white noise[END_REF] is the pointwise, on Z d , limit, as i → ∞, of simple exponential polynomials (s i τ ) with extended sets of "frequencies" {ω j (ℓ)} j,ℓ : in the approximating polynomials, every one of these frequencies is replaced by (m j + 1) frequencies ω j (ℓ) -kǫ i , 0 ≤ k ≤ m j . Note that by the definition of partial sizes of exponential polynomials, the approximating polynomials have exactly the same partial sizes as the original polynomial (s τ ). Combining Lemmas 21 and (19), we immediately conclude that the exponential polynomial [START_REF] Ibragimov | Nonparametric estimation of the value of a linear functional in Gaussian white noise[END_REF] belongs to F t ∞ (0, ρ d (N 1 , ..., N d )). Since the filters q (T ),i certifying well-filterability of the approximating polynomials (s i τ ) can be chosen to depend solely on T and the sets of partial frequencies of these approximating polynomials, from the proof of Lemma 19 it follows that the filters q (T ) certifying the inclusion (s τ ) ∈ F t ∞ (0, ρ d (N 1 , ..., N d )) can be chosen to depend solely on T and the sets of partial frequencies of (s τ ), as required in Proposition 10. We have proved Proposition 10 for the case of a deterministic exponential polynomial; since the filters certifying well-filterability of such a polynomial are independent of the coefficients c ℓ , the result is valid for random polynomials as well. 2 Proof of Lemma 21. Proof is by induction in d. Base d = 1 is readily given by Lemma 20 combined with Proposition 6.

Step 1 ≤ d ⇒ d + 1: Let s τ = ℓ c ℓ exp{ω T (ℓ)τ } be a simple exponential polynomial on Z d+1 with partial sizes N j and the sets of partial frequencies O j , j = 1, ..., N. Let T ≥ 0, and let t ∈ Z d+1 . By the inductive hypothesis, there exist filters g (T ) ∈ C T (Z d ), h (T ) ∈ C T (Z) (depending solely on T and on O 1 ,...,O d+1 ) such that (a) :

|g (T ) | 2 ≤ ρ d (N 1 , ..., N d )(2T + 1) -d/2 , (a ′ ) : |h (T ) | 2 ≤ ρ 1 (N d+1 )(2T + 1) -1/2 , (b) : r τ = ν∈Z d r τ -ν g (T ) ν ∀τ ∈ Z d ∀(r τ ) ∈ E(O 1 , ..., O d ), (b ′ ) : p τ = ν∈Z p τ -ν h (T ) ν ∀τ ∈ Z ∀(p τ ) ∈ E(O d+1 ), (68)
where E(O 1 , ..., O m ) is the space of all simple exponential polynomials on Z m with the sets of partial frequencies O 1 , ..., O m . Setting q (T ) τ = g (T ) τ 1 ,...,τ d h (T ) τ d+1 , τ ∈ Z d+1 , we clearly have

q (T ) ∈ C T (Z d+1 ), |q (T ) | 2 = |g (T ) | 2 |h (T ) | 2 ≤ ρ d (N 1 , ..., N d )ρ 1 (N d+1 ) = ρ d+1 (N 1 , ..., N d+1 ) (69) (see (68.a, a ′ ). Further, for every (s τ ) ∈ E(O 1 , ..., O d+1 ) we have, setting τ = (τ ′ , τ ′′ ) with τ ′ ∈ Z d , τ ′′ ∈ Z: ν∈Z d+1 q (T ) ν s τ -ν = ν ′ ∈Z d g (T ) ν ′ ν ′′ ∈Z h (T ) ν ′′ s τ ′ -ν ′ ,τ ′′ -ν ′′ = a ν ′ ∈Z d g (T ) ν ′ s τ ′ -ν ′ ,τ ′′ = b s τ ′ ,τ ′′ (a is by (68.b ′ ) since (s τ ′ -ν ′ ,µ ) µ∈Z ∈ E(O d+1 ), b is by (68.b) since (s µ,τ ′′ ) µ∈Z d ∈ E(O 1 , ..., O d ))
, which combines with (69) to imply that (s τ ) ∈ S t ∞ (0, ρ d+1 (N 1 , ..., N d+1 ), T ).

Thus, the filters q (T ) (which depend solely on T and O 1 ,...,O d+1 ) certify the inclusion (s τ ) ∈ L t ∞ (0, ρ d+1 (N 1 , ..., N d+1 ). The inductive step is completed. 2

Proof of statement in Remark 11

It suffices to prove that for every nonnegative integer T and every m, d there exists a filter q (T ) , ord(q (T ) ) ≤ T , depending solely on T, m, d, such that (a) q (T ) (∆)p = p for every polynomial [START_REF] Juditsky | Oracle Inequalities for adaptive filtering problem[END_REF],

(b) |q (T ) | 2 ≤ 16m √ 2T +1 d ≡ Θ d . ( 70
)
This well-known fact can be proved by induction in d completely similar to the one used to prove Lemma 21; the only difference is in the Base, which now should be replaced with the following statement:

Lemma 22 Let p(τ ) = m ℓ=0
p ℓ τ ℓ be a deterministic univariate algebraic polynomial of degree m. Then for every T ≥ 0 there exists a filter q ∈ C T (Z), depending solely on T, m, with |q| 2 ≤ 16m(2T + 1) -1/2 such that p(t) = ν q (T ) ν p(t -ν) for all t ∈ Z.

Proof. By evident reasons, it suffices to prove that for a given T ≥ 0 there exists a collection of weights q t , -T ≤ t ≤ T , such that

T t=-T q t = 1, T t=-T q t t i = 0, i = 1, ..., m, T t=-T q 2 t ≤ Θ 2 ≡ 256m 2 2T + 1 .
By the standard separation arguments, this is the same as to prove that for every real algebraic polynomial r(t) of degree ≤ m such that r(0) = 1 one has T t=-T r 2 (t) ≥ 2T +1 256m 2 , or, which is the same, that for the real trigonometric polynomial ρ(φ) = r(T sin(φ)) one has Lemma 24 There exists c 2 ∈ (0, 1) such that

M ⊂ M = ζ | |ζ| ≤ 1, |ℑ(ζ)| ≤ c -1 2 (1 -ℜ(ζ)) 3/2 , (74)
F (α) ≤ c -1 2 [α d/2 + N -d ], 0 ≤ α ≤ 2. ( 75
)
Proof. (74), (75) are evident when

k ℓ=1 ρ ℓ < 1, since then |δ(ω)| ≤ 1 -c 2 for
properly chosen c 2 and all ω. Thus, in the sequel we focus on the case of

k ℓ=1 ρ ℓ = 1 (recall that k ℓ=1 ρ ℓ ≤ 1 by R.2). 2 0 .1) Let K = {ω ∈ [-π, π] d : δ(ω) = 1}. Since ρ ℓ > 0, ℓ ρ ℓ = 1 and δ(ω) = ℓ ρ ℓ exp{iφ ℓ + ω α(ℓ)}, a point ω ∈ K must satisfy the equations exp{i[φ ℓ + ω T α(ℓ)]} = 1 ∀(1 ≤ ℓ ≤ k), (76)
whence

φ ℓ + ω T α(ℓ) ∈ 2πZ ∀(1 ≤ ℓ ≤ k). Since Rank{α(ℓ) : 1 ≤ ℓ ≤ k} = d,
δ(ω + dω) = k ℓ=1 ρ ℓ exp{i[φ ℓ + ω T α(ℓ)]} exp{i(dω) T α(ℓ)} = a k ℓ=1 ρ ℓ exp{i(dω) T α(ℓ)} ⇒ |δ(ω + dω)| = k ℓ=1 ρ ℓ exp{i(dω) T α(ℓ)} ≤ b k ℓ=1 ρ ℓ 1 + i(dω) T α(ℓ) -1 2 (dω) T α(ℓ) 2 + c 4 |dω| 3 = b k ℓ=1 ρ ℓ 1 -1 2 (dω) T α(ℓ) 2 + c 4 |dω| 3 ≤ c 1 -c 5 |dω| 2 + c 4 |dω| 3 (for a, see (76), b is by (20.b), c is due to Rank ({α(ℓ)} ℓ ) = d).
It follows that with properly chosen c 6 one has

∀(ω ∈ [-π, π] d , |δ(ω) -1| ≤ α) ∃ω ∈ K : |ω -ω| ≤ c -1 6 √ α. (77)
Since Card (K) ≤ c 3 by 2 0 .1) and |δ(ω)| ≤ 1 for all ω, we conclude that

ν {ω ∈ Ω d N : |δ(ω) -1| ≤ α} ≤ c 7 [α d/2 + N -d ] ∀α ≤ 2. ( 78
)
2 0 .3) Now we can complete the proof of (74), (75). Let ω ∈ K, dω ∈ R d , |dω| ≤ 1. We have

δ(ω + dω) = k ℓ=1 ρ ℓ exp{i[φ ℓ + ωT α(ℓ)]} exp{i(dω) T α(ℓ)} = a k ℓ=1 ρ ℓ exp{i(dω) T α(ℓ)} = k ℓ=1 ρ ℓ 1 + i(dω) T α(ℓ) -1 2 (dω) T α(ℓ) 2 -i 6 (dω) T α(ℓ) 3 + r ℓ (ω, dω) [|r ℓ (ω, dω)| ≤ c 10 |dω| 4 ] = b k ℓ=1 ρ ℓ 1 -1 2 (dω) T α(ℓ) 2 -i 6 (dω) T α(ℓ) 3 + r ℓ (ω, dω) (79)
(for a, see (76), for b, see ( 20)). Taking into account that ), so that (75) follows from (78). 2 3 0 . Let n be a positive integer, and let T n (ζ) be the Tschebyshev polynomial of degree n. Recall that this polynomial is defined as follows:

T n (ζ) = w n + w -n 2 , where w = ζ + i √ 1 -ζ 2 . ( 80
p n (α) ≡ max ζ {|P n (ζ)| : ζ ∈ M, ℜ(ζ) = 1 -α} ≤ q n (α) = c 15 , 0 ≤ α ≤ 1 n 2 c 15 (1+c 15 α) n n 2 α , 1 n 2 ≤ α ≤ 2 . (81) Proof. Let ζ = 1 -α + iβ ∈ M, so that |β| ≤ c 16 α 3/2 . ( 82
)
We have

w ≡ ζ + i √ 1 -ζ 2 = 1 -α + iβ + i 2α -α 2 -2i(1 -α)β + β 2 = 1 -α + iβ + i √ 2α 1 -0.5α + [0.5β -i(1 -α)](β/α) = 1 + i √ 2α + r 1 (ζ), |r 1 (ζ)| ≤ c 17 α (83)
(since |β/α| ≤ c 16 √ α by ( 83)). Note that completely similar considerations demonstrate that

w -1 = ζ -i 1 -ζ 2 = 1 -i √ 2α + r 2 (ζ), |r 2 (ζ)| ≤ c 17 α. (84)
3 0 .1) Assume, first, that 0 ≤ α ≤ 1 n 2 . In this case from (83) it follows that |1 -w| ≤ √ 2n -1 , whence, taking into account (83),

|w n -(1 + n(w -1) + n(n-1) 2 (w -1) 2 )| ≤ c 17 (n|w -1|) 3 ≤ c 18 n 3 α 3/2 , |w -n -(1 -n(w -1) + n(n+1) 2 (w -1) 2 )| ≤ c 17 (n|w -1|) 3 ≤ c 18 n 3 α 3/2 ⇒ w n +w -n 2 -1 ≤ n 2 2 |w -1| 2 + c 18 n 3 α 3/2 ≤ c 19 (n 2 α + n 3 α 3/2 ) ≤ c 20 n 2 α. Thus, one has |P n (ζ)| = w n +w -n 2 -1 n 2 |α-iβ| ≤ c 15 , as required in (81) for the case of 0 ≤ α ≤ 1 n 2 . 3 0 .2) Now consider the case of 1 n 2 ≤ α ≤ 2. From (83), (84) it follows that |w| ≤ 1 + c 21 α, |w -1 | ≤ 1 + c 21 α, whence |P n (ζ)| = w n +w -n 2 -1 n 2 |α-iβ| ≤ c 22 (1+c 21 α) n n 2 α , as required in (81). 2 4 0 . Let Q(ζ) = 1+ζ 2 . It is immediately seen that ζ = 1 -α + iβ ∈ M ⇒ |Q(ζ)| ≤ 1 -c 23 α [c 23 < 1 2 ]. (85)
Now let c 24 be a positive integer which is ≥

(P n ) ≤ n). To verify (86.c), note that if ζ = 1 -α + iβ ∈ M, then in view of (81) one has 0 ≤ α ≤ 1 n 2 ⇒ |S n (ζ)| ≤ |P n (ζ)||Q(ζ)| c 24 n ≤ |P n (ζ)| ≤ c 15 ; 1 n 2 ≤ α ≤ 2 ⇒ |S n (ζ)| ≤ |P n (ζ)||Q(ζ)| c 24 n ≤ a c 15 (1+c 15 α) n n 2 α (1 -c 23 α) c 24 n ≤ c 15
Consider the filters q (n) (z) given by q (n) (∆) = R n (D), n = 0, 1, ... By (87.b) and Lemma 23 we have

T ≤ c 27 N 1 ≤ n(T ) ≡ ⌊c 27 T ⌋ (s) ∈ H t N (D)              ⇒     
ord(q (n(T )) ) ≤ T, s τ = (q (n(T )) (∆)s) τ ∀(τ : |τ -t| ≤ c 27 N).

(indeed, one can choose, as a required q (T ) , the filter q (n(T )) ). Setting q (T ) (z) ≡ 1 for T < 1 c 27 , we enforce the validity of (93) for all T , 0 ≤ T ≤ L. Thus, H t N (D) ⊂ F t ⌊c 29 L⌋ (0, c 34 ). (from now on, c i are positive absolute constants).

Proof. First, we should prove that the "discrete harmonic" function φ on B t N which coincides with f on ∂B t N does exist. This fact is well known; we present here its proof just for the sake of completeness. Let ψ be a function on ∂B t N . Consider the following random walk on B t N : arriving for the first time at a point τ from ∂B t N , we pay penalty ψ(τ ) and terminate; from an "interior point" τ ∈ intB t N ≡ B t N \∂B t N we make a random step of length 1 along one of the coordinate axes, choosing every one of 2d possible steps with probability 1/(2d). It is immediately seen that the expected penalty payed at the termination, treated as a function of the initial state, is a discrete harmonic function with the boundary values ψ. Now, since |t| ≤ N and 2N ≤ M, the function f is harmonic in the "continuous box" D t 2N = {τ ∈ R d : |τ -t| ≤ 2N}, and the uniform norm of f in this square does not exceed f ∞,2M . From the standard results on harmonic functions it follows that ∀(τ ∈ D t N ) : Since f is harmonic, we conclude that

∂ κ ∂x κ j f (τ ) ≤ c 2 f ∞,2M N -κ , κ = 1,
|(Df ) τ | ≤ c 4 f ∞,2M N -4 , τ ∈ B t N . ( 96
) Now let h = f | Z d -φ ∈ C(B t N ) and let h ± τ = h τ ± 2c 4 f ∞,2M N 4 d j=1 (τ j -t j ) 2 .
Taking into account (96) and the fact that φ is discrete harmonic, we have for τ ∈ intB t N :

(Dh + ) τ = (Dh) τ + 2c 4 f ∞,2M N 4 > 0, (Dh -) τ = (Dh) τ - 2c 4 f ∞,2M N 4 < 0,
whence both the maximum of h + and the minimum of h -over B t N are attained at ∂B t N . Since at the discrete boundary of B t N we have f = φ and therefore (recall that d ≤ 4). 2

h + ≤ 4c 4 f ∞,2M N -2 , we conclude that τ ∈ B t N ⇒ h τ ≤ h + τ ≤ max τ ∈∂B t N h + τ ≤ 2dc 4 f ∞,2M N -2 . By similar reasons, τ ∈ B t N ⇒ h τ ≥ h - τ ≥ min τ ∈∂B t N h - τ ≥ -2dc 4 f ∞,2M N -
The proof of Proposition 14 is completely similar to that of Proposition 10.

  |τ d |}, with the standard interpretation of the right hand side when p = ∞, and we set |r| p = lim T →∞ |r| T,p ∈ R ∪ {+∞}. A field r ∈ C(Z d ) with finitely many nonzero entries r τ is called a filter, and the smallest T such that r τ = 0 whenever |τ | > T , is called the order ord(r) of a filter r; we write C T (Z d ) = {r ∈ C(Z d ) | ord(r) ≤ T }. We identify a filter r with the multivariate Laurent sum r(z 1 , ..., z d ) = τ r τ z τ 1 1 ...z τ d d .

  Our current goal is to understand how wide are the families of nice signals, and our plan is as follows: (a) we list a number of operations which preserve the property in question, and (b) we present a list of examples of signals possessing the property. Applying to "raw materials" from (b) operations from (a), one can produce a wide variety of nice signals. Here is a sample of operations preserving niceness of signals.

4. 2

 2 Examples of nice signals I. Exponential and algebraic polynomials. Let us define an exponential polynomial (s τ ) on Z d as a finite sum of exponential monomials cτ α exp{ω T τ } ≡ cτ α 1 1 ...τ α d d exp{ω T τ } with nonnegative multi-indices α and ω ∈ C d :

1 2

 12 τ i+1 ,...,τ d for all τ with |τ -t| ≤ N -1. Let us call a difference operator D regular, if it possesses the following properties: R.The vectors {α(ℓ)} 1≤ℓ≤k span the entire R d ; R.The coefficients w ℓ = ρ ℓ exp{iφ ℓ } (ρ ℓ ≥ 0, φ ℓ ∈ R) are nonzero, and

[

  Norms of convolutions of filters] r, s ∈ C(Z d ) ⇒ |r(z 1 , ..., z d )s(z 1 , , ..., z d )| p ≤ |r| 1 |s| p ;

ρ 2

 2 (φ t ) ≥ 2T + 1 256m 2 , φ t = asin(t/T ). (71) the measure supported by the finite set M = {ζ | ∃ω ∈ Ω d N : ζ = δ(ω)}, and µ({ζ}) = ω∈Ω d N :δ(ω)=ζ ν({ω}). Let also F (α) = µ ({ζ | ℜ(ζ) ≥ 1 -α}) , α ≥ 0.

2 0 . 2 )

 22 the latter system of equations implies that K belongs to a set of the form r + AZ d with certain d × d nonsingular matrix A (depending solely on D). The cardinality of the intersection of latter set with the cube [-π, π] d does not exceed certain c 3 . Thus, Card K ≤ c 3 . Let ω ∈ K, and let dω ∈ R n be such that |dω| ≤ 1. Then

ℓ ρ ℓ = 1 and c 11 |dω| 2

 2 ≤ ℓ ρ ℓ (dω) T α(ℓ) 2 ≤ c 12 |dω| 2 , we conclude from (77) combined with (79) that for properly chosen c 13 one has ω ∈ [-π, π] d ⇒ |ℑ(δ(ω))| ≤ c 13 (1 -ℜ(δ(ω))) 3/2 , and (74) follows. By (74) one has |1 -δ(ω)| ≤ c 14 (1 -ℜ(δ(ω))

  ) In (80), the choice of the branch of √ • affects the value of w, but does not affect the value of w n + w -n ; since we intend to work with ζ from the unit disk, so that ℜ(1 -ζ 2 ) > 0, in the calculations to follow we deal with the main branch of √ • in the closed right half-plane. On the segment [-1, 1] of the real axis one has T n (ζ) = cos(n acos(ζ)), whence T n (1) = 1, T ′ n (1) = n 2 . From these relations it follows that the function P n (ζ) = 1-Tn(ζ) n 2 (1-ζ) is a polynomial of degree n -1, and P n (1) = 1. Lemma 25 One has

c 15 c 23 (

 23 see (81)). Consider the polynomial S n (ζ) = P n (ζ)Q c 24 n (ζ). Lemma 26 For every positive integer n, the polynomial S n (ζ) possesses the following properties: (a) : deg(S n ) ≤ c 25 n; (b) : S n (1) = 1; (c) : max ζ {|S n (ζ)| : ζ ∈ M, ℜ(ζ) = 1 -α} ≤ c 15 min 1 n 2 α ; 1 . (86) Proof. Relations (86.a -b) are evident (take into account that P n (1) = 1 and deg

exp{c 15 nα} n 2 α

 2 exp{-c 23 c 24 nα} ≤ b c 15 n 2 α (for a, see (85), b is due to c 23 c 24 ≥ c 15 ). 2 5 0 . Now we are ready to complete the proof of Proposition 12. Given a positive integer n, let us set R n (ζ) = S d n (ζ). In view of (86) one has (a) : deg(R n ) ≤ c 26 n; (b) : R n (1) = 1; (c) : max ζ {|R n (ζ)| : ζ ∈ M, ℜ(ζ) = 1 -α} ≤ r n (α) ≡ c 26 min 1 n 2d α d ; 1 .

min 2 n

 2 s equality, we have also (in what follows, n = n(T ))|q (n) | 2 2 = Ω d N |R n (δ(ω))| 2 ν(dω) = M |R n (ζ)| 2 µ(dζ) agiven by (87.c), (74) and the definition of F (•). Let γ be the measure on [0, 2] defined byG(α) ≡ γ([0, α]) = c -1 2 (α d/2 + N -d ), so that F (α) ≤ G(α) ≡ γ([0, α]) ∀α ∈ [0)G(α)dα = ρ n (2) -ρ n (2)G(-2d α -d , 1 α d 2 -1 dα +ρ n (0)N -d ≤ d c 30 N -d + n -d ≤ c 31 (2T + 1) -d(91)(a holds since ρ n (•) is nonincreasing, see (87.c), and by (90), b holds since c 2 ∈ (0, 1), see Lemma 24, c is by (87.c) and (89), d is due to n = n(T ) = ⌊c 27 T ⌋).Combining (89) and (91), we conclude that|q (n(T )) | 2 ≤ c 32 (2T + 1) -d/2 .(92)From (88) and (92) we conclude that if L = ⌊c 33 N⌋ and T ≤ L is such that n(T ) ≡ ⌊c 27 T ⌋ ≥ 1, then∃q (T ) ∈ C T (Z d ) : (T ) | 2 ≤ c 32 (2T + 1) -d/2, s τ = (q (T ) (∆)s) τ ∀(τ, |τ -t| ≤ L, (s) ∈ H t N (D))

2

 2

5. 2 . 8 Proof of Proposition 13 Lemma 27

 281327 Let f ∈ H + (M) be a deterministic function, let N ≤ M/2, and let t ∈ Z d , |t| ≤ N. Consider the "discrete box" B t N = {τ ∈ Z d : |τ -t| ≤ N}, and let φ be a deterministic function on B t N which coincides with f on the "discrete boundary" ∂B t N ≡ {τ ∈ Z d : |τ -t| = N} of B t N and is "discrete harmonic": τ ∈ Z d , |τ -t| < N ⇒ φ τ = 1 2d ǫ=(ǫ 1 ,...,ǫ d ) |ǫ 1 |=...=|ǫ d |=1 φ τ +ǫ . Then τ ∈ B t N ⇒ |f (τ ) -φ τ | ≤ c 1 f ∞,2M N -2(94)

2 , 3 , 4 ,f

 234 j = 1, ..., d. (95)Consequently, for the basic orths e j , j = 1, ..., d we haveτ ∈ D t N , |s| ≤ 1 ⇒ f (τ + se j ) -(τ )s κ ≤ c 3 |s| 4 f ∞,2M N -4 .

2 . 2 2 1/ 2 ≤ c 6 [ 2 ≤RL - 2 ( 1 +

 22226221 Now let |t| ≤ M/8 and L ≤ M/8. Given T , 0 ≤ T ≤ L, and applying Proposition 12, we can build filter q (T ) ∈ C T (Z d ) such that|q (T ) | 2 ≤ c 5 (2T + 1) -1 , φ τ = |ν|≤T φ τ -ν q (T ) ν ∀(τ : |τ -t| ≤ L)(97)for every φ which is discrete harmonic in the discrete box B t 2L . Now let f ∈ H(M, R). Applying Lemma 27, we can find function φ which is discrete harmonic in the box B t 2L and such that |φ τ -f τ | 2 ≤ c 2 6 f 2 ∞,2M L -4 for τ ∈ B t 2L .From (97) it now follows that∀(τ : |τ -t| ≤ L) : E |f τ -|ν|≤T f τ q (T ) ν | E{ f 2 ∞,2M }] 1/|q (T ) | 1 ) ≤ c 6 RL -2 (1 + |q (T ) | 2 (2T + 1) d/2 ) ≤ c 8 RL -2 ≤ c 9 R(2T + 1) -d/2

  Definition 1 Let θ ≥ 0, ρ ≥ 1 be reals, let L be a nonnegative integer or +∞, and let t ∈ Z d . Finally, let (s τ ) τ ∈Z d ≡ (s τ (ξ)) τ ∈Z d

	be a random field on
	ξ∈Ω
	Z d .
	(1) [T -well-filtered signals] Let T be a nonnegative integer. We say that (s τ )
	is T -well-filtered, with the parameters θ, ρ, L, at the point t (notation: (s τ ) ∈ S t L (θ, ρ, T )), if there exists a filter q

To be more precise, in the filtering literature this case is referred to as interpolation.

Note that the degree of the trigonometric polynomial ρ(•) is ≤ m and that ρ(0) = 1. Besides this, ρ(φ) = ρ(π -φ); due to the latter fact,

By Bernstein's Theorem on trigonometric polynomials, we have |ρ ′ (φ)| ≤ mM. Now let φ * ∈ [-π/2, π/2] be a point such that |ρ(φ * )| = M, let ∆ be the segment of the length 1 m centered at φ * , and ∆ be the part of this segment in [-π/2, π/2]. Note that the length of ∆ is at least 1 2m and that for φ

Let n be the minimum number of points φ t belonging to a segment δ ⊂ [-π/2, π/2] of the length 1/(2m), the minimum being taken over all positions of δ in

When T ≥ 64m 2 , the latter quantity is ≥ 2T +1 256m 2 , and in any case

Thus, we always have

as required in (71). 2

Proof of Proposition 12

In the proof to follow, c i stand for positive constants depending solely on D. 1 0 . We start with the following evident observation:

Lemma 23 There exists c 1 such that for every polynomial p(t) of one variable satisfying the relation p(1) = 1 one has

2 0 . Let us fix a positive integer N, and let