# $\epsilon$-nets with respect to the cut norm

The cut norm $||A||_C$ of a real matrix $A = (a_{i,j}) \in \mathcal{R}^{n\times n}$ is the maximum over all $I \subseteq [n], J \subseteq [n]$ of the quantity $\left|\sum_{i \in I, j \in J}a_{i,j}\right|$.

Define the distance between two matrices $A$ and $B$ to be $d_C(A,B) = ||A-B||_C$

What is the cardinality of the smallest $\epsilon$-net of the metric space $([0,1]^{n\times n}, d_C)$?

i.e. the size of the smallest subset $S \subset [0,1]^{n\times n}$ such that for all $A \in [0,1]^{n\times n}$, there exists an $A' \in S$ such that $d_C(A, A') \leq \epsilon$.

(EDIT: I forgot to mention, but I am also interested in "non-proper" $\epsilon$-nets, with $S \subset \mathcal{R}_+^{n\times n}$ -- i.e. if the elements of the $\epsilon$-net have entries outside of [0,1], that is also interesting.)

I am interested in both upper bounds and lower bounds.

Note that cut sparsifier techniques imply $\epsilon$-nets for cut metrics, but give something stronger than I need -- they give an $\epsilon$-net for which you can efficiently find an $\epsilon$-close point to any matrix simply by sampling from that matrix. One might imagine that there exist much smaller $\epsilon$-nets for which you cannot simply sample do find an $\epsilon$-close point to an arbitrary matrix.

I initially asked this question here on mathoverflow.

-
Because the cut norm of A is greater than or equal to the absolute value of each entry of A, it is clear that an ε-net must have size at least (1/(2ε))^(n^2). What is the upper bound derived from the cut sparsifier technique? (This is probably a dumb question, but I do not know that technique.) –  Tsuyoshi Ito Jan 29 '11 at 21:20
Just to make sure, I turned the first half of my previous comment into an answer (and added an upper bound to it). I am still interested in the upper bound derived from the cut sparsifier technique. –  Tsuyoshi Ito Jan 30 '11 at 0:51
The above technique yields matrices with entries in $\{0, m||A||_1\}$ rather than in $[0,1]$. I forgot to mention it in the post, but I am also interested in these kinds of $\epsilon$-covers. –  Aaron Roth Jan 30 '11 at 13:46
The $\epsilon$-net you get from cut sparsification does not actually lie in $[0,1]^{n×n}$. Interpret the matrix as a probability distribution over the edges of a directed graph, and sample $m=\tilde{O}(n/\epsilon^2)$ edges from the distribution. Weight each edge by $||A||_1/m$. By VC-dimension arguments (or just a union bound over cuts), the max additive error on any cut will w.h.p. be $O(\epsilon n^2)$. So this implies that that the set of (appropriately weighted) graphs on $n^5/\epsilon^2$ edges form an $\epsilon$-net, which is non-trivial for $\epsilon>n^{3/2}$. –  Aaron Roth Jan 30 '11 at 14:15

Here is an easy estimate. Here we call a set SX an ε-net of a metric space X when for every point xX, there exists a point sS such that the distance between x and s is at most ε. If you want a strict inequality in the definition of ε-net, you can tweak the value of ε slightly.

It holds that ||A|| ≤ ||A||Cn2||A||, where ||A|| denotes the entrywise max-norm of an n×n matrix A.

It is easy to construct an ε-net of the metric space ([0,1]N, d) with size ⌈1/(2ε)⌉N, and it is not hard to show that this size is the minimum. (To show the minimality, consider the ⌈1/(2ε)⌉N points whose coordinates are multiples of 1/⌈1/(2ε)−1⌉ and show that the distance between any two of these points is greater than 2ε.) By setting N=n2 and combining this with the aforementioned comparison between the cut norm and the max-norm, the minimum cardinality of an ε-net with respect to the cut norm is at least ⌈1/(2ε)⌉n2 and at most ⌈n2/(2ε)⌉n2.

Update: If my calculation is correct, a better lower bound Ω(n/ε)n2 can be obtained by the volume argument. To do this, we need an upper bound on the volume of an ε-ball with respect to the cut norm.

First we consider the “cut norm” of a single vector, which is the maximum between the sum of positive elements and the negated sum of negative elements. It is not hard to show that the volume of an ε-ball in ℝn with respect to this “cut norm” is equal to

$$\varepsilon^n \sum_{I \subseteq \{1,\dotsc,n\}} \frac{1}{|I|!} \cdot \frac{1}{(n-|I|)!} = \varepsilon^n \sum_{r=0}^n \binom{n}{r} \frac{1}{r!(n-r)!}$$

$$= \frac{\varepsilon^n}{n!} \sum_{r=0}^n \binom{n}{r}^2 = \frac{\varepsilon^n}{n!} \binom{2n}{n} = \frac{(2n)!\varepsilon^n}{(n!)^3}.$$

Next, since the cut norm of an n×n matrix A is greater than or equal to the cut norm of each row, the volume of an ε-ball in ℝn×n is at most the nth power of the volume of an ε-ball in ℝn. Therefore the size of an ε-net of [0,1]n×n must be at least

$$\frac{(n!)^{3n}}{(2n)!^n \varepsilon^{n^2}} = \left(\Omega\left(\frac{n}{\varepsilon}\right)\right)^{n^2},$$

where the last equality is a boring calculation in which we use Stirling’s formula: ln n! = n ln nn + O(log n).

-
In response to the edit (revision 4) of the question, the lower bound stated in this answer is also applicable to “non-proper” ε-nets. –  Tsuyoshi Ito Jan 30 '11 at 13:59
Looks correct, nicely done! –  Hsien-Chih Chang 張顯之 Jan 31 '11 at 4:15
@Hsien-Chih: Thanks. The part I like the most is the use of binomial coefficients in the calculation of the volume of an ε-ball in ℝ^n. –  Tsuyoshi Ito Jan 31 '11 at 5:15
I suspect that the lower bound on the size of the net (equivalently, the upper bound on the volume) can be improved. I asked a related question on MathOverflow. –  Tsuyoshi Ito Feb 21 '11 at 21:22