Symmetric¶

Sthocastic Lanczos Quadrature¶

Given a semi-positive definite matrix \(A \in \mathbb R^{|V|\times|V|}\), which has the set of eigenvalues given by \(\{\lambda_i\}\) a trace of a matrix function is given by

\[\mathrm{tr}(f(A)) = \sum\limits_{i=0}^{|V|} f(\lambda_i)\]

The methods for calculating such traces functions have a cubic computational complexity lower bound, \(O(|V|^3)\). Therefore, it is not feasible for large networks. One way to overcome such computational complexity it is use stochastic approximations combined with a mryiad of another methods to get the results with enough accuracy and with a small computational cost. The methods available in this module uses the Sthocastic Lanczos Quadrature, a procedure proposed in the work made by Ubaru, S. et.al. [1] (you need to cite them).

References

[1] Ubaru, S., Chen, J., & Saad, Y. (2017). Fast Estimation of tr(f(A)) via Stochastic Lanczos Quadrature. SIAM Journal on Matrix Analysis and Applications, 38(4), 1075-1099.

[2] Hutchinson, M. F. (1990). A stochastic estimator of the trace of the influence matrix for laplacian smoothing splines. Communications in Statistics-Simulation and Computation, 19(2), 433-450.

emate.symmetric.slq.pyslq(A, num_vecs, num_steps, trace_function, device='/gpu:0', precision=32, random_factory=<function radamacher>, parallel_iterations=10, swap_memory=False, infer_shape=False)[source]¶

Compute the approxiamted value of a given trace function using the sthocastic Lanczos quadrature using Radamacher’s random vectors.

Parameters:

A (scipy sparse matrix) – The semi-positive definite matrix
num_vecs (int) – Number of random vectors in oder to aproximate the trace
num_steps (int) – Number of Lanczos steps

trace_function (function) –

A function like

def trace_function(eig_vals)
    *tensorflow ops
    return result

precision (int) –
1. Single or (64) double precision

Returns:

f_estimation (float) – The approximated value of the given trace function
gammas (array of floats) – See [1] for more details

References

[1] Ubaru, S., Chen, J., & Saad, Y. (2017). Fast Estimation of tr(f(A)) via Stochastic Lanczos Quadrature. SIAM Journal on Matrix Analysis and Applications, 38(4), 1075-1099.