CPBS 7620 - Lecture 13 - Norms and Inner Products

Overview

Nicholas Dwork develops norms, inner products, and metrics as increasingly general ways to measure vector size, angles, and distance. He connects the Lp and matrix norms to SVD-based low-rank approximation, then extends inner products to square-summable functions and distinguishes norm-induced distances from more general metrics.

Key takeaways

The Lp expression defines a norm only for p ≥ 1, with L∞ given by the largest absolute coordinate; for 0 ≤ p < 1 it is a penalty rather than a norm.
The L0 penalty records sparsity, not magnitude: any two vectors with exactly one nonzero coordinate receive penalty 1, even if those coordinates are 10^-99 and 10^99.
The Frobenius norm of A equals the square root of the sum of its squared singular values, and truncating the SVD to the largest k singular values yields the best rank-k Frobenius approximation.
Induced matrix norms quantify worst-case input-to-output amplification; the induced 2-norm is the largest singular value, while the induced 1- and infinity-norms are maximum column and row sums.
An inner product determines both a norm and an angle, allowing function-space angles to be computed with integrals; the example functions e^-x and e^-3x on the nonnegative real line meet at π/6.
Every norm defines a metric by measuring ||x-y||, but metrics need not come from norms, as shown by the discrete metric and distances along the unit sphere.

Chapters

0:00 Lp Norms, Frobenius Norm, and SVD-Based Matrix Approximation

A norm satisfies nonnegativity with equality only at zero, absolute homogeneity, and the triangle inequality; the Lp formula is a norm for 1 ≤ p ≤ ∞.
The L∞ norm is the largest absolute vector entry, while the L0 penalty counts nonzero entries and treats vectors with one nonzero entry equally regardless of its magnitude.
The Frobenius norm is the L2 norm of a matrix's entries and also the L2 norm of its singular values; the nuclear norm sums singular values, and both are Schatten norms.
For a rank-r matrix A, the rank-k truncated SVD gives the closest rank-at-most-k approximation under the Frobenius norm.

6:49 Induced Matrix Norms and Inner-Product Angles

An induced matrix norm maximizes the output β-norm of Ax over inputs with α-norm equal to 1; the induced 2-norm is A's 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 satisfy ||AB||p ≤ ||A||p||B||p.
Real inner products are positive definite, symmetric, and linear in the first argument; each induces a norm, and cos θ = <A,B>/(||A||||B||).
For f(x)=e^-x and g(x)=e^-3x on x ≥ 0, the squared norms are 1/2 and 1/6, their inner product is 1/4, and the angle is π/6.

10:02 Metric Spaces, Norm-Induced Distance, and Counterexamples

Square-summable functions form a vector space with inner product <f,g> = ∫ from -∞ to ∞ f(x)g(x) dx, extending angle calculations to functions.
The Cauchy-Schwarz inequality bounds |<x,y>| by ||x||||y||, while the L1 norm cannot be induced by an inner product.
A metric obeys nonnegativity and identity of indiscernibles, symmetry, and the triangle inequality; every norm creates a metric through d(x,y)=||x-y||.
The discrete metric, which assigns distance 1 to distinct points, is not norm-induced because scaling x to 2x does not scale its distance from zero; spherical arc distance also lives on a set that is not a vector space.

Transcript excerpt

0:00 Hi, I'm Nicholas Twork, and in this lecture we'll discuss norms and inner products. Previously, we've discussed the lengths of vectors, which we calculated using the L2 norm, shown here. We've also discussed the angles between vectors, which we calculated using the dot product, shown here. We'll now see that these concepts of lengths and angles can be generalized to other implementations of norms and inner products. A norm on a vector space V is a function that maps V to R that satisfies three properties. The first is that the norm of a vector is always greater than or equal to zero, and the norm equals zero if and only if the vector is the zero vector. The second property is that the norm of a scalar times the vector, alpha times X, is equal to the absolute value of

0:50 alpha times the norm of X. And the third is that the norm of X plus Y is less than or equal to the norm of X plus the norm of Y. This is known as the triangle inequality. So, for example, consider this expression here. The magnitude of X1 to the P plus the magnitude of X2 to the P plus dot dot dot plus the magnitude of Xn to the P, all raised to the 1/P power. This is a norm whenever P is between 1 and infinity inclusive, and we call it the LP norm. I do mean inclusive. The L infinity norm of a vector X is the maximum magnitude of the elements of X. When P is greater than or equal to zero and less than one, this function is not

1:38 a norm, but it is still useful. We sometimes call it a penalty. So, for example, here's the L1/2 penalty. The L0 penalty is the number of nonzero

This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.

Related notes

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.