Adaptive Filter | ADPCM | ADSP | ADSP-2181 | Aliasing | AMR | Anti-Aliasing | ARMA | Autocorrelation | AutoCovariance | Beamforming | Bessel | Blackfin | Butterworth | C6713 | CCS | Chebyshev | CIC Filter | Circular Convolution | Code Composer Studio | Comb Filter | Compression | Convolution | Cross Correlation | DCT | Decimation | Deconvolution | Demodulation | DM642 | DSP Boards | DSP/BIOS | DTMF | Echo Cancellation | Equalization | Equalizer | ETSI | EZLITE (Ez-kit Lite) | FFT | FFTW | FIR Filter | Fixed Point | FSK | G.711 | G.723 | G.729 | Gaussian Noise | Goertzel | GPIO | Hilbert Transform | IFFT | IIR Filter | Interpolation | Invariance | JTAG | Kalman | Laplace Transform | Levinson | LPC | McBSP | MIPS | Modulation | MPEG | Multirate | Notch Filter | Nyquist | OFDM | Oversampling | Pink Noise | Pitch | PLL | Polyphase | QAM | QDMA | Quantization | Quantizer | Radar | Random Noise | Reed Solomon | Remez | Resampling | RTDX | Sampling | Sharc | TI C6711 | Undersampling | Viterbi | Wavelets | White Noise | Wiener Filter | Windowing | XDS510PP | Z Transform

I have two discrete signals A(x), B(x). (x = 1..10000).
They are similar looking but are shifted in (x) and and
scaled. Is there a way to calculate the transformation
scalars c,d such that
    cA(x) + d  is as near to B(x) 
as possible in some norm.

Is this problem known by some specific name in DSP. 
Where can i find more literature on it. Any hints
on how to solve the problem fast. I cant afford to
spend more than O(nlogn) on the two signals. 
(Here n = 10000)

Thanks,
--Elijah

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.

"Elijah Bailey" <g...@hotmail.com> wrote in message
news:e...@posting.google.com...
> I have two discrete signals A(x), B(x). (x = 1..10000).
> They are similar looking but are shifted in (x) and and
> scaled. Is there a way to calculate the transformation
> scalars c,d such that
>     cA(x) + d  is as near to B(x)
> as possible in some norm.
>
> Is this problem known by some specific name in DSP.
> Where can i find more literature on it. Any hints
> on how to solve the problem fast. I cant afford to
> spend more than O(nlogn) on the two signals.
> (Here n = 10000)

Homework, eh?

You mean this:
One is a scaled copy of the other and is shifted relative to the other?

It would seem that "c" takes care of the scaling, doesn't it?
This leaves the question then about the shift.

Why would adding a constant "d" have anything to do with a shift in x?
Why are A and B upper case?  Does that have some significance?

What norm?  We can use Fred's norm that states if d=0 then cA(x-y)>B(x) as
y>K where K is the shift in x between A and B.  :-)

Given your statement of the problem, here's an interesting question (I
think):

Given that B(x) is a scaled and x-shifted version of A(x) (where the shift
is not zero and is otherwise arbitrary), what functions "A(x)" allow a B(x)
that exactly satisfy the expression:

B(x)=cA(x) + d

Off hand, I can't think of any.

Now, why do I think that this is a distorted version of a homework question
that is aimed at asking to apply the shifting and scaling properties of a
Fourier Transform?

Fred

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.

> 
> Homework, eh?
> 

I'm glad that this looks like a HW problem. :)
I wish i had taken a DSP course. 

> You mean this:
> One is a scaled copy of the other and is shifted relative to the other?
> 

Not exactly. One is a scaled copy of the other and shifted relative to 
the other with some added noise. 

> It would seem that "c" takes care of the scaling, doesn't it?

Yes.

> This leaves the question then about the shift.
> 
> Why would adding a constant "d" have anything to do with a shift in x?

Sorry, My mistake. 

> Why are A and B upper case?  Does that have some significance?

Nope.

> 
> What norm?  

L2 for instance. The area in the difference of A and B?

> We can use Fred's norm that states if d=0 then cA(x-y)>B(x) as
> y>K where K is the shift in x between A and B.  :-)
> 

So, the problem is 

Find c,d such that
cA(x-d) - B(x) is minimized in say L2 norm ? Pick a meaningful norm
if that makes life easier. 

> Given your statement of the problem, here's an interesting question (I
> think):
> 
> Given that B(x) is a scaled and x-shifted version of A(x) (where the shift
> is not zero and is otherwise arbitrary), what functions "A(x)" allow a B(x)
> that exactly satisfy the expression:
> 
> B(x)=cA(x) + d
> 

Note that there is an error term also involved. A and B are not
exactly shifted and scaled copies of each other. 

> Off hand, I can't think of any.
> 
> Now, why do I think that this is a distorted version of a homework question
> that is aimed at asking to apply the shifting and scaling properties of a
> Fourier Transform?
> 
> Fred

I will read up more about FTs :)

Thanks,
--Elijah

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.

"Elijah Bailey" <g...@hotmail.com> wrote in message
news:e...@posting.google.com...
> >
> > Homework, eh?
> >
>
> I'm glad that this looks like a HW problem. :)
> I wish i had taken a DSP course.

Not homework?  OK, then:

You are looking for the point of maximal magnitude in the cross-correlation
function. The magnitude at that point is your scaling factor, and the
abscissa is your time shift. See:

http://mathworld.wolfram.com/Cross-Correlation.html

As noted in the link, cross-correlation can be reduced to convolution, and
convolutions can be evaluated efficiently using Fourier transforms:

http://mathworld.wolfram.com/ConvolutionTheorem.html

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.

I knew about the cross correlation,
but i thought it could only give an x-shift. 
I understood it as, for every x-shift, find the correlation.

How would i extract the scale parameter from correlation.

Let A and B be signals of length n. Lets suppose we compute the
cross-correlation of A and B in C whose length is 2n -1.  How
does one extract the shift and scale infor from C?

Thanks,
--Elijah

"Matt Timmermans" <m...@sympatico.nospam-remove.ca> wrote in message
news:<lSs7c.5485$r...@news20.bellglobal.com>...
> "Elijah Bailey" <g...@hotmail.com> wrote in message
> news:e...@posting.google.com...
> > >
> > > Homework, eh?
> > >
> >
> > I'm glad that this looks like a HW problem. :)
> > I wish i had taken a DSP course.
> 
> Not homework?  OK, then:
> 
> You are looking for the point of maximal magnitude in the cross-correlation
> function. The magnitude at that point is your scaling factor, and the
> abscissa is your time shift. See:
> 
> http://mathworld.wolfram.com/Cross-Correlation.html
> 
> As noted in the link, cross-correlation can be reduced to convolution, and
> convolutions can be evaluated efficiently using Fourier transforms:
> 
> http://mathworld.wolfram.com/ConvolutionTheorem.html

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.

"Elijah Bailey" <g...@hotmail.com> wrote in message
news:e...@posting.google.com...
> I knew about the cross correlation,
> but i thought it could only give an x-shift.
> I understood it as, for every x-shift, find the correlation.
>
> How would i extract the scale parameter from correlation.

Let |A|^2 be sum(A[x]^2), your maximal correlation be c, and the best time
shift be d.

Then, s=c/|A|^2 is the scale factor that minimizes the L2 difference between
sA(x) and B(x-d),
and s=c/|B|^2 minimizes the L2 difference between A(x) and sB(x-d).

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.

"Elijah Bailey" <g...@hotmail.com> wrote in message
news:e...@posting.google.com...
> > This leaves the question then about the shift.
> >
> > Why would adding a constant "d" have anything to do with a shift in x?
>
> Sorry, My mistake.
>

OK, just to be complete, you meant:

cA(x-d) ~ B(x) + n(x)     ?

And you need to find c and d.

Matt has addressed this nicely...

Fred

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.

Thanks a lot Matt

"Matt Timmermans" <m...@sympatico.nospam-remove.ca> wrote in message
news:<PUC7c.7959$A...@news20.bellglobal.com>...
> "Elijah Bailey" <g...@hotmail.com> wrote in message
> news:e...@posting.google.com...
> > I knew about the cross correlation,
> > but i thought it could only give an x-shift.
> > I understood it as, for every x-shift, find the correlation.
> >
> > How would i extract the scale parameter from correlation.
> 
> Let |A|^2 be sum(A[x]^2), your maximal correlation be c, and the best time
> shift be d.
> 
> Then, s=c/|A|^2 is the scale factor that minimizes the L2 difference between
> sA(x) and B(x-d),
> and s=c/|B|^2 minimizes the L2 difference between A(x) and sB(x-d).

______________________________
New DSP Code Snippets Section now Live.   Learn more about the reward program for contributors here.