FFT from incomplete data

Hi, 

I am computing the spectrum of a signal. Sometimes I don't have the full data available because of communication losses. It is clear, that I can't show the correct spectrum, but I want to show something that is as close as possible.

Is there a mathematical correct way to do this ?

Is there a way to do it without adding frequencies not present in the original signal ?

you can fit a polynomial across the gap to match end points and derivatives
(use Lagrange polynomials to estimate the derivative in either end point).

If that's not good enough, calculate all "allowed" waveforms (the bins in
your FFT that you expect to be non-zero) and fit to endpoints and
derivatives. Matlab's backslash operator comes in handy.

Both are "ad-hoc" solutions but maybe good enough for real-world problems.

Are the communication losses "bursty"? Are you missing large chunks of data?

Sometimes the error correction system will include an interleaving scheme that spreads bursty errors out in time, which would make the interpolation method suggested above a good approach.

Bob

>Hi, 
>
>I am computing the spectrum of a signal. Sometimes I don't have the full
data available because of communication losses. It is clear, that I can't
show the correct spectrum, but I want to show something that is as close as
possible.
>
>Is there a mathematical correct way to do this ?
>
>Is there a way to do it without adding frequencies not present in the
original signal ?
>
What exactly is your impairment? Do you lose individual samples, or bursts?
Do you know exactly how many samples you have lost?

If you lose samples at one end of the block, you can probably change your
windowing function to match, and run the transform. If you lose individual
samples mid-block, and know they are missing, you can probably apply a
reasonable interpolator. If you lose groups of samples mid-block I guess
you are sunk.

Steve

TomTurbo <thomaslehner72@gmail.com> writes:

> Hi, 
>
> I am computing the spectrum of a signal. Sometimes I don't have the
> full data available because of communication losses. It is clear, that
> I can't show the correct spectrum, but I want to show something that
> is as close as possible.
>
> Is there a mathematical correct way to do this ?
>
> Is there a way to do it without adding frequencies not present in the
> original signal ?

I had investigated doing this quite some time ago and found FIR-based
methods, but I'm having a hard time finding any information on it now. 
However, I did find one reference on the subject:

  http://search.informit.com.au/documentSummary;dn=591107675619023;res=IELENG

It is not the same as linear, cubic, spline, etc. interpolation. Hope
this helps.
-- 
Randy Yates
Digital Signal Labs
http://www.digitalsignallabs.com

TomTurbo <thomaslehner72@gmail.com> wrote:
 
> I am computing the spectrum of a signal. Sometimes I don't have 
> the full data available because of communication losses. 
> It is clear, that I can't show the correct spectrum, but I 
> want to show something that is as close as possible.

Is your input periodic with a known period? 

Is it band-limited with a known bandwidth?
 
> Is there a mathematical correct way to do this ?

FFT gives you the sum of N basis functions that matches your
input at N points. In mathematical terms, N equations and N
unknowns. If you have M equations (from M data points) you
can't solve for N>M unknowns.

If you have more data points than unknowns (coefficients)
you can solve it as a least-squares problem. You lose the
first F (Fast) but the problem does have a solution.
 
> Is there a way to do it without adding frequencies not present 
> in the original signal ?

Nyquist doesn't require N equally spaces sample points over
the interval, but it does require N. If you have fewer points,
and your signal is band-limited appropriately, the problem
still has a solution. Otherwise, the solution is underdetermined.

Numerically, when you have either more or less data points than
unknowns, SVD allows for a solution. In the more data points case,
you get the least-squares solution. When less, you get the closest
I can think of to your "without adding frequencies". 

-- glen

On Tuesday, November 13, 2012 3:22:37 AM UTC-6, TomTurbo wrote:
> Hi, I am computing the spectrum of a signal. Sometimes I don't have the full data available because of communication losses. It is clear, that I can't show the correct spectrum, but I want to show something that is as close as possible. Is there a mathematical correct way to do this ? Is there a way to do it without adding frequencies not present in the original signal ?

This may be _off-the-wall_, but take a look at compressed sensing/compressed sampling. A bunch of research has been done recently on reconstruction from sparce data. In the _mathematical_ world, you might find some info on matrix reconstruction from sparce data in the area of harmonic analysis.

Regards.

On Tue, 13 Nov 2012 01:22:36 -0800, TomTurbo wrote:

> Hi,
> 
> I am computing the spectrum of a signal. Sometimes I don't have the full
> data available because of communication losses. It is clear, that I
> can't show the correct spectrum, but I want to show something that is as
> close as possible.
> 
> Is there a mathematical correct way to do this ?
> 
> Is there a way to do it without adding frequencies not present in the
> original signal ?

The mathematically correct way to do this is to treat it as a detection 
and estimation problem where the only measurements taken are the ones you 
have.  I couldn't tell you off the top of my head what the answer would 
be, but it's probably pretty close to interpolation and an FFT in the 
case of sporadically missing data points.

Technically you're not adding frequencies not present in the original 
signal -- but only because aliasing doesn't add spectral components, it 
just shifts them around.  The action of deleting data points _is_ going 
to cause some oddball aliasing-like effects; this is unavoidable.

The more redundancy you start with, the better your answer will be at the 
end.

-- 
Tim Wescott
Control system and signal processing consulting
www.wescottdesign.com

On 11/13/12 10:34 AM, glen herrmannsfeldt wrote:
> TomTurbo<thomaslehner72@gmail.com>  wrote:
>
>> I am computing the spectrum of a signal. Sometimes I don't have
>> the full data available because of communication losses.
>> It is clear, that I can't show the correct spectrum, but I
>> want to show something that is as close as possible.
>
> Is your input periodic with a known period?
>
> Is it band-limited with a known bandwidth?
>

these are important questions.

>> Is there a mathematical correct way to do this ?

not much hope if your input is white noise.  you'll have no idea how to 
reconstruct, even approximately, what was in the gap.

but if you *do* have some idea of what the spectrum had been, over the 
long term, you can use Linear Predictive Coding (rather than polynomial 
interpolation which essentially makes no use of this information) to 
extend the data on both sides of the gap into the gap.  then apply some 
kinda cross-fading from the interpolated data extended from the left to 
the interpolated data from the right.


-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

On Tue, 13 Nov 2012 14:02:27 -0500, robert bristow-johnson wrote:

> On 11/13/12 10:34 AM, glen herrmannsfeldt wrote:
>> TomTurbo<thomaslehner72@gmail.com>  wrote:
>>
>>> I am computing the spectrum of a signal. Sometimes I don't have the
>>> full data available because of communication losses.
>>> It is clear, that I can't show the correct spectrum, but I want to
>>> show something that is as close as possible.
>>
>> Is your input periodic with a known period?
>>
>> Is it band-limited with a known bandwidth?
>>
>>
> these are important questions.
> 
>>> Is there a mathematical correct way to do this ?
> 
> not much hope if your input is white noise.  you'll have no idea how to
> reconstruct, even approximately, what was in the gap.
> 
> but if you *do* have some idea of what the spectrum had been, over the
> long term, you can use Linear Predictive Coding (rather than polynomial
> interpolation which essentially makes no use of this information) to
> extend the data on both sides of the gap into the gap.  then apply some
> kinda cross-fading from the interpolated data extended from the left to
> the interpolated data from the right.

Huh.  I hadn't thought of that.

A Kalman filter will give you a direct answer for missing data in the 
middle of such a sequence.  Assuming that you can model the behavior of 
the signal as a linear lumped-constant system excited by white Gaussian 
noise, then just a plain ol' Kalman will do it just fine, and give you a 
least-squares approximation of the correct answer, too.

But, if you're going to do that much work it may be worth while to start 
out by treating it as that general estimation problem that I mentioned in 
my reply.

-- 
Tim Wescott
Control system and signal processing consulting
www.wescottdesign.com