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.

  • $\begingroup$ 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.) $\endgroup$ Jan 29, 2011 at 21:20
  • $\begingroup$ 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. $\endgroup$ Jan 30, 2011 at 0:51
  • $\begingroup$ 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. $\endgroup$
    – Aaron Roth
    Jan 30, 2011 at 13:46
  • $\begingroup$ 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}$. $\endgroup$
    – Aaron Roth
    Jan 30, 2011 at 14:15

1 Answer 1


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).

  • $\begingroup$ In response to the edit (revision 4) of the question, the lower bound stated in this answer is also applicable to “non-proper” ε-nets. $\endgroup$ Jan 30, 2011 at 13:59
  • $\begingroup$ Looks correct, nicely done! $\endgroup$ Jan 31, 2011 at 4:15
  • $\begingroup$ @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. $\endgroup$ Jan 31, 2011 at 5:15
  • $\begingroup$ 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. $\endgroup$ Feb 21, 2011 at 21:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.