A naive question, but wouldn't it be possible to generate the positive semidefinite matrix as a positive weighted sum of rank-1 matrices? That way the sparsity can also be controlled.