3

Let $G$ be a class of $\it{indicator}$ functions where $g\in G$ implies that $g : X \rightarrow \{0,1\}$, where the domain $X$ is a compact subset of $\mathbf{R}^n$. For example:

$$ g(x) = 0 \text{ if } w_1x_1+\cdots+w_dx_d < \eta $$ $$ g(x) = 1 \text{ otherwise } $$

Note: I am not interested in this particular class. This is just an example.

Is there a theorem that would say something like below?

Theorem: Let $G$ be an arbitrary class of $\it{indicator}$ functions with properties IMPORTANT TEXT MISSING. Then for any $f : X \rightarrow \mathbf{R}$ which is NICELY BEHAVING IN SOME SENSE and any $\epsilon$ a linear combination $h=w_1g_1+\cdots+w_kg_k$ (of elements in $G$) can be found such that $\vert h(x)-f(x)\vert<\epsilon$ for all $x\in X$.

Any hint highly appreciated!

EDIT: A possible answer might be found here but I am not sure. It all depends whether my understanding of the discussed theorem is correct.

Community
  • 1
zorank
  • 275
  • Uniform convergence of linear combinations of indicator functions do not converge to anything interesting. If your metric of interest was $L^p$ then we could start to have a lot of conversations. – John Feb 17 '15 at 16:19
  • ok, but can a given (fixed) class of such functions can approximate anything useful? For example, if I tell you what the class is, could you tell me whether it could approximate anything useful? In fact by anything useful, I mean any function. What would you check to figure it out? p.s. I am not a mathematician, so my question might feel silly, but there is a background to it. – zorank Feb 17 '15 at 16:23
  • another question, please bear with me, why do you insist on $L^p$, i.e. want to avoid uniform convergence (point by point) and instead want to go to integrals? My naive understanding is that if I have a bounded functions then the integral can be converted to max bound (sup): $\int(h-f)dx<\max{h-f}\int dx$. – zorank Feb 17 '15 at 16:25
  • You added "nicely behaving" after I posted my comment. My training (long ago) was in real analysis and measure theory, in that field, you use finite sums of indicator functions to prove everything. Restricting yourself to nicely behaving means that yes, there are lots of possibilities, but your question is too open ended for me to help you. Providing more of your context will help you get better answers. – John Feb 17 '15 at 16:30
  • regarding the example: well, I've given it above. Can the class of theta functions approximate any function? That would be an example. Such questions are often posed when various classification models are studied. Just the very fact that you are referring to the measure theory seems I was on the right track... – zorank Feb 17 '15 at 16:39
  • hmmm... a potential problem: uniform convergence seems to imply $L^2$ convergence, but not necessairly the other way around. so my argument that it does not matter what one looks at (uniform convergence versus integrals) is probably not correct. but then the question is, is there a class of functions for which the reverse is also true? I suppose one should avoid discontinuities that are badly behaving. – zorank Feb 17 '15 at 16:48
  • If by "nicely behaving" you mean, "functions that are continuous" then L2 and uniform convergence is equivalent on compact domains. I do not know however if the sets you specified above could be used to approximate any continuous function on a compact domain in R^n. – John Feb 17 '15 at 16:56
  • here is a potential problem: indicator functions are not continuous. they are piecewise continuous. would your argument still hold for piecewise continuous functions? for example if I have two linear combinations of indiator functions $h_1$ and $h_2$, can I say that uniform convergence/closenes is equivalent to L2 convergence/closenes? – zorank Feb 17 '15 at 17:01

1 Answers1

2

For sake of an answer, let's assume by nicely behaved you mean "piecewise continuous and bounded functions on a compact subset of $R^n$."

The metric you've stated an interest in is the uniform convergence metric.

Arbitrary indicator functions can approximate piece wise continuous functions uniformly. For example, if you are interested in an $\epsilon$ approximation, create a partition $r_i$ of the real line with norm less than $\epsilon.$ Then let your indicator sets $A$ be $A_i = \{ x | r_{i-1} <= f(x) < r_i\}$.

But, you seem to be interested in a space that's more restrictive than "half open / closed subsets of $R^n$" (which is what is required for the above to work.)

The space $G$ has to be able to generate arbitrarily small sets, that don't overlap (so half open intervals on the dyadics are a good example). For continuous functions that is a sufficient characterization.

For piece wise continuous functions, your space $G$ has to be able to "exactly" model the discontinuities. So, for example, in $R^2$ if you have discontinuities on the line $y=x$, you cannot piecewise approximate it if the space of $G$ indicator functions is made up of half open rectangles.

John
  • 482