Methods and systems for computing singular value decompositions of matrices and low rank approximations of matrices
AssigneeMicrosoft Corporation
InventorsDimitris Achlioptas, Frank D. McSherry
Life of this patent
Estimating the term…
Abstract
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.
Claims54
A method of processing data for use in Singular Value Decomposition (SVD), the method comprising:
- providing multiple entries that are associated with points in a space, the multiple entries being arrangable into a first m×n matrix;
- modifying values of at least some of the entries;
- and
- defining a second m×n matrix comprising the modified entries, the second m×n matrix being configured to be processed in accordance with Singular Value Decomposition techniques.
One or more computer readable media having computer-readable instructions thereon which, when executed by one or more processors, cause the one or more processors to:
- provide multiple entries that are associated with points in a space, the multiple entries being arrangable into a first m×n matrix;
- modify values of at least some of the entries so that at least some modified entry values are zero, and some modified entry values are non-zero values;
- and
- define a second m×n matrix that includes the modified entry values, the second m×n matrix being configured to be processed in accordance with Singular Value Decomposition techniques.
A method of performing Singular Value Decomposition (SVD) comprising:
- processing a matrix containing entries associated with points in a space, the matrix having a number of rows, said processing comprising changing at least some entry values and retaining the same number of rows in the matrix;
- and
- after said processing, performing Singular Value Decomposition on the matrix.
A method of processing data for use in Singular Value Decomposition (SVD), the method comprising:
- defining a first m×n matrix where m represents a number of points of interest in a space, and n represents number of dimensions in the space, each row of the matrix having multiple entries;
- mathematically perturbing values of at least some of the multiple entries;
- defining a second m×n matrix that contains entries having values that have been perturbed;
- and
- processing the second m×n matrix in accordance with SVD techniques.
One or more computer readable media having computer-readable instructions thereon which, when executed by one or more processors, cause the one or more processors to:
- define a first m×n matrix where m represents a number of points of interest in a space, and n represents number of dimensions in the space, each row of the matrix having multiple entries;
- mathematically randomly perturb the values of at least some of the multiple entries;
- define a second m×n matrix that contains entries having values that have been perturbed;
- and
- process the second m×n matrix in accordance with SVD techniques.
A method of processing data for use in Singular Value Decomposition (SVD), the method comprising:
- providing multiple entries that are associated with points in a space, the multiple entries being arrangable into a first m×n matrix where m represents the number of points of interest in the space, and n represents the number of dimensions in the space, each row of the matrix having multiple entries;
- mathematically randomly perturbing the values of at least some of the multiple entries;
- and
- defining a second m×n matrix that contains entries having values that have been perturbed, the second m×n matrix being configured to be processed in accordance with SVD techniques.
A system for processing data for use in Singular Value Decomposition (SVD), the system comprising:
- means for defining a first m×n matrix where m represents a number of points of interest in a space, and n represents number of dimensions in the space, each row of the matrix having multiple entries;
- means for mathematically perturbing the values of at least some of the multiple entries;
- means for defining a second m×n matrix that contains entries having values that have been perturbed;
- and
- means for processing the second m×n matrix in accordance with SVD techniques.
A method of processing data for use in Singular Value Decomposition (SVD), the method comprising:
- establishing a relationship that defines one or more probabilities that pertain to whether values associated with a data set that can be represented as an m×n matrix are set to zero;
- and
- processing multiple values associated with said data set in accordance with said one or more probabilities, at least some of the values being set to zero.
A method of processing data for use in Singular Value Decomposition (SVD), the method comprising:
- establishing a relationship that defines one or more probabilities that pertain to whether values associated with a data set that can be represented as an m×n matrix are modified to zero, said one or more probabilities making it more likely that larger entry values will be retained than smaller entry values;
- and
- processing multiple values associated with said data set in accordance with said one or more probabilities, at least some of the values being set to zero.
A method of processing data for use in Singular Value Decomposition (SVD), the method comprising:
- establishing a relationship that defines a probability that pertains to how values associated with a data set that can be represented as an m×n matrix are to be modified;
- and
- processing multiple values associated with the data set in accordance with the probability to provide values that have been modified.
A method of processing data for use in Singular Value Decomposition (SVD), the method comprising:
- receiving multiple entries that are associated with points in a space, the multiple entries being arrangable into a first m×n matrix;
- modifying values of at least some of the entries;
- and
- providing said multiple entries, including any modified entries, to an SVD processor for processing in accordance with Singular Value Decomposition techniques, said multiple entries, including any modified entries, being arrangable into a second m×n matrix.
A Singular Value Decomposition (SVD) processor configured to:
- receive multiple entries that are associated with points in a space, the multiple entries being arrangable into a first m×n matrix;
- modify values of at least some of the entries;
- and
- process said multiple entries, including any modified entries, in accordance with Singular Value Decomposition techniques, said multiple entries, including any modified entries, being arrangable into a second m×n matrix.
A Singular Value Decomposition (SVD) processor configured to:
- process a first m×n matrix by mathematically perturbing values of at least some of matrix entries, where m represents a number of points of interest in a space, and n represents number of dimensions in the space;
- and
- define a second m×n matrix that contains entries having values that have been perturbed;
- and
- process the second m×n matrix in accordance with SVD techniques.
Dependencies are inferred from the claim text.