#!/bin/env/python


def sketch_sq_sample(X, Y):
    pass


def main():
    pass

if __name__ == '__main__':
    main()

@@ -12,16 +12,294 @@
 python%0A%0A
+import numpy as np%0A%0A%0Adef _compute_dim_scores(A, B, A_col_norms=None, B_row_norms=None):%0A    if A_col_norms is None:%0A        A_col_norms = np.linalg.norm(A, axis=0)%0A    if B_row_norms is None:%0A        B_row_norms = np.linalg.norm(B, axis=1)%0A    return A_col_norms * B_row_norms%0A%0A
 %0Adef ske
@@ -316,46 +316,1321 @@
 ple(
-X, Y
+A, B, d
 ):%0A    
-pass%0A%0A%0Adef main():%0A    pass
+scores = _compute_dim_scores(A, B)%0A    probs = scores / np.sum(scores)%0A    D = A.shape%5B1%5D%0A    keep_idxs = np.random.choice(D, size=d, p=probs)%0A%0A    weights = np.sqrt(d * probs%5Bkeep_idxs%5D)%0A    return A%5B:, keep_idxs%5D / weights, B%5Bkeep_idxs%5D / weights.reshape(-1, 1)%0A%0A%0Adef sketch_sq_deterministic(A, B, d):%0A    scores = _compute_dim_scores(A, B)%0A    D = A.shape%5B1%5D%0A    keep_idxs = np.argsort(scores)%5B::-d%5D%0A%0A    weights = np.sqrt(d * (1. / D))  # uniform prob%0A    return A%5B:, keep_idxs%5D / weights, B%5Bkeep_idxs%5D / weights%0A%0A%0Adef main():%0A    N, M, D = 100, 50, 200%0A    np.random.seed(1234)%0A    A = np.random.randint(5, size=(N, D)).astype(np.float32)%0A    B = np.random.randint(5, size=(D, M)).astype(np.float32)%0A%0A    AB = A @ B%0A    orig_frob_sq = np.sum(AB * AB)%0A%0A    # normed_errs = %5B%5D%0A    prev_normed_err = np.inf%0A    for d in (10, 20, 30, 40, 50):%0A        A_hat, B_hat = sketch_sq_sample(A, B, d)%0A        # A_hat, B_hat = sketch_sq_deterministic(A, B, d)%0A        AB_hat = A_hat @ B_hat%0A        diffs = AB - AB_hat%0A        err_frob_sq = np.sum(diffs * diffs)%0A        normed_err_sq = err_frob_sq / orig_frob_sq%0A        print('d = %7B%7D, err = %7B:.3f%7D'.format(d, normed_err_sq))%0A        assert normed_err_sq %3C prev_normed_err%0A        prev_normed_err = normed_err_sq%0A        # normed_errs.append(normed_err_sq)%0A
 %0A%0Aif

add drineas 2006 amm impl