"""Hastie, Tibshirani and Friedman (2009), Chapter 14: Unsupervised Learning (part B, Sections 14.5.2-14.10).

Reproduces the figures of Sections 14.5.2-14.10 of T. Hastie, R. Tibshirani and J. Friedman, The Elements
of Statistical Learning (2nd edition, Springer, 2009), pp. 541-579, written from scratch with numpy, scipy
and matplotlib; part A (ch14_unsupervised_learning_a.py) covers Sections 14.2-14.5.1 and supplies the
shared data loaders (zip-code digits, the half-sphere data), K-means and the principal components. Every
method is a small function meant to be read next to the lecture notes (../ch14-unsupervised-learning.html):

* Principal curves and surfaces, Section 14.5.2: principal_curve() alternates the two steps (14.62)
  (local linear smoothing of each coordinate on the arc length, then projection onto the curve,
  project_to_polyline()); principal_surface() is the two-dimensional version with a local linear
  surface smoother on a lattice (surface_smooth()).
* Spectral clustering, Section 14.5.3: similarity_graph() (radial similarities on the symmetric
  K-nearest-neighbour pairs or on all pairs), graph_laplacian() (14.63) and its normalised versions,
  spectral_embedding(); rings() draws the concentric rings of Figure 14.29 with the demos' random number
  generator (ch02.JSRandom, identical to DK.rng in courses/demo-kit.js) and kmeans_js() is K-means with
  starts drawn by the same generator.
* Kernel principal components, Section 14.5.4: kernel_pca() (double centring (14.65), Z = UD,
  alpha = u/d) and kernel_pca_project() for new points (Exercise 14.16).
* Sparse principal components, Section 14.5.5: sparse_pca() alternates the elastic-net step and the
  Procrustes step of (14.71) (elastic_net_prox(), elastic_net_gram(), procrustes_theta() (14.116)).
* Non-negative matrix factorisation, Section 14.6: nmf_kl() is the multiplicative algorithm (14.74) for
  the Poisson log-likelihood (14.73) (nmf_loglik()); nmf_js_start() gives the browser demo's start.
  Archetypal analysis (14.75)-(14.77): archetypes(), by block coordinate descent with exact
  simplex-constrained least-squares blocks (simplex_ls(), project_simplex(), furthest_sum()).
* Independent component analysis, Section 14.7: whiten(), fastica() (the fixed point (14.96) with
  G(u) = log cosh u and symmetric orthogonalisation), negentropy_approx() (14.87), amari() (14.97);
  fit_tilted_gaussian() and prodenica() implement Algorithm 14.3 (the tilted Gaussian (14.89) fitted by
  the penalised Poisson regression (14.93)-(14.94)); factor_analysis() fits (14.80)-(14.81) by
  maximum likelihood (Exercise 14.15).
* Multidimensional scaling and nonlinear dimension reduction, Sections 14.8-14.9: classical_mds()
  (Exercise 14.11), local_mds() (the stress (14.106)), lle() ((14.102)-(14.104)) and isomap().
* PageRank, Section 14.10: pagerank() is the power method (14.110) on the matrix A of (14.109)
  (pagerank_matrix()), pagerank_direct() solves (14.108) directly and finds the eigenvector of A.
* exercises() returns the numbers used in the solutions of Exercises 14.12-14.25; som_1d() is a
  one-dimensional self-organising map for Exercise 14.13. The functions compare_fastica_sklearn() and
  compare_lle_isomap_sklearn() compare our implementations with scikit-learn's.

Figures reproduced: 14.27-14.31, 14.33-14.40, 14.42-14.47. Run `python3 ch14_unsupervised_learning_b.py
--list`, `python3 ch14_unsupervised_learning_b.py` (all figures, about two minutes once the ICA simulation
and the archetypes of the threes are cached in cache/; about six minutes the first time), `--fig 14.29`,
or `--demo-data` to write ../data/ch14-rings.json and ../data/ch14-zip-twos.json for the browser demos.

Figures not reproduced:
* 14.19 (a self-organising map of 12,088 newsgroup articles): the document collection is not available.
* 14.32 (a photograph of a brain slice): an illustration, nothing is computed.
* 14.41 (EEG recordings and their ICA components): the recordings are not available.
Figures whose data are not available, replaced by the same analysis on other data:
* 14.31: the corpus callosum shapes are not available; the figure shows the first four ordinary and
  sparse principal component loadings of the 658 zip-code threes as 16 x 16 images.
* 14.33: the face database is not available; NMF, VQ and PCA with r = 25 basis images are fitted to the
  731 training 2s (grey levels shifted to [0, 2]).
* 14.45: the face images are not available; the LLE embedding is of the zip-code threes.

Settings chosen where the book gives none:
* Figure 14.27: 100 points about an arc of radius 3 (angles U(0.25, 2.9), noise sd 0.22, numpy seed 1427);
  smoother bandwidth 0.2 x range of lambda.
* Figure 14.28: half-sphere data of part A (noise sd 0.1); local linear surface smoother with bandwidth
  0.2 x range of lambda_1 on a 31 x 31 lattice padded by 10%.
* Figures 14.29-14.30: rings(seed=1429); symmetric 10-NN graph ("i among the 10 nearest of i' or vice
  versa"), weights exp(-d^2/c) with c = 2; K-means on the 2nd and 3rd eigenvectors with 10 starts.
* Figure 14.31: lambda_2 = 1e-6, lambda_1 = 60 for every component.
* Figure 14.33: NMF 500 sweeps from a uniform(0.5, 1.5) start (seed 33); VQ is K-means with 5 starts;
  PCA is the uncentred rank-25 SVD, so that all three are X ~ W H.
* Figure 14.34: eleven points at angles U(28, 62) degrees, radii U(1.2, 3.4) (seed 1434).
* Figure 14.35: 50 points from N(0, [[1, .6], [.6, 1]]) (seed 1435); best of 2 starts for archetypes,
  20 for K-means. Figure 14.36: best of 3 starts.
* Figures 14.37-14.38: sources sin(2 pi t/100) and a sawtooth of period 285 (t = 1..1000), mixing
  [[1, .7], [.5, 1]]; uniforms on (-sqrt 3, sqrt 3) with mixing [[1, .45], [.25, .9]] (seed 1438).
* Figures 14.39-14.40: the threes are whitened in the space of their first 30 principal components,
  FastICA extracts 30 components and the five with the largest negentropy approximation are shown.
* Figure 14.42: 30 simulations per distribution (the book also uses 30), N = 1024, 5 random starts per
  method, 256 bins and a cubic B-spline with 20 coefficients and a third-difference penalty at 5 df for
  ProDenICA; KernelICA is not included. The two- and four-component Gaussian mixtures (g-r) use our own
  parameters, chosen to give the shapes named by Bach and Jordan (2002).
* Figure 14.44: 25 points on x2 = -x1^2 with x1 ~ U(-3.2, 3.2) (seed 1444); local MDS with K = 2 and
  tau = 0.01, the best of 30 L-BFGS starts.
* Figure 14.45: LLE with K = 12 neighbours and regularisation 1e-3 x trace.
* Figures 14.46-14.47: d = 0.85, power iterations until the largest change is below 1e-12.
"""
import json
import math
import os
import warnings

import numpy as np
from scipy import linalg, optimize, sparse
from scipy.interpolate import BSpline
from scipy.optimize import nnls
from scipy.sparse.csgraph import shortest_path

import common
from common import BLUE, GREEN, GREY, ORANGE, PURPLE, RED, savefig
import ch02_overview_supervised_learning as ch02
import ch14_unsupervised_learning_a as A

import matplotlib.pyplot as plt
from matplotlib.colors import LinearSegmentedColormap

CH = 14
HERE = os.path.dirname(os.path.abspath(__file__))
CACHE_DIR = os.path.join(HERE, "cache")
DATA_OUT = os.path.normpath(os.path.join(HERE, "..", "data"))
os.makedirs(CACHE_DIR, exist_ok=True)
warnings.filterwarnings("ignore", category=linalg.LinAlgWarning)

RING_COLOURS = ("#e69f00", "#56b4e9", "#009e73")   # inner, middle, outer ring (as in Figures 14.29-14.30)
# black for positive pixel values, red for negative ones, white at zero (the book's NMF/VQ/PCA montage)
SIGNED = LinearSegmentedColormap.from_list("signed", ["#c62828", "#ffffff", "#000000"])


def _save_json(obj, name):
    os.makedirs(DATA_OUT, exist_ok=True)
    path = os.path.join(DATA_OUT, name)
    with open(path, "w") as f:
        json.dump(obj, f, separators=(",", ":"))
    print("wrote", os.path.relpath(path, os.getcwd()), "(%.0f kB)" % (os.path.getsize(path) / 1024))
    return path


def sqdist(A_, B_=None):
    """Matrix of squared Euclidean distances between the rows of A_ and B_ (default B_ = A_)."""
    B_ = A_ if B_ is None else B_
    d = (A_ * A_).sum(1)[:, None] + (B_ * B_).sum(1)[None, :] - 2 * A_ @ B_.T
    return np.maximum(d, 0.0)


def ari(a, b):
    """Adjusted Rand index between two labellings (Hubert and Arabie 1985)."""
    from sklearn.metrics import adjusted_rand_score
    return float(adjusted_rand_score(a, b))


def kmeans_js(X, K, seed=1, starts=10, iters=200):
    """K-means whose random starts (distinct observations) are drawn with the demos' generator
    (DK.rng in courses/demo-kit.js, mirrored by ch02.JSRandom), so a browser demo reproduces it.
    Returns (labels, within sum of squares) of the best start."""
    rng = ch02.JSRandom(seed)
    N = len(X)
    best = (np.inf, None)
    for _ in range(starts):
        idx = []
        while len(idx) < K:
            j = int(math.floor(rng.u() * N))
            if j not in idx:
                idx.append(j)
        C = X[idx].copy()
        lab = None
        for _ in range(iters):
            new = np.argmin(((X[:, None, :] - C[None, :, :]) ** 2).sum(-1), axis=1)
            if lab is not None and np.array_equal(new, lab):
                break
            lab = new
            for r in range(K):
                if (lab == r).any():
                    C[r] = X[lab == r].mean(0)
        ss = float(((X - C[lab]) ** 2).sum())
        if ss < best[0] - 1e-12:
            best = (ss, lab.copy())
    return best[1], best[0]


def digit_img(x):
    """16 x 16 image of a zip-code digit stored row by row."""
    return np.asarray(x).reshape(16, 16)


def show_digit(ax, x, cmap="gray_r", vmin=-1, vmax=1):
    ax.imshow(digit_img(x), cmap=cmap, vmin=vmin, vmax=vmax, interpolation="nearest")
    ax.set_xticks([])
    ax.set_yticks([])


# =========================================================================== 14.5.2 principal curves and surfaces
def local_linear(t, Y, t0, h):
    """Local linear regression of the columns of Y on t, Gaussian kernel of bandwidth h, at the points t0."""
    out = np.empty((len(t0), Y.shape[1]))
    for m, s in enumerate(t0):
        w = np.exp(-0.5 * ((t - s) / h) ** 2)
        sw, swt = w.sum(), (w * (t - s)).sum()
        swtt = (w * (t - s) ** 2).sum()
        den = sw * swtt - swt ** 2
        a = (w[:, None] * Y).sum(0)
        b = ((w * (t - s))[:, None] * Y).sum(0)
        out[m] = (swtt * a - swt * b) / den if den > 1e-12 * sw * sw else a / sw
    return out


def project_to_polyline(X, P):
    """Closest point of the polyline through the rows of P to each row of X.
    Returns (arc-length coordinate of the closest point, squared distance)."""
    seg = P[1:] - P[:-1]
    L2 = np.maximum((seg * seg).sum(1), 1e-300)
    cum = np.r_[0.0, np.cumsum(np.sqrt(L2))]
    lam = np.empty(len(X))
    dist = np.empty(len(X))
    for i, x in enumerate(X):
        t = np.clip(((x - P[:-1]) * seg).sum(1) / L2, 0, 1)
        Q = P[:-1] + t[:, None] * seg
        d2 = ((Q - x) ** 2).sum(1)
        k = int(np.argmin(d2))
        lam[i], dist[i] = cum[k] + t[k] * math.sqrt(L2[k]), d2[k]
    return lam, dist


def principal_curve(X, span=0.2, n_grid=200, max_iter=50, tol=1e-6, history=False):
    """The principal-curve algorithm (14.62) for data (Hastie and Stuetzle 1989).

    Start from the first principal component line; then alternate
    (a) f(lambda) <- E(X | lambda(X) = lambda), estimated by smoothing every coordinate of X against
        lambda with a local linear smoother whose Gaussian bandwidth is span x (range of lambda);
    (b) lambda(x) <- the arc length of the closest point of the curve to x (projection onto the
        smoothed curve, evaluated on n_grid values and joined into a polyline);
    until the relative change of the average squared distance is below tol.
    Returns dict(lam, curve (n_grid x p), D2 (average squared distance per iteration))."""
    X = np.asarray(X, float)
    xbar, U, d, V = A.pca(X)
    lam = (X - xbar) @ V[:, 0]
    lam = lam - lam.min()
    D2, path = [], []
    curve = None
    for it in range(max_iter):
        h = span * (lam.max() - lam.min())
        grid = np.linspace(lam.min(), lam.max(), n_grid)
        curve = local_linear(lam, X, grid, h)
        lam, dist = project_to_polyline(X, curve)
        D2.append(float(dist.mean()))
        if history:
            path.append((curve.copy(), lam.copy()))
        if it > 0 and abs(D2[-2] - D2[-1]) < tol * D2[-1]:
            break
    out = dict(lam=lam, curve=curve, D2=np.array(D2))
    if history:
        out["path"] = path
    return out


def arc_data(n=100, seed=1427, sd=0.22):
    """Points scattered about a circular arc of radius 3 (data for Figure 14.27)."""
    r = np.random.default_rng(seed)
    t = np.sort(r.uniform(0.25, 2.9, n))
    return np.c_[3 * np.cos(t), 3 * np.sin(t)] + sd * r.standard_normal((n, 2)), t


def surface_smooth(L, Y, G, h):
    """Two-dimensional local linear smooth (Gaussian kernel, bandwidth h) of the columns of Y on the
    coordinates L (N x 2), evaluated at the rows of G (M x 2): at each g, weighted least squares of Y
    on (1, l1 - g1, l2 - g2), intercept returned."""
    W = np.exp(-0.5 * sqdist(G, L) / h ** 2)
    out = np.empty((len(G), Y.shape[1]))
    for m, g in enumerate(G):
        Z = np.c_[np.ones(len(L)), L - g]
        w = W[m]
        M = Z.T @ (w[:, None] * Z) + 1e-8 * np.eye(3)
        out[m] = linalg.solve(M, Z.T @ (w[:, None] * Y), assume_a="pos")[0]
    return out


def principal_surface(X, h=0.2, n_grid=31, max_iter=30, tol=1e-5, pad=0.1):
    """Principal surface by the two-dimensional version of (14.62): start from the first two principal
    component scores; (a) smooth every coordinate of X on (lambda_1, lambda_2) with a local linear
    Gaussian-kernel smoother of bandwidth h x (range of lambda_1), on an n_grid x n_grid lattice that
    extends the range of the current coordinates by the fraction pad on each side; (b) project every
    point to the closest lattice point of the fitted surface. With a local constant smoother step (a)
    is the batch SOM update (14.48) with one prototype per lattice point.
    Returns dict(lam (N x 2), grid (n_grid^2 x 2), surface, D2)."""
    X = np.asarray(X, float)
    xbar, U, d, V = A.pca(X)
    lam = (X - xbar) @ V[:, :2]
    D2 = []
    for it in range(max_iter):
        lo, hi = lam.min(0), lam.max(0)
        span = hi - lo
        g1 = np.linspace(lo[0] - pad * span[0], hi[0] + pad * span[0], n_grid)
        g2 = np.linspace(lo[1] - pad * span[1], hi[1] + pad * span[1], n_grid)
        G = np.array([(a, b) for b in g2 for a in g1])
        S = surface_smooth(lam, X, G, h * span[0])
        d2 = sqdist(X, S)
        k = d2.argmin(1)
        lam = G[k]
        D2.append(float(d2[np.arange(len(X)), k].mean()))
        if it > 0 and abs(D2[-2] - D2[-1]) < tol * D2[-1]:
            break
    return dict(lam=lam, grid=G, surface=S, n_grid=n_grid, D2=np.array(D2))


def fig_14_27(out_dir=None):
    """Principal curve of points about an arc (Figure 14.27)."""
    X, t = arc_data()
    pc = principal_curve(X)
    xbar, U, d, V = A.pca(X)
    fig, ax = plt.subplots(figsize=(5.0, 4.4))
    ax.plot(X[:, 0], X[:, 1], "o", ms=3.5, color=RED, zorder=3)
    C = pc["curve"]
    ax.plot(C[:, 0], C[:, 1], color=BLUE, lw=2.0, zorder=2, label="principal curve")
    s = np.linspace(-3.5, 3.5, 2)
    ax.plot(xbar[0] + s * V[0, 0], xbar[1] + s * V[1, 0], color=GREY, lw=1, ls="--", label="first principal component")
    # highlight the points projecting to two chosen arc-length values: f(lambda) is their average
    seg = C[1:] - C[:-1]
    cum = np.r_[0, np.cumsum(np.sqrt((seg ** 2).sum(1)))]
    for frac in (0.3, 0.72):
        l0 = frac * cum[-1]
        sel = np.abs(pc["lam"] - l0) < 0.035 * cum[-1]
        f0 = np.array([np.interp(l0, cum, C[:, j]) for j in range(2)])
        for x in X[sel]:
            ax.plot([x[0], f0[0]], [x[1], f0[1]], color=CYAN_, lw=1.2, zorder=2.5)
        ax.plot(*f0, "o", ms=6, color="k", zorder=4)
        ax.annotate(r"$f(\lambda)=[f_1(\lambda),f_2(\lambda)]$" if frac > 0.5 else "", f0, xytext=(f0[0] + 0.3, f0[1] + 0.55), fontsize=9)
    ax.set_aspect("equal")
    ax.set_xlabel("$X_1$")
    ax.set_ylabel("$X_2$")
    ax.legend(loc="lower center", fontsize=8, frameon=False)
    savefig(fig, CH, "fig14-27", out_dir)
    return pc


CYAN_ = "#17becf"


def fig_14_28(out_dir=None):
    """Principal surface fitted to the half-sphere data (Figure 14.28)."""
    X, g = A.half_sphere()
    ps = principal_surface(X)
    # draw the fitted surface over the range of the final coordinates only
    n = 25
    lo, hi = ps["lam"].min(0), ps["lam"].max(0)
    G = np.array([(a, b) for b in np.linspace(lo[1], hi[1], n) for a in np.linspace(lo[0], hi[0], n)])
    S = surface_smooth(ps["lam"], X, G, 0.2 * (hi[0] - lo[0])).reshape(n, n, 3)
    fig = plt.figure(figsize=(9.2, 4.2))
    ax = fig.add_subplot(1, 2, 1, projection="3d")
    ax.plot_wireframe(S[:, :, 0], S[:, :, 1], S[:, :, 2], rstride=2, cstride=2, color="#9acd32", lw=0.6)
    for k in range(3):
        P = X[g == k]
        ax.scatter(P[:, 0], P[:, 1], P[:, 2], s=9, color=A.HS_COLOURS[k], depthshade=False)
    ax.view_init(elev=22, azim=35)
    ax.set_xlabel("$X_1$", labelpad=-8)
    ax.set_ylabel("$X_2$", labelpad=-8)
    ax.set_zlabel("$X_3$", labelpad=-8)
    ax.tick_params(labelsize=6, pad=-3)
    ax.set_box_aspect((1, 1, 0.8), zoom=0.85)
    ax2 = fig.add_subplot(1, 2, 2)
    rng = np.random.default_rng(0)
    L = ps["lam"] + 0.012 * (ps["lam"].max(0) - ps["lam"].min(0)) * rng.standard_normal(ps["lam"].shape)
    for k in range(3):
        ax2.plot(L[g == k, 0], L[g == k, 1], "o", ms=3.5, color=A.HS_COLOURS[k])
    ax2.set_xlabel(r"$\hat\lambda_1$")
    ax2.set_ylabel(r"$\hat\lambda_2$")
    fig.subplots_adjust(wspace=0.15)
    savefig(fig, CH, "fig14-28", out_dir)
    return ps


# =========================================================================== 14.5.3 spectral clustering
def rings(seed=1429, n_per=150, radii=(1.0, 2.8, 5.0), sd=0.25):
    """Concentric rings of Figure 14.29, drawn with the demos' generator: for ring k, point i,
    angle = 2 pi u, then x = r cos(angle) + sd z1, y = r sin(angle) + sd z2 (z from Box-Muller with
    the cached second value, as DK.rng.norm). Returns (X, ring label)."""
    rng = ch02.JSRandom(seed)
    X, g = [], []
    for k, r in enumerate(radii):
        for _ in range(n_per):
            a = 2 * math.pi * rng.u()
            x = r * math.cos(a) + sd * rng.norm()
            y = r * math.sin(a) + sd * rng.norm()
            X.append((x, y))
            g.append(k)
    return np.array(X), np.array(g)


def knn_mask(D2, k):
    """Symmetric k-nearest-neighbour set N_K: (i, i') joined if either is among the other's k nearest."""
    N = len(D2)
    order = np.argsort(D2 + np.diag(np.full(N, np.inf)), axis=1)[:, :k]
    M = np.zeros((N, N), bool)
    M[np.repeat(np.arange(N), k), order.ravel()] = True
    return M | M.T


def similarity_graph(X, k=10, c=2.0, graph="knn"):
    """Adjacency matrix W: radial similarities exp(-d^2/c) on the symmetric k-NN pairs (graph='knn')
    or on all pairs (graph='full'), zero diagonal."""
    D2 = sqdist(X)
    S = np.exp(-D2 / c)
    np.fill_diagonal(S, 0.0)
    if graph == "knn":
        S = np.where(knn_mask(D2, k), S, 0.0)
    return S


def graph_laplacian(W, kind="unnormalised"):
    """L = G - W (14.63), or the normalised versions: 'rw' I - G^{-1} W, 'sym' I - G^{-1/2} W G^{-1/2}."""
    g = W.sum(1)
    L = np.diag(g) - W
    if kind == "unnormalised":
        return L
    if kind == "sym":
        s = 1 / np.sqrt(g)
        return s[:, None] * L * s[None, :]
    return L / g[:, None]


def spectral_embedding(X, k=10, c=2.0, m=3, graph="knn", laplacian="unnormalised", W=None):
    """Smallest eigenvalues and eigenvectors of the graph Laplacian of X (Section 14.5.3).
    Returns (all eigenvalues ascending, the first m eigenvectors as columns N x m). For 'rw' the
    generalised problem L v = lambda G v is solved (same eigenvalues as I - G^{-1}W)."""
    W = similarity_graph(X, k, c, graph) if W is None else W
    g = W.sum(1)
    L = np.diag(g) - W
    if laplacian == "unnormalised":
        vals, vecs = linalg.eigh(L)
    elif laplacian == "sym":
        s = 1 / np.sqrt(g)
        vals, vecs = linalg.eigh(s[:, None] * L * s[None, :])
    else:
        vals, vecs = linalg.eigh(L, np.diag(g))
    # fix signs (largest |entry| positive)
    idx = np.abs(vecs).argmax(0)
    vecs = vecs * np.sign(vecs[idx, np.arange(vecs.shape[1])])
    return vals, vecs[:, :m]


def rings_reference(seed=1429, k=10, c=2.0):
    X, g = rings(seed)
    vals, Z = spectral_embedding(X, k, c, m=3)
    lab_raw, _ = kmeans_js(X, 3, seed=1, starts=10)
    lab_sp, _ = kmeans_js(Z[:, 1:3], 3, seed=1, starts=10)
    return dict(X=X, g=g, vals=vals, Z=Z, ari_kmeans=ari(g, lab_raw), ari_spectral=ari(g, lab_sp),
                lab_raw=lab_raw, lab_sp=lab_sp)


def export_rings_json():
    """Reference numbers of the spectral clustering demo (data generated in the browser by rings())."""
    out = {"generator": "rings(seed, n_per, radii, sd): ring k then point i; angle = 2 pi u; x = r cos + sd z; y = r sin + sd z",
           "cases": []}
    for (seed, radii, k, c) in [(1429, (1.0, 2.8, 5.0), 10, 2.0), (1429, (1.0, 2.8, 5.0), 5, 2.0),
                                (1429, (1.0, 2.8, 5.0), 3, 2.0), (7, (1.0, 3.0), 10, 2.0)]:
        X, g = rings(seed, radii=radii)
        K = len(radii)
        vals, Z = spectral_embedding(X, k, c, m=K)
        lab_raw, w_raw = kmeans_js(X, K, seed=1, starts=10)
        lab_sp, w_sp = kmeans_js(Z[:, 1:K], K, seed=1, starts=10)
        out["cases"].append(dict(seed=seed, radii=list(radii), sd=0.25, n_per=150, k=k, c=c,
                                 smallest_eigenvalues=[float("%.12g" % v) for v in vals[:6]],
                                 ari_kmeans_raw=round(ari(g, lab_raw), 10), ari_spectral=round(ari(g, lab_sp), 10),
                                 within_ss_raw=float("%.12g" % w_raw), first_point=[float("%.15g" % v) for v in X[0]]))
    return _save_json(out, "ch14-rings.json")


def _ring_scatter(ax, X, g, s=6):
    for k in range(int(g.max()) + 1):
        ax.plot(X[g == k, 0], X[g == k, 1], "o", ms=s / 2.5, color=RING_COLOURS[k % 3])


def fig_14_29(out_dir=None):
    """Spectral clustering of three concentric rings (Figure 14.29)."""
    R = rings_reference()
    X, g, vals, Z = R["X"], R["g"], R["vals"], R["Z"]
    fig = plt.figure(figsize=(8.4, 7.8))
    gs = fig.add_gridspec(4, 2, left=0.09, right=0.98, bottom=0.07, top=0.97, hspace=0.55, wspace=0.3,
                          height_ratios=[1, 1, 0.8, 0.8])
    ax = fig.add_subplot(gs[0:2, 0])
    _ring_scatter(ax, X, g)
    ax.set_aspect("equal")
    ax.set_xlabel("$x_1$")
    ax.set_ylabel("$x_2$")
    ax = fig.add_subplot(gs[0:2, 1])
    ax.plot(np.arange(1, 16), vals[:15], "o", ms=4, color=RING_COLOURS[2])
    ax.axhline(0, color=GREY, lw=0.8, ls=":")
    ax.set_xlabel("Number")
    ax.set_ylabel("Eigenvalue")
    ax.set_xticks([1, 3, 5, 10, 15])
    for row, j, lab in ((2, 1, "2nd smallest"), (3, 2, "3rd smallest")):
        axe = fig.add_subplot(gs[row, 0])
        for k in range(3):
            idx = np.where(g == k)[0]
            axe.plot(idx, Z[idx, j], "o", ms=2.2, color=RING_COLOURS[k])
        axe.set_ylabel(lab, fontsize=8)
        axe.tick_params(labelsize=7)
        if row == 2:
            axe.set_title("Eigenvectors", fontsize=9.5)
        else:
            axe.set_xlabel("Index")
    ax = fig.add_subplot(gs[2:4, 1])
    for k in range(3):
        ax.plot(Z[g == k, 1], Z[g == k, 2], "o", ms=3, color=RING_COLOURS[k])
    ax.set_xlabel("Second smallest eigenvector")
    ax.set_ylabel("Third smallest eigenvector")
    ax.set_title("Spectral clustering", fontsize=9.5)
    ax.tick_params(labelsize=7)
    savefig(fig, CH, "fig14-29", out_dir)
    return R


# =========================================================================== 14.5.4 kernel principal components
def kernel_pca(K, m=2):
    """Kernel PCA from a kernel matrix (14.65): double-centre K~ = (I - M) K (I - M) = U D^2 U^T,
    components Z = U D, coefficients alpha_jm = u_jm / d_m (Exercise 14.16).
    Returns (eigenvalues of K~ descending, U (N x m), Z (N x m), alpha (N x m))."""
    N = len(K)
    J = np.eye(N) - 1.0 / N
    Kc = J @ K @ J
    vals, U = linalg.eigh((Kc + Kc.T) / 2)
    vals, U = vals[::-1], U[:, ::-1]
    idx = np.abs(U[:, :m]).argmax(0)
    s = np.sign(U[idx, np.arange(m)])
    U = U[:, :m] * s
    d = np.sqrt(np.maximum(vals[:m], 0))
    return vals, U, U * d, U / d


def kernel_pca_project(K_new, K, alpha):
    """Components of new points: rows of K_new are K(x0, x_j); centring uses the training kernel.
    z0m = sum_j alpha_jm K~(x0, x_j) with K~ the centred kernel (Exercise 14.16)."""
    N = len(K)
    Kn = K_new - K_new.mean(1, keepdims=True) - K.mean(0)[None, :] + K.mean()
    return Kn @ alpha


def fig_14_30(out_dir=None):
    """Kernel principal components of the rings with four kernels (Figure 14.30)."""
    X, g = rings()
    D2 = sqdist(X)
    panels = []
    for c in (2.0, 10.0):
        K = np.exp(-D2 / c)
        panels.append(("Radial kernel (c=%g)" % c, kernel_pca(K, 2)[1], ("First largest eigenvector", "Second largest eigenvector")))
    W = similarity_graph(X, 10, 2.0, "knn")
    panels.append(("NN radial kernel (c=2)", kernel_pca(W, 2)[1], ("First largest eigenvector", "Second largest eigenvector")))
    vals, Z = spectral_embedding(X, c=2.0, m=3, graph="full")
    panels.append(("Radial kernel Laplacian (c=2)", Z[:, 1:3], ("Second smallest eigenvector", "Third smallest eigenvector")))
    fig, axes = common.panel_grid(2, 2, size=(3.9, 3.5))
    for ax, (title, U, labs) in zip(axes.ravel(), panels):
        for k in range(3):
            ax.plot(U[g == k, 0], U[g == k, 1], "o", ms=2.6, color=RING_COLOURS[k])
        ax.set_title(title, fontsize=9.5)
        ax.set_xlabel(labs[0], fontsize=8.5)
        ax.set_ylabel(labs[1], fontsize=8.5)
        ax.tick_params(labelsize=7)
    fig.tight_layout()
    savefig(fig, CH, "fig14-30", out_dir)


# =========================================================================== 14.5.5 sparse principal components
def elastic_net_gram(G, b, lam2, lam1, v0=None, tol=1e-10, max_iter=5000):
    """Coordinate descent for min_v v^T (G + lam2 I) v - 2 b^T v + lam1 ||v||_1 (an elastic net written
    through the Gram matrix G = X^T X and b = X^T y): v_j <- S(b_j - sum_{l != j} G_jl v_l, lam1/2) / (G_jj + lam2)."""
    p = len(b)
    v = np.zeros(p) if v0 is None else v0.copy()
    Gv = G @ v
    diag = np.diag(G) + lam2
    for _ in range(max_iter):
        delta = 0.0
        for j in range(p):
            r = b[j] - (Gv[j] - G[j, j] * v[j])
            new = np.sign(r) * max(abs(r) - lam1 / 2, 0.0) / diag[j]
            if new != v[j]:
                Gv += G[:, j] * (new - v[j])
                delta = max(delta, abs(new - v[j]))
                v[j] = new
        if delta < tol:
            break
    return v


def elastic_net_prox(Gl, B, lam1, V0, step, iters=300):
    """All K elastic nets min_v v^T Gl v - 2 b_k^T v + lam1_k ||v||_1 at once by accelerated proximal
    gradient (soft thresholding), warm-started at V0; Gl = X^T X + lam2 I, B = X^T X Theta."""
    V, Zm, t = V0.copy(), V0.copy(), 1.0
    thr = step * np.asarray(lam1)[None, :]
    for _ in range(iters):
        U = Zm - step * 2 * (Gl @ Zm - B)
        Vn = np.sign(U) * np.maximum(np.abs(U) - thr, 0.0)
        tn = 0.5 * (1 + math.sqrt(1 + 4 * t * t))
        Zm = Vn + (t - 1) / tn * (Vn - V)
        V, t = Vn, tn
    return V


def procrustes_theta(M):
    """argmax_Theta trace(Theta^T M) subject to Theta^T Theta = I (14.116): Theta = U Q^T with M = U D Q^T."""
    U, d, Qt = linalg.svd(M, full_matrices=False)
    return U @ Qt


def sparse_pca(X, K=4, lam2=1e-6, lam1=0.0, max_iter=400, tol=1e-6):
    """Sparse principal components by the criterion (14.71) of Zou, Hastie and Tibshirani (2006):
    alternate (i) Theta fixed: K elastic-net regressions of X theta_k on X (Exercise 14.12, part 1),
        solved together by accelerated proximal gradient (elastic_net_gram is the coordinate-descent
        version of one of them, used to confirm the solution),
    (ii) V fixed: the reduced-rank Procrustes step Theta = U Q^T from the SVD of X^T X V (part 2).
    X is centred. lam1 may be a scalar or one value per component. Returns (V normalised to unit
    length, Theta, number of iterations)."""
    X = X - X.mean(0)
    G = X.T @ X
    xbar, U, d, Vp = A.pca(X)
    Theta = Vp[:, :K].copy()
    V = Theta.copy()
    lam1 = np.broadcast_to(np.asarray(lam1, float), (K,))
    Gl = G + lam2 * np.eye(G.shape[0])
    step = 1.0 / (2 * linalg.eigvalsh(Gl)[-1])
    for it in range(max_iter):
        Vold = V.copy()
        V = elastic_net_prox(Gl, G @ Theta, lam1, V, step)
        Theta = procrustes_theta(G @ V)
        if np.abs(V - Vold).max() < tol * max(np.abs(V).max(), 1e-12):
            break
    nrm = np.linalg.norm(V, axis=0)
    nrm[nrm == 0] = 1
    return V / nrm, Theta, it + 1


def fig_14_31(out_dir=None, lam1=60.0):
    """Substitute for Figure 14.31: standard and sparse principal component loadings of the zip-code
    threes (the corpus callosum shapes of the book are not available)."""
    X = A.zip_threes()
    xbar, U, d, V = A.pca(X)
    Vs, Th, its = sparse_pca(X, K=4, lam2=1e-6, lam1=lam1)
    # align signs with the ordinary components
    Vs = Vs * np.sign((Vs * V[:, :4]).sum(0))
    fig, axes = plt.subplots(2, 4, figsize=(7.6, 4.0))
    for k in range(4):
        for row, (W, name) in enumerate(((V[:, :4], "PCA"), (Vs, "Sparse PCA"))):
            ax = axes[row, k]
            v = W[:, k]
            m = np.abs(v).max()
            ax.imshow(digit_img(v), cmap=SIGNED, vmin=-m, vmax=m, interpolation="nearest")
            ax.set_xticks([])
            ax.set_yticks([])
            nz = int((np.abs(v) > 1e-12).sum())
            ax.set_title("%s %d (%d nonzero)" % (name, k + 1, nz), fontsize=8)
    fig.tight_layout()
    savefig(fig, CH, "fig14-31", out_dir)
    return Vs, its


# =========================================================================== 14.6 non-negative matrix factorisation
def nmf_loglik(X, W, H):
    """L(W, H) of (14.73): sum_ij [x_ij log (WH)_ij - (WH)_ij] (terms with x_ij = 0 contribute -(WH)_ij)."""
    WH = W @ H
    pos = X > 0
    return float((X[pos] * np.log(WH[pos])).sum() - WH.sum())


def nmf_kl(X, r=None, iters=200, W0=None, H0=None, seed=0, trace=False):
    """Lee and Seung's multiplicative updates (14.74) for the Poisson log-likelihood (14.73):
    w_ik <- w_ik sum_j h_kj x_ij/(WH)_ij / sum_j h_kj, then (with the new W)
    h_kj <- h_kj sum_i w_ik x_ij/(WH)_ij / sum_i w_ik. Each sweep never decreases L (Exercise 14.23).
    The ratio x_ij/(WH)_ij is taken as 0 where x_ij = 0 (its limit; this avoids 0/0 when a column of H
    reaches 0). Returns (W, H, log-likelihood after every sweep if trace)."""
    X = np.asarray(X, float)
    if W0 is None:
        rng = np.random.default_rng(seed)
        W0, H0 = rng.uniform(0.5, 1.5, (X.shape[0], r)), rng.uniform(0.5, 1.5, (r, X.shape[1]))
    W, H = np.array(W0, float), np.array(H0, float)
    tr = []
    pos = X > 0
    for _ in range(iters):
        R = np.divide(X, W @ H, out=np.zeros_like(X), where=pos)     # x_ij / (WH)_ij, taken as 0 where x_ij = 0
        W = W * (R @ H.T) / H.sum(1)[None, :]
        R = np.divide(X, W @ H, out=np.zeros_like(X), where=pos)
        H = H * (W.T @ R) / W.sum(0)[:, None]
        if trace:
            tr.append(nmf_loglik(X, W, H))
    return W, H, np.array(tr)


def nmf_js_start(N, p, r, seed=2025):
    """Starting values of the browser demo: W[i][k] = 0.5 + u row by row, then H[k][j] = 0.5 + u,
    with u from DK.rng(seed) (ch02.JSRandom)."""
    rng = ch02.JSRandom(seed)
    W = np.array([[0.5 + rng.u() for _ in range(r)] for _ in range(N)])
    H = np.array([[0.5 + rng.u() for _ in range(p)] for _ in range(r)])
    return W, H


def twos_demo_data(n=300):
    """The first n training 2s, quantised to integers 0..255 of (x + 1)/2; the demo uses v/255."""
    X = A.zip_class(2)[:n]
    Q = np.rint((X + 1) / 2 * 255).astype(int)
    return Q, Q / 255.0


def export_twos_json():
    Q, X = twos_demo_data()
    xbar = X.mean(0)
    d = linalg.svd(X - xbar, compute_uv=False)
    d_unc = linalg.svd(X, compute_uv=False)
    ref = []
    for r in (5, 10, 25):
        W0, H0 = nmf_js_start(*X.shape, r, 2025)
        W, H, tr = nmf_kl(X, iters=200, W0=W0, H0=H0, trace=True)
        W50, H50, _ = nmf_kl(X, iters=50, W0=W0, H0=H0)
        ref.append(dict(r=r, loglik_50=float("%.15g" % tr[49]), loglik_200=float("%.15g" % tr[199]),
                        nmf_frob2_50=float("%.15g" % ((X - W50 @ H50) ** 2).sum()),
                        nmf_frob2_200=float("%.15g" % ((X - W @ H) ** 2).sum()),
                        pca_centred_rss=float("%.15g" % (d[r:] ** 2).sum()),
                        svd_uncentred_rss=float("%.15g" % (d_unc[r:] ** 2).sum())))
    out = {"n": int(Q.shape[0]), "p": 256, "scale": 255, "start": "W[i][k]=0.5+u row by row, then H[k][j]=0.5+u, DK.rng(2025)",
           "X": Q.ravel().tolist(), "reference": ref, "total_ss_centred": float((d ** 2).sum())}
    return _save_json(out, "ch14-zip-twos.json")


def vq_pca_nmf(r=25, nmf_iters=500):
    """The three factorisations of Figure 14.33 on the 731 training 2s shifted to [0, 2]."""
    X = A.zip_class(2) + 1.0
    W, H, tr = nmf_kl(X, r, iters=nmf_iters, seed=33, trace=True)
    km = A.kmeans(X, r, n_init=5, seed=33)
    U, d, Vt = linalg.svd(X, full_matrices=False)
    return dict(X=X, W=W, H=H, tr=tr, km=km, U=U[:, :r] * d[:r], Vt=Vt[:r])


def _montage(ax, B, cmap, signed=False):
    """5 x 5 montage of the 25 rows of B (each a 16 x 16 image), each image scaled separately."""
    tile = np.ones((5 * 17 + 1, 5 * 17 + 1)) * (0.0 if signed else 0.0)
    for k in range(25):
        r_, c_ = divmod(k, 5)
        b = digit_img(B[k])
        m = np.abs(b).max() or 1
        tile[1 + 17 * r_:17 + 17 * r_, 1 + 17 * c_:17 + 17 * c_] = b / m
    ax.imshow(tile, cmap=cmap, vmin=-1 if signed else 0, vmax=1, interpolation="nearest")
    for t in range(6):
        ax.axhline(17 * t, color="#4a78b5", lw=0.6)
        ax.axvline(17 * t, color="#4a78b5", lw=0.6)
    ax.set_xticks([])
    ax.set_yticks([])


def fig_14_33(out_dir=None, case=0):
    """Substitute for Figure 14.33 (the face database is not available): NMF, VQ and PCA with r = 25
    basis images on the zip-code 2s, and the reconstruction of one 2."""
    R = vq_pca_nmf()
    X = R["X"]
    i = case
    rows = []
    rows.append(("NMF", R["H"], R["W"][i], R["W"][i] @ R["H"], False))
    lab = R["km"]["labels"]
    coef = np.zeros(25)
    coef[lab[i]] = 1
    rows.append(("VQ", R["km"]["centres"], coef, R["km"]["centres"][lab[i]], False))
    rows.append(("PCA", R["Vt"], R["U"][i], R["U"][i] @ R["Vt"], True))
    fig = plt.figure(figsize=(7.4, 7.6))
    gs = fig.add_gridspec(3, 6, width_ratios=[5.2, 0.45, 1.5, 0.45, 1.5, 0.05], hspace=0.22, wspace=0.06,
                          left=0.02, right=0.98, top=0.93, bottom=0.02)
    for row, (name, B, c, rec, signed) in enumerate(rows):
        ax = fig.add_subplot(gs[row, 0])
        _montage(ax, B, SIGNED if signed else "gray_r", signed=signed)
        ax.set_title(name, loc="left", fontsize=11)
        ax = fig.add_subplot(gs[row, 1])
        ax.text(0.5, 0.5, r"$\times$", ha="center", va="center", fontsize=16)
        ax.axis("off")
        ax = fig.add_subplot(gs[row, 2])
        cm = np.abs(c).max() or 1
        ax.imshow(c.reshape(5, 5) / cm, cmap=SIGNED if signed else "gray_r", vmin=-1 if signed else 0, vmax=1)
        ax.set_xticks([])
        ax.set_yticks([])
        ax = fig.add_subplot(gs[row, 3])
        ax.text(0.5, 0.5, "=", ha="center", va="center", fontsize=16)
        ax.axis("off")
        ax = fig.add_subplot(gs[row, 4])
        ax.imshow(digit_img(rec), cmap="gray_r", vmin=0, vmax=2, interpolation="nearest")
        ax.set_xticks([])
        ax.set_yticks([])
    ax = fig.add_axes([0.80, 0.935, 0.12, 0.06])
    ax.imshow(digit_img(X[i]), cmap="gray_r", vmin=0, vmax=2, interpolation="nearest")
    ax.set_xticks([])
    ax.set_yticks([])
    ax.set_title("Original", fontsize=9)
    savefig(fig, CH, "fig14-33", out_dir)
    return R


def cone_points(seed=1434):
    """Eleven points in the positive quadrant, inside the cone between the angles 25 and 65 degrees."""
    r = np.random.default_rng(seed)
    ang = np.radians(r.uniform(28, 62, 11))
    rad = r.uniform(1.2, 3.4, 11)
    return np.c_[rad * np.cos(ang), rad * np.sin(ang)]


def exact_nmf_coefficients(X, H):
    """Coefficients W with X = W H for a 2 x 2 basis H (rows h1, h2); they are all >= 0 exactly when every
    point lies in the cone spanned by h1 and h2."""
    return X @ linalg.inv(H)


def fig_14_34(out_dir=None):
    """Non-uniqueness of the non-negative matrix factorisation (Figure 14.34)."""
    X = cone_points()
    bases = [np.array([[np.cos(np.radians(a)), np.sin(np.radians(a))] for a in pair]) * 4.2
             for pair in ((80, 12), (70, 20))]
    fig, ax = plt.subplots(figsize=(4.6, 4.4))
    ax.plot(X[:, 0], X[:, 1], "o", ms=5, color=BLUE, zorder=3)
    for H, ls, col in zip(bases, ("-", "--"), (CYAN_, GREEN)):
        Wc = exact_nmf_coefficients(X, H)
        assert (Wc >= 0).all() and np.allclose(Wc @ H, X)
        for k in range(2):
            ax.annotate("", H[k], (0, 0), arrowprops=dict(arrowstyle="-|>", color=col, lw=1.2, ls=ls))
            ax.text(*(H[k] * 1.05), "$h_%d$" % (2 - k) if ls == "-" else "$h'_%d$" % (2 - k), color=col, fontsize=10)
    ax.set_xlim(0, 4.6)
    ax.set_ylim(0, 4.6)
    ax.set_aspect("equal")
    ax.set_xlabel("$X_1$")
    ax.set_ylabel("$X_2$")
    savefig(fig, CH, "fig14-34", out_dir)


# =========================================================================== archetypal analysis
def project_simplex(V):
    """Euclidean projection of each row of V (or of a vector) onto the probability simplex
    {w >= 0, sum w = 1} (sort-and-threshold algorithm)."""
    V = np.asarray(V, float)
    one = V.ndim == 1
    V = np.atleast_2d(V)
    n = V.shape[1]
    U = -np.sort(-V, axis=1)
    css = np.cumsum(U, axis=1) - 1
    ok = U - css / np.arange(1, n + 1) > 0
    k = n - 1 - np.argmax(ok[:, ::-1], axis=1)
    tau = css[np.arange(len(V)), k] / (k + 1)
    out = np.maximum(V - tau[:, None], 0.0)
    return out[0] if one else out


def simplex_ls(Mx, Y, W0=None, L=None, max_iter=60, tol=1e-9):
    """For every row y of Y (or a single vector): min_w ||y - Mx w||^2 subject to w >= 0, sum w = 1,
    by accelerated projected gradient (FISTA) with exact projection onto the simplex, all rows at once,
    warm-started at W0."""
    one = np.asarray(Y).ndim == 1
    Y = np.atleast_2d(Y)
    n = Mx.shape[1]
    L = L if L is not None else linalg.norm(Mx, 2) ** 2
    G = Mx.T @ Mx
    YM = Y @ Mx
    W = np.full((len(Y), n), 1.0 / n) if W0 is None else np.atleast_2d(W0).copy()
    Z, t = W.copy(), 1.0
    for _ in range(max_iter):
        Wn = project_simplex(Z - (Z @ G - YM) / L)
        tn = 0.5 * (1 + math.sqrt(1 + 4 * t * t))
        Z = Wn + (t - 1) / tn * (Wn - W)
        done = np.abs(Wn - W).max() < tol
        W, t = Wn, tn
        if done:
            break
    if W0 is not None:   # keep the step monotone: never return rows worse than the warm start
        W0 = np.atleast_2d(W0)
        f_new = ((Y - W @ Mx.T) ** 2).sum(1)
        f_old = ((Y - W0 @ Mx.T) ** 2).sum(1)
        W = np.where((f_new <= f_old)[:, None], W, W0)
    return W[0] if one else W


def furthest_sum(X, r, start):
    """Indices of r data points: start, then repeatedly the point with the largest summed Euclidean
    distance to the points already chosen (the first choice is then discarded and redrawn, as usual)."""
    D = np.sqrt(sqdist(X))
    idx = [start]
    for _ in range(r):
        tot = D[:, idx].sum(1)
        tot[idx] = -1
        idx.append(int(tot.argmax()))
    return idx[1:]


def archetypes(X, r, n_start=5, seed=0, max_iter=400, tol=1e-7):
    """Archetypal analysis (14.75)-(14.77) (Cutler and Breiman 1994): minimise ||X - W B X||_F^2 over
    row-stochastic W (N x r) and B (r x N). Alternate (i) each row of W by simplex-constrained least
    squares on the archetypes H = B X; (ii) each archetype k in turn: with the others fixed the
    criterion is ||w_k||^2 ||z_k - X^T b_k||^2 + const, z_k = R_k^T w_k / ||w_k||^2, R_k = X - sum_{l != k}
    w_l h_l^T, a simplex-constrained least squares in b_k. The first start places the archetypes at data
    points chosen by the furthest-sum rule (each new point maximises the summed distance to those already
    chosen; Morup and Hansen 2012), the other n_start - 1 at random distinct data points; the best fit
    is returned as dict(H, W, B, rss, iters)."""
    X = np.asarray(X, float)
    N = len(X)
    LX = linalg.norm(X, 2) ** 2
    rng = np.random.default_rng(seed)
    best = None
    for s in range(n_start):
        B = np.zeros((r, N))
        B[np.arange(r), furthest_sum(X, r, int(rng.integers(N))) if s == 0 else rng.choice(N, r, replace=False)] = 1.0
        old = np.inf
        for it in range(max_iter):
            H = B @ X
            LH = linalg.norm(H, 2) ** 2
            W = simplex_ls(H.T, X, None if it == 0 else W, LH)
            for k in range(r):
                wk = W[:, k]
                nk = wk @ wk
                if nk < 1e-12:
                    continue
                Rk = X - W @ H + np.outer(wk, H[k])
                z = Rk.T @ wk / nk
                B[k] = simplex_ls(X.T, z, B[k], LX)
                H[k] = B[k] @ X
            rss = float(((X - W @ H) ** 2).sum())
            if old - rss < tol * rss:
                break
            old = rss
        if best is None or rss < best["rss"]:
            best = dict(H=H.copy(), W=W.copy(), B=B.copy(), rss=rss, iters=it + 1)
    return best


def gauss_cloud(n=50, seed=1435):
    r = np.random.default_rng(seed)
    S = np.array([[1.0, 0.6], [0.6, 1.0]])
    return r.multivariate_normal([0, 0], S, n)


def fig_14_35(out_dir=None):
    """Archetypal analysis (top) and K-means (bottom) on 50 bivariate Gaussian points, r = 2, 4, 8."""
    X = gauss_cloud()
    fig, axes = common.panel_grid(2, 3, size=(2.7, 2.7))
    res = {}
    for j, r in enumerate((2, 4, 8)):
        aa = archetypes(X, r, n_start=2, seed=r, max_iter=2500, tol=1e-9)
        km = A.kmeans(X, r, n_init=20, seed=r)
        res[r] = (aa, km)
        for row, (P, col) in enumerate(((aa["H"], RED), (km["centres"], BLUE))):
            ax = axes[row, j]
            ax.plot(X[:, 0], X[:, 1], "o", mfc="none", mec="#555555", ms=4, mew=0.7)
            ax.plot(P[:, 0], P[:, 1], "o", color=col, ms=7)
            ax.set_xticks([])
            ax.set_yticks([])
            if row == 0:
                ax.set_title("%d prototypes" % r, fontsize=9.5)
    fig.tight_layout()
    savefig(fig, CH, "fig14-35", out_dir)
    return res


def fig_14_36(out_dir=None):
    """Archetypes of the zip-code threes with 2, 3 and 4 archetypes (Figure 14.36)."""
    path = os.path.join(CACHE_DIR, "ch14_archetypes_threes.npz")
    X = A.zip_threes()
    if os.path.exists(path):
        z = np.load(path)
        Hs = {r: z["H%d" % r] for r in (2, 3, 4)}
    else:
        Hs = {r: archetypes(X, r, n_start=3, seed=r, max_iter=60, tol=1e-6)["H"] for r in (2, 3, 4)}
        np.savez(path, **{"H%d" % r: H for r, H in Hs.items()})
    fig, axes = plt.subplots(3, 4, figsize=(5.2, 4.0))
    for i, r in enumerate((2, 3, 4)):
        for j in range(4):
            ax = axes[i, j]
            if j < r:
                show_digit(ax, Hs[r][j])
            else:
                ax.axis("off")
    fig.subplots_adjust(wspace=0.08, hspace=0.08)
    savefig(fig, CH, "fig14-36", out_dir)
    return Hs


# =========================================================================== 14.7 independent component analysis
def whiten(X, q=None):
    """Centre X and rotate/scale it to identity sample covariance (divisor N), keeping the first q
    principal directions: Z = (X - m) K with K = E_q Lambda_q^{-1/2}. Returns (Z, m, K)."""
    m = X.mean(0)
    Xc = X - m
    vals, E = linalg.eigh(Xc.T @ Xc / len(X))
    vals, E = vals[::-1], E[:, ::-1]
    q = q or X.shape[1]
    K = E[:, :q] / np.sqrt(vals[:q])
    return Xc @ K, m, K


def sym_orth(Am):
    """Symmetric orthogonalisation (A A^T)^{-1/2} A = U V^T, A = U D V^T the SVD."""
    U, _, Vt = linalg.svd(Am)
    return U @ Vt


def random_orthogonal(p, rng):
    Q, R = linalg.qr(rng.standard_normal((p, p)))
    return Q * np.sign(np.diag(R))


E_LOGCOSH_GAUSS = 0.37456720749   # E log cosh(Z) for Z ~ N(0, 1) (numerical integration)


def negentropy_approx(S, a=1.0):
    """The approximation (14.87): J(Y) ~ [E G(Y) - E G(Z)]^2 with G(u) = (1/a) log cosh(a u), per column."""
    G = np.log(np.cosh(a * S)) / a
    if a == 1.0:
        EGZ = E_LOGCOSH_GAUSS
    else:
        z = np.linspace(-10, 10, 20001)
        EGZ = float(np.trapz(np.log(np.cosh(a * z)) / a * np.exp(-z * z / 2) / math.sqrt(2 * math.pi), z))
    return (G.mean(0) - EGZ) ** 2


def fastica(Z, n_starts=5, seed=0, a=1.0, max_iter=1000, tol=1e-10, A0=None):
    """FastICA on whitened data Z (N x p), all components at once (Hyvarinen and Oja 2000):
    the fixed point (14.96) with the contrast G(u) = (1/a) log cosh(a u), i.e.
    a_j <- E{Z tanh(a a_j^T Z)} - E{a (1 - tanh^2(a a_j^T Z))} a_j, followed by the symmetric
    orthogonalisation A <- U V^T. The start with the largest summed negentropy approximation (14.87)
    is kept. Returns (A orthogonal p x p with the directions as columns, S = Z A, iterations)."""
    N, p = Z.shape
    rng = np.random.default_rng(seed)
    best = None
    starts = [A0] if A0 is not None else [random_orthogonal(p, rng) for _ in range(n_starts)]
    for Am in starts:
        Am = sym_orth(Am)
        for it in range(max_iter):
            S = Z @ Am
            g = np.tanh(a * S)
            new = Z.T @ g / N - Am * (a * (1 - g * g)).mean(0)
            new = sym_orth(new)
            delta = np.abs(1 - np.abs((new * Am).sum(0))).max()
            Am = new
            if delta < tol:
                break
        J = negentropy_approx(Z @ Am, a).sum()
        if best is None or J > best[0]:
            best = (J, Am, it + 1)
    Am = best[1]
    return Am, Z @ Am, best[2]


def amari(A0, Ahat):
    """Amari distance (14.97) between two frames, with r = A0 Ahat^{-1}."""
    r = np.abs(A0 @ linalg.inv(Ahat))
    p = len(r)
    return float((r.sum(1) / r.max(1) - 1).sum() / (2 * p) + (r.sum(0) / r.max(0) - 1).sum() / (2 * p))


def amari_matrix(r):
    r = np.abs(r)
    p = len(r)
    return float((r.sum(1) / r.max(1) - 1).sum() / (2 * p) + (r.sum(0) / r.max(0) - 1).sum() / (2 * p))


def compare_fastica_sklearn(S_true=None, seed=0):
    """Our FastICA and scikit-learn's on the same mixed uniforms: the Amari-type distance between the two
    recovered source sets (via their cross-correlation matrix) and the distance of each from the truth."""
    from sklearn.decomposition import FastICA
    S, X, Amix = uniform_mixture()
    Z, m, K = whiten(X)
    Am, Sh, it = fastica(Z, seed=seed)
    sk = FastICA(n_components=2, whiten="unit-variance", fun="logcosh", algorithm="parallel",
                 random_state=seed, tol=1e-10, max_iter=2000).fit(X)
    Ssk = sk.transform(X)
    C = np.corrcoef(Sh.T, Ssk.T)[:2, 2:]
    Ct = np.corrcoef(Sh.T, S.T)[:2, 2:]
    return dict(ours_vs_sklearn=amari_matrix(C), ours_vs_truth=amari_matrix(Ct), iterations=it)


def uniform_mixture(n=500, seed=1438):
    """Two independent uniform sources with unit variance, and their mixture X = S A^T (Figure 14.38)."""
    r = np.random.default_rng(seed)
    S = r.uniform(-math.sqrt(3), math.sqrt(3), (n, 2))
    Amix = np.array([[1.0, 0.45], [0.25, 0.9]])
    return S, S @ Amix.T, Amix


def time_series_sources(n=1000):
    """Sources of Figure 14.37: a sine wave (about ten periods) and a sawtooth (three and a half)."""
    t = np.arange(1, n + 1)
    s1 = np.sin(2 * np.pi * t / 100.0)
    s2 = 2 * ((t / 285.0) % 1.0) - 1
    S = np.c_[s1, s2]
    return (S - S.mean(0)) / S.std(0)


def _traces(ax, Y, cols, title):
    Y = (Y - Y.mean(0)) / Y.std(0)
    for j in range(Y.shape[1]):
        off = 3.6 * (Y.shape[1] - 1 - j)
        ax.plot(Y[:, j] + off, color=cols[j], lw=0.9)
        ax.axhline(off - 1.8, color=GREY, lw=0.6) if j < Y.shape[1] - 1 else None
    ax.set_xticks([])
    ax.set_yticks([])
    ax.set_title(title, fontsize=9.5)


def fig_14_37(out_dir=None):
    """ICA versus PCA on two mixed time series (Figure 14.37)."""
    S = time_series_sources()
    Amix = np.array([[1.0, 0.7], [0.5, 1.0]])
    X = S @ Amix.T
    Z, m, K = whiten(X)
    Am, Sh, it = fastica(Z, n_starts=3, seed=37)
    # order and sign the ICA components to match the listed sources (sawtooth first, as in the book)
    C = np.corrcoef(Sh.T, S.T)[:2, 2:]
    order = [int(np.argmax(np.abs(C[:, 1]))), int(np.argmax(np.abs(C[:, 0])))]
    Sh = Sh[:, order] * np.sign(C[order, [1, 0]])
    fig, axes = plt.subplots(2, 2, figsize=(8.0, 4.2))
    _traces(axes[0, 0], S, (GREEN, RED), "Source signals")
    _traces(axes[0, 1], X, (PURPLE, ORANGE), "Measured signals")
    _traces(axes[1, 0], Z, (MAGENTA_, "#d4c21a"), "PCA solution")
    _traces(axes[1, 1], Sh, (RED, GREEN), "ICA solution")
    fig.tight_layout()
    savefig(fig, CH, "fig14-37", out_dir)
    return dict(corr=np.corrcoef(Sh.T, S[:, [1, 0]].T)[:2, 2:])


MAGENTA_ = "#c2185b"


def fig_14_38(out_dir=None):
    """Mixtures of independent uniforms: sources, data, PCA and ICA solutions (Figure 14.38)."""
    S, X, Amix = uniform_mixture()
    Z, m, K = whiten(X)
    Am, Sh, it = fastica(Z, n_starts=3, seed=38)
    fig, axes = common.panel_grid(2, 2, size=(2.9, 2.9))
    for ax, (Y, title, col) in zip(axes.ravel(), ((S, "Source S", GREEN), (X - X.mean(0), "Data X", GREEN),
                                                   (Z, "PCA solution", MAGENTA_), (Sh, "ICA solution", GREEN))):
        ax.plot(Y[:, 0], Y[:, 1], "o", ms=1.6, color=col)
        ax.set_title(title, fontsize=9.5)
        ax.set_aspect("equal")
        lim = 1.05 * np.abs(Y).max()
        ax.set_xlim(-lim, lim)
        ax.set_ylim(-lim, lim)
        ax.set_xticks([])
        ax.set_yticks([])
    fig.tight_layout()
    savefig(fig, CH, "fig14-38", out_dir)
    return dict(amari=amari_matrix(np.corrcoef(Sh.T, S.T)[:2, 2:]), iters=it)


def digits_ica(q=5, q_white=30, seed=39):
    """PCA and ICA of the zip threes. The data are whitened in the space of their first q_white principal
    components, FastICA extracts q_white components, and the q with the largest negentropy approximation
    (14.87) are kept, oriented to have positive skewness (their long tail positive) and ordered by
    decreasing negentropy. Returns the first q standardised principal components, these ICA scores, and
    the two most extreme and two most central images of each ICA component."""
    X = A.zip_threes()
    Z, m, K = whiten(X, q_white)
    Am, S, it = fastica(Z, n_starts=5, seed=seed)
    order = np.argsort(-negentropy_approx(S))[:q]
    S = S[:, order]
    S = S * np.sign((S ** 3).mean(0))
    P = Z[:, :q].copy()        # whitened PC scores = standardised principal components
    picks = []
    for j in range(q):
        ext = list(np.argsort(-S[:, j])[:2])
        cen = list(np.argsort(np.abs(S[:, j]))[:2])
        picks.append((ext, cen))
    return dict(X=X, P=P, S=S, picks=picks, kurt=(S ** 4).mean(0) - 3, kurt_pca=(P ** 4).mean(0) - 3, iters=it)


def fig_14_39(out_dir=None):
    """Pairs plot: five standardised PCA components (below the diagonal) and five ICA components (above)."""
    R = digits_ica()
    P, S, picks = R["P"], R["S"], R["picks"]
    q = P.shape[1]
    fig, axes = plt.subplots(q, q, figsize=(7.6, 7.6))
    hl = sorted(set(i for e, c in picks for i in e + c))
    for i in range(q):
        for j in range(q):
            ax = axes[i, j]
            ax.set_xticks([])
            ax.set_yticks([])
            if i == j:
                ax.text(0.5, 0.5, "Component\n%d" % (i + 1), ha="center", va="center", fontsize=9, transform=ax.transAxes)
            elif i > j:
                ax.plot(P[:, j], P[:, i], "o", ms=1.2, color=GREEN, rasterized=True)
            else:
                ax.plot(S[:, j], S[:, i], "o", ms=1.2, color=RED, rasterized=True)
                ax.plot(S[hl, j], S[hl, i], "o", ms=2.6, color=BLUE)
    fig.text(0.5, 0.995, "ICA components", ha="center", va="top", fontsize=10)
    fig.text(0.005, 0.5, "PCA components", ha="left", va="center", rotation=90, fontsize=10)
    fig.subplots_adjust(left=0.04, right=0.995, bottom=0.005, top=0.97, wspace=0.05, hspace=0.05)
    savefig(fig, CH, "fig14-39", out_dir)
    return R


def fig_14_40(out_dir=None):
    """The highlighted digits of Figure 14.39: two extreme and two central images per ICA component."""
    R = digits_ica()
    X, picks = R["X"], R["picks"]
    fig, axes = plt.subplots(4, 6, figsize=(6.0, 4.4))
    for r_ in range(4):
        ax = axes[r_, 0]
        if r_ == 0:
            show_digit(ax, X.mean(0))
        else:
            ax.axis("off")
        for j in range(5):
            ext, cen = picks[j]
            show_digit(axes[r_, j + 1], X[(ext + cen)[r_]])
    axes[3, 0].text(0.5, 0.0, "", transform=axes[3, 0].transAxes)
    for j, name in enumerate(["Mean"] + ["ICA %d" % k for k in range(1, 6)]):
        axes[0, j].set_title(name, fontsize=9)
    axes[0, 0].set_ylabel("", fontsize=8)
    fig.text(0.008, 0.72, "extreme", rotation=90, va="center", fontsize=8.5)
    fig.text(0.008, 0.27, "central", rotation=90, va="center", fontsize=8.5)
    fig.subplots_adjust(left=0.04, right=0.995, bottom=0.01, top=0.93, wspace=0.06, hspace=0.06)
    savefig(fig, CH, "fig14-40", out_dir)


# =========================================================================== 14.7.4 product density ICA
def _bspline_setup(lo, hi, nbasis=20, degree=3):
    h = (hi - lo) / (nbasis - degree)
    return lo + h * np.arange(-degree, nbasis + 1)


def fit_tilted_gaussian(s, df=5.0, L=256, nbasis=20, max_newton=30):
    """Step 2(a) of ProDenICA: fit f(s) = phi(s) exp(g(s)) (14.89) to one component by the penalised
    Poisson regression (14.93)-(14.94): bin the s_i into L bins of width Delta, y*_l = count/N, and
    maximise sum_l y*_l [log phi(s*_l) + g(s*_l)] - Delta sum_l phi(s*_l) exp(g(s*_l)) - lam theta^T P theta
    with g = B theta a cubic B-spline with equally spaced knots and P the third-difference penalty
    (whose null space is the quadratics, as for the integrated squared third derivative); lam is set
    at the first Newton step to give df effective degrees of freedom and then held fixed.
    Returns a dict with callables g, g1 (g'), g2 (g'') and the binned fit."""
    s = np.asarray(s, float)
    pad = 0.05 * (s.max() - s.min())
    lo, hi = s.min() - pad, s.max() + pad
    edges = np.linspace(lo, hi, L + 1)
    Delta = edges[1] - edges[0]
    mid = 0.5 * (edges[1:] + edges[:-1])
    y = np.histogram(s, edges)[0] / len(s)
    t = _bspline_setup(lo, hi, nbasis)
    Bm = BSpline.design_matrix(mid, t, 3).toarray()
    D = np.diff(np.eye(nbasis), 3, axis=0)
    P = D.T @ D
    logphi = -0.5 * mid ** 2 - 0.5 * math.log(2 * math.pi)
    theta = np.zeros(nbasis)
    lam = None
    ridge = 1e-9 * np.eye(nbasis)

    def objective(th):
        gg = Bm @ th
        with np.errstate(over="ignore", invalid="ignore"):
            return float(y @ (logphi + gg) - Delta * np.exp(logphi + gg).sum() - lam * th @ P @ th)

    for it in range(max_newton):
        g = Bm @ theta
        mu = Delta * np.exp(logphi + g)
        H = Bm.T @ (mu[:, None] * Bm) + ridge
        if lam is None:
            def dfun(ll):
                return np.trace(linalg.solve(H + 2 * ll * P, H, assume_a="sym"))
            a_, b_ = -8.0, 12.0
            for _ in range(50):
                mid_ = 0.5 * (a_ + b_)
                if dfun(10 ** mid_) > df:
                    a_ = mid_
                else:
                    b_ = mid_
            lam = 10 ** (0.5 * (a_ + b_))
        grad = Bm.T @ (y - mu) - 2 * lam * P @ theta
        step = linalg.solve(H + 2 * lam * P, grad, assume_a="sym")
        f0, h = objective(theta), 1.0
        while objective(theta + h * step) < f0 - 1e-15 and h > 1e-8:   # step halving keeps the ascent
            h /= 2
        theta = theta + h * step
        if np.abs(h * step).max() < 1e-10:
            break
    spl = BSpline(t, theta, 3, extrapolate=True)
    return dict(g=spl, g1=spl.derivative(1), g2=spl.derivative(2), theta=theta, lam=lam, mid=mid,
                y=y, Delta=Delta, mu=Delta * np.exp(logphi + Bm @ theta), logphi=logphi, Bm=Bm, P=P)


def prodenica(Z, n_starts=3, seed=0, df=5.0, max_iter=40, tol=1e-6, A0=None):
    """Product density ICA (Algorithm 14.3): alternate (a) the tilted-Gaussian fits of every component
    and (b) one fixed-point step (14.96) a_j <- E{Z g_j'(a_j^T Z)} - E{g_j''(a_j^T Z)} a_j with symmetric
    orthogonalisation. The start with the largest criterion C(A) of (14.95) is kept.
    Returns (A, S = Z A, iterations)."""
    N, p = Z.shape
    rng = np.random.default_rng(seed)
    starts = [A0] if A0 is not None else [random_orthogonal(p, rng) for _ in range(n_starts)]
    best = None
    for Am in starts:
        Am = sym_orth(Am)
        for it in range(max_iter):
            S = Z @ Am
            fits = [fit_tilted_gaussian(S[:, j], df) for j in range(p)]
            new = np.empty_like(Am)
            for j, f in enumerate(fits):
                new[:, j] = (Z * f["g1"](S[:, j])[:, None]).mean(0) - f["g2"](S[:, j]).mean() * Am[:, j]
            new = sym_orth(new)
            delta = np.abs(1 - np.abs((new * Am).sum(0))).max()
            Am = new
            if delta < tol:
                break
        S = Z @ Am
        C = sum(fit_tilted_gaussian(S[:, j], df)["g"](S[:, j]).mean() for j in range(p))
        if best is None or C > best[0]:
            best = (C, Am, it + 1)
    return best[1], Z @ best[1], best[2]


def _gmix(w, m, sd):
    return (np.array(w, float) / np.sum(w), np.array(m, float), np.array(sd, float))


# The 18 source distributions of Figure 14.42, labelled as in Bach and Jordan (2002): our own parameter
# choices for the Gaussian mixtures (the book does not list them).
ICA_DISTS = {
    "a": ("t", 3), "b": ("laplace", None), "c": ("uniform", None), "d": ("t", 5), "e": ("exponential", None),
    "f": ("laplace_mix", None),
    "g": ("gmix", _gmix([1, 1], [-0.5, 0.5], [0.15, 0.15])),
    "h": ("gmix", _gmix([1, 1], [-0.5, 0.5], [0.4, 0.4])),
    "i": ("gmix", _gmix([1, 1], [-0.5, 0.5], [0.5, 0.5])),
    "j": ("gmix", _gmix([1, 3], [-0.75, 0.35], [0.2, 0.25])),
    "k": ("gmix", _gmix([1, 3], [-0.75, 0.35], [0.45, 0.4])),
    "l": ("gmix", _gmix([1, 3], [-0.75, 0.35], [0.65, 0.6])),
    "m": ("gmix", _gmix([1, 1, 1, 1], [-1.5, -0.5, 0.5, 1.5], [0.15] * 4)),
    "n": ("gmix", _gmix([1, 1, 1, 1], [-1.5, -0.5, 0.5, 1.5], [0.35] * 4)),
    "o": ("gmix", _gmix([1, 1, 1, 1], [-1.5, -0.5, 0.5, 1.5], [0.5] * 4)),
    "p": ("gmix", _gmix([1, 2, 3, 4], [-1.4, -0.4, 0.5, 1.3], [0.15] * 4)),
    "q": ("gmix", _gmix([1, 2, 3, 4], [-1.4, -0.4, 0.5, 1.3], [0.3] * 4)),
    "r": ("gmix", _gmix([1, 2, 3, 4], [-1.4, -0.4, 0.5, 1.3], [0.5] * 4)),
}


def ica_source(name, n, rng):
    kind, par = ICA_DISTS[name]
    if kind == "t":
        x = rng.standard_t(par, n)
    elif kind == "laplace":
        x = rng.laplace(0, 1, n)
    elif kind == "uniform":
        x = rng.uniform(-1, 1, n)
    elif kind == "exponential":
        x = rng.exponential(1, n)
    elif kind == "laplace_mix":
        x = rng.laplace(np.where(rng.uniform(size=n) < 0.5, -2.0, 2.0), 1)
    else:
        w, m, sd = par
        k = rng.choice(len(w), n, p=w)
        x = rng.normal(m[k], sd[k])
    return (x - x.mean()) / x.std()


def ica_density(name, x):
    """Density of the standardised source (for the left panel of Figure 14.42), up to the standardisation
    computed from the exact mean and variance."""
    from scipy import stats
    kind, par = ICA_DISTS[name]
    if kind == "t":
        s = math.sqrt(par / (par - 2))
        return stats.t.pdf(x * s, par) * s
    if kind == "laplace":
        s = math.sqrt(2)
        return 0.5 * np.exp(-np.abs(x * s)) * s
    if kind == "uniform":
        s = 1 / math.sqrt(3)
        return np.where(np.abs(x * s) <= 1, 0.5, 0.0) * s
    if kind == "exponential":
        return np.where(x + 1 >= 0, np.exp(-(x + 1)), 0.0)
    if kind == "laplace_mix":
        s = math.sqrt(2 + 4)
        u = x * s
        return 0.25 * (np.exp(-np.abs(u - 2)) + np.exp(-np.abs(u + 2))) * s
    w, m, sd = par
    mean = (w * m).sum()
    var = (w * (sd ** 2 + m ** 2)).sum() - mean ** 2
    s = math.sqrt(var)
    u = x * s + mean
    return (w[None, :] * np.exp(-0.5 * ((u[:, None] - m) / sd) ** 2) / (sd * math.sqrt(2 * math.pi))).sum(1) * s


def random_mixing(rng):
    """2 x 2 mixing matrix R(t1) diag(1, kappa) R(t2) with condition number kappa ~ U(1, 2)."""
    def rot(t):
        return np.array([[math.cos(t), -math.sin(t)], [math.sin(t), math.cos(t)]])
    return rot(rng.uniform(0, np.pi)) @ np.diag([1.0, rng.uniform(1, 2)]) @ rot(rng.uniform(0, np.pi))


def ica_simulation(nsim=30, n=1024, starts=5, seed=1442):
    """The simulation of Figure 14.42 (reduced): for each distribution, nsim pairs of independent
    sources, a random mixing matrix, whitening, FastICA and ProDenICA with `starts` random starts;
    the Amari distance (14.97) to the orthogonalised true mixing. Cached."""
    path = os.path.join(CACHE_DIR, "ch14_ica_simulation_%d_%d.json" % (nsim, starts))
    if os.path.exists(path):
        with open(path) as f:
            return json.load(f)
    rng = np.random.default_rng(seed)
    out = {}
    for name in ICA_DISTS:
        res = {"FastICA": [], "ProDenICA": []}
        for _ in range(nsim):
            S = np.c_[ica_source(name, n, rng), ica_source(name, n, rng)]
            Amix = random_mixing(rng)
            X = S @ Amix.T
            Z, m, K = whiten(X)
            Mo = sym_orth(Amix.T @ K)            # Z ~ S Mo
            sd = int(rng.integers(1 << 30))
            Af, _, _ = fastica(Z, n_starts=starts, seed=sd)
            Ap, _, _ = prodenica(Z, n_starts=starts, seed=sd)
            res["FastICA"].append(amari(Mo, Af.T))
            res["ProDenICA"].append(amari(Mo, Ap.T))
        out[name] = res
        print("  distribution", name, {k: round(float(np.mean(v)), 4) for k, v in res.items()}, flush=True)
    with open(path, "w") as f:
        json.dump(out, f)
    return out


def fig_14_42(out_dir=None):
    """ProDenICA versus FastICA on 18 source distributions (Figure 14.42, without KernelICA)."""
    res = ica_simulation()
    names = list(ICA_DISTS)
    fig = plt.figure(figsize=(9.0, 4.4))
    gs = fig.add_gridspec(6, 3, left=0.02, right=0.47, bottom=0.12, top=0.95, wspace=0.08, hspace=0.12)
    x = np.linspace(-3.2, 3.2, 801)
    for k, name in enumerate(names):
        r_, c_ = divmod(k, 3)
        ax = fig.add_subplot(gs[r_, c_])
        ax.plot(x, ica_density(name, x), color=GREEN, lw=1.0)
        ax.text(0.04, 0.92, name, transform=ax.transAxes, fontsize=7, va="top")
        ax.set_xticks([])
        ax.set_yticks([])
        ax.set_ylim(bottom=0)
    ax = fig.add_axes([0.57, 0.12, 0.41, 0.83])
    for meth, col, mk in (("FastICA", ORANGE, "o"), ("ProDenICA", GREEN, "s")):
        m = [np.mean(res[n][meth]) for n in names]
        ax.plot(range(18), m, marker=mk, color=col, lw=1.2, ms=4, label=meth)
    ax.set_yscale("log")
    ax.set_xticks(range(18))
    ax.set_xticklabels(names)
    ax.set_xlabel("Distribution")
    ax.set_ylabel("Amari distance from true A")
    ax.legend(fontsize=8, frameon=False)
    savefig(fig, CH, "fig14-42", out_dir)
    return res


# =========================================================================== 14.8 multidimensional scaling
def classical_mds(D, k=2):
    """Classical scaling (14.100) from a distance matrix: B = -1/2 J D^2 J (the centred inner products
    when D is Euclidean), Z = E_k Lambda_k^{1/2} from the k largest eigenpairs (Exercise 14.11)."""
    N = len(D)
    J = np.eye(N) - 1.0 / N
    Bm = -0.5 * J @ (D ** 2) @ J
    vals, E = linalg.eigh((Bm + Bm.T) / 2)
    vals, E = vals[::-1][:k], E[:, ::-1][:, :k]
    idx = np.abs(E).argmax(0)
    E = E * np.sign(E[idx, np.arange(k)])
    return E * np.sqrt(np.maximum(vals, 0)), vals


def fig_14_43(out_dir=None):
    """First two classical MDS coordinates of the half-sphere data (Figure 14.43)."""
    X, g = A.half_sphere()
    Zm, vals = classical_mds(np.sqrt(sqdist(X)), 2)
    fig, ax = plt.subplots(figsize=(4.4, 4.2))
    for k in range(3):
        ax.plot(Zm[g == k, 0], Zm[g == k, 1], "o", ms=3.5, color=A.HS_COLOURS[k])
    ax.set_xlabel("First MDS coordinate")
    ax.set_ylabel("Second MDS coordinate")
    savefig(fig, CH, "fig14-43", out_dir)
    return Zm


# =========================================================================== 14.9 nonlinear dimension reduction
def parabola(n=25, seed=1444):
    r = np.random.default_rng(seed)
    x1 = np.sort(r.uniform(-3.2, 3.2, n))
    return np.c_[x1, -x1 ** 2]


def local_mds_stress(z, D, Nmask, tau):
    """Local MDS stress (14.106) for configuration z (N x k), unordered pairs."""
    Zd = np.sqrt(np.maximum(sqdist(z), 0))
    iu = np.triu_indices(len(z), 1)
    nb = Nmask[iu]
    return float(((D[iu][nb] - Zd[iu][nb]) ** 2).sum() - tau * Zd[iu][~nb].sum())


def local_mds(X, K=2, tau=0.01, k=1, n_starts=30, seed=0):
    """Local multidimensional scaling (Chen and Buja 2008), the stress (14.106) with symmetric K-nearest-
    neighbour pairs N, minimised by L-BFGS from n_starts starts (classical scaling plus random).
    Returns (z, stress)."""
    D = np.sqrt(sqdist(X))
    Nmask = knn_mask(D ** 2, K)
    N = len(X)
    iu = np.triu_indices(N, 1)
    nb = Nmask[iu]

    def f(v):
        z = v.reshape(N, k)
        diff = z[:, None, :] - z[None, :, :]
        dist = np.sqrt((diff ** 2).sum(-1) + 1e-12)
        Wc = np.where(Nmask, -2 * (D - dist) / dist, -tau / dist)
        np.fill_diagonal(Wc, 0)
        val = ((D[iu][nb] - dist[iu][nb]) ** 2).sum() - tau * dist[iu][~nb].sum()
        grad = (Wc[:, :, None] * diff).sum(1)
        return val, grad.ravel()

    rng = np.random.default_rng(seed)
    z0 = classical_mds(D, k)[0]
    starts = [z0] + [rng.standard_normal((N, k)) * z0.std() for _ in range(n_starts - 1)]
    best = None
    for zs in starts:
        r = optimize.minimize(f, zs.ravel(), jac=True, method="L-BFGS-B", options=dict(maxiter=5000))
        if best is None or r.fun < best[1]:
            best = (r.x.reshape(N, k), float(r.fun))
    return best


def fig_14_44(out_dir=None):
    """Classical versus local MDS in one dimension for points on a parabola (Figure 14.44)."""
    from scipy.stats import spearmanr
    X = parabola()
    D = np.sqrt(sqdist(X))
    zc = classical_mds(D, 1)[0][:, 0]
    zl, stress = local_mds(X, K=2, tau=0.01)
    zl = zl[:, 0]
    order = np.arange(len(X))
    rc, rl = abs(spearmanr(zc, order)[0]), abs(spearmanr(zl, order)[0])
    fig, axes = plt.subplots(1, 2, figsize=(7.4, 3.6))
    for ax, z, title in ((axes[0], zc, "Classical MDS"), (axes[1], zl, "Local MDS")):
        z = z - z.mean()
        if np.corrcoef(z, X[:, 0])[0, 1] < 0:
            z = -z
        for i in range(len(X)):
            ax.plot([X[i, 0], z[i]], [X[i, 1], -15], color=GREY, lw=0.6)
        ax.plot(X[:, 0], X[:, 1], "-o", color="#e69f00", ms=4, lw=0.8)
        ax.plot(z, np.full(len(z), -15.0), "-o", color="#56b4e9", ms=4, lw=0.8)
        ax.set_title(title, fontsize=10)
        ax.set_xlabel("$x_1$")
        ax.set_ylabel("$x_2$")
    fig.tight_layout()
    savefig(fig, CH, "fig14-44", out_dir)
    return dict(spearman_classical=rc, spearman_local=rl, stress=stress)


def lle(X, K=12, d=2, reg=1e-3):
    """Local linear embedding (14.102)-(14.104) (Roweis and Saul 2000): affine reconstruction weights
    from the K nearest neighbours (the local Gram matrix regularised by reg x trace, which is needed
    when K > p and harmless otherwise), then the eigenvectors 2, ..., d+1 of M = (I - W)^T (I - W).
    Returns (Y N x d, W)."""
    N = len(X)
    D2 = sqdist(X)
    np.fill_diagonal(D2, np.inf)
    nbr = np.argsort(D2, axis=1)[:, :K]
    W = np.zeros((N, N))
    for i in range(N):
        Zi = X[nbr[i]] - X[i]
        C = Zi @ Zi.T
        C = C + reg * np.trace(C) * np.eye(K) if reg > 0 else C
        w = linalg.solve(C, np.ones(K), assume_a="pos")
        W[i, nbr[i]] = w / w.sum()
    M = (np.eye(N) - W).T @ (np.eye(N) - W)
    vals, E = linalg.eigh(M)
    return E[:, 1:d + 1], W


def isomap(X, K=10, d=2):
    """Isomap (Tenenbaum et al. 2000): K-nearest-neighbour graph with Euclidean edge lengths, geodesic
    distances by shortest paths, then classical scaling. Returns (Y N x d, geodesic distances)."""
    N = len(X)
    D = np.sqrt(sqdist(X))
    order = np.argsort(D + np.diag(np.full(N, np.inf)), axis=1)[:, :K]
    G = np.zeros((N, N))
    rows = np.repeat(np.arange(N), K)
    G[rows, order.ravel()] = D[rows, order.ravel()]
    Dg = shortest_path(sparse.csr_matrix(G), method="D", directed=False)
    return classical_mds(Dg, d)[0], Dg


def compare_lle_isomap_sklearn():
    """Our LLE and Isomap against scikit-learn's (dense eigensolvers) on a Swiss roll: the largest
    coordinate difference after matching signs."""
    from sklearn.datasets import make_swiss_roll
    from sklearn.manifold import Isomap, LocallyLinearEmbedding
    X, t = make_swiss_roll(400, noise=0.05, random_state=0)
    Y, _ = lle(X, K=12, d=2)
    Ys = LocallyLinearEmbedding(n_neighbors=12, n_components=2, reg=1e-3, eigen_solver="dense").fit_transform(X)
    dl = max(min(np.abs(Y[:, j] - Ys[:, j]).max(), np.abs(Y[:, j] + Ys[:, j]).max()) for j in range(2))
    Yi, _ = isomap(X, K=10, d=2)
    Yis = Isomap(n_neighbors=10, n_components=2, eigen_solver="dense", path_method="D").fit_transform(X)
    di = max(min(np.abs(Yi[:, j] - Yis[:, j]).max(), np.abs(Yi[:, j] + Yis[:, j]).max()) for j in range(2))
    return dict(lle_maxdiff=float(dl), isomap_maxdiff=float(di), isomap_scale=float(np.abs(Yis).max()))


def fig_14_45(out_dir=None, K=12):
    """Substitute for Figure 14.45 (the face images are not available): the two-dimensional LLE
    embedding of the 658 zip-code threes, with the images of a few circled points."""
    from matplotlib.offsetbox import AnnotationBbox, OffsetImage
    X = A.zip_threes()
    Y, W = lle(X, K=K, d=2)
    fig, ax = plt.subplots(figsize=(7.2, 6.4))
    ax.plot(Y[:, 0], Y[:, 1], "o", ms=2.0, color=BLUE, alpha=0.7)
    lo, hi = np.percentile(Y, 2, axis=0), np.percentile(Y, 98, axis=0)
    chosen = []
    for a_ in np.linspace(lo[0], hi[0], 3):
        for b_ in np.linspace(lo[1], hi[1], 3):
            i = int(np.argmin(((Y - [a_, b_]) ** 2).sum(1)))
            if i not in chosen:
                chosen.append(i)
    span = Y.max(0) - Y.min(0)
    for i in chosen:
        ax.plot(*Y[i], "o", mfc="none", mec=RED, ms=9, mew=1.2)
        im = OffsetImage(digit_img(X[i]), cmap="gray_r", zoom=1.4, norm=plt.Normalize(-1, 1))
        off = np.sign(Y[i] - Y.mean(0) + 1e-12) * 0.09 * span
        ab = AnnotationBbox(im, Y[i], xybox=Y[i] + off, xycoords="data", boxcoords="data", pad=0.1,
                            arrowprops=dict(arrowstyle="-", color=GREY, lw=0.6))
        ax.add_artist(ab)
    ax.set_xlim(Y[:, 0].min() - 0.18 * span[0], Y[:, 0].max() + 0.18 * span[0])
    ax.set_ylim(Y[:, 1].min() - 0.18 * span[1], Y[:, 1].max() + 0.18 * span[1])
    ax.set_xticks([])
    ax.set_yticks([])
    ax.set_xlabel("First LLE coordinate")
    ax.set_ylabel("Second LLE coordinate")
    savefig(fig, CH, "fig14-45", out_dir)
    return Y


# =========================================================================== 14.10 PageRank
L_14_111 = np.array([[0, 0, 1, 0], [1, 0, 0, 0], [1, 1, 0, 1], [0, 0, 0, 0]], float)
EDGES_14_47 = [(1, 2), (1, 3), (2, 3), (3, 1), (4, 1), (4, 3), (5, 3), (6, 2), (6, 5)]   # j -> i


def link_matrix(edges, N):
    """L_ij = 1 if page j points to page i (pages numbered from 1)."""
    L = np.zeros((N, N))
    for j, i in edges:
        L[i - 1, j - 1] = 1.0
    return L


def pagerank_matrix(L, d=0.85):
    """A = (1 - d) e e^T / N + d L D_c^{-1} of (14.109). A page without out-links (c_j = 0) is treated as
    linking to every page (its column of L D_c^{-1} becomes e / N), so that every column sums to one."""
    N = len(L)
    c = L.sum(0)
    P = np.where(c > 0, L / np.where(c > 0, c, 1), 1.0 / N)
    return (1 - d) * np.ones((N, N)) / N + d * P


def pagerank(L, d=0.85, tol=1e-12, version="book", max_iter=10000, p0=None):
    """Power method (14.110): p <- A p, then p <- N p / e^T p (version 'book', average PageRank 1) or
    p <- p / e^T p (version 'surfer', the stationary distribution of the random surfer, which is the
    book solution divided by N). Returns (p, number of iterations)."""
    N = len(L)
    Am = pagerank_matrix(L, d)
    scale = N if version == "book" else 1.0
    p = np.ones(N) * scale / N if p0 is None else np.asarray(p0, float)
    for it in range(1, max_iter + 1):
        q = Am @ p
        q = scale * q / q.sum()
        if np.abs(q - p).max() < tol:
            return q, it
        p = q
    return p, max_iter


def pagerank_direct(L, d=0.85):
    """Two direct solutions: the linear system (14.108) p = (1 - d) e + d L D_c^{-1} p, and the
    eigenvector of A for the eigenvalue 1 scaled to e^T p = N. Returns (p_linear, p_eigen, eigenvalues of A)."""
    N = len(L)
    c = L.sum(0)
    P = np.where(c > 0, L / np.where(c > 0, c, 1), 1.0 / N)
    p_lin = linalg.solve(np.eye(N) - d * P, (1 - d) * np.ones(N))
    vals, vecs = linalg.eig(pagerank_matrix(L, d))
    k = int(np.argmin(np.abs(vals - 1)))
    v = np.real(vecs[:, k])
    return p_lin, N * v / v.sum(), vals


def _draw_network(ax, pos, edges, p, curved=()):
    from matplotlib.patches import FancyArrowPatch, FancyBboxPatch
    for k, (x, y) in pos.items():
        ax.add_patch(FancyBboxPatch((x - 0.085, y - 0.055), 0.17, 0.11, boxstyle="round,pad=0.01",
                                    fc="#eef3fb", ec="#4a78b5", lw=1.0))
        ax.text(x, y + 0.018, "Page %d" % k, ha="center", va="center", fontsize=9, weight="bold")
        ax.text(x, y - 0.024, "p = %.2f" % p[k - 1], ha="center", va="center", fontsize=8.5)
    for j, i in edges:
        rad = 0.25 if (j, i) in curved else 0.0
        ax.add_patch(FancyArrowPatch(pos[j], pos[i], arrowstyle="-|>", mutation_scale=12, color=BLUE, lw=1.2,
                                     shrinkA=24, shrinkB=24, connectionstyle="arc3,rad=%g" % rad))
    ax.set_xlim(0, 1)
    ax.set_ylim(0, 1)
    ax.set_aspect("equal")
    ax.axis("off")


def fig_14_46(out_dir=None):
    """The four-page network of Figure 14.46 with its PageRanks (power method, d = 0.85)."""
    p, it = pagerank(L_14_111, 0.85)
    pos = {1: (0.18, 0.78), 2: (0.70, 0.88), 3: (0.42, 0.25), 4: (0.86, 0.45)}
    edges = [(j + 1, i + 1) for i, j in zip(*np.nonzero(L_14_111))]
    fig, ax = plt.subplots(figsize=(5.0, 4.0))
    _draw_network(ax, pos, edges, p, curved={(1, 2), (2, 3), (3, 1), (4, 3)})
    savefig(fig, CH, "fig14-46", out_dir)
    return p, it


def fig_14_47(out_dir=None):
    """The six-page network of Exercise 14.22 (Figure 14.47) with its PageRanks (d = 0.85)."""
    L = link_matrix(EDGES_14_47, 6)
    p, it = pagerank(L, 0.85)
    pos = {1: (0.22, 0.86), 2: (0.80, 0.74), 3: (0.50, 0.52), 4: (0.16, 0.22), 5: (0.56, 0.14), 6: (0.86, 0.40)}
    fig, ax = plt.subplots(figsize=(5.0, 4.4))
    _draw_network(ax, pos, EDGES_14_47, p, curved={(1, 3), (3, 1)})
    savefig(fig, CH, "fig14-47", out_dir)
    return p, it


# =========================================================================== exercises
def som_1d(X, K=20, passes=40, alpha0=1.0, R0=None, seed=0):
    """Online self-organising map with K prototypes on a line (Section 14.4, update (14.46)):
    prototypes start on the first principal component; for each observation (random order) the closest
    prototype j and its neighbours |k - j| <= r move by m_k += alpha (x - m_k); alpha decreases
    linearly from alpha0 to 0 and r from R0 to 1. Returns (prototypes K x p, assignment)."""
    X = np.asarray(X, float)
    rng = np.random.default_rng(seed)
    xbar, U, d, V = A.pca(X)
    sc = (X - xbar) @ V[:, 0]
    M = xbar + np.linspace(sc.min(), sc.max(), K)[:, None] * V[:, 0]
    R0 = R0 if R0 is not None else K / 3
    T = passes * len(X)
    t = 0
    for _ in range(passes):
        for i in rng.permutation(len(X)):
            frac = t / T
            alpha, r = alpha0 * (1 - frac), R0 + (1 - R0) * frac
            j = int(((M - X[i]) ** 2).sum(1).argmin())
            nb = np.abs(np.arange(K) - j) <= r
            M[nb] += alpha * (X[i] - M[nb])
            t += 1
    lab = sqdist(X, M).argmin(1)
    return M, lab


def factor_analysis(X, q=1, n_starts=10, seed=0):
    """Maximum-likelihood factor analysis (14.80)-(14.81), Sigma = A A^T + D_eps: for given uniquenesses
    psi the best loadings are A = Psi^{1/2} E (Lambda - I)_+^{1/2} from the q largest eigenpairs of
    Psi^{-1/2} S Psi^{-1/2}; the profile log-likelihood is maximised over log psi by L-BFGS from several
    starts (psi may approach 0: a Heywood case). Returns (A p x q, psi, log-likelihood per observation)."""
    Xc = X - X.mean(0)
    S = Xc.T @ Xc / len(X)
    p = S.shape[0]
    v = np.diag(S)

    def model(lp):
        psi = np.exp(lp)
        r = 1 / np.sqrt(psi)
        vals, E = linalg.eigh(r[:, None] * S * r[None, :])
        vals, E = vals[::-1][:q], E[:, ::-1][:, :q]
        Am = np.sqrt(psi)[:, None] * E * np.sqrt(np.maximum(vals - 1, 0))
        return Am, psi

    def negll(lp):
        Am, psi = model(lp)
        Sig = Am @ Am.T + np.diag(psi)
        sign, ld = np.linalg.slogdet(Sig)
        return 0.5 * (ld + np.trace(linalg.solve(Sig, S, assume_a="pos")) + p * math.log(2 * math.pi))

    rng = np.random.default_rng(seed)
    best = None
    lo = np.log(1e-8 * v)
    for k in range(n_starts):
        lp0 = np.log(v * (0.5 if k == 0 else rng.uniform(0.05, 1.0, p)))
        r = optimize.minimize(negll, lp0, method="L-BFGS-B", bounds=list(zip(lo, np.log(v * 1.0001))))
        if best is None or r.fun < best.fun:
            best = r
    Am, psi = model(best.x)
    return Am, psi, -float(best.fun)


def helix(n=200, seed=1413):
    r = np.random.default_rng(seed)
    s = np.linspace(0, 2 * np.pi, n)
    return np.c_[np.cos(s), np.sin(s), s] + 0.1 * r.standard_normal((n, 3)), s


def exercises():
    """Numbers quoted in the solutions of Exercises 14.12-14.25 (part B)."""
    from scipy.stats import spearmanr
    out = {}
    rng = np.random.default_rng(14)
    # 14.12: the Procrustes step and sparse PCA with lambda_1 = 0
    M = rng.standard_normal((8, 3))
    Th = procrustes_theta(M)
    best_rand = max(np.trace(linalg.qr(rng.standard_normal((8, 3)), mode="economic")[0].T @ M) for _ in range(5000))
    X3 = A.zip_threes()
    Vs, _, its = sparse_pca(X3, K=3, lam2=1e-6, lam1=0.0)
    _, _, _, Vp = A.pca(X3)
    out["14.12"] = dict(trace_opt=float(np.trace(Th.T @ M)), sum_sv=float(linalg.svdvals(M).sum()),
                        best_random=float(best_rand), spca_lam1_0_abs_cos=[float(abs(Vs[:, k] @ Vp[:, k])) for k in range(3)])
    # 14.13: helix, principal curve and a one-dimensional SOM
    X, s = helix()
    pc = principal_curve(X, span=0.08)
    lam = pc["lam"]
    sh = lam / lam.max() * 2 * np.pi
    if np.corrcoef(sh, s)[0, 1] < 0:
        sh = 2 * np.pi - sh
    seg = pc["curve"]
    cum = np.r_[0, np.cumsum(np.sqrt((np.diff(seg, axis=0) ** 2).sum(1)))]
    fhat = np.array([np.interp(lam, cum, seg[:, j]) for j in range(3)]).T
    rmse = np.sqrt(((fhat - np.c_[np.cos(s), np.sin(s), s]) ** 2).mean(0))
    Msom, lab = som_1d(X, K=20)
    ms = np.array([s[lab == k].mean() if (lab == k).any() else np.nan for k in range(20)])
    ok = ~np.isnan(ms)
    out["14.13"] = dict(curve_rmse_cos_sin_s=rmse.tolist(), spearman_lambda_s=float(spearmanr(lam, s)[0]),
                        D2=float(pc["D2"][-1]), iterations=len(pc["D2"]),
                        som_spearman_index_s=float(abs(spearmanr(np.arange(20)[ok], ms[ok])[0])),
                        som_rss=float(((X - Msom[lab]) ** 2).sum()))
    # 14.15: PCA versus factor analysis
    from sklearn.decomposition import FactorAnalysis
    Zs = np.random.default_rng(1415).standard_normal((200, 3))
    Xf = np.c_[Zs[:, 0], Zs[:, 0] + 0.001 * Zs[:, 1], 10 * Zs[:, 2]]
    _, _, _, Vf = A.pca(Xf)
    Af, psi, ll = factor_analysis(Xf, 1)
    load = Af[:, 0] * np.sign(Af[0, 0])
    fa = FactorAnalysis(n_components=1).fit(Xf)
    out["14.15"] = dict(pc1=Vf[:, 0].tolist(), fa_loading=load.tolist(), fa_uniquenesses=psi.tolist(), fa_loglik=ll,
                        fa_direction=(load / linalg.norm(load)).tolist(),
                        sklearn_loglik=float(fa.score(Xf)), sklearn_loading=fa.components_[0].tolist())
    # 14.16-14.17: kernel PCA, training components and new points against scikit-learn
    from sklearn.decomposition import KernelPCA
    Xr, g = rings()
    Xa, Xb = Xr[::3], Xr[1::3][:50]
    c = 2.0
    K = np.exp(-sqdist(Xa) / c)
    vals, U, Zk, alpha = kernel_pca(K, 2)
    Jc = np.eye(len(K)) - 1 / len(K)
    z_from_alpha = (Jc @ K @ Jc) @ alpha
    znew = kernel_pca_project(np.exp(-sqdist(Xb, Xa) / c), K, alpha)
    sk = KernelPCA(n_components=2, kernel="rbf", gamma=1 / c, eigen_solver="dense").fit(Xa)
    sknew = sk.transform(Xb)
    diffnew = max(min(np.abs(znew[:, j] - sknew[:, j]).max(), np.abs(znew[:, j] + sknew[:, j]).max()) for j in range(2))
    out["14.16"] = dict(rank_K=int(np.linalg.matrix_rank(Jc @ K @ Jc)), z_eq_UD=float(np.abs(z_from_alpha - Zk).max()),
                        new_vs_sklearn=float(diffnew))
    # 14.18: moment conditions of the tilted Gaussian fit
    s1 = ica_source("e", 1024, np.random.default_rng(1418))
    f = fit_tilted_gaussian(s1)
    out["14.18"] = dict(mass=float(f["mu"].sum()), mean_fit=float(f["mu"] @ f["mid"]), mean_bins=float(f["y"] @ f["mid"]),
                        m2_fit=float(f["mu"] @ f["mid"] ** 2), m2_bins=float(f["y"] @ f["mid"] ** 2))
    # 14.19: the Gaussian part of the log-likelihood does not depend on the orthogonal A
    Z, _, _ = whiten(np.c_[s1, ica_source("c", 1024, np.random.default_rng(1419))])
    vals19 = []
    for _ in range(3):
        Q = random_orthogonal(2, rng)
        vals19.append(float((-0.5 * (Z @ Q) ** 2 - 0.5 * math.log(2 * math.pi)).sum()))
    out["14.19"] = vals19
    # 14.20: the Newton step with the approximation E{X X^T g''} ~ E{X X^T} E{g''} is the fixed point (14.96)
    a = random_orthogonal(2, rng)[:, 0]
    y = Z @ a
    gp, gpp = np.tanh(y), 1 - np.tanh(y) ** 2
    beta = (y * gp).mean()
    newton = a - ((Z * gp[:, None]).mean(0) - beta * a) / (gpp.mean() - beta)
    fixed = (Z * gp[:, None]).mean(0) - gpp.mean() * a
    out["14.20"] = float(1 - abs(newton @ fixed) / (linalg.norm(newton) * linalg.norm(fixed)))
    # 14.21: Laplacian of a graph with three connected components
    Xg = np.r_[rng.normal(0, 0.3, (15, 2)), rng.normal(5, 0.3, (12, 2)), rng.normal([0, 6], 0.3, (10, 2))]
    W = np.exp(-sqdist(Xg))
    lab = np.repeat([0, 1, 2], [15, 12, 10])
    W *= lab[:, None] == lab[None, :]
    np.fill_diagonal(W, 0)
    vals21, vecs21 = linalg.eigh(graph_laplacian(W))
    Ind = np.eye(3)[lab]
    P = Ind @ linalg.pinv(Ind)
    out["14.21"] = dict(smallest=vals21[:5].tolist(), n_zero=int((vals21 < 1e-10).sum()),
                        span_residual=float(np.abs(vecs21[:, :3] - P @ vecs21[:, :3]).max()))
    # 14.22: PageRank of the six-page network
    L = link_matrix(EDGES_14_47, 6)
    p, it = pagerank(L, 0.85)
    p_lin, p_eig, _ = pagerank_direct(L, 0.85)
    out["14.22"] = dict(p=p.tolist(), iterations=it, sum_linear=float(p_lin.sum()), max_diff_eig=float(np.abs(p - p_eig).max()))
    # 14.23-14.25: NMF
    X2 = A.zip_class(2) + 1.0
    _, _, tr = nmf_kl(X2[:200], 10, iters=100, seed=23, trace=True)
    Xs = rng.uniform(0, 5, (6, 5))
    W1, H1, _ = nmf_kl(Xs, 1, iters=1, seed=24)
    closed = np.outer(Xs.sum(1), Xs.sum(0)) / Xs.sum()
    W25, H25, _ = nmf_kl(X2, 25, iters=500, seed=25)
    xbar = X2.mean(0)
    sv = linalg.svdvals(X2 - xbar)
    out["14.23"] = dict(min_increase=float(np.diff(tr).min()), L_first=float(tr[0]), L_last=float(tr[-1]))
    out["14.24"] = dict(max_diff_after_one_sweep=float(np.abs(W1 @ H1 - closed).max()))
    out["14.25"] = dict(nmf25_rss=float(((X2 - W25 @ H25) ** 2).sum()), pca24_mean_rss=float((sv[24:] ** 2).sum()),
                        total_ss=float((sv ** 2).sum()), n=len(X2))
    return out


def pagerank_table():
    """PageRanks of both networks for d in (0.5, 0.85, 0.95), book and random-surfer scalings."""
    out = {}
    for name, L in (("fig14_46", L_14_111), ("fig14_47", link_matrix(EDGES_14_47, 6))):
        for d in (0.5, 0.85, 0.95):
            for v in ("book", "surfer"):
                p, it = pagerank(L, d, version=v)
                out["%s d=%g %s" % (name, d, v)] = ([round(float(x), 6) for x in p], it)
    return out


def export_demo_data():
    export_rings_json()
    export_twos_json()


# =========================================================================== driver
FIGURES = {
    "14.27": fig_14_27, "14.28": fig_14_28, "14.29": fig_14_29, "14.30": fig_14_30, "14.31": fig_14_31,
    "14.33": fig_14_33, "14.34": fig_14_34, "14.35": fig_14_35, "14.36": fig_14_36, "14.37": fig_14_37,
    "14.38": fig_14_38, "14.39": fig_14_39, "14.40": fig_14_40, "14.42": fig_14_42, "14.43": fig_14_43,
    "14.44": fig_14_44, "14.45": fig_14_45, "14.46": fig_14_46, "14.47": fig_14_47,
}


if __name__ == "__main__":
    import sys
    if "--demo-data" in sys.argv:
        export_demo_data()
    else:
        common.run(FIGURES, CH)
