Generate symmetric positive definite matrix with a pre-specified sparsity pattern

I am trying to generate a correlation matrix $p\times p$ (symmetric p.s.d) with a pre-specified sparsity structure (specified by a graph on $p$ nodes). The nodes that are connected in the graph have correlation $\rho \sim U(0,1)$, rest all are 0 and the diagonal is all 1.

I have tried generating this matrix several times but only rarely get a valid correlation matrix.

Is there a way that I can assure a correlation matrix w.h.p? Note that I can only have positive correlation so $\rho \sim U(-1,1)$ etc. is not an option.

Any help is greatly appreciated!

Answer

Close but no cigar for @Rodrigo de Azevedo.

The solution is to use semidefinite programming to find the maximum value, $\rho_{max}$, and the minimum value (subject to being nonnegative), $\rho_{min}$, of $\rho$ such that the correlation matrix with prescribed sparsity pattern is positive semidefinite (psd). All values of $\rho$ such that $\rho_{max}\le \rho \le \rho_{max}$, will produce psd matrices (exercise for reader)

Therefore, you must either choose a distribution of $\rho$ which can only take values in $[\rho_{max},\rho_{max}]$, or you must use acceptance/rejection and reject any generated values of $\rho$ which do not produce a psd matrix.

Example for a 4 by 4 matrix using YALMIP under MATLAB

sdpvar rho % declare rho to be a scalar variable
% find maximum value of rho (by minimizing -rho) subject to prescribed matrix being psd.
optimize([1 0 rho 0;0 1 rho 0;rho rho 1 rho;0 0 rho 1] >= 0,-rho) 
% find minimum value of rho subject to prescribed matrix being psd and rho being >= 0.
optimize([[1 0 rho 0;0 1 rho 0;rho rho 1 rho;0 0 rho 1] >= 0,rho >= 0],rho) 

Results: maximum rho = 0.57735, minimum rho = 0. It is readily apparent that zero will be the minimum value of rho subject to rho being nonegative and the prescribed matrix being psd, regardless of dimension or sparsity pattern. Therefore, it is unnecessary to run the semidefinite optimization to find the minimum nonnegative value of $\rho$.

Attribution
Source : Link , Question Author : Blade Runner , Answer Author : Mark L. Stone

Leave a Comment