System and method for anomaly detection in dynamically evolving data using hybrid decomposition

1. A method, comprising steps of: in a computer system,

a) receiving data in the form of a matrix A=m× n comprising a plurality of m measurements of multidimensional data points (MDDPs), each data point having n features, wherein n≥2, wherein m>>n and wherein matrix A has a rank k<n;

a) applying randomized lower and upper triangular matrix (LU) decomposition to matrix A using l random projections and rank k of matrix A to obtain a dictionary D in the form of a matrix of size l×n, wherein k<l<n;

b) embedding dictionary D in a reduced dimension embedded space with a dimension r, wherein 0≤r<n, to obtain an embedded dictionary D, wherein the applying of randomized LU decomposition and the embedding of dictionary D in a reduced dimension embedded space are performed by dynamically configuring computer system parameters on-the-fly; and

c) in the reduced dimension embedded space and based on embedded dictionary D, applying an out-of-sample extension (OOSE) procedure to classify a newly arrived MDDP (NAMDDP) as normal or as an anomaly while requiring less computational effort and having faster processing due to the reduction in size from m to l and the reduction in dimension from n to r, thereby enhancing anomaly detection performance.

2. The method of claim 1 , wherein the applying an OOSE procedure to classify a NAMDDP as normal or as an anomaly includes computing coordinates of the NAMDDP in the reduced dimension embedded space and using the computed coordinates to classify the NAMDDP as normal or as an anomaly.

3. The method of claim 2 , wherein the computed coordinates are diffusion coordinates.

4. The method of claim 1 , further comprising:

d) repeating step (b) p≥1 times to obtain p additional dictionaries D(p);

e) concatenating each additional dictionary D(p) with all previously obtained dictionaries into a concatenated dictionary Dc, wherein steps (c) and (d) are performed using dictionary Dc,

whereby the repeating step (b) p≥1 times removes randomization effects related to the randomized LU decomposition, thereby providing a more robust embedded concatenated dictionary Dc and further improving anomaly detection performance.

5. The method of claim 1 , wherein the dynamic on-the-fly configuring of computer system parameters is done without changing computer system software code and without halting computer system operation, thereby improving computer system performance.

6. The method of claim 1 , wherein the classifying a NAMDDP as an anomaly includes classifying the NAMDDP as an anomaly without relying on a signature and/or a rule and/or on domain expertise.

7. A computer program product, comprising: a non-transitory tangible storage medium readable by a processing circuit and storing instructions for execution by the processing circuit for performing a method comprising:

a) receiving data in the form of a matrix A=m×n comprising a plurality of m measurements of multidimensional data points (MDDPs), each data point having n features wherein n≥2 and wherein m>>n and wherein matrix A has a rank k<n;

b) applying randomized lower and upper triangular matrix (LU) decomposition to matrix A using l random projections and rank k to obtain a dictionary D in the form of a matrix of size l×n, wherein k<l<n;

c) embedding dictionary D in a reduced dimension embedded space that has a dimension r, wherein 0<r<n, to obtain an embedded dictionary D, wherein the applying of randomized LU decomposition and the embedding of dictionary D in a reduced dimension embedded space are performed by dynamically configuring computer system parameters on-the-fly; and

d) in the reduced dimension embedded space and based on embedded dictionary D, applying an out-of-sample extension (OOSE) procedure to classify a newly arrived MDDP (NAMDDP) as normal or as an anomaly while requiring less computational effort and having faster processing due to the reduction in size from m to l and the reduction in dimension from n to r, thereby enhancing anomaly detection performance.

8. The computer program product of claim 7 , wherein the applying an OOSE procedure to classify a NAMDDP as normal or as an anomaly includes computing coordinates of the NAMDDP in the reduced dimension embedded space and using the computed coordinates to classify the NAMDDP as normal or as an anomaly.

9. The computer program product of claim 8 , wherein the computed coordinates are diffusion coordinates.

10. The computer program product of claim 7 , wherein the method further comprises:

e) repeating step (b) p≥1 times to obtain p additional dictionaries D(p);

f) concatenating each additional dictionary D(p) with all previously obtained dictionaries into a concatenated dictionary Dc, wherein steps (c) and (d) are performed using dictionary Dc,

whereby the repeating step (b) p≥1 times removes randomization effects related to the randomized LU decomposition by causing eigenvalues of each dictionary D to decline, thereby providing a more robust embedded concatenated dictionary Dc and further improving anomaly detection performance.

11. The computer program product of claim 7 , wherein the classifying a NAMDDP as an anomaly includes classifying the NAMDDP as an anomaly without relying on a signature and/or a rule and/or on domain expertise.

12. A computer system, comprising: a hardware processor configurable to perform a method comprising steps of:

a) receiving data in the form of a matrix A=m×n comprising a plurality of m measurements of multidimensional data points (MDDPs), each data point having n features, wherein n≥2, wherein m>>n and wherein matrix A has a rank k<n;

b) applying randomized lower and upper triangular matrix (LU) decomposition to matrix A using l random projections and rank k to obtain a dictionary D in the form of a matrix of size l×n, wherein k<l<n;

c) embedding dictionary D in a reduced dimension embedded space that has a dimension r, wherein 0<r<n, to obtain an embedded dictionary D, wherein the applying of randomized LU decomposition and the embedding of dictionary D in a reduced dimension embedded space are performed by dynamically configuring computer system parameters on-the-fly; and

d) in the reduced dimension embedded space and based on embedded dictionary D, applying an out-of-sample extension (OOSE) procedure to classify a newly arrived MDDP (NAMDDP) as normal or as an anomaly while requiring less computational effort and having faster processing due to the reduction in size from m to l and the reduction in dimension from n to r, thereby enhancing anomaly detection performance.

13. The computer system of claim 12 , wherein the applying an OOSE procedure to classify a NAMDDP as normal or as an anomaly includes computing coordinates of the NAMDDP in the reduced dimension embedded space and using the computed coordinates to classify the NAMDDP as normal or as an anomaly.

14. The computer system of claim 13 , wherein the computed coordinates are diffusion coordinates.

15. The computer system of claim 12 , wherein the method further comprises:

e) repeating step (b) p≥1 times to obtain p additional dictionaries D(p);

f) concatenating each additional dictionary D(p) with all previously obtained dictionaries into a concatenated dictionary Dc, wherein steps (c) and (d) are performed using dictionary Dc,

whereby the repeating step (b) p≥1 times removes randomization effects related to the randomized LU decomposition by causing eigenvalues of each dictionary D to decline, thereby providing a more robust embedded concatenated dictionary Dc and further improving anomaly detection performance.