Thread Subject: Singular value decomposition

I am trying to simulate something I have read in a paper and it
requires me to find W such that

C*' * W = 0

where (.)*' means Hermitian transpose of (.).

C is a vector whose elements are the spreading code for a CDMA system
but that is not really important. If C is length N, W must have
dimension N x N.

The paper says I have to find W using singular value decomposition. It
said that W is a blocking matrix whose columns span the left nullspace
of C but I think that is just the above equation put into words. I
have searched on singular value deomposition but cannot find any
explanation that seems to fit what I am trying to solve, or maybe I
just don't understand it. I looked at matlab help for svd but that
didn't help me either.

Could anyone tell me how to find W. Preferably relating to matlab but
any explanation will do.

Thanks,

Steve

In article <4d3ee211.0108291525.66542627@posting.google.com>,
 steve41@totalise.co.uk (Steve) wrote:

> I am trying to simulate something I have read in a paper and it
> requires me to find W such that
>
> C*' * W = 0
>
> where (.)*' means Hermitian transpose of (.).
>
> C is a vector whose elements are the spreading code for a CDMA system
> but that is not really important. If C is length N, W must have
> dimension N x N.
>
> The paper says I have to find W using singular value decomposition. It
> said that W is a blocking matrix whose columns span the left nullspace
> of C but I think that is just the above equation put into words. I
> have searched on singular value deomposition but cannot find any
> explanation that seems to fit what I am trying to solve, or maybe I
> just don't understand it. I looked at matlab help for svd but that
> didn't help me either.
>
> Could anyone tell me how to find W. Preferably relating to matlab but
> any explanation will do.

Usually, you are given the NxN matrix W and you are trying to find the
vector C that solves the above equation. That is where the SVD of W
comes in.

$.02 -Ron Shepard

Actually, W should be of size N x (N-1).

Basically, the problem is asking you to find vectors that are orthogonal
to C (a vector A is orthogonal to C if C*'A = 0. Since C is an
N-dimensional vector, there is an (N-1)-dimensional subspace of
N-dimensional complex space, such that every vector in this subspace is
orthogonal to C. We can represent the (N-1)-dimensional subspace by a
collection of N-1 orthonormal basis vectors, and place each basis vector
into a column of W.

Now, when you compute the singular value decomposition of a matrix B,
you are solving for U (orthogonal),V (orthogonal), and S (diagonal),
where B = U*S*V'. Let's break this equation down by looking at each
column of U and V, and write V on the left hand side. This gives us:

B*V(:,i) = U(:,i)*S(i,i), for i = 1,...,N

If it turns out that B is a row vector (which it is in your case: B =
C*'), then it must be true that S(i,i) == 0 whenever any V(:,i) is
orthogonal to B (because either S(i,i) == 0, or U(:,i) = zeros(N,1), but
U(:,i) is a unit vector).

Therefore, if you compute the SVD of your vector C*' (in MATLAB:
[U,S,V]=svd(C');), then the last N-1 elements of the vector S should be
zeros. This means the last N-1 columns of V are all orthogonal to C',
and we know they are all orthogonal to each other, so W = V(:,2:end) is
an orthogonal basis for the null space of C'.

Summing up:

[U,S,V] = svd(C');
W = V(:,2:end); % or in general if C' is not a vector: W = V(:,S==0);

HTH,
Nathan Cahill

Steve wrote:
>
> I am trying to simulate something I have read in a paper and it
> requires me to find W such that
>
> C*' * W = 0
>
> where (.)*' means Hermitian transpose of (.).
>
> C is a vector whose elements are the spreading code for a CDMA system
> but that is not really important. If C is length N, W must have
> dimension N x N.
>
> The paper says I have to find W using singular value decomposition. It
> said that W is a blocking matrix whose columns span the left nullspace
> of C but I think that is just the above equation put into words. I
> have searched on singular value deomposition but cannot find any
> explanation that seems to fit what I am trying to solve, or maybe I
> just don't understand it. I looked at matlab help for svd but that
> didn't help me either.
>
> Could anyone tell me how to find W. Preferably relating to matlab but
> any explanation will do.
>
> Thanks,
>
> Steve

steve41@totalise.co.uk (Steve) writes:

> I am trying to simulate something I have read in a paper and it
> requires me to find W such that
>
> C*' * W = 0
>
> where (.)*' means Hermitian transpose of (.).

matlab denotes this with a plain '. (minor rant -- matlab gets this
issue extremely right. the ' is the dual operator which
for matrics over a complex field means complex conjugate transpose.
if you just want tranpose, use ".'". stuff like X.' * conj(Y) is the
hallmark of someone who knows enough math to be dangerous but doesn't
really know what they are doing.)

> C is a vector whose elements are the spreading code for a CDMA system
> but that is not really important. If C is length N, W must have
> dimension N x N.
>
> The paper says I have to find W using singular value decomposition. It
> said that W is a blocking matrix whose columns span the left nullspace
> of C but I think that is just the above equation put into words.

take SVD of C

[U,S,V] = svd(C)

now, C = U*S*V' and hence C' = V*S*U' (since S is real and symmetric).

look at S, it will have singular values in descending order from
something positive down to something small positive or zero. declare
the small stuff (less than some epsilon) to be zero (this accounts for
some round off error). say n of the last singlular values are
essentially zero. the last n rows of U' (i.e., last n columns of U)
are an orthonormal basis for the null space of C'. these n columns is
your W.

> I
> have searched on singular value deomposition but cannot find any
> explanation that seems to fit what I am trying to solve, or maybe I
> just don't understand it. I looked at matlab help for svd but that
> didn't help me either.
>
> Could anyone tell me how to find W. Preferably relating to matlab but
> any explanation will do.
>
> Thanks,
>
> Steve

--
J o h a n K u l l s t a m
[kullstam@ne.mediaone.net]
sysengr

Steve wrote:
>
> I am trying to simulate something I have read in a paper and it
> requires me to find W such that
>
> C*' * W = 0
>
> where (.)*' means Hermitian transpose of (.).
>
> C is a vector whose elements are the spreading code for a CDMA system
> but that is not really important. If C is length N, W must have
> dimension N x N.
>
> The paper says I have to find W using singular value decomposition. It
> said that W is a blocking matrix whose columns span the left nullspace
> of C but I think that is just the above equation put into words. I
> have searched on singular value deomposition but cannot find any
> explanation that seems to fit what I am trying to solve, or maybe I
> just don't understand it. I looked at matlab help for svd but that
> didn't help me either.

W isn't square, the paper either has an error, or you might have
misunderstood.

The block matrix | C W | is square. You could use the SVD to find the
null space of C, but you can use the qr() routine as well. Do a help on
qr to see how to set up the arguments.
>
> Could anyone tell me how to find W. Preferably relating to matlab but
> any explanation will do.
>
> Thanks,
>
> Steve

Johan Kullstam <kullstam@ne.mediaone.net> wrote in message news:<m3d75dsk2g.fsf@sysengr.res.ray.com>...
> steve41@totalise.co.uk (Steve) writes:
>
> > I am trying to simulate something I have read in a paper and it
> > requires me to find W such that
> >
> > C*' * W = 0
> >
> > where (.)*' means Hermitian transpose of (.).
>
> matlab denotes this with a plain '. (minor rant -- matlab gets this
> issue extremely right. the ' is the dual operator which
> for matrics over a complex field means complex conjugate transpose.
> if you just want tranpose, use ".'". stuff like X.' * conj(Y) is the
> hallmark of someone who knows enough math to be dangerous but doesn't
> really know what they are doing.)

I just did it to make it more obvious as I have seen someone use this
notation before. Also, some people may use matlab and always use real
so may not know that the apostrophe means conjugate and transpose at
the same time.

>
> take SVD of C
>
> [U,S,V] = svd(C)
>
> now, C = U*S*V' and hence C' = V*S*U' (since S is real and symmetric).
>
> look at S, it will have singular values in descending order from
> something positive down to something small positive or zero. declare
> the small stuff (less than some epsilon) to be zero (this accounts for
> some round off error). say n of the last singlular values are
> essentially zero. the last n rows of U' (i.e., last n columns of U)
> are an orthonormal basis for the null space of C'. these n columns is
> your W.

Okay thanks.

Steve

Nathan Cahill <cahill@image.kodak.com> wrote in message news:<3B8E3F1F.327B8A73@image.kodak.com>...

> Actually, W should be of size N x (N-1).

You're right. I have found another paper and it said W should be N x (N-1).

 
> Basically, the problem is asking you to find vectors that are orthogonal
> to C (a vector A is orthogonal to C if C*'A = 0. Since C is an
> N-dimensional vector, there is an (N-1)-dimensional subspace of
> N-dimensional complex space, such that every vector in this subspace is
> orthogonal to C. We can represent the (N-1)-dimensional subspace by a
> collection of N-1 orthonormal basis vectors, and place each basis vector
> into a column of W.
>
> Now, when you compute the singular value decomposition of a matrix B,
> you are solving for U (orthogonal),V (orthogonal), and S (diagonal),
> where B = U*S*V'. Let's break this equation down by looking at each
> column of U and V, and write V on the left hand side. This gives us:
>
> B*V(:,i) = U(:,i)*S(i,i), for i = 1,...,N
>
> If it turns out that B is a row vector (which it is in your case: B =
> C*'), then it must be true that S(i,i) == 0 whenever any V(:,i) is
> orthogonal to B (because either S(i,i) == 0, or U(:,i) = zeros(N,1), but
> U(:,i) is a unit vector).

> Therefore, if you compute the SVD of your vector C*' (in MATLAB:
> [U,S,V]=svd(C');), then the last N-1 elements of the vector S should be
> zeros. This means the last N-1 columns of V are all orthogonal to C',
> and we know they are all orthogonal to each other, so W = V(:,2:end) is
> an orthogonal basis for the null space of C'.


Very clear description, thanks very much indeed.

Steve

Stan Pawlukiewicz <stanp@mitre.org> wrote in message news:<3B8E5C3B.D99A6F4E@mitre.org>...
> > The paper says I have to find W using singular value decomposition. It
> > said that W is a blocking matrix whose columns span the left nullspace
> > of C but I think that is just the above equation put into words. I
> > have searched on singular value deomposition but cannot find any
> > explanation that seems to fit what I am trying to solve, or maybe I
> > just don't understand it. I looked at matlab help for svd but that
> > didn't help me either.
>
> W isn't square, the paper either has an error, or you might have
> misunderstood.

Yes, I made the mistake. The paper didn't say what the dimensions were
so I used the dimensions of C which I knew and worked it through and
thought it was N x N.

> The block matrix | C W | is square. You could use the SVD to find the
> null space of C, but you can use the qr() routine as well. Do a help on
> qr to see how to set up the arguments.

I've followed how a previous post told me and I have found the
blocking matrix using SVD which is Nx(N-1) as C is an N-vector.

Thanks anyway,

Steve