leverage_scores.py

# leverage scores l_[i] = tr(X @ (X^T X)^-1 @ X)
# indication of self-sensitivity or self-influence of i-th sample.
import numpy as np

n = 2048 # samples
d = 256 # dimensions
X = np.random.randn(n, d) # design matrix

# navie computation, high memory footprint (quadtratic in n^2) 
l_naive = np.trace(X @ np.linalg.inv(X) @ X)

# less memory (linear in n), less compute, more robust
l_refactored = (X * np.linalg.pinv(X).T).sum(-1)

print("sorted diff", np.sort(l_naive - l_refactored))
print("allclose?", np.allclose(l_naive, l_refactored))

# some algebra
# l_i = trace( X @ (X^T X)^-1 @ X )
# l_i = trace( X @ X^pinv )
# l_i = sum_j( x_ij @ x^pinv_ji )
# l_i = sum_j( X * X^pinv^T )