Computing positive semidefinite (PSD) rank with mathematical software

Question

I would like find positive semidefinite (PSD) rank or a decomposition for 10~15 size square nonnegative matrices with the aid of some mathematical software. I wonder if it is feasible with standard laptop and also wonder what is the best software to use for such numerics.

N.B. the notion of PSD rank is different from the standard rank of a matrix. It can be only defined for positive matrices and defined on page 14 of this paper http://arxiv.org/pdf/1111.0837.pdf . Basically it is defined as the following; Given a positive $m\times n$ matrix $M$, we consider two sets of positive semidefinite matrices $\{A_i\}_{i\in 1\ldots m}$ and $\{B_j\}_{j\in 1\ldots n}$ such that the entries of the $M$ is given by $M_{ij}=<A_i,B_j>$. PSD rank is defined as the smallest size of these square positive semi-definite matrices. PSD rank of positive matrix can be larger or smaller then the standard rank and in general it is hard to find a good bound of one with the other.

I reckon this quantity is rather combinatorial than linear algebraic.

Answer 1

You can use the MATLAB rank function. If you don't have the money for MATLAB you can use Octave, an open source clone of MATLAB.

I tried using the rank function in Octave on a $15$ by $15$ Hilbert matrix and it computed almost instantly. This is on tablet with a 1.60 GHz Intel processor with 1.0 GB RAM.

Answer 2

More conceptually, if your computing environment has the ability to compute the singular value decomposition (SVD) of a matrix, then you have a handy way of determining the (numerical) rank: set a particular threshold (it is customary to use the norm of the matrix multiplied by machine epsilon, but is often application-dependent), and then count the number of singular values that are greater than this set threshold. This count is the rank of your matrix.

That procedure is for inexact matrices; for exact matrices, you can use row reduction for rank determination.

(In fact, functions for computing the matrix rank in most of the standard computing environments will perform either of the two procedures given above.)