##  [Kolmogorov N-Width](/kolmogorov-n-width-0) 

 Definition

For a compact set F in a normed linear space and integer n, the Kolmogorov n-width is the smallest possible worst-case approximation error when elements of F are projected onto any n-dimensional linear subspace; formally, d_n(F)=inf_{subspace V, dim V=n} sup_{f in F} dist(f,V).

 

 

 

 

 

 





## Principle

Principle

Organize approximation quality by the minimax error over all n-dimensional linear subspaces: choose the linear subspace that minimizes the maximum distance from F to that subspace.

 

 

 

 

 





## Demonstration

Demonstration

Approximate the unit ball of a Sobolev space by an n-dimensional polynomial subspace: the n-width decays at a rate determined by the smoothness and ambient dimension, giving a concrete bound on the sup-norm approximation error for all functions in the ball.

 

 

 

 

## Misapplication

Misapplication

Using Kolmogorov n-width to evaluate nonlinear approximation schemes (e.g., neural networks or adaptive dictionaries) as if they were constrained to linear subspaces; this underestimates the power of nonlinear methods.

 

 

 

 

 





## Consequence

Consequence

A small n-width implies that F can be uniformly approximated by low-dimensional linear models, which yields compression, model reduction, and deterministic worst-case error guarantees for linear approximation methods.

 

 

 

 

## Reversal

Reversal

Invert the perspective by fixing the approximation error and asking for the minimal n required to achieve it; contrasted with dual widths (e.g., Gelfand widths) that measure approximation from linear functionals rather than subspaces.

 

 

 

 

 





## Boundary

Boundary

Applies only to linear subspaces and worst-case (supremum) errors in a specified norm; values depend strongly on the norm, require compactness or precompactness of F to be finite, and do not describe randomized or average-case approximability.

 

 

 

 

 





## Semantic Tension

Semantic Tension

Competes with nonlinear approximation measures (manifold dimension, nonlinear widths) and with dual concepts like Gelfand widths; similar terms may conflate linearity, worst-case versus average error, or dependence on the ambient norm.

 

 

 

 

 





## Synthesis

Synthesis

Kolmogorov n-width quantifies the best worst-case linear compressibility of a compact set in a given norm: it is the infimum over n-dimensional subspaces of the maximum distance from the set to the subspace, providing a precise measure of linear approximation power.