Unique solution to system of generalized eigenvector problems

Thread view:

Enable EMail Alerts

Start New Thread

Thread rating:

cv_curious - 04 Oct 2008 19:20 GMT

Suppose we have the following sequence of equations:

Fi k = alpha_i Ai k

where we know that alpha_i > 0, all Fi and Ai are 6x6 having rank 3
and the column space of both Fi and Ai is the same for all i. All Fi
and Ai are known. All alpha_i and k are unknown and we are interested
in finding k. Each equation represents an instance of the generalized
eigenvector problem. Unfortunately, since Fi and Ai are of rank 3
having the same column space, each problem has infinitely many
solutions and is thus severely under-constrained. The question is, is
it possible to solve uniquely for k from the whole system of problems
(as opposed to just a single problem)? And if so, how?

The solution to the above problem can seriously simplify camera auto-
calibration where I have posed this problem in a manner not posed up
till now.

Reply to this Message

Ilya Zakharevich - 05 Oct 2008 01:03 GMT

[A complimentary Cc of this posting was sent to
cv_curious
<phdscholar80@yahoo.com>], who wrote in article <gc8c60$rt$1@dizzy.math.ohio-state.edu>:

> Suppose we have the following sequence of equations:
>
> Fi k = alpha_i Ai k
>
> where we know that alpha_i > 0, all Fi and Ai are 6x6 having rank 3
> and the column space of both Fi and Ai is the same for all i.

So, essentially, (after taking a basis in this column space) you have

(Fi' - alpha_i Ai') k = 0

with 3x6 matrices Fi' and Ai'.

> All Fi and Ai are known. All alpha_i and k are unknown and we are
> interested in finding k.

So for each i, you get a certain cone of possible solutions for k; for
generic Fi', Ai', the cone is going to have dimension 4 (swapped by
planes of dimension 3, one for each fixed alpha_i). Codimension is
<=2 (it is 2 provided that for every alpha_i, the rank of the linear
combination above is 3).

[Hmm, since you do not allow alpha_i = infinity (which means the
extra possible equation Ai k = 0), the cone is not going to be
closed. This may slightly complicate the analysis below - you may
get some "spurious" solutions, which, as usual, you would need to
"plug back" into the original equations.]

> Each equation represents an instance of the generalized
> eigenvector problem. Unfortunately, since Fi and Ai are of rank 3
> having the same column space, each problem has infinitely many
> solutions and is thus severely under-constrained. The question is, is
> it possible to solve uniquely for k from the whole system of problems
> (as opposed to just a single problem)? And if so, how?

Note that if the solution is unique, it is k=0. The codimension is
bounded by 2*N from above, so you need N >= 3 for uniqueness. To
solve, you need to find the (dimension of the) intersection of cones.

Most symbolic manipulation programs which can deal with algebraic
equations would be able to solve this. You need to ask them to
"eliminate variables alpha_i" from the equations above.

Hope this helps,
Ilya

Reply to this Message

cv_curious - 06 Oct 2008 12:38 GMT

> Most symbolic manipulation programs which can deal with algebraic
> equations would be able to solve this. ?You need to ask them to
> "eliminate variables alpha_i" from the equations above.
>
> Hope this helps,
> Ilya

Let us denote the jth row of matrix M as M^j. Then, to eliminate
alpha_i from

Fi k = alpha_i Ai k

I would need to assume that

(Ai)^j k != 0 (where != is used to mean 'not equal to').

Keep in mind that if this were reasonable then the ordinary
generalized eigenvalues problem could be solved in the same manner.
But people use the QZ algorithm instead. I am looking for a similar
approach. I have read that for singualr matrices, the GUPTRI algorithm
is used to solve the generalized eigenvalues problem. I was hoping
that someone has extended this research to include the case of a
system of problems. Maybe I should ask over at sci.math.num-analysis???

Reply to this Message

Math Forum / Mathematics / Research / October 2008

Unique solution to system of generalized eigenvector problems