1import numpy as np
 2
 3
 4def select_signs(candidates, residual, descent, rho=0.05):
 5    """Select +/- signs minimizing infinity norm under a descent constraint.
 6
 7    Parameters
 8    ----------
 9    candidates : (n, m) array
10        Candidate residual updates.
11    residual : (m,) array
12        Accumulated residual state before this round.
13    descent : (m,) array
14        Desired descent direction (the experiment uses the mean candidate).
15    rho : float
16        Required projection coefficient.
17
18    Returns
19    -------
20    signs : (n,) array of +/-1
21    feasible : bool
22        Whether the returned signs satisfy the projection constraint.
23
24    Exhaustive search is used for n <= 8. For larger n, a coordinate-flip
25    local search is used, as proposed in the implementation plan.
26    """
27    candidates = np.asarray(candidates, dtype=float)
28    residual = np.asarray(residual, dtype=float)
29    descent = np.asarray(descent, dtype=float)
30    n = candidates.shape[0]
31    threshold = rho * float(descent @ descent)
32
33    def update(s):
34        return residual + s @ candidates
35
36    def feasible(s):
37        return float(descent @ (s @ candidates)) >= threshold - 1e-12
38
39    def objective(s):
40        return float(np.max(np.abs(update(s))))
41
42    if n <= 8:
43        best = None
44        for mask in range(1 << n):
45            s = np.array([1.0 if mask & (1 << j) else -1.0
46                          for j in range(n)])
47            if feasible(s):
48                candidate = (objective(s), s)
49                if best is None or candidate[0] < best[0]:
50                    best = candidate
51        if best is not None:
52            return best[1], True
53        return np.ones(n), False
54
55    signs = np.ones(n)
56    if not feasible(signs):
57        return signs, False
58    value = objective(signs)
59    for _ in range(3):
60        changed = False
61        for j in range(n):
62            trial = signs.copy()
63            trial[j] *= -1
64            trial_value = objective(trial)
65            if feasible(trial) and trial_value < value - 1e-12:
66                signs, value = trial, trial_value
67                changed = True
68        if not changed:
69            break
70    return signs, feasible(signs)
71
72
73def infinity_norm(x):
74    """Coordinatewise maximum norm used by the discrepancy objective."""
75    return float(np.max(np.abs(np.asarray(x))))