convex nonnegative basis vectors in nullspace of matrix

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

convex nonnegative basis vectors in nullspace of matrix

capy_bara
Dear all,

I want to explore the nullspace of a matrix S: I currently use the function Null from the MASS package to get a basis for the null space:
> S  = matrix(nrow=3, ncol=5, c(1,0,0,-1,1,1,1,-1,-1,0,-1,0,0,0,-1)); S
> MASS::Null(t(S))
My problem is that I actually need a nonnegative basis for the null space of S.
There should be a unique set of convex basis vectors spanning a vector space in which each vector v satisfies sum (S %*%  v) == 0 and min(v)>=0.
Is there maybe an R function that can calculate that for me?
I would appreciate any help,
Thanks in advance,

Hannes
Reply | Threaded
Open this post in threaded view
|

Re: convex nonnegative basis vectors in nullspace of matrix

Petr Savicky
On Wed, Apr 11, 2012 at 06:04:28AM -0700, capy_bara wrote:

> Dear all,
>
> I want to explore the nullspace of a matrix S: I currently use the function
> Null from the MASS package to get a basis for the null space:
> > S  = matrix(nrow=3, ncol=5, c(1,0,0,-1,1,1,1,-1,-1,0,-1,0,0,0,-1)); S
> > MASS::Null(t(S))
> My problem is that I actually need a nonnegative basis for the null space of
> S.
> There should be a unique set of convex basis vectors spanning a vector space
> in which each vector v satisfies sum (S %*%  v) == 0 and min(v)>=0.

Hi.

The null space of the above matrix has dimension 2. Its intersection
with nonnegative vectors in R^5 is an infinite cone. In order to restrict
it to a finite set, we can consider its intersection with the set
of vectors with the sum of coordinates equal to 1. Then, the solution
is a finite convex polytop and we can search for its vertices. The
following code searches for vertices in random directions and finds two
vertices. In this simple case, the polytop is in fact a line segment,
so we get its endpoints. These endpoints form a linear basis of the
original null space consisting of nonnegative vectors.

  library(lpSolve)
  S <- matrix(nrow=3, ncol=5, c(1,0,0,-1,1,1,1,-1,-1,0,-1,0,0,0,-1))
  a <- MASS::Null(t(S))
  n <- nrow(a)
  a1 <- rbind(a, colSums(a))
  b <- rep(0, times=n+1)
  b[n+1] <- 1
  dir <- c(rep(">=", times=n), "==")
  sol <- matrix(nrow=100, ncol=n)
  for (i in seq.int(length=nrow(sol))) {
      crit <- rnorm(ncol(a))
      out <- lp(objective.in=crit, const.mat=a1, const.dir=dir, const.rhs=b)
      sol[i, ] <- a %*% out$solution
  }
  unique(round(sol, digits=10))

            [,1]      [,2]      [,3]      [,4]      [,5]
  [1,] 0.2500000 0.2500000 0.0000000 0.2500000 0.2500000
  [2,] 0.1642631 0.3357369 0.1714738 0.1642631 0.1642631

Use this with care, since for more complex cases, this method does not
guarantee that all vertices are found. So, it is not guaranteed that
every nonnegative vector in the null space is a nonnegative combination
of the obtained vectors.

Hope this helps.

Petr Savicky.

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
Reply | Threaded
Open this post in threaded view
|

Re: convex nonnegative basis vectors in nullspace of matrix

Petr Savicky
In reply to this post by capy_bara
On Wed, Apr 11, 2012 at 06:04:28AM -0700, capy_bara wrote:

> Dear all,
>
> I want to explore the nullspace of a matrix S: I currently use the function
> Null from the MASS package to get a basis for the null space:
> > S  = matrix(nrow=3, ncol=5, c(1,0,0,-1,1,1,1,-1,-1,0,-1,0,0,0,-1)); S
> > MASS::Null(t(S))
> My problem is that I actually need a nonnegative basis for the null space of
> S.
> There should be a unique set of convex basis vectors spanning a vector space
> in which each vector v satisfies sum (S %*%  v) == 0 and min(v)>=0.

Hi.

In my previous solution, i forgot that lp() assumes all variables
nonnegative. So, the code was searching only a subset of the true
set of solutions. A better alternative is as follows.

  library(lpSolve)
  S <- matrix(nrow=3, ncol=5, c(1,0,0,-1,1,1,1,-1,-1,0,-1,0,0,0,-1))
  a <- MASS::Null(t(S))
  a1 <- cbind(a, -a)
  n <- nrow(a1)
  a2 <- rbind(a1, colSums(a1))
  b <- rep(0, times=n+1)
  b[n+1] <- 1
  dir <- c(rep(">=", times=n), "==")
  sol <- matrix(nrow=100, ncol=n)
  for (i in seq.int(length=nrow(sol))) {
      crit <- rnorm(ncol(a))
      crit <- c(crit, -crit)
      out <- lp(objective.in=crit, const.mat=a2, const.dir=dir, const.rhs=b)
      sol[i, ] <- a1 %*% out$solution
  }
  unique(round(sol, digits=10))

       [,1] [,2] [,3] [,4] [,5]
  [1,] 0.00 0.50  0.5 0.00 0.00
  [2,] 0.25 0.25  0.0 0.25 0.25

Petr Savicky.

______________________________________________
[hidden email] mailing list
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
Reply | Threaded
Open this post in threaded view
|

Re: convex nonnegative basis vectors in nullspace of matrix

capy_bara
Hi
the solution with linear programming works very well!
Even if I take more 'realistic' matrices with dimensions of about  25x60, the calculation of the basis goes well (if I increase the number of iterations to 1000).
Meanwhile I also found an algorithm for an exact calculation of the extreme rays of the cone (Appendix in http://www.sciencedirect.com/science/article/pii/S0022519300910737).
When I have time I will try to implement this solution as well and compare the performances, but the one I have now works fine in my application.
Many thanks,
Hannes