Oriented linear least-squares
in [Math]
|
Prev: roots to *any* polynomial
Next: JSH: Using Usenet
From: Kaba on 18 Jun 2010 20:01 Robert Israel wrote: > > Can you see a way to approach this problem? > > If a solution of the non-oriented version has det(A) > 0, then > that does it. Otherwise, there will be no solution. > But you might want to make the constraint det(A) >= 0, in which case > you might get a solution with det(A) = 0 using a Lagrange multiplier. Yes, I actually meant det(A) >= 0. How do you know the minimizing A must have det(A) = 0? -- http://kaba.hilvi.org
From: Kaba on 18 Jun 2010 20:41 Robert Israel wrote: > Kaba <none(a)here.com> writes: > > > E = sum_{i = 1}^n || Ap_i - r_i ||^2 > note that the objective > is convex in A, so any local minimum is a global minimum. I can't see that E is convex in A: Let x = Ap_i - r_i y = Bp_i - r_i t in [0, 1] subset R <((1 - t)A + tB)p_i - r_i> = <(1 - t)(Ap_i - r_i) + t(Bp_i - r_i)> = <(1 - t)x + ty> = (1 - t)^2 <x> + 2t(1 - t)<x, y> + t^2 <y> ....? <= (1 - t) <x> + t<y> -- http://kaba.hilvi.org
From: Kaba on 18 Jun 2010 21:08 Kaba wrote: > Robert Israel wrote: > > > Can you see a way to approach this problem? > > > > If a solution of the non-oriented version has det(A) > 0, then > > that does it. Otherwise, there will be no solution. > > But you might want to make the constraint det(A) >= 0, in which case > > you might get a solution with det(A) = 0 using a Lagrange multiplier. > > Yes, I actually meant det(A) >= 0. How do you know the minimizing A must > have det(A) = 0? Oh, I see: this follows from the convexity of E. Assume the non-oriented solution A' has det(A') < 0. Then if the oriented solution A has det(A) > 0, we can interpolate between A' and A to give smaller E, contradicting minimality. Now I just need a proof for the convexity of E... -- http://kaba.hilvi.org
From: Kaba on 19 Jun 2010 09:37
Kaba wrote: > Robert Israel wrote: > > Kaba <none(a)here.com> writes: > > > > E = sum_{i = 1}^n || Ap_i - r_i ||^2 > > > note that the objective > > is convex in A, so any local minimum is a global minimum. > > I can't see that E is convex in A: > > Let > x = Ap_i - r_i > y = Bp_i - r_i > t in [0, 1] subset R > > <((1 - t)A + tB)p_i - r_i> > = <(1 - t)(Ap_i - r_i) + t(Bp_i - r_i)> > = <(1 - t)x + ty> > = (1 - t)^2 <x> + 2t(1 - t)<x, y> + t^2 <y> = <x> - 2t <x> + t^2 <x> + t^2 <y> + 2t(1 - t)<x, y> = (1 - t)<x> - t<x> + t^2 <x> + (t<y> - t<y>) + t^2 <y> + 2t(1 - t)<x, y> = (1 - t)<x> + t<y> - t(1 - t)(<x> + <y>) + 2t(1 - t)<x, y> = (1 - t)<x> + t<y> - t(1 - t)(<x> + <y> - 2<x, y>) = (1 - t)<x> + t<y> - t(1 - t)(<x - y>) <= (1 - t)<x> + t<y> -- http://kaba.hilvi.org |