Re: [eigen] SVD for finding a basis for the nullspace of a wide matrix

[Benoît Jacob <jacob@xxxxxxxxxxxxxxx>]

Hi,

I admit I never looked into SVD decomposition algorithms and was happy that 
Gael at least took the public domain code from JAMA so we have at least 
something for now. As Gael said it's meant as a temporary solution.

I have one question. From what you say it seems that a LU decomposition is 
really what you want, no? From what you say below it seems like you want to 
find a basis of the kernel (nullspace) of a 3x4 matrix. Eigen's LU module 
allows you to that already, the syntax is m.lu().kernel():

http://eigen.tuxfamily.org/api/classEigen_1_1LU.html#64cf46c69c9aab1ad26faf5600502708

See also computeKernel() if you prefer a C-style function avoiding to return a 
matrix by value.

Of course I understand there may be other reasons why you really want a SVD 
here.

Cheers,
Benoit

On Friday 14 November 2008 10:23:41 Keir Mierle wrote:
> Right now the SVD, which computes A = USV^T for a mxn matrix A with m >= n,
> produces a square V n x n and rectangular U m x min(n,m). However, for 
> many applications it is necessary to compute the extra columns of U, such
> that U is m x m. For example, in computer vision a (very) common operation
> is to take the SVD of a 3x4 matrix (call it P), row-deficient, in order to
> find the null vector. With a SVD that requires m >= n, this is done by
> taking the SVD of P^T and using U to find the nullvector X such that PX = 0
> and ||X|| = 1. However, if U is not computed fully, this is not possible.
> In other words, the current Eigen SVD isn't useful for solving
> underdetermined homogeneous linear systems (Ax = 0 with A wide rather than
> tall).
>
> I looked into extending the existing SVD code but sadly it's pretty opaque.
> The various papers about implementing the SVD aren't easy either, and I
> don't have a week sink into it. Is anyone working on eigen familiar with
> the SVD algorithms? I may be able to do it in less time with a bit of help.
>
> Thanks,
> Keir



---