[Math] Algorithm for generating positive semidefinite matrices

linear algebramatrices

I'm looking for an efficient algorithm to generate large positive semidefinite matrices.

One possible way I know of is:

  • generate a random square matrix
  • multiply it with its transpose.
  • calculate all eigenvalues of the result matrix and check if all of them are non-negative.

However, this approach is infeasible given a large matrix, say $1000 \times 1000$ or more.

Could anyone please suggest an efficient way to generate a positive semidefinite matrix?
Is there any MATLAB function for this job?

Thanks,

Best Answer

  1. Generate a random symmetric matrix, determine eigenvalue bounds via, say, Gerschgorin, and then shift the diagonal elements by an appropriate amount determined from the Gerschgorin bound of the leftmost eigenvalue.

  2. Generate a diagonal matrix with random nonnegative elements from a distribution of your choice, and perform a similarity transformation with a Haar-distributed pseudorandom orthogonal matrix.

  3. Generate a diagonal matrix with random nonnegative elements from a distribution of your choice, and perform a few sweeps of the (cyclic) Jacobi algorithm, with randomly generated rotation matrices $\begin{pmatrix}c&-s\\s&c\end{pmatrix}$ (e.g., randomly generate a $c\in [-1,1]$ and calculate a corresponding $s$ through $c^2+s^2=1$).

Related Question