Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

1 Answer 1

up vote 8 down vote accepted

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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