Sketching structured matrices in nonlinear regression problems

Patent metadata

Field	Value
Publication number	US-9928214-B2
Application number	US-201414333978-A
Country	US
Kind code	B2
Filing date	Jul 17, 2014
Priority date	Dec 4, 2013
Publication date	Mar 27, 2018
Grant date	Mar 27, 2018

Abstract

A system, method and computer program product for quickly and approximately solving structured regression problems. In one aspect, the system, method and computer program product are applied to problems that arise naturally in various statistical modeling settings—when the design matrix is a Vandermonde matrix or a sequence of such matrices. Using the Vandermonde matrix structure further accelerates the solution of the regression problem, achieving running times that are faster than “input sparsity”. The modeling framework speedup benefits of randomized regression for solving structured regression problems.

First claim

The invention claimed is:

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.

Assignees

• IBM

Inventors

• Avron Haim
• Sindhwani Vikas
• Woodruff David P

Classifications

• G06F17/18 Primary

  for evaluating statistical data {, e.g. average values, frequency distributions, probability functions, regression analysis (forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04)} · CPC title

• G06F17/10

  Complex mathematical operations {(function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544)} · CPC title

• G06F40/30

  Semantic analysis · CPC title

• G06F17/16

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

• G06F17/2785

  Physics · mapped topic