Enhanced power method on an electronic device

Patent metadata

Field	Value
Publication number	US-9684538-B1
Application number	US-201615341263-A
Country	US
Kind code	B1
Filing date	Nov 2, 2016
Priority date	Jun 2, 2016
Publication date	Jun 20, 2017
Grant date	Jun 20, 2017

Abstract

A power method can be enhanced. For example, an electronic communication indicating a job to be performed can be received. A best rank-1 approximation of a matrix associated with the job can be determined using the power method. Each iteration of the power method can include determining a point that lies on a line passing through (i) a first value for a first singular vector from an immediately prior iteration of the power method; and (ii) a second value for the first singular vector from another prior iteration of the power method. Each iteration of the power method can also include determining, by performing the power method using the point, a current value for the first singular vector and a current value for a second singular vector for a current iteration of the power method. The job can then be performed using the best rank-1 approximation of the matrix.

First claim

The invention claimed is:

1. A non-transitory computer readable medium comprising:
program code executable by a processor for causing the processor to receive an electronic communication indicating a job to be performed;
program code executable by the processor for causing the processor to determine a best rank-1 approximation of a matrix associated with the job using a power method, wherein each iteration of the power method comprises:
determining a point that lies on a line passing through (i) a first value for a first singular vector from an immediately prior iteration of the power method; and (ii) a second value for the first singular vector from another prior iteration of the power method; and
determining, by performing the power method using the point, a current value for the first singular vector and a current value for a second singular vector for a current iteration of the power method;

program code executable by the processor for causing the processor to perform the job at least in part using the best rank-1 approximation of the matrix; and
program code executable by the processor for causing the processor to transmit another electronic communication associated with a result of the job.

2. The non-transitory computer readable medium of claim 1 , further comprising program code executable by the processor for causing the processor to determine the point based on a refinement factor, the refinement factor being a value that maximizes a function that includes a predetermined relationship between (i) the matrix; (ii) the first value for the first singular vector from the immediately prior iteration of the power method, and (iii) the second value for the first singular vector from the other prior iteration of the power method.

3. The non-transitory computer readable medium of claim 2 , wherein the first singular vector is a left singular vector for the matrix and the second singular vector is a right singular vector for the matrix.

4. The non-transitory computer readable medium of claim 3 , wherein the job is associated with ranking documents or links in a search engine or generating recommended content to be provided to a user.

5. The non-transitory computer readable medium of claim 1 , wherein the job is associated with generating a model that represents a relationship between data included in the electronic communication and a plurality of independent variables that influence the data.

6. The non-transitory computer readable medium of claim 1 , wherein the power method is configured to use a lower number of computational iterations for determining the best rank-1 approximation of the matrix than another power method in which the current value for the first singular vector and the current value for the second singular vector are determined exclusive of the second value for the first singular vector from the other prior iteration of the power method.

7. The non-transitory computer readable medium of claim 1 , wherein the power method is configured to use less memory for storing data associated with performing the power method than another power method in which the current value for the first singular vector and the current value for the second singular vector are determined exclusive of the second value for the first singular vector from the other prior iteration of the power method.

8. The non-transitory computer readable medium of claim 1 , further comprising program code executable by the processor for causing the processor to communicate at least one of the best rank-1 approximation of the matrix, the current value for the first singular vector, or the current value for the second singular vector to a worker node in a communications grid computing system for performing the job.

9. The non-transitory computer readable medium of claim 8 , further comprising program code executable by the processor for causing the processor to receive the electronic communication from the worker node in the communications grid computing system, the electronic communication comprising at least one of the first value for the first singular vector from the immediately prior iteration of the power method, or the second value for the first singular vector from the other prior iteration of the power method.

10. The non-transitory computer readable medium of claim 1 , further comprising program code executable by the processor for causing the processor to transmit the other electronic communication associated with the result of the job by transmitting a display signal configured to cause a display device to output a graphical representation of the result of the job.

11. A computer-implemented method executed by a processing device coupled to a memory device, the computer-implemented method comprising:
receiving, by the processing device, an electronic communication indicating a job to be performed;
determining, by the processing device, a best rank-1 approximation of a matrix associated with the job using a power method, wherein each iteration of the power method comprises:
determining a point that lies on a line passing through (i) a first value for a first singular vector from an immediately prior iteration of the power method; and (ii) a second value for the first singular vector from another prior iteration of the power method; and
determining, by performing the power method using the point, a current value for the first singular vector and a current value for a second singular vector for a current iteration of the power method;

performing, by the processing device, the job at least in part using the best rank-1 approximation of the matrix; and
transmitting, by the processing device, another electronic communication associated with a result of the job.

12. The computer-implemented method of claim 11 , further comprising determining the point based on a refinement factor, the refinement factor being a value that maximizes a function that includes a predetermined relationship between (i) the matrix; (ii) the first value for the first singular vector from the immediately prior iteration of the power method, and (iii) the second value for the first singular vector from the other prior iteration of the power method.

13. The computer-implemented method of claim 12 , wherein the first singular vector is a left singular vector for the matrix and the second singular vector is a right singular vector for the matrix.

14. The computer-implemented method of claim 11 , wherein the job is associated with ranking documents or links in a search engine or generating recommended content to be provided to a user.

15. The computer-implemented method of claim 11 , wherein the job is associated with generating a model that represents a relationship between data included in the electronic communication and a plurality of independent variables that influence the data.

16. The computer-implemented method of claim 11 , wherein the power method is configured to use a lower number of computational iterations for determining the best rank-1 approximation of the matrix than another power method in which the current value for the first singular vector and the current value for the second singular vector are determined exclusive of the second value for the first singular vector from the other prior iteration of the power method.

17. The computer-implemented method of claim 11 , wherein the power method is configured to use less memory for storing data associated with performing the power method than another power method in which the current value for the first singular vector and the current value for the second singular ve

Assignees

• Sas Inst Inc

Inventors

• Liu Jun
• Zhang Ruiwen
• Xu Yan
• Griffin Joshua

Classifications

• G06F17/16 Primary

  Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)} · CPC title

• G06N99/005

  Physics · mapped topic

• G06F17/175

  of multidimensional data · CPC title

• G06F9/4893 Primary

  taking into account power or heat criteria (power management in computers in general G06F1/3203; thermal management in computers in general G06F1/206) · CPC title

• G06F9/5072

  Grid computing · CPC title