Sketching structured matrices in nonlinear regression problems

1. A computer-implemented method involving a fast nonlinear regression problem for use in classifying an image for an image classification system, said method comprising:

receiving, at a hardware processor of a computer system, input data corresponding to a image feature design matrix (A) of values representing an image, wherein matrix (A) is an n×d matrix where n>d, and receiving data representing a corresponding output data target vector (b), and

forming, at the hardware processor, a nonlinear regression problem to be solved, said nonlinear regression problem being of a form min xϵC ∥Ax−b∥ p , where x is a matrix, p is an 1-2 norm, and C is a constraint set; and

modifying said nonlinear regression problem by:

applying, using said hardware processor, a matrix operator T q to said matrix (A) to generate data representing a block-Vandermonde structured matrix T q (A), said T q (A) expanding matrix (A) to an (n×(dq)) matrix, said block-Vandermonde structured matrix having a fast vector-matrix method associated therewith;

generating, using said hardware processor, a sparse embedding matrix for said 1-2 norm with an associated hash function;

multiplying, using said hardware processor, said spare embedding matrix with said T q (A) to obtain a first product;

multiplying, using said hardware processor, said spare embedding matrix with said vector (b) to obtain a second product; and

running an iterative regression solver device on said modified nonlinear regression problem with p=2 to generate an output vector for said image classification system, said regression solver generating said output vector in an accelerated time according to:

O(nnz(A)log 2 q) +poly(dq/ϵ) , where nnz(A) represents a number of non-zero entries of the matrix A and ϵ is a pre-specified accuracy parameter ϵ>0,

wherein said output vector is used in classifying said image.

2. The computer-implemented method of claim 1 , wherein the T q (A) expands said matrix A to said (n ×(dq)) matrix by replacing each entry A i,j with a q-tuple (1, A i,j , A i,j 2 , . . . A i,j q−1 ).

3. The computer-implemented method of claim 2 ,

wherein the generated output vector is an output vector x′ that satisfies |Ax′-b| p ≤(1+eps) min x |Ax-b| p , where eps(ϵ)>0 is a user-specified accuracy parameter.

4. The computer-implemented method of claim 3 , further comprising:

solving said modified regression problem with p =2 in a time according to:

O((nnz(A)+dq)log(1/ϵ))+poly(dq) , where nnz(A) represents a number of non-zero entries of the matrix A.

5. The computer-implemented method according to claim 3 , further comprising:

solving said modified regression problem with p=1 in a time according to:

O(nnz(A)log n log 2 q) +(dqϵ −1 log n) , where nnz(A) represents a number of non-zero entries of the matrix A.

6. A computer-implemented image classification system involving a fast nonlinear regression problem for use in classifying an image comprising:

a memory;

a hardware processor coupled to the memory, the hardware processor configured to:

receive input data corresponding to a image feature design matrix (A) of values representing an image, wherein matrix (A) is an n×d matrix where n>d, and receiving data representing a corresponding output data target vector (b), and

form a nonlinear regression problem to be solved, said nonlinear regression problem being of a form min xϵC ∥Ax−b∥ p , where x is a matrix, p is an 1-2 norm, and C is a constraint set; and

modify said nonlinear regression problem by:

applying, using said hardware processor, a matrix operator T q to said matrix (A) to generate data representing a block-Vandermonde structured matrix T q (A), said T q (A) expanding matrix (A) to an (n×(dq)) matrix, said block-Vandermonde structured matrix having a fast vector-matrix method associated therewith;

generating, using said hardware processor, a sparse embedding matrix for said 1-2 norm with an associated hash function;

multiplying, using said hardware processor, said spare embedding matrix with said T q (A) to obtain a first product;

multiplying, using said hardware processor, said spare embedding matrix with said vector (b) to obtain a second product; and

run an iterative regression solver device on said modified nonlinear regression problem with p =2 to generate an output vector for said image classification system, said regression solver generating said output vector in an accelerated time according to:

O(nnz(A)log 2 q)+poly(dq/ϵ) , where nnz(A) represents a number of non-zero entries of the matrix A and ϵ is a pre-specified accuracy parameter ϵ>0,

wherein said output vector is used in classifying said image.

7. The system of claim 6 , wherein the T q (A) expands said matrix A to said (n ×(dq)) matrix by replacing each entry A i,j with a q-tuple (1, A i,j , A i,j 2 , . . . , A i,j q−1 ).

8. The system of claim 6 ,

wherein the generated output vector is an output vector x′ that satisfies |Ax′-b| p ≤(1+eps) min x |Ax-b| p , where eps(ϵ)>0 is a user-specified accuracy parameter.

9. A computer program product for an image classification system involving a fast nonlinear regression problem used to classify an image, the computer program product comprising a non-transitory storage medium readable by a processing circuit, the computer program product storing instructions run by the processing circuit for performing method steps comprising:

receiving, at the processing circuit, input data corresponding to a image feature design matrix (A) of values representing an image, wherein matrix (A) is an n×d matrix where n>d, and receiving data representing a corresponding output data target vector (b), and

forming, at the processing circuit, a nonlinear regression problem to be solved, said nonlinear regression problem being of a form min xϵC ∥Ax−b∥ p , where x is a matrix, p is an 1-2 norm, and C is a constraint set; and

modifying said nonlinear regression problem by:

applying, using said processing circuit, a matrix operator T q to said matrix (A) to generate data representing a block-Vandermonde structured matrix T q (A), said T q (A) expanding matrix (A) to an (n×(dq)) matrix, said block-Vandermonde structured matrix having a fast vector-matrix method associated therewith;

generating, using said processing circuit, a sparse embedding matrix for said 1-2 norm with an associated hash function;

multiplying, using said processing circuit, said spare embedding matrix with said T q (A) to obtain a first product;

multiplying, using said processing circuit, said spare embedding matrix with said vector (b) to obtain a second product; and

running an iterative regression solver device on said modified nonlinear regression problem with p=2 to generate an output vector for said image classification system, said regression solver generating said output vector in an accelerated time according to:

O(nnz(A)log 2 q)+poly(dq/ϵ) , where nnz(A) represents a number of non-zero entries of the matrix A and ϵ is a pre-specified accuracy parameter ϵ>0,

wherein said output vector is used in classifying said image.

10. The computer program product of claim 9 , wherein the T q (A) expands said matrix A to an (n ×(dq)) matrix by replacing each entry A i,j with the q-tuple (1, A i,j , A i,j 2 , . . . , A i,j q−1 ).

11. The computer program product of claim 9 , wherein the

generated output vector is an output vector x′ that satisfies |Ax′-b| p <(1+eps) min x |Ax-b| p , where eps(ϵ)>0 is a user-specified accuracy parameter.