Neural Sync Active

Randomized Regression

Registry Synced

Randomized Regression

102 words

1 min read

Reading compass

Now · 7.1 Leverage Score Sampling

Randomized Regression

7.1 Leverage Score Sampling

Leverage score:

h_{ii} = \mathbf{x}_i^T(\mathbf{X}^T\mathbf{X})^{-1}\mathbf{x}_i

Higher leverage = more influential point. Sample rows proportional to leverage for a fast, accurate regression.


python
import numpy as np
def leverage_score_sampling(X, y, k):
    n, p = X.shape
    U, _, _ = np.linalg.svd(X, full_matrices=False)
    leverage = np.sum(U**2, axis=1)
    prob = leverage / np.sum(leverage)
    idx = np.random.choice(n, size=k, replace=False, p=prob)
    return X[idx], y[idx]

7.2 Sketched Regression

Use random projection to reduce

n

before regression:

\min ||\mathbf{SA}\beta - \mathbf{Sb}||_2^2

Where

\mathbf{S}

is a random sketching matrix (count-sketch, Gaussian, or Hadamard). Join Discord PreviousMinHash, SimHash, BloomNextMatrix Sketching