|[eigen] SVD for finding a basis for the nullspace of a wide matrix|
[ Thread Index |
| More lists.tuxfamily.org/eigen Archives
- To: eigen@xxxxxxxxxxxxxxxxxxx
- Subject: [eigen] SVD for finding a basis for the nullspace of a wide matrix
- From: "Keir Mierle" <mierle@xxxxxxxxx>
- Date: Fri, 14 Nov 2008 01:23:41 -0800
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:received:message-id:date:from:to :subject:mime-version:content-type; bh=OLvOlJn5VrJSABMrH3ap1rqezzdcdi3rnmY+SzkeBoM=; b=JU0915JLbzcbLoIDIsVnSJANrKyIPokQDfbkGFkw4BpDiHheGDY9r7E3wJz5DLYXK0 o6svQsbC1xmfTDooCyyOKV2HjyMv3jiOMGv2LEy896Do6nHKAwclTq5ZeMfYQ5NB986s KHXPyy4ooMEFceFIy3oYqZAtLpReEKM6DcO2A=
- Domainkey-signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=message-id:date:from:to:subject:mime-version:content-type; b=EKxn+aCKOj5/LPXda0+nB/oX3OGkjcPlLOwWy96GLXyVNF7u380awnvuujaWTfmuuH gC25rD6mzcIZD5NLTsia9gnYOUdrrjrtEkXDCzOpGA1ZjpXO97m5gIurRiqMxjGtDsq4 T8Gc/vp2NQJRdA0hPsc4BgO/XGeFjBqeNfGDw=
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.