Sketching structured matrices in nonlinear regression problems
AssigneeInternational Business Machines Corporation
InventorsHaim Avron, Vikas Sindhwani, David P. Woodruff
Life of this patent
Estimating the term…
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.
Claims20
A computer-implemented method for solving fast nonlinear regression and classification problems comprising:
- sketching an input data and output data using sparse embedding matrices and structured random matrices;
- utilizing structure in the data to accelerate sketching, said structure is a Vandermonde matrix form;
- and
- solving a regression problem on the sketched data, a hardware processor performing one or more said sketching, structure utilizing and problem solving.
A system for solving fast nonlinear regression and classification problems comprising:
- a memory;
- a hardware processor coupled to the memory, the hardware processor configured to perform a method comprising:
- sketching an input data and output data using sparse embedding matrices and structured random matrices;
- utilizing structure in the input data and output data to accelerate sketching, said structure is a Vandermonde matrix form;
- and
- solving a regression problem on the sketched data.
A computer program product for solving fast nonlinear regression and classification problems, the computer program product comprising a storage medium readable by a processing circuit, said storage medium not a propagating signal, the computer program product storing instructions run by the processing circuit for performing method steps comprising:
- sketching an input data and output data using sparse embedding matrices and structured random matrices;
- utilizing structure in the input data and output data to accelerate sketching, said structure is a Vandermonde matrix form;
- and
- solving a regression problem on the sketched data.
Dependencies are inferred from the claim text.