Decomposition into known components?

I have a signal that is composed of a few (2 or 3) known shapes, in
different (unknown) proportions.

If I define the components as:

    Rn[t]

then the combined signal is:

   s[t] = SUMovern(x[n]*Rn[t])   (sum over n) .....(1)

where x[n] are the (unknown) proportions of each component.

If I correlate (computing the zero-lag coefficent only) with each
component in turn:

   c[m] = SUMovert(Rn[t]*s[t])  (sum over t)  .....(2)

Then (using (1) in (2)) this is:

  c[m] = SUMovert(Rn[t]*SUMovern(x[n]*Rn[t])  ....(3)

and I can rewrite this as:

  c[m] = SUMovern(x[n]*SUMovert(Rm[t]*Rn[t])   ...(4)

and if I define:

  R[m][n] = SUMovert(Rm[t]*Rn[t])   ...(5)

(4) can be re-written:

  c[m] = SUMovern(x[n]*R[m][n])    ...(6)

which is just a matrix equation:

   c = x.R   ....(7)

and can be easily solved algebraically.

So, provided I know all the terms R[m][n], and I can measure all the c
[m], I can compute the unknwon proportions x[n].

OK, I think I just outlined a generic transform in a leaden way. :-)

But my questions:

a) is the above reasoning correct?
b) what is this traditionally called?
c) what is its sensitivitiy to noise?

Thanks,

Chris
=========================
Chris Bore
BORES Signal Processing

Chris Bore <chris.bore@gmail.com> wrote:
< I have a signal that is composed of a few (2 or 3) known 
< shapes, in different (unknown) proportions.
(snip)
 
<   s[t] = SUMovern(x[n]*Rn[t])   (sum over n) .....(1)
 
< where x[n] are the (unknown) proportions of each component.
 
(snip)
 
< and I can rewrite this as:
 
<  c[m] = SUMovern(x[n]*SUMovert(Rm[t]*Rn[t])   ...(4)
 
(snip)
 
< which is just a matrix equation:
 
<   c = x.R   ....(7)
 
< and can be easily solved algebraically.

If the number of sample points is equal to the number of 
components, then it is an ordinary matrix equation which can be
solved by inverting the matrix.  It is is not singular, you have
a solution.  
 
(snip)
 
< a) is the above reasoning correct?
< b) what is this traditionally called?
< c) what is its sensitivitiy to noise?

Sensitivity to noise depends on how close it is to singular.

As I believe you intend the number of components to be much
smaller than the number of samples, you might look at SVD.
(The description in Numerical Recipes isn't so bad.)  
For the components smaller than samples case you get the least
squares solution, which is what most people do for fitting problems.

As for noise, least squares averages out noise assuming that
there are enough samples.

-- glen

On May 26, 12:55&#4294967295;pm, Chris Bore <chris.b...@gmail.com> wrote:
> I have a signal that is composed of a few (2 or 3) known shapes, in
> different (unknown) proportions.
>
> If I define the components as:
>
> &#4294967295; &#4294967295; Rn[t]
>
> then the combined signal is:
>
> &#4294967295; &#4294967295;s[t] = SUMovern(x[n]*Rn[t]) &#4294967295; (sum over n) .....(1)
>
> where x[n] are the (unknown) proportions of each component.
>
> If I correlate (computing the zero-lag coefficent only) with each
> component in turn:
>
> &#4294967295; &#4294967295;c[m] = SUMovert(Rn[t]*s[t]) &#4294967295;(sum over t) &#4294967295;.....(2)
>
> Then (using (1) in (2)) this is:
>
> &#4294967295; c[m] = SUMovert(Rn[t]*SUMovern(x[n]*Rn[t]) &#4294967295;....(3)
>
> and I can rewrite this as:
>
> &#4294967295; c[m] = SUMovern(x[n]*SUMovert(Rm[t]*Rn[t]) &#4294967295; ...(4)
>
> and if I define:
>
> &#4294967295; R[m][n] = SUMovert(Rm[t]*Rn[t]) &#4294967295; ...(5)
>
> (4) can be re-written:
>
> &#4294967295; c[m] = SUMovern(x[n]*R[m][n]) &#4294967295; &#4294967295;...(6)
>
> which is just a matrix equation:
>
> &#4294967295; &#4294967295;c = x.R &#4294967295; ....(7)
>
> and can be easily solved algebraically.
>
> So, provided I know all the terms R[m][n], and I can measure all the c
> [m], I can compute the unknwon proportions x[n].
>
> OK, I think I just outlined a generic transform in a leaden way. :-)
>
> But my questions:
>
> a) is the above reasoning correct?
> b) what is this traditionally called?
> c) what is its sensitivitiy to noise?
>
> Thanks,
>
> Chris
> =========================
> Chris Bore
> BORES Signal Processing

Chris, you might also want to look into \ell_1 minimization
of the above matrix equation.  Since you know apriori that
you have a small number of components, then this may
be necessary if the shapes themselves are not orthogonal.

You don't state exactly what prior information you have,
but in many cases if you know that your solution has only
a few components, then you may have to minimize the
number of non-zero components (i.e., the \ell_0 norm).
However, this is NP-complete, so you can convexify
the problem and consider the \ell_1 norm instead.

Does this sound more like your problem statement
to you?

Julius

I had lunch with a friend today that is working on a project that
requires DTMF decoding and discovered that many of the
single chip solutions he used several years ago are not available.

I speculated that now that embedded processors are getting
more powerful that DTMF decoding was being implemented in
software.

Any favourite links free or commercial solutions.  Hardware
or software.

Regards,

--
Walter Banks
Byte Craft Limited
http://www.bytecraft.com

Walter Banks wrote:

> I had lunch with a friend today that is working on a project that
> requires DTMF decoding and discovered that many of the
> single chip solutions he used several years ago are not available.
> 
> I speculated that now that embedded processors are getting
> more powerful that DTMF decoding was being implemented in
> software.
> 
> Any favourite links free or commercial solutions.  Hardware
> or software.

http://www.abvolt.com/research/Multitone%20detect-IEEE.pdf

http://www.abvolt.com/products/telephone.htm



Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com

Walter Banks wrote:
> I had lunch with a friend today that is working on a project that
> requires DTMF decoding and discovered that many of the
> single chip solutions he used several years ago are not available.
> 
> I speculated that now that embedded processors are getting
> more powerful that DTMF decoding was being implemented in
> software.
> 
> Any favourite links free or commercial solutions.  Hardware
> or software.

1) Please start a new thread when appropriate. What you did is called 
"highjacking">

2) Your perspective is off. At least 5 years ago, there was DTMF code 
for an 8-bit microcontroller on the Rice U web site.

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

Jerry Avins wrote:

> 1)  My bad. Finger problem on my part.

> 2) Your perspective is off. At least 5 years ago, there was DTMF code
> for an 8-bit microcontroller on the Rice U web site.

Was this the Z80 version from a few years ago? I tried to
track down a link.

There were a couple MELPs M16xx solutions a few years ago, one
I know of was designed into a POS terminal that passed all the
telephone signaling requirements.

I am looking for more recent developments.

Walter Banks

Chris Bore wrote:

> I have a signal that is composed of a few (2 or 3) known shapes,
> in different (unknown) proportions.

The derivation becomes a bit shorter if you start out in a matrix 
setting. Take the components matrix  R = R[n,t]  and the coefficient 
vector  x.  Then the signal vector is

  s = R^T x  (your eq. 1)

and correlating with the components means writing

  c = Rs = (R R^T) x  (your eq. 7).

This is the set of eq. 1's Normal equations of linear least squares 
theory.


Martin

-- 
Quidquid latine scriptum est, altum videtur.

 >> many of the single chip solutions he used several
 >> years ago are not available.
These were SC-ICs from the late 70ies.
The market for such DTMF-decoder ICs has shrunk. And
typical suppliers have given up on production
of SC-chips, probably because the size of these chips
is now uncompetitive.
   MT8870 variants are still available from Holtek. But
internally they are now digital. Resulted in some
incompatibility: the capacitors for the crystal are no
longer integrated, the op-amps are unstable if required
to drive additional ICs.

> Was this the Z80 version from a few years ago? I tried to
> track down a link.
Probably that one:
http://www.embeddedFORTH.de/temp/dtmf3.pdf
Text is in german, but pictures should be clear enough.
Implemented on a 68HC908 ( 8MHz bus ; 3kByte FLASH ;
256 byte RAM ). Due to the appetite for RAM ( to
avoid signed multiplication ) thats not a small
controller. And at 8 MHz its not a background task,
100% of the time working on it.

MfG  JRD

Walter Banks wrote:
> 
> Jerry Avins wrote:
> 
>> 1)  My bad. Finger problem on my part.
> 
>> 2) Your perspective is off. At least 5 years ago, there was DTMF code
>> for an 8-bit microcontroller on the Rice U web site.
> 
> Was this the Z80 version from a few years ago? I tried to
> track down a link.
> 
> There were a couple MELPs M16xx solutions a few years ago, one
> I know of was designed into a POS terminal that passed all the
> telephone signaling requirements.
> 
> I am looking for more recent developments.

It was on the Rice website. I've lost the link.

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