On exact and optimal recovering of missing values for sequences
Nikolai Dokuchaev

arXiv:1604.06980v5 [] 4 Jan 2017

Department of Mathematics & Statistics, Curtin University, GPO Box U1987, Perth 6845,
Western Australia, Australia

Submitted April 24, 2016. Revised January 4, 2017

Abstract
The paper studies recoverability of missing values for sequences in a pathwise setting
without probabilistic assumptions. This setting is oriented on a situation where the underlying sequence is considered as a sole sequence rather than a member of an ensemble
with known statistical properties. Sufficient conditions of recoverability are obtained; it
is shown that sequences are recoverable if there is a certain degree of degeneracy of the
Z-transforms. We found that, in some cases, this degree can be measured as the number of
the derivatives of Z-transform vanishing at a point. For processes with non-degenerate Ztransform, an optimal recovering based on the projection on a set of recoverable sequences
is suggested. Some robustness of the solution with respect to noise contamination and
truncation is established.
Key words: data recovery, discrete time, sampling theorem, band-limited interpolation.

1

Introduction

The paper studies optimal recovering of missing values for sequences, or discrete time deterministic processes. This important problem was studied intensively. The classical results for
stationary stochastic processes with the spectral density φ is that a single missing value is
recoverable with zero error if and only if
Z π
φ(ω)−1 dω = −∞.
−π

Accepted to Signal Processing

1

(1)

(Kolmogorov [12], Theorem 24). Stochastic stationary Gaussian processes without this property are called minimal [12]. 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 with the notion of bandlimitiness or its relaxed versions such as (1). In particular, criterion (1) was extended on stable processes [14]
and vector Gaussian processes [15].
In theory, a process can be converted into a band-limited and recoverable process with a
low-pass filter. However, a ideal low-pass filter cannot be applied if there are missing values.
This leads to approximation and optimal estimation of missing values. For the forecasting
and other applications, it is common to use band-limited approximations of non-bandlimited
underlying processes. There are many works devoted to smoothing and sampling an based on
frequency properties; see e.g. [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17].
The present paper also consider band-limited approximations. We consider approximation
of an observed sequence in ℓr -norms rather than matching the values at selected points. The
solution is not error-free; the error can be significant if the underlying process is not bandlimited. This is different from a setting in [2, 3, 4, 11, 13], where error-free recovering was
considered. Our setting is closer to the setting from [18, 20]. In [18], optimization was considered as minimization of the total energy for an approximating bandlimited process within a
given distance from the original process smoothed by an ideal low-pass filter. In [20], extrapolation of a band-limited process matching a finite number of points process was considered
using special Slepian’s type basis in the frequency domain.
The present paper considers optimal recovering of missing values of sequences (discrete
time processes) based on intrinsic properties of sequences, in the pathwise setting, without
using probabilistic assumptions on the ensemble. This setting targets a scenario where a sole
underlying sequence is deemed to be unique and such that one cannot rely on statistics collected
from observations of other similar samples. To address this, we use a pathwise optimality
criterion that does not involve an expectation on a probability space. For this setting, we
obtained explicit optimal estimates for missing values of a general type processes (Theorems 1
and 2). We identified some classes of processes with degenerate Z-transforms allowing error-free
recoverability (Corollary 1 and 3). For a special case of a single missing values, this gives a
condition of error-free recoverability of sequences reminding classical criterion (1) for stochastic

2

processes but based on intrinsic properties of sequences, in the pathwise setting (Corollary 3).
In addition, we established numerical stability and robustness of the method with respect to
the input errors and data truncation (Section 5).

2

Some definitions and background

Let Z be the set of all integers. For a set G ⊂ Z and r ∈ [1, ∞], we denote by ℓr (G) a Banach

P
∆
r 1/r < +∞ for
space of complex valued sequences {x(t)}t∈G such that kxkℓr (G) =
t∈G |x(t)|
∆

r ∈ [1, +∞), and kxkr(G) = supt∈G |x(t)| < +∞ for r = ∞.
For x ∈ ℓ2 (Z), we denote by X = Zx the Z-transform
X(z) =

∞
X

x(t)z −t ,

t=−∞


defined for z ∈ C such that the series converge. For x ∈ ℓ2 (Z), the function X eiω |ω∈(−π,π]

is defined as an element of L2 (−π, π). For x ∈ ℓ1 (Z), the function X eiω is defined for all

ω ∈ (−π, π] and is continuous in ω.

Let m ∈ Z be given, m ≥ 0. For s ∈ Z, let Ms = {s, s + 1, s + 2, ..., s + m}.
We consider data recovery problem for input processes x ∈ ℓr such that the trace
{x(t)}t∈Z\Ms represents the available observations; the values {x(t)}t∈Ms are missing.
Definition 1. Let Y ⊂ ℓr be a class of sequences. We say that this class is recoverable if, for

any s ∈ Z, there exists a mapping F : ℓr (Z \ Ms ) → Rm+1 such that x|Ms = F x|Z\Ms for all
x ∈ Y.

For a sequence that does not belong to a recoverable class, it is natural to accept, as
an approximate solution, the corresponding values of the closest process from a preselected
recoverable class. More precisely, given observations x|Z\Ms and a recoverable class Y ⊂ ℓr , we
suggest to find an optimal solution x
b ∈ Y of the minimization problem
Minimize

X

|b
x(t) − x(t)|2

t∈Z\Ms

over

x
b ∈ Y,

(2)

and accept the trace x
b|Ms as the recovered missing values x|Ms .
3

3

Recovering based on band-limited smoothing

,Ω
We assume that we are given Ω ∈ (0, π). Let ℓBL
be the set of all x ∈ ℓ2 (Z) such that
2

,Ω
X eiω = 0 for |ω| > Ω for X = Zx. We will call sequences x ∈ ℓBL
band-limited. Let
2
,Ω
,Ω
ℓBL
(Z \ Ms ) be the subset of ℓ2 (Z \ Ms ) consisting of traces x|Z\Ms for all sequences x ∈ ℓBL
.
2
2

,Ω
,Ω
Proposition 1. For any x ∈ ℓBL
(Z \ Ms ), there exists a unique x
b ∈ ℓBL
such that x
b(t) =
2
2

x(t) for t ∈ Z \ Ms .

In a general case, where the sequence of observations x|Z\Ms does not necessarily represents
a trace of a band-limited process, we will be using approximation described in the following
lemma.
,Ω
Lemma 1. There exists a unique optimal solution x
b ∈ ℓBL
of the minimization problem (2)
2
,Ω
with r = 2 and Y = ℓBL
.
2

Under the assumptions of Lemma 1, there exists a unique band-limited process x
b such

that the trace x
b|Z\Ms provides an optimal approximation of its observable trace x|Z\Ms . The

corresponding trace x
b|Ms is uniquely defined and can be interpreted as the solution of the
problem of optimal recovering of the missing values x|Ms (optimal in the sense of problem (2)

given Ω). In this setting, the process x
b is deemed to be a smoothed version of x, and the

process η = x − x
b is deemed to be an irregular noise. This justifies acceptance of x
b|Ms as an

estimate of missing values. It can be noted that the recovered values depend on the choice of

Ω; the selection of Ω has to be based on some presumptions about cut-off frequencies suitable
for particular applications.

Let H(z) be the transfer function for an ideal low-pass filter such that H eiω = I[−Ω,Ω] (ω),

where I denotes the indicator function. Let h = Z −1 H; it is known that h(t) = Ω sinc (Ωt)/π;
we use the notation sinc (x) = sin(x)/x, and we use notation ◦ for the convolution in ℓ2 (Z).
,Ω
The definitions imply that h ◦ x ∈ ℓBL
for any x ∈ ℓ2 (Z).
2
(m+1)×(m+1) . Let I
Consider a matrix A = {h(k − p)}m,m
m+1 be the unit matrix in
k=0,p=0 ∈ R

R(m+1)×(m+1) .
Lemma 2. The matrix Im+1 − A is non-degenerate.

4

Theorem 1. Let x ∈ ℓ2 (Z) and Ω ∈ (0, π). Given observations x|Z\Ms , the problem (2) with
,Ω
,Ω
r = 2 and Y = ℓBL
has a unique optimal solution x
b ∈ ℓBL
which yields an estimate of x|Ms
2
2

defined as

x
b(s + p) = yp ,

p = 0, 1, ..., m,

(3)

m+1 is defined as
where y = {yp }m
p=0 ∈ C

y = (Im+1 − A)−1 z,

(4)

m+1 defined as
with z = {zp }m
p=0 ∈ C

zp =

X

h(p − t)x(t).

(5)

t∈Z\Ms
,Ω
Corollary 1. For any Ω ∈ (0, π), the class ℓBL
is recoverable in the sense of Definition 1.
2
,Ω
Remark 1. Equations (3)-(5) applied to a band-limited process x ∈ ℓBL
represent a special
2

case of the result [9, 10]. The difference is that x is Theorem 1 and (3)-(5) is not necessarily
band-limited.

The case of a single missing value
It appears that the solution for the special case of a single missing value (i.e. where m = 0)
allows a convenient explicit formula.
Corollary 2. Let Ω ∈ (0, π) and x ∈ ℓ2 (Z) be given. Given observations x|Z\{s} , the problem
,Ω
,Ω
(2) with r = 2 and Y = ℓBL
has a unique solution x
b ∈ ℓBL
which yields an estimate of x(s)
2
2

defined as

x
b(s) =

X
Ω
x(t)sinc [Ω(s − t)].
π−Ω

(6)

t∈Z\Ms

This solution is optimal in the sense of problem (2) with m = 0, Ms = {s}, r = 2, and
,Ω
, given Ω ∈ (0, π).
Y = ℓBL
2
,Ω
Remark 2. Corollary 2 applied to a band-limited process xBL ∈ ℓBL
gives a formula
2

xBL (s) =

X
Ω
xBL (t)sinc [Ω(s − t)].
π−Ω
t∈Z\Ms

This formula is known [9, 10]; however, equation (6) is Corollary 2 is different since x in (6)
is not necessarily band-limited.
5

4

Recovering without smoothing

Theorem 1 suggests to replace missing values by corresponding values of a smoothed bandlimited process. This process is actually different from the underlying input process; this could
cause a loss of some information contained in high-frequency components. Besides, it could be
difficult to justify a particular choice of Ω in (6) defining the degree of smoothing. To overcome
this, we consider below the limit case where Ω → π − 0.
Again, we consider input sequences {x(t)}t∈Z\Ms representing the observations available;
the values for t ∈ Ms are missing.
Without a loss of generality, we assume that either s = 0 or m = 0.
Let ω0 ∈ (0, π] be given. For x ∈ ℓ2 , l
For σ = (σ0 , σ1 ..., σm ) ∈ Rm+1 such that σk ≥ 0, k = 0, 1, ..., m, let
n
X
∆
Xσ = x ∈ ℓ1 :
|t|m |x(t)| < +∞,
t∈Z

dk X iω0 
e
≤ σk ,
dω k
o
k = 0, 1, ..., m, X = Zx .

Here and below we assume, as usual, that dk X/dω k = X for k = 0.
It can be shown that, for x ∈ Xσ and X = Zx, we have that the functions

dk X (eiω )
dω k

are

continuous in ω for k = 0, 1, ..., m.
Definition 2. Let X0 be the corresponding set Xσ with σ = 0, i.e. with σp = 0 for p =
0, 1, ..., m. We will call x degenerate of order m.
(m+1)×(m+1) such that
Let us introduce a matrix B(ω) = {bpk (ω)}m,m
k=0,p=0 ∈ C

bpk (ω) = [−i(s + k)]p e−iω(s+k) ,

ω ∈ (−π, π].

In particular, if m = 0, then B(ω) = e−iωs . If m > 0, then, by the assumptions, s = 0 and
bpk (ω) = (−ik)p e−iωk .
Lemma 3. For any ω ∈ (−π, π], the matrix B(ω) is non-degenerate.
Theorem 2. Let x ∈ ℓ1 (Z) be given such that

P

m
t∈Z |t| |x(t)|

< +∞. Given observations

,Ω
x|Z\Ms , the problem (2) with r = 1 and Y = X0 has a unique solution x
b ∈ ℓBL
which yields
2

an estimate of x|Ms defined as

x
b(s + p) = yp (ω0 ),

p = 0, 1, ..., m,
6

(7)

m+1 is defined as
where y(ω) = {yp (ω)}m
p=0 ∈ C

y(ω) = B(ω)−1 z(ω),

(8)

m+1 defined as
with z(ω) = {zp (ω)}m
p=0 ∈ C

zp (ω) = −

X

(−it)p e−iωt x(t).

(9)

t∈Z\Ms

Under the assumptions of Theorem 2, there exists a unique recoverable process x
b ∈ X0

such that x
b|t∈Z\Ms = x|t∈Z\Ms . The corresponding trace x
b|Ms is uniquely defined and can be

interpreted as the solution of the problem of optimal recovering of the missing values x|Ms

(optimal in the sense of problem (2) for Y = X0 ). In addition, Theorem 2 implies that X0 6= ∅
for any m ≥ 0; this follows from the implication from this theorem that a sequence from ℓ1 can
be transformed into a sequence in Xσ by changing its m terms.
Corollary 3. The class X0 is recoverable in the sense of Definition 1 with r = 1 and Y = X0 .
Remark 3. By Corollary 3 applied with m = 0, a single missing value process x ∈ ℓ1 is
recoverable if X (eω0 ) = 0 for X = Zx; this reminds condition (1) for spectral density of
minimal Gaussian processes [12].

The case of a single missing value
Again, the solution for the special case of a single missing value (i.e. where m = 0 and
Ms = {s}) allows a simple explicit formula.
Corollary 4. Let s ∈ Z and x ∈ ℓ1 (Z) be given. Given observations x|Z\{s} , the problem (2)
,Ω
with r = 1 and Y = X0 has a unique solution x
b ∈ ℓBL
which yields an estimate of x(s) defined
2

as

x
b(s) = −

X

eiω0 (s−t) x(t),

(10)

t6=s

where the optimality is understood in the sense of problem (2) with m = 0, Ms = {s}, r = 1,
and Y = X0 .
Remark 4. Formula (10) with ω0 = π has the form
x
b(s) = −

X

(−1)t−s x(t).

t∈Z\Ms

7

(11)

This represents the limit case of formula (6), since
Ω
sinc [Ω(s − t)] → −(−1)t−s
π−Ω

as

Ω→π−0

for all t 6= s.

Optimality in the minimax sense
It will be convenient to use mappings δp : Cm+1 → C, where p ∈ {0, 1, ..., m}, such that
δp (y) = yp for a vector y = (y0 , y1 , ..., ym ) ∈ Cm+1 .
Proposition 2. In addition to the optimality in the sense of problem (2) with Y = X0 , solutions
obtained in Theorems 2 and Corollalry 2 are also optimal in the following sense.
(i) If m = 0, then solution (6) is optimal in the minimax sense such that
sup |b
x(s) − x(s)| ≤ σ0 ≤ sup |e
x(s) − x(s)|

x∈Xσ

(12)

x∈Xσ


for any estimator x
e(s) = F x|Z\{s} , where F : ℓ1 (Z \ {s}) → C is a mapping.

(ii) If m ≥ 0 and s = 0, then solution (7)-(9) is optimal in the mininax sense such that
sup |δp (B(ω0 )b
η )| ≤ σp ≤ sup |δp (B(ω0 )e
η )|,

x∈Xσ

x∈Xσ

p = 0, 1, ..., m,

(13)


for any estimator x
e|Ms = F x|Z\Ms , where F : ℓ1 (Z \ Ms ) → Cm+1 is a mapping,

s+m
s+m
∈ Cm+1 .
∈ Cm+1 , ηe = {e
x(t) − x(t)}t=s
ηb = {b
x(t) − x(t)}t=s

5

Robustness with respect to noise contamination and data
truncation

Let us consider a situation where an input process x|Z\Ms is observed with an error. In other
words, assume that we observe a process xη |Z\Ms = x|Z\Ms + η|Z\Ms , where η is a noise.
For a matrix S ∈ Cm+1 and r1 , r2 ∈ [1, +∞], we denote by kSkr1 ,r2 the operator norm
m+1 denote the linear
of this matrix considered as an operator S : Cm+1
→ Cm+1
r1
r2 , where Cr

normed space formed as Cm+1 provided with ℓr -norm.

8

Proposition 3. In the notations of Theorem 1,
kb
x|Ms kℓθ (Ms ) ≤ (Im+1 − A)−1

2,θ

kx|Z\Ms kℓ2 (Z\Ms ) .

for any θ ∈ [1, +∞]. In particular, under the assumption of Corollary 2,
|b
x(s)| ≤

Ω
kxkℓ2 (Z\Ms ) .
π−Ω

Proposition 4. In the notations of Theorem 2,
kb
x|Ms kℓθ (Ms ) ≤ B(ω0 )−1

∞,θ

X

|t|m |x(t)|

t∈Z\Ms

for any θ ∈ [1, +∞]. In particular, under the assumption of Corollary 4,
|b
x(s)| ≤ kxkℓ1 (Z\Ms ) .
Propositions 3 and 4 ensure robustness of the data recovering with respect to noise contamination and truncation. This can be shown as the following.
Let x
bη |Ms be the sequence of corresponding values defined by (3)-(5) or (7)-(9) with xη |Z\Ms

as an input, and let x
b|Ms be the corresponding values defined by (3)-(5) or with x|Z\Ms as an

input. By Proposition 3,

k(b
x−x
bη )|Ms kℓr (Ms ) ≤ k(Im+1 − A)−1 kρ,2 kηkℓ2 (Z\Ms )

(14)

for all η|Z\Ms ∈ ℓ2 (Z \ Ms ). In particular, under the assumption of Corollary 2, i.e. for m = 0
and Ms = {s}, it follows that, in the notations of Theorem 1,
|b
x(s) − x
b(s)| ≤

Ω
kηkℓ2 (Z\Ms ) .
π−Ω

(15)

Similarly, Propositions 4 implies that

|b
x(s) − x
bη (s)| ≤ kzη (ω0 )kℓ1 (Z\Ms )

(16)

for all η|Z\Ms ∈ ℓ1 (Z \ Ms ), under the assumptions of this theorem, with zη (p, ω) =
m+1 defined as
{zη (p, ω)}m
p=0 ∈ C

zη (p, ω) = −

X

(−it)p e−iωt η(t).

t∈Z\Ms

9

This demonstrates some robustness of the method with respect to the noise in the observations. In particular, this ensures robustness of the estimate with respect to truncation
of the input processes, such that infinite sequences x ∈ ℓr (Z \ Ms ), r ∈ {1, 2}, are replaced
by truncated sequences xη (t) = x(t)I{|t|≤q} for q > 0; in this case η(t) = I|t|>q x(t). Clearly,
kηkℓr (Z\Ms ) → 0 as q → +∞. This overcomes principal impossibility to access infinite sequences
of observations.
The experiments with sequences generated by Monte-Carlo simulation demonstrated a good
numerical stability of the method; the results were quite robust with respect to deviations of
input processes and truncation.

On a choice between recovering formulae (6) and (10)
It can be seen from (14) and (16) that recovering formula (10) is less robust with respect to data
truncation and the noise contamination than recovering formula (6). In addition, recovering
formula (10) is not applicable to x ∈ ℓ2 (Z) \ ℓ1 (Z). On the other hand, application of (10) does
not require to select Ω. In practice, numerical implementation requires to replace a sequence
{x(t)} by a truncated sequence x(t)I{t:

|t|≤q} ;

technically, this means that both formulas could

be applied. The choice between (6) and (10) and of a particular Ω for (6) should be done based
on the purpose of the model. In general, a more numerically robust result can be achieved with
choice of a smaller Ω.
This can be illustrated with the following example for a case of a single missing value.
,Ω
Consider a band-limited input x ∈ ℓBL
with a missing value x(0) (i.e, m = 0 and s = 0, in the
2

notations above). In theory, application of (6) with Ω replaced by Ω1 ∈ (Ω, π] produces errorfree recovering, i.e. x
b(0) = x(0). However, application of (6) with Ω replaced by Ω2 ∈ (0, Ω1 )
may lead to a large error x
b(0) − x(0).

On the other hand, application of (10), where Ω is not used, performs better than (6)

with too small miscalculated Ω1 . This is illustrated by Figure 1 that shows an example of a
,Ω
process x(t) ∈ ℓBL
with Ω = 0.1π and recovered values x
b(0) corresponding to band-limited
2

extensions obtained from (6) with Ω = 0.1π and Ω = 0.05π. In addition, this figure shows x
b(0)

calculated by (10). On the hand, the presence of a noise in processes that are nor recoverable

without error may lead to a larger error for estimate (10). This is illustrated by Figure 2 that
shows an example of a noisy process x and recovered values x
b(0) corresponding to band-limited
10

extensions obtained from (6) with Ω = 0.1π and Ω = 0.05π. In addition, this figure shows x
b(0)

calculated by (10). In these experiments, we used Ms = {0} and truncated sums (6) and (10)
with 100 members.

6

Proofs

Proof of Proposition 1. It is known [9, 10, 11] that a continuous time bandlimited function can
be recovered without error from an oversampling sequence where a finite number of sample
,Ω
values is unknown. This implies that if x ∈ ℓBL
is such that x(t) = 0 for t ∈ Z \ Ms , then
2

x ≡ 0. Then the proof of Proposition 1 follows. 
,Ω
Proof of Lemma 1. It suffices to prove that ℓBL
(Z \ Ms ) is a closed linear subspace of
2
,Ω
ℓ2 (Z \ Ms ). In this case, there exists a unique projection x
b|Z\Ms of x|Z\Ms on ℓBL
(Z \ Ms ),
2

and the proof will be completed.


Let B be the set of all mappings X : T → C such that X eiω ∈ L2 (−π, π) and such that

X eiω = 0 for |ω| > Ω for X = Zx.
,Ω
Consider the mapping ζ : B → ℓBL
(Z \ Ms ) such that
2
Z π

1
x(t) = (ζ(X))(t) =
X eiω eiωt dω,
2π −π

t ∈ Z \ Ms .

It is a linear continuous operator. By Proposition 1, it is a bijection.
,Ω
Since the mapping ζ : B → ℓBL
(Z \ Ms ) is continuous, it follows that the inverse mapping
2
,Ω
ζ −1 : ℓBL
(Z \ Ms ) → B is also continuous; see e.g. Corollary in Ch.II.5 [19], p. 77. Since the
2
,Ω
set B is a closed linear subspace of L2 (−π, π), it follows that ℓBL
(Z \ Ms ) is a closed linear
2

subspace of ℓ2 (Z \ Ms ). Then a solution x
b of problem (2) is such that x
b|D is a projection of

,Ω
x|D on ℓBL
(Z \ Ms ) which is unique. Then the proof of Lemma 1 follows. 
2

m+1 be arbitrarily selected such that kȳk 6= 0.
Proof of Lemma 2. Let ȳ = {ȳk }m
ℓ2
k=0 ∈ C
,Ω
Let y ∈ ℓ2 (Z) be such that y|Z\Ms = 0 and that ȳ = y|M . In this case, y ∈
/ ℓBL
; it follows, for
2


instance, from Proposition 1. Let Y = Zy. We have that Z(h ◦ y) = H eiω Y eiω . Hence



kH eiω Y eiω kL2 (−π,π) < kY eiω kL2 (−π,π) . This implies that kh ◦ ykℓ2 < kykℓ2 . Hence

kAȳkℓ2 = kIM (h ◦ y)kℓ2 ≤ kh ◦ ykℓ2 < kykℓ2 = kȳkℓ2 .
Since the space ℓ2 (M ) is finite dimensional, it follows that kAk2,2 < 1. Then the statement of
Lemma 2 follows. 
11

Proof of Theorem 1. Assume that the input sequences {x(t)}t∈Z\Ms are extended on Ms
such that x|Ms = x
b|Ms , where x
b is the optimal process that exists according to Lemma 1. Then

x
b is a unique solution of the minimization problem
Minimize

X

|xBL (t) − x(t)|2

t∈Z

over

,Ω
xBL ∈ ℓBL
.
2

(17)

,Ω
By the property of the low-pass filters, x
b = h ◦ x. Hence the optimal process x
b ∈ ℓBL
from
2

Lemma 1 is such that


x
b = h ◦ xIZ\Ms + x
bIMs .

Hence
x
b(t) =

X

h(t − s)x(s) +

X

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

(18)

s∈Ms

s∈Z\Ms

This gives that
x(t) −

X

At,s x(s) = zt .

s∈Ms

This gives (3)-(5). 
,Ω
Proof of Corollary 1. If x ∈ ℓBL
, then x
b = x, since it is a solution of (2). By Theorem 1,
2

,Ω
x
b is obtained as is required in Definition 1 with r = 2 and Y = ℓBL
. 
2

Proof of Lemma 3. The case where m = 0 is trivial, since B(ω) = e−ωs in this case. Let

us consider the case where m > 0; by the assumptions, s = 0 in this case. Suppose that there
exists ω ∈ (−π, π] such that the matrix B(ω) is degenerate. In this case, there exists q =
Pm
∆ Ps+m
m+1 such that q 6= 0 and B(ω)y = 0. Let Q(z) =
k
k
{q(k)}m
k=0 q(k)z ,
k=s q(k)z =
k=0 ∈ C

p
z ∈ C. By the definition of B(ω), it follows that ddωQp eiω = 0 for p = 0, 1, ..., m. Hence
dp Q
dz p (z0 )

= 0 at z0 = eiω for p = 0, 1, ..., m. Hence Q ≡ 0. Therefore, the vector q cannot be

non-zero. This completes the proof. 
Proof of Theorem 2. Let y ∈ ℓ1 be selected such that y(t) = x(t) for t ∈
/ Ms and y|Ms = 0.
Let Y = Zy, and let x
b ∈ ℓ1 be selected such that x
b(t) = x(t) for t ∈
/ Ms , with some choice of
b = Zx
x
b|Ms . Let X
b. It follows from the definitions that

X
b
 dp Y iω  s+m
dp X
iω
(−iωt)p e−iωt x
b(t)
e
e
=
+
dω p
dω p
t=s
= −zp (ω) + δp (B(ω)y(ω)),
12

p = 0, 1, ..., m.

For ω = ω0 , this gives B(ω0 )y(ω0 ) = z(ω0 ). Hence there is a unique choice that ensures
that x
b ∈ X0 and x
b|Z\Ms = x|Z\Ms ; this choice is defined by equations (7)-(9). Clearly, this

is a unique optimal solution of the minimization problem (13) with r = 1 and Y = X0 . This

completes the proof of Theorem 2. 
Proof of Proposition 2. It suffices to prove statement (ii) only, since statment (i) is its
 P
special case. Let x ∈ Xσ for some σ 6= 0, and let Y eiω = k∈Z\Ms e−iωk x(k), ω ∈ (−π, π];

this function is observable. By the definitions, it follows that


 X −iωk
e
x(t)
X eiω = Y eiω +
t∈Ms

and
dp X iω  dp Y iω 
e
e
=
+ δp (B(ω)y(ω)),
dω p
dω p

p = 0, 1, ..., m.

For ω = ω0 , it gives
ξ = −z(ω0 ) + B(ω0 )y(ω0 ),
m+1 has components ξ =
where ξ = {ξp }m
p
p=0 ∈ C

dp X
dω p

eiω0



such that |ξp | ≤ σp . Using

the estimator from Theorem 2, we accept the value yb(ω0 ) = B(ω0 )−1 z(ω0 ) as the estimate of

y (ω0 ) = ξ. It follows that the first
y(ω0 ) = {x(s + p)}m
p=0 . We have that B(ω0 )y(ω0 ) − B(ω0 )b

inequality in (13) holds. If σ = 0 then the estimator is error-free.
Let us show that the second inequality in (13) holds. Suppose that we use another estimator

x
e(s) = Fe x|Z\Ms , where Fe : ℓ2 (Z \ Ms ) → C is some mapping. Let p ∈ {0, 1, ..., m}, and

let X± eiω be such that δk (B(ω)y(ω)) = ±σk I{k=p} , k ∈ {0, 1, ..., m}, and x± (t) = 0 for

k
t ∈ Z \ Ms for x± = Z −1 X± . By the definition of B(ω), it follows ddωXk± eiω = ±σk I{k=p} .

Clearly, x± ∈ Xσ . Moreover, we have that x
e− |Ms = x
e+ |Ms for x
e± = Fe x± |Z\Ms , for any
choice of Fe, and

max(|δp (B(ω0 )η− )|, |δp (B(ω0 )η+ )|) ≥ σp ,
p = 0, 1, ..., m,

s+m
s+m
∈ Cm+1 . Then the second
∈ Cm+1 , η+ = {e
x+ (t) − x+ (t)}t=s
where η− = {e
x− (t) − x− (t)}t=s

inequality in (13) and the proof of Proposition 2 follow. 
Proof of Corollary 3. If x ∈ X0 , then x
b = x since it is a solution of (2). By Theorem 2, x
b

is obtained as is required in Definition 1 with r = 1 and Y = X0 . 
13

Proof of Proposition 3. By Theorem 1,
kb
x|Ms kℓθ (Ms ) ≤ k(Im+1 − A)−1 k2,θ kzkℓ2 (Ms ) .
In addition,
kzkℓ2 (Ms ) ≤ kIMs (h ◦ xIZ\Ms )kℓ2 (Z) ≤ kx|Z\Ms kℓ2 (Z\Ms ) .
Then the proof of Proposition 3 follows. 
Proof of Proposition 4. By Theorem 2,
kb
x|Ms kℓθ (Ms ) ≤ kB(ω0 )−1 kρ,θ kz(ω0 )kℓρ (Z\Ms ) .
Further,
|zp (ω0 )| ≤

X

|t|m |x(t)|.

t∈Z\Ms

Then the proof of Proposition 3 follows. 

7

Discussion and possible modifications

The present paper is focused on theoretical aspects of possibility to recover missing values.
The paper suggests frequency criteria of error-free recoverability of a single missing value in
pathwise deterministic setting. In particular, m missing values can be recovered for processes
that are degenerate of order m (Definition 2). Corollary 3 gives a recoverability criterion
reminding the classical Kolmogorov’s criterion (1) for the spectral densities [12]. 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 [12], i.e. this process is non-recoverable. On the other hand, Corollary
3 imply that single values of processes x ∈ ℓ1 are recoverable if X(−1) = 0 for X = Zx. In

particular, this class includes sequences x such that |X eiω | ≤ const ·(π 2 − ω 2 )ν for ν ∈ (0, 1).

Nevertheless, this similarity still could be used for analysis of the properties of pathwise Ztransforms 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 belong to ℓBL
or X0 .
2

We leave this analysis for the future research.
14

There are some other open questions. The most challenging problem is to obtain pathwise
necessary conditions of recoverability that are close enough to sufficient conditions. In addition,
there are more technical questions. In particular, it is unclear if it possible to relax conditions
of recoverability described as weighted ℓ1 -summarability presented in the definition for Xσ .
It is also unclear if it is possible to replace the restrictions on the derivatives of Z-transform
imposed at one common point for the processes from X0 by conditions at different points. We
leave this for the future research.

Acknowledgment
This work was supported by ARC grant of Australia DP120100928 to the author. In addition, the author thanks the anonymous referees for their valuable suggestions which helped to
improve the paper.

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] 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.
[4] 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.
[5] N. Dokuchaev. (2012). On predictors for band-limited and high-frequency time series.
Signal Processing 92, iss. 10, 2571-2575.
[6] N. Dokuchaev. (2012). Predictors for discrete time processes with energy decay on higher
frequencies. IEEE Transactions on Signal Processing 60, No. 11, 6027-6030.
15

[7] N. Dokuchaev. (2016). Near-ideal causal smoothing filters for the real sequences. Signal
Processing 118, iss. 1, pp. 285-293.
[8] D. L. Donoho and P. B. Stark. (1989). Uncertainty principles and signal recovery. SIAM
J. Appl. Math., vol. 49, no. 3, pp. 906–931.
[9] P.J.S.G. Ferreira. (1992). Incomplete sampling series and the recovery of missing samples
from oversampled band-limited signals, IEEE Transactions on signal processing, 40(1),
pp.225–227.
[10] P.J.S.G. Ferreira. (1994). The stability of a procedure for the recovery of lost samples in
band-limited signals, Signal Processing, 40(2-3), pp.195-205.
[11] P. G. S. G. Ferreira (1994). Interpolation and the discrete Papoulis-Gerchberg algorithm.
IEEE Transactions on Signal Processing 42 (10), 2596–2606.
[12] A.N. Kolmogorov. (1941). Interpolation and extrapolation of stationary stochastic series.
Izv. Akad. Nauk SSSR Ser. Mat., 5:1, 3–14.
[13] D.G. Lee, P.J.S.G. Ferreira. (2014). Direct construction of superoscillations. IEEE Transactions on Signal processing, V. 62, No. 12,3125-3134.
[14] 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.
[15] M. Pourahmadi (1984). On minimality and interpolation of harmonizable stable processes. SIAM Journal on Applied Mathematics, Vol. 44, No. 5, pp. 1023–1030.
[16] M. Pourahmadi. Estimation and interpolation of missing values of a stationary time
series. J. Time Ser. Anal., 10 (1989), pp. 149-169
[17] 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.
[18] R. Tzschoppe, J.B. Huber. (2009). Causal discrete-time system approximation of nonbandlimited continuous-time systems by means of discrete prolate spheroidal wave functions. Eur. Trans. Telecomm.20, 604–616.
16

[19] K. Yosida. (1965). Functional Analysis. Springer, Berlin Heilderberg New York.
[20] H. Zhao, R. Wang, D. Song, T. Zhang, D. Wu. (2014). Extrapolation of discrete bandlimited signals in linear canonical transform domain Signal Processing 94, 212–218.

17

1
recovered value
missed value
observed process

0.8

0.6

0.4

0.2

0

-0.2

-0.4
-20

-15

-10

-5

0

5

10

15

20

1
recovered value
missed value
observed process

0.8

0.6

0.4

0.2

0

-0.2

-0.4
-20

-15

-10

-5

0

5

10

15

20

1
recovered value
missed value
observed process

0.8

0.6

0.4

0.2

0

-0.2

-0.4
-20

-15

-10

-5

0

5

10

15

20

,Ω
Figure 1: Example of a path x ∈ ℓBL
with Ω = 0.1π and the recovered values x
b(0) calculated
2

using 100 observations: (i) calculated by (6) for Ω = 0.1π (top); (ii) calculated by (6) with Ω = 0.05π
(middle); (iii) calculated by (10) (bottom).

18

1.2
recovered value
missed value
observed process

1
0.8
0.6
0.4
0.2
0
-0.2
-0.4
-0.6
-0.8
-20

-15

-10

-5

0

5

10

15

20

1.2
recovered value
missed value
observed process

1
0.8
0.6
0.4
0.2
0
-0.2
-0.4
-0.6
-0.8
-20

-15

-10

-5

0

5

10

15

20

1.2
recovered value
missed value
observed process

1
0.8
0.6
0.4
0.2
0
-0.2
-0.4
-0.6
-0.8
-20

-15

-10

-5

0

5

10

15

20

Figure 2: Example of a path x ∈ ℓ2 (Z \ Ms ) and the recovered values x
b(0) calculated using 100
observations: (i) calculated by (6) for Ω = 0.1π (top); (ii) calculated by (6) with Ω = 0.05π (middle);

(iii) calculated by (10) (bottom).

19

