Vector and Matrix Norms

What is a Norm

A norm is a function from a vector space to the non-negative real numbers that satisfies four fundamental axioms:

Axiom	Property	Description
1	Non-negativity	for all
2	Definiteness
3	Homogeneity	for all scalars
4	Triangle Inequality	for all

A vector space equipped with a norm is called a normed vector space. The norm induces a natural distance function , making it a metric space.

Vector Norms

Norm	Formula	When to Use
L1 (Manhattan)		Sparse solutions, feature selection (Lasso)
L2 (Euclidean)		Smooth solutions, general-purpose (Ridge)
L∞ (Max Norm)		Worst-case analysis, adversarial robustness
Lp (General)		Interpolation between L1 and L∞
L0 (Pseudo-norm)		Cardinality (non-convex, NP-hard to optimize)

Step-by-Step Example: Computing Vector Norms

Matrix Norms

The Frobenius norm treats a matrix as a vector in 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

Norm	Formula	Use Case
Frobenius		General matrix similarity, reconstruction error
Spectral		Stability analysis, condition number, Lipschitz constants
Nuclear		Matrix completion, low-rank recovery
L1 (entry-wise)		Sparse matrix recovery
L∞ (entry-wise)		Bounded perturbations

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:

Induced Norm	Definition	Formula
Induced 2-norm
Induced 1-norm
Induced ∞-norm

Example: Computing Matrix Norms

Norm Equivalence

Unit Ball: Geometric Interpretation

The unit ball of a norm is the set . Its shape reveals the geometric character of the norm.

Norm	Unit Ball Shape	Geometry
L1	Diamond (rotated square in 2D)	Vertices at and
L2	Circle / Sphere	Smooth, rotationally symmetric
L∞	Square / Hypercube	Vertices at
Lp (1 < p < ∞)	Rounded polygon	Interpolates between diamond and circle

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

Penalty	Name	Effect
	Lasso	Sparse solutions, automatic feature selection
	Ridge	Small weights, no feature selection
	Elastic Net	Combines sparsity and smoothness
	Minimax	Bounded maximum coefficient

Distance Metrics

A norm induces a distance metric that satisfies:

Non-negativity:
Identity:
Symmetry:
Triangle inequality:

Distance	Formula	Use Case
Manhattan ()		Grid-based movement, high-dimensional data
Euclidean ()		Geometric distance, clustering
Chebyshev ()		Warehouse logistics, robotics

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

Mistake	Why It's Wrong	Correct Approach
Using L0 norm for optimization	L0 is non-convex, NP-hard	Use L1 as convex relaxation
Confusing with	Frobenius sums all singular values, spectral takes the max
Forgetting	Homogeneity requires absolute value on scalar	, not
Assuming all norms are equal in infinite dimensions	Norm equivalence requires finite dimensions	In function spaces, different norms define different topologies
Using L2 norm for sparse feature selection	L2 shrinks but doesn't zero out features	Use L1 (Lasso) or Elastic Net
Ignoring norm when computing condition number	depends on the norm	Choose the norm appropriate for your error metric

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 .

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 .

Problem 2: Verify the Cauchy-Schwarz inequality for and .

Problem 3: Compute the Frobenius and spectral norms of .

Problem 4: Show that for any vector : .

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

Vector and Matrix Norms