"""Chapter 7 (Linear Algebra) of Murphy (2022), Probabilistic Machine Learning: An Introduction.

Reproduces the figures of the chapter that are computed from data, a model or a simulation:

  7.6   level set of a quadratic form and of a Gaussian, with the eigenvectors as axes
  7.7   raw, standardised, PCA-whitened and ZCA-whitened height and weight data
        (stand-in data: the 88 men of the Davis (1990) height and weight study, R package carData)
  7.9   low-rank approximations of a 200 x 320 greyscale image by the truncated SVD
        (stand-in image: the 'china' photograph bundled with scikit-learn)
  7.10  the first 100 singular values of the image and of the same pixels shuffled at random
  7.12  one, two and three linear equations in two unknowns: least-norm, unique and least-squares solutions
  7.S1  supplementary: convergence of the power method and of its Rayleigh quotient
  7.S2  supplementary: accuracy of the Hutchinson trace estimator, Gaussian and Rademacher probes
  7.S3  supplementary: forward and central finite differences, truncation against rounding error
  7.S4  supplementary: least squares by the normal equations, by QR and by the SVD, against the condition number

Skipped figures, with the reason:
  7.1   vector, matrix and tensor drawn as coloured boxes: a schematic, nothing computed;
  7.2   row-major against column-major order: a schematic;
  7.3   vector addition and two bases of the plane: hand-drawn diagrams;
  7.4   the range and null space of a matrix: a schematic;
  7.5   how the entries of a matrix product are formed: a schematic;
  7.8   the shapes of the factors in the full and economy SVD: a schematic;
  7.11  the shapes of the factors in the full and economy QR decomposition: a schematic.

Besides the figures this module holds the small linear-algebra routines the notes describe, written out
so that the arithmetic is visible (Gram-Schmidt QR, LU with partial pivoting, Cholesky, forward and back
substitution, the power method with deflation, the Hutchinson estimator, PCA and ZCA whitening, the
pseudo-inverse from the SVD, the centring matrix and the double-centring trick, squared distances), and it
exports small data for the browser demonstrations to ../data/ch07-*.json.

Run:  python ch07_linear_algebra.py [--fig 7.6 7.9 ...]
"""
import base64
import json
import os
import shutil
import subprocess
import sys

import numpy as np

sys.path.insert(0, os.path.dirname(os.path.abspath(__file__)))
import common  # noqa: E402
from common import RED, BLUE, GREEN, ORANGE, GREY, PURPLE, savefig, panel_label, plt  # noqa: E402

CH = 7
DATA_OUT = os.path.normpath(os.path.join(common.HERE, "..", "data"))
CACHE_DIR = os.path.join(common.HERE, "cache")
IMG_H, IMG_W = 200, 320


# ================================================================== seeded generator shared with the demos
def mulberry32(seed):
    """The uniform generator of the browser demonstrations (demo-kit.js, DK.rng(seed).u), in Python,
    so that a 'random' shuffle in a demonstration and in a figure is the same shuffle."""
    a = seed & 0xFFFFFFFF

    def imul(x, y):
        return (x * y) & 0xFFFFFFFF

    def u():
        nonlocal a
        a = (a + 0x6D2B79F5) & 0xFFFFFFFF
        t = imul(a ^ (a >> 15), 1 | a)
        t = ((t + imul(t ^ (t >> 7), 61 | t)) & 0xFFFFFFFF) ^ t
        return ((t ^ (t >> 14)) & 0xFFFFFFFF) / 4294967296.0
    return u


def js_shuffle(n, seed):
    """Fisher-Yates permutation of range(n) drawn exactly as ML.shuffle(DK.rng(seed), a) does."""
    u = mulberry32(seed)
    a = list(range(n))
    for i in range(n - 1, 0, -1):
        j = int(np.floor(u() * (i + 1)))
        a[i], a[j] = a[j], a[i]
    return np.array(a)


# ================================================================== triangular solves and factorisations
def forward_sub(L, b):
    """Solve L y = b for lower-triangular L, one unknown at a time (7.219), (7.220)."""
    L, b = np.asarray(L, float), np.asarray(b, float)
    n = len(b)
    y = np.zeros(n)
    for i in range(n):
        y[i] = (b[i] - L[i, :i] @ y[:i]) / L[i, i]
    return y


def back_sub(U, y):
    """Solve U x = y for upper-triangular U, from the last unknown upwards."""
    U, y = np.asarray(U, float), np.asarray(y, float)
    n = len(y)
    x = np.zeros(n)
    for i in range(n - 1, -1, -1):
        x[i] = (y[i] - U[i, i + 1:] @ x[i + 1:]) / U[i, i]
    return x


def lu_partial_pivot(A):
    """Gaussian elimination with partial pivoting: P A = L U (7.203), L unit lower triangular."""
    A = np.array(A, float)
    n = A.shape[0]
    perm = np.arange(n)
    L = np.eye(n)
    U = A.copy()
    for k in range(n - 1):
        p = k + int(np.argmax(np.abs(U[k:, k])))        # the largest pivot in column k
        if p != k:
            U[[k, p], k:] = U[[p, k], k:]
            L[[k, p], :k] = L[[p, k], :k]
            perm[[k, p]] = perm[[p, k]]
        if U[k, k] == 0:
            continue                                     # a zero column below the diagonal: nothing to eliminate
        m = U[k + 1:, k] / U[k, k]
        L[k + 1:, k] = m
        U[k + 1:, k:] -= np.outer(m, U[k, k:])
        U[k + 1:, k] = 0.0
    P = np.eye(n)[perm]
    return P, L, U


def lu_solve(A, b):
    """Solve a square system with P A = L U, then L y = P b and U x = y (7.215)-(7.218)."""
    P, L, U = lu_partial_pivot(A)
    return back_sub(U, forward_sub(L, P @ np.asarray(b, float)))


def gram_schmidt_qr(A):
    """Reduced QR factorisation A = Q R by modified Gram-Schmidt (7.204)-(7.208).

    Column j of A is stripped of its components along q_1, ..., q_{j-1}; what is left, normalised, is q_j.
    Requires linearly independent columns."""
    A = np.array(A, float)
    m, n = A.shape
    Q = A.copy()
    R = np.zeros((n, n))
    for j in range(n):
        for i in range(j):
            R[i, j] = Q[:, i] @ Q[:, j]
            Q[:, j] -= R[i, j] * Q[:, i]
        R[j, j] = np.linalg.norm(Q[:, j])
        Q[:, j] /= R[j, j]
    return Q, R


def cholesky(A):
    """Lower-triangular L with A = L L^T for symmetric positive definite A (Section 7.6.3), column by column."""
    A = np.array(A, float)
    n = A.shape[0]
    L = np.zeros_like(A)
    for j in range(n):
        d = A[j, j] - L[j, :j] @ L[j, :j]
        if d <= 0:
            raise np.linalg.LinAlgError("matrix is not positive definite")
        L[j, j] = np.sqrt(d)
        L[j + 1:, j] = (A[j + 1:, j] - L[j + 1:, :j] @ L[j, :j]) / L[j, j]
    return L


def logdet_chol(A):
    """log det A = 2 sum_i log L_ii (7.45)."""
    return 2.0 * np.log(np.diag(cholesky(A))).sum()


# ================================================================== eigenvectors: the power method and deflation
def power_method(A, v0, iters):
    """v_t proportional to A v_{t-1}, normalised (7.168); returns the iterates and their Rayleigh quotients (7.172)."""
    A = np.asarray(A, float)
    v = np.asarray(v0, float) / np.linalg.norm(v0)
    V, lam = [v], [v @ A @ v]
    for _ in range(iters):
        w = A @ v
        v = w / np.linalg.norm(w)
        V.append(v)
        lam.append(v @ A @ v)
    return np.array(V), np.array(lam)


def deflate(A, u, lam):
    """A - lam u u^T (7.174): removes the eigenpair (lam, u) of a symmetric matrix, keeps the others."""
    u = np.asarray(u, float)
    return np.asarray(A, float) - lam * np.outer(u, u)


def top_eigs_by_deflation(A, k, iters=2000, seed=0):
    """The k eigenpairs of largest magnitude of a symmetric matrix by power iteration and deflation (Section 7.4.7)."""
    rng = np.random.default_rng(seed)
    B = np.array(A, float)
    vals, vecs = [], []
    for _ in range(k):
        V, lam = power_method(B, rng.standard_normal(B.shape[0]), iters)
        vals.append(lam[-1])
        vecs.append(V[-1])
        B = deflate(B, V[-1], lam[-1])
    return np.array(vals), np.array(vecs).T


def sin_angle(v, u):
    """sin of the angle between the lines spanned by v and u (insensitive to sign)."""
    v = np.asarray(v, float) / np.linalg.norm(v)
    u = np.asarray(u, float) / np.linalg.norm(u)
    return np.linalg.norm(v - (v @ u) * u)          # accurate also when the angle is tiny


def rot2(theta):
    c, s = np.cos(theta), np.sin(theta)
    return np.array([[c, -s], [s, c]])


def sym2(l1, l2, theta_deg):
    """The symmetric 2 x 2 matrix with eigenvalues l1, l2 and first eigenvector at angle theta (degrees):
    A = U diag(l1, l2) U^T with U a rotation (7.157). Used by the power-method demonstration."""
    U = rot2(np.deg2rad(theta_deg))
    return U @ np.diag([l1, l2]) @ U.T


# ================================================================== trace estimation
def hutchinson(A, m, rng, kind="gauss"):
    """(1/m) sum_j v_j^T A v_j with E[v v^T] = I (7.37): Gaussian or Rademacher probes."""
    n = A.shape[0]
    if kind == "gauss":
        V = rng.standard_normal((n, m))
    else:
        V = rng.choice([-1.0, 1.0], size=(n, m))
    return np.einsum("im,ij,jm->", V, A, V) / m


def hutchinson_sd(A, m, kind="gauss"):
    """Exact standard deviation of the m-probe estimator: var = 2||A_s||_F^2 / m (Gaussian),
    2(||A_s||_F^2 - sum_i a_ii^2) / m (Rademacher), with A_s the symmetric part of A."""
    As = 0.5 * (A + A.T)
    f2 = (As ** 2).sum()
    v = 2 * f2 if kind == "gauss" else 2 * (f2 - (np.diag(As) ** 2).sum())
    return np.sqrt(v / m)


# ================================================================== data matrices (Section 7.2.4)
def centering_matrix(N):
    """C_N = I_N - J_N / N (7.86)."""
    return np.eye(N) - np.ones((N, N)) / N


def double_center(K):
    """Centred Gram matrix C K C = K - JK/N - KJ/N + (1^T K 1) J / N^2 (7.89, with the last term written as a matrix)."""
    N = K.shape[0]
    r = K.mean(1, keepdims=True)
    c = K.mean(0, keepdims=True)
    return K - r - c + K.mean()


def sq_dists(X, Y):
    """Squared Euclidean distances D_ij = ||x_i||^2 - 2 x_i^T y_j + ||y_j||^2 (7.93), without loops."""
    xx = (X ** 2).sum(1)[:, None]
    yy = (Y ** 2).sum(1)[None, :]
    return np.maximum(xx - 2 * X @ Y.T + yy, 0.0)


# ================================================================== whitening (Section 7.4.5)
def whitening(X, ddof=0):
    """PCA and ZCA whitening matrices of the data X (rows = cases), (7.164), (7.166).

    Sigma = X_c^T X_c / (N - ddof) with X_c the centred data; Sigma = E D E^T with the eigenvalues in
    decreasing order and the eigenvector signs fixed so that det E = +1 and the first component of
    e_1 is positive (the convention of the demonstration)."""
    X = np.asarray(X, float)
    mu = X.mean(0)
    Xc = X - mu
    S = Xc.T @ Xc / (len(X) - ddof)
    d, E = np.linalg.eigh(S)
    d, E = d[::-1], E[:, ::-1]
    if E[0, 0] < 0:
        E[:, 0] *= -1
    if np.linalg.det(E) < 0:
        E[:, -1] *= -1
    Wpca = np.diag(d ** -0.5) @ E.T
    Wzca = E @ np.diag(d ** -0.5) @ E.T
    return dict(mu=mu, S=S, d=d, E=E, Wpca=Wpca, Wzca=Wzca)


def standardize(X, ddof=0):
    """(X - 1 mu^T) diag(sigma)^{-1} (7.82): every column gets mean 0 and standard deviation 1."""
    X = np.asarray(X, float)
    return (X - X.mean(0)) / X.std(0, ddof=ddof)


# ================================================================== SVD tools
def pinv_svd(A, rtol=1e-12):
    """Moore-Penrose pseudo-inverse V S^+ U^T (7.191): invert the singular values above rtol * sigma_max."""
    U, s, Vt = np.linalg.svd(A, full_matrices=False)
    inv = np.where(s > rtol * s.max(), 1.0 / np.where(s > 0, s, 1.0), 0.0)
    return (Vt.T * inv) @ U.T


def truncated_svd(A, K):
    """Best rank-K approximation U_K S_K V_K^T (Section 7.5.5)."""
    U, s, Vt = np.linalg.svd(A, full_matrices=False)
    return (U[:, :K] * s[:K]) @ Vt[:K]


def svd_from_gram(A):
    """Singular values and left singular vectors of a wide matrix A (m <= n) from the eigendecomposition of
    the m x m matrix A A^T (7.182)-(7.184): the route the browser demonstration takes."""
    lam, U = np.linalg.eigh(A @ A.T)
    lam, U = lam[::-1], U[:, ::-1]
    return np.sqrt(np.maximum(lam, 0.0)), U


# ================================================================== calculus
def fd_derivative(f, x, h, kind="forward"):
    """Finite-difference approximations of f'(x) (7.241)."""
    if kind == "forward":
        return (f(x + h) - f(x)) / h
    if kind == "central":
        return (f(x + h / 2) - f(x - h / 2)) / h
    return (f(x) - f(x - h)) / h


def num_grad(f, X, h=1e-6):
    """Central-difference gradient of a scalar function of a vector or matrix argument (used to confirm (7.262)-(7.273))."""
    X = np.array(X, float)
    G = np.zeros_like(X)
    it = np.nditer(X, flags=["multi_index"])
    for _ in it:
        i = it.multi_index
        E = np.zeros_like(X)
        E[i] = h
        G[i] = (f(X + E) - f(X - E)) / (2 * h)
    return G


# ================================================================== data
def load_davis_males():
    """Height (cm) and weight (kg) of the 88 men in the Davis (1990) study (R package carData), cached as CSV."""
    path = os.path.join(CACHE_DIR, "ch07_davis_males.csv")
    if not os.path.exists(path):
        js = os.path.join(DATA_OUT, "ch07-heightweight.json")
        if os.path.exists(js):                      # the copy published with the demonstrations
            d = json.load(open(js))
            return np.column_stack([d["height"], d["weight"]])
        os.makedirs(CACHE_DIR, exist_ok=True)
        rscript = shutil.which("Rscript") or "/usr/local/bin/Rscript"
        r = ('library(carData); d <- Davis[Davis$sex == "M", c("height", "weight")]; '
             'write.csv(d, "%s", row.names = FALSE)' % path)
        subprocess.run([rscript, "-e", r], check=True, capture_output=True)
    return np.loadtxt(path, delimiter=",", skiprows=1)


def load_image(name="china"):
    """A greyscale 200 x 320 version (uint8) of one of the photographs bundled with scikit-learn: the
    central 400 x 640 window, converted to luminance and resized with a Lanczos filter."""
    from PIL import Image
    from sklearn.datasets import load_sample_image
    im = Image.fromarray(load_sample_image(name + ".jpg")).convert("L")
    w, h = im.size                      # 640 x 427
    top = (h - 400) // 2
    im = im.crop((0, top, 640, top + 400)).resize((IMG_W, IMG_H), Image.LANCZOS)
    return np.asarray(im, dtype=np.uint8)


SHUFFLE_SEED = 7


def shuffled_image(img):
    """The same pixels in a random order (the permutation the SVD demonstration uses)."""
    p = js_shuffle(img.size, SHUFFLE_SEED)
    return img.ravel()[p].reshape(img.shape)


# ================================================================== Figure 7.6
def fig_7_6(out=None):
    """Level sets of a quadratic form and of the Gaussian with the inverse matrix, with the eigenvectors."""
    lam = np.array([4.0, 1.0])
    U = rot2(np.deg2rad(30.0))                 # u_1 at 30 degrees, u_2 at 120 degrees
    A = U @ np.diag(lam) @ U.T
    semi = lam ** -0.5                         # (a) and (b) are the same ellipse, labelled through A or through Sigma = A^{-1}
    fig, axes = plt.subplots(1, 2, figsize=(8.4, 3.9))
    t = np.linspace(0, 2 * np.pi, 400)
    for k, ax in enumerate(axes):
        pts = U @ np.vstack([semi[0] * np.cos(t), semi[1] * np.sin(t)])
        ax.plot(pts[0], pts[1], color=RED, lw=2)
        labels = [r"$\lambda_1^{-1/2}$", r"$\lambda_2^{-1/2}$"] if k == 0 else [r"$\gamma_2^{1/2}$", r"$\gamma_1^{1/2}$"]
        for i, (col, name) in enumerate([(BLUE, r"$\mathbf{u}_1$"), (GREEN, r"$\mathbf{u}_2$")]):
            v = U[:, i] * semi[i]
            ax.annotate("", v, (0, 0), arrowprops=dict(arrowstyle="-|>", color=col, lw=1.6))
            ax.text(*(v * 1.22), name, color=col, fontsize=11, ha="center", va="center")
            perp = np.array([-U[1, i], U[0, i]]) * (0.13 if i == 0 else -0.16)
            ax.text(*(v / 2 + perp), labels[i], fontsize=10, ha="center", va="center")
        if k == 0:
            ax.set_title(r"(a) $\mathbf{x}^\top\mathbf{A}\mathbf{x}=1$, eigenvalues $\lambda_1=4,\ \lambda_2=1$")
        else:
            ax.set_title(r"(b) $\boldsymbol{\Sigma}=\mathbf{A}^{-1}$, eigenvalues $\gamma_1=1,\ \gamma_2=\frac{1}{4}$")
        ax.axhline(0, color=GREY, lw=0.6)
        ax.axvline(0, color=GREY, lw=0.6)
        ax.set_aspect("equal")
        ax.set_xlim(-1.35, 1.35)
        ax.set_ylim(-1.15, 1.15)
        ax.set_xlabel(r"$x_1$")
        ax.set_ylabel(r"$x_2$")
    fig.tight_layout()
    savefig(fig, CH, "fig7-6", out)


# ================================================================== Figure 7.7
def fig_7_7(out=None):
    """Height and weight data: raw, standardised, PCA-whitened and ZCA-whitened."""
    X = load_davis_males()
    w = whitening(X)
    Xc = X - w["mu"]
    panels = [("Raw", X), ("Standardised", standardize(X)),
              ("PCA-whitened", Xc @ w["Wpca"].T), ("ZCA-whitened", Xc @ w["Wzca"].T)]
    fig, axes = plt.subplots(2, 2, figsize=(8.0, 7.0))
    for k, (ax, (title, Z)) in enumerate(zip(axes.ravel(), panels)):
        ax.plot(Z[:, 0], Z[:, 1], "x", color=BLUE, ms=5, mew=1)
        mu = Z.mean(0)
        S = np.cov(Z.T, bias=True)
        ex, ey = common.ellipse_xy(mu, S, 2.0)
        ax.plot(ex, ey, color=BLUE, lw=1)
        for j in range(4):
            ax.text(Z[j, 0], Z[j, 1], " %d" % (j + 1), fontsize=12, color="k", va="bottom")
        ax.set_title(title)
        if k >= 2 or k == 1:
            ax.set_aspect("equal", "datalim")
        if k == 0:
            ax.set_xlabel("height (cm)")
            ax.set_ylabel("weight (kg)")
        panel_label(ax, "abcd"[k], "lower right")
    fig.tight_layout()
    savefig(fig, CH, "fig7-7", out)


# ================================================================== Figures 7.9 and 7.10
def fig_7_9(out=None):
    """Truncated-SVD approximations of an image of rank 200 by matrices of rank 2, 5 and 20."""
    A = load_image().astype(float)
    U, s, Vt = np.linalg.svd(A, full_matrices=False)
    fig, axes = plt.subplots(2, 2, figsize=(8.0, 5.6))
    for ax, K, lab in zip(axes.ravel(), [200, 2, 5, 20], "abcd"):
        Ak = (U[:, :K] * s[:K]) @ Vt[:K]
        ax.imshow(np.clip(Ak, 0, 255), cmap="gray", vmin=0, vmax=255, interpolation="nearest")
        rel = np.linalg.norm(A - Ak) / np.linalg.norm(A)
        ax.set_title("(%s) rank %d" % (lab, K) + ("" if K == 200 else ", relative error %.3f" % rel))
        ax.set_xticks([])
        ax.set_yticks([])
    fig.tight_layout()
    savefig(fig, CH, "fig7-9", out)


def fig_7_10(out=None):
    """log10 of the first 100 singular values of the image and of its pixels shuffled at random."""
    A = load_image().astype(float)
    s = np.linalg.svd(A, compute_uv=False)
    s2 = np.linalg.svd(shuffled_image(load_image()).astype(float), compute_uv=False)
    fig, ax = plt.subplots(figsize=(4.8, 3.3))
    i = np.arange(1, 101)
    ax.plot(i, np.log10(s[:100]), color=RED, label="original")
    ax.plot(i, np.log10(s2[:100]), color=BLUE, label="pixels shuffled")
    ax.set_xlabel(r"index $i$")
    ax.set_ylabel(r"$\log_{10}\sigma_i$")
    ax.legend()
    fig.tight_layout()
    savefig(fig, CH, "fig7-10", out)


# ================================================================== Figure 7.12
EQ_A = np.array([[1.0, 2.0], [-1.0, 2.0], [1.0, -1.0]])
EQ_B = np.array([4.0, 2.4, -0.3])


def eq_label(a1, a2, b):
    def term(c, v, first):
        sgn = "-" if c < 0 else ("" if first else "+")
        mag = "" if abs(c) == 1 else "%g" % abs(c)
        return sgn + mag + v
    return "$" + term(a1, "x_1", True) + term(a2, "x_2", False) + "=%g$" % b


def fig_7_12(out=None):
    """Least-norm solution of one equation, the unique solution of two, the least-squares solution of three."""
    fig, axes = plt.subplots(1, 3, figsize=(10.2, 3.5))
    xs = np.linspace(-1, 3.2, 10)
    cols = [BLUE, PURPLE, ORANGE]
    for m, ax in zip([1, 2, 3], axes):
        A, b = EQ_A[:m], EQ_B[:m]
        for i in range(m):
            a1, a2 = A[i]
            ax.plot(xs, (b[i] - a1 * xs) / a2, color=cols[i], lw=1.4, label=eq_label(a1, a2, b[i]))
        if m == 1:
            x = pinv_svd(A) @ b                     # = A^T (A A^T)^{-1} b (7.223)
            ax.plot([0, x[0]], [0, x[1]], ":", color=RED, lw=1.6)
            title = "(a) $m=1<n$: least-norm solution"
        elif m == 2:
            x = lu_solve(A, b)
            title = "(b) $m=n=2$: unique solution"
        else:
            Q, R = gram_schmidt_qr(A)
            x = back_sub(R, Q.T @ b)                # least squares through QR
            title = "(c) $m=3>n$: least-squares solution"
        ax.plot(*x, "o", color=RED, ms=7, zorder=5)
        ax.text(x[0] + 0.12, x[1] - 0.05, "(%.2f, %.2f)" % tuple(x), fontsize=8.5, va="top")
        ax.axhline(0, color=GREY, lw=0.6)
        ax.axvline(0, color=GREY, lw=0.6)
        ax.set_xlim(-1, 3.2)
        ax.set_ylim(-0.6, 2.8)
        ax.set_aspect("equal")
        ax.set_title(title, fontsize=10)
        ax.set_xlabel(r"$x_1$")
        ax.legend(fontsize=7.5, loc="upper right")
    axes[0].set_ylabel(r"$x_2$")
    fig.tight_layout()
    savefig(fig, CH, "fig7-12", out)


# ================================================================== Figure 7.S1: power method
def random_sym(n, eigs, seed):
    rng = np.random.default_rng(seed)
    Q, _ = np.linalg.qr(rng.standard_normal((n, n)))
    return (Q * eigs) @ Q.T, Q


def fig_7_s1(out=None):
    """Power method: angle to u_1 and error of the Rayleigh quotient against the iteration, for three eigengaps."""
    n, T = 50, 120
    fig, axes = plt.subplots(1, 2, figsize=(9.0, 3.5))
    v0 = np.random.default_rng(1).standard_normal(n)
    for ratio, col in zip([0.5, 0.9, 0.97], [RED, BLUE, GREEN]):
        eigs = np.concatenate([[1.0, ratio], np.linspace(ratio * 0.9, 0.0, n - 2)])
        A, Q = random_sym(n, eigs, 3)
        V, lam = power_method(A, v0, T)
        err = np.array([sin_angle(v, Q[:, 0]) for v in V])
        t = np.arange(T + 1)
        axes[0].semilogy(t, err, color=col, label=r"$\lambda_2/\lambda_1=%g$" % ratio)
        axes[0].semilogy(t, err[0] / np.sqrt(1 - err[0] ** 2) * ratio ** t, ":", color=col, lw=1)
        axes[1].semilogy(t, np.maximum(1.0 - lam, 1e-17), color=col)
        axes[1].semilogy(t, (1 - lam[0]) * ratio ** (2 * t), ":", color=col, lw=1)
    axes[0].set_ylim(1e-16, 2)
    axes[1].set_ylim(1e-17, 2)
    axes[0].set_title(r"(a) $\sin\angle(\mathbf{v}_t,\mathbf{u}_1)$; dotted: $\tan\theta_0\,(\lambda_2/\lambda_1)^t$")
    axes[1].set_title(r"(b) $\lambda_1-R(\mathbf{A},\mathbf{v}_t)$; dotted: rate $(\lambda_2/\lambda_1)^{2t}$")
    for ax in axes:
        ax.set_xlabel("iteration $t$")
    axes[0].legend(fontsize=8)
    fig.tight_layout()
    savefig(fig, CH, "fig7-s1", out)


# ================================================================== Figure 7.S2: Hutchinson
def hutchinson_matrix(n=100, seed=5):
    rng = np.random.default_rng(seed)
    B = rng.standard_normal((n, n // 2))
    return B @ B.T / n + np.diag(rng.uniform(0, 2, n))


def fig_7_s2(out=None):
    """Standard deviation of the Hutchinson estimator against the number of probes, simulated and exact."""
    A = hutchinson_matrix()
    ms = np.array([1, 2, 5, 10, 20, 50, 100, 200, 500])
    rng = np.random.default_rng(11)
    fig, ax = plt.subplots(figsize=(5.2, 3.6))
    for kind, col, lab in [("gauss", BLUE, "Gaussian probes"), ("rademacher", RED, "Rademacher probes")]:
        sd = [np.std([hutchinson(A, m, rng, kind) for _ in range(400)]) for m in ms]
        ax.loglog(ms, sd, "o", color=col, ms=4, label=lab + " (simulated)")
        ax.loglog(ms, [hutchinson_sd(A, m, kind) for m in ms], "-", color=col, lw=1, label=lab + " (exact)")
    ax.set_xlabel("number of probes $m$")
    ax.set_ylabel("standard deviation of the estimate")
    ax.set_title(r"tr$(\mathbf{A})=%.1f$, $n=100$" % np.trace(A))
    ax.legend(fontsize=8)
    fig.tight_layout()
    savefig(fig, CH, "fig7-s2", out)


# ================================================================== Figure 7.S3: finite differences
def fig_7_s3(out=None):
    """Error of forward and central differences of exp at x = 1 against the step h."""
    hs = np.logspace(-16, 0, 161)
    f, x0, d = np.exp, 1.0, np.exp(1.0)
    eps = np.finfo(float).eps
    fig, ax = plt.subplots(figsize=(5.2, 3.6))
    for kind, col in [("forward", RED), ("central", BLUE)]:
        err = np.abs([fd_derivative(f, x0, h, kind) - d for h in hs])
        ax.loglog(hs, np.maximum(err, 1e-17), color=col, lw=1.2, label=kind + " difference")
    ax.loglog(hs, d / 2 * hs, ":", color=RED, lw=1)
    ax.loglog(hs, d / 24 * hs ** 2, ":", color=BLUE, lw=1)
    ax.loglog(hs, 2 * eps * d / hs, "--", color=GREY, lw=1, label=r"rounding $\approx 2\epsilon|f|/h$")
    ax.axvline(np.sqrt(eps), color=RED, lw=0.6, alpha=0.6)
    ax.axvline(eps ** (1 / 3), color=BLUE, lw=0.6, alpha=0.6)
    ax.set_ylim(1e-12, 1e2)
    ax.set_xlabel("step $h$")
    ax.set_ylabel("absolute error")
    ax.set_title(r"$f=\exp$ at $x=1$; vertical lines $\epsilon^{1/2}$, $\epsilon^{1/3}$")
    ax.legend(fontsize=8, loc="upper center")
    fig.tight_layout()
    savefig(fig, CH, "fig7-s3", out)


# ================================================================== Figure 7.S4: conditioning of least squares
def vandermonde(N, deg):
    t = np.linspace(0, 1, N)
    return np.vander(t, deg + 1, increasing=True)


def ls_errors(deg, N=60):
    """Relative error of three least-squares solvers on a consistent polynomial system of degree deg."""
    A = vandermonde(N, deg)
    xt = np.ones(deg + 1)
    b = A @ xt
    kappa = np.linalg.cond(A)
    G = A.T @ A
    try:
        L = cholesky(G)
        x_ne = back_sub(L.T, forward_sub(L, A.T @ b))
    except np.linalg.LinAlgError:
        x_ne = np.full(deg + 1, np.nan)
    Q, R = np.linalg.qr(A)
    x_qr = back_sub(R, Q.T @ b)
    x_sv = pinv_svd(A, 1e-15) @ b
    e = lambda x: np.linalg.norm(x - xt) / np.linalg.norm(xt)
    return kappa, e(x_ne), e(x_qr), e(x_sv)


def fig_7_s4(out=None):
    """Least squares: the normal equations lose accuracy like kappa^2, QR and the SVD like kappa."""
    rows = np.array([ls_errors(d) for d in range(1, 17)])
    eps = np.finfo(float).eps
    fig, ax = plt.subplots(figsize=(5.4, 3.7))
    k = rows[:, 0]
    ax.loglog(k, rows[:, 1], "o-", color=RED, ms=4, label=r"normal equations (Cholesky of $\mathbf{A}^\top\mathbf{A}$)")
    ax.loglog(k, rows[:, 2], "s-", color=BLUE, ms=4, label="QR (Householder)")
    ax.loglog(k, rows[:, 3], "^-", color=GREEN, ms=4, label="SVD pseudo-inverse")
    ax.loglog(k, eps * k ** 2, ":", color=RED, lw=1, label=r"$\epsilon\,\kappa^2$")
    ax.loglog(k, eps * k, ":", color=BLUE, lw=1, label=r"$\epsilon\,\kappa$")
    ax.set_ylim(1e-17, 1e3)
    ax.set_xlabel(r"condition number $\kappa(\mathbf{A})$")
    ax.set_ylabel("relative error of the solution")
    ax.set_title("polynomial least squares, degrees 1 to 16, $N=60$")
    ax.legend(fontsize=7.5, loc="upper left")
    fig.tight_layout()
    savefig(fig, CH, "fig7-s4", out)


# ================================================================== data export
def export_json():
    os.makedirs(DATA_OUT, exist_ok=True)
    imgs = {name: base64.b64encode(load_image(name).tobytes()).decode("ascii") for name in ("china", "flower")}
    with open(os.path.join(DATA_OUT, "ch07-images.json"), "w") as f:
        json.dump({"h": IMG_H, "w": IMG_W, "shuffle_seed": SHUFFLE_SEED, "images": imgs}, f, separators=(",", ":"))
    X = load_davis_males()
    with open(os.path.join(DATA_OUT, "ch07-heightweight.json"), "w") as f:
        json.dump({"height": [float(v) for v in X[:, 0]], "weight": [float(v) for v in X[:, 1]]}, f, separators=(",", ":"))
    print("wrote ch07-images.json, ch07-heightweight.json")


FIGURES = {"7.6": fig_7_6, "7.7": fig_7_7, "7.9": fig_7_9, "7.10": fig_7_10, "7.12": fig_7_12,
           "7.S1": fig_7_s1, "7.S2": fig_7_s2, "7.S3": fig_7_s3, "7.S4": fig_7_s4}

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