🔢 mathematics

Sampling and reconstruction of convex functions

This paper establishes optimal recovery rates for multivariate convex functions in $L_p$ spaces, demonstrating that unlike classical smoothness classes, uniform tensor product grids and linear reconstruction methods generally yield suboptimal results for convex functions and are outperformed by nonlinear methods.

Original authors: Andrea Bonito, Albert Cohen, Wolfgang Dahmen, Ronald Devore, Guergana Petrova, Jonathan W. Siegel

Published 2026-06-04

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Andrea Bonito, Albert Cohen, Wolfgang Dahmen, Ronald Devore, Guergana Petrova, Jonathan W. Siegel

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to reconstruct a smooth, hilly landscape (a "convex function") based on a limited number of measurements you've taken. You have a map, but you can only stick a few flags into the ground to measure the height at specific spots. Your goal is to draw the most accurate picture of the entire terrain possible using only those flag measurements.

This paper is about finding the best possible strategy for placing those flags and the best way to draw the map between them, specifically when the terrain has a special property: it is convex. In math terms, "convex" means the land never dips into a valley; it only curves upward like a bowl or a hill. It might have sharp corners, but it never has a "dip" in the middle of a slope.

Here is the breakdown of their discovery, using simple analogies:

1. The Old Way: The Grid Pattern

For decades, mathematicians have solved similar problems (like drawing smooth hills) by using a uniform grid. Imagine laying a perfect checkerboard over your land and sticking a flag at every intersection. Then, you connect the dots with straight lines (linear interpolation).

The Assumption: Everyone thought this "checkerboard" method was the gold standard. It's easy, organized, and works great for smooth, wavy hills (like sine waves).
The Paper's Finding: For convex hills, the checkerboard method is actually suboptimal (not the best). It's like trying to measure a curved bowl with a rigid, square ruler; you miss the nuances of the curve.

2. The New Discovery: Breaking the Grid

The authors found that to get the best possible map of a convex landscape, you need to break the rules:

Don't use a grid: You shouldn't place your flags in a neat, uniform pattern.
Don't use a straight line: You shouldn't just draw straight lines between the flags.
The Solution: You need to place your flags in a smart, irregular pattern (specifically, a pattern that clusters more flags near the edges of the map) and use a non-linear method to draw the terrain.

The Analogy:
Imagine you are trying to guess the shape of a bowl by poking it with a stick.

The Grid Method: You poke the bowl in a perfect grid pattern. You miss the steep curves near the rim because your sticks are too far apart there.
The New Method: You realize the bowl gets steeper near the edges. So, you place your sticks very close together near the rim and spread them out in the flat middle. You also realize the surface isn't straight; it curves. So, you draw a curve that hugs the "tightest" possible shape that fits your data. This gives you a much more accurate picture of the bowl.

3. The Two Types of Landscapes

The paper studies two types of convex landscapes:

Class L (The Gentle Slope): These are hills where the slope never gets too steep (the "subgradient" is bounded). Think of a gentle, rolling hill.
Class B (The Steep Cliff): These are hills that can get very steep near the edges, as long as the total height doesn't exceed a certain limit. Think of a bowl with very sharp, steep sides.

The Results:

For Gentle Slopes (Class L): If you use the old checkerboard grid, you get a decent map, but not the best one. If you use the new "smart, irregular" placement of flags, you get a significantly better map. The improvement is huge, especially in higher dimensions (like 3D or 4D space).
For Steep Cliffs (Class B): The old grid method fails even harder here. You must use a non-uniform grid (more flags near the edges) to get a good map. If you try to use a uniform grid, your error doesn't even get smaller as you add more flags in certain scenarios (specifically for measuring the worst-case error).

4. Linear vs. Non-Linear: The "Straight Line" Trap

A major finding is about how you draw the map between the flags.

Linear Methods: These are like connecting the dots with a straight ruler. The paper proves that for convex functions, straight lines are often the wrong tool. They produce a "suboptimal" map.
Non-Linear Methods: These allow the map to curve and bend to fit the convex shape. The paper shows that non-linear methods are vastly superior for these specific types of functions. In fact, for some cases, the linear method is so bad that it's almost useless compared to the non-linear one.

5. The "Worst-Case" Guarantee

The paper doesn't just say "this works on average." It proves that no matter what the convex hill looks like (as long as it fits the rules), their new method guarantees a specific level of accuracy. They calculated exactly how fast the error shrinks as you add more flags.

The Rate: They found that with the right strategy, the error shrinks much faster than the old grid method allows. It's like upgrading from a blurry, low-resolution photo to a high-definition one just by changing where you took the picture.

Summary

In short, this paper tells us that when dealing with convex shapes (like bowls, hills, or optimization problems):

Stop using the checkerboard grid. It's too rigid.
Stop using straight lines to connect the dots.
Start using smart, irregular patterns of data points (clustering near edges) and curved, non-linear reconstruction.

This approach yields the most accurate possible reconstruction of the function, beating all previous "standard" methods. The authors also provided a practical algorithm (a recipe) for how to actually calculate this best-fit map using standard computer optimization tools, making it possible to use in real-world scenarios where these convex constraints exist.

Technical Summary: Sampling and Reconstruction of Convex Functions

1. Problem Statement

The paper addresses the problem of optimal recovery for multivariate convex functions defined on the unit cube $\Omega = [0, 1]^d$ . Given a set of $n$ point samples $\Lambda = \{x_1, \dots, x_n\}$ and the corresponding data vector $w = (f(x_1), \dots, f(x_n))$ , the goal is to construct an approximation $\tilde{f}$ that minimizes the worst-case recovery error in the $L_p$ norm ( $1 \le p \le \infty$ ).

The study focuses on two specific model classes of convex functions:

Class $B(\Omega)$ : Convex functions uniformly bounded by 1 ( $|f(x)| \le 1$ ).
Class $L(\Omega)$ : Convex functions uniformly bounded by 1 with uniformly bounded subgradients ( $|v| \le 1$ for all $v \in \partial f(x)$ ), which is equivalent to being 1-Lipschitz.

The primary objective is to determine the sampling numbers $\rho_n(K)_{L_p}$ , defined as the infimum of the worst-case error over all possible choices of $n$ sample sites and all recovery algorithms. The paper also investigates linear sampling numbers $\rho_n^\ell(K)_{L_p}$ , where the recovery algorithm is restricted to be linear.

2. Methodology

The authors employ a combination of approximation theory, convex geometry, and probabilistic methods to establish upper and lower bounds for the sampling numbers.

2.1 Tensor Product Grids and Linear Methods

Initially, the paper analyzes the performance of standard uniform tensor product grids and piecewise multilinear interpolation.

Upper Bounds: For the class $L$ , uniform grids yield an error rate of $O(n^{-r/d})$ where $r = 1 + 1/p$ . For the class $B$ , non-uniform tensor grids (graded near the boundary) are required to achieve the same rate.
Lower Bounds: The authors construct specific counter-examples (using "hinge" functions or modified convex functions) to prove that these rates are optimal if one is restricted to tensor product grids or linear recovery methods.

2.2 Non-Linear and Non-Tensor Sampling

To determine the true optimal rates, the paper moves beyond tensor grids.

Existence of Optimal Sets: Using probabilistic arguments, the authors prove the existence of specific sets of data sites $\Lambda_n^*$ $Λ_{n}^{*}$ (which are not tensor product grids) that satisfy two key geometric properties:
1. Any closed convex set with no sample points in its interior has a volume bounded by $O(\frac{\log n}{n})$ .
2. The set forms an $\epsilon$ -net with $\epsilon \approx n^{-1/d}$ .
Error Analysis: By analyzing the difference between two convex functions that agree on these specific sites, the authors derive sharper upper bounds for the sampling numbers. This involves covering the region where the functions differ with convex sets and utilizing properties of subgradients and polar sets (referencing Mahler's inequality).

2.3 Constructive Recovery Algorithms

While the existence of optimal rates relies on non-constructive probabilistic proofs, Section 6 proposes a computationally feasible, near-optimal recovery algorithm.

Supremum Property: The algorithm exploits the fact that the classes $L$ and $B$ are closed under pointwise suprema.
Formulation: The recovery map $A_\Lambda(w)$ is defined as the pointwise supremum of all functions in the model class that satisfy the data constraints (and boundedness constraints).
Implementation: This infinite-dimensional optimization problem is reduced to a finite-dimensional one. The recovery function is shown to be the supremum of a set of affine functions satisfying linear (for $B$ ) or conic (for $L$ ) constraints. This allows the recovery to be computed via Linear Programming (for $B$ ) or Conic Programming (for $L$ ).

3. Key Contributions and Results

3.1 Suboptimality of Standard Methods

A central finding is that for convex functions, standard procedures that are optimal for classical smoothness classes (like Sobolev or Hölder spaces) are suboptimal.

Tensor Grids: For $1 < p < \infty$ and $d \ge 2$ , sampling on uniform tensor product grids yields a rate of $n^{-(1+1/p)/d}$ . However, the optimal rate is faster.
Linear Methods: Linear recovery methods are significantly worse than nonlinear ones. Specifically, for $p=2$ , the linear sampling number decays as $n^{-3/2d}$ , whereas the optimal nonlinear rate is $n^{-2/d}$ (up to logarithmic factors).

3.2 Optimal Sampling Rates

The paper establishes the optimal decay rates for the sampling numbers $\rho_n(K)_{L_p}$ (up to logarithmic factors):

For $1 \le p \le d$ : The rate is $n^{-2/d}$ .
For $p \ge d$ : The rate is $n^{-(1+d/p)/d}$ .
Combined: The optimal rate is characterized by $n^{-\tilde{r}/d}$ where $\tilde{r} = \min\{2, 1 + d/p\}$ .

These rates are achieved by using specific, non-tensor product sampling sets and nonlinear reconstruction methods.

3.3 Specific Cases

$p=1$ and $p=\infty$ : The optimal rates can be achieved using tensor product grids and linear methods.
$p=2$ : The linear sampling number $\rho_n^\ell(L)_{L_2}$ decays as $n^{-3/2d}$ , while the optimal nonlinear rate is $n^{-2/d}$ . This highlights a substantial gap between linear and nonlinear recovery for convex functions.
Class $B$ vs. $L$ : While $L \subset B$ , the optimal sampling rates for both classes are essentially the same for $p < \infty$ . However, for $p=\infty$ , the sampling numbers for $B$ do not decay to zero ( $\rho_n(B)_{L_\infty} \asymp 1$ ), whereas for $L$ they decay as $n^{-1/d}$ .

4. Significance and Claims

The paper claims to characterize the optimal rate of decay for sampling numbers of convex functions, resolving the discrepancy between standard grid-based methods and the theoretical optimum.

Nonlinearity is Essential: The work demonstrates that for convex functions, nonlinear reconstruction methods significantly outperform linear methods and standard tensor grid sampling for most $p$ values. This contrasts with classical smoothness classes where linear methods on uniform grids are often optimal.
Connection to Entropy: The optimal sampling rates derived ( $n^{-2/d}$ for $p \le d$ ) match the decay rates of the entropy numbers for these classes. This suggests that the sampling numbers for convex functions are governed by the same complexity measures as entropy, unlike some classical smoothness classes where sampling numbers can decay faster than entropy numbers.
Constructive Algorithms: The paper provides a practical, stable, and near-optimal recovery algorithm based on convex optimization (supremum of affine functions), which is applicable even to noisy data.

The authors note that while the existence of optimal sampling sets is proven via probabilistic methods, the explicit construction of such sets remains an open area, though the proposed recovery algorithm works for any set of sites and achieves near-optimal performance when the sites are chosen according to the theoretical requirements.