Streaming Polyphase Factor Decomposition / SKAT

Download original file

This is the original source text. Reading it does not run or verify the program.

Read the typeset paper

1 import unittest
2 import numpy as np
3 
4 from spectral_tail_bridge import (
5     certify_operator_pruning,
6     range_core_certificate,
7     spectral_interval_from_pruned_operator,
8     dual_budget_greedy_schedule,
9 )
10 
11 
12 class SpectralTailBridgeTests(unittest.TestCase):
13     def test_block_norm_bound_dominates_operator_norm(self):
14         rng = np.random.default_rng(1)
15         widths = [3, 4, 2]
16         n = sum(widths)
17         E = rng.normal(size=(n, n))
18         E = 0.5 * (E + E.T)
19         H0 = rng.normal(size=(n, n))
20         H0 = 0.5 * (H0 + H0.T)
21         H = H0 + E
22         cert = certify_operator_pruning(H, H0, widths)
23         self.assertLessEqual(
24             cert.exact_operator_error,
25             cert.block_norm_error_bound + 1e-12
26         )
27 
28     def test_weyl_interval_contains_true_eigenvalues(self):
29         rng = np.random.default_rng(2)
30         A = rng.normal(size=(16, 12))
31         H = A.T @ A
32         E = rng.normal(size=H.shape)
33         E = 0.5 * (E + E.T)
34         E *= 1e-3 / np.linalg.norm(E, ord=2)
35         H0 = H - E
36         cert = certify_operator_pruning(H, H0, [4,4,4])
37         interval = spectral_interval_from_pruned_operator(
38             H0, cert.block_norm_error_bound
39         )
40         true = np.linalg.eigvalsh(H)[::-1]
41         self.assertTrue(np.all(true >= interval.lower - 1e-10))
42         self.assertTrue(np.all(true <= interval.upper + 1e-10))
43 
44     def test_range_core_interval_contains_true_singular_values(self):
45         rng = np.random.default_rng(3)
46         A = rng.normal(size=(20, 15))
47         U = rng.normal(size=(20, 7))
48         cert = range_core_certificate(A, U)
49         true = np.linalg.svd(A, compute_uv=False)
50         self.assertTrue(
51             np.all(true >= cert.lower_singular_values - 1e-10)
52         )
53         self.assertTrue(
54             np.all(true <= cert.upper_singular_values + 1e-10)
55         )
56 
57 
58     def test_dual_budget_scheduler_respects_both_budgets(self):
59         from budget_scheduler import edge_risks_depth
60         B = np.array([
61             [1.0, 0.10, 0.01],
62             [0.10, 1.0, 0.02],
63             [0.01, 0.02, 1.0],
64         ])
65         rho = np.array([1.0, 0.0, 0.0])
66         risks = edge_risks_depth(B, rho, 3)
67         r = dual_budget_greedy_schedule(
68             B, risks, query_budget=0.2, operator_budget=0.03
69         )
70         self.assertTrue(r.certificate_valid)
71         self.assertLessEqual(r.additive_query_bound, 0.2 + 1e-15)
72         self.assertLessEqual(r.operator_norm_bound, 0.03 + 1e-15)
73 
74 
75     def test_tail_bracket_contains_true_probability(self):
76         import math
77         from spectral_tail_bridge import positive_quadratic_tail_bracket
78         from kcos_v2 import adaptive_kcos_logsf
79         rng = np.random.default_rng(9)
80         A = rng.normal(size=(12, 10))
81         H = A.T @ A
82         E = rng.normal(size=H.shape)
83         E = 0.5 * (E + E.T)
84         E *= 1e-3 / np.linalg.norm(E, ord=2)
85         H0 = H - E
86         eps = np.linalg.norm(E, ord=2)
87         interval = spectral_interval_from_pruned_operator(H0, eps)
88         lam = np.linalg.eigvalsh(H)[::-1]
89         mean = float(np.sum(lam))
90         q = mean + 4.0 * math.sqrt(2.0 * np.sum(lam * lam))
91         true = adaptive_kcos_logsf(q, lam, relative_tolerance=1e-9)
92         bracket = positive_quadratic_tail_bracket(
93             q, interval, relative_tolerance=1e-8
94         )
95         self.assertLessEqual(bracket.lower_log_p, true.log_p + 1e-9)
96         self.assertGreaterEqual(bracket.upper_log_p, true.log_p - 1e-9)
97 
98 
99 if __name__ == "__main__":
100     unittest.main(verbosity=2)

Back to source controls

Back to Streaming Polyphase Factor Decomposition / SKAT