6

I have some distribution X of values (which I don't know exactly but I can sample many times). I also have a function $f : X \to Y$ which may be complicated. I want to approximate $f$ with a piecewise constant function $g$, where the number of pieces is constant but I can choose the intervals, and where I minimize $|f - g|^2$.

Is this a studied problem? Are there some relatively simple ways of doing this in a good way?

amWhy
  • 209,954
Andrey
  • 61
  • 1
    Given the breakpoints in $g$, the value in a given interval should be just the average of all $f$ values in that interval. It comes down to choosing the breakpoints. I don't know any way better than a multidimensional minimizer, but maybe somebody does. – Ross Millikan Jun 01 '11 at 02:35
  • I'm not entirely clear what your motivation is, or the nature of the function $f$, or how you hope to apply your desired piecewise function. etc. Also, are you speaking, strictly, of a piecewise "constant" function (step function), or are you thinking about a piecewise "linear" function? – amWhy Jun 01 '11 at 02:37
  • based on @Ross's answer, I'm assuming you mean strictly a piecewise constant function. I don't have any additional suggestions other than what Ross has offered. – amWhy Jun 01 '11 at 02:42
  • Do you want to minimize the expected value of $|f-g|^2$? Or $\sup_{x\in X}|f(x)-g(x)|^2$, or something else? – mac Jun 01 '11 at 08:33
  • Yes, I mean strictly a piecewise constant function. Let's say I want to minimize the expected value of |f-g|^2, although I would be happy with anything like that. – Andrey Jun 01 '11 at 22:00
  • This is a studied problem: Konno, Hiroshi, and Takahito Kuno. "Best piecewise constant approximation of a function of single variable." Operations research letters 7.4 (1988): 205-210. – Wouter May 10 '20 at 06:25

0 Answers0