Source-linked AI summary
Approximation with Random Bases: Pro et Contra
Alexander N. Gorban, Ivan Yu. Tyukin, Danil V. Prokhorov, Konstantin I. Sofeikov
TL;DR
The paper examines how to select approximators for modeling unknown functions when input dimensions may be high and different convergence guarantees seem to conflict. It compares greedy and randomized approximation analyses and studies the geometry of random vectors. It concludes that bounded coefficients can require exponentially many random vectors, while allowing large coefficients can reduce the count at the cost of ill-conditioning.
Problem
The paper asks how to reconcile reported randomized approximation rates with worst-case estimates when modeling unknown, potentially high-dimensional functions.
Source: §1 · pp. 2–3Method
The paper compares greedy and randomized approximation guarantees and analyzes measure concentration and almost orthogonality in high-dimensional random-vector representations.
Source: §4.4 · p. 15, §5 · p. 17Results
With bounded coefficients, representing high-dimensional elements may require exponentially many random vectors; allowing arbitrarily large coefficients can reduce the number below dimension but makes approximation ill-conditioned.
Source: §7 · p. 28Takeaways & Limitations
For RVFL networks used to model or compensate system uncertainties in adaptive control, re-initialization with supervisory monitoring is necessary.
Source: §7 · p. 26Randomized convergence guarantees are probabilistic, so unlucky draws may require re-initialization, and achievable rates depend on the probability parameter δ.
Source: §3.2 · p. 8, §5 · p. 17
Abstract
from arXiv · showhide
In this work we discuss the problem of selecting suitable approximators from families of parameterized elementary functions that are known to be dense in a Hilbert space of functions. We consider and analyze published procedures, both randomized and deterministic, for selecting elements from these families that have been shown to ensure the rate of convergence in $L_2$ norm of order $O(1/N)$, where $N$ is the number of elements. We show that both randomized and deterministic procedures are successful if additional information about the families of functions to be approximated is provided. In the absence of such additional information one may observe exponential growth of the number of terms needed to approximate the function and/or extreme sensitivity of the outcome of the approximation to parameters. Implications of our analysis for applications of neural networks in modeling and control are illustrated with examples.
1. Introduction
The introduction frames approximation of unknown, potentially high-dimensional functions as a choice between trained and randomly selected bases. It asks why randomized and worst-case convergence claims differ, then previews how high-dimensional geometry and coefficient constraints help explain their practical trade-offs.
1. Introduction
- The motivating data-modeling problem is to infer an unknown relation from inputs that may be numerous, when physical models are not always available.The introduction notes that such models are often built from data when detailed prior knowledge of the true model is absent.Source: §1 · p. 2
- Without detailed prior knowledge of an unknown function, one common approach represents it as a linear combination of known functions, with both linear and nonlinear parameters typically trained.The surveyed basis families include classical functions, wavelets, sigmoids, radial basis functions, and other functions used in neural networks,,,,,.Source: §1 · p. 2
- Allowing all network parameters to vary yields an L2 approximation rate O(1/N^1/2) independent of input dimension for sufficiently smooth functions, but requires nonlinear parameter optimization.With nonlinear parameters fixed, the cited worst-case rate is O(d−1/N^1/d); the introduction notes this as a practical cost of the dimension-independent rate.Source: §1 · pp. 2–3
- Random-basis methods instead initialize nonlinear weights randomly and train only linear coefficients, simplifying nonlinear optimization while retaining a reported O(1/N^1/2) error rate.The cited proposals include,,,, and, with earlier discussion of random-weight perceptrons in.Source: §1 · p. 3
- The paper frames an apparent contradiction between randomized approximator rate O(1/N 1/2) and earlier worst-case estimate O(d−1/N 1/d), explaining that they use different performance criteria.Source: §1 · p. 3
- In high dimensions, random vectors are typically nearly orthogonal; with unconstrained coefficients n−k vectors can approximate any normalized vector, while bounded coefficients may require exponentially many vectors.The paper also notes that exponentially large sets of quasiorthogonal vectors are typical, extending earlier existence results,.Source: §1 · p. 4
2. Notation
The notation section establishes the real-number spaces, norms, and geometric sets used in the paper, and specifies the function norm used for approximation.
2. Notation
- R denotes the real-number field, R^n the n-dimensional real vector space, and ∥x∥ the Euclidean norm of x.The displayed norm is defined by the square root of the sum of squared coordinates.Source: §2 · p. 4
- For nonzero vectors x and y, ∠(x, y) denotes their angle; |·|_Rn denotes an arbitrary norm on R^n..Source: §2 · p. 4
- S^(n−1)(R) denotes the radius-R sphere centered at 0, and B^n(R) the radius-R ball centered at 0.The sphere contains points at Euclidean distance R; the ball contains points at distance at most R.Source: §2 · pp. 4–5
- For continuous f on [0,1]^d, the notation also specifies the L2 norm of f.Source: §2 · p. 5
3. Preliminary analysis and motivation
The section compares deterministic greedy approximation with randomized basis selection: despite similar-looking convergence rates, their guarantees differ, with one deterministic and the other probabilistic,.
3.1. Greedy approximation and Jones Lemma
- The classical Jones iteration, later refined by Barron, provides an estimate of achievable convergence rate; the iteration is deterministic, and the parameter choice is possible when f is in convex hull of G.The convergence estimate is an upper bound for approximation error at the Nth step of the iteration.Source: §3.1 · p. 6
3. Preliminary analysis and motivation
- The deterministic rate is a guaranteed upper bound on approximation error, whereas randomized rates hold probabilistically and permit unlucky draws that may require re-initialization.The randomized rate also depends on a fixed tolerance.Source: §3.1 · p. 6, §3.2 · p. 8
3.2. Approximation by linear combinations of functions with randomly chosen parameters
- The randomized approach approximates an integral representation by Monte Carlo sampling of basis parameters, while optimizing only linear coefficients.The parameters are sampled from the domain of network weights and biases.Source: §3.2 · p. 7
- Randomized convergence claims depend on a probability measure and fixed tolerance, and measure concentration is an additional concern for these approximators.The analysis highlights a nonzero chance of an unlucky draw and raises measure concentration as an issue for applications.Source: §3.2 · p. 8
4. Randomized Data Approximation and Measure Concentration
The section examines whether random vectors can represent data accurately and robustly, then analyzes their dependence and concentration in high dimensions. It finds that high-dimensional concentration can coexist with exponentially many pairwise almost orthogonal vectors.
4. Randomized Data Approximation and Measure Concentration
- The motivating representation problem asks how many randomly chosen vectors are needed for accurate, broadly applicable representation, and how robust that representation is to small data perturbations.For analysis, the vectors are treated as random samples in a hypercube.Source: §4 · p. 9
4.1. Linear dependence and independence and related elementary properties
- Linear independence of the vectors is equivalent to a positive lower bound ε on |Hx| over the unit sphere.The lower bound provides a criterion for assessing independence, although small ε can be difficult to check numerically.Source: §4.1 · p. 10, §4.2 · p. 10
4.2. Quantification of linear independence
- The paper quantifies near-independence by combining a separation threshold ε with a measure μ of how many unit vectors satisfy it.These probabilistic notions approach conventional linear independence in the stated limiting case.Source: §4.2 · pp. 10–11
4.3. Measure concentration
- In high dimensions, most of a ball’s volume lies near its surface and is concentrated around the largest equator; nearly all random vectors lie near an (n−1)-disc.A set of n−1 vectors spans almost all vectors with probability close to one.Source: §4.3 · pp. 11–13
4.4. Almost orthogonality in high dimensions
- Exponentially many pairwise ε-orthogonal vectors can be selected in high dimensions with probability at least 1 − ϑ; the refined estimate retains exponential rate e^(ε²n/4).The section also describes almost-linear dependence among sufficiently large families of independently chosen vectors.Source: §4.2 · p. 11, §4.4 · p. 16
5. Discussion
The discussion reconciles reported randomized and greedy convergence rates while showing why randomized bases can still be impractical. Their constants, success-probability targets, and coefficient sensitivity all matter.
5. Discussion
- Both greedy approximation and randomized basis systems achieve O(1/N^1/2) convergence independent of domain dimension, but greedy methods require nonlinear optimization while randomized methods reduce the task to a linear one.The exponential bound helps explain the apparent controversy between these approaches.Source: §5 · p. 17
- The randomized error constant C can become large, and achieving higher success probability by reducing δ affects the rate, so practical use requires analysis of the function class.Kernels approaching Dirac delta-functions can make C arbitrarily large.Source: §5 · p. 17
- With coefficient values bounded, randomized bases may require exponentially many vectors; shorter bases can be nearly dependent and yield arbitrarily large, noise-sensitive coefficients.Systems of n − k vectors span almost all vectors in a ball, but the resulting coefficients can be arbitrarily large.Source: §5 · p. 17
- Binning through lower-dimensional spaces, such as multiscale bases randomized at each scale, may limit exponential growth, but efficiency depends on suitability and the approach violates isotropy.For signals sparse in a fixed basis, proves that few random measurements can reconstruct them with very high accuracy.Source: §5 · p. 18
6. Examples
The examples show that approximation performance depends strongly on how bases are selected and on the dimensionality effects encountered. Greedy convergence is consistent, while random-basis approximation can be slow and variable, including for a simple constant function.
6.1. Error convergence rate. Deterministic vs Randomized approaches
- Greedy approximation converged consistently at O(1/N), whereas Monte-Carlo bases were slower, variable, and mostly underperformed greedy for reasonable network sizes.Full training achieved normalized error 1.5 · 10^-4 for N = 20, 40, 60, 80, and 100; random-basis approximation with N = 100 performed worse than full-trained MLPs with N ≥ 4.Source: §6.1 · pp. 19, 22, Figure 2 · p. 20, Figure 3 · p. 21
6.2. Measure concentration effects
- For n = 1920, centered, normalized class vectors in [−1,1]^n had angles concentrating near π/2; random-chain lengths aligned with conservative and refined theoretical estimates at ϑ = 0.1.Chains used independently sampled vectors from [−1,1]^n, with 20 chains per dimension. The precision margin π/2 ± 0.037π/2 corresponds to ε = 0.0581.Source: §6.2 · pp. 22, 24, Figure 5 · p. 24
6.3. Approximation of a constant: dimensionality blowup
- Even a constant exactly representable by one basis function showed rapid initial error reduction only through N ≤ 100, then near-stalling as errors became spiky and demanded narrower features.The authors describe each step as effectively increasing problem dimensionality; overcoming measure concentration requires exponentially many samples.Source: §6.3 · pp. 25–26, Figure 6 · p. 26
7. Conclusion
Random-basis approximation has probabilistic guarantees and practical constraints that matter in control and modeling. In high dimensions, random-vector geometry creates a trade-off between the number of elements and ill-conditioning.
7. Conclusion
- The paper urges attention to practical factors that may affect random-basis network performance in applications.The discussion focuses especially on intelligent and adaptive control.Source: §7 · p. 26
- Random-basis approximation is statistical: small errors are guaranteed in probability, so adaptive-control RVFL use needs supervisory quality monitoring and reinitialization.The monitoring mechanism may also need robustness to numerical problems such as ill-conditioning.Source: §7 · p. 26
- Combining unsupervised node placement by input density with supervised or reinforcement learning of linear weights could improve random-basis effectiveness, but adaptive resource allocation makes the combination nontrivial.Full network training seems a natural way to handle adaptive allocation in modeling and control.Source: §7 · pp. 26, 28
- In high dimensions, random independent vectors are almost orthogonal with high probability; bounded coefficients may require exponentially many samples, while unbounded coefficients reduce the count below dimension but cause ill-conditioning.The paper provides a numerical example illustrating measure concentration in a simple approximation problem and its implications for other randomized approximation schemes.Source: §7 · p. 28