Source-linked AI summary
An Algorithm for Computing Lipschitz Inner Functions in Kolmogorov's Superposition Theorem
Jonas Actor, Matthew G. Knepley
TL;DR
Prior constructions yielded only Hölder-continuous inner functions, leaving computation of Lipschitz-continuous ones unresolved. The paper examines a candidate that loses separation in the limit, then constructs a Lipschitz inner function. The construction has Lipschitz constant 1 and supports a Kolmogorov representation for continuous functions.
Problem
Prior constructions produced Hölder-continuous inner functions, but no method to compute a Lipschitz-continuous one had been shown.
Source: §1 · p. 2Method
The paper examines a simple candidate that loses separation in the limit, then constructs an inner function satisfying the conditions for Sprecher’s reformulation.
Source: §3 · p. 3, §3.1 · p. 6, §4 · p. 6Results
The constructed inner function is Lipschitz continuous on [−1, 1] with constant 1, and every continuous f on [0, 1]^n admits a KST representation.
Source: §4 · p. 7, §4.4 · p. 12Takeaways & Limitations
The construction improves inner-function smoothness over prior Hölder-continuous versions; practical computation is envisioned with an efficient method for constructing the outer functions.
Source: §6 · p. 15The main text does not complete the original KST proof, instead directing readers to the appendix for the remainder.
Source: §2 · p. 3
Abstract
from arXiv · showhide
Kolmogorov famously proved that multivariate continuous functions can be represented as a superposition of a small number of univariate continuous functions, $$ f(x_1,\dots,x_n) = \sum_{q=0}^{2n+1} \chi^q \left( \sum_{p=1}^n \psi^{pq}(x_p) \right).$$ Fridman \cite{fridman} posed the best smoothness bound for the functions $\psi^{pq}$, that such functions can be constructed to be Lipschitz continuous with constant 1. Previous algorithms to describe these inner functions have only been H\"older continuous, such as those proposed by K\"oppen and Braun and Griebel. This is problematic, as pointed out by Griebel, in that non-smooth functions have very high storage/evaluation complexity, and this makes Kolmogorov's representation (KR) impractical using the standard definition of the inner functions. To date, no one has presented a method to compute a Lipschitz continuous inner function. In this paper, we revisit Kolmogorov's theorem along with Fridman's result. We examine a simple Lipschitz function which appear to satisfy the necessary criteria for Kolmogorov's representation, but fails in the limit. We then present a full solution to the problem, including an algorithm that computes such a Lipschitz function.
1. Kolmogorov’s Superposition Theorem.
Kolmogorov’s theorem represents multivariate continuous functions through univariate continuous functions. The section highlights the construction of Lipschitz inner functions and introduces Sprecher’s reformulation using a single inner function.
1. Kolmogorov’s Superposition Theorem.
- Kolmogorov’s theorem represents a continuous function on [0, 1]^n using continuous inner functions ψ_pq and outer functions χ_q.The theorem passage specifies n ≥ 2 and indexes p from 1 to n and q from 0 to 2n.Source: §1 · p. 1
- The inner functions ψ_pq can be chosen independently of f and Lipschitz continuous with constant 1.Source: §1 · p. 1
- Sprecher’s reformulation replaces the family ψ_pq with translations and scalings of a single Lipschitz-continuous function ψ.The reformulation fixes ε ≤ 1/(2n) and uses integrally independent parameters.Source: §1 · pp. 1–2
- Earlier constructions by Köppen and Braun and Griebel produced Hölder-continuous inner functions, but no method to compute a Lipschitz-continuous one had been shown.The section identifies this as the gap motivating its construction.Source: §1 · p. 2
2. Kolmogorov’s Original Proof.
Kolmogorov’s proof builds shifted interval partitions and successive refinements to construct inner functions. Cube-covering and separation lemmas support the construction, while the paper leaves the rest of the proof to the appendix.
2. Kolmogorov’s Original Proof.
- The line is divided into intervals separated by gaps, replicated 2n+1 times with shifts so the gaps do not align, then combined by products to form small cubes.Source: §2 · p. 2
- Successive refinements of the shifted line divisions create “towns” in two dimensions; gaps allow continuous functions to approximate parts of the target function whose contributions add correctly.Arnold termed these structures “towns”.Source: §2 · p. 2
- At each refinement level, the cube systems nearly cover the unit cube, each point is included for n+1 values of q, and cube diameters tend to zero.Source: §2 · p. 2
- A second lemma constructs inner functions so the sums Ψq distinguish the relevant cubes at each refinement level.The passage introduces Ψq as the sum of ψ_pq over coordinates.Source: §2 · p. 2
- The proof’s remaining steps follow Kolmogorov, but are not completed in the main text and are provided in the appendix.Source: §2 · p. 3
3. A Misleading Candidate for a Lipschitz Inner Function.
The section tests a Lipschitz monotone candidate built from shifted, refined intervals: although it appears to meet the separation criterion, separation is lost in the limit. It then shows that the resulting linear inner functions do not yield a Kolmogorov representation.
3. A Misleading Candidate for a Lipschitz Inner Function.
- The proposed candidate is a Lipschitz monotone function intended to separate values on the boxes, but that criterion alone is insufficient for the theorem.Source: §3 · p. 3
- The candidate construction combines Kolmogorov’s uniformly spaced intervals with shrinking diameters and Sprecher’s base-γ decimal representation.The base is chosen with γ ≥ 2n + 2.Source: §3 · p. 3
- For every point in I^n, Lemma 3.1 places it in S_q for n + 1 values of q.Source: §3 · p. 3
3.1. Why this function is misleading.
- The candidate separates values on the constructed boxes but loses separation in the limit, effectively separating only values on dyadic-expansion points.The authors state that this flaw extends beyond their n = 2 illustration to higher dimensions.Source: §3 · p. 3, §3.1 · p. 6
- The cited theorem states that the function class F is nowhere dense and of first category in C(D), with even a polynomial outside F.The passage attributes the theorem to Vitushkin’s result.Source: §3.1 · p. 6
- The constructed linear inner functions do not allow a Kolmogorov representation.The paper presents this as confirmation that a linear inner function is insufficient for the representation.Source: §3.1 · p. 6
4. Construction of our Lipschitz Inner Function.
The construction builds a Lipschitz inner function from refining systems of shifted intervals, then establishes that its limit meets the required conditions for a Kolmogorov representation. Its algorithm identifies holes, solves for plugs, and creates gaps while preserving the interval and function properties needed by the proof.
4. Construction of our Lipschitz Inner Function.
- The construction yields a KST representation for every continuous f using inner functions formed from a shared Lipschitz function and shifted, weighted copies.The inner sums use integrally independent weights.Source: §4 · pp. 6–7
4.1. Finding Holes.
- For each breakpoint, the algorithm identifies holes where shifted points lack town coverage and groups any plugs needed within those holes.Breakpoints are town midpoints, perturbed slightly when needed to avoid ε-aligned collisions.Source: §4.1 · p. 8
4.2. Solve for Plugs.
- The algorithm solves for all plugs in a hole at once, using a block-diagonal linear system and symmetry constraints to obtain unique, nonoverlapping plugs.Adding plugs ensures the breakpoints remain covered by enough towns for the interval conditions.Source: §4 · p. 7, §4.2 · pp. 8, 9, 11
4.3. Create Gaps.
- It creates gaps around selected breakpoints so shifted gaps remain within corresponding towns, then replaces each split interval with two intervals.The algorithm avoids overlapping gaps.Source: §4.3 · pp. 11–12
4.4. Analysis of Inner Function ψ.
- The limit function is well-defined and Lipschitz with constant 1, while the refining towns preserve coverage, shrinking diameters, disjoint images, and bounded slopes.The construction’s towns satisfy the stated refinement conditions at each level.Source: §4 · p. 7, §4.4 · pp. 12–13
5. Results.
The refined town families show at most one family with a gap at any point in [0, 1] for the displayed levels, while the largest intervals approximately halve between iterations. The paper also reports the implementation used to generate the figures and ψ.
5. Results.
- Algorithm 1 was implemented in Python 2.7 with mpmath and intervaltree and run serially on a Razer Blade computer with an i7 processor.The interval tree was used to efficiently store the system of towns.Source: §5 · p. 13
- At levels j = 3, 4, at most one family has a gap at any point in [0, 1], as verified in Fig. 4.The figure focuses on the interval [0, 1].Source: §5 · p. 15, Figure 4 · p. 15
- The largest intervals are approximately halved between iterations, even when the gaps created are small.The families of towns shown in Fig. 3 were produced during the first four iterations.Source: §5 · pp. 13, 15, Figure 3 · p. 14
6. Discussion.
The algorithm improves the smoothness of inner KST functions over earlier H er-continuous versions. The authors argue that Lipschitz regularity should address concerns about insufficient regularity, while practical computation and applications remain prospective.
6. Discussion.
- The algorithm improves inner-function smoothness over H er-continuous versions proposed by Kppen and Braun and Griebel.The authors describe the earlier versions as H er continuous.Source: §6 · p. 15
- The authors argue that Lipschitz regularity should answer concerns that KST functions lack sufficient regularity for efficient real-world resolution.They plan to extend Lipschitz regularity to the outer functions in an upcoming publication.Source: §6 · p. 15
- The authors envision practical computation of the representation when this construction is paired with an efficient method for constructing the outer functions χq.They identify encryption, content-based image and video retrieval, and image compression as possible application areas.Source: §6 · p. 15
Appendix: Proof of Kolmogorov Superposition Theorem.
The appendix completes the theorem proof by constructing approximations through induction and showing that their limit yields the representation. The argument uses continuity-preserving extensions and a Cauchy sequence of outer functions.
Appendix: Proof of Kolmogorov Superposition Theorem.
- At induction step r, the proof chooses kr so the oscillation of f − fr−1 is bounded on each specified square.The base case sets f0 to zero and M0 to the supremum norm of f.Source: Appendix: Proof of Kolmogorov… · p. 16
- The construction uses the Tietze Extension Theorem to maintain continuity while defining the next approximation.The proof partitions the indices into Q1 and Q2, with sizes n + 1 and n, respectively.Source: Appendix: Proof of Kolmogorov… · p. 16
- The sequence of outer functions is Cauchy, so its limit χq is well-defined and continuous.The proof concludes that fr converges to f as Mr tends to zero, completing the theorem proof.Source: Appendix: Proof of Kolmogorov… · p. 17