# Error Estimates from Noise Samples for Iterative Algorithm in Shift-Invariant Signal Spaces

Authors: Jun Xian
Journal: Abstract and Applied Analysis
 (2010)

---

## Abstract

We consider error estimates of iterative algorithm in
shift-invariant signal spaces. For the classical sampling and reconstruction algorithm,
error estimate from its samples corrupted by white noises are widely studied,
but the error analysis of noise with time jitter and iterative noise has not been
given as much attention. In this paper, three types of error estimates are studied.
In detail, we obtain the error estimate for reconstructing a signal from its noise
samples, noise samples with time jitter, and iterative noise.


---

## Body

## 1. Introduction

The famousShannon sampling theorem [1] successful resolves the reconstruction of a function f on ℝd from its samples {f(xj):j∈J}, where J is a countable index set. This is a common task in many applications in signal or image processing. The Shannon sampling theorem says that if f is the bandlimited signal of finite energy, then it is completely characterized by its samples. In many engineering applications, such as MRI imaging, signals and images are not band limited. One such example is the shift-invariant spaces. Nonuniform sampling and reconstruction problems in shift-invariant spaces are a relatively recent and active research field [2–12]. The shift-invariant space model developed in the 1990s is successful for many engineering problems, where the signal f to be reconstructed is assumed to live in a shift-invariant space. It has been shown to be suitable and realistic, especially for taking into account of realistic environment, for modeling signals with smooth spectrum, or for numerical implementation [8, 10, 12].In this paper, we will assume that the functions or signals all belong to shift-invariant space of the form [2–12] (1.1)V2={∑k∈Zckφ(⋅-k):{ck}∈l2}.Many reconstruction algorithms are studied in shift-invariant spaces. For example, the iterative algorithm is obtained in shift-invariant spaces [3]. However, the reconstructing a function from data corrupted by noise has not been given as much attention. Smale and Zhou reconstructed signals from noisy data in [7] and gave error estimates for the reconstructed signal [8]. Aldroubi et al. discussed error analysis of frame reconstruction from noisy samples in [2]. Chen et al. gave the estimate of aliasing error for reconstruction algorithm in shift-invariant spaces [4]. We will study error analysis of the iterative reconstruction algorithm from noisy samples in shift-invariant spaces.In this paper, the following three types of errors are considered for the iterative algorithm in shift-invariant spaces.(1)
Signal samples are affected by some additive noise and are therefore given by(1.2)f(xj)+ϵ(xj),
where {xj} is sampling point and ϵ is a vector of noise samples.(2)
Add time-jitter error in the above error model(1.3)f(xj+δj)+ϵ(xj),
where {δj} are jitter. Due to the sampling time, points are not met correctly but might differ from the exact ones by not more than a given δ, that is, |δj|≤δ.(3)
Numerical error in thenth iterative step in the iterative algorithm as shown in Theorem 2.1 is ϵn, that is,
(1.4)f̃1=PQXf+ϵ1,f̃n+1=f̃1+(I-PQX)(f̃n)+ϵn+1.For the first kind of error analysis, it is widely studied, see [1, 3, 7, 8, 10]. However, the second and third kinds of error analysis have not been given as much attention. The second type of error analysis is presented in band-limited signal spaces [13]. The time-jitter errors without additive noise are studied in [6, 9]. Some results of the third type of error analysis are shown in reproducing kernel spaces [14]. In this paper, we study the three types of error for the iterative algorithm in shift-invariant spaces.The paper is organized as follows. In Section2, we introduce some concepts such as bounded partition of unity, shift-invariant spaces, and the iterative algorithm in shift-invariant spaces. In Section 3, we give error estimates of the iterative algorithm reconstruction algorithm from noisy samples.


## 2. Notations and Preliminaries

The shift-invariant spaces under consideration are of the form(2.1)V2={∑k∈Zckψ(⋅-k):{ck}∈l2},
where ψ is the so-called generator. The generator belongs to a subspace of continuous functions of Wiener amalgam spaces W0(L1)⊂W(L1). A measurable function f belongs to Wiener amalgam spaces W(L1) if it satisfies (2.2)‖f‖W(L1)=∑k∈Zesssup⁡{|f(x+k)|;x∈[0,1]d}<∞.
For any f=∑k∈Zckψ(·-k)∈V2, we have the norm equivalences ∥f∥L2≈∥c∥ℓ2 in [3]; that is, there exist constants α and β such that(2.3)β‖f‖L2≤‖c‖l2≤α‖f‖L2.A setX={xj:j∈J} satisfying infj,l|xj-xl|>0 is called separated, where J is a countable index set. For the sampling set X, we can give the following definition of bounded partition of unity (BPU). A bounded partition of unity (BPU) associated with X={xj}j∈J is a set of functions {βj} that satisfy(1)
0≤βj≤1, where j∈J,(2)
suppβj⊂Bδ(xj),(3)
∑j∈Jβj=1.The operatorQX defined by QXf(x)=∑xj∈Xf(xj)βxj(x) is a quasi-interpolant of the sampled values f|X.Aldroubi and Gröchenig presented the following iterative algorithm in [3].Theorem 2.1.
LetX={xj:j∈J} be sampling set with  ℝd=⋃j∈JBδ(xj) for some  δ>0 and  {βj} be a BPU associated with  X. Let  ψ be in  W0(L1) and  P be a bounded projection from  L2(ℝd) onto  V2. Then, there exists density  δ such that if  X={xj} is separated, then any  f∈V2 can be recovered from its samples  {f(xj)}j∈J on sampling set  X by the iterative algorithm
(2.4)f1=PQXf,fn+1=PQX(f-fn)+fn.


## 3. Error Estimates of Iterative Reconstruction Algorithm

First, for given data{y}j∈J of the form yj=f(xj)+ϵ(xj), we give the estimation of ∥f-f′∥ in Theorem 3.3, where f′ is recovered via the iterative approximation projection reconstruction algorithm in Theorem 2.1 from corrupted samples {f(xi)+ϵ(xi)}. If ϵ are noise with zero mean and σ2 variance, then the error estimates of E(f(x)-f′(x)) and Var(f(x)-f′(x)) are presented in Theorem 3.1. Second, we discuss the second type of error. The estimate of |f(x)-f∞(x)| will be shown in Theorem 3.4, where f∞ is recovered via the iterative approximation projection reconstruction algorithm from corrupted samples {f(xi+δi)+ϵ(xi)}. Third, if there exists the numerical error in nth iterative step in the iterative algorithm, then we will consider the numerical stability of the iterative algorithm in Theorem 3.5.Theorem 3.1.
Suppose that the initial samples in the iterative approximation projection reconstruction algorithm as shown by Theorem2.1 are corrupted,  that is, {f(xi)+ϵ(xi)} for noise  ϵ={ϵ(xi)}. Assume that  ϵ(x), x∈X are noises with zero mean and  σ2 variance,  that is,
(3.1)E(ϵ(x))=0,Var⁡(ϵ(x))=σ2.
If there exists a constant M>0 such that
(3.2)∑|Sxj(x)|2≤M,
then for any x∈ℝd(3.3)E(f(x)-f′(x))=0,Var⁡(f(x)-f′(x))≤Mσ2,
where f′ is recovered via the iterative approximation projection reconstruction algorithm from corrupted samples {f(xi)+ϵ(xi)},Sxj(x)=(I+∑n=1∞(I-PQX)n)Pβxj(x) and P,QX, and βxj are defined in Theorem 2.1.Proof.
Applying (2.4) iteratively leads to
(3.4)fn=(I+∑k=1n(I-PQX)k)f1(x),
which together with the convergence of (2.4) implies that
(3.5)f(x)=∑xj∈Xf(xj)Sxj(x),
where Sxj(x)=(I+∑n=1∞(I-PQX)n)Pβxj(x), QXf(x)=∑xj∈Xf(xj)βxj(x).
Combining (3.5) with E(ϵ(x))=0 leads to
(3.6)E(f(x)-f′(x))=E(∑xj∈Xϵ(xj)Sxj(x))=∑xj∈XE(ϵ(xj))Sxj(x)=0.
ByVar(ϵ(x))=σ2, (3.2), and (3.6), we obtain
(3.7)Var⁡(f(x)-f′(x))=E(∑xj∈Xϵ(xj)Sxj(x))2=σ2∑xj∈X|Sxj(x)|2≤Mσ2.Remark 3.2.
If we add some restricted conditions presented in [14] for generator ψ, that is,
(3.8)‖sup⁡Z∈Rd∣K(⋅+z,z)‖L1(Rd)<∞,lim⁡δ→0‖sup⁡Z∈Rd∣ωδK(⋅+z,z)‖L1(Rd)=0,
where ωδ(f)(x)=supx′∈[-δ,δ]|f(x+x′)-f(x)|, K(x,y)=∑k∈ℤψ(x-k)ψ̃(y-k) and {ψ̃(·-k)}k∈ℤ is the dual of ψ(·-k)}k∈ℤ, then it is easy to check that (3.2) holds in shift-invariant space. Song et al. obtained the restricted conditions such that (3.2) holds for bandlimited space in [15]. From Lemma  2.1 of [16], (3.2) holds for special shift-invariant, that is spline subspace.Theorem 3.3.
If the initial samples in the iterative approximation projection reconstruction algorithm as shown by Theorem2.1 are corrupted,  that is, {f(xi)+ϵ(xi)} for noise  ϵ={ϵ(xi)}, then  ∥f-f′∥ is bounded by the  ℓ2 norm of the noise. More precisely,
(3.9)‖f-f′‖≤δ1/211-γ‖P‖op∥‖ϵ‖l2,
where f′ is recovered via the iterative approximation projection reconstruction algorithm from corrupted samples {f(xi)+ϵ(xi)} and γ:=∥I-PQX∥op.Proof.
Let(3.10)f1′=PQXf1,fn+1′=PQX(f1-fn′)+fn′,
where f1=f+ϵ.
From the iterative (3.10),
(3.11)fn+1′-fn′=(I-PQX)(fn′-fn-1′)=⋯=(I-PQX)nf1′(n≥1).
Using Lemma  8.3 of [3], we may choose δ so small that
(3.12)γ:=‖I-PQX‖op<1.
By (3.4),(3.11), and (3.12), we have
(3.13)‖fn′-f‖2≤∑k=n+1∞‖(I-PQX)k(f1′-PQXϵ)‖L2+∑k=0n‖(I-PQX)kPQXϵ‖L2≤∑k=n+1∞γk‖f1′-PQXϵ‖L2+∑k=0nγk‖PQXϵ‖L2≤∑k=n+1∞γk‖f1′‖L2+∑k=0∞γk‖PQXϵ‖L2≤11-γ(γn+1‖f1′‖L2+‖PQXϵ‖L2)≤‖P‖opδ1/211-γ(γn+1‖(f(xi)+ϵ(xi))‖l2+‖(ϵ(xi))‖l2).
This implies that ∥f-f′∥≤δ1/21/(1-γ)∥P∥op∥ϵ∥ℓ2.Theorem 3.4.
Assume that the initial samples in the iterative approximation projection reconstruction algorithm as shown by Theorem2.1 are corrupted,  that is, {f(xi+δi)+ϵ(xi)} for noise  δ={δi} with  sup|δi|≤δ and  ϵ={ϵ(xi)}. If there exist  constants  L,M>0 such that
(3.14)∑xj∈X|ψ′(x+xj)|≤L<+∞,∑|Sxj(x)|2≤M<+∞,∀x∈R,
for the generator ψ and sampling set X, then
(3.15)|f(x)-f∞(x)|≤2M(α2δ2L2‖f‖2+∑n|ϵn|2),
where f∞ is recovered via the iterative approximation projection reconstruction algorithm from corrupted samples {f(xi+δi)+ϵ(xi)},{Sxj} as defined in Theorem 3.1 and α as defined in (2.3).Proof.
From (3.2) and (3.5), we have
(3.16)|f(x)-f∞(x)|2=|∑j[f(xj)-f(xj+δj)-ϵj]Sxj(x)|2≤∑j|f(xj)-f(xj+δj)-ϵj|2∑j|Sxj(x)|2≤2M(∑j|f(xj)-f(xj+δj)|2+∑j|ϵj|2).
Next, we will estimate∑j|f(xj)-f(xj+δj)|2.
By the Hölder inequality and (3.14),
(3.17)∑j|f(xj)-f(xj+δj)|2=∑j|∫0δjf′(t+xj)dt|2≤∑jδj∫0δj|f′(t+xj)|2dt≤δ∫0δ∑j|f′(t+xj)|2dt=δ∫0δ∑j|∑kc(k)ψ′(t+xj-k)|2dt≤δ2L2∑k|c(k)|2≤α2δ2L2‖f‖2.
The last inequality follows from (2.3).
So, we have(3.18)|f(x)-f∞(x)|2≤2(∑j|f(xj)-f(xj+δj)|2+∑j|ϵj|2)∑j|Sxj(x)|2≤2M(α2δ2L2‖f‖2+∑n|ϵn|2).Lastly, we will consider the numerical stability of the iterative algorithm.Theorem 3.5.
Assume that the numerical error innth iterative step in the iterative algorithm as shown in Theorem 2.1 is  ϵn, that is,
(3.19)f̃1=PQXf+ϵ1,f̃n+1=f̃1+(I-PQX)(f̃n)+ϵn+1.
Then, we have the following estimation
(3.20)‖f-f̃n‖L2≤(1+‖P‖opδ1/21-γ)((n-1)‖ϵ1‖L2+∑j=1n‖ϵj‖L2)+γn1-γ‖P‖opδ1/2‖(f(xj))‖l2,
where γ:=∥I-PQX∥op.Proof.
By induction, we obtainf̃n-fn=-∑k=1n-1(I-PQ)n-1-kPQXϵ̃k+ϵ̃n, where ϵ̃1=ϵ1 and ϵ̃k=kϵ1+ϵ2+⋯+ϵk for k≥2.
Using Lemma  8.3 of [3], we may choose δ so small such that (3.12) holds.
Therefore,(3.21)‖f̃n-fn‖L2=∑k=1n-1‖(I-PQX)n-1-kPQXϵ̃k‖L2+‖ϵ̃n‖L2≤∑k=1n-1γn-1-k‖P‖opδ1/2‖ϵ̃k‖L2+‖ϵ̃n‖L2≤∑k=1n-1γn-1-k‖P‖opδ1/2(k‖ϵ1‖L2+∑j=2k‖ϵj‖L2)+n‖ϵ1‖L2+∑j=2n‖ϵj‖L2≤(1+‖P‖opδ1/21-γ)((n-1)‖ϵ1‖L2+∑j=1n‖ϵj‖L2).
The iterative algorithm converges exponentially too, precisely(3.22)‖fn-f‖≤γn1-γ‖f1‖.
In fact, by the iterative algorithm(3.23)fn+1-fn=(I-PQX)(fn-fn-1)=⋯=(I-PQX)nf1,(n≥1).
From (3.12), we have ∥fn-f∥≤γn/(1-γ)∥f1∥.
Combining (3.21) with (3.22), we have
(3.24)‖f-f̃n‖L2≤‖f̃n-fn‖L2+‖fn-f‖L2≤(1+‖P‖opδ1/21-γ)((n-1)‖ϵ1‖L2+∑j=1n‖ϵj‖L2)+γn1-γ‖f1‖≤(1+‖P‖opδ1/21-γ)((n-1)‖ϵ1‖L2+∑j=1n‖ϵj‖L2)+γn1-γ‖P‖opδ1/2‖(f(xj))‖l2.



---

*Source: 214213-2010-11-14.xml*