CPBS 7620 - Lecture 13 - Norms and Inner Products

Overview

Nicholas Dwork develops norms and inner products as generalizations of vector length and angle, then connects them to matrix approximation and distance. He explains Lp and matrix norms, the best rank-k approximation via truncated SVD, inner-product geometry for functions, and why some metrics cannot come from norms.

Key takeaways

The Lp formula is a norm for p ≥ 1, while L0 counts nonzero coordinates and ignores their magnitudes, making it useful as a sparsity penalty rather than a norm.
Truncating a matrix's SVD to its k largest singular values solves the best rank-at-most-k approximation problem under Frobenius distance.
The Frobenius norm is the Schatten-2 norm, the nuclear norm is the Schatten-1 norm, and the induced 2-norm equals the largest singular value.
An inner product supplies both a norm and an angle; for square-integrable functions, integration of their product plays the role of the vector dot product.
Every norm creates a metric through d(x,y)=||x−y||, but not every metric comes from a norm: the discrete metric violates norm homogeneity.

Chapters

0:00 Vector Norms, Lp Penalties, and Low-Rank SVD Approximation

A norm must be nonnegative with equality only at zero, scale by the absolute value of a scalar, and satisfy the triangle inequality.
For p ≥ 1, the Lp norm is valid; L∞ is the largest absolute vector entry, while L0 counts nonzero entries and is a penalty rather than a norm.
The L0 penalty assigns the same value of 1 to vectors with one nonzero entry even when those entries have very different magnitudes.
The Frobenius norm extends L2 length to matrices, and truncating an SVD to its top k singular values gives the closest rank-at-most-k matrix in Frobenius norm.

3:08 Frobenius, Schatten, and Induced Matrix Norms

The Frobenius norm equals the square root of the sum of squared singular values, as shown using orthogonality of U and V and the identity tr(AB) = tr(BA).
The nuclear norm sums singular values; both it and the Frobenius norm are Schatten norms, specifically Schatten-1 and Schatten-2.
An induced matrix norm maximizes the output norm of Ax over inputs x with unit norm; the induced 2-norm is the largest singular value.
The induced 1-norm is the maximum absolute column sum, the induced infinity norm is the maximum absolute row sum, and induced p-norms are submultiplicative.

6:49 Inner-Product Geometry, Function Angles, and Metrics

A real inner product is positive definite, symmetric, and linear in its first argument; it induces a norm through the square root of ⟨x,x⟩.
Inner products define angles by cos θ = ⟨a,b⟩/(||a|| ||b||), and the Cauchy–Schwarz inequality bounds |⟨x,y⟩| by ||x|| ||y||.
For square-summable functions, ⟨f,g⟩ = ∫f(x)g(x)dx; for f=e⁻ˣ and g=e⁻³ˣ on x≥0, the angle is π/6.
A metric obeys nonnegativity, identity of indiscernibles, symmetry, and the triangle inequality; every norm induces d(x,y)=||x−y||, but the discrete metric is not norm-induced.
Arc length on the unit sphere S² defines a distance between points, but S² is not a vector space and therefore cannot carry a norm.

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Nicholas Dwork.