Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
determine sign of s'*(H*x+g)

Subject: determine sign of s'*(H*x+g)

From: Dimitar Dimitrov

Date: 1 Sep, 2008 10:03:02

Message: 1 of 5

Hello,

I would like to determine the sign of z defined as:
z = s'*(H*x+g)

where,
H is [n x n] symmetric positive definite
and x, s, g are [n x 1]

Is there a way in Matlab to determine it without explicitly
carrying out the whole multiplication.

Thanks,
Dimitar

Subject: determine sign of s'*(H*x+g)

From: woodchips@rochester.rr.com

Date: 1 Sep, 2008 11:23:48

Message: 2 of 5

On Sep 1, 6:03=A0am, "Dimitar Dimitrov" <mail_mi...@example.com> wrote:
> Hello,
>
> I would like to determine the sign of z defined as:
> z =3D s'*(H*x+g)
>
> where,
> H is [n x n] symmetric positive definite
> and x, s, g are [n x 1]
>
> Is there a way in Matlab to determine it without explicitly
> carrying out the whole multiplication.
>
> Thanks,
> Dimitar

No, you cannot do so in general.

If you knew the eigenvalues and eigenvectors
of H, then you might be able to do something,
but it would cost at least a matrix*vector multiply
and more to do so anyway.

John

Subject: determine sign of s'*(H*x+g)

From: Dimitar Dimitrov

Date: 2 Sep, 2008 07:04:02

Message: 3 of 5

Hi John,
Thanks for the post.

It is safe to assume that I have all information necessary
for the matrix H (eigenvalues, singular values, H in any
factorized form). I am running a cycle in which H is
constant, so I can obtain information about H beforehand. In
fact g is constant as well. So within the cycle only x and s
are altered.

Probably I should have mentioned in my previous post.


> No, you cannot do so in general.
>
> If you knew the eigenvalues and eigenvectors
> of H, then you might be able to do something,
> but it would cost at least a matrix*vector multiply
> and more to do so anyway.
>
> John

Subject: determine sign of s'*(H*x+g)

From: John D'Errico

Date: 2 Sep, 2008 12:07:01

Message: 4 of 5

"Dimitar Dimitrov" <mail_mitko@example.com> wrote in message
<g9ioh2$jdt$1@fred.mathworks.com>...
> Hi John,
> Thanks for the post.
>
> It is safe to assume that I have all information necessary
> for the matrix H (eigenvalues, singular values, H in any
> factorized form). I am running a cycle in which H is
> constant, so I can obtain information about H beforehand. In
> fact g is constant as well. So within the cycle only x and s
> are altered.
>
> Probably I should have mentioned in my previous post.

If H and g are given, and H is non-singular,
then a logical tactic is to re-write the
expression s'*(H*x+g) as effectively

  s'*H*(x+inv(H)*g)

Of course, we will write inv(H)*g in matlab
as either pinv(H)*g or as H\g. Either choice
is valid if H is known to be non-singular,
and we will pre-compute that result. If H
is singular (and thus only non-negative
definite) then this step was not valid. So
we can write it in matlab as

  G = H\g
  s'*H(x+G)

Now, we can break x + G into two pieces,
one of which is parallel to the vector s, and
a second part which is orthogonal to s, in
terms of the inner product defined by H.

 x + G = k*s + v

where

 s*H*v = 0

Then

  s'*H*(x+G) = k*s'*H*s

since H is SPD, the sign of our original
form is the same as that of k. The problem
is, I don't see a solution to find k that is
any better than the matrix multiplication
we started with. That decomposition of
x + G will still require something equivalent
to a matrix*vector multiplication, so O(n^2)
flops.

Sorry, but I don't see a way out of it. I
might be missing something, but I don't
think so.

John

Subject: determine sign of s'*(H*x+g)

From: Dimitar Dimitrov

Date: 2 Sep, 2008 17:09:02

Message: 5 of 5

John, I appreciate your effort.

We end up having to do a projection of (x+G) on s'*H
which might end up to be even more expensive.

I have been doing some thinking in this direction, however
as you pointed out the complexity is O(n^2) no matter how we
twist it.

Thanks
Dimitar


"John D'Errico" <woodchips@rochester.rr.com> wrote in
message <g9ja95$ikj$1@fred.mathworks.com>...
> "Dimitar Dimitrov" <mail_mitko@example.com> wrote in message
> <g9ioh2$jdt$1@fred.mathworks.com>...
> > Hi John,
> > Thanks for the post.
> >
> > It is safe to assume that I have all information necessary
> > for the matrix H (eigenvalues, singular values, H in any
> > factorized form). I am running a cycle in which H is
> > constant, so I can obtain information about H beforehand. In
> > fact g is constant as well. So within the cycle only x and s
> > are altered.
> >
> > Probably I should have mentioned in my previous post.
>
> If H and g are given, and H is non-singular,
> then a logical tactic is to re-write the
> expression s'*(H*x+g) as effectively
>
> s'*H*(x+inv(H)*g)
>
> Of course, we will write inv(H)*g in matlab
> as either pinv(H)*g or as H\g. Either choice
> is valid if H is known to be non-singular,
> and we will pre-compute that result. If H
> is singular (and thus only non-negative
> definite) then this step was not valid. So
> we can write it in matlab as
>
> G = H\g
> s'*H(x+G)
>
> Now, we can break x + G into two pieces,
> one of which is parallel to the vector s, and
> a second part which is orthogonal to s, in
> terms of the inner product defined by H.
>
> x + G = k*s + v
>
> where
>
> s*H*v = 0
>
> Then
>
> s'*H*(x+G) = k*s'*H*s
>
> since H is SPD, the sign of our original
> form is the same as that of k. The problem
> is, I don't see a solution to find k that is
> any better than the matrix multiplication
> we started with. That decomposition of
> x + G will still require something equivalent
> to a matrix*vector multiplication, so O(n^2)
> flops.
>
> Sorry, but I don't see a way out of it. I
> might be missing something, but I don't
> think so.
>
> John

Tags for this Thread

No tags are associated with this thread.

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us