Minimum number of partials to fit a set of points

Hi. I'm curious about the following problem. I have no immediate
pressing need for an answer, but here goes.

Let's say that we define a single cycle of a waveform to be from x=0 to
x=1. Similarly, we'll restrict the range of amplitude values to be
between y=-1 to y=1.

Given this it would be easy to create a gui where a user could use a
mouse to add a number of points to the rectangle bounded by (0,-1),
(0,1), (1,1), (1,-1).

It would be trivial to convert these points to a waveform by linear
interpolation between the points (I'm thinking "drawing straight
lines"). A smoother waveform could be achieved by using better
interpolation.

However, is there a simple method of finding the fewest number of
partials required to create a waveform that passes through each of the
points?

I could "solve" this using search-based techniques such as genetic
algorithms, simulated annealing, or similar. But of course these
methods wouldn't guarantee finding the smallest number of partials, and
would probably take a lot of computing time.

Any suggestions?

Cheers,

Ross-c

Before I answer: what is a partial?

Regards,
Andor

A sine wave. As in any periodic waveform can be reconstructed by a
fourier series. "Partial" is a name sometimes used in additive audio
synthesis.

Cheers,

Ross-c

> A sine wave. As in any periodic waveform can be reconstructed by a
> fourier series. "Partial" is a name sometimes used in additive audio
> synthesis.

Partials are like harmonics, but they don't appear on odd or even multiples
of the base frequency, but at any frequency.

Tim

"Tim" <tim@nospam.com> wrote in message 
news:oOO7e.134611$dP1.472479@newsc.telia.net...
>> A sine wave. As in any periodic waveform can be reconstructed by a
>> fourier series. "Partial" is a name sometimes used in additive audio
>> synthesis.
>
> Partials are like harmonics, but they don't appear on odd or even 
> multiples
> of the base frequency, but at any frequency.
>
> Tim
>
>
So you'd like to find the smallest number of sine waves that , added 
together will pass exactly through every point ,  sampling interval is 
irregular and you don't care what happens in the intervals between the 
defining points ?  Sounds really interesting. Please try not to fragment 
this thread, I'd like to know too.

Best of Luck - Mike
 

Tim, thanks for the correction. "Harmonic" is what I meant rather than
"Partial". I'm too used to thinking of being able to control the
frequencies of sine waves independently. However, in this question, I'd
like to know the smallest number of harmonics. The smallest number of
partials is a different problem. And, now I think about it, not the
problem I was interested in.

Cheers,

Ross-c

On 15 Apr 2005 03:46:05 -0700, clemenr@wmin.ac.uk wrote:

>>However, is there a simple method of finding the fewest number of
>>partials required to create a waveform that passes through each of the
>>points?
>>
>>I could "solve" this using search-based techniques such as genetic
>>algorithms, simulated annealing, or similar. But of course these
>>methods wouldn't guarantee finding the smallest number of partials, and
>>would probably take a lot of computing time.
>>
>>Any suggestions?


Working out of long-term memory here, but I think that the Notch
Fourier Transform might be what you're looking for.

-- Greg Berchin


	Notch Fourier transform
Tadokoro, Y.; Abe, K.;
Acoustics, Speech, and Signal Processing [see also IEEE
Transactions on Signal Processing], IEEE Transactions on
Volume 35,  Issue 9,  Sep 1987 Page(s):1282 - 1288 

Summary: This paper presents a new computational algorithm for the
Fourier transform at arbitrary frequencies. This algorithm, if an
input signal has r frequencies, can be implemented by one FIR
filter composed of r second-order digital notch filters
(2-DNF's....

--

	A new discrete Fourier transform for unevenly sampled data
Tadokoro, Y.; Nakamura, K.;
Acoustics, Speech, and Signal Processing, 1989. ICASSP-89., 1989
International Conference on
23-26 May 1989 Page(s):1007 - 1010 vol.2 

Summary: The authors derive a discrete Fourier transform (DFT)
algorithm for unevenly sampled data by generalizing the notch
Fourier transform (NFT) algorithm. First, a second-order digital
notch filter for unevenly sampled data (2-VNF) that eliminates one
fr.....

--

	Adaptive IIR notch filter by frequency estimation for
notch Fourier transform
Kudoh, N.; Tadokoro, Y.;
Signal Processing Proceedings, 1998. ICSP '98. 1998 Fourth
International Conference on
12-16 Oct. 1998 Page(s):490 - 493 vol.1 

Summary: This paper presents a method to compute Fourier
coefficients at arbitrary frequencies. The method is developed for
the case that prior knowledge of signal frequencies is not
accurate or the frequencies are time varying and additive white
noise exists.....

Thanks. In actual fact, the recommendation of fourier transform for
unevenly spaced data is very interesting, and not just for the question
I originally asked.

Cheers,

Ross-c

in article 1113574894.119281.156740@g14g2000cwa.googlegroups.com,
clemenr@wmin.ac.uk at clemenr@wmin.ac.uk wrote on 04/15/2005 10:21:

> Thanks. In actual fact, the recommendation of fourier transform for
> unevenly spaced data is very interesting, and not just for the question
> I originally asked.

actually, i think the problem is much simpler than that.  the context is
exactly one cycle of a periodic waveform, no?  the user specifies a series
of possibly unequally spaced points of this waveform.  1 point all by itself
would define a DC waveform.  3 points would define DC and the magnitude and
phase of the 1st harmonic.  5 points would define DC, and the magnitudes and
phases of the 1st and 2nd harmonic.

similar to fitting the curve in the remez exchange algorithm, this requires
solving a linear set of equations (since the magnitude and phase of a
harmonic can be represented as magnitudes applied to cos() and sin() for
that harmonic).

-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

clemenr@wmin.ac.uk wrote:
> Tim, thanks for the correction. "Harmonic" is what I meant rather than
> "Partial". I'm too used to thinking of being able to control the
> frequencies of sine waves independently. However, in this question, I'd
> like to know the smallest number of harmonics. The smallest number of
> partials is a different problem. And, now I think about it, not the
> problem I was interested in.

Then the solution is easy. Lay down a grid fine enough so tat every 
point lies "close enough" to a vertical line, read out the coordinates, 
and do a Fourier transform. You could treat the problem as a set of 
simultaneous equations.

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