Signal processing technique

• US 6,954,721 B2
• Filed: 01/31/2001
• Issued: 10/11/2005
• Est. Priority Date: 02/17/2000
• Status: Expired due to Term

• Current Assignee: Qinetiq Limited (QinetiQ Group PLC)
• Original Assignee: Qinetiq Limited (QinetiQ Group PLC)
• Inventors: Webber, Christopher J St C
• Primary Examiner(s): Hoff, Marc S.
• Assistant Examiner(s): O MALLEY, MARY CATHERINE
• Application Number:
  US10/182,912
• Publication Number:
  US 20030055610A1
• Time in Patent Office: 1,714 Days
• Field of Search: 375142-143, 375/150, 375/152, 375259-261, 375365-367, 375/343, 370514-515, 370/320, 370/335, 370/342, 370/441, 370/479, 702 57- 59, 702189-197
• US Class Current: 702/189
• CPC Class Codes: G06F 17/15 Correlation function computation including computation of convolution operations arithmetic circuits for sum of products per se, e.g. multiply-accumulators G06F7/5443; digital filters, e.g. FIR, IIR, adaptive filters H03H17/00
• CPC Class Codes: G06F 18/2134 based on separation criteria, e.g. independent component analysis

Abstract

A signal processing technique for generating separated signal components incorporates the steps of correlating basis vectors with input data to produce output vectors, applying a non-linear function to the output vectors to produce non-linearized vectors, and convolving the non-linearized vectors with the basis vectors to produce separated signal components. Each vector may comprise a set of one-dimensional channel vectors. Separated signal components are combined to form an input signal reconstruction and an anomaly signal indicating deviation of the reconstruction from the associated input signal. Basis vectors are determined by training which involves use of weighting factors referred to as basis scales. When used to scale separated signal components in the production of reconstruction vectors, basis scales have the effect of reducing a mean squared error between such vectors and associated input data used to derive them.

Claims

1. A signal processing technique for generating separated signal components incorporating the steps of:

correlating basis vectors with input data vectors to produce output vectors,

applying to the output vectors a non-linear function having a gradient to produce non-linearised output vectors, and

convolving the non-linearised output vectors with the basis vectors to produce separated signal components.

2. A signal processing technique according to claim 1 wherein data vectors and basis vectors are multi-dimensional and multi-dimensional convolution and correlation operations are implemented by:

a) arranging both data vectors and basis vectors as pluralities of one-dimensional signals referred to as channel vectors,

b) correlating or convolving each data vector channel vector with a corresponding basis vector channel vector to yield a plurality of one-dimensional correlation or convolution functions, and

c) vectorially adding the plurality of correlation or convolution functions to produce a sum vector providing a convolution or correlation result.

3. A signal processing technique according to claim 1 wherein convolution and correlation operations between pairs of one-dimensional signals are implemented by fast Fourier transformation of both signals to the frequency domain, taking the complex conjugate of one of the two Fourier transforms in the case of correlation, multiplying together corresponding frequency components of both Fourier transforms after conjugation of one if implemented, and then implementing an inverse fast Fourier transformation back to the original domain.

4. A signal processing technique according to claim 1 including the step of combining the separated signal components to form at least one result vector comprising at least one of a reconstruction of an input data vector and an anomaly vector indicating the reconstruction'"'"'s deviation from the associated input data vector.

5. A signal processing technique according to claim 4 wherein combining the separated signal components to form at least one result vector comprises multiplying separated signal components by respective basis scales and adding resulting products by vector addition.

6. A signal processing technique according to claim 1 wherein basis vectors are determined by a training process including:

a) arranging non-identical initial current values for basis vectors,

b) operating the signal processing technique using the current values of the basis vectors,

c) deriving for each basis vector at least one respective correland vector for correlation with an associated vector selected from input data and at least one result vector comprising at least one of a reconstruction of an input signal and an anomaly signal indicating the reconstruction'"'"'s deviation from its associated input signal,

d) for each basis vector, correlating the at least one respect ye correland vector with the associated vector to produce at least one respective correlation function,

e) modifying each basis vector to form a respective new current value incorporating a contribution in accordance with the at least one correlation function associated with the respective correland vector,

f) iterating steps (b) to (e) until the current values converge.

7. A signal processing technique according to claim 6 wherein the said contribution is proportional to the at least one correlation function, the constant of proportionality in this connection being referred to as the learning rate parameter.

8. A signal processing technique according to claim 6 wherein the at least one correland vector is at least one of:

a) an input data vector'"'"'s correlation vector derived by applying the non-linear function gradient to each element of an output vector to derive a gradient output vector and multiplying the gradient output vector by an associated correlation vector obtained from a correlation of basis and anomaly vectors, and

b) an anomaly vector'"'"'s correlation vector derived from a non-linearised output vector.

9. A signal processing technique according to claim 8 wherein the at least one correland vector is or includes a data vector'"'"'s correlation vector corresponding to a basis vector which is multi-dimensional, associated with a plurality of channels and gives rise to a plurality of correlation functions when correlated with the anomaly vector, and prior to multiplication by the gradient output vector the correlation functions are reduced to a correlation vector in one dimension by combining contributions of like time index from different channels.

10. A signal processing technique according to claim 8 wherein the at least one correland vector is or includes an input data vector'"'"'s correlation vector, and prior to multiplication by the said correlation function, the gradient output vector is multiplied by a respective weighting factor selected from quantities collectively referred to as basis scales and which when applied to respective input data vector reconstructions have the effect of reducing mean squared errors between such reconstructions and associated input data vectors used to derive them.

11. A signal processing technique according to claim 10 wherein the basis scales are computed by:

a) arranging non-identical initial current values for basis scales,

b) calculating a respective scalar product of an anomaly vector with each separated signal component associated with a like input data item,

c) modifying each basis scale to form a respective new current value incorporating a contribution in accordance with the scalar product associated therewith, and

d) iterating steps (b) and (c) for successive data items.

12. A signal processing technique according to claim 10 wherein the basis scales are computed by calculating:

a) over an input data set, a mean value of a vector of scalar products of input data items and associated separated signal components (SSCs),

b) over an input data set, a mean value of a matrix of scalar products of pairs of separated signal components associated with individual input data items,

c) an inverse of the mean scalar product matrix, and

d) a product of the inverse matrix and the mean vector of data-SSC scalar products, the product being a vector having elements which are basis scales.

13. A signal processing technique according to claim 8 wherein the at least one correland vector is or includes an anomaly vector'"'"'s correlation vector derived by multiplying elements of a non-linearised output vector by its respective basis scale.

14. A signal processing technique according to claim 13 wherein the at least one correland vector is a plurality of correland vectors, the technique including the step of computing correlation functions with such vectors, and the step of combining the resulting plurality of correlation functions, prior to modifying each basis vector to form a respective new current value.

15. A signal processing technique according to claim 13 wherein basis vectors are determined by a batch-mode iterative procedure involving a training set of input data for use in input data reconstruction, and wherein in each iteration of the procedure a respective sub-set of the training set undergoes reconstruction, and successive basis vectors are modified to form respective new current values incorporating multiple contributions derived from input data in the sub-set, each contribution being in accordance with the associated at least one correlation function associated with the respective correland vector.

16. A signal processing technique according to claim 15 wherein the number of input data items in each sub-set is at least as great as the number of basis vectors and each sub-set is selected randomly from the training set avoiding re-use of a small sub-set or of highly correlated sub-sets.

17. A signal processing technique according to claim 1 wherein the non-linear function is a threshold function which has at least one of the following properties:

a) being small for small argument values and begins to grow quickly for near threshold argument values,

b) not being sharp but relatively smooth and continuous,

c) not becoming exactly zero for argument values less than the threshold value,

d) asymptoting exponentially towards zero for argument values less than the threshold value, and

e) being a sigmoid function.

18. A signal processing technique according to claim 1 wherein the basis vectors are obtained by:

a) providing initial value of current basis vectors,

b) deriving data vector'"'"'s q-correlation and Q-correlation vectors from current basis vectors and non-linearised output vectors,

c) correlating the data vector'"'"'s q-correlation vector with its associated data vector,

d) correlating the data vector'"'"'s Q-correlation vector with its associated data vector,

e) correlating output vectors with separated signal components, such vectors and components having been derived from the associated data vector,

f) summing those correlations which involve data vector'"'"'s q-correlation vectors,

g) summing those correlations which involve data vector'"'"'s Q-correlation vectors and output vectors.

h) repeating steps (b) to (g) for successive data vectors, and

i) deriving contributions to basis vectors from a quadratic function of basis scales including a linear term involving added correlations associated with data vector'"'"'s q-correlation vectors and subtracted therefrom a quadratic term involving other added correlations.

19. A computer program for controlling operation of a computer system and providing for generation of separated signal components, wherein the program is arranged to implement a procedure incorporating the steps of:

a) correlating basis vectors with input data to produce output vectors,

b) applying to the output vectors a non-linear function having a gradient to produce non-linearised output vectors, and

c) convolving the non-linearised vectors with the basis vectors to produce separated signal components.

20. A computer program according to claim 19 wherein data and basis vectors are multi-dimensional and the procedure implements convolution and correlation operations by:

a) arranging both data vectors and basis vectors as pluralities of one-dimensional signals referred to as channel vectors,

b) correlating or convolving each data vector channel vector with a corresponding basis vector channel vector to yield a plurality of one-dimensional correlation or convolution functions, and

c) vectorially adding the plurality of correlation or convolution functions to produce a sum vector providing a convolution or correlation result.

21. A computer program according to claim 20 wherein the procedure includes the step of combining the separated signal components to form at least one result vector comprising at least one of a reconstruction of an input data vector and an anomaly vector indicating the reconstruction'"'"'s deviation from the associated input data vector.

22. A computer program according to claim 21 wherein the step of combining the separated signal components to form at least one result vector comprises multiplying separated signal components by respective basis scales and adding resulting products by vector addition.

23. A computer program according to claim 21 wherein the procedure determines basis vectors by a training process including:

a) arranging non-identical initial current values for basis vectors,

b) operating the signal processing technique using the current values,

c) deriving for each basis vector at least one respective correland vector for correlation with an associated vector selected from input data and at least one result vector comprising at least one of a reconstruction of an input signal and an anomaly signal indicating the reconstruction'"'"'s deviation from the input signal,

d) for each basis vector, correlating the at least one respective correland vector with the associated vector to produce at least one respective correlation function,

e) modifying each basis vector to form a respective new current value incorporating a contribution in accordance with the at least one correlation function associated with the respective correland vector,

f) iterating steps (b) to (e) until the current values converge.

24. A computer program according to claim 23 wherein the said contribution is proportional to the at least one correlation function, the constant of proportionality in this connection being referred to as the learning rate parameter.

25. A computer program according to claim 23 wherein the at least one correlated signal is at least one of:

a) an input data vector'"'"'s correlation vector derived by applying the non-linear function gradient to each element of an output vector to derive a gradient output vector and multiplying the gradient output vector by an associated correlation vector obtained from a correlation of basis and anomaly vectors, and

b) an anomaly vector'"'"'s correlation vector derived from a non-linearised output vector.

26. A computer program according to claim 25 wherein the at the at least one correland vector is or includes a data vector'"'"'s correlation vector corresponding to a basis vector which is multi-dimensional, associated with a plurality of channels and gives rise to a plurality of correlation functions when correlated with the anomaly vector, and prior to multiplication by the gradient output vector the correlation functions are reduced to a correlation vector in one dimension by combining contributions of like time index from different channels.

27. A computer program according to claim 25 characterised in that wherein the at least one correland vector is or includes an input data vector'"'"'s correlation vector, and prior to multiplication by the said correlation function, the gradient output vector is multiplied by a respective weighting factor selected from quantities collectively referred to as basis scales and which when applied to respective input data vector reconstructions have the effect of reducing mean squared errors between such reconstructions and associated input data vectors used to derive them.

28. A computer program according to claim 27 wherein the at least one correland vector is or includes an anomaly vector'"'"'s correlation vector derived by multiplying elements of a non-linearised output vector by its respective basis scale.

29. A computer program according to claim 28 wherein the at least one correland vector is a plurality of correlation vectors, and the procedure includes the step of computing correlation functions with such vectors the step of combining the resulting plurality of correlation functions, prior to modifying each basis vector to form a respective new current value.

30. A computer program according to claim 28 wherein basis vectors are determined by a batch-mode iterative procedure involving a training set of input data for use in input data reconstruction, and wherein in each iteration of the procedure a respective sub-set of the training set undergoes reconstruction, and successive basis vectors are modified to form respective new current values incorporating multiple contributions derived from input data in the sub-set, each contribution being in accordance with the associated at least one correlation function associated with the respective correland vector.

31. A computer program according to claim 30 wherein the number of input data items in each sub-set is at least as great as the number of basis vectors and the procedure provides for each sub-set to be selected randomly from the training set avoiding re-use of a small sub-set or of highly correlated sub-sets.

32. A computer program according to claim 27 wherein the procedure provides for the basis scales to be computed by calculating;

a) over an input data set, a mean value of a vector of scalar products of input data items and associated separated signal components (SSCs),

b) over an input data set, a mean value of a matrix of scalar products of pairs of separated signal components associated with individual input data items,

c) an inverse of the mean scalar product matrix, and

d) a product of the inverse matrix and the mean vector of data-SSC scalar products, the product being a vector having elements which are basis scales.

33. A computer program according to claim 27 wherein the procedure provides for the basis scales to be computed by:

a) arranging non-identical initial current values for basis scales,

b) calculating a respective scalar product of an anomaly vector with each separated signal component associated with a like input data item,

c) modifying each basis scale to form a respective new current value incorporating a contribution in accordance with the scalar product associated therewith, and

d) iterating steps (b) and (c) for successive data items.

34. A computer program according to claim 19 wherein the procedure implements convolution and correlation operations between pairs of vectors by fast Fourier transformation of both vectors to the frequency domain, taking a complex conjugate of one of the two Fourier transforms in the case of correlation only, multiplying together corresponding frequency components of both Fourier transforms after conjugation if implemented, and then implementing an inverse fast Fourier transformation back to the time domain.

35. A computer program according to claim 19 wherein the non-linear function is a threshold function which has at least one of the following properties:

a) being small for small argument values and begins to grow quickly for near threshold argument values,

b) not being sharp but relatively smooth and continuous,

c) not becoming exactly zero for argument values less than the threshold value,

d) asymptoting exponentially towards zero for argument values less than the threshold value, and

e) being a sigmoid function.

36. A computer program according to claim 19 wherein the procedure provides for the basis vectors to be obtained by:

a) providing initial values of current basis vectors,

b) denying data vector'"'"'s q-correlation and Q-correlation vectors from current basis vectors and non-linearised output vectors,

c) correlating the data vector'"'"'s q-correlation vector with its associated data vector,

d) correlating the data vector'"'"'s Q-correlation vector with the associated data vector,

e) correlating output vectors with separated signal components, such vectors and components having been derived from the associated data vector,

f) summing those correlations which involve data vector'"'"'s q-correlation vector,

g) summing those correlations which involve data vector'"'"'s Q-correlation vectors and output vectors

h) repeating steps (b) to (g) for successive data vectors, and

i) deriving contributions to basis vectors from a quadratic function of basis scales including a linear term involving added correlations associated with data vector'"'"'s q-correlation vectors and subtracted therefrom a quadratic term involving other added correlations.

37. A computer system programmed with a program in accordance with claim 19.

38. A computer system programmed to execute a processing technique to generate separated signal components, wherein the technique incorporates the steps of:

a) correlating basis vectors with input data to produce output vectors,

b) applying to the output vectors a non-linear function having a gradient to produce non-linearised vectors, and

c) convolving the non-linearised vectors with the basis vectors to produce separated signal components.

39. A computer system according to claim 38 wherein data and basis vectors are multi-dimensional and the convolution and correlation operations are implemented by:

a) arranging both data vectors and basis vectors as pluralities of one-dimensional signals referred to as channel vectors,

b) correlating or convolving each data vector channel vector with a basis vector channel vector to yield a plurality of one-dimensional correlation or convolution functions, and

c) vectorially adding the plurality of correlation or convolution functions to produce a sum vector providing convolution or correlation result.

40. A computer system according to claim 39 wherein the technique which it is programmed to execute includes combining the separated signal components to form at least one result vector comprising at least one of a reconstruction of an input data vector and an anomaly vector indicating the reconstruction'"'"'s deviation from the associated input data vector.

41. A computer system according to claim 40 wherein the technique with which the system is programmed provides for combining the separated signal components to form at least one result vector by multiplying separated signal components by respective basis scales and adding resulting products by vector addition.

42. A computer system according to claim 40 wherein the technique determines basis vectors by a training process including:

a) arranging non-identical initial current values for basis vectors,

b) operating the signal processing technique using the current values,

c) deriving for each basis vector at least one respective correland vector for correlation with an associated vector selected from input data and said at least one result vector,

d)for each basis vector, correlating the at least one respective correland vector with the associated vector to produce at least one respective correlation function,

e) modifying each basis vector to form a respective new current value incorporating a contribution in accordance with the at least one correlation function associated with the respective correland vector,

f) iterating steps (b) to (e) until the current values converge.

43. A computer system according to claim 42 wherein the at least one correland vector is at least one of:

a) an input data vector'"'"'s correlation vector derived by applying the non-linear function gradient to each element of an output vector to derive a gradient output vector and multiplying the gradient output vector by an associated correlation vector obtained from a correlation of basis and anomaly vectors, and

b) an anomaly vector'"'"'s correlation vector derived from a non-linearised output vector.

44. A computer system according to claim 43 wherein the at least one correland vector is or includes a data vector'"'"'s correlation vector corresponding to a basis vector which is multi-dimensional, associated with a plurality of channels and gives rise to a plurality of correlation functions when correlated with the anomaly vector, and prior to multiplication by the gradient output vector the correlation functions are reduced to a correlation vector in one dimension by combining contributions of like time index from different channels.

45. A computer system according to claim 43 wherein the at least one correland vector is or includes an input data vector'"'"'s correlation vector, and prior to multiplication by the said correlation function, the gradient output vector is multiplied by a respective weighting factor selected from quantities collectively referred to as basis scales and which when applied to respective input data vector reconstructions have the effect of reducing mean squared errors between such reconstructions and associated input data vectors used to derive them.

46. A computer system according to claim 45 wherein the technique provides for the basis scales to be computed by calculating over an input data set:

a) a mean value of a vector of scalar products of input data items and associated separated signal components (SSCs),

b) a mean value of a matrix of scalar products of pairs of separated signal components associated with individual input data items,

c) an inverse of the mean scalar product matrix, and

d) a product of the inverse matrix and the mean vector of data-SSC scalar products, the product being a vector having elements which are basis scales.

47. A computer system according to claim 45 wherein the technique provides for the basis scales to be computed by:

a) arranging non-identical initial current values for basis scales,

b) calculating a respective scalar product of an anomaly vector with each separated signal component associated with a like input data item,

c) modifying each basis scale to form a respective new current value incorporating a contribution in accordance with the scalar product associated therewith, and

d) iterating steps (b) and (c) for successive data items.

48. A computer system according to claim 43 wherein the at least one correland vector is or includes an anomaly vector'"'"'s correlation vector derived by multiplying elements of a non-linearised output vector by its respective basis scale.

49. A computer system according to claim 48 wherein the at least one correland vector is a plurality of correland vectors, and the technique includes the step of computing correlation functions with such vectors and the step of combining the resulting plurality of correlation functions, prior to modifying each basis vector to form a respective new current value.

50. A computer system according to claim 48 wherein basis vectors are determined by a batch-mode iterative procedure involving a training set of input data for use in input data reconstruction, and wherein in each iteration of the procedure a respective sub-set of the training set undergoes reconstruction,and successive basis vectors are modified to form respective new current values incorporating multiple contributions derived from input data in the sub-set, each contribution being in accordance with the associated at least one correlation function associated with the respective correland vector.

51. A computer system according to claim 38 wherein the technique implements convolution and correlation operations by fast Fourier transformation of both signals to the frequency domain, taking the complex conjugate of one of the two Fourier transforms in the case of correlation only, multiplying together corresponding frequency components of both Fourier transforms after conjugation of one if implemented, and then implementing an inverse fast Fourier transformation back to the original domain.

52. A computer system according to claim 38 wherein the non-linear function is a threshold function which has at least one of the following properties:

a) being small for small argument values and begins to grow quickly for near threshold argument values,

b) not being sharp but relatively smooth and continuous,

c) not becoming exactly zero for argument values less than the threshold value,

d) asymptoting exponentially towards zero for argument values less than the threshold value, and

e) being a sigmoid function.

53. A computer system according to claim 38 wherein the technique with which the system is programmed provides for the basis vectors to be obtained by:

a) providing initial values of current basis vectors,

b) deriving data vector'"'"'s q-correlation and Q-correlation vectors from current basis vectors and non-linearised output vectors,

c) correlating the data vector'"'"'s q-correlation vector with its associated data vector,

d) correlating the data vector'"'"'s Q-correlation vector with the associated data vector,

e) correlating output vectors with separated signal components, such vectors and components having been derived from the associated data vector,

f) summing those correlations which involve data vector'"'"'s q-correlation vectors,

g) summing those correlations which involve data vector'"'"'s Q-correlation vectors and output vectors,

h) repeating steps (b) to (g) for successive data vectors, and

i) deriving contributions to basis vectors from a quadratic function of basis scales including a linear term involving added correlations associated with data vector'"'"'s q-correlation vectors and subtracted therefrom a quadratic term involving other added correlations.