Quantizing Bounded Functions by Simple Functions

From Bounded Values to a Finite Range

A bounded measurable function can take infinitely many different values, even when it is supported on a set of finite measure. Quantization replaces its values by points on a fixed grid. The resulting function has only finitely many values, while its error is controlled by the grid spacing. This gives a concrete approximation procedure and, when the support has finite measure, a direct bound in $L^p$.

Throughout, let $(X,\mathcal{M},\mu)$ be any measure space; no completeness or sigma-finiteness assumption is needed. Fix $1\le p<\infty$. Let $E\in\mathcal{M}$ satisfy $\mu(E)<\infty$, and let $f:X\to\mathbb{R}$ be measurable, vanish outside $E$, and satisfy $|f(x)|\le M$ for every $x\in E$, where $M<\infty$. These assumptions ensure that $f\in L^p(\mu)$: indeed, $|f|^p\le M^p\chi_E$, so $\int |f|^p\,d\mu\le M^p\mu(E)<\infty$. A finite-valued measurable function is one whose range is finite; equivalently, it is a simple function.

Definition: Given a mesh size $\delta>0$, quantize $f$ downward by setting $q_\delta(x)=0$ for $x\notin E$, and $q_\delta(x)=\delta\lfloor f(x)/\delta\rfloor$ for $x\in E$. Here $\lfloor t\rfloor$ is the greatest integer not exceeding $t$.

Rounding downward is useful because it gives the pointwise inequalities $q_\delta(x)\le f(x)<q_\delta(x)+\delta$ on $E$, including for negative values. Since $f$ is bounded on $E$, only finitely many grid values can occur. Measurability follows because the sets on which each grid value occurs are measurable: for an integer $k$, the corresponding set inside $E$ is $E\cap\{k\delta\le f<(k+1)\delta\}$.

The Quantization Error Bound

Theorem: Under the assumptions above, $q_\delta$ is a finite-valued measurable function, vanishes outside $E$, and belongs to $L^p(\mu)$. Pointwise on $X$, $$ |f-q_\delta|\le \delta\chi_E, $$ and consequently $$ \|f-q_\delta\|_p\le \delta\,\mu(E)^{1/p}. $$ The conclusion includes $\mu(E)=0$, in which case the $L^p$ error is zero.

Proof. Choose an integer $N\ge M/\delta$. For $x\in E$, the integer $\lfloor f(x)/\delta\rfloor$ lies between $-N$ and $N$. Thus $q_\delta$ takes values among the finite set $\{0\}\cup\{\delta k:-N\le k\le N,\ k\in\mathbb{Z}\}$. For each integer $k$, the set where $q_\delta=\delta k$ is $E\cap\{k\delta\le f<(k+1)\delta\}$, except that the value zero can also occur outside $E$. Each such set is measurable because $f$ is measurable and $E\in\mathcal{M}$. The zero set is measurable as well. Hence $q_\delta$ is measurable and finite-valued. Since it is bounded and vanishes outside $E$, $|q_\delta|^p$ is bounded by a finite constant times $\chi_E$, so $q_\delta\in L^p(\mu)$.

For $x\in E$, the defining property of the floor gives $0\le f(x)-q_\delta(x)<\delta$. For $x\notin E$, both $f(x)$ and $q_\delta(x)$ equal zero. Therefore $|f-q_\delta|\le\delta\chi_E$ everywhere. Raising this nonnegative inequality to the power $p$ gives $|f-q_\delta|^p\le\delta^p\chi_E$. Integrating and using $\int\chi_E\,d\mu=\mu(E)$ yields $$ \|f-q_\delta\|_p^p=\int|f-q_\delta|^p\,d\mu \le\delta^p\mu(E). $$ Taking the $p$-th root proves the claimed estimate. If $\mu(E)=0$, the same inequality gives $\|f-q_\delta\|_p^p\le0$, so the norm is zero. $\square$

The estimate supplies a direct way to select a mesh. If $0<\mu(E)<\infty$ and $\eta>0$ is a desired error tolerance, choosing $\delta=\eta/(2\mu(E)^{1/p})$ gives $\|f-q_\delta\|_p\le\eta/2<\eta$. If $\mu(E)=0$, every positive mesh gives zero $L^p$ error. The pointwise quantization still works in that case, although values on $E$ do not affect the $L^p$ norm.

Worked Example: A Piecewise-Constant Function on a Finite Interval

Let $X=[0,4]$ with Lebesgue measure, $E=X$, $p=2$, and $\delta=1/2$. Define $f$ to equal $1/5$ on $[0,1)$, $11/10$ on $[1,2)$, $-3/5$ on $[2,3)$, and $19/10$ on $[3,4]$. The bound $|f|\le19/10$ holds on $E$, and $\mu(E)=4$.

On the four pieces, respectively, the floor computations are $\lfloor(1/5)/(1/2)\rfloor=\lfloor2/5\rfloor=0$, $\lfloor(11/10)/(1/2)\rfloor=\lfloor11/5\rfloor=2$, $\lfloor(-3/5)/(1/2)\rfloor=\lfloor-6/5\rfloor=-2$, and $\lfloor(19/10)/(1/2)\rfloor=\lfloor19/5\rfloor=3$. Thus $q_\delta$ takes the values $0,1,-1,3/2$ on those pieces. The absolute errors are $1/5,1/10,2/5,2/5$, respectively. Each piece has measure $1$, so

\|f-q_\delta\|_2^2 =1\left(\frac15\right)^2 +1\left(\frac1{10}\right)^2 +1\left(\frac25\right)^2 +1\left(\frac25\right)^2 =\frac4{100}+\frac1{100}+\frac{16}{100}+\frac{16}{100} =\frac{37}{100}.

Hence $\|f-q_\delta\|_2=\sqrt{37}/10$. The theorem gives the bound $(1/2)\cdot4^{1/2}=1$. The computed error is below this bound because $37/100<1$. As a further check, on each piece the squared error is the square of the difference between the displayed value of $f$ and the displayed value of $q_\delta$; summing those four contributions reproduces $37/100$.

Worked Example: Quantizing the Identity Function

Take $X=E=[0,1]$ with Lebesgue measure, $f(x)=x$, $p=2$, and mesh $\delta=1/4$. For $k=0,1,2,3$, $q_\delta(x)=k/4$ on $[k/4,(k+1)/4)$, and $q_\delta(1)=1$. The endpoint $x=1$ has measure zero and does not change the integral.

On each of the four intervals, the error $x-q_\delta(x)$ runs from $0$ up to, but not including, $1/4$. The integral of its square on each interval is $\int_0^{1/4}t^2\,dt=(1/4)^3/3=1/192$, by the substitution $t=x-k/4$. Therefore

\|f-q_\delta\|_2^2=4\cdot\frac1{192}=\frac1{48}, \qquad \|f-q_\delta\|_2=\frac1{\sqrt{48}}.

The theorem gives $\|f-q_\delta\|_2\le(1/4)\cdot1^{1/2}=1/4$. This is consistent with the exact value, since $1/48<1/16=(1/4)^2$. The exact integral also checks the calculation by summing the four equal interval contributions rather than estimating the error pointwise.

Worked Example: Downward Rounding of a Negative Constant

Let $X=\mathbb{R}$ with Lebesgue measure, $E=(0,2)$, $p=1$, and $f(x)=-5/4$ on $E$, with $f(x)=0$ outside $E$. Use $\delta=1/2$. On $E$, $\lfloor f(x)/\delta\rfloor=\lfloor(-5/4)/(1/2)\rfloor=\lfloor-5/2\rfloor=-3$, so $q_\delta=-3/2$ on $E$, and $q_\delta=0$ outside.

The error on $E$ is $|-5/4-(-3/2)|=|-5/4+6/4|=1/4$. Since $\mu(E)=2$, direct integration gives $\|f-q_\delta\|_1=2\cdot(1/4)=1/2$. The theorem gives $\delta\mu(E)=(1/2)\cdot2=1$, so the computed error satisfies the bound. The floor is $-3$, not $-2$: rounding $-5/2$ toward zero would not be the floor operation used in this construction.

Why the Assumptions and the Measure Factor Matter

The finite-measure support is what turns a uniform pointwise error into an $L^p$ estimate. In the proof, the key calculation is $\int\delta^p\chi_E\,d\mu=\delta^p\mu(E)$. If $\mu(E)=\infty$, this upper bound is infinite and gives no finite $L^p$ error estimate. For example, on $\mathbb{R}$, quantizing the constant function $f=1/4$ on all of $\mathbb{R}$ with mesh $\delta=1$ gives $q_\delta=0$ everywhere. The pointwise error is $1/4$, but its $p$-th power has infinite integral for every finite $p$.

Boundedness is what makes the quantized function finite-valued for a fixed positive mesh. If a function takes arbitrarily large values, its downward quantization can use infinitely many grid levels. For instance, $f(x)=1/x$ on $E=(0,1)$ is measurable but unbounded; with mesh $1$, the values $\lfloor1/x\rfloor$ are unbounded as $x$ approaches zero. Thus this construction alone does not yield a finite-valued function for that $f$. The boundedness and finite-measure support conditions play separate roles: the first controls the number of output values, and the second controls the $L^p$ error.

A frequent mistake is to infer $\|f-q_\delta\|_p\le\delta$ from the pointwise bound $|f-q_\delta|\le\delta\chi_E$, omitting the measure of $E$. For a direct counterexample, let $E=[0,16)$ with Lebesgue measure, $p=2$, mesh $\delta>0$, and $f=\delta/2$ on $E$, zero outside. The quantizer is $q_\delta=0$ on $E$, since $\lfloor(\delta/2)/\delta\rfloor=\lfloor1/2\rfloor=0$. Its error norm is $(\int_E(\delta/2)^2\,dm)^{1/2}=((16\delta^2/4))^{1/2}=2\delta$, which is larger than $\delta$. The correct estimate includes the support factor: $\delta\mu(E)^{1/2}=\delta\cdot4=4\delta$, and indeed $2\delta\le4\delta$.

Quantization is a specific approximation method with an explicit error bound. It applies once a function has a bounded representative supported on a finite-measure set. It does not by itself address how to reduce a general $L^p$ function to that setting; the present result concerns the finite-range approximation after those properties are available.

Check Your Understanding

Use the definition of the floor quantizer and the error theorem to answer these questions.

If $f$ is bounded by $M$ on $E$, why can only finitely many multiples of a fixed $\delta>0$ occur as values of $q_\delta$?
For $p=3$, $\mu(E)=8$, and mesh $\delta=1/10$, what upper bound does the theorem give for $\|f-q_\delta\|_3$?
On $E$, compute the quantized value and error when $f=-7/10$ and $\delta=1/4$.
Which assumption ensures that the quantizer has finite range, and which assumption supplies the finite measure factor in the $L^p$ estimate?
Why does a pointwise error bound of $\delta$ not imply an $L^p$ error bound of $\delta$ on every finite-measure support?

Quantizing Bounded Functions by Simple Functions

What You'll Learn