Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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 1 '11 at 2: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 1 '11 at 2: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 1 '11 at 2: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 1 '11 at 8: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 1 '11 at 22:00
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.