Approximation of a function wth piecewise constant functions

[Suresh Venkatasubramanian]

On Mon, 8 Dec 2003, andreas wrote:

> Hello,
>
> I have 100 values between 0 and 255.
> I want to approximate this function
> with 10 non-overlapping intervals,
> where the degree of freedom is
> * the  start and endpoint
> * the value associated to the interval.
>
> This is probably a classical problem
> but I got no reply on sci.op-research.
>
> Thanks in advance,
>
> andreas
>
>

You didn't mention the error function: assuming it is some kind of least
squares, what you want a k-median solution (k=10 in this case). The
k-median problem in R^n with metric d is

Find k centers c_1, ... c_k such that the cost
\sum d(p_i, c_n(i)) is minimized, where c_n(i) is the center closest to
p_i.

In your case, you are looking to solve k-median on the line.

If your error metric is more of an l_infty kind of thing (i.e minimize the
max error), then this boils down to the k-center problem: same as the
above, except that you want to minimize the max error, rather than the
sum of errors.

There are a variety of algorithms for this problem depending on the
metric, so a search for k-median/k-center results should help narrow
things down a bit.

Suresh Venkatasubramanian, Ph: 973 360 8951 (o)
Member, Technical Staff    Web: http://www.research.att.com/~suresh/
AT&T Shannon Labs

"The guitar is the ideal instrument for anyone who is able to love
loneliness." --Angelo Gilardino

-------------
The compgeom mailing lists: see
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.