0
$\begingroup$

I am looking for a reference to a solution of the multivariate piecewise linear interpolation. I am not quite sure how to generalize a well-known dynamic programming Segmented Least Squares algorithm.

The exact version I'd like is this. Let B be a box $[1,a_1]\times[1,a_2]\times ... \times[1,a_k]\subset\mathbb{Z}^k$, and consider a function $f:B\to\mathbb{R}$, that is given to us at some points of the box. Also, given to us some penalty factor $P>0$. The problem is to find $k$ partitions $1=b_{i0}\lt b_{i1}\lt b_{i2}\lt ...\lt b_{in_k}=a_k$ of the segments $[1,a_i]$ into subintervals so that when the function is interpolated at each $k$-dimensional segment $[b_{1j_1},b_{1(j_1+1)}-1]\times[b_{2j_2},b_{2(j_2+1)}-1]\times ...\times[b_{kj_k},b_{k(j_k+1)}-1]$ the value sum of errors for each segment + $P\times \#segments$ is minimized.

I would be happy with a 3-dimensional version (function of 2 variables), which I think will be easy to generalize.

Improve this question
$\endgroup$
6
  • $\begingroup$ Thanks for the edit! I'm struggling to understand the notation. What does $b_{k0}$ represent? Do you mean $b_{i0}$ where $1 \le i \le k$, so each segment $[1,a_i]$ can be segmented differently? How are functions to be interpolated at each $k$-dimensional segment -- do you have some specific way in mind (e.g., interpolation on all points that fall within that segment where the value of $f$ is known), or do you want the solution to specify a linear function for each $k$-dimensional segment? What do you want to do if none of the points in the segment have a known value of $f$? $\endgroup$
    – D.W. ♦
    Nov 15, 2021 at 21:48
  • $\begingroup$ This is just a $k$-dimensional grid, and yes, the grid can be non-uniform. I think the actual method of interpolation is not too important. What I am looking is for an algorithm to optimally partition the box to minimize the error. So, suppose I have a way of calculating the error for any particular segment, for example if the segment contains no points we can set the error to 0. So, we can actually forget about the function itself and work with the error function defined on the set of all segments contained in the box. We probably could use the fact that the error function is sub-additive. $\endgroup$
    – lanskey
    Nov 15, 2021 at 23:07
  • $\begingroup$ Do you mean that you are willing to accept any answer that uses any method of interpolation? That seems hard for me to accept. For instance, if my method of interpolation was "interpolate using all of the known data points", that will lead to the same multilinear function in all segments, which makes the problem solvable but also trivial. You say you want to minimize the error, but you need to define how you plan to measure the error; that's not defined in the question. Also, you haven't answered my question about $b_{k0}$ vs $b_{i0}$. $\endgroup$
    – D.W. ♦
    Nov 16, 2021 at 3:52
  • $\begingroup$ One more question: do you intend to require that the piecewise linear function be continuous, i.e., the two linear functions for two separate segments must agree on the boundary share? $\endgroup$
    – D.W. ♦
    Nov 16, 2021 at 3:56
  • $\begingroup$ Regarding the $b_{ij}$ question, I spotted a mistake in my notation. Yes, $b_{ij}$ belongs to the partition on $j$-s axis, and each axis can be segmented in any way, a partition consisting of the whole segment only is also allowed. $\endgroup$
    – lanskey
    Nov 16, 2021 at 21:43

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.