Vector and Matrix Norms

Vector and Matrix Norms

What is a Norm

A norm is a function $\|\cdot\|: V \to \mathbb{R}_{\geq 0}$ from a vector space $V$ to the non-negative real numbers that satisfies four fundamental axioms:

A vector space equipped with a norm is called a normed vector space. The norm induces a natural distance function $d(\vec{x}, \vec{y}) = \|\vec{x} - \vec{y}\|$, making it a metric space.

Vector Norms

Step-by-Step Example: Computing Vector Norms

Matrix Norms

The Frobenius norm treats a matrix as a vector in $\mathbb{R}^{m \times n}$ and computes its Euclidean norm. It equals the square root of the sum of squared singular values.

The spectral norm measures the maximum "stretch" factor of a linear transformation. It equals the largest singular value.

The nuclear norm (also called the trace norm) is the convex envelope of the rank function over the unit spectral norm ball. It is used in matrix completion and low-rank approximation.

Comparison of Matrix Norms

Induced (Operator) Norms

An induced norm (also called an operator norm) measures the maximum output norm given an input constrained to unit norm. The most common induced norms are:

Example: Computing Matrix Norms

Norm Equivalence

Unit Ball: Geometric Interpretation

The unit ball of a norm is the set $B = \{\vec{x} : \|\vec{x}\| \leq 1\}$. Its shape reveals the geometric character of the norm.

The L1 unit ball's "pointy" vertices at the axes explain why L1 optimization produces sparse solutions — the optimal point is more likely to land on a vertex where some coordinates are exactly zero.

Norms in Optimization

Distance Metrics

A norm $\|\cdot\|$ induces a distance metric $d(\vec{x}, \vec{y}) = \|\vec{x} - \vec{y}\|$ that satisfies:

1. Non-negativity: $d(\vec{x}, \vec{y}) \geq 0$
2. Identity: $d(\vec{x}, \vec{y}) = 0 \iff \vec{x} = \vec{y}$
3. Symmetry: $d(\vec{x}, \vec{y}) = d(\vec{y}, \vec{x})$
4. Triangle inequality: $d(\vec{x}, \vec{z}) \leq d(\vec{x}, \vec{y}) + d(\vec{y}, \vec{z})$

Python Implementation

import numpy as np

# --- Vector Norms ---
x = np.array([1, -2, 3, -4])

l1 = np.linalg.norm(x, ord=1)           # L1: 10.0
l2 = np.linalg.norm(x, ord=2)           # L2: sqrt(30) ≈ 5.477
linf = np.linalg.norm(x, ord=np.inf)    # L∞: 4.0
l4 = np.linalg.norm(x, ord=4)           # L4: 354^(1/4) ≈ 4.34

print(f"L1: {l1}, L2: {l2:.4f}, L∞: {linf}, L4: {l4:.4f}")

# --- Matrix Norms ---
A = np.array([[1, 2], [3, 4]])

frob = np.linalg.norm(A, ord='fro')     # Frobenius: sqrt(30) ≈ 5.477
spectral = np.linalg.norm(A, ord=2)     # Spectral: largest singular value
nuclear = np.linalg.norm(A, ord='nuc')  # Nuclear: sum of singular values

print(f"Frobenius: {frob:.4f}")
print(f"Spectral: {spectral:.4f}")
print(f"Nuclear: {nuclear:.4f}")

# --- Induced Norms ---
induced1 = np.linalg.norm(A, ord=1)     # Induced 1-norm: max column sum
induced_inf = np.linalg.norm(A, ord=np.inf)  # Induced ∞-norm: max row sum
print(f"Induced 1-norm: {induced1}")
print(f"Induced ∞-norm: {induced_inf}")

# --- Distance Computation ---
from scipy.spatial.distance import cdist, pdist

points = np.array([[0, 0], [1, 0], [0, 1], [1, 1]])
dist_l1 = cdist(points, points, metric='cityblock')   # Manhattan
dist_l2 = cdist(points, points, metric='euclidean')   # Euclidean
dist_linf = cdist(points, points, metric='chebyshev') # Chebyshev

# --- Regularization Comparison ---
from sklearn.linear_model import Lasso, Ridge

np.random.seed(42)
X = np.random.randn(100, 10)
true_coef = np.zeros(10)
true_coef[:3] = [3, -2, 1]  # Only 3 non-zero features
y = X @ true_coef + np.random.randn(100) * 0.1

lasso = Lasso(alpha=0.1).fit(X, y)
ridge = Ridge(alpha=0.1).fit(X, y)

print(f"Lasso coefficients: {np.round(lasso.coef_, 3)}")  # Sparse
print(f"Ridge coefficients: {np.round(ridge.coef_, 3)}")  # Small but non-zero

Applications in AI/ML

Common Mistakes

Interview Questions

Q1: Why does L1 regularization produce sparse solutions while L2 does not?

Q2: What is the relationship between the spectral norm and the Frobenius norm?

Q3: When would you use the nuclear norm instead of the Frobenius norm?

Q4: Prove that the L∞ norm is indeed a norm on $\mathbb{R}^n$.

Q5: What is the condition number of a matrix, and why does the norm matter?

Q6: How do norms relate to convergence in optimization algorithms?

Practice Problems

Problem 1: Compute the L1, L2, L∞, and L4 norms of $\vec{x} = \begin{bmatrix} 3 \\ -4 \\ 0 \\ 5 \end{bmatrix}$.

Problem 2: Verify the Cauchy-Schwarz inequality for $\vec{x} = \begin{bmatrix} 1 \\ 2 \\ 3 \end{bmatrix}$ and $\vec{y} = \begin{bmatrix} 4 \\ 5 \\ 6 \end{bmatrix}$.

Problem 3: Compute the Frobenius and spectral norms of $A = \begin{bmatrix} 2 & 0 \\\\ 0 & 3 \end{bmatrix}$.

Problem 4: Show that for any vector $\vec{x} \in \mathbb{R}^n$: $\|\vec{x}\|_\infty \leq \|\vec{x}\|_2 \leq \sqrt{n} \|\vec{x}\|_\infty$.

Quick Reference

Cross-References

• Vector Spaces: Foundation for defining norms
• Eigenvalues and Singular Values: Used to compute spectral and nuclear norms
• Inner Products: Cauchy-Schwarz inequality connects norms to inner products
• Optimization: Regularization, gradient descent, constrained optimization
• Machine Learning: Lasso, Ridge, Elastic Net, adversarial robustness
• Numerical Linear Algebra: Condition numbers, stability analysis
• Clustering: K-means uses Euclidean norm, K-medians uses L1
• Dimensionality Reduction: PCA minimizes Frobenius norm reconstruction error