Regression using M-estimators and polynomial kernel support vector machines and principal component regression

1. A method comprising:

obtaining one or more sets of input data;

performing, by a processor device, a sketching process including:

generating a matrix A and a vector b using the one or more sets of input data;

creating, by the processor device, a randomized sketching matrix S based on the matrix A; and

determining, by the processor device, a vector x that minimizes a normalized measure function based on the matrix A and the vector b; and

performing, by the processor device, a relationship process using the sketching process for determining a relationship between the one or more sets of input data based on the vector x.

2. The method of claim 1 , wherein determining the vector x comprises determining the min x ∥Ax−b∥ G , where Aε n×d and bε n , and ∥y∥ G for yε n is specified by the measure function G: + , and ∥y∥ G ≡Σ i G(y i ), where i, n and d are positive integers, and the matrix A comprises an n×d matrix.

3. The method of claim 2 , further comprising:

estimating, by the processor device, ∥Ax∥ G , for all xε d based on the sketching matrix S.

4. The method of claim 3 , wherein the relationship process further comprises using the sketching matrix S for a plurality of M-estimators requiring O(nnz(A)+poly(d log n)) time, the processor device performs one pass over the matrix A for determining a regression solution with a residual error within a constant factor of a specified tolerance and with constant probability, and nnz comprises a number of non-zero entries of the matrix A.

5. The method of claim 1 , further comprising:

embedding, by the processor device, a space induced by a nonlinear polynomial kernel for the matrix A using an oblivious subspace embedding (OSE).

6. The method of claim 5 , wherein embedding the space comprises applying, by the processor device, a map φ(A) to rows of A, and the map φ(A) corresponds to the nonlinear polynomial kernel.

7. The method of claim 6 , wherein determining the vector x comprises determining min x ∥φ(A)x−b∥ G , where Aε n×d and bε n , and ∥y∥ G for yε n is specified by the measure function G: + , and ∥y∥ G ≡Σ i G(y i ), where i, n and d are positive integers, and the matrix A comprises an n×d matrix.

8. A computer program product for determining relationships between data, the computer program product comprising a computer readable storage medium having program code embodied therewith, the program code executable by a processor to:

receive, by the processor, one or more sets of input data;

perform, by the processor, a sketching process executable by the processor to:

generate a matrix A and a vector b based on the one or more sets of input data;

create, by the processor, a randomized sketching matrix S based on the matrix A; and

determine, by the processor, a vector x that minimizes a normalized measure function based on the matrix A and the vector b; and

perform, by the processor, a relationship process using the sketching process to determine a relationship between the one or more sets of input data based on the vector x.

9. The computer program product of claim 8 , wherein determining the vector x comprises further program code executable by the processor to determine the min x ∥Ax−b∥ G , where Aε n×d and bε n , and ∥y∥ G for yε n is specified by the measure function G: + , and ∥y∥ G ≡Σ i G(y i ), where i, n and d are positive integers, and the matrix A comprises an n×d matrix.

10. The computer program product of claim 9 , wherein the program code further executable by a processor to estimate ∥Ax∥ G , for all xε d based on the sketching matrix S.

11. The computer program product of claim 10 , wherein the relationship process further comprises using the sketching matrix S for a plurality of M-estimators requiring O(nnz(A)+poly(d log n)) time, the processor makes one pass over the matrix A for determining a regression solution with a residual error within a constant factor of a specified tolerance and with constant probability, and nnz comprises a number of non-zero entries of the matrix A.

12. The computer program product of claim 8 , wherein the program code executable by the processor further to:

embed, by the processor, a space induced by a nonlinear polynomial kernel for the matrix A using an oblivious subspace embedding (OSE).

13. The computer program product of claim 12 , wherein the program code executable by the processor further to: embed the space by applying a map φ(A) to rows of A, and the map φ(A) corresponds to the nonlinear polynomial kernel.

14. The computer program product of claim 8 , wherein determine the vector x comprises determine min x ∥φ(A)x−b∥ G , where Aε n×d and bε n , and ∥y∥ G for yε n is specified by the measure function G: + , ∥y∥ G ≡Σ i G(y i ), where i, n and d are positive integers, and the matrix A comprises an n×d matrix.

15. A method comprising:

receiving one or more sets of input data;

performing, by a processor device, a sketching process including:

generating a matrix A and a vector b using the one or more sets of input data;

creating, by the processor device, a randomized sketching matrix S based on the matrix A;

applying, by the processor device, a map φ(A) to rows of the matrix A using an oblivious subspace embedding (OSE), wherein the map φ corresponds to a nonlinear kernel;

processing, using the processor device, the map φ(A) and the vector b based on the randomized sketching matrix S; and

determining a vector x that minimizes a normalized measure function based on the map φ(A) and the vector b; and

performing, by the processor device, a relationship process using the sketching process for determining a relationship between the one or more sets of input data based on the vector x.

16. The method of claim 15 , wherein determining the vector x comprises determining the min x ∥φ(A)x−b∥ G , where Aε n×d and bε n , and ∥y∥ G for yε n is specified by the measure function G: + , and ∥y∥ G ≡Σ i G(y i ), where i, n and d are positive integers, and the matrix A comprises an n×d matrix.

17. The method of claim 16 , further comprising estimating, by the processor device, ∥φ(A)x∥ G , for all xε d based on the sketching matrix S.

18. The method of claim 17 , wherein the map φ(A) maps each row of A to a higher dimensional space using a polynomial kernel of a given degree.

19. The method of claim 18 , further comprising:

computing, by the processor device, an implicit low rank decomposition of φ(A).

20. The method of claim 19 , further comprising:

performing, by the processor device, a principal component regression (PCR) process with respect to an approximation of top k left singular vectors of φ(A), wherein k is a positive integer.