{
 "nbformat": 4,
 "nbformat_minor": 5,
 "metadata": {
  "kernelspec": {
   "name": "python3",
   "display_name": "Python 3",
   "language": "python"
  },
  "language_info": {
   "name": "python"
  },
  "colab": {
   "name": "randomprojection.ipynb"
  }
 },
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "# random projection \u2014 Python demo\n\nNumerical companion to the entry [random projection](https://dictionaryofml.org/terms/randomprojection.html) of the [Dictionary of Applied Machine Learning](https://dictionaryofml.org/): it recomputes what the entry states and prints one line per check.\n\nNumerical companion to the glossary entry 'randomprojection'. Each data point is one day at Krems an der Donau (GeoSphere station 3805); its feature vector holds the daily maximum temperatures of the days up to and including it. Two window lengths give two ambient dimensions for the same m = 256 days: one year of daily maxima (d = 365) and ten years of them (d = 3650).\n\nRequires NumPy and Matplotlib only, and uses fixed seeds, so the printed numbers reproduce exactly. Generated from [`pythondemos/randomprojection.py`](https://dictionaryofml.org/terms/randomprojection.py); CC BY 4.0.\n\nBefore running a downloaded copy, scan it: `uvx bandit -q -t B102,B307,B602,B605 randomprojection.py` (B102,B307,B602,B605 are the exec, eval and shell checks of [bandit](https://bandit.readthedocs.io/)) reports nothing: the script runs no shell command and evaluates no generated code."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "# Notebook shim: the script resolves output paths relative to __file__,\n# which a notebook kernel does not define; everything lands in the\n# working directory instead.\nimport os\n__file__ = os.path.join(os.getcwd(), \"randomprojection.py\")\nos.makedirs(\"pythondemos\", exist_ok=True)"
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "\"\"\"A random projection of Krems an der Donau weather records: how much the\npairwise Euclidean distances change, and what the Johnson-Lindenstrauss\nlemma guarantees.\n\nPurpose\n-------\nNumerical companion to the glossary entry 'randomprojection'.  Each data\npoint is one day at Krems an der Donau (GeoSphere station 3805); its\nfeature vector holds the daily maximum temperatures of the days up to and\nincluding it.  Two window lengths give two ambient dimensions for the same\nm = 256 days: one year of daily maxima (d = 365) and ten years of them\n(d = 3650).\n\nEvery feature vector is multiplied by a random matrix A of d' rows whose\nentries are realizations of i.i.d. normal random variables with mean zero\nand variance 1/d'.  The demo checks the identity the entry derives,\nE{||A u||^2} = ||u||^2, and then measures, for each target dimension d',\nthe relative change of all 32640 pairwise squared distances of the 256\ndays.  The measured change is compared with the tolerance the\nJohnson-Lindenstrauss lemma guarantees for that d', which involves the\nnumber m of data points and not the ambient dimension d -- and the two\nambient dimensions, a factor of ten apart, indeed need the same d'.\n\nSelf-contained (numpy and matplotlib only), fixed seeds; the GeoSphere\ndownload falls back to the committed CSV.\n\nBlocks\n------\n[B-data]     Daily maximum temperature at Krems for 2005-2024 (7305 days,\n             no missing value).\n[B-points]   The m = 256 days, each with a one-year feature vector\n             (d = 365) and a ten-year one (d = 3650).\n[B-expect]   The identity E{||A u||^2} = ||u||^2 for a random matrix with\n             i.i.d. entries of mean zero and variance 1/d', checked\n             against the average over many draws.\n[B-bound]    The Johnson-Lindenstrauss target dimension\n             4 ln(m) / (eps^2/2 - eps^3/3) and the floor 24 ln(m) below\n             which no tolerance eps < 1 is reachable.\n[B-distort]  The relative change of the 32640 pairwise squared distances\n             for d' = 144, ..., 320, over 40 draws of A, for both ambient\n             dimensions, against the guaranteed tolerance.\n[B-storage]  The application: at d' = 256 a ten-year record shrinks from\n             3650 numbers to 256 while no pairwise distance changes by\n             more than the reported fraction.\n\nOutputs\n-------\nrandomprojection_weather.csv    : date, tmax for 2005-2024 (committed).\nrandomprojection_distortion.csv : dprime, the guaranteed tolerance eps,\n                                  and the median / 95th percentile /\n                                  largest relative change of the pairwise\n                                  squared distances, for both ambient\n                                  dimensions.\nrandomprojection.png            : matplotlib preview (checking only).\n\"\"\"\n\n# /// script\n# requires-python = \">=3.10\"\n# dependencies = [\"matplotlib==3.10.7\", \"numpy==2.3.4\"]\n# ///\n\nimport json\nimport math\nimport urllib.request\nfrom pathlib import Path\n\nimport numpy as np\nimport matplotlib\n\nmatplotlib.use(\"Agg\")\nimport matplotlib.pyplot as plt\n\nOUT_DIR = Path(__file__).parent\n\nSAMPLESIZE = 256                 # m, the number of days compared\nSTRIDE = 14                      # days between two consecutive data points\nSHORT, LONG = 365, 3650          # the two ambient dimensions d\nDIMS = [144, 176, 208, 240, 256, 288, 320]        # target dimensions d'\nDRAWS = 40                       # independent draws of A per target dimension\nDELTA = 0.05                     # failure probability allowed in the check\n\nreport = []\n\n\ndef check(name, ok):\n    report.append((name, bool(ok)))\n    print(f\"  [{'ok' if ok else 'FAIL'}] {name}\")"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-data]** Daily maximum temperature at Krems for 2005-2024 (7305 days, no missing value)."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[B-data] daily maximum temperature at Krems an der Donau, 2005-2024\")\nURL = (\"https://dataset.api.hub.geosphere.at/v1/station/historical/\"\n       \"klima-v2-1d?parameters=tlmax&station_ids=3805\"\n       \"&start=2005-01-01&end=2024-12-31\")\nCSV = OUT_DIR / \"randomprojection_weather.csv\"\ntry:\n    with urllib.request.urlopen(URL, timeout=180) as resp:\n        payload = json.load(resp)\n    params = payload[\"features\"][0][\"properties\"][\"parameters\"]\n    records = [(stamp[:10], hi)\n               for stamp, hi in zip(payload[\"timestamps\"],\n                                    params[\"tlmax\"][\"data\"])]\n    with open(CSV, \"w\") as fh:\n        fh.write(\"date,tmax\\n\")\n        for day, hi in records:\n            fh.write(f\"{day},{hi}\\n\")\n    print(f\"    downloaded {len(records)} days\")\nexcept OSError as err:\n    print(f\"    download failed ({err}); reading the committed CSV\")\n    rows = CSV.read_text().strip().splitlines()[1:]\n    records = [(d, float(v)) for d, v in (r.split(\",\") for r in rows)]\n\ncheck(\"[B-data] 7305 days for 2005-2024\", len(records) == 7305)\ncheck(\"[B-data] no day is missing its maximum temperature\",\n      all(hi is not None for _, hi in records))\ntmax = np.array([hi for _, hi in records], dtype=float)\ndates = [d for d, _ in records]"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-points]** The m = 256 days, each with a one-year feature vector (d = 365) and a ten-year one (d = 3650)."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[B-points] the 256 days, with a one-year and a ten-year window\")\nends = LONG - 1 + np.arange(SAMPLESIZE) * STRIDE\ncheck(f\"[B-points] the {SAMPLESIZE} days run from {dates[ends[0]]} to \"\n      f\"{dates[ends[-1]]}, every {STRIDE}th day\", ends[-1] < len(tmax))\n\n\ndef windows(length):\n    \"\"\"Feature vectors: the `length` daily maxima up to each chosen day.\"\"\"\n    return np.stack([tmax[e - length + 1:e + 1] for e in ends])\n\n\nX = {SHORT: windows(SHORT), LONG: windows(LONG)}\ncheck(f\"[B-points] feature matrices of shape {X[SHORT].shape} and \"\n      f\"{X[LONG].shape}\",\n      X[SHORT].shape == (SAMPLESIZE, SHORT)\n      and X[LONG].shape == (SAMPLESIZE, LONG))\ncheck(\"[B-points] the one-year window is the tail of the ten-year one\",\n      np.allclose(X[LONG][:, -SHORT:], X[SHORT]))\niu = np.triu_indices(SAMPLESIZE, 1)\nNPAIRS = len(iu[0])\nsqdist = {d: np.sum((Z[iu[0]] - Z[iu[1]]) ** 2, axis=1) for d, Z in X.items()}\ncheck(f\"[B-points] {NPAIRS} pairs of days, every squared distance positive\",\n      NPAIRS == SAMPLESIZE * (SAMPLESIZE - 1) // 2\n      and min(sqdist[SHORT].min(), sqdist[LONG].min()) > 0)\n\n\ndef projection(dprime, d, rng):\n    \"\"\"A random matrix of d' rows with i.i.d. N(0, 1/d') entries.\"\"\"\n    return rng.standard_normal((dprime, d)) / math.sqrt(dprime)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-expect]** The identity E{||A u||^2} = ||u||^2 for a random matrix with i.i.d. entries of mean zero and variance 1/d', checked against the average over many draws."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[B-expect] the expected squared length is preserved exactly\")\nrng = np.random.default_rng(20261119)\nu = X[SHORT][0] - X[SHORT][7]\nusq = float(u @ u)\nlengths = [float(np.sum((projection(16, SHORT, rng) @ u) ** 2))\n           for _ in range(4000)]\navg = float(np.mean(lengths))\ncheck(f\"[B-expect] squared length {usq:.1f}, average of 4000 draws with \"\n      f\"d' = 16: {avg:.1f} ({100 * (avg / usq - 1):+.1f} percent)\",\n      abs(avg / usq - 1) < 0.02)\ncheck(f\"[B-expect] a single draw is far off: the 4000 draws range from \"\n      f\"{min(lengths) / usq:.2f} to {max(lengths) / usq:.2f} times the \"\n      f\"squared length\", min(lengths) / usq < 0.5 < 1.5 < max(lengths) / usq)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-bound]** The Johnson-Lindenstrauss target dimension 4 ln(m) / (eps^2/2 - eps^3/3) and the floor 24 ln(m) below which no tolerance eps < 1 is reachable."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[B-bound] the target dimension the lemma asks for\")\n\n\ndef jl_dim(eps, m):\n    \"\"\"4 ln(m) / (eps^2/2 - eps^3/3), the lemma's lower bound on d'.\"\"\"\n    return 4 * math.log(m) / (eps ** 2 / 2 - eps ** 3 / 3)\n\n\ndef jl_eps(dprime, m):\n    \"\"\"The smallest tolerance eps < 1 the lemma grants at d' = dprime.\"\"\"\n    if dprime < 24 * math.log(m):\n        return float(\"nan\")\n    lo, hi = 1e-9, 1.0\n    for _ in range(200):\n        mid = 0.5 * (lo + hi)\n        if jl_dim(mid, m) > dprime:\n            lo = mid\n        else:\n            hi = mid\n    return hi\n\n\nfloor = 24 * math.log(SAMPLESIZE)\ncheck(f\"[B-bound] the denominator is largest at eps = 1, where it is 1/6, \"\n      f\"so no eps < 1 is reachable below 24 ln(m) = {floor:.1f}\",\n      abs(jl_dim(1.0, SAMPLESIZE) - floor) < 1e-9)\ncheck(f\"[B-bound] eps = 1/2 asks for d' >= {jl_dim(0.5, SAMPLESIZE):.0f}, \"\n      f\"eps = 1/4 for d' >= {jl_dim(0.25, SAMPLESIZE):.0f}\",\n      jl_dim(0.25, SAMPLESIZE) > jl_dim(0.5, SAMPLESIZE) > floor)\ncheck(f\"[B-bound] the bound grows only with ln(m): {SAMPLESIZE} days ask \"\n      f\"for d' >= {jl_dim(0.5, SAMPLESIZE):.0f} at eps = 1/2, \"\n      f\"{100 * SAMPLESIZE} days for d' >= \"\n      f\"{jl_dim(0.5, 100 * SAMPLESIZE):.0f}\",\n      jl_dim(0.5, 100 * SAMPLESIZE) < 2 * jl_dim(0.5, SAMPLESIZE))"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-distort]** The relative change of the 32640 pairwise squared distances for d' = 144, ..., 320, over 40 draws of A, for both ambient dimensions, against the guaranteed tolerance."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[B-distort] relative change of the 32640 pairwise squared distances\")\nstats = {}\nfor dprime in DIMS:\n    for d in (SHORT, LONG):\n        rng = np.random.default_rng(31415 + dprime)\n        med, p95, largest = [], [], []\n        for _ in range(DRAWS):\n            Z = X[d] @ projection(dprime, d, rng).T\n            after = np.sum((Z[iu[0]] - Z[iu[1]]) ** 2, axis=1)\n            rel = np.abs(after / sqdist[d] - 1)\n            med.append(np.median(rel))\n            p95.append(np.percentile(rel, 95))\n            largest.append(rel.max())\n        stats[(dprime, d)] = (float(np.median(med)), float(np.median(p95)),\n                              float(np.median(largest)),\n                              float(np.mean(np.array(largest)\n                                            < jl_eps(dprime, SAMPLESIZE))))\n    eps = jl_eps(dprime, SAMPLESIZE)\n    s_short, s_long = stats[(dprime, SHORT)], stats[(dprime, LONG)]\n    check(f\"[B-distort] d' = {dprime:3d}: guaranteed {eps:.2f}; largest \"\n          f\"change {s_long[2]:.2f} (d = {LONG}) and {s_short[2]:.2f} \"\n          f\"(d = {SHORT}); median {s_long[0]:.3f}\",\n          s_long[2] < eps and s_short[2] < eps)\n\nheld = min(stats[(dp, d)][3] for dp in DIMS for d in (SHORT, LONG))\ncheck(f\"[B-distort] the guarantee held in at least \"\n      f\"{100 * held:.0f} percent of the {DRAWS} draws at every target \"\n      f\"dimension, above the {100 * (1 - DELTA):.0f} percent the lemma \"\n      f\"promises\", held >= 1 - DELTA)\ngaps = [abs(stats[(dp, LONG)][2] - stats[(dp, SHORT)][2]) for dp in DIMS]\ncheck(f\"[B-distort] a tenfold larger ambient dimension changes the largest \"\n      f\"change by at most {max(gaps):.3f}\", max(gaps) < 0.05)"
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": "**[B-storage]** The application: at d' = 256 a ten-year record shrinks from 3650 numbers to 256 while no pairwise distance changes by more than the reported fraction."
  },
  {
   "cell_type": "code",
   "metadata": {},
   "execution_count": null,
   "outputs": [],
   "source": "print(\"[B-storage] a ten-year record kept as 256 numbers\")\nmed, p95, largest, _ = stats[(256, LONG)]\ncheck(f\"[B-storage] d' = 256 shrinks a ten-year record from {LONG} numbers \"\n      f\"to 256, a factor of {LONG / 256:.1f}\", LONG / 256 > 14)\ncheck(f\"[B-storage] no pairwise distance changes by more than \"\n      f\"{100 * largest:.0f} percent, half change by less than \"\n      f\"{100 * med:.0f} percent, and nineteen of twenty by less than \"\n      f\"{100 * p95:.0f} percent\", 0 < med < p95 < largest)\n\n# ---- CSV and preview\nwith open(OUT_DIR / \"randomprojection_distortion.csv\", \"w\") as fh:\n    fh.write(\"dprime,eps,med_short,p95_short,max_short,\"\n             \"med_long,p95_long,max_long\\n\")\n    for dprime in DIMS:\n        a, b, c, _ = stats[(dprime, SHORT)]\n        e, f, g, _ = stats[(dprime, LONG)]\n        fh.write(f\"{dprime},{jl_eps(dprime, SAMPLESIZE):.4f},\"\n                 f\"{a:.4f},{b:.4f},{c:.4f},{e:.4f},{f:.4f},{g:.4f}\\n\")\n\ngrid = np.array(DIMS, dtype=float)\neps_curve = np.array([jl_eps(dp, SAMPLESIZE) for dp in DIMS])\nfig, (ax1, ax2) = plt.subplots(1, 2, figsize=(9.6, 3.9))\nax1.plot(grid, eps_curve, \"k-.\", lw=1.0,\n         label=\"tolerance guaranteed by the JL lemma\")\nax1.plot(grid, [stats[(dp, LONG)][2] for dp in DIMS], \"k:\", marker=\"^\",\n         mfc=\"none\", ms=4, lw=0.9, label=\"largest change over the pairs\")\nax1.plot(grid, [stats[(dp, LONG)][1] for dp in DIMS], \"k--\", marker=\"s\",\n         mfc=\"none\", ms=4, lw=0.9, label=\"95th percentile\")\nax1.plot(grid, [stats[(dp, LONG)][0] for dp in DIMS], \"k-\", marker=\"o\",\n         ms=4, lw=0.9, label=\"median\")\nax1.set_ylim(0, 1.0)\nax1.set_xlabel(\"target dimension d'\")\nax1.set_ylabel(\"relative change of a squared distance\")\nax1.set_title(\"ten-year records (d = 3650): change against d'\")\nax1.legend(frameon=False, fontsize=8)\nax2.plot(grid, [stats[(dp, SHORT)][2] for dp in DIMS], \"k-\", marker=\"o\",\n         ms=4, lw=0.9, label=\"d = 365 (one year)\")\nax2.plot(grid, [stats[(dp, LONG)][2] for dp in DIMS], \"k--\", marker=\"s\",\n         mfc=\"none\", ms=4, lw=0.9, label=\"d = 3650 (ten years)\")\nax2.set_ylim(0, 0.6)\nax2.set_xlabel(\"target dimension d'\")\nax2.set_ylabel(\"largest relative change\")\nax2.set_title(\"the ambient dimension d does not matter\")\nax2.legend(frameon=False, fontsize=8)\nfig.tight_layout()\nfig.savefig(OUT_DIR / \"randomprojection.png\", dpi=110)\n\nn_ok = sum(ok for _, ok in report)\nprint(f\"\\n{n_ok}/{len(report)} checks pass\")\nif n_ok != len(report):\n    raise SystemExit(1)"
  }
 ]
}