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.

Assumptions

  • $V$ is a vector of sets $V_1,V_2,...,V_n$ of numbers:
  • $V=[V_1, V_2,..., V_n]^T, \forall_{i=1..n}V_i\subset\mathbb{R}$
  • $c\in\mathbb{R}$ is constant
  • $d(V,c)$ is an error metric: $d(V,c)=\sqrt[p]{\sum_{i=1}^{n}\min_{v\in{V_i}}(|v-c|)^p}$
  • $p\in\mathbb{N}\backslash\{0\}$
  • $c^*=\arg\min_c{d(V,c)}$

Interpretation

$V$ is a template for vector of numbers $W$, where $V_i$ sets represent acceptable values for corresponding $i$ positions in the vector $W$. E.g. for $V=[\{1,2\},\{2,3\}]^T$, possible $W$ values are $[1,2]^T,[1,3]^T,[2,2]^T,[2,3]^T$.

$c$ is constant (scalar), that substituting all elements of $W$, e.g. $W=C=[c,c]^T$ causes an error $d(V,c)$ for template $V$. Note that it is not required to $c$ be an element of set $\bigcup_i{V_i}$ (it may be any real number).

The error caused by $c$ is an minimal Minkowski distance over all possible values of $W$.

We look for $c$, such that the error caused by it is the smallest. We denote such $c$ as $c^*$.

The question

Is there a general algorithm that finds optimal $\mathbb{c}$ in polynomial time? I know that, there is an exhaustive search algorithm, but its complexity is not acceptable complexity.

Solution for $p=1$

The problem seems to be easy for $p=1$. In such case error metric transforms to $\sum_{i=1}^n{\min_{v\in{V_i}}|v-c|}$. Note that sum of linear functions is an linear function, so:

  • $\forall_{i=1..n}$ sort $V_i$
  • Let $X_i=V_i\cup{V_i'}$, where $V_i'$ is set of averages of consecutive values in $V_i$. E.g. for $V_i=\{1,2,3\}$, $V_i'=\{1.5,2.5\}$. In other words $X_i$ is a set of points, where segmentally linear error function $d(V,c)$ breaks.
  • $X=\bigcup_{i=1..n}{X_i}$
  • $c^*=\arg\min_{c\in{X}}d(V,c)$ (Since $d(V,c)$ is segmentally linear, the minimum may be located only in point, where function breaks).

So, $O(|X|)=O(\bigcup_{i=1..n}V_i)$, assuming $V_i$s are sorted, the entire algorithm works in $O(n\log{n})$, where $n=\bigcup_{i=1..n}V_i$.

Unfortunately the above algorithms does not work for Euclidean distance, or other Minkowski distances, since the breaking points of $d(V,c)$ cannot be obtained in the above way.

share|improve this question

1 Answer 1

Actually, almost the same approach can be used for $p>1$. The only exception is that the set $X$ should be treated as the set of endpoints of consecutive intervals and you'll need to find the minimum within each interval instead of knowing it has to occur at one of the endpoints (as is the case with $p=1$).

Since the $p$-th root in the definition of the metric does not play any role when it comes to optimality, it's sufficient to consider the sum itself. Within each interval, the sum simplifies to a polynomial of degree $p$. Finding the minimum value of the polynomial within an interval can be done explicitly if $p$ is small enough (trivial for $p=2$, quadratic formula for $p=3$, possibly going up to $p=5$ with Cardano and Ferrari), but for higher values of $p$, you might have to resort to approximate, numeric solutions (bisection, Newton-Raphson, ...).

share|improve this answer

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.