1
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • $\begingroup$ I do not understand the question. What do you mean by a sample? the net is of size $2^{O(d)}$ and the algorithm outputs it in time $2^{O(d)}\mathrm{poly}(n,d)$. Also, don't you mean Theorem 3.1.? $\endgroup$ – Sasho Nikolov Jan 24 '16 at 23:19
  • $\begingroup$ What I understood from the description of the algorithm is that: for a $x\in \Delta_n$ we find its image on the column space of $B^T$, let it be $y$, then we perform an exponential binning of the coordinates of $y$ and finally, with the aid of the binning, we discretize the coordinates of $y$ to multiples of $\frac{\epsilon}{\sqrt{d}}$. My question is, on how many $x \in \Delta_n$ we must do this procedure in order to obtain a $\epsilon$-net of the size you mentioned. Maybe my question implies a misunderstanding on the algorithm on my side. $\endgroup$ – Kapoios Jan 25 '16 at 11:17
  • $\begingroup$ I have to mention that I don't have a solid background on $\epsilon$-nets, except of those for set systems of discrete sets. On $\epsilon$-nets for convex bodies, I have only studied some very simple constructions such as taking a tiling consisted of cubes of a suitable edge length. $\endgroup$ – Kapoios Jan 25 '16 at 11:48
  • $\begingroup$ I think you do misunderstand the algorithm. Actually the net is independent of $B$. To construct it, for each possible profile, and each possible way to realize the profile by assigning coordinates to buckets, you take all possible values of the coordinate that are multiples of $\epsilon/\sqrt{d}$. $\endgroup$ – Sasho Nikolov Jan 25 '16 at 20:15
  • $\begingroup$ Thanks for your explanation. Now, the algorithm seems much more conceivable. I have one more question. Why the authors consider the bucketing step, instead of just taking the grid of $\frac{\epsilon}{\sqrt{d}}$ edge length? $\endgroup$ – Kapoios Jan 25 '16 at 23:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.