Fine-grained Provenance for Linear Algebra Operators

Provenance is well-understood for relational query operators. Increasingly, however, data analytics is incorporating operations expressed through linear algebra: machine learning operations, network centrality measures, and so on. In this paper, we study provenance information for matrix data and linear algebra operations. Our core technique builds upon provenance for aggregate queries and constructs a K semialgebra. This approach tracks provenance by annotating matrix data and propagating these annotations through linear algebra operations. We investigate applications in matrix inversion and graph analysis.