Prev: convert to polar coordinate
Next: Region boundary extraction post-edge detection
From: Jason on 21 May 2010 11:28
"Matt J " <mattjacREMOVE(a)THISieee.spam> wrote in message <ht624t$p6b$1(a)fred.mathworks.com>...
> "Jason" <jf203(a)ic.ac.uk> wrote in message <ht5si9$ipb$1(a)fred.mathworks.com>...
>
> >
> > Bruno, it is quite clearly quadratic.
> > And it's quite clear that you minimize x, i.e. find the values of x that minimize x' Q x.
> >
> > If something is not clear in your mind then don't blame me.
> =================
>
> No it is not quadratic. You are trying to find the simultaneous *root* of 3 quadratic functions (one for each ellipse), not their minimum. To do this, you wrote down a cost function J in which you square all the quadratics for each ellipse and add them up. This leads to a 4th order function polynomial in x, not a 2nd order one

Well it depends on how you define your cost function. lsqnonlin will automatically sum of squares. other methods might not.

In any case, Bruno, I wanted to ask you something else.

I did what you said, i.e. setting x_3 = 1 and x_3 = 0 and then compute two different cost functions.

Also you said we can set x_1 = t * cosd (alpha) and x_2 = t * sind (alpha).

This means that x_1 = x_2 cosd(alpha)/sind(alpha) right ? So if we set beta = cosd(alpha)/sind(alpha) then we have in the first case (x_3 = 0):

J_1 (x_2) = [beta*x_2 x_2 0]*Q*[[beta*x_2 x_2 0]^T

If I do the multiplications correctly then that gives me a polynomial of degree 2 ?! Of course lsqnonlin will sum the squares which would make this degree 4, but what I am saying is correct right?

Also you said I should compute J_1 for each value of alpha from 0:0.1:180 which would make the problem about 1800 iterations for finding x_2. I can then simply find x_1 by computing beta*x_2 and we know that x_3 in this case is 0. Repeat all this for the case that x_3 is 1. Which means 3600 iterations in total.

Have I understood you correctly?

The part which troubles me a bit is when you say: " I can do this in a loop over a finely sampled range of angles alpha, say alpha=0:0.1:180, until I find a good approximation of the global minimum over all alpha and t and hence over all
x(1) and x(2)."

Over all alpha, ok, but over all t ? Haven't I taken t out of the picture here?

Kind regards,
Jason
From: Matt J on 22 May 2010 11:41
"Jason" <jf203(a)ic.ac.uk> wrote in message <ht68q6$mcu$1(a)fred.mathworks.com>...

> Well it depends on how you define your cost function. lsqnonlin will automatically sum of squares. other methods might not.
=====================

That's true, but the cost function you've defined here, and the only one we've been talking about in this thread, is the one used by lsqnonlin. This is for good reason. It would be highly non-standard and take considerable ingenuity to find a simpler cost function for this root-finding problem than what lsqnonlin uses.


> In any case, Bruno, I wanted to ask you something else.
==============

Not Bruno. Me.


> I did what you said, i.e. setting x_3 = 1 and x_3 = 0 and then compute two different cost functions.
>
> Also you said we can set x_1 = t * cosd (alpha) and x_2 = t * sind (alpha).
>
> This means that x_1 = x_2 cosd(alpha)/sind(alpha) right ?
================

This manipulation requires a division operation that is only valid for t~=0 and alpha~=0.

It was not my intention that you do this. My intention was that you substitute both
x_1 = t * cosd (alpha) and x_2 = t * sind (alpha)
into the cost function so that, with x_3 and alpha held fixed, the cost function would become a function of t, not x_2.

The result is virtually the same - you end up with a 1D 4th order polynomial to minimize.
However, in your approach, you have to worry about beta being infinite...


So if we set beta = cosd(alpha)/sind(alpha) then we have in the first case (x_3 = 0):
>
> J_1 (x_2) = [beta*x_2 x_2 0]*Q*[[beta*x_2 x_2 0]^T
>
> If I do the multiplications correctly then that gives me a polynomial of degree 2 ?! Of course lsqnonlin will sum the squares which would make this degree 4, but what I am saying is correct right?
===================

You shouldn't be using lsqnonlin for this. lsqnonlin does not know how to minimize anything analytically, even a simple 1D polynomial. You should be writing your own routine to do this.

To keep this discussion clear, it would also be a good idea if you stop treating lsqnonlin as the thing that's defining the cost function. WE are defining the cost function for this problem and it is the multi-variable 4th order polynomial

J(x)=sum_i (x' * Q{i} *x)^2

There is no other obvious and more tractable alternative to this cost function for the task you've described.


> Also you said I should compute J_1 for each value of alpha from 0:0.1:180 which would make the problem about 1800 iterations for finding x_2. I can then simply find x_1 by computing beta*x_2 and we know that x_3 in this case is 0. Repeat all this for the case that x_3 is 1. Which means 3600 iterations in total.
===============

One other thing. It has occured to me that you don't really have to do this for the case x_3=0

In this case, the remaining unknowns x_1 and x_2 can also be normalized with impunity so that x_1=1 or x_2=1 as long as one of these is non-zero. So, you can subdivide the case x_3=0 into 2 more subcases

(1) x_1=1, x_3=0
(2) x_2=1, x_3=0

In each of these sub-cases, the cost function reduces to a 1D polynomial again, which you can minimize trivially.
From: Jason on 22 May 2010 19:42
"Matt J " <mattjacREMOVE(a)THISieee.spam> wrote in message <ht8tug$sjj$1(a)fred.mathworks.com>...
> "Jason" <jf203(a)ic.ac.uk> wrote in message <ht68q6$mcu$1(a)fred.mathworks.com>...
>
> > Well it depends on how you define your cost function. lsqnonlin will automatically sum of squares. other methods might not.
> =====================
>
> That's true, but the cost function you've defined here, and the only one we've been talking about in this thread, is the one used by lsqnonlin. This is for good reason. It would be highly non-standard and take considerable ingenuity to find a simpler cost function for this root-finding problem than what lsqnonlin uses.
>
>
> > In any case, Bruno, I wanted to ask you something else.
> ==============
>
> Not Bruno. Me.
>
>
> > I did what you said, i.e. setting x_3 = 1 and x_3 = 0 and then compute two different cost functions.
> >
> > Also you said we can set x_1 = t * cosd (alpha) and x_2 = t * sind (alpha).
> >
> > This means that x_1 = x_2 cosd(alpha)/sind(alpha) right ?
> ================
>
> This manipulation requires a division operation that is only valid for t~=0 and alpha~=0.
>
> It was not my intention that you do this. My intention was that you substitute both
> x_1 = t * cosd (alpha) and x_2 = t * sind (alpha)
> into the cost function so that, with x_3 and alpha held fixed, the cost function would become a function of t, not x_2.
>
> The result is virtually the same - you end up with a 1D 4th order polynomial to minimize.
> However, in your approach, you have to worry about beta being infinite...
>
>
> So if we set beta = cosd(alpha)/sind(alpha) then we have in the first case (x_3 = 0):
> >
> > J_1 (x_2) = [beta*x_2 x_2 0]*Q*[[beta*x_2 x_2 0]^T
> >
> > If I do the multiplications correctly then that gives me a polynomial of degree 2 ?! Of course lsqnonlin will sum the squares which would make this degree 4, but what I am saying is correct right?
> ===================
>
> You shouldn't be using lsqnonlin for this. lsqnonlin does not know how to minimize anything analytically, even a simple 1D polynomial. You should be writing your own routine to do this.
>
> To keep this discussion clear, it would also be a good idea if you stop treating lsqnonlin as the thing that's defining the cost function. WE are defining the cost function for this problem and it is the multi-variable 4th order polynomial
>
> J(x)=sum_i (x' * Q{i} *x)^2
>
> There is no other obvious and more tractable alternative to this cost function for the task you've described.
>
>
> > Also you said I should compute J_1 for each value of alpha from 0:0.1:180 which would make the problem about 1800 iterations for finding x_2. I can then simply find x_1 by computing beta*x_2 and we know that x_3 in this case is 0. Repeat all this for the case that x_3 is 1. Which means 3600 iterations in total.
> ===============
>
> One other thing. It has occured to me that you don't really have to do this for the case x_3=0
>
> In this case, the remaining unknowns x_1 and x_2 can also be normalized with impunity so that x_1=1 or x_2=1 as long as one of these is non-zero. So, you can subdivide the case x_3=0 into 2 more subcases
>
> (1) x_1=1, x_3=0
> (2) x_2=1, x_3=0
>
> In each of these sub-cases, the cost function reduces to a 1D polynomial again, which you can minimize trivially.

Matt, yes, sorry about this!

Re: My intention was that you substitute both
> x_1 = t * cosd (alpha) and x_2 = t * sind (alpha)
> into the cost function

Yes, just realized that before you answered. Got you now!

However I do not understand your last point:

> One other thing. It has occured to me that you don't really have to do this for the case x_3=0
>
> In this case, the remaining unknowns x_1 and x_2 can also be normalized with impunity so that x_1=1 or x_2=1 as long as one of these is non-zero. So, you can subdivide the case x_3=0 into 2 more subcases.

Could you elaborate this a little bit please, I'm not sure I get you. You are basically saying than when x_3 = 0 then x_1 and x_2 ~= 0 ?

I don't really understand.

Thanks!
From: Matt J on 23 May 2010 10:24
"Jason" <jf203(a)ic.ac.uk> wrote in message <ht9q4c$jbj$1(a)fred.mathworks.com>...

> Could you elaborate this a little bit please, I'm not sure I get you. You are basically saying than when x_3 = 0 then x_1 and x_2 ~= 0 ?
>
> I don't really understand.
=========

It's the same equivalence class consideration associated with homogeneous coordinates that we already said made the space of solutions with x3~=0 equivalent to the space of solutions with x3=1.

Once you restrict the search to the space x_3=0, it means you are searching for a solution of the form (x1, x2, 0). Suppose we restrict this search further to the subspace of solutions of the form (x1,x2,0) and for which x1~=0. Each of the solutions in this subspace are equivalent to a solution of the form
(1,x2/x1,0) or more simply (1,z,0). Therefore, you can just as well restrict the search to the subspace (1,x2,0)

You can do the same thing for the subspace {x2~=0, x3=0}
It is equivalent to the subspace {x2=1, x3=0}
First  |  Prev  | 
Pages: 1 2 3 4 5 6 7
Prev: convert to polar coordinate
Next: Region boundary extraction post-edge detection