<p>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</p>

<blockquote>
  <p><a href="http://eccc.hpi-web.de/report/2012/169/" rel="nofollow">The approximate rank of a matrix and its algorithmic applications</a></p>
</blockquote>

<p>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.</p>

<p>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?</p>

CC BY-SA 3.0
2016-01-24T23:19:23.817Z
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.?
Sasho Nikolov
CC BY-SA 3.0
2016-01-25T11:17:53.187Z
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.
Kapoios
CC BY-SA 3.0
2016-01-25T11:48:30.297Z
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.
Kapoios
CC BY-SA 3.0
2016-01-25T20:15:42.173Z
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}$.
Sasho Nikolov
CC BY-SA 3.0
2016-01-25T23:16:54.267Z
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?
Kapoios
CC BY-SA 3.0
2016-02-22T22:37:55.193Z
I managed to understand the algorithm, based on your explanation. Thank you!
Kapoios
<ds.algorithms><cg.comp-geom><epsilon-nets>
Clarification needed on an algorithm for $\epsilon$-net construction for the column space of PSD matrices
Kapoios
# Clarification needed on an algorithm for $\epsilon$-net construction for the column space of PSD matrices

(Asked by: username_0 on 2016-01-23)

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](http://eccc.hpi-web.de/report/2012/169/)

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?

**Tags:** ds.algorithms, cg.comp-geom, epsilon-nets
> **Comments:**
> **username_1**: 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.?  
> **username_0**: 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.  
> **username_0**: 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.  
> **username_1**: 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}$.  
> **username_0**: 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?  
> **username_0**: I managed to understand the algorithm, based on your explanation. Thank you!  

---

## 0 answers

