I found an algorithm for constructing an $\epsilon$-net for a positive semidefine matrix $A\in[-1,1]^{n\times n}$ which has $rank(A)=d$, described in the paper
The approximate rank of a matrix and its algorithmic applications
by Alon et al. The main problem is to approximate the quadratic form $x^TAy$, where $x,y\in \Delta_n:=\{x\in R^n:\|x\|_1=1,x\geq0\}$ and $A$ is a positive semidefinite matrix, so it can be written in the form $A=BB^T$ for a matrix $B\in R^{n \times d}$. The authors give an algorithm that constructs a $\frac{\epsilon}{\sqrt[]d}$-net for $A$ with respect to the $\|\|_{\infty}$ norm. It's description can be found in the proof of Theorem 3.1 of the paper.
It seems to be unclear how many samples this algorithm requires and by its description, I hesitatingly deduce that it works with just one sample from $\Delta_n$. Is my conclusion correct and if it is, why?