Gauss quadrature for matrix inverse forms with applications
We present a framework for accelerating a spectrum of machine learning algorithms that require computation of bilinear inverse forms u[superscript T] A[superscript −1]u, where A is a positive definite matrix and u a given vector. Our framework is built on Gauss-type quadrature and easily scales to...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Proceedings of Machine Learning Research
2017
|
| Online Access: | http://hdl.handle.net/1721.1/113000 https://orcid.org/0000-0003-1532-3083 https://orcid.org/0000-0001-8516-4925 https://orcid.org/0000-0002-6121-9474 |
| Summary: | We present a framework for accelerating a spectrum of machine learning algorithms that require computation of bilinear inverse forms u[superscript T] A[superscript −1]u, where A is a positive definite matrix and u a given
vector. Our framework is built on Gauss-type quadrature and easily scales to large, sparse matrices. Further, it allows retrospective computation of lower and upper bounds on u[superscript T] > A[superscript −1]u, which in
turn accelerates several algorithms. We prove that these bounds tighten iteratively and converge at a linear (geometric) rate. To our knowledge, ours is the first work to demonstrate these key properties of Gauss-type quadrature, which is a classical and deeply studied topic. We illustrate empirical consequences of our results by using quadrature to accelerate machine learning tasks involving determinantal point processes and submodular optimization, and observe tremendous speedups in several
instances. |
|---|