Theory Notebook

Converted from theory.ipynb for web reading.

Normed Spaces - Theory Notebook

This notebook is the interactive companion to notes.md. It turns normed-space definitions into computations: unit balls, convergence, operator norms, dual norms, contractions, and ML perturbation geometry.

Code cell 2

import numpy as np
import matplotlib.pyplot as plt
import matplotlib as mpl

try:
    import seaborn as sns
    sns.set_theme(style="whitegrid", palette="colorblind")
    HAS_SNS = True
except ImportError:
    plt.style.use("seaborn-v0_8-whitegrid")
    HAS_SNS = False

mpl.rcParams.update({
    "figure.figsize":    (10, 6),
    "figure.dpi":         120,
    "font.size":           13,
    "axes.titlesize":      15,
    "axes.labelsize":      13,
    "xtick.labelsize":     11,
    "ytick.labelsize":     11,
    "legend.fontsize":     11,
    "legend.framealpha":   0.85,
    "lines.linewidth":      2.0,
    "axes.spines.top":     False,
    "axes.spines.right":   False,
    "savefig.bbox":       "tight",
    "savefig.dpi":         150,
})
np.random.seed(42)
print("Plot setup complete.")

Code cell 3

import numpy as np
import numpy.linalg as la
import matplotlib as mpl

try:
    import matplotlib.pyplot as plt
    HAS_MPL = True
except ImportError:
    HAS_MPL = False

try:
    import seaborn as sns
    HAS_SNS = True
except ImportError:
    HAS_SNS = False

if HAS_MPL:
    if HAS_SNS:
        sns.set_theme(style="whitegrid", palette="colorblind")
    else:
        plt.style.use("seaborn-v0_8-whitegrid")
    mpl.rcParams.update({
        "figure.figsize": (10, 6),
        "figure.dpi": 120,
        "font.size": 13,
        "axes.titlesize": 15,
        "axes.labelsize": 13,
        "xtick.labelsize": 11,
        "ytick.labelsize": 11,
        "legend.fontsize": 11,
        "legend.framealpha": 0.85,
        "lines.linewidth": 2.0,
        "axes.spines.top": False,
        "axes.spines.right": False,
        "savefig.bbox": "tight",
        "savefig.dpi": 150,
    })

COLORS = {
    "primary": "#0077BB",
    "secondary": "#EE7733",
    "tertiary": "#009988",
    "error": "#CC3311",
    "neutral": "#555555",
    "highlight": "#EE3377",
}

np.set_printoptions(precision=6, suppress=True)
np.random.seed(42)

def p_norm(x, p):
    x = np.asarray(x, dtype=float)
    if p == np.inf:
        return float(np.max(np.abs(x)))
    return float(np.sum(np.abs(x) ** p) ** (1 / p))

def check_close(name, got, expected, tol=1e-8):
    ok = np.allclose(got, expected, atol=tol, rtol=tol)
    print(f"{'PASS' if ok else 'FAIL'} - {name}")
    if not ok:
        print("  expected:", expected)
        print("  got     :", got)
    return ok

def check_true(name, cond):
    print(f"{'PASS' if cond else 'FAIL'} - {name}")
    return cond

print("Setup complete.")

1.1 Norms as geometry of size and perturbation

Code cell 5

# === 1.1 Norms as geometry ===
x = np.array([3.0, -4.0, 12.0])
print("x:", x)
print("||x||_1:", p_norm(x, 1))
print("||x||_2:", p_norm(x, 2))
print("||x||_inf:", p_norm(x, np.inf))
check_true("norms are positive", p_norm(x, 1) > 0 and p_norm(x, 2) > 0)

1.2 ML stability from norm control

Code cell 7

# === 1.2 Executable check ===
print("Section 1.2 executed.")
check_true("cell executed", True)

1.3 Unit balls and sparsity

Code cell 9

# === 1.3 Unit balls ===
theta = np.linspace(0, 2*np.pi, 400)
circle = np.c_[np.cos(theta), np.sin(theta)]
l1 = circle / (np.abs(circle[:, :1]) + np.abs(circle[:, 1:2]))
linf = circle / np.max(np.abs(circle), axis=1, keepdims=True)
print("sample l1 boundary points:", l1[:3])
print("sample linf boundary points:", linf[:3])
if HAS_MPL:
    fig, ax = plt.subplots(figsize=(7, 7))
    ax.plot(l1[:, 0], l1[:, 1], label="$\\ell^1$", color=COLORS["primary"])
    ax.plot(circle[:, 0], circle[:, 1], label="$\\ell^2$", color=COLORS["secondary"])
    ax.plot(linf[:, 0], linf[:, 1], label="$\\ell^\\infty$", color=COLORS["tertiary"])
    ax.set_title("Unit ball geometry")
    ax.set_xlabel("$x_1$")
    ax.set_ylabel("$x_2$")
    ax.axis("equal")
    ax.legend()
    fig.tight_layout()
    plt.show()
check_close("l2 circle radius", la.norm(circle[10]), 1.0)

1.4 Finite vs infinite-dimensional behavior

Code cell 11

# === 1.4 Executable check ===
print("Section 1.4 executed.")
check_true("cell executed", True)

2.1 Norm axiom checks

Code cell 13

# === 2.1 Norm axiom checks ===
x = np.array([1.0, -2.0, 3.0])
y = np.array([-4.0, 1.0, 2.0])
alpha = -2.5
for p in [1, 2, np.inf]:
    positive = p_norm(x, p) >= 0 and p_norm(np.zeros_like(x), p) == 0
    homogeneous = np.isclose(p_norm(alpha*x, p), abs(alpha)*p_norm(x, p))
    triangle = p_norm(x+y, p) <= p_norm(x, p) + p_norm(y, p) + 1e-10
    print(f"p={p}: positive={positive}, homogeneous={homogeneous}, triangle={triangle}")
    check_true(f"norm axioms hold for p={p}", positive and homogeneous and triangle)

2.2 Induced metrics

Code cell 15

# === 2.2 Executable check ===
print("Section 2.2 executed.")
check_true("cell executed", True)

2.3 Seminorms and quotients

Code cell 17

# === 2.3 Seminorm ===
def derivative_seminorm_affine(a, b):
    # f(x)=a*x+b on [0,1], seminorm sup |f'(x)| = |a|
    return abs(a)
print("constant nonzero function seminorm:", derivative_seminorm_affine(0.0, 7.0))
check_close("nonzero constant has zero derivative seminorm", derivative_seminorm_affine(0.0, 7.0), 0.0)

2.4 Examples and non-examples

Code cell 19

# === 2.4 Non-example: l0 ===
x = np.array([1.0, 0.0, 0.0])
alpha = 3.0
l0_x = np.count_nonzero(x)
l0_ax = np.count_nonzero(alpha*x)
print("||x||_0:", l0_x)
print("||alpha x||_0:", l0_ax)
print("|alpha| ||x||_0:", abs(alpha)*l0_x)
check_true("l0 violates homogeneity", l0_ax != abs(alpha)*l0_x)

2.5 Open and closed balls

Code cell 21

# === 2.5 Executable check ===
print("Section 2.5 executed.")
check_true("cell executed", True)

3.1 $\ell^p$ norms

Code cell 23

# === 3.1 lp norms ===
X = np.random.normal(size=(5, 4))
for row in X:
    print(row, "l1=", p_norm(row, 1), "l2=", p_norm(row, 2), "linf=", p_norm(row, np.inf))
check_true("l_inf <= l2 <= l1 for samples", all(p_norm(r, np.inf) <= p_norm(r, 2) <= p_norm(r, 1) for r in X))

3.2 Why nonconvex quasi-norms fail

Code cell 25

# === 3.2 p below one violates triangle ===
x = np.array([1.0, 0.0])
y = np.array([0.0, 1.0])
p = 0.5
quasi_xy = p_norm(x+y, p)
quasi_sum = p_norm(x, p) + p_norm(y, p)
print("quasi ||x+y||:", quasi_xy)
print("quasi ||x||+||y||:", quasi_sum)
check_true("triangle fails for p<1", quasi_xy > quasi_sum)

3.3 Matrix norms

Code cell 27

# === 3.3 Matrix norms ===
A = np.array([[3.0, 1.0], [0.0, 2.0]])
fro = la.norm(A, "fro")
spec = la.svd(A, compute_uv=False)[0]
nuclear = np.sum(la.svd(A, compute_uv=False))
print("Frobenius:", fro)
print("Spectral:", spec)
print("Nuclear:", nuclear)
check_close("spectral norm equals top singular value", spec, la.norm(A, 2))

3.4 Norm equivalence

Code cell 29

# === 3.4 Norm equivalence ===
X = np.random.normal(size=(1000, 8))
ok = True
for x in X:
    ok &= p_norm(x, np.inf) <= p_norm(x, 2) + 1e-10
    ok &= p_norm(x, 2) <= p_norm(x, 1) + 1e-10
    ok &= p_norm(x, 1) <= np.sqrt(len(x))*p_norm(x, 2) + 1e-10
print("all finite-dimensional inequalities verified:", ok)
check_true("norm equivalence inequalities hold on samples", ok)

3.5 Unit ball convexity

Code cell 31

# === 3.5 Executable check ===
print("Section 3.5 executed.")
check_true("cell executed", True)

4.1 Convergence

Code cell 33

# === 4.1 Norm convergence ===
target = np.array([1.0, -2.0])
seq = np.array([target + np.array([1/k, -1/k]) for k in range(1, 51)])
dist = np.array([p_norm(x-target, 2) for x in seq])
print("first distance:", dist[0])
print("last distance:", dist[-1])
check_true("distance to target decreases", dist[-1] < dist[0])

4.2 Cauchy sequences

Code cell 35

# === 4.2 Cauchy sequence ===
terms = np.array([np.sqrt(2) + 1/k for k in range(1, 200)])
tail_diameter = np.max(np.abs(terms[-20:, None] - terms[-20:]))
print("tail diameter:", tail_diameter)
check_true("tail terms are close", tail_diameter < 0.01)

4.3 Banach completeness

Code cell 37

# === 4.3 Banach intuition ===
partial = np.array([sum(2.0**(-k) for k in range(1, n+1)) for n in range(1, 30)])
limit = 1.0
print("last partial sum:", partial[-1])
check_true("geometric partial sums converge in R", abs(partial[-1] - limit) < 1e-8)

4.4 Function norm examples

Code cell 39

# === 4.4 Function norm comparison ===
grid = np.linspace(0, 1, 2000)
f = np.sin(2*np.pi*grid)
l1 = np.trapezoid(np.abs(f), grid)
l2 = np.sqrt(np.trapezoid(f*f, grid))
linf = np.max(np.abs(f))
print("L1 approx:", l1)
print("L2 approx:", l2)
print("Linf approx:", linf)
check_true("finite function norms are positive", l1 > 0 and l2 > 0 and linf > 0)

4.5 Completion intuition

Code cell 41

# === 4.5 Executable check ===
print("Section 4.5 executed.")
check_true("cell executed", True)

5.1 Bounded linear operators

Code cell 43

# === 5.1 Bounded linear operators ===
A = np.array([[2.0, 0.0], [0.0, 0.5]])
samples = np.random.normal(size=(500, 2))
ratios = np.array([la.norm(A@x) / la.norm(x) for x in samples if la.norm(x) > 0])
print("sample max ratio:", ratios.max())
print("spectral norm:", la.norm(A, 2))
check_true("sample ratios are below spectral norm", ratios.max() <= la.norm(A, 2) + 1e-8)

5.2 Bounded iff continuous

Code cell 45

# === 5.2 Executable check ===
print("Section 5.2 executed.")
check_true("cell executed", True)

5.3 Lipschitz constants

Code cell 47

# === 5.3 Neural-network Lipschitz bound ===
W1 = np.array([[1.0, 2.0], [0.0, 1.0]])
W2 = np.array([[0.5, -1.0], [1.0, 0.5]])
bound = la.norm(W2, 2) * la.norm(W1, 2)
combined = la.norm(W2 @ W1, 2)
print("product bound:", bound)
print("actual linear composition norm:", combined)
check_true("composition norm <= product of norms", combined <= bound + 1e-10)

5.4 Dual norms

Code cell 49

# === 5.4 Dual norms ===
y = np.array([1.0, -3.0, 2.0])
dual_l1 = p_norm(y, np.inf)
dual_l2 = p_norm(y, 2)
dual_linf = p_norm(y, 1)
print("dual of l1:", dual_l1)
print("dual of l2:", dual_l2)
print("dual of linf:", dual_linf)
check_close("dual l1 is linf", dual_l1, 3.0)

5.5 Holder inequality

Code cell 51

# === 5.5 Holder inequality ===
x = np.array([1.0, -2.0, 0.5])
y = np.array([3.0, 1.0, -4.0])
lhs = abs(np.dot(x, y))
rhs = p_norm(x, 1) * p_norm(y, np.inf)
print("|<x,y>|:", lhs)
print("||x||_1 ||y||_inf:", rhs)
check_true("Holder inequality holds", lhs <= rhs + 1e-10)

6.1 Contraction mappings

Code cell 53

# === 6.1 Contraction mapping ===
gamma = 0.7
b = 2.0
x = 0.0
history = []
for _ in range(30):
    x = gamma*x + b
    history.append(x)
fixed = b / (1-gamma)
print("iteration result:", x)
print("fixed point:", fixed)
check_close("contraction converges to fixed point", x, fixed, tol=1e-4)

6.2 Compactness failure

Code cell 55

# === 6.2 Noncompact unit vectors in l2 intuition ===
n = 8
E = np.eye(n)
distances = la.norm(E[:, None, :] - E[None, :, :], axis=2)
off_diag = distances[np.triu_indices(n, 1)]
print("distance between distinct basis vectors:", np.unique(np.round(off_diag, 6)))
check_close("basis vectors stay sqrt(2) apart", off_diag[0], np.sqrt(2))

6.3 Function convergence modes

Code cell 57

# === 6.3 Pointwise vs uniform convergence ===
grid = np.linspace(0, 1, 5000)
for n in [5, 20, 100]:
    f = grid**n
    print(f"n={n:3d}, point at 0.5={0.5**n:.6f}, sup norm={np.max(f):.6f}")
check_true("x^n does not converge uniformly to zero on [0,1]", np.max(grid**100) > 0.9)

6.4 Strict convexity

Code cell 59

# === 6.4 Executable check ===
print("Section 6.4 executed.")
check_true("cell executed", True)

6.5 Bridge to Hilbert spaces

Code cell 61

# === 6.5 Parallelogram law ===
x = np.array([1.0, 2.0])
y = np.array([3.0, -1.0])
l2_lhs = p_norm(x+y, 2)**2 + p_norm(x-y, 2)**2
l2_rhs = 2*p_norm(x, 2)**2 + 2*p_norm(y, 2)**2
l1_lhs = p_norm(x+y, 1)**2 + p_norm(x-y, 1)**2
l1_rhs = 2*p_norm(x, 1)**2 + 2*p_norm(y, 1)**2
print("l2 parallelogram lhs/rhs:", l2_lhs, l2_rhs)
print("l1 parallelogram lhs/rhs:", l1_lhs, l1_rhs)
check_close("l2 satisfies parallelogram", l2_lhs, l2_rhs)
check_true("l1 generally fails parallelogram", not np.isclose(l1_lhs, l1_rhs))

7.1 Norm regularization

Code cell 63

# === 7.1 Executable check ===
print("Section 7.1 executed.")
check_true("cell executed", True)

7.2 Adversarial perturbations

Code cell 65

# === 7.2 Adversarial perturbation balls ===
g = np.array([1.0, -2.0, 0.5, 4.0])
eps = 0.1
delta_inf = eps * np.sign(g)
delta_l2 = eps * g / la.norm(g)
print("linf perturbation:", delta_inf, "norm", p_norm(delta_inf, np.inf))
print("l2 perturbation:", delta_l2, "norm", p_norm(delta_l2, 2))
check_close("linf perturbation budget", p_norm(delta_inf, np.inf), eps)
check_close("l2 perturbation budget", p_norm(delta_l2, 2), eps)

7.3 Gradient clipping

Code cell 67

# === 7.3 Gradient clipping ===
g = np.array([10.0, -5.0, 0.0])
C = 3.0
clipped = g * min(1.0, C / la.norm(g))
print("raw norm:", la.norm(g))
print("clipped norm:", la.norm(clipped))
check_close("clipped gradient norm", la.norm(clipped), C)

7.4 Spectral normalization

Code cell 69

# === 7.4 Spectral normalization ===
W = np.array([[3.0, 1.0], [0.0, 2.0]])
Wbar = W / la.norm(W, 2)
print("original spectral norm:", la.norm(W, 2))
print("normalized spectral norm:", la.norm(Wbar, 2))
check_close("spectral norm after normalization", la.norm(Wbar, 2), 1.0)

7.5 Fixed-point iterations

Code cell 71

# === 7.5 Bellman contraction toy ===
gamma = 0.9
V = np.array([0.0, 0.0])
U = np.array([1.0, -2.0])
TV = gamma * V + np.array([1.0, 0.0])
TU = gamma * U + np.array([1.0, 0.0])
lhs = p_norm(TV - TU, np.inf)
rhs = gamma * p_norm(V - U, np.inf)
print("||TV-TU||_inf:", lhs)
print("gamma ||V-U||_inf:", rhs)
check_close("Bellman-style contraction", lhs, rhs)

8 Common mistakes

Code cell 73

# === 8 Executable check ===
print("Section 8 executed.")
check_true("cell executed", True)

9 Exercises preview

Code cell 75

# === 9 Executable check ===
print("Section 9 executed.")
check_true("cell executed", True)

10 AI perspective

Code cell 77

# === 10 Executable check ===
print("Section 10 executed.")
check_true("cell executed", True)

11 Conceptual bridge

Code cell 79

# === 11 Executable check ===
print("Section 11 executed.")
check_true("cell executed", True)

Normed Spaces