Simple Function Approximation by Quantizing Values

Truncating and Quantizing Values

A simple function has only finitely many values. A measurable function, by contrast, may take infinitely many values and may be unbounded. To approximate a nonnegative measurable function by simple functions, we perform two operations: first cap its values at a finite level, then round the capped values down to a dyadic grid. Increasing the cap and refining the grid together gives a sequence that increases to the original function.

Let $(X,\mathcal{M},\mu)$ be any measure space; no assumption of finiteness, sigma-finiteness, or completeness is needed. In this tutorial, functions are measurable and take values in $[0,\infty]$, and pointwise statements hold at every $x\in X$, not merely almost everywhere. A simple function means a measurable function with finite range.

Definition: For each integer $n\ge1$, define the truncated, dyadically quantized function $\varphi_n:X\to[0,\infty)$ by $$ \varphi_n(x)=2^{-n}\left\lfloor 2^n\min(f(x),n)\right\rfloor. $$ Here $\min(\infty,n)=n$, and $\lfloor r\rfloor$ is the greatest integer less than or equal to the real number $r$.

The truncation ensures that $\varphi_n$ has finite range: its values belong to $\{k2^{-n}:k=0,1,\ldots,n2^n\}$. Rounding down ensures $\varphi_n(x)\le \min(f(x),n)$. The grid at stage $n+1$ is finer than the grid at stage $n$, while the truncation level also increases. We now check that these operations give simple functions and preserve measurability.

Finite Range and Measurability

Proposition: For every $n\ge1$, $\varphi_n$ is a measurable simple function. More precisely, with $N_n=n2^n$, define $$ B_{n,k}=\{x:k2^{-n}\le f(x)<(k+1)2^{-n}\}\quad(0\le k<N_n), \qquad B_{n,N_n}=\{x:f(x)\ge n\}. $$ These are disjoint measurable sets whose union is $X$, and $$ \varphi_n=\sum_{k=0}^{N_n-1}k2^{-n}\chi_{B_{n,k}}+n\chi_{B_{n,N_n}}. $$

Proof. Each $B_{n,k}$ is the inverse image under the measurable function $f$ of a Borel interval in $[0,\infty]$; $B_{n,N_n}$ is the inverse image of $[n,\infty]$. Thus all these sets belong to $\mathcal{M}$. The intervals $[k2^{-n},(k+1)2^{-n})$, for $0\le k<N_n$, are pairwise disjoint and together cover $[0,n)$. The remaining values, including $n$ and $\infty$, form $[n,\infty]$. Consequently the sets $B_{n,k}$ are disjoint and cover $X$. On $B_{n,k}$ for $k<N_n$, truncation does not change $f(x)$, and rounding down gives $k2^{-n}$. On $B_{n,N_n}$, the truncated value is $n$, which is already on the grid. The displayed finite sum therefore equals $\varphi_n$ everywhere. It is measurable as a finite linear combination of indicators of measurable sets and has finite range, so it is simple. $\square$

Worked Example: A Function on a Three-Point Space

Let $X=\{a,b,c\}$ with the counting measure and $\mathcal{M}$ equal to the power set of $X$. Define $f(a)=0$, $f(b)=5/4$, and $f(c)=\infty$. Compute the first three approximations.

At $n=1$, the cap is $1$ and the grid spacing is $1/2$. Thus $\min(f(a),1)=0$, $\min(f(b),1)=1$, and $\min(f(c),1)=1$. These are already grid values, so $(\varphi_1(a),\varphi_1(b),\varphi_1(c))=(0,1,1)$.

At $n=2$, the cap is $2$ and the spacing is $1/4$. The capped values are $0,5/4,2$, all on this grid. Hence $(\varphi_2(a),\varphi_2(b),\varphi_2(c))=(0,5/4,2)$. At $n=3$, the spacing is $1/8$; the capped values are $0,5/4,3$, again grid values. Thus $(\varphi_3(a),\varphi_3(b),\varphi_3(c))=(0,5/4,3)$.

Check: At each point the values increase: $0=0=0$, $1\le5/4=5/4$, and $1\le2\le3$. At $a$ and $b$ the sequence reaches $f$; at $c$, its values are $n$ at stage $n$, so they tend to $\infty=f(c)$.

Error Bound and Increasing Convergence

Proposition: For every $n\ge1$ and $x\in X$, $$ 0\le \min(f(x),n)-\varphi_n(x)<2^{-n}. $$

Proof. Put $r=2^n\min(f(x),n)$, which is a finite nonnegative real number because $\min(f(x),n)\le n$. The defining property of the floor gives $\lfloor r\rfloor\le r<\lfloor r\rfloor+1$. Multiplying by $2^{-n}>0$ yields $$ \varphi_n(x)\le\min(f(x),n)<\varphi_n(x)+2^{-n}. $$ Subtracting $\varphi_n(x)$ proves both inequalities, including the strict upper bound. $\square$

Theorem: For every measurable $f:X\to[0,\infty]$, the simple functions $(\varphi_n)$ defined above satisfy $\varphi_n(x)\le\varphi_{n+1}(x)$ for every $x\in X$, and $\varphi_n(x)\to f(x)$ for every $x\in X$. No assumption on the measure $\mu$ is required.

Proof. Fix $x\in X$ and write $a=\min(f(x),n)$ and $b=\min(f(x),n+1)$. Then $0\le a\le b$, and both are finite. Therefore $2^{n+1}b\ge 2^{n+1}a=2(2^na)$. The floor function is increasing, and $\lfloor2r\rfloor\ge2\lfloor r\rfloor$ for every real $r$: indeed, $r\ge\lfloor r\rfloor$ implies $2r\ge2\lfloor r\rfloor$, where $2\lfloor r\rfloor$ is an integer. It follows that $$ \varphi_{n+1}(x) =2^{-(n+1)}\lfloor2^{n+1}b\rfloor \ge 2^{-(n+1)}\,2\lfloor2^na\rfloor =\varphi_n(x). $$ This proves monotonicity, including when $f(x)=\infty$.

If $f(x)=t<\infty$, then for every integer $n\ge t$, $\min(t,n)=t$. The error bound just proved gives $0\le t-\varphi_n(x)<2^{-n}$. Since $2^{-n}\to0$, $\varphi_n(x)\to t=f(x)$. If $f(x)=\infty$, then $\min(f(x),n)=n$, and $n2^n$ is an integer, so $\varphi_n(x)=2^{-n}(n2^n)=n$. Hence $\varphi_n(x)\to\infty=f(x)$. These cases cover every possible value of $f(x)$, proving pointwise convergence everywhere. $\square$

Worked Example: Quantizing a Function on the Unit Interval

Take $X=[0,1]$, its Lebesgue sigma-algebra, Lebesgue measure $m$, and $f(x)=2x$. Compute $\varphi_1$ and $\varphi_2$, specifying the endpoints of the sets on which they are constant.

For $n=1$, the cap is $1$ and the spacing is $1/2$. If $0\le x<1/4$, then $0\le2x<1/2$, so the rounded value is $0$. If $1/4\le x\le1$, then $2x\ge1/2$, and its value after capping at $1$ rounds down to $1/2$. In particular, at $x=1$ the capped value is $1$, which also rounds to $1/2$. Thus $$ \varphi_1(x)= \begin{cases} 0,&0\le x<1/4,\\ 1/2,&1/4\le x\le1. \end{cases} $$

For $n=2$, the cap is $2$ and the spacing is $1/4$. For each $k=0,1,\ldots,7$, the condition $k/4\le2x<(k+1)/4$ is equivalent to $k/8\le x<(k+1)/8$. The remaining set where $2x\ge2$ is just $\{1\}$. Therefore $\varphi_2(x)=k/4$ on $[k/8,(k+1)/8)$, for $k=0,\ldots,7$, and $\varphi_2(1)=2$.

Check: At $x=3/8$, $f(x)=3/4$. The first approximation is $1/2$, since $3/8\ge1/4$; the second is $3/4$, since $3/8\in[3/8,4/8)$. Thus $\varphi_1(3/8)\le\varphi_2(3/8)\le f(3/8)$, with values $1/2\le3/4=3/4$. The intervals above also include their lower endpoint and exclude their upper endpoint, as required by rounding down.

Worked Example: An Unbounded Function

On $X=[0,1]$ with its Lebesgue sigma-algebra and Lebesgue measure, define $f(0)=\infty$ and $f(x)=1/x$ for $0<x\le1$. This is a nonnegative measurable extended real-valued function. Compute its approximations at $x=2/5$ and $x=0$.

At $x=2/5$, $f(x)=5/2$. For $n=1$, the cap gives $\min(5/2,1)=1$, so $\varphi_1(2/5)=1$. For $n=2$, the capped value is $2$, so $\varphi_2(2/5)=2$. For $n=3$, the value is not capped, and $2^3(5/2)=20$, giving $\varphi_3(2/5)=20/8=5/2$. For every $n\ge3$, $5/2$ is a multiple of $2^{-n}$, so the approximation remains exactly $5/2$.

At $x=0$, the function value is $\infty$. Thus $\varphi_n(0)=2^{-n}\lfloor2^n n\rfloor=n$ for every $n\ge1$, and these values tend to infinity. Check: the displayed values at $2/5$ are $1\le2\le5/2$, while at $0$ the sequence is $1,2,3,\ldots$. This illustrates how each approximation remains finite-valued even though the function is unbounded and takes the value infinity.

A Common Mistake: Rounding Without Truncating

Rounding alone does not necessarily produce a simple function. For example, let $X=[0,\infty)$ with its Borel sigma-algebra and Lebesgue measure, and let $f(x)=x$. At fixed $n$, the untruncated expression $2^{-n}\lfloor2^nf(x)\rfloor$ takes the distinct values $k2^{-n}$ at $x=k2^{-n}$, for every integer $k\ge0$. It therefore has infinitely many values and is not simple.

The correction is to cap the function before rounding. With the cap at $n$, the possible outputs are only $0,2^{-n},\ldots,n$, a finite set. The cap does not spoil convergence: at each point where $f(x)$ is finite, it eventually lies below the cap, and where $f(x)=\infty$, the capped values increase to infinity. The finite-range property and pointwise convergence thus come from distinct parts of the construction.

Check Your Understanding

For each question, use the cap and grid at the stated stage, and distinguish the terminal set $\{f\ge n\}$ from the half-open rounding intervals below $n$.

For a measurable $f:X\to[0,\infty]$, write the measurable sets on which $\varphi_n$ takes each of its possible values.
Let $f(x)=7/4$. Compute $\varphi_1(x)$, $\varphi_2(x)$, and $\varphi_3(x)$.
Explain why the inequality $\lfloor2r\rfloor\ge2\lfloor r\rfloor$ implies that the approximations increase when both the cap and grid change.
For $f(0)=\infty$, determine $\varphi_n(0)$ and its limit.
Give an unbounded measurable function for which rounding without truncation has infinitely many values, and explain how truncation changes its range.

Simple Function Approximation by Quantizing Values

What You'll Learn