Piecewise constant approximation

Let s(t) be a continuous bandlimited signal. Let p(t) be its best
piecewise constant approximation on the uniformly partitioned unit
interval [0,1],

i.e  p(t) = \sum_{i=1}^n c_i I_i(t)

where I_i(t) is the indicator function which takes 1 on the interval
[(i-1)/n , i/n) and 0 elsewhere.

Now how does the MSE ||s(t)-p(t)||^2 vary with n ?

Thanks,
er

erudite wrote:

> Let s(t) be a continuous bandlimited signal. Let p(t) be its best
> piecewise constant approximation on the uniformly partitioned unit
> interval [0,1],
>
> i.e  p(t) = \sum_{i=1}^n c_i I_i(t)
>
> where I_i(t) is the indicator function which takes 1 on the interval
> [(i-1)/n , i/n) and 0 elsewhere.
>
> Now how does the MSE ||s(t)-p(t)||^2 vary with n ?

It doesn't if c_i = <a constant> for all i.

You need to know something about how the c_i are selected before you
can answer the question. For example: what does "best" mean in the
phrase "best piecewise constant approximation"?  Does it mean minimum
MSE?

Are there any restrictions on s(t) other than that it is continuous and
bandlimited?

Ciao,

Peter K.

yeah I meant best MSE fit.

I think the c_i will be given by

c_i = n int_{ (i-1)/n }^{i/n} s(t) dt

and no there are no other restrictions on s(t).

Peter K. wrote:
> erudite wrote:
>
> > Let s(t) be a continuous bandlimited signal. Let p(t) be its best
> > piecewise constant approximation on the uniformly partitioned unit
> > interval [0,1],
> >
> > i.e  p(t) = \sum_{i=1}^n c_i I_i(t)
> >
> > where I_i(t) is the indicator function which takes 1 on the interval
> > [(i-1)/n , i/n) and 0 elsewhere.
> >
> > Now how does the MSE ||s(t)-p(t)||^2 vary with n ?
>
> It doesn't if c_i = <a constant> for all i.
>
> You need to know something about how the c_i are selected before you
> can answer the question. For example: what does "best" mean in the
> phrase "best piecewise constant approximation"?  Does it mean minimum
> MSE?
>
> Are there any restrictions on s(t) other than that it is continuous and
> bandlimited?
> 
> Ciao,
> 
> Peter K.

Hi Peter,

I choose the MMSE approximation to p(t) in the set of
piecewise-constant-functions with n equal partitions of the unit
interval, i.e in

F = { f : f(t) = \sum_{i=1}^n c_i I_i(t) }

where c_i is real and I_i(t) is the indicator function which takes 1 on
the interval
[(i-1)/n , i/n) and 0 elsewhere

It is easy to show that

c_i = n \int_{(i-1)/n}^{1/n} s(t) dt

Hope this makes more sense. And yeah, there are no other assumptions on
s(t). If I assume s(t) to be Lipschitz, its easy to show that
approximation rate is 1/n^2

thanks


Peter K. wrote:
> erudite wrote:
>
> > Let s(t) be a continuous bandlimited signal. Let p(t) be its best
> > piecewise constant approximation on the uniformly partitioned unit
> > interval [0,1],
> >
> > i.e  p(t) = \sum_{i=1}^n c_i I_i(t)
> >
> > where I_i(t) is the indicator function which takes 1 on the interval
> > [(i-1)/n , i/n) and 0 elsewhere.
> >
> > Now how does the MSE ||s(t)-p(t)||^2 vary with n ?
>
> It doesn't if c_i = <a constant> for all i.
>
> You need to know something about how the c_i are selected before you
> can answer the question. For example: what does "best" mean in the
> phrase "best piecewise constant approximation"?  Does it mean minimum
> MSE?
>
> Are there any restrictions on s(t) other than that it is continuous and
> bandlimited?
> 
> Ciao,
> 
> Peter K.

erudite wrote:
> Hi Peter,
>
> I choose the MMSE approximation to p(t) in the set of
> piecewise-constant-functions with n equal partitions of the unit
> interval, i.e in
>
> F = { f : f(t) = \sum_{i=1}^n c_i I_i(t) }
>
> where c_i is real and I_i(t) is the indicator function which takes 1 on
> the interval
> [(i-1)/n , i/n) and 0 elsewhere
>
> It is easy to show that
>
> c_i = n \int_{(i-1)/n}^{1/n} s(t) dt
>
> Hope this makes more sense. And yeah, there are no other assumptions on
> s(t). If I assume s(t) to be Lipschitz, its easy to show that
> approximation rate is 1/n^2

If s is bandlimited it is also analytic (and therefore Lipschitz). I
agree that the approximation error || s(t) - p_n(t) ||^2 is O(1/n^2) as
n -> infinity (develop s into a Taylor series for each interval).

Regards,
Andor

I don't understand "If s is bandlimited it is also analytic" - why is
that so ?

Can you please elaborate ?

Andor wrote:
> erudite wrote:
> > Hi Peter,
> >
> > I choose the MMSE approximation to p(t) in the set of
> > piecewise-constant-functions with n equal partitions of the unit
> > interval, i.e in
> >
> > F = { f : f(t) = \sum_{i=1}^n c_i I_i(t) }
> >
> > where c_i is real and I_i(t) is the indicator function which takes 1 on
> > the interval
> > [(i-1)/n , i/n) and 0 elsewhere
> >
> > It is easy to show that
> >
> > c_i = n \int_{(i-1)/n}^{1/n} s(t) dt
> >
> > Hope this makes more sense. And yeah, there are no other assumptions on
> > s(t). If I assume s(t) to be Lipschitz, its easy to show that
> > approximation rate is 1/n^2
>
> If s is bandlimited it is also analytic (and therefore Lipschitz). I
> agree that the approximation error || s(t) - p_n(t) ||^2 is O(1/n^2) as
> n -> infinity (develop s into a Taylor series for each interval).
> 
> Regards,
> Andor

erudite wrote:
> I don't understand "If s is bandlimited it is also analytic" - why is
> that so ?
>
> Can you please elaborate ?

Erudite,

assume s(t) is a real signal with Fourier transformed S(w) and

s(t) = int_{-B}^B S(w) exp(i w t) dw,           (1)

where B is the bandwidth of s(t) (modulo some scaling factors). Using
the Leibniz integral rule, you can see that differentiation of s only
leads to a differentiation of exp.

However, it should also be noted that not all bandlimited signals can
be written in the form (1). Specifically, one can construct bandlimited
signals that are _nowhere_ differentiable (let alone analytic). For
such signals however, the roundtrip time domain -> frequency domain ->
time domain is not the identity. I'm not quite sure but would say that
the condition "bandlimited & continuous" rules such cases out, ie.
"bandlimited & continuous => analytic".

Hope that helps,
Andor

Andor wrote:
> erudite wrote:
>> I don't understand "If s is bandlimited it is also analytic" - why is
>> that so ?
>>
>> Can you please elaborate ?
> 
> Erudite,
> 
> assume s(t) is a real signal with Fourier transformed S(w) and
> 
> s(t) = int_{-B}^B S(w) exp(i w t) dw,           (1)
> 
> where B is the bandwidth of s(t) (modulo some scaling factors). Using
> the Leibniz integral rule, you can see that differentiation of s only
> leads to a differentiation of exp.
> 
> However, it should also be noted that not all bandlimited signals can
> be written in the form (1). Specifically, one can construct bandlimited
> signals that are _nowhere_ differentiable (let alone analytic). For
> such signals however, the roundtrip time domain -> frequency domain ->
> time domain is not the identity. I'm not quite sure but would say that
> the condition "bandlimited & continuous" rules such cases out, ie.
> "bandlimited & continuous => analytic".

Eh? How can a signal with a discontinuity be bandlimited?

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

Jerry Avins wrote:
> Andor wrote:
> > erudite wrote:
> >> I don't understand "If s is bandlimited it is also analytic" - why is
> >> that so ?
> >>
> >> Can you please elaborate ?
> >
> > Erudite,
> >
> > assume s(t) is a real signal with Fourier transformed S(w) and
> >
> > s(t) = int_{-B}^B S(w) exp(i w t) dw,           (1)
> >
> > where B is the bandwidth of s(t) (modulo some scaling factors). Using
> > the Leibniz integral rule, you can see that differentiation of s only
> > leads to a differentiation of exp.
> >
> > However, it should also be noted that not all bandlimited signals can
> > be written in the form (1). Specifically, one can construct bandlimited
> > signals that are _nowhere_ differentiable (let alone analytic). For
> > such signals however, the roundtrip time domain -> frequency domain ->
> > time domain is not the identity. I'm not quite sure but would say that
> > the condition "bandlimited & continuous" rules such cases out, ie.
> > "bandlimited & continuous => analytic".
>
> Eh? How can a signal with a discontinuity be bandlimited?

Consider the following function:

s(t) = 1, if t is rational, and s(t) = 0 if t is irrational.

The Fourier transform of s is equal to zero everywhere, and therefore
bandlimited. However, s is nowhere continuous. Note that you can add
s(t) to any another bandlimited function, without changing the
bandwidth, making the sum also very discontinuous.

Regards,
Andor

Andor wrote:
> Jerry Avins wrote:
>> Andor wrote:
>>> erudite wrote:
>>>> I don't understand "If s is bandlimited it is also analytic" - why is
>>>> that so ?
>>>>
>>>> Can you please elaborate ?
>>> Erudite,
>>>
>>> assume s(t) is a real signal with Fourier transformed S(w) and
>>>
>>> s(t) = int_{-B}^B S(w) exp(i w t) dw,           (1)
>>>
>>> where B is the bandwidth of s(t) (modulo some scaling factors). Using
>>> the Leibniz integral rule, you can see that differentiation of s only
>>> leads to a differentiation of exp.
>>>
>>> However, it should also be noted that not all bandlimited signals can
>>> be written in the form (1). Specifically, one can construct bandlimited
>>> signals that are _nowhere_ differentiable (let alone analytic). For
>>> such signals however, the roundtrip time domain -> frequency domain ->
>>> time domain is not the identity. I'm not quite sure but would say that
>>> the condition "bandlimited & continuous" rules such cases out, ie.
>>> "bandlimited & continuous => analytic".
>> Eh? How can a signal with a discontinuity be bandlimited?
> 
> Consider the following function:
> 
> s(t) = 1, if t is rational, and s(t) = 0 if t is irrational.
> 
> The Fourier transform of s is equal to zero everywhere, and therefore
> bandlimited. However, s is nowhere continuous. Note that you can add
> s(t) to any another bandlimited function, without changing the
> bandwidth, making the sum also very discontinuous.

Bah! A canard! That function doesn't even have a derivative. By the way, 
it's average value is zero. :-)

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������