"""Wasserman (2006), Chapter 9: Wavelets and Other Adaptive Methods.

Companion code for Chapter 9 of L. Wasserman, All of Nonparametric Statistics (Springer, 2006),
pp. 197-225, written from scratch with numpy, scipy and matplotlib, to be read next to the lecture
notes (../ch09-wavelets-adaptive-methods.html). No wavelet library is used: the Haar, Daubechies and
symmlet filters are built here by spectral factorisation, and the transforms are coded directly.

Methods
* Test functions: blocks (Example 9.39, with its exact antiderivative), doppler (Example 5.63),
  heavisine.
* Section 9.2, constructing wavelets: daubechies_filter (spectral factorisation of
  |m0|^2 = cos^{2N}(t/2) P(sin^2(t/2)); extremal phase or least asymmetric = symmlet), highpass
  (the mother filter h_k = (-1)^{k+1} l_{1-k}, shifted), m0 (9.19), cascade (the scaling function and
  the mother wavelet on a dyadic grid, from the two-scale relation (9.16)).
* Section 9.12, the cascade algorithm: dwt and idwt (periodised, orthonormal; (9.55)-(9.59)),
  dwt_matrix.
* Sections 9.3-9.4, wavelet regression: mad_sigma (the robust noise estimate), soft, hard,
  universal threshold (9.32), sure_threshold ((9.38), with the optional hybrid rule), js_level
  (James-Stein per level), wavelet_smooth (VisuShrink, SureShrink, hard, level-wise James-Stein;
  periodic or mirrored boundary, Section 9.7).
* Risk calculations: soft_risk and hard_risk (exact, Exercise 8), oracle_risk (9.36).
* Linear competitors: ll_fit (local linear regression with the tricube kernel, computed in row
  blocks, with the leave-one-out shortcut), ll_cv, nw_gauss (Nadaraya-Watson weights for ICI),
  react_cosine (nested-subset REACT in the cosine basis, Chapter 8).
* Section 9.8: basis_pursuit (block coordinate relaxation for a cosine plus spike dictionary).
* Section 9.9: ici (intersecting confidence intervals, Goldenshluger and Nemirovski 1997), lepski
  (a version of Lepski et al. 1997), sigma_rice (the difference estimator of Section 5.6).
* Exercise 6: haar_density (the wavelet histogram, SURE shrinkage per level and testing).

Figures. Figure 9.10 is a schematic of the cascade algorithm (boxes and arrows, nothing computed)
and is skipped. Figure 9.9 is drawn in the book as a schematic; here it is computed: the ICI
intervals of an actual Nadaraya-Watson fit of Doppler data at one point. Every other figure,
9.1-9.8, is reproduced. Supplementary figures:
  9.S1 the Daubechies family: scaling functions and mother wavelets for N = 1, 2, 4 and the symmlet 8;
  9.S2 exact risk of soft and hard thresholding (Exercise 8) and the oracle inequality (9.37);
  9.S3 sparsity: n-term approximation errors in the Haar, symmlet and cosine bases;
  9.S4 Exercise 5: wavelet, REACT and local linear fits of Doppler data;
  9.S5 Exercise 6: the Haar wavelet histogram of the geyser durations;
  9.S6 Section 9.9 and Exercise 9: ICI and Lepski bandwidths along x;
  9.S7 Section 9.8: basis pursuit with a cosine plus spike dictionary;
  9.S8 Section 9.10: risk against n for the blocks function, wavelets against local linear regression.
Run `python3 ch09_wavelets_adaptive_methods.py --list`, `python3 ch09_wavelets_adaptive_methods.py`
(all figures, a few minutes on one CPU thread) or `python3 ch09_wavelets_adaptive_methods.py --fig 9.7`.
Files go to ../img/ch09/; the data used by the browser demonstrations go to ../data/ch09-*.json.
"""
import itertools
import json
import os
from math import comb

import numpy as np
from scipy import integrate
from scipy.fft import dct, idct
from scipy.stats import norm

import common
from common import BLUE, GREEN, GREY, ORANGE, PURPLE, RED, panel_grid, panel_label, plt, savefig

CH = 9
HERE = os.path.dirname(os.path.abspath(__file__))
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))
CACHE_DIR = os.path.join(HERE, "cache")

# =========================================================================== test functions
BLOCKS_T = np.array([0.10, 0.13, 0.15, 0.23, 0.25, 0.40, 0.44, 0.65, 0.76, 0.78, 0.81])
BLOCKS_H = np.array([4, -5, 3, -4, 5, -4.2, 2.1, 4.3, -3.1, 2.1, -4.2])
BLOCKS_C = 3.655606


def blocks(x):
    """The blocks function of Example 9.39: 3.655606 * sum_j h_j K(x - t_j), K(t) = (1 + sgn t)/2."""
    x = np.asarray(x, dtype=float)
    return BLOCKS_C * ((1 + np.sign(x[..., None] - BLOCKS_T)) / 2 * BLOCKS_H).sum(-1)


def blocks_antideriv(x):
    """F(x) = int_0^x blocks(u) du, exactly (blocks is piecewise constant)."""
    x = np.asarray(x, dtype=float)
    return BLOCKS_C * (np.maximum(x[..., None] - BLOCKS_T, 0) * BLOCKS_H).sum(-1)


def doppler(x):
    """The Doppler function of Example 5.63: sqrt(x(1-x)) sin(2.1 pi / (x + 0.05))."""
    x = np.asarray(x, dtype=float)
    return np.sqrt(x * (1 - x)) * np.sin(2.1 * np.pi / (x + 0.05))


def heavisine(x):
    """Donoho and Johnstone's heavisine: 4 sin(4 pi x) - sgn(x - 0.3) - sgn(0.72 - x)."""
    x = np.asarray(x, dtype=float)
    return 4 * np.sin(4 * np.pi * x) - np.sign(x - 0.3) - np.sign(0.72 - x)


def design(n):
    """The equally spaced design x_i = i/n, i = 1, ..., n of (9.25)."""
    return np.arange(1, n + 1) / n


def simulate(fun, n, sigma, seed, contaminate=False):
    """Y_i = r(i/n) + sigma eps_i; with contaminate=True eps ~ 0.95 N(0,1) + 0.05 N(0,4) (Exercise 5b,
    N(0,4) read as variance 4)."""
    rng = np.random.default_rng(seed)
    x = design(n)
    e = rng.standard_normal(n)
    if contaminate:
        out = rng.random(n) < 0.05
        e = np.where(out, 2.0 * rng.standard_normal(n), e)
    return x, fun(x) + sigma * e


# =========================================================================== filters (Section 9.2)
SYM8_BOOK = np.array([0.0018899503, -0.0003029205, -0.0149522583, 0.0038087520, 0.0491371797,
                      -0.0272190299, -0.0519458381, 0.3644418948, 0.7771857517, 0.4813596513,
                      -0.0612733591, -0.1432942384, 0.0076074873, 0.0316950878, -0.0005421323,
                      -0.0033824160])


def _phase_nonlinearity(h):
    w = np.linspace(0, np.pi, 1025)[1:-1]
    H = np.exp(-1j * np.outer(w, np.arange(len(h)))) @ h
    ph = np.unwrap(np.angle(H))
    A = np.vstack([w, np.ones_like(w)]).T
    c = np.linalg.lstsq(A, ph, rcond=None)[0]
    return float(np.sum((ph - A @ c) ** 2))


def daubechies_filter(N, kind="extremal"):
    """Scaling coefficients l_0, ..., l_{2N-1} of the Daubechies wavelet with N vanishing moments.

    |m0(t)|^2 = cos^{2N}(t/2) P(sin^2(t/2)) with P(y) = sum_{k<N} C(N-1+k, k) y^k (the unique
    polynomial of degree < N making |m0(t)|^2 + |m0(t+pi)|^2 = 1). Each root y of P gives a reciprocal
    pair z, 1/z of z + 1/z = 2 - 4y; m0 keeps one root of each pair (conjugate pairs together). kind=
    'extremal' keeps the roots inside the unit circle (Daubechies' minimum phase choice); kind='symmlet'
    keeps the choice whose phase is closest to linear (the least asymmetric wavelet, the symmlet).
    Normalised so that sum l_k = sqrt 2 (condition (9.21)).
    """
    if N == 1:
        return np.array([1.0, 1.0]) / np.sqrt(2)
    P = [comb(N - 1 + k, k) for k in range(N)]
    yroots = np.roots(P[::-1])
    zs = []
    for y in yroots:
        z = np.roots([1, -(2 - 4 * y), 1])
        zs.append(z[np.argmin(np.abs(z))])
    groups, used = [], [False] * len(zs)
    for i, z in enumerate(zs):
        if used[i]:
            continue
        used[i] = True
        if abs(z.imag) < 1e-9:
            groups.append([z.real])
            continue
        j = min((k for k in range(len(zs)) if not used[k]), key=lambda k: abs(zs[k] - np.conj(z)))
        used[j] = True
        groups.append([z, zs[j]])
    choices = [tuple([0] * len(groups))] if kind == "extremal" else itertools.product([0, 1], repeat=len(groups))
    best, best_score = None, np.inf
    for ch in choices:
        roots = [-1.0] * N
        for c, g in zip(ch, groups):
            roots += [(r if c == 0 else 1 / r) for r in g]
        h = np.real(np.poly(roots))
        h = h / h.sum() * np.sqrt(2)
        score = _phase_nonlinearity(h) if kind == "symmlet" else 0.0
        if score < best_score:
            best, best_score = h, score
    return best


def wavelet_filter(name):
    """'haar', 'd4' (Daubechies N = 2), 'd8' (N = 4), 'sym8' (symmlet, N = 8)."""
    return {"haar": lambda: daubechies_filter(1), "d4": lambda: daubechies_filter(2),
            "d8": lambda: daubechies_filter(4), "sym8": lambda: daubechies_filter(8, "symmlet")}[name]()


def highpass(h):
    """Mother wavelet filter g_m = (-1)^{m+1} l_{L-1-m}, m = 0..L-1: the book's h_k = (-1)^{k+1} l_{1-k}
    of (9.59), shifted by the even amount L - 2 so that the indices start at 0."""
    L = len(h)
    return np.array([(-1) ** (m + 1) * h[L - 1 - m] for m in range(L)])


def m0(t, h):
    """m0(t) = (1/sqrt 2) sum_k l_k e^{-itk} of (9.19)."""
    t = np.asarray(t, dtype=float)
    return np.exp(-1j * np.multiply.outer(t, np.arange(len(h)))) @ h / np.sqrt(2)


def cascade(h, levels=10, mother=True):
    """phi (or psi) on the grid k / 2^levels by iterating c <- sqrt2 sum_k l_{n-2k} c_k (from (9.16)).

    Returns (x, values). phi lives on [0, L-1]; psi, built with one step of the high-pass filter
    first, lives on [0, L-1] as well; the book's convention puts psi on [-N+1, N], i.e. shifted by
    -(L/2 - 1)."""
    c = np.array([1.0])
    first = highpass(h) if mother else h
    for it in range(levels):
        f = first if it == 0 else h
        up = np.zeros(2 * len(c) - 1)
        up[::2] = c
        c = np.sqrt(2) * np.convolve(up, f)
    x = np.arange(len(c)) / 2.0 ** levels
    return x, c


# =========================================================================== the transform (Section 9.12)
def _analysis(a, h, g):
    n = len(a)
    L = len(h)
    idx = (2 * np.arange(n // 2)[:, None] + np.arange(L)[None, :]) % n
    A = a[idx]
    return A @ h, A @ g


def _synthesis(lo, hi, h, g):
    m = len(lo)
    n = 2 * m
    L = len(h)
    out = np.zeros(n)
    idx = (2 * np.arange(m)[:, None] + np.arange(L)[None, :]) % n
    np.add.at(out, idx, lo[:, None] * h[None, :] + hi[:, None] * g[None, :])
    return out


def dwt(y, h, j0=0):
    """Periodised orthonormal DWT of y (length n = 2^J) down to level j0, by the cascade equations
    (9.55)-(9.56): alpha_{j,k} = sum_r l_{r-2k} alpha_{j+1,r}, beta_{j,k} = sum_r h_{r-2k} alpha_{j+1,r}.

    Returns [s (2^j0 scaling coefficients), d_j0, d_{j0+1}, ..., d_{J-1}], d_j of length 2^j.
    With y_i = Y_i the coefficients are sqrt(n) times the book's S_k and D_jk (footnote 2, p. 207)."""
    y = np.asarray(y, dtype=float)
    n = len(y)
    J = int(round(np.log2(n)))
    assert 2 ** J == n, "n must be a power of 2"
    g = highpass(h)
    a = y.copy()
    details = []
    for j in range(J - 1, j0 - 1, -1):
        a, d = _analysis(a, h, g)
        details.append(d)
    return [a] + details[::-1]


def idwt(coeffs, h):
    """Inverse of dwt."""
    g = highpass(h)
    a = np.asarray(coeffs[0], dtype=float)
    for d in coeffs[1:]:
        a = _synthesis(a, np.asarray(d, dtype=float), h, g)
    return a


def dwt_matrix(n, h, j0=0):
    """The n x n matrix W of the transform (rows = basis vectors)."""
    return np.array([np.concatenate(dwt(e, h, j0)) for e in np.eye(n)]).T


# =========================================================================== thresholding (Sections 9.3, 9.4)
def soft(d, lam):
    """Soft threshold (9.31): sign(d)(|d| - lambda)_+."""
    return np.sign(d) * np.maximum(np.abs(d) - lam, 0.0)


def hard(d, lam):
    """Hard threshold (9.29)."""
    return np.where(np.abs(d) >= lam, d, 0.0)


def mad_sigma(d_finest):
    """sigma-hat = median|D - median D| / 0.6745 on the finest level (scaling of footnote 2)."""
    d = np.asarray(d_finest)
    return float(np.median(np.abs(d - np.median(d))) / 0.6745)


def sure_threshold(d, hybrid=False):
    """Threshold t for standardised coefficients d (noise variance 1) minimising SURE (9.38):
    S(t) = m - 2 #{|d_k| <= t} + sum min(d_k^2, t^2), over 0 <= t <= sqrt(2 log m).
    With hybrid=True, the universal threshold is used when the level looks sparse (Donoho and
    Johnstone 1995): (sum d^2 - m)/m <= (log2 m)^{3/2} / sqrt m."""
    d = np.abs(np.asarray(d, dtype=float))
    m = len(d)
    tu = np.sqrt(2 * np.log(m)) if m > 1 else 0.0
    if hybrid and (np.sum(d ** 2) - m) / m <= np.log2(max(m, 2)) ** 1.5 / np.sqrt(m):
        return tu
    a = np.sort(d)
    cand = np.concatenate([[0.0], a[a <= tu], [tu]])
    cs = np.cumsum(a ** 2)
    # #{|d| <= t} and sum min(d^2, t^2) for each candidate t
    k = np.searchsorted(a, cand, side="right")
    low = np.where(k > 0, cs[np.maximum(k - 1, 0)], 0.0)
    s = m - 2 * k + low + (m - k) * cand ** 2
    return float(cand[np.argmin(s)])


def sure_value(d, t):
    """SURE (9.38) in standardised form, for checking."""
    d = np.abs(np.asarray(d))
    return float(len(d) - 2 * np.sum(d <= t) + np.sum(np.minimum(d ** 2, t ** 2)))


def js_level(d):
    """Positive-part James-Stein on one level of standardised coefficients."""
    m = len(d)
    s = float(np.sum(np.asarray(d) ** 2))
    return max(0.0, 1.0 - (m - 2) / s) * np.asarray(d) if s > 0 else np.zeros(m)


def wavelet_smooth(y, h, j0=5, rule="soft", lam_mult=1.0, sigma=None, boundary="periodic", hybrid=False):
    """Wavelet regression of Sections 9.3-9.4 for equally spaced y (n = 2^J).

    rule: 'soft' (VisuShrink: universal threshold (9.32), soft), 'hard' (universal, hard), 'sure'
    (SureShrink: a SURE threshold per level, soft), 'js' (James-Stein per level), 'none'.
    The universal threshold is lam_mult * sigma sqrt(2 log n) in the sqrt(n) scaling of footnote 2.
    boundary='reflect' mirrors the data (Section 9.7): transform (y, reversed y), keep the first half.
    Returns (fit, info) with info = sigma-hat, threshold, number of coefficients kept, coefficients."""
    y = np.asarray(y, dtype=float)
    n0 = len(y)
    yy = np.concatenate([y, y[::-1]]) if boundary == "reflect" else y
    c = dwt(yy, h, j0)
    s = mad_sigma(c[-1]) if sigma is None else sigma
    lam = lam_mult * s * np.sqrt(2 * np.log(n0))
    out, lams = [c[0]], []
    for d in c[1:]:
        if rule == "soft":
            out.append(soft(d, lam)); lams.append(lam)
        elif rule == "hard":
            out.append(hard(d, lam)); lams.append(lam)
        elif rule == "sure":
            t = s * sure_threshold(d / s, hybrid) if s > 0 else 0.0
            out.append(soft(d, t)); lams.append(t)
        elif rule == "js":
            out.append(s * js_level(d / s)); lams.append(np.nan)
        else:
            out.append(d); lams.append(0.0)
    fit = idwt(out, h)[:n0]
    kept = int(sum(np.count_nonzero(d) for d in out[1:]))
    return fit, {"sigma": s, "lam": lam, "lams": lams, "kept": kept, "coef": c, "shrunk": out}


# =========================================================================== exact risks (Exercise 8), oracle (9.36)
def soft_risk(theta, lam):
    """E(soft(X, lam) - theta)^2 for X ~ N(theta, 1), exactly."""
    th = np.asarray(theta, dtype=float)
    a, b = lam - th, -lam - th
    return (1 + lam ** 2 + (th ** 2 - lam ** 2 - 1) * (norm.cdf(a) - norm.cdf(b))
            - (lam - th) * norm.pdf(lam + th) - (lam + th) * norm.pdf(lam - th))


def hard_risk(theta, lam):
    """E(hard(X, lam) - theta)^2 for X ~ N(theta, 1), exactly."""
    th = np.asarray(theta, dtype=float)
    return (th ** 2 * (norm.cdf(lam - th) - norm.cdf(-lam - th)) + norm.sf(lam - th) + norm.sf(lam + th)
            + (lam - th) * norm.pdf(lam - th) + (lam + th) * norm.pdf(lam + th))


def oracle_risk(theta, eps2):
    """R*_n = sum min(theta_i^2, eps^2) of (9.36) (eps^2 = sigma^2/n)."""
    return float(np.sum(np.minimum(np.asarray(theta) ** 2, eps2)))


# =========================================================================== linear smoothers
def tricube(u):
    a = np.abs(u)
    return np.where(a < 1, (1 - a ** 3) ** 3, 0.0)


def ll_fit(x, Y, h, block=512):
    """Local linear regression (tricube kernel) at the design points.

    Y may be a vector or an n x m matrix of responses. Returns (fits, diag L, ok), computed in row
    blocks so that large n does not need the full n x n matrix."""
    x = np.asarray(x, dtype=float)
    Y = np.asarray(Y, dtype=float)
    n = len(x)
    F = np.zeros(Y.shape)
    dg = np.zeros(n)
    ok = True
    for s in range(0, n, block):
        D = x[None, :] - x[s:s + block, None]
        K = tricube(D / h)
        S1 = (K * D).sum(1)
        S2 = (K * D * D).sum(1)
        W = K * (S2[:, None] - D * S1[:, None])
        den = W.sum(1)
        if np.any(den <= 1e-300):
            ok = False
            den = np.where(den <= 1e-300, np.nan, den)
        W = W / den[:, None]
        F[s:s + block] = W @ Y
        dg[s:s + block] = W[np.arange(W.shape[0]), np.arange(s, s + W.shape[0])]
    return F, dg, ok


def ll_cv(x, y, hs):
    """Leave-one-out CV over the bandwidth grid hs (shortcut (5.35)); returns (best h, fit, scores)."""
    scores, fits = [], []
    for h in hs:
        F, dg, ok = ll_fit(x, y, h)
        if not ok or np.any(dg >= 1 - 1e-10):
            scores.append(np.inf); fits.append(None); continue
        scores.append(float(np.mean(((y - F) / (1 - dg)) ** 2)))
        fits.append(F)
    k = int(np.argmin(scores))
    return hs[k], fits[k], np.array(scores)


def ll_cv_many(x, Y, hs):
    """CV-chosen local linear fits for every column of Y (one pass over hs)."""
    best = np.full(Y.shape[1], np.inf)
    out = np.zeros(Y.shape)
    hbest = np.zeros(Y.shape[1])
    for h in hs:
        F, dg, ok = ll_fit(x, Y, h)
        if not ok or np.any(dg >= 1 - 1e-10):
            continue
        sc = np.mean(((Y - F) / (1 - dg)[:, None]) ** 2, axis=0)
        better = sc < best
        best[better] = sc[better]
        out[:, better] = F[:, better]
        hbest[better] = h
    return out, hbest


def log_grid(lo, hi, k):
    return np.exp(np.linspace(np.log(lo), np.log(hi), k))


def react_cosine(y, sigma):
    """Nested-subset REACT in the orthonormal cosine (DCT-II) basis: keep the first J coefficients,
    J minimising SURE: J sigma^2 + sum_{j >= J} (c_j^2 - sigma^2)."""
    c = dct(y, norm="ortho")
    tail = np.cumsum((c ** 2 - sigma ** 2)[::-1])[::-1]
    n = len(y)
    risk = np.array([J * sigma ** 2 + (tail[J] if J < n else 0.0) for J in range(n + 1)])
    J = int(np.argmin(risk))
    cc = c.copy()
    cc[J:] = 0
    return idct(cc, norm="ortho"), J


def sigma_rice(y):
    """The first-difference estimator of Section 5.6: sum (Y_{i+1} - Y_i)^2 / (2(n-1))."""
    return float(np.sqrt(np.sum(np.diff(y) ** 2) / (2 * (len(y) - 1))))


# =========================================================================== Section 9.8: basis pursuit
def basis_pursuit(y, lam, iters=200):
    """min ||y - C a - b||^2 + lam (||a||_1 + ||b||_1) with C the orthonormal cosine basis and b the
    spike basis, by block coordinate relaxation: each block update is an exact soft threshold at lam/2
    (the blocks are orthonormal). Returns (a, b, objective values)."""
    a = np.zeros(len(y))
    b = np.zeros(len(y))
    obj = []
    for _ in range(iters):
        a = soft(dct(y - b, norm="ortho"), lam / 2)
        b = soft(y - idct(a, norm="ortho"), lam / 2)
        r = y - idct(a, norm="ortho") - b
        obj.append(float(r @ r + lam * (np.abs(a).sum() + np.abs(b).sum())))
    return a, b, np.array(obj)


def spikes_signal(n=512):
    x = design(n)
    smooth = 2 * np.cos(3 * np.pi * x) + np.cos(9 * np.pi * x)
    sp = np.zeros(n)
    for pos, ht in [(0.18, 4.0), (0.42, -3.5), (0.61, 5.0), (0.83, 3.0)]:
        sp[int(round(pos * n)) - 1] = ht
    return x, smooth, sp


# =========================================================================== Section 9.9: ICI and Lepski
def nw_gauss_all(x, hs, Y, sigma=1.0):
    """Nadaraya-Watson (Gaussian kernel) fits for every bandwidth in hs at the design points:
    returns fits[j, i] (or fits[j, i, m] for a matrix Y), the standard deviations
    s_j(x_i) = sigma ||l(x_i, h_j)||, and the means sum_k l_k(x_i) r(x_k) are left to the caller."""
    x = np.asarray(x, dtype=float)
    D = x[None, :] - x[:, None]
    fits, sds = [], []
    for h in hs:
        W = np.exp(-0.5 * (D / h) ** 2)
        W /= W.sum(1, keepdims=True)
        fits.append(W @ Y)
        sds.append(sigma * np.sqrt((W ** 2).sum(1)))
    return np.array(fits), np.array(sds)


def nw_weights(x, h):
    D = x[None, :] - x[:, None]
    W = np.exp(-0.5 * (D / h) ** 2)
    return W / W.sum(1, keepdims=True)


def ici(fits, sds, gamma):
    """ICI with bandwidths in increasing order (rows): D_j = [r_j - gamma s_j, r_j + gamma s_j]
    (gamma = 2 kappa in the book); j+ = the largest k with D_1 cap ... cap D_k nonempty, (9.49).
    Returns (j+ per point, the estimate r_{j+} (9.48))."""
    lo = np.maximum.accumulate(fits - gamma * sds, axis=0)
    hi = np.minimum.accumulate(fits + gamma * sds, axis=0)
    ok = lo <= hi
    jp = ok.sum(0) - 1
    return jp, np.take_along_axis(fits, jp[None, :], 0)[0]


def lepski(fits, sds, gamma):
    """A version of Lepski's rule: the largest bandwidth h_j such that |r_j - r_k| <= gamma s_k for
    every smaller bandwidth h_k (k < j)."""
    J, n = fits.shape
    jh = np.zeros(n, dtype=int)
    for j in range(J):
        good = np.all(np.abs(fits[j][None, :] - fits[:j]) <= gamma * sds[:j], axis=0) if j else np.ones(n, bool)
        jh[good] = j
    return jh, np.take_along_axis(fits, jh[None, :], 0)[0]


ICI_N, ICI_SIGMA, ICI_SEED = 1024, 0.1, 909
ICI_H = log_grid(1.0 / 1024, 1.0, 50)
ICI_GAMMA_THEORY = 2 * np.sqrt(2 * np.log(ICI_N))   # 2 kappa with kappa = sqrt(2 log n)
ICI_GAMMA = 1.0                                       # a practical constant (Exercise 9)


def ici_data():
    return simulate(doppler, ICI_N, ICI_SIGMA, ICI_SEED)


def ici_analysis(gamma=None, sigma_known=True):
    x, y = ici_data()
    s = ICI_SIGMA if sigma_known else sigma_rice(y)
    fits, sds = nw_gauss_all(x, ICI_H, y, s)
    g = 2 * np.sqrt(2 * np.log(ICI_N)) if gamma is None else gamma
    jp, est = ici(fits, sds, g)
    return x, y, fits, sds, jp, est, s


# =========================================================================== Exercise 6: wavelet histogram
GEY_A, GEY_B = 1.5, 5.5


def geyser():
    df = common.nps_data("faithful.dat")
    return np.asarray(df["eruptions"], dtype=float)


def haar_density_coefs(u, J):
    """Empirical Haar coefficients beta_hat_jk = mean psi_jk(U_i), j < J, for data u in [0, 1), with the
    book's psi = -1 on the left half and +1 on the right half of each dyadic interval (half-open
    intervals [a, m) and [m, b), as in N_{x,y} of the exercise); also the variance estimates (2^j p_jk - beta^2)/n."""
    n = len(u)
    out = []
    for j in range(J):
        k = np.arange(2 ** j)
        left = np.array([np.sum((u >= kk / 2 ** j) & (u < (kk + 0.5) / 2 ** j)) for kk in k])
        right = np.array([np.sum((u >= (kk + 0.5) / 2 ** j) & (u < (kk + 1) / 2 ** j)) for kk in k])
        beta = 2 ** (j / 2) * (right - left) / n
        var = (2 ** j * (left + right) / n - beta ** 2) / n
        out.append({"beta": beta, "var": var, "left": left, "right": right})
    return out


def haar_eval(x, coefs, weights):
    """f(x) = 1 + sum_j sum_k w_jk beta_jk psi_jk(x) on [0, 1)."""
    f = np.ones_like(x)
    for j, (c, w) in enumerate(zip(coefs, weights)):
        k = np.minimum((x * 2 ** j).astype(int), 2 ** j - 1)
        frac = x * 2 ** j - k
        sgn = np.where(frac < 0.5, -1.0, 1.0)
        f += 2 ** (j / 2) * sgn * (w * c["beta"])[k]
    return f


def haar_density(u, J, method="sure", alpha=0.05):
    co = haar_density_coefs(u, J)
    ws = []
    for c in co:
        if method == "sure":
            s2, b2 = c["var"].sum(), (c["beta"] ** 2).sum()
            a = max(0.0, 1 - s2 / b2) if b2 > 0 else 0.0
            ws.append(np.full(len(c["beta"]), a))
        elif method == "test":
            tot = c["left"] + c["right"]
            z = np.where(tot > 0, (c["right"] - c["left"]) / np.sqrt(np.maximum(tot, 1)), 0.0)
            ws.append((np.abs(z) > norm.ppf(1 - alpha / 2)).astype(float))
        else:
            ws.append(np.ones(len(c["beta"])))
    return co, ws


def hist_cv(u, ms=range(1, 101)):
    """Histogram on [0, 1] with m bins chosen by the CV score of Chapter 6:
    2/((n-1)h) - (n+1)/((n-1)h) sum p_j^2, h = 1/m."""
    n = len(u)
    best = None
    for m in ms:
        p = np.histogram(u, bins=m, range=(0, 1))[0] / n
        h = 1.0 / m
        sc = 2 / ((n - 1) * h) - (n + 1) / ((n - 1) * h) * np.sum(p ** 2)
        if best is None or sc < best[0]:
            best = (sc, m)
    return best[1]


# =========================================================================== shared computations
BLOCKS_SEEDS = {2048: 939, 256: 938, 100: 91}
F97 = dict(n=2048, sigma=1.0)
F98 = dict(n=256, sigma=3.0)
J0 = 5


def blocks_analysis(n, sigma, j0=J0):
    """Data, the symmlet-8 VisuShrink fit and the CV local linear fit for the blocks function."""
    x, y = simulate(blocks, n, sigma, BLOCKS_SEEDS[n])
    h8 = wavelet_filter("sym8")
    fw, info = wavelet_smooth(y, h8, j0, "soft")
    hs = log_grid(1.2 / n, 0.15, 40)
    hb, fl, sc = ll_cv(x, y, hs)
    r = blocks(x)
    return dict(x=x, y=y, r=r, fw=fw, info=info, h=hb, fl=fl,
                mse_w=float(np.mean((fw - r) ** 2)), mse_l=float(np.mean((fl - r) ** 2)))


def haar_projection_doppler(J):
    """f_J = alpha phi + sum_{j<J} sum_k beta_jk psi_jk: for Haar this is the average of f over each
    dyadic interval of length 2^-J (V_J = piecewise constants), computed by quadrature."""
    edges = np.arange(2 ** J + 1) / 2 ** J
    return edges, np.array([integrate.quad(doppler, a, b, limit=200)[0] * 2 ** J for a, b in zip(edges[:-1], edges[1:])])


def blocks_haar_exact(j):
    """Exact Haar coefficients of blocks at level j: alpha_jk and beta_jk (psi = -1 then +1)."""
    k = np.arange(2 ** j)
    a, m, b = k / 2 ** j, (k + 0.5) / 2 ** j, (k + 1) / 2 ** j
    F = blocks_antideriv
    alpha = 2 ** (j / 2) * (F(b) - F(a))
    beta = 2 ** (j / 2) * ((F(b) - F(m)) - (F(m) - F(a)))
    return alpha, beta


def _clean(ax):
    ax.spines[["top", "right"]].set_visible(False)


# =========================================================================== figures
def fig_9_1(out=None):
    """Blocks, 100 data points, and local linear fits with a small and a large bandwidth."""
    n = 100
    x, y = simulate(blocks, n, 1.0, BLOCKS_SEEDS[100])
    xg = np.linspace(0, 1, 2001)
    fig, ax = panel_grid(2, 2, (3.4, 2.5))
    ax[0, 0].plot(xg, blocks(xg), color="k", lw=1.2)
    ax[0, 1].plot(x, y, ".", color=GREY, ms=4)
    for a, h, lab in [(ax[1, 0], 0.02, "h = 0.02"), (ax[1, 1], 0.12, "h = 0.12")]:
        F, _, _ = ll_fit(x, y, h)
        a.plot(x, y, ".", color=GREY, ms=3, alpha=0.6)
        a.plot(x, F, color=BLUE, lw=1.3)
        a.set_title("local linear, " + lab)
    for a in ax.ravel():
        a.set_ylim(-12, 24); _clean(a)
    ax[0, 0].set_title("blocks function r(x)"); ax[0, 1].set_title("n = 100, $\\sigma$ = 1")
    fig.tight_layout()
    savefig(fig, CH, "fig9-1", out)


def fig_9_2(out=None):
    """The Haar mother wavelet psi and psi_{2,2}."""
    x = np.linspace(0, 1, 4001)
    psi = lambda t: np.where((t >= 0) & (t <= 0.5), -1.0, np.where((t > 0.5) & (t <= 1), 1.0, 0.0))
    fig, ax = panel_grid(1, 2, (3.4, 2.5))
    ax[0, 0].plot(x, psi(x), color="k", lw=1.3); ax[0, 0].set_title("$\\psi(x)$")
    ax[0, 1].plot(x, 2 * psi(4 * x - 2), color="k", lw=1.3); ax[0, 1].set_title("$\\psi_{2,2}(x)=2\\,\\psi(4x-2)$")
    for a in ax.ravel():
        a.set_ylim(-2.3, 2.3); a.axhline(0, color=GREY, lw=0.5); _clean(a)
    fig.tight_layout()
    savefig(fig, CH, "fig9-2", out)


def fig_9_3(out=None):
    """The Doppler function and its Haar approximations f_J, J = 3, 5, 8."""
    xg = np.linspace(0, 1, 4001)
    fig, ax = panel_grid(2, 2, (3.4, 2.5))
    ax[0, 0].plot(xg, doppler(xg), color="k", lw=1.0); ax[0, 0].set_title("Doppler")
    for a, J in zip([ax[0, 1], ax[1, 0], ax[1, 1]], [3, 5, 8]):
        e, v = haar_projection_doppler(J)
        a.plot(xg, doppler(xg), color=GREY, lw=0.6)
        a.step(e, np.append(v, v[-1]), where="post", color=BLUE, lw=1.1)
        a.set_title("$f_J$, J = %d (%d terms)" % (J, 2 ** J))
    for a in ax.ravel():
        a.set_ylim(-0.6, 0.6); _clean(a)
    fig.tight_layout()
    savefig(fig, CH, "fig9-3", out)


def fig_9_4(out=None):
    """Blocks and its Haar coefficients: father at level 4, mothers at levels 4, 5, 6."""
    xg = np.linspace(0, 1, 4001)
    fig, ax = plt.subplots(5, 1, figsize=(6.2, 7.2), gridspec_kw=dict(height_ratios=[1.3, 1, 1, 1, 1]))
    ax[0].plot(xg, blocks(xg), color="k", lw=1.2); ax[0].set_ylabel("f(x)")
    j0 = 4
    alpha, _ = blocks_haar_exact(j0)
    rows = [("father coefficients $\\alpha_{4k}$ (16)", alpha, j0)]
    for j in (4, 5, 6):
        rows.append(("mother coefficients $\\beta_{%dk}$ (%d)" % (j, 2 ** j), blocks_haar_exact(j)[1], j))
    for a, (lab, c, j) in zip(ax[1:], rows):
        pos = (np.arange(len(c)) + 0.5) / len(c)
        a.vlines(pos, 0, c, color=BLUE if "father" in lab else RED, lw=1.4)
        a.axhline(0, color=GREY, lw=0.6)
        a.set_title(lab, fontsize=9.5)
        a.set_xlim(0, 1)
    for a in ax:
        _clean(a)
    fig.tight_layout()
    savefig(fig, CH, "fig9-4", out)


def fig_9_5(out=None):
    """The symmlet 8 mother wavelet (cascade algorithm)."""
    h = wavelet_filter("sym8")
    x, psi = cascade(h, 10, mother=True)
    fig, ax = plt.subplots(figsize=(5.4, 2.8))
    ax.plot(x - 7, psi, color="k", lw=1.1)
    ax.axhline(0, color=GREY, lw=0.5)
    ax.set_xlim(-7, 8); ax.set_xlabel("x"); ax.set_title("symmlet 8 mother wavelet $\\psi$, support $[-7, 8]$")
    _clean(ax)
    fig.tight_layout()
    savefig(fig, CH, "fig9-5", out)


def fig_9_6(out=None):
    """Hard and soft thresholding rules."""
    d = np.linspace(-3, 3, 1201)
    lam = 1.0
    fig, ax = panel_grid(1, 2, (3.2, 3.0))
    for a, f, t in [(ax[0, 0], hard, "Hard thresholding"), (ax[0, 1], soft, "Soft thresholding")]:
        v = f(d, lam)
        if f is hard:
            for s in (d < -lam, (d >= -lam) & (d < lam), d >= lam):
                a.plot(d[s], v[s], color="k", lw=1.5)
        else:
            a.plot(d, v, color="k", lw=1.5)
        a.plot(d, d, ":", color=GREY, lw=0.8)
        a.axhline(0, color=GREY, lw=0.5); a.axvline(0, color=GREY, lw=0.5)
        a.set_xticks([-lam, lam]); a.set_xticklabels(["$-\\lambda$", "$\\lambda$"])
        a.set_yticks([]); a.set_xlabel("D"); a.set_ylabel("$\\hat\\beta(D)$"); a.set_title(t)
        _clean(a)
    fig.tight_layout()
    savefig(fig, CH, "fig9-6", out)


def _fig_blocks_pair(res, name, out):
    xg = np.linspace(0, 1, 2001)
    fig, ax = panel_grid(2, 2, (3.4, 2.5))
    ax[0, 0].plot(xg, blocks(xg), color="k", lw=1.1); ax[0, 0].set_title("r(x)")
    ax[0, 1].plot(res["x"], res["y"], ".", color=GREY, ms=1.6 if len(res["x"]) > 1000 else 3)
    ax[0, 1].set_title("n = %d, $\\sigma$ = %g" % (len(res["x"]), res["sigma"]))
    ax[1, 0].plot(res["x"], res["fw"], color=BLUE, lw=0.9)
    ax[1, 0].set_title("wavelets (symmlet 8, universal soft)\naverage squared error %.3f" % res["mse_w"], fontsize=9)
    ax[1, 1].plot(res["x"], res["fl"], color=RED, lw=0.9)
    ax[1, 1].set_title("local linear, CV h = %.4f\naverage squared error %.3f" % (res["h"], res["mse_l"]), fontsize=9)
    for a in ax.ravel():
        a.set_ylim(-12, 25); _clean(a)
    fig.tight_layout()
    savefig(fig, CH, name, out)


def fig_9_7(out=None):
    """Blocks, n = 2048, sigma = 1: wavelet (symmlet 8, universal soft) against CV local linear."""
    res = blocks_analysis(**F97); res["sigma"] = 1.0
    _fig_blocks_pair(res, "fig9-7", out)
    print("  Fig 9.7: sigma-hat %.4f, kept %d, mse wavelet %.4f, local linear %.4f (h = %.5f)"
          % (res["info"]["sigma"], res["info"]["kept"], res["mse_w"], res["mse_l"], res["h"]))


def fig_9_8(out=None):
    """Blocks, n = 256, sigma = 3."""
    res = blocks_analysis(**F98); res["sigma"] = 3.0
    _fig_blocks_pair(res, "fig9-8", out)
    print("  Fig 9.8: sigma-hat %.4f, kept %d, mse wavelet %.4f, local linear %.4f (h = %.5f)"
          % (res["info"]["sigma"], res["info"]["kept"], res["mse_w"], res["mse_l"], res["h"]))


ICI_X0 = 0.60


def ici_point(x0_index=None):
    """The quantities of Figure 9.9 at one design point: fits r_j, s_j, means rbar_j, bias b_j, j*, j+."""
    x, y, fits, sds, jp, est, s = ici_analysis()
    i = int(round(ICI_X0 * ICI_N)) - 1 if x0_index is None else x0_index
    kappa = np.sqrt(2 * np.log(ICI_N))
    rx = doppler(x)
    means = np.array([nw_weights(x, h)[i] @ rx for h in ICI_H])
    b = np.abs(means - doppler(x[i]))
    rho = kappa * sds[:, i]
    jstar = int(np.max(np.where(b <= rho)[0]))
    return dict(i=i, x0=x[i], r=fits[:, i], s=sds[:, i], rho=rho, b=b, jstar=jstar, jplus=int(jp[i]),
                est=float(est[i]), truth=float(doppler(x[i])))


def fig_9_9(out=None):
    """ICI at one point (computed): the intervals D_j for increasing bandwidths, j* and j+."""
    P = ici_point()
    j = np.arange(len(ICI_H))
    fig, ax = plt.subplots(figsize=(6.4, 3.4))
    for k in j:
        col = BLUE if k <= P["jplus"] else GREY
        ax.plot([k, k], [P["r"][k] - 2 * P["rho"][k], P["r"][k] + 2 * P["rho"][k]], color=col, lw=1.3)
        ax.plot(k, P["r"][k], "o", color=col, ms=2.5)
    ax.axhline(P["truth"], color=RED, lw=1, ls="--", label="r(x)")
    ax.axvline(P["jstar"], color=GREEN, lw=1, ls=":", label="j* (oracle)")
    ax.axvline(P["jplus"], color=ORANGE, lw=1, ls="-.", label="j+ (ICI)")
    ax.set_xlabel("bandwidth index j (h from 1/n to 1, log spaced)")
    ax.set_title("ICI intervals $D_j=[\\hat r_j\\pm2\\rho_j]$ at x = %.3f (Doppler, n = 1024, $\\sigma$ = 0.1)" % P["x0"], fontsize=9.5)
    ax.set_ylim(P["truth"] - 1.2, P["truth"] + 1.2)
    ax.legend(fontsize=8, loc="lower left")
    _clean(ax)
    fig.tight_layout()
    savefig(fig, CH, "fig9-9", out)
    print("  Fig 9.9: x0 %.4f, j* %d, j+ %d, |est - r| %.4f, 6 rho_j* %.4f"
          % (P["x0"], P["jstar"], P["jplus"], abs(P["est"] - P["truth"]), 6 * P["rho"][P["jstar"]]))


# =========================================================================== supplementary figures
def fig_9_S1(out=None):
    """The Daubechies family: scaling functions and mother wavelets."""
    names = [("Haar (N = 1)", daubechies_filter(1)), ("Daubechies N = 2", daubechies_filter(2)),
             ("Daubechies N = 4", daubechies_filter(4)), ("symmlet N = 8", daubechies_filter(8, "symmlet"))]
    fig, ax = panel_grid(2, 4, (2.4, 2.0))
    for c, (lab, h) in enumerate(names):
        for r, mother in enumerate((False, True)):
            x, v = cascade(h, 9, mother)
            a = ax[r, c]
            if len(h) == 2:
                a.step(x, v, where="post", color=BLUE if not mother else RED, lw=1.1)
            else:
                a.plot(x, v, color=BLUE if not mother else RED, lw=1.0)
            a.axhline(0, color=GREY, lw=0.4)
            a.set_title(("$\\phi$, " if not mother else "$\\psi$, ") + lab, fontsize=8.5)
            _clean(a)
    fig.tight_layout()
    savefig(fig, CH, "fig9-S1", out)


def fig_9_S2(out=None):
    """Exact risk of soft and hard thresholding (Exercise 8) and the oracle bound (9.37)."""
    n = 1024
    lam = np.sqrt(2 * np.log(n))
    th = np.linspace(0, 8, 401)
    rng = np.random.default_rng(98)
    thm = np.linspace(0, 8, 17)
    Z = rng.standard_normal((40000, 1))
    mc_s = np.mean((soft(thm + Z, lam) - thm) ** 2, 0)
    mc_h = np.mean((hard(thm + Z, lam) - thm) ** 2, 0)
    fig, ax = panel_grid(1, 2, (3.6, 2.9))
    a = ax[0, 0]
    a.plot(th, soft_risk(th, lam), color=BLUE, label="soft (exact)")
    a.plot(th, hard_risk(th, lam), color=RED, label="hard (exact)")
    a.plot(thm, mc_s, "o", color=BLUE, ms=3, mfc="none"); a.plot(thm, mc_h, "s", color=RED, ms=3, mfc="none")
    a.plot(th, (2 * np.log(n) + 1) * (1 / n + np.minimum(th ** 2, 1)), color=GREY, ls="--", label="$(2\\log n+1)(1/n+\\min(\\theta^2,1))$")
    a.plot(th, np.minimum(th ** 2, 1), color="k", lw=0.8, ls=":", label="oracle $\\min(\\theta^2,1)$")
    a.set_ylim(0, 16); a.set_xlabel("$\\theta$ (noise sd 1)"); a.set_title("$\\lambda=\\sqrt{2\\log n}$, n = 1024", fontsize=9)
    a.legend(fontsize=7)
    _clean(a)
    a = ax[0, 1]
    ns = 2 ** np.arange(4, 21)
    p_all = (1 - 2 * norm.sf(np.sqrt(2 * np.log(ns)))) ** (ns - 1)
    a.semilogx(ns, p_all, "o-", color=BLUE, ms=3, label="P(all n-1 coefficients killed)")
    a.semilogx(ns, 1 - np.sqrt(2 / np.pi) / np.sqrt(2 * np.log(ns)), "--", color=GREY, label="Mills lower bound")
    a.set_ylim(0, 1); a.set_xlabel("n"); a.set_title("Theorem 9.33 for pure noise", fontsize=9)
    a.legend(fontsize=7, loc="lower right")
    _clean(a)
    fig.tight_layout()
    savefig(fig, CH, "fig9-S2", out)


def nterm_errors(f, n=2048, ks=None):
    """Relative squared n-term approximation errors of the samples f(i/n) in three bases: keep the
    first k (linear) or the k largest (nonlinear) coefficients."""
    x = design(n)
    v = f(x)
    tot = np.sum(v ** 2)
    out = {}
    bases = {"Haar": np.concatenate(dwt(v, wavelet_filter("haar"), 0)),
             "symmlet 8": np.concatenate(dwt(v, wavelet_filter("sym8"), 3)),
             "cosine": dct(v, norm="ortho")}
    for name, c in bases.items():
        lin = tot - np.concatenate([[0], np.cumsum(c ** 2)])
        nl = tot - np.concatenate([[0], np.cumsum(np.sort(c ** 2)[::-1])])
        out[name] = (np.maximum(lin, 1e-300) / tot, np.maximum(nl, 1e-300) / tot)
    return out


def fig_9_S3(out=None):
    """Sparsity: n-term approximation errors, linear (first k) against nonlinear (largest k)."""
    fig, ax = panel_grid(1, 2, (3.6, 3.0))
    cols = {"Haar": RED, "symmlet 8": BLUE, "cosine": GREEN}
    k = np.arange(2049)
    for a, (f, t) in zip(ax[0], [(blocks, "blocks"), (doppler, "Doppler")]):
        E = nterm_errors(f)
        for name, (lin, nl) in E.items():
            a.loglog(k[1:400], nl[1:400], color=cols[name], label=name + ", largest k")
            a.loglog(k[1:400], lin[1:400], color=cols[name], ls=":", label=name + ", first k")
        a.set_ylim(1e-8, 1.2); a.set_xlabel("number of terms k"); a.set_title(t + ": relative error", fontsize=9)
        _clean(a)
    ax[0, 0].legend(fontsize=6.5, loc="lower left")
    fig.tight_layout()
    savefig(fig, CH, "fig9-S3", out)


EX5_SIGMAS = (0.01, 0.1, 1.0)
EX5_REPS = 10


def exercise5(reps=EX5_REPS):
    """Average squared errors for Doppler, n = 1024: wavelets (James-Stein per level, VisuShrink,
    SureShrink), REACT (cosine) and CV local linear; Gaussian and contaminated noise. Cached."""
    path = os.path.join(CACHE_DIR, "ch09_ex5.json")
    if os.path.exists(path):
        with open(path) as f:
            return json.load(f)
    n = 1024
    x = design(n)
    r = doppler(x)
    h8 = wavelet_filter("sym8")
    cols, keys = [], []
    for cont in (False, True):
        for s in EX5_SIGMAS:
            for rep in range(reps):
                _, y = simulate(doppler, n, s, 5000 + 100 * rep + int(1000 * s) + (7 if cont else 0), cont)
                cols.append(y); keys.append((cont, s))
    Y = np.array(cols).T
    per = []
    for col in range(Y.shape[1]):
        y = Y[:, col]
        e = {}
        for m in ("js", "soft", "sure"):
            e[m] = float(np.mean((wavelet_smooth(y, h8, J0, m)[0] - r) ** 2))
        sig = mad_sigma(dwt(y, h8, J0)[-1])
        e["react"] = float(np.mean((react_cosine(y, sig)[0] - r) ** 2))
        per.append(e)
    LL, hb = ll_cv_many(x, Y, log_grid(1.5 / n, 0.3, 30))
    for col in range(Y.shape[1]):
        per[col]["loclin"] = float(np.mean((LL[:, col] - r) ** 2))
    res = {}
    for col, key in enumerate(keys):
        res.setdefault("%s, sigma=%g" % ("contaminated" if key[0] else "Gaussian", key[1]), []).append(per[col])
    table = {}
    for key, lst in res.items():
        table[key] = {m: float(np.mean([d[m] for d in lst])) for m in lst[0]}
    os.makedirs(CACHE_DIR, exist_ok=True)
    with open(path, "w") as f:
        json.dump(table, f, indent=1)
    return table


def fig_9_S4(out=None):
    """Exercise 5: one Doppler sample (sigma = 0.1) fitted five ways."""
    n = 1024
    x, y = simulate(doppler, n, 0.1, 5100)
    h8 = wavelet_filter("sym8")
    fits = [("SureShrink", wavelet_smooth(y, h8, J0, "sure")[0]),
            ("VisuShrink", wavelet_smooth(y, h8, J0, "soft")[0]),
            ("James-Stein per level", wavelet_smooth(y, h8, J0, "js")[0]),
            ("REACT (cosine)", react_cosine(y, mad_sigma(dwt(y, h8, J0)[-1]))[0]),
            ("local linear, CV", ll_cv(x, y, log_grid(1.5 / n, 0.3, 30))[1])]
    fig, ax = panel_grid(2, 3, (3.0, 2.3))
    ax[0, 0].plot(x, y, ".", color=GREY, ms=1); ax[0, 0].plot(x, doppler(x), color="k", lw=0.8)
    ax[0, 0].set_title("data, $\\sigma$ = 0.1", fontsize=9)
    for a, (lab, f) in zip(ax.ravel()[1:], fits):
        a.plot(x, doppler(x), color=GREY, lw=0.6)
        a.plot(x, f, color=BLUE, lw=0.8)
        a.set_title("%s: %.5f" % (lab, np.mean((f - doppler(x)) ** 2)), fontsize=8.5)
    for a in ax.ravel():
        a.set_ylim(-0.7, 0.7); _clean(a)
    fig.tight_layout()
    savefig(fig, CH, "fig9-S4", out)
    T = exercise5()
    for k, v in T.items():
        print("  Ex5", k, {m: "%.2e" % e for m, e in v.items()})


def geyser_u():
    g = geyser()
    return (g - GEY_A) / (GEY_B - GEY_A)


def fig_9_S5(out=None):
    """Exercise 6: Haar wavelet histograms of the geyser durations."""
    u = geyser_u()
    n = len(u)
    J = int(np.floor(np.log2(n + 1)))
    xs = np.linspace(0, 1, 4000, endpoint=False)
    scale = GEY_B - GEY_A
    m = hist_cv(u)
    fig, ax = panel_grid(1, 2, (3.7, 2.9))
    a = ax[0, 0]
    a.hist(u * scale + GEY_A, bins=m, range=(GEY_A, GEY_B), density=True, color="#dbe6f5", ec=BLUE, lw=0.5, label="CV histogram (%d bins)" % m)
    co, ws = haar_density(u, J, "sure")
    a.plot(xs * scale + GEY_A, haar_eval(xs, co, ws) / scale, color=RED, lw=1.1, label="SURE wavelet histogram")
    a.set_xlabel("eruption duration (minutes)"); a.legend(fontsize=7); a.set_title("SURE shrinkage per level, J = %d" % J, fontsize=9)
    _clean(a)
    a = ax[0, 1]
    for alpha, col in [(0.01, BLUE), (0.05, RED), (0.2, GREEN)]:
        co, ws = haar_density(u, J, "test", alpha)
        a.plot(xs * scale + GEY_A, haar_eval(xs, co, ws) / scale, color=col, lw=1.0, label="$\\alpha$ = %g (%d kept)" % (alpha, int(sum(w.sum() for w in ws))))
    a.set_xlabel("eruption duration (minutes)"); a.legend(fontsize=7); a.set_title("hard threshold by testing", fontsize=9)
    _clean(a)
    fig.tight_layout()
    savefig(fig, CH, "fig9-S5", out)


def fig_9_S6(out=None):
    """ICI and Lepski bandwidths along x for Doppler data (Exercise 9)."""
    x, y, fits, sds, jp_t, est_t, s = ici_analysis()
    r = doppler(x)
    jp, est = ici(fits, sds, ICI_GAMMA)
    _, est_hat = ici(*nw_gauss_all(x, ICI_H, y, sigma_rice(y)), ICI_GAMMA)
    jl, estl = lepski(fits, sds, ICI_GAMMA)
    fixed = np.mean((fits - r[None, :]) ** 2, axis=1)
    jb = int(np.argmin(fixed))
    fig, ax = panel_grid(1, 2, (3.7, 2.9))
    a = ax[0, 0]
    a.plot(x, y, ".", color=GREY, ms=1)
    a.plot(x, est, color=BLUE, lw=0.9, label="ICI ($\\Gamma$ = 1): %.5f" % np.mean((est - r) ** 2))
    a.plot(x, est_t, color=ORANGE, lw=0.8, label="ICI (theory $\\Gamma$): %.5f" % np.mean((est_t - r) ** 2))
    a.plot(x, fits[jb], color=RED, lw=0.8, ls="--", label="best fixed h: %.5f" % fixed[jb])
    a.set_ylim(-0.7, 0.7); a.legend(fontsize=7, loc="lower right"); a.set_title("fits and average squared errors", fontsize=9)
    _clean(a)
    a = ax[0, 1]
    a.semilogy(x, ICI_H[jp], color=BLUE, lw=0.8, label="ICI")
    a.semilogy(x, ICI_H[jl], color=GREEN, lw=0.8, alpha=0.8, label="Lepski")
    a.axhline(ICI_H[jb], color=RED, ls="--", lw=0.8, label="best fixed h")
    a.set_xlabel("x"); a.set_ylabel("chosen bandwidth"); a.legend(fontsize=7); a.set_title("local bandwidth h(x)", fontsize=9)
    _clean(a)
    fig.tight_layout()
    savefig(fig, CH, "fig9-S6", out)
    print("  ICI theory %.6f; ICI mse %.6f (sigma estimated: %.6f), Lepski %.6f, best fixed %.6f at h=%.4f"
          % (np.mean((est_t - r) ** 2), np.mean((est - r) ** 2), np.mean((est_hat - r) ** 2), np.mean((estl - r) ** 2), fixed[jb], ICI_H[jb]))


BP_SIGMA, BP_SEED = 0.5, 98


def bp_analysis():
    x, smooth, sp = spikes_signal()
    r = smooth + sp
    rng = np.random.default_rng(BP_SEED)
    y = r + BP_SIGMA * rng.standard_normal(len(x))
    n = len(x)
    lam = 2 * BP_SIGMA * np.sqrt(2 * np.log(2 * n))
    a, b, obj = basis_pursuit(y, lam)
    fit_bp = idct(a, norm="ortho") + b
    lu = BP_SIGMA * np.sqrt(2 * np.log(n))
    fit_cos = idct(soft(dct(y, norm="ortho"), lu), norm="ortho")
    fit_sp = soft(y, lu)
    return dict(x=x, y=y, r=r, smooth=smooth, sp=sp, a=a, b=b, obj=obj, lam=lam,
                fits={"cosine only": fit_cos, "spikes only": fit_sp, "basis pursuit": fit_bp})


def fig_9_S7(out=None):
    """Basis pursuit with the cosine + spike dictionary (Section 9.8)."""
    B = bp_analysis()
    fig, ax = panel_grid(2, 2, (3.4, 2.4))
    ax[0, 0].plot(B["x"], B["y"], ".", color=GREY, ms=1.5); ax[0, 0].plot(B["x"], B["r"], color="k", lw=0.8)
    ax[0, 0].set_title("smooth + spikes, n = 512, $\\sigma$ = 0.5", fontsize=9)
    for a, (lab, f) in zip([ax[0, 1], ax[1, 0], ax[1, 1]], B["fits"].items()):
        a.plot(B["x"], B["r"], color=GREY, lw=0.6)
        a.plot(B["x"], f, color=BLUE if lab == "basis pursuit" else RED, lw=0.8)
        a.set_title("%s: %.4f" % (lab, np.mean((f - B["r"]) ** 2)), fontsize=9)
    for a in ax.ravel():
        a.set_ylim(-5, 7); _clean(a)
    fig.tight_layout()
    savefig(fig, CH, "fig9-S7", out)


RATE_NS = (256, 512, 1024, 2048, 4096)


def rates_experiment(reps=8):
    """Average squared error against n for blocks (sigma = 1): Haar and symmlet VisuShrink and
    SureShrink, and local linear regression with the best fixed bandwidth (an oracle). Cached."""
    path = os.path.join(CACHE_DIR, "ch09_rates.json")
    if os.path.exists(path):
        with open(path) as f:
            return json.load(f)
    out = {"n": list(RATE_NS), "haar": [], "sym8": [], "sym8_sure": [], "loclin": []}
    for n in RATE_NS:
        x = design(n)
        r = blocks(x)
        Y = np.array([simulate(blocks, n, 1.0, 70000 + 31 * n + k)[1] for k in range(reps)]).T
        out["haar"].append(float(np.mean([np.mean((wavelet_smooth(Y[:, k], wavelet_filter("haar"), 0, "soft")[0] - r) ** 2) for k in range(reps)])))
        out["sym8"].append(float(np.mean([np.mean((wavelet_smooth(Y[:, k], wavelet_filter("sym8"), J0, "soft")[0] - r) ** 2) for k in range(reps)])))
        out["sym8_sure"].append(float(np.mean([np.mean((wavelet_smooth(Y[:, k], wavelet_filter("sym8"), J0, "sure")[0] - r) ** 2) for k in range(reps)])))
        best = np.inf
        for h in log_grid(1.2 / n, 0.08, 24):
            F, _, ok = ll_fit(x, Y, h)
            if ok:
                best = min(best, float(np.mean((F - r[:, None]) ** 2)))
        out["loclin"].append(best)
    os.makedirs(CACHE_DIR, exist_ok=True)
    with open(path, "w") as f:
        json.dump(out, f, indent=1)
    return out


def fig_9_S8(out=None):
    """Risk against n for blocks: wavelets against the best fixed-bandwidth local linear fit."""
    R = rates_experiment()
    n = np.array(R["n"], dtype=float)
    fig, ax = plt.subplots(figsize=(5.2, 3.4))
    for k, lab, col in [("haar", "Haar, universal soft", RED), ("sym8", "symmlet 8, universal soft", BLUE),
                        ("sym8_sure", "symmlet 8, SureShrink", PURPLE), ("loclin", "local linear, best fixed h", GREEN)]:
        ax.loglog(n, R[k], "o-", color=col, ms=3.5, label=lab)
    ax.loglog(n, R["loclin"][0] * (n / n[0]) ** -0.5, ":", color=GREEN, lw=0.8, label="slope $-1/2$")
    ax.loglog(n, R["haar"][0] * (np.log(n) / n) / (np.log(n[0]) / n[0]), ":", color=RED, lw=0.8, label="$\\propto \\log n / n$")
    ax.set_xlabel("n"); ax.set_ylabel("average squared error"); ax.set_title("blocks, $\\sigma$ = 1", fontsize=9.5)
    ax.legend(fontsize=7)
    _clean(ax)
    fig.tight_layout()
    savefig(fig, CH, "fig9-S8", out)
    print("  rates", R)


# =========================================================================== demo data
def _r(v, d=6):
    return [float(round(float(t), d)) for t in v]


def export_json():
    os.makedirs(DATA_OUT, exist_ok=True)
    W = {"filters": {k: _r(wavelet_filter(k), 12) for k in ("haar", "d4", "d8", "sym8")},
         "blocks2048": _r(simulate(blocks, 2048, 1.0, BLOCKS_SEEDS[2048])[1]),
         "blocks256": _r(simulate(blocks, 256, 3.0, BLOCKS_SEEDS[256])[1]),
         "doppler1024": _r(simulate(doppler, 1024, 0.1, 5100)[1]),
         "j0": J0}
    with open(os.path.join(DATA_OUT, "ch09-wavelets.json"), "w") as f:
        json.dump(W, f, separators=(",", ":"))
    x, y = ici_data()
    with open(os.path.join(DATA_OUT, "ch09-ici.json"), "w") as f:
        json.dump({"y": _r(y), "sigma": ICI_SIGMA, "h": _r(ICI_H, 10)}, f, separators=(",", ":"))
    print("wrote ../data/ch09-wavelets.json, ../data/ch09-ici.json")


def _with_export(fun):
    def wrapped(out_dir=None):
        fun(out_dir)
        export_json()
    wrapped.__doc__ = fun.__doc__
    return wrapped


FIGURES = {
    "9.1": fig_9_1, "9.2": fig_9_2, "9.3": fig_9_3, "9.4": fig_9_4, "9.5": fig_9_5, "9.6": fig_9_6,
    "9.7": fig_9_7, "9.8": fig_9_8, "9.9": fig_9_9,
    "9.S1": fig_9_S1, "9.S2": fig_9_S2, "9.S3": fig_9_S3, "9.S4": fig_9_S4, "9.S5": fig_9_S5,
    "9.S6": fig_9_S6, "9.S7": fig_9_S7, "9.S8": _with_export(fig_9_S8),
}

if __name__ == "__main__":
    common.run(FIGURES, CH)
