# Approximation in $L^2$ by piecewise constant functions

Dear all, I'd like to know if there is any general result on the approximation of $L^2$ functions by piecewise constant functions. More specifically, I'd like to know if the following approximability property is correct

for all $w\in V$, $\lim_{h\rightarrow 0}\inf_{w^h\in V^h}||w-w^h||=0$,

where $V=L^2([0, 1]^d)$, $V^h$ is the space of piecewise constant functions on a regular (orthogonal grid), with step $h$.

Could you point to any reference ?

-
Note that the continuous functions are dense in $V$ and your set of piecewise constant functions is dense in the set of continuous functions (even under the sup-norm), so the property is indeed true. A reference for the first statement is any book on measure theory. For example Rudin's "Real and Complex Analysis". The second is an easy exercise. –  Sam Apr 27 '11 at 3:32
OK, I like your argument. I think that the proof of this result is not so obvious for a continuous function. However, it can easily be proved on $H^1$ thanks to the Poincaré inequality. Then using the fact that $C^\infty$ is dense in $L^2$ and embedded in $H^1$, the result can be extended to $L^2$. What do you think of this proof? Is is too convoluted? –  Sebastien Apr 27 '11 at 18:07

Let $1>\epsilon > 0$ be given. Let $w\in V$ be arbitrary. Since you know that $C^\infty$ is dense in $V$, let $f \in C^\infty$ be a smooth function such that

$$\Vert w - f \Vert_2 < \epsilon/2$$

Now since $f$ is continuous on the compact set $[0,1]^d$, by uniform continuity there exists $\delta >0$ such that for all $x,y \in [0,1]^d$

$$|x-y| < \delta \; \implies \; |f(x) - f(y)| < \epsilon/2$$

Now let $h$ be small enough, so that on each cube of the grid, the maximal distance of points is smaller than $\delta$. Then by choosing $w^h \in V^h$ to take on an arbitrary value of $f$ in each cube where $w^h$ is constant, we have

$$\Vert f - w^h \Vert_\infty^2 < \left(\epsilon/2\right)^2 \le \epsilon/2$$

Hence

\begin{eqnarray*} \Vert w - w^h \Vert_2 &\le& \Vert w - f\Vert_2 + \Vert f - w^h \Vert_2 \\ &\le& \Vert w - f\Vert_2 + \lambda([0,1]^d) \cdot \Vert f - w^h \Vert_\infty \\ &<& \frac \epsilon 2 + \frac \epsilon 2 = \epsilon \end{eqnarray*}

So that $V^h$ must be dense in $V$.

-
Excellent! Thanks very much for taking the time to write down the proof. There is a french say: do not use a jackhammer to drive a nail... That's surely what I did with Poincaré's inequality. Uniform continuity is much, much more elegant! Thanks again. –  Sebastien Apr 28 '11 at 18:40

By "step $h$" I assume you mean the spacing of your grid points, i.e. $w^h$ is a linear combination of indicators of boxes of the form $\prod_i (x_i, x_i + h]$, where $x_i$ is perhaps an integer multiple of $h$, or something like that. Then yes, it is true, and follows a standard approximation argument. I'm too lazy to write the details here, but if you look up a proof that step functions are dense in $L^2$, essentially the same argument applies. The key is that the set of all your boxes generates the Borel $\sigma$-algebra on $[0,1]^d$.

-
Indeed, your asumptions are correct. Sorry for not being more accurate. So "density" seems to be the answer, but in my problem, $h$ is initially fixed (and then tends to zero), so it's not strictly speaking a density argument, is it? However, as you suggest, the details of the proof of density may probably be recycled here. –  Sebastien Apr 27 '11 at 3:57
OK, I've looked up Rudin (has been seating a long time in my bookshelves...). It seems that the construction of the approximating step function assumes a discretization of the image of the function, not of its domain. In my case, I need to define an approximation of the L2 function on a specified grid. –  Sebastien Apr 27 '11 at 10:36
My claim is that for any $\epsilon$, there is a grid sufficiently fine and a $w^h$ on that grid such that $||w-w^h|| < \epsilon$. This implies your statement, and is also equivalent to the set of all $w^h$ being dense. (There is a small argument in between that you can always make the grid finer without hurting the approximation; for instance if you make the grid twice as fine, you can use the same function.) –  Nate Eldredge Apr 27 '11 at 12:41
Thanks very much for your answer. Your claim does not seem obvious to me. It seems to me that Rudin proves that for any $epsilon>0$, there is a step function $s$ such that $||w-s||<\epsilon$. His proof doesn't say anything on the "layout" of the steps. In particular, it does not state that $s$ is piecewise constant over the cells of a grid. Maybe I'm missing a very obvious argument, my math is a bit rusty. –  Sebastien Apr 27 '11 at 18:04