= Rademacher rounding for a semidefinite relaxation
{c}
{title2=$\widehat x=V\Lambda^{1/2}\xi,\quad x=\widehat x/\max_i|a_i^T\widehat x|$}
Use an orthogonal <eigendecomposition> $X=V\Lambda V^T$ and a vector $\xi$ of independent <Rademacher random variables>. Because $\Lambda$ is diagonal and $\xi_j^2=1$, every sign vector gives $\|\widehat x\|_2^2=\operatorname{tr}X$, without taking an expectation. If the scaling denominator $M$ is positive, then $x$ satisfies every slab constraint and $\|x\|_2^2=\operatorname{tr}X/M^2$. Under spanning constraints and positive trace, $M>0$ automatically. A nonzero $\widehat x$ with $M=0$ instead certifies an unbounded direction.
Back to article page
