# How to ensure the covariance matrix for randomization in boolean least square problem is positive semidefinite?

I am trying to use SDR and solve a boolean least square problem. The problem is solved. But when I try to use randomization to generate a vector solution, the covariance matrix that constructed by the solved solution does not hold the positive semidefinite property. Below is my formulation

``````        cvx_begin
variable F(J,J) hermitian semidefinite
variable v(J,1) complex

minimize( real(trace(Z * F)) - 2 * real(J * as_ele_Tx.' * v) + J^2  )
subject to

for i = 1:(K_num)
trace(Hm(i,:)' * Hm(i,:) * F) <= gamma_seq(i2) ./ P;
end
diag(F) == 1;
[F v;v' 1] == hermitian_semidefinite(J+1);

cvx_end

% extract the weight solution by randomization
mu = v;              % expectation

cov = F - v * v';     % covariance
L = 5000;            % number of samples

% randomization procedure
z = 1 ./ sqrt(2) .* (randn(J, L) + 1j .* randn(J, L));
f_L = mu .* ones(J, L) + chol(cov)' * z ;
``````

Although I regulate the semidefinite in [F v;v’ 1] == hermitian_semidefinite(J+1), the chol(cov) procedure still give an error that the cov is not PSD matrix. I checked the singular value here and it did have a negative singular value.

So, kind of stuck here, maybe it’s more like a precision or scaling problem? How can I ensure the PSD here? As the cvx solved this problem, I assumed the cov here to be PSD.

The corresponding code is at https://github.com/la0719/temp/blob/main/main.

I ran the code with Mosek as solver. All eigenvalues of `cov` were positive, with the exception of min(eig(cov)) being -2.6745e-08. So apparently you are encountering a numerical issue. I will leave the appropriate resolution to you, because this is not really a CVX issue, and SDR is outside the forum’s scope. Nevertheless, feel free to add another post to this topic with your resolution.

BTW `chol` requires its argument to be numerically positive definite, not positive semidefinite. It takes an optional 2nd output argument `FLAG`, which prevents an error if `chol` can’t succeed.

Really thanks for the answer, Mark. Yes I will see how to fix this issue and leave a post here if I fix it. And you are right, it is required to be positive definite, sorry for wrong statement here.

Hi Mark. I think I got a solution from Mathworks forum for this problem. In matlab, we could use the function nearestSPD to find the smallest perturbation to a matrix such that the matrix will be PSD, where chol will then succeed. The function is writtern by John D’Errico, and released at file exchange. I will leave my question website on Mathworks below. And of course, we could also add an identity matrix here, but we will have to decide that how small the diagnoal value should be, which is a little bit petty. And of course, there might be some other solutions here as well.

As i wrote, I will leave the appropriate resolution to you.

There are multiple possible resolutions, but it is your problem, so for you to decide what to do.

Options include:

Use `eig` to find eigenvalues and eigenvectors, set all eigenvalues below a specified minimum (for you to specify) to that minimum, then form the matrix with those eigenvectors and adjusted eigenvalues. Perhaps this is what the function you found does?

or

Add diagonal matrix whose diagonal elements are {specified minimum eigenvalue (for you to specify) - minimum eigenvalue of unadjusted matrix}

Or concoct you own convex optimization problem to do what you want.

Or

change

`[F v;v' 1] == hermitian_semidefinite(J+1);`
to
`[F v;v' 1] - min_desired_eigenvalue*eye(J+1) == hermitian_semidefinite(J+1);`
which should avoid the need for post-processing adjustment, and which is essentially the same as the first option in terms of the result.

or

none of the above

Really thanks Mark, again. All these can be exploited.