An Errata to: Convergence of a SOR-Weiszfeld Type Algorithm for Incomplete Data Sets

Abstract

We discovered an error in our proof of convergence of a generalization of the Weiszfeld algorithm to incomplete data sets, and we provide here a partial correction, with slightly weaker claims.

CORRECTIONS

The proof of [1, Theorem 5.5], attempting to prove convergence for the Weiszfeld method for incomplete data sets, includes a few errors of “hasty generalization” of the corresponding proofs for the standard method [2, 3]. In summary, the problem is that (a) if a subsequence of iterates approaches a non-optimal point q at zero distance from multiple vertices, the next iterate might not consistently “deflect” from always the same vertex, and (b) it is possible to get arbitrarily close to these vertices while staying outside a ball around q, whence once an iterate is inside this ball, it can take arbitrarily long to get back outside.

• (a) The result of [1, Lemma 5.3] only holds as a limit supremum, and not as a full limit: there exists some k ∊ π_∞\π′ such that lim sup _{p→p ∞} d _k (p′)/d _k (p) > 1. Equivalently, as we may apply the argument to any subsequence of a limiting sequence,

  The reason for this modification of the claim is that the values f _i passed to [1, Lemma 5.2] are dependent on the direction of approach to p _∞, and thus the “deflecting” k could differ for different directions.

  However, we can also improve the claim of the lemma slightly: if ρ _k ρ _i  = ρ₀ (that is, the operator mapping all coordinates to φ) for all k, i ∊ π_∞\ π′, then h(·; p _∞) is independent on the range of each ρ _k . Therefore, applying [\citealp{1}, Lemma 5.2] to the corresponding subproblem, we can actually get the deflection property for all k ∊ π_∞\ π′, such that h(ζ ρ _k z; p _∞) < 0 for some z. Hence, in this case, for some k, actually lim ∊ f _{p→p ∞} d _k (p′)/d _k (p) > 1.

• (b) There is also an error in the application of the above-mentioned [1, Lemma 5.3] in the proof of [1, Theorem 5.5]. In the case of the standard Weiszfeld method with complete data, the equivalent result would show that if q = a _k is not optimal, there exists a δ > 0 and ∊ > 0, such that if d(q, p _r ) < δ, then d _k (p _r ′) > (1 + ∊)d _k (p _r ). This would mean that once the former holds, then d _k (p _s ) for s > r grows until d(q, p _s ) = d _k (p _s ) > δ. The whole sequence could not therefore converge to q. There could, however, exist a subsequence {p _{r ℓ} } such that d _k (p _{r ℓ} ) = d(q, p _{r ℓ} ) > δ and d _k (p _{r ℓ} ′) → 0, but then we'd reach a contradiction from

  where the last term would be greater than w _k δ/2 for r = r _ℓ.

  In our situation with incomplete data, we have the problem that d(q, p _{r ℓ} ) > δ does not imply d _k (p _{r ℓ} ′) > δ′ for k ∊ π(q). There may actually exist another subsequence convergent to  ≠ q, also with k ∊ π(), but with different “deflecting” vertex  ≠ k. Therefore, even if the deflecting k ∊ π(q)\ π′ provided by [\citealp{1}, Lemma 5.3] were the same for the subsequence approaching q (such as under the additional range independence assumption), d _k (p _{r ℓ} ) may actually be arbitrarily small, and consequently d(q, p _s ) < δ for s > r _ℓ, may also become arbitrarily small until d _k (p _s ) has grown large enough to counteract this.

  Thus, in order to reach a contradiction, we have to make assumptions that ensure k ≠ in π(), whence the part of {p _r } not clustering at q must be far enough in d _k , that a contradiction can be reached by (1). [In fact, (1) shows that when there are cluster points with π(q) ≠ π(), there must be infinitely many of them.] Alternatively, cluster points with k ∊ π() must share it as a deflecting vertex. However, a common deflecting vertex for the whole sequence {p _r } suffices to contradict its assumed convergence (to a non-optimal point).

• (c) Combining the above observations, we get the following corrected claim.

Assumption 1

(i) ρ _k ρ _i  = ρ₀ whenever k, i ∊ π(p), k ≠ i, for any p ∊ ℝ ^m . (ii) #π (p) ≤ 1 for all p ∊ ℝ ^m .

Theorem 2 (Correction of Theorem 5.5 of [1])

Let p ₀ be given and . Suppose ω _r  ∊ [1, ω′] for fixed ω′ < 2 = Ω(p _r ), and that eventually π (p _r ′) ⊃ π(p _r ) (which can be satisfied by suitable choice of step size). If Assumption 1(i) holds, then either , or {p _r } diverges. If Assumption 1(ii) holds, then .

Proof

We have slightly strengthened the assumption on the step lengths to ensure eventual constant π(p _r ) and (p _r ) = 0 for any subsequence. Virtually the same proof as before shows that this can be done.

The final claim involving Assumption 1(ii) demands some clarification: there may still exist a set Q _k of cluster points q with π(q) = {k}. But now, if we did not have lim ∊ f _r d _k (p _{r ℓ} ′)/d _k (p _{r ℓ} ) > 1 for the subsequence {p _{r ℓ} } of {p _r } (π (p _{r ℓ} ) = ) approaching Q _k , we could (by boundedness) extract a further subsequence convergent to q ∊ Q _k with h(·, q) ≥ 0 ((q) = 0), and thus pass to the next step of the proof to show that q is optimal. Therefore, we may replace q by Q _k in the above deflection arguments.