Piecewise-Linear Approximations of Uncertain Functions

We study the problem of approximating a function F: ℝ → ℝ by a piecewise-linear function

$\overline{\mathrm{F}}$

when the values of F at {

x

1

,…,

x

n

} are given by a discrete probability distribution. Thus, for each

x

i

we are given a discrete set

$y_{i,1},\dots,y_{i,m_i}$

of possible function values with associated probabilities

p

i

,

j

such that

Pr

[F(

x

i

) = 

y

i

,

j

] = 

p

i

,

j

. We define the error of

$\overline{\mathrm{F}}$

as

$\mbox{\sl error}(\mathrm{F},\overline{\mathrm{F}}) = \max_{i=1}^n \mathbf{E}[|\mathrm{F}(x_i)-\overline{\mathrm{F}}(x_i)|]$

. Let

$m=\sum_{i=1}^n m_i$

be the total number of potential values over all F(

x

i

). We obtain the following two results: (i) an

O

(

m

) algorithm that, given F and a maximum error

ε

, computes a function

$\overline{\mathrm{F}}$

with the minimum number of links such that

$\mbox{\sl error}(\mathrm{F},\overline{\mathrm{F}}) \leq \epsilon$

; (ii) an

O

(

n

4/3 + 

δ

 + 

m

log

n

) algorithm that, given F, an integer value 1 ≤ 

k

 ≤ 

n

and any

δ

 > 0, computes a function

$\overline{\mathrm{F}}$

of at most

k

links that minimizes

$\mbox{\sl error}(\mathrm{F},\overline{\mathrm{F}})$

.