Determining a Product Vector for Performing Dynamic Time Warping

• US 20150095391A1
• Filed: 09/30/2014
• Published: 04/02/2015
• Est. Priority Date: 09/30/2013
• Status: Abandoned Application

• Current Assignee: Siemens AG
• Original Assignee: Siemens AG
• Inventors: Gajjar, Mrugesh, Vydyanathan, Nagavijayalakshmi
• Application Number:
  US14/503,079
• Publication Number:
  US 20150095391A1
• Time in Patent Office: Days
• US Class Current: 708/441
• CPC Class Codes: G06F 17/16 Matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization matrix transposition G06F7/78
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors

Abstract

A method and a system for determining a product vector for computation of a Euclidean distance for performing Dynamic Time Warping of a test signal and a template signal are provided. Low-rank factorized vectors are determined for the template signal. The low-rank factorized vectors are processed along with the test signal for determining the product vector. The product vector is thereafter usable for the determination of a Euclidean distance between the test signal and the template signal, and for performing dynamic time warping of the test signal and the template signal.

Claims

1. A method for determining a product vector for determining a Euclidean distance between a test signal vector and at least a template signal vector, wherein the test signal vector comprises vectorized values of at least a portion of a test signal, and wherein the template signal vector comprises vectorized values of a template signal, the method comprising:

factorizing, by a processor, the template signal vector for obtaining at least a first template signal factorized vector and a second template signal factorized vector of the template signal vector, wherein respective ranks of the first template signal factorized vector and the second template signal factorized vector are both less than a rank of the template signal vector;

multiplying, by the processor, the test signal vector and the first template signal factorized vector for obtaining an intermediate test signal vector, wherein a rank of the intermediate test signal vector is less than or equal to a rank of the test signal vector; and

multiplying, by the processor, the intermediate test signal vector and the second template signal factorized vector for determining the product vector.

2. The method of claim 1, wherein a product of the first template signal factorized vector and the second template signal factorized vector is at least an approximation of the template signal vector.

3. The method of claim 1, wherein the first template signal factorized vector and the second template signal factorized vector are obtained by performing Singular Value Decomposition of the template signal vector.

4. The method of claim 1, wherein in the factorizing of the template signal vector, the obtaining of the first template signal factorized vector comprises:

multiplying a random signal with the template signal vector for obtaining a quasi product vector, wherein the random signal comprises a plurality of random signal vectors, wherein each random signal vector of the plurality of the random signal vectors comprises a plurality of random values;

factorizing the quasi product vector for obtaining a first quasi product factorized vector and a second quasi product factorized vector for the quasi product vector, wherein respective ranks of the first quasi product factorized vector and the second quasi product factorized vector are both less than a rank of the quasi product vector; and

multiplying the first quasi product factorized vector with an inverse random signal for obtaining the first template signal factorized vector, wherein the inverse random signal is an inverse of the random signal.

5. The method of claim 4, wherein the second quasi product factorized vector is the second template signal factorized vector.

6. The method of claim 4, wherein the first quasi product factorized vector and the second quasi product factorized vector are obtained by performing Singular Value Decomposition of the quasi product factorized vector.

7. A method for performing Dynamic Time Warping between a test signal vector and at least a template signal vector, wherein the test signal vector comprises vectorized values of at least a portion of a test signal, and wherein the template signal vector comprises vectorized values of a template signal, the method comprising:

determining, by a processor, a product vector of the test signal vector and the template signal vector, wherein the determining comprises factorizing the template signal vector for obtaining at least a first template signal factorized vector and a second template signal factorized vector of the template signal vector, wherein respective ranks of the first template signal factorized vector and the second template signal factorized vector are both less than a rank of the template signal vector, wherein the determining further comprises multiplying the test signal vector and the first template signal factorized vector for obtaining an intermediate test signal vector, wherein a rank of the intermediate test signal vector is less than or equal to a rank of the test signal vector, wherein the determining further comprises multiplying the intermediate test signal vector and the second template signal factorized vector for determining the product vector;

processing, by the processor, the product vector for determining a Euclidean distance between the test signal vector and the template signal vector; and

processing, by the processor, the Euclidean distance for determining a global distance between the test signal vector and the template signal vector, wherein the global distance represents a Dynamic Time Warping Score for the test signal vector and the template signal vector, and wherein the Dynamic Time Warping Score represents a similarity between the test signal vector and the template signal vector.

8. A system for determining a product vector from a test signal vector and a template signal vector, wherein the test signal vector comprises vectorized values of at least a portion of a test signal, and wherein the template signal vector comprises vectorized values of a template signal, the system comprising:

a processor configured for;

factorizing the template signal vector for obtaining a first template signal factorized vector and a second template signal factorized vector for the template signal vector;

multiplying the test signal vector and the first template signal factorized vector for obtaining an intermediate test signal vector; and

multiplying the second template signal factorized vector and the intermediate test signal vector for obtaining the product vector.

9. The system of claim 8, wherein respective ranks of the first template signal factorized vector and the second template signal factorized vector are both less than a rank of the template signal vector, and

wherein a rank of the intermediate test signal vector is less than or equal to a rank of the test signal vector.

10. The system of claim 8, wherein the processor is further configured to factorize the template signal vector, such that the product of the first template signal factorized vector and the second template signal factorized vector is at least an approximation of the template signal vector.

11. The system of claim 8, wherein the processor is further configured to factorize the template signal vector by performing Singular Value Decomposition of the template signal vector for obtaining the first template signal factorized vector and the second template signal factorized vector.

12. The system of claim 11, wherein the processor is further configured for multiplying the random signal and the template signal vector for obtaining the quasi product vector.

13. The system of claim 12, wherein the processor is further configured to factorize a quasi product vector for obtaining the first quasi product factorized vector and the second quasi product factorized vector from the quasi product vector, wherein the second quasi product factorized vector is the second template signal factorized vector.

14. The system of claim 13, wherein the processor is further configured for multiplying an inverse random signal and the first quasi product factorized vector for obtaining the first template signal factorized vector.

15. The system of claim 14, wherein the processor is further configured to multiply the first template signal factorized vector and the second quasi product factorized vector for obtaining the product vector.

16. The system of claim 8, further comprising a memory unit configured for storing the test signal vector, the template signal vector, the product vector, the first template signal factorized vector, the second template signal factorized vector, or any combination thereof.

17. A Dynamic Time Warping Block for Dynamic Time Warping a test signal vector and at least a template signal vector, wherein the test signal vector comprises vectorized values of at least a portion of a test signal, and wherein the template signal vector comprises vectorized values of a template signal, the Dynamic Time Warping Block comprising:

a system for determining a product vector of the test signal vector and the template signal vector, the system comprising a processor configured for factorizing the template signal vector for obtaining a first template signal factorized vector and a second template signal factorized vector for the template signal vector, multiplying the test signal vector and the first template signal factorized vector for obtaining an intermediate test signal vector, and multiplying the second template signal factorized vector and the intermediate test signal vector for obtaining the product vector;

a Euclidean Distance Matrix Computation module configured to process the test signal vector, the template signal vector and the product vector or determining a Euclidean distance between the test signal vector and the template signal vector based on the product vector; and

a Dynamic Time Warping Score computation module configured to process the Euclidean distance for determining a global distance between the test signal vector and the template signal vector, wherein the global distance represents a Dynamic Time Warping Score for the test signal vector and the template signal vector, and wherein the Dynamic Time Warping Score represents a similarity between the test signal vector and the template signal vector.