On recovering missing values in a pathwise setting

arXiv:1604.04967v2 [] 21 Apr 2016

Nikolai Dokuchaev
April 18, 2016

Abstract
The paper suggests a frequency criterion of error-free recoverability of a missing value for
sequences, i.e., discrete time processes, in a pathwise setting, without using probabilistic
assumptions on the ensemble. This setting targets situations where we deal with a sole
sequence that is deemed to be unique and such that we cannot rely on statistics collected
from other similar samples. A missing value has to be recovered using the intrinsic properties
of this sole sequence. In the paper, error-free recoverability is established for classes of
sequences with Z-transform vanishing at a point with a rate that can be chosen arbitrarily.
The corresponding recovering kernels are obtained explicitly. Some robustness with respect
to noise contamination is established for the suggested recovering algorithm.
Key words: data recovery, minimal Gaussian processes, pathwise criterions, frequency
criterion, discrete time, Z-transform, robustness

1

Introduction

A core problem of the mathematical theory of signal processing is the problem of recovery
of missing data. For continuous data, the recoverability is associated with smoothness or
analytical properties of the processes. For discrete time processes, it is less obvious how to
interpret analyticity; so far, these problems were studied in a stochastic setting, where an
observed process is deemed to be representative of an ensemble of paths with the probability
distribution that is either known or can be estimated from repeating experiments. A classical
result for stationary stochastic processes with the spectral density φ is that a missing single
value is recoverable with zero error if and only if
Z

π
−π

φ eiω

−1

dω = −∞.

(1)

The author is with Department of Mathematics & Statistics, Curtin University, GPO Box U1987, Perth,
6845 Western Australia.

1

(Kolmogorov [9], Theorem 24). Stochastic stationary Gaussian processes without this property
are called minimal [9]. In particular, a process is recoverable if it is “band-limited” meaning
that the spectral density is vanishing on an arc of the unit circle T = {z ∈ C : |z| = 1}.
This illustrates the relationship of recoverability on the notion of bandlimitiness or its relaxed
versions such as (1). In particular, criterion (1) was extended on stable processes [10] and vector
Gaussian processes [11]. There are many works devoted to minimization of data recovery errors
in different settings; see e.g. [1, 2, 4, 5, 3, 12, 13].
The paper suggests a criterion of error-free recoverability of sequences (discrete time processes) similar to (1) based on intrinsic properties of sequences, in the pathwise setting, without
using probabilistic assumptions on the ensemble. This setting targets situations where we deal
with a sole sequence that is deemed to be unique and such that one cannot rely on statistics
collected from observations of other similar samples. An estimate of the missing value has to be
done based on the intrinsic properties of this sole sequence and the observed values. The result
is based on the approach developed for pathwise predicting [6, 7, 8], where some predictors
were derived to establish error-free predicability. In the present paper, error-free recoverability
is established for certain classes of processes with Z-transform vanishing at a point (Theorem
1). The decay rate can selected as an arbitrarily small power of the distance to this point
(Proposition 1). The corresponding recovering kernels are obtained and represented explicitly
via their transfer functions. Some robustness with respect to noise contamination is established
for the suggested recovering algorithm.

2

Some definitions and background
∆

Let T = {z ∈ C : |z| = 1}, and let Z be the set of all integers.
We denote by ℓr the set of all sequences x = {x(t)} ⊂ C, t = 0, ±1, ±2, such that kxkℓr =

P∞
r 1/r < +∞ for r ∈ [1, ∞) or kxk
ℓ∞ = supt |x(t)| < +∞ for r = +∞.
t=−∞ |x(t)|
For x ∈ ℓ1 or x ∈ ℓ2 , we denote by X = Zx the Z-transform
X(z) =

∞
X

x(t)z −t ,

z ∈ C.

t=−∞

Respectively, the inverse x = Z−1 X is defined as
1
x(t) =
2π

Z

π

−π


X eiω eiωt dω,

t = 0, ±1, ±2, ....


We have that x ∈ ℓ2 if and only if kX eiω kL2 (−π,π) < +∞. In addition, kxkℓ∞ ≤
2


kX eiω kL1 (−π,π) .

We use the sign ◦ for convolution in ℓ2 .
b be the set of all real sequences b
Let K
k ∈ ℓ2 such that b
k(0) = 0.

By recoverability, we mean a possibility of constructing a linear recovering operator as
described in the definition below.
Definition 1 Let Y ⊂ ℓ2 be a class sequences.
b
(i) We say that this class is recoverable if there exists a sequence {b
km (·)}+∞
m=1 ⊂ K and
|x(0) − x
bm (0)| → 0
∆

Here x
b = h ◦ x, i.e. x
bm (0) =

P

as

m → +∞

∀x ∈ Y.

b

s∈Z\{0} km (s)x(s).

b
(ii) We say that the class Y is uniformly recoverable if, for any ε > 0, there exists b
k(·) ∈ K
such that

∆

Here x
b = h ◦ x, i.e. x
b(0) =

3

|x(0) − x
b(0)| ≤ ε

P

s∈Z\{0}

∀x ∈ Y.

b
k(s)x(s).

The main results

We will establish recoverability for sequences with Z-transforms in a special weighted Lp -spaces.
Let us introduce some classes of the corresponding weights.

Special weighted spaces
For p ∈ (1, +∞], let H(p) be the set of functions h : (−π, π) → (0, +∞) such that the following
holds:
(h1) h is continuous at any ω ∈ (−π, π), inf ω∈(−π,π) h(ω) > 0, and h(−ω) = h(ω) for all ω.
(h2) There exits a function W : (−π, π) → R such that W (ω) = W (−ω), and that
Z

0

π

|W (ω)|q h(ω)−q dω < +∞ for q = (1 − 1/p)−1 ,
Z π
W (ω)dω = +∞ ∀ε ∈ (π − 1, π).
π−ε

3

The following proposition gives examples of possible choices for h ∈ H(p) and of the corresponding functions W .
Proposition 1

(i) Let a function h : (−π, π) → (0, +∞) be such that condition (h1) outlined

in the definition of H(p) holds, and that there exists a ∈ R and q ≥ 1 such that
Z

π

Z

a

h(ω) dω = +∞,

−π

π

h(ω)q(a−1) dω < +∞.

−π

Then h ∈ H(p) for p = (1 − 1/q)−1 . A possible choice of W is W (ω) = h(ω)a .
(ii) Let ν > 0, and let h(ω) = (π 2 − ω 2 )−ν for ω ∈ (−π, π). Then h ∈ H(p) for any p > 1/ν.
A possible choice of W is W (ω) = h(ω)1/ν . In particular, for any ν > 0, any function h
of this type belongs to H(∞).
(iii) Let a function h : (−π, π) → (0, +∞) be such that conditions (h1) outlined in the definiRπ
tion of H(p) holds, and that −π h(ω)dω = +∞. Then h ∈ H(∞). A possible choice of
W is W (ω) = h(ω).

For p ∈ (1, +∞] and h ∈ H(p), let X(p, h) be the class of all sequences x ∈ ℓ2 such that
Z

π
−π


h(ω)|X eiω |p dω < +∞,

if

p ∈ [1, +∞),

(2)

p = +∞,

(3)

and

ess sup h(ω)|X eiω | < +∞,

if

ω∈(−π,π)

where X = Zx.
Note that if h ∈ H(p) then h(ω) → +∞ as ω → ±π. In this case, (2) and (3) hold

for “degenerate” processes, with X eiω vanishing as ω → ±π with the corresponding rate of

decay defined by h. In particular, a class X(ν, p) includes all band-limited processes x such


that X eiω ∈ Lp (−π, π) and X eiω = 0 for ω ∈
/ [−Ω, Ω], for some Ω ∈ (0, π), where X = Zx.
It can be also noted that if h1 ∈ H(p) and h2 ∈ H(p) be such that h1 (ω) ≤ Ch2 (ω) for all

ω and for some C > 0, then X(p, h2 ) ⊂ X(p, h1 ).
For given p ∈ [1, +∞] and h ∈ H(p), let U(p, h) be a class of processes x ∈ X(p, h) such
that
Z

Dε


h(ω)|X eiω |p dω → 0 as

ε→0+

4

uniformly over x ∈ U (p, h),

for p ∈ [1, +∞), and

ess sup h(ω)|X eiω |p dω → 0 as

ε→0+

uniformly over x ∈ U (p, h).

ω∈Dε

for p = +∞. Here Dε = (−π, −π + ε) ∪ (π − ε, π) and X = Zx.

Recovering kernels and recoverable sequences
Lemma 1 Let p ∈ (1, +∞] and h ∈ H(p) be given, and let a function W : (−π, π) → R be such
as described in the definition for H(p), with this h. For n > 1, consider kernels constructed as
b
b n , where functions K
b =K
b n are such that
k(·) = b
kn (·) = Z−1 K

b eiω = 1,
K

b eiω = −W (ω),
K

b eiω = 0,
K

|ω| < π − 1/n,
|ω| ∈ [π − 1/n, π − εn ],
|ω| ∈ (π − εn , π).

Here εn ∈ (0, 1/n) are uniquely defined such that
Z

π−εn

W (ω)dω = π −

π−1/n

1
.
n

(4)

b i.e. b
Then b
k ∈ K,
k ∈ ℓ2 and b
k(o) = 0.

It follows that the kernels introduced in Lemma 1 are potential candidates for the role of

recovering kernels presented in Definition 1. The following theorem shows that these kernels
ensure recoverability of certain classes of sequences.
Theorem 1 For any p ∈ (1, +∞) or p = +∞, and for any h ∈ H(p), the following holds.
(i) The class X(p, h) is recoverable.
(ii) The class U(p, h) is uniformly recoverable.
(iii) The kernels b
k=b
kn introduced in Lemma 1 ensure prediction required in (i) and (ii) as
n → +∞. For these kernels,

|x(0) − x
b(0)| → 0

as

n → +∞

5

∀x ∈ X(p, h).

Moreover, for any ε > 0, there exists n > 0 such that

∆

Here x
b(t) =

P∞

|x(0) − x
b(0)| ≤ ε

b

∀x ∈ U(p, h).

(5)

s=−∞ k(s)x(s).

Remark 1 The choice of the functions W and recovering kernels b
k is not unique for a given
h ∈ H(p). For instance, let h be such as described in Proposition 1(ii), then W (ω) = h(ω, ν)µ

satisfies the conditions outlined of the definition for H(p) for any µ > 0 such that νµ ∈
h

1, 1 + 1q , where q = (1 − 1/p)−1 .

4

Proofs

Proof of Proposition 1. To prove statement (i), it suffices to observe that W (ω) = h(ω)a satisfy
condition (h2) outlined in the definition of H(p). For statements (ii) and (iii), it suffices to
observe that h(ω) satisfy the assumptions of statement (i). For statement (ii), we have to select
a = 1/ν. For statement (ii), we have to select a = 1. 

b e−iω = K
b (eiω ), we have that b
b is real valued. The
Proof of Lemma 1. Since K
k = Z−1 K
conditions (i)-(ii) in the definition of H(p) ensure that there exists εn ∈ (0, 1/n) such that (4)
holds. Further, (4) implies that
Z

−π+1/n

−π+εn

Hence

Rπ

−π

b
K(ω)dω
+

Z

π−εn

π−1/n

b
K(ω)dω
= 2/n − 2π = −


b eiω dω = 0. Therefore,
K

1
b
k(0) =
2π

Z

π

−π

Z

π−1/n

−π+1/n


b eiω dω.
K


b eiω dω = 0.
K

This completes the proof of Lemma 1. 
b =K
b n be as defined above. Let x ∈ X(p, h),
Proof of Theorem 1. Let n → +∞, and let K
b and
X = Zx, b
k = Z−1 K,
∆

∆

x
b(t) =

t
X

s=−∞

b
k(t − s)x(s).

 ∆



b eiω =
b eiω X eiω = (Zb
By the definitions, it follows that X
K
x) eiω .
6



b eiω − X eiω kL (−π,π) = I1 + I2 + I3 , where
We have that kX
1
Ik =

Z

b e
|X

iω

Dk



iω

−X e



|dω =

Z

Dk



b eiω − 1)X eiω |dω,
|(K

and where
D1 = (−π + 1/n, π − 1/n),

D2 = [−π + εn , −π + 1/n] ∪ [π − 1/n, π − εn ],

D3 = (−π, −π + εn ) ∪ (π − εn , π).
Clearly,


b eiω − 1)X eiω kL (D ) = 0.
I1 = k(K
1
1


Let us estimate I2 . By the assumptions, kh(ω)X eiω kLp (−π,π) < +∞. We have that
I2 =

Z

D2





b eiω − 1)X eiω |dω ≤ ψn kX eiω kL (−π,π) ≤ ψn kh(ω)X eiω kL (D ) ,
|(K
p
p
2

where
ψn =

Z

−q

|h(ω)|
D2

b e
|(K

iω



q

− 1)| dω

1/q

,

and where q = (1 − 1/p)−1 ∈ [1, +∞). We have that
ψn ≤

Z

D2


b eiω |q dω
|h(ω)|−q |K

1/q Z
+

|h(ω)|−q dω

D2

1/q
.

Clearly,
Z
b
By the assumption on K,
Z

|h(ω)|−q dω ≤
D2

−q

|h(ω)|
D2

Z

π

|h(ω)|−q dω < +∞.

−π


b eiω |q dω ≤ 2
|K

Z

π

|h(ω)|−q |W (ω)|q dω.

0

By the assumptions on W , it follows that the sequence {ψn } is bounded. Hence I2 → 0 as
n → +∞.

7

Let us estimate I3 . We have that
I3 =

Z

D3



b eiω − 1)X eiω |dω =
|(K

Z

D3


|X eiω |dω → 0

n → +∞.

It follows that I1 + I2 + I3 → 0 for any c > 0 and x ∈ X(h, p). Hence kb
y − ykℓ∞ → 0 as
n → +∞ for any x ∈ X(h, p). This completes the proof of statement (i).
Let us prove statement (ii). By the assumptions on U(h, p), it follows that, in the notations
of the proof above,


b eiω − X eiω kL (−π,π) = I1 + I2 + I3
kX
1
= I2 + I3 → 0

as

n → +∞

uniformly over x ∈ U(h, p). For any ε > 0, one can select n such that I2 + I3 ≤ ε. This choice
ensures that kb
x − xkℓ∞ ≤ ε. This completes the proof of statement (ii). It follows that the
b are such as required. This completes the proof of Theorem 1.
predicting kernels b
k(·) = Z−1 K


5

On robustness with respect to noise contamination

Let us discuss the impact of on the recovery error of the presence of the noise contaminating
recoverable sequences. Assume that the kernels b
k described above and designed for recoverable

sequences are applied to a sequence with a noise contamination. Let us consider an input
sequence x ∈ ℓ2 such that x = x0 + η, where x0 ∈ U(p, h) for some h ∈ H(p) and p ∈ [1, +∞],
and where η ∈ ℓ2 \ X(p, h) represents a noise. Let X = Zx, X0 = Zx0 , and N = Zη. We assume


that X0 eiω ∈ L1 (−π, π) and kN eiω kL1 (−π,π) = σ. The parameter σ ≥ 0 represents the
intensity of the noise.

k are such as described in Theorem 1. In the proof of Theorem 1,
Assume that the kernels b

we found that, for an arbitrarily small ε > 0, there exists n = n(p, h) such that
Z

π
−π



b eiω − 1)X0 eiω |dω ≤ 2πε
|(K

∀x0 ∈ U(p, h),

b = Zb
k ◦ x0 , this implies that
k. For x
b0 = b
where K

|b
x0 (0) − x0 (0)| ≤ kb
x0 − x0 kℓ∞ ≤ ε.

k ◦ x, we have We
Let us estimate the prediction error for the case where σ > 0. For x
b=b
8

have that
kb
x − xkℓ∞ ≤ E0 + Eη ,
where
E0 =



1
b eiω − 1)X0 eiω |kL (−π,π) ≤ ε,
k(K
1
2π

Eη =



1
b eiω − 1)N eiω |kL (−π,π) .
k(K
1
2π

The value Eη represents the additional error caused by the presence of unexpected highfrequency noise (when σ > 0). It follows that
|b
x(0) − x(0)| ≤ kb
x − xkℓ∞ ≤ ε + σ(κ + 1),

(6)


b eiω |.
where κ = supω∈[−π,π] |K

Therefore, it can be concluded that the prediction is robust with respect to noise contami-

nation for any given ε.
It can be noted that if ε → 0 then n → +∞ and κ → +∞. In this case, error (6) is
increasing for any given σ > 0. This happens when the predictor is targeting too small a size
of the error for the sequences from X(p, h), i.e., under the assumption that σ = 0.
The equations describing the dependence of ε and κ on n could be derived similarly to
estimates in [7], Section 6, where it was done for some predicting kernels and for band-limited
sequences.

6

Discussion and future development

The paper suggests a frequency criterion of error-free recoverability of a single missing value
in pathwise deterministic setting in the spirit of the Kolmogorov’s criterion of minimality for
stochastic Gaussian stationary processes [9]. Some robust recovering algorithm for classes of
these sequences is suggested.
With the choice of h from Proposition 1 (ii), Theorem 1 gives a criterion that reminds
the classical Kolmogorov’s criterion (1) for the spectral densities [9]. However, the degree of
similarity is quite limited. For instance, if a stationary Gaussian process has the spectral density
φ(ω) ≥ const · (π 2 − ω 2 )ν for ν ∈ (0, 1), then, according to criterion (1), this process is not
minimal [9], i.e. this process is non-recoverable. On the other hand, Theorem 1 and Proposition
1 (ii) imply that, for p ∈ (1, +∞], the class X(p, h) is recoverable with |h(ω)| = (π 2 − ω 2 )−ν if

ν > 1/p; in particular, this class includes sequences x such that |X eiω | ≤ const ·(π 2 −ω 2 )ν for
9

X = Zx. If p = +∞ then recoverability can be ensured with an arbitrarily small rate of decay
ν > 0. Nevertheless, this similarity still could be used for analysis of the properties of pathwise
Z-transforms for stochastic Gaussian processes. In particular, assume that y = {y(t)}t∈Z is
a stochastic stationary Gaussian process with spectral density φ such that (1) does not hold.
It follows that adjusted paths {(1 + δt2 )−1 y(t)}t∈Z , where δ > 0, cannot have Z-transform
satisfying the assumption of Proposition 1 (ii). We leave this analysis for the future research.
There are other open questions. In particular, it is unclear if it is possible to obtain pathwise
necessary conditions of error-free recoverability based on Z-transform. In addition, it could be
b similarly to Proposition 1
interesting to find other convenient choices of functions h and K,
and Lemma 1.

Acknowledgment
This work was supported by ARC grant of Australia DP120100928 to the author.

References
[1] Y. Alem, Z. Khalid, R.A. Kennedy. (2014). Band-limited extrapolation on the sphere for
signal reconstruction in the presence of noise, Proc. IEEE Int. Conf. ICASSP’2014, pp.
4141-4145.
[2] T. Cai, G. Xu, and J. Zhang. (2009), On recovery of sparse signals via ℓ1 minimization,
IEEE Trans. Inf. Theory, vol. 55, no. 7, pp. 3388-3397.
[3] D. L. Donoho and P. B. Stark. (1989). Uncertainty principles and signal recovery. SIAM
J. Appl. Math., vol. 49, no. 3, pp. 906–931.
[4] E. Candés, T. Tao. (2006), Near optimal signal recovery from random projections: Universal encoding strategies? IEEE Transactions on Information Theory 52(12) (2006),
5406-5425.
[5] E.J. Candes, J. Romberg, T. Tao. (2006). Robust uncertainty principles: Exact signal
reconstruction from highly incomplete frequency information. IEEE Transactions on Information Theory 52 (2), 489–509.
[6] N.Dokuchaev. (2012). On predictors for band-limited and high-frequency time series.
Signal Processing 92, iss. 10, 2571-2575.

10

[7] N. Dokuchaev. (2012). Predictors for discrete time processes with energy decay on higher
frequencies. IEEE Transactions on Signal Processing 60, No. 11, 6027-6030.
[8] N. Dokuchaev. (2016). Near-ideal causal smoothing filters for the real sequences. Signal
Processing 118, iss. 1, pp. 285-293.
[9] A.N. Kolmogorov. (1941). Interpolation and extrapolation of stationary stochastic series.
Izv. Akad. Nauk SSSR Ser. Mat., 5:1, 3–14.
[10] V. V. Peller (2000). Regularity conditions for vectorial stationary processes. In: Complex
Analysis, Operators, and Related Topics. The S.A. Vinogradov Memorial Volume. Ed. V.
P. Khavin and N. K. Nikol’skii. Birkhauser Verlag, pp 287-301.
[11] M. Pourahmadi (1984). On minimality and interpolation of harmonizable stable processes. SIAM Journal on Applied Mathematics, Vol. 44, No. 5, pp. 1023–1030.
[12] M. Pourahmadi. Estimation and interpolation of missing values of a stationary time
series. J. Time Ser. Anal., 10 (1989), pp. 149-169
[13] J. Tropp and A. Gilbert. (2007). Signal recovery from partial information via orthogonal
matching pursuit, IEEE Trans. Inf. Theory, vol. 53, no. 12, pp. 4655–4666.

11

