Digital Signal Processing Methods and Apparatus

• US 20080291122A1
• Filed: 11/30/2005
• Published: 11/27/2008
• Est. Priority Date: 12/23/2004
• Status: Active Grant

• Current Assignee: Cambridge Display Technology Limited (Sumitomo Chemical Company Limited)
• Original Assignee: Cambridge Display Technology Limited (Sumitomo Chemical Company Limited)
• Inventors: Routley, Paul Richard, Smith, Euan Christopher, Foden, Clare Louise
• Granted Patent: US 7,953,682 B2
• Time in Patent Office: Days
• US Class Current: 345/55
• 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: G09G 2310/0208 using active addressing
• CPC Class Codes: G09G 2320/043 Preventing or counteracting the effects of ageing
• CPC Class Codes: G09G 3/3216 using a passive matrix

Abstract

This invention generally relates to methods, apparatus and computer program code processing digital data using non-negative matrix factorisation.

A method of digitally processing data in a data array defining a target matrix (X) using non-negative matrix factorisation to determine a pair of matrices (F, G), a first matrix of said pair determining a set of features for representing said data, a second matrix of said pair determining weights of said features, such that a product of said first and second matrices approximates said target matrix, the method comprising: inputting said target matrix data (X); selecting a row of said one of said first and second matrices and a column of the other of said first and second matrices; determining a target contribution (R) of said selected row and column to said target matrix; determining, subject to a non-negativity constraint, updated values for said selected row and column from said target contribution; and repeating said selecting and determining for the other rows and columns of said first and second matrices until all said rows and columns have been updated.

Claims

1. A method of digitally processing data in a data array defining a target matrix (X) using non-negative matrix factorisation to determine a pair of matrices (F, G), a first matrix of said pair determining a set of features for representing said data, a second matrix of said pair determining weights of said features, such that a product of said first and second matrices approximates said target matrix, the method comprising:

inputting said target matrix data (X);

selecting a row of said one of said first and second matrices and a column of the other of said first and second matrices;

determining a target contribution (R) of said selected row and column to said target matrix;

determining, subject to a non-negativity constraint, updated values for said selected row and column from said target contribution; and

repeating said selecting and determining for the other rows and columns of said first and second matrices until all said rows and columns have been updated.

2. A method as claimed in claim 1 wherein said determining of updated values comprises determining a new value for said selected row substantially independent of a previous value of said selected row and determining a new value for said selected column substantially independent of a previous value of said selected column.

3. A method as claimed in claim 1, wherein said determining of a target contribution (R) comprises determining a difference between said target matrix (X) and a sum of weighted features determined from all said rows and columns of said first and second matrices except said selected row and column.

4. A method as claimed in claim 1, wherein said determining of updated values comprises calculating values of G_ia=f₁(R,F) and F_au=f₂(R, G) where R is a matrix with I rows and U columns, F is a matrix with A rows and U columns and G is a matrix with I rows and A columns, where f₁ and f₂ denote first and second functions, and where G_ia denotes a data element in the ith row and ath column of G and F_au denotes a data element in the ath row and uth column of F.

5. A method as claimed in claim 4 wherein f₁ and f₂ are selected to minimise a cost function measuring a quality of approximation of a product of said selected row and column to said target contribution.

6. A method as claimed in claim 5 wherein said cost function comprises a squared Euclidean distance between a product of said selected row and column and said target contribution.

7. A method as claimed in claim 5 wherein said cost function comprises a divergence function between a product of said selected row and column and said target contribution.

8. A method as claimed in claim 4, wherein G_ia and F_iu are determined in accordance with:

9. A method as claimed in claim 8 wherein Φ

iu is substantially unity for all i and u.

10. A method as claimed in claim 8 wherein Φ

_iu has the form Φ

_iu=I/(Z_iu+γ

) where Z_iu denotes a data element in the ith row and uth column of an I by U matrix dependent upon at least one of X and R, and γ

is positive.

11. A method as claimed in claim 4, wherein A is less than the smaller of I and U.

12. A method as claimed in claim 1, further comprising initialising said first and second matrices.

13. A method as claimed in claim 12 wherein said data comprises image data for an image in a time series of images, and wherein said initialising is conditional upon a degree of difference between said image and a previous image.

14. A method as claimed in claim 1, wherein said determining subject to a non-negativity constraint comprises setting a said updated value to substantially zero where the updated value would otherwise be negative.

15. A method as claimed in claim 1, further comprising constraining said updated values to lie between a minimum and a maximum value.

16. A method as claimed in claim 1, further comprising repeating said updating of all said rows and columns of said first and second matrices for a plurality of iterations.

17. A method as claimed in claim 1, wherein said data comprises image data defining an image, and wherein said set of features determined by said first matrix comprises a set of subframes which when combined according to said weights determined by said second matrix approximate said image.

18. A method of driving a display comprising a plurality of pixels arranged in rows and columns, the method comprising employing the method of claim 1 to process data for display as said target matrix data (X) to determine said first and second matrices (F,G), and driving said display to form an image using a plurality of subframes, each subframe having said rows and columns of pixels driven responsive to a row of one of said first and second matrices and a column of the other of said first and second matrices.

19. A method of image matching, the method comprising inputting target image data for matching as said target matrix data;

processing said image data as claimed in claim 1 to determine said first and second matrices;

comparing data from at least one of said first and second matrices with stored data comprising data for a corresponding first and/or second matrix for a second image; and

outputting image match data responsive to said comparing.

20. A method as claimed in claim 19 wherein said stored data comprises data for a plurality of images held in a non-volatile store in the form of at least one of said first matrix said second matrix.

21. A method as claimed in claim 19 wherein said stored data comprises stored data derived from said second image, the method further comprising inputting said second image data and processing said data input to determine said first and second matrices for said second image.

22. A method as claimed in claim 19, wherein both said target image data and said second image data define a biometric image, in particular a facial image.

23. A method of providing security data for a data network, the method comprising:

reading traffic on said network to provide data for analysis;

processing said data for analysis as claimed in claim 1 to determine said first and second matrices; and

analysing data from at least one of said first and second matrices to determine security data for the network.

24. A method as claimed in claim 23 further comprising controlling access to and/or traffic on said network responsive to said analysing.

25. A method of data mining, the method comprising:

applying the method of claim 1 to data stored in a database to determine a set of discovered features; and

outputting analysis data derived from expression of said stored data in terms of said discovered features.

26. A method of processing sensor data, the method comprising:

inputting said sensor data as a data array; and

processing said sensor data using the method of claim 1; and

outputting said processed data expressed in terms of a set of said features.

27. A method of analysing biological data, the method comprising:

inputting said biological data;

processing said biological data using the method of claim 1 to determine feature data representing features for said biological data; and

analysing said biological data using said feature data.

28. A method as claimed in claim 27 wherein said biological data comprises atomic coordinate data and wherein said features correspond to physically similar or complementary features of biological entities.

29. A method as claimed in claim 27 wherein said biological data comprises sequence data in particular one or more of genome sequence data, proteome sequence data, microarray data, amino acid sequence data, and nucleotide sequence data, the method further comprising outputting analysing data for matching portions of said biological data.

30. A method of teaching a data processing system, the method comprising:

inputting data object data for a plurality of instances of data objects about which said data processing system is to learn;

processing said data object data using the method of claim 1 to identify feature data defining one or more features defining characteristics of said objects; and

updating an information store of said data processing system using said feature data.

31. A method as claimed in claim 30 wherein a number or dimension of said features is less than a number of attributes or dimension of said objects.

32. A method of data analysis, the method comprising:

inputting data for analysis;

processing said data for analysis using the method of claim 1 to determine feature data representing a plurality of features of said data for analysis; and

analysing said data for analysis by analysing said feature data.

33. A carrier medium carrying processor control code, to, when running, implement the method of claim 1.

34. A computer system inputting said target matrix data (X), the system comprising:

an input for said data for said data array;

an output for outputting said first and second matrices;

data memory for storing said target matrix and said pair of matrices;

program memory storing processor control code; and

a processor coupled to said input, to said output, to said data memory and to said program memory for loading and implementing said processor control code, said code comprising code to, when running implement the method of claim 1.

35. Apparatus for digitally processing data in a data array defining a target matrix (X) using non-negative matrix factorisation to determine a pair of matrices (F, G), a first matrix of said pair determining a set of features for representing said data, a second matrix of said pair determining weights of said features, such that a product of said first and second matrices approximates said target matrix, the apparatus comprising:

means for inputting said target matrix data (X);

means for selecting a row of said one of said first and second matrices and a column of the other of said first and second matrices;

means for determining a target contribution (R) of said selected row and column to said target matrix;

means for determining, subject to a non-negativity constraint, updated values for said selected row and column from said target contribution; and

means for repeating said selecting and determining for the other rows and columns of said first and second matrices until all said rows and columns have been updated.

36. A method of driving an electro-optic display, the display having a matrix of pixels, the method comprising:

inputting image data for said matrix of pixels into an image data matrix;

factorising said image data matrix into a product of first and second factor matrices; and

driving said display using said factor matrices; and

wherein

said factorising comprising iteratively adjusting said factor matrices such that their product approaches said image data matrix; and

wherein

said iterative adjusting comprises adjusting each row of one of said factor matrices and each column of the other of said factor matrices in turn.

37. A method as claimed in claim 36 wherein said adjusting of a row or column comprises determining a new value for a said row or column substantially independently of a previous value of said row or column.

38. A method as claimed in claim 36, wherein each said pixel is addressable by a row electrode and a column electrode;

wherein one of said factor matrices defines row drive signals and the other of said factor matrices defines column drive signals; and

wherein said driving comprises driving using said row and column drive signals.

39. A method as claimed in claim 38 wherein said driving comprises driving a plurality of said row electrodes in combination with a plurality of said column electrodes.

40. A method as claimed in claim 38, wherein said driving comprises driving said display with successive sets of said row and column signals to build up a display image, each said set of signals defining a subframe of said display image, said subframes combining to define said display image.

41. A method as claimed in claim 40 wherein said first factor matrix has dimensions determined by a number of said row electrodes and a number of said subframes, and wherein said second factor matrix has dimensions determined by a number of said column electrodes and said number of subframes.

42. A method as claimed in claim 40, wherein a number of said subframes is no greater than the smaller of a number of said row electrodes and a number of said column electrodes.

43. A method as claimed in claim 36, wherein said display comprises a passive matrix OLED display.

44. A method as claimed in claim 36, wherein said display comprises a plasma display.

45. A method as claimed in claim 36, wherein said display comprises an inorganic LED display.

46. A method as claimed in claim 36, wherein said display comprises a liquid crystal display.

47. A carrier medium carrying processor control code, to, when running, implement the method of claim 36.

48. A driver for an electro-optic display, the display having a matrix of pixels, the driver comprising:

an input to input image data for said matrix of pixels into an image data matrix;

a matrix factorisation system to factorise said image data matrix into a product of first and second factor matrices; and

a driver output to drive said display using said factor matrices, and wherein

said matrix factorisation system is configured to iteratively adjust said factor matrices, such that their product approaches said image data matrix, by adjusting each row of one of said factor matrices and each column of the other of said factor matrices in turn.

49. An integrated circuit including the matrix factorisation system of claim 48.

50. A method of processing a data array defining a target matrix (X) to determine a pair of factor matrices (F,G) such that a product of said factor matrices approximates said target matrix (X), the method comprising:

determining for a single row or column of a first said factor matrix a value to which an updating rule would converge when iteratively applied, said updating rule comprising an updating rule of a factorising algorithm which iteratively updates two factor matrices to more closely approximate a target matrix using said updating rule;

updating said row or column with said determined value;

repeating said determining and updating for a column or row of a second said factor matrix; and

repeating said determining and updating of said first and second factor matrices to update each row or column of said first factor matrix and each column or row of said second factor matrix.

51. A carrier carrying processor control code to, when running, implement the method of claim 50.