12

I have a generic matrix A which is symmetric, positive definite and sparsely populated (it's also quite big, say composed of tens to hundreds thousands rows). I would like to have a neural network learn how to find a matrix B that resembles the inverse of A (ie: that multiplied by A will yeld a minimal spread of the spectral radius) as accurately and as fast as possible.

I was wondering if there are some AI branches that are focused on this kind of problems or if not how could I approach it.

I know the classical algorithms used to do this, but I would just like to have a look at the possibilities offered by machine learning on the subject.

Sovos
  • 231
  • 2
  • 4
  • It would also be interesting to know if the determinant can be approximated by a neural network. – Simd Oct 16 '17 at 11:18

1 Answers1

10

In general this problem falls under the umbrella of "structured prediction" since you are trying to estimate a number of things that are related by virtue of being embedded in a PSD matrix.

Instead of estimating the inverse in one swoop, I'd pick an appropriate algorithm, say inversion by eigendecomposition, estimate the components (eigenvalues and eigenvectors), then piece them together. Here's one paper that shows how: Neural networks based approach for computing eigenvectors and eigenvalues of symmetric matrix.

Alternatively, you can investigate approximation algorithms such as the one elaborated in Approximating the inverse of a symmetric positive definite matrix

Welcome to DataScience.SE

Emre
  • 10,491
  • 1
  • 29
  • 39
  • That's quite an interesting paper you cite. However, as I understand it, neural networks are best at solving non-linear problems, where exact analytical solutions don't exist. Inverting matrices, finding eigenvectors, etc, have well-understood algorithms that lead to exact solutions. As the neural network approach is likely to be slower, it is a bit hard to see what could be gained from such a solution. – John Powell Oct 19 '16 at 18:02
  • 2
    It's not a given that it will slower once the network is trained, since exact matrix inversion is cubic in time. Sovos asked how to invert a matrix with neural networks and I showed how; I didn't say that one should or had to use machine learning, let alone neural networks, but it is possible. I'd have started with approximate matrix inversion myself. – Emre Oct 19 '16 at 18:14
  • 1
    Indeed. Perhaps you could expand the answer. It is an interesting question, as to what classes of problem could potentially be solved with neural nets. I work in GIS where training any sensible network can take days, but your point about speed once trained is well taken. – John Powell Oct 19 '16 at 18:23
  • 5
    Hmmm, I had the exact same idea (use neuralnet to find approximate inverse of a matrix), and googled to see if someone has done that, and arrived here :) – Hugh Perkins Sep 04 '17 at 15:48