Methods and systems for computing singular value...

Details Methods and systems for computing singular value... Methods and systems for computing singular value...

2001-11-15

2004-10-19

Davis, George B. (Department: 2121)

Data processing: artificial intelligence

Neural network

C702S181000, C324S303000

Reexamination Certificate

active

06807536

ABSTRACT:

TECHNICAL FIELD
This invention relates to methods and systems for computing Singular Value Decompositions of matrices and low rank approximations of matrices.
BACKGROUND
Many aspects of machine learning and data mining are affected by what has become known as “the curse of dimensionality”. In order to find more sophisticated trends in data, potential correlations between larger and larger groups of variables must be considered. Unfortunately, the number of potential correlations generally increases exponentially with the number of input variables and, as a result, brute force approaches become infeasible.
A natural goal for machine learning is to attempt to identify and isolate these characteristic dimensions. We would like to simplify the data sufficiently so that we can apply traditional machine learning techniques, yet we do not wish to oversimplify, leaving out information crucial to understanding. A method widely used in this regard is to cast the data as a matrix A (indexed by <instance, attribute>) and compute a low rank approximation, D, of A. The idea is that the rank of a matrix corresponds roughly to the degrees of freedom of its entries. By constraining the rank of D we aim to capture the most pertinent characteristics of the data in A, leaving behind dimensions in which the data appears “random”.
Such low rank approximations are most often derived by computing the Singular Value Decomposition of A and taking the rank k matrix, A
k
, that corresponds to the k largest singular values.
Recall that for an arbitrary matrix A its Frobenius norm, |A|
F
, is given by
|
A
⁢
|
F
=
∑
i
,
j
⁢
A
⁡
(
i
,
j
)
2
.
Perhaps the best-known property of A
k
is that for any rank k matrix D,
|
A−D|
F
≧|A−A
K
|
F
.  (1)
that is, A
k
is the optimal rank k approximation of matrix A, since every other rank k matrix D is “further” from A as measured by the Frobenius norm.
This method has met with significant empirical success in a number of different areas, including Latent Semantic Analysis (LSA) in Information Retrieval as described in Berry et al.,
Matrices, Vector Spaces, and Information Retrieval
, SIAM Rev. 41 (1999) no. 2, 335-362 and Berry et al.,
Using Linear Algebra for Intelligent Information Retrieval
, SIAM Rev. 37 (1995), no. 4, 573-595. This method has also met with significant empirical success in Face Recognition, as described in Turk et al.,
Eigenfaces for Recognition
, Journal of Cognitive Neuroscience 3 (1991), no. 1, 71-86.
Accordingly, this invention arose out of concerns associated with providing improved methods and systems for processing data in high dimensional space and, in particular, for computing low rank approximations to matrices using the Singular Value Decomposition.
SUMMARY
Methods and systems for finding a low rank approximation for an m×n matrix A are described. The described embodiments can independently sample and/or quantize the entries of an input matrix A, and can thus speed up computation by reducing the number of non-zero entries and/or their representation length. The embodiments can be used in connection with Singular Value Decomposition techniques to greatly benefit the processing of high-dimensional data sets in terms of storage, transmission and computation.


REFERENCES:
patent: 5517115 (1996-05-01), Prammer
patent: 5548798 (1996-08-01), King
patent: 6594622 (2003-07-01), Srivastava
Ferzali et al, “Adaptive SVD Algorithm for Covariance Matrix Eigenstructure Computation”, IEEE International Conference on Acoustics, Speech, and Signal Processing, Apr. 1990.*
Frieze, Alan et al., “Fast Monte-Carlo Algorithms for finding low-rank approximations”, Oct. 22, 1998, 15 pages.
Drineas, P. et al., “Clustering in large graphs and matrices”, 16 pages.

Affiliated with

Also associated with

Rating

Methods and systems for computing singular value... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Methods and systems for computing singular value..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and systems for computing singular value... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3295887