Sign rank versus VC dimension

Introduction

Boolean matrices (with $0,1$ entries) and sign matrices (with $\pm 1$ entries) naturally appear in many areas of research There is a standard transformation of a boolean matrix $B$ to the sign matrix $S=2B-J$, where $J$ is the all $1$ matrix. The matrix $S$ is called the signed version of $B$, and the matrix $B$ is called the boolean version of $S$.. We use them e.g. to represent set systems and graphs in combinatorics, hypothesis classes in learning theory, and boolean functions in communication complexity.

This work further investigates the relation between two useful complexity measures on sign matrices.

For a real matrix $M$ with no zero entries, let $\text{sign}(M)$ denote the sign matrix such that $(\text{sign}(M))_{i,j}=\text{sign}(M_{i,j})$ for all $i,j$. The sign rank of a sign matrix $S$ is defined as

The VC dimension of a sign matrix $S$, denoted $VC(S)$, is defined as follows. A subset $C$ of the columns of $S$ is called shattered if each of the $2^{|C|}$ different patterns of ones and minus ones appears in some row in the restriction of $S$ to the columns in $C$. The VC dimension of $S$ is the maximum size of a shattered subset of columns. It captures the size of the minimum $\epsilon$-net for the underlying set system .

The VC dimension and the sign rank appear in various areas of computer science and mathematics. One important example is learning theory, where the VC dimension captures the sample complexity of learning in the PAC model , and the sign rank relates to the generalization guarantees of practical learning algorithms, such as support vector machines, large margin classifiers, and kernel classifiers . Loosely speaking, the VC dimension relates to learnability, while sign rank relates to learnability by linear classifiers. Another example is communication complexity, where the sign rank is equivalent to the unbounded error randomized communication complexity , and the VC dimension relates to one round distributional communication complexity under product distributions ,

The main focus of this work is how large can the sign rank be for a given VC dimension. In learning theory, this question concerns the universality of linear classifiers. In communication complexity, this concerns the difference between randomized communication complexity with unbounded error and between communication complexity under product distribution with bounded error. Previous works have studied these differences from the communication complexity perspective and the learning theory perspective . In this work we provide explicit matrices and stronger separations compared to those of and . See the discussions in Section 1.2 and Section 2.4 for more details.

We start by providing alternative descriptions of the VC dimension and sign rank, which demonstrate that these notions are dual to each other. The sign rank of a sign matrix $S$ is the maximum number $k$ such that

The dual sign rank of $S$ is the maximum number $k$ such that

It turns out that the dual sign rank is almost equivalent to the VC dimension (the proof is in Section 3.1).

$VC(S)\leq\text{dual-sign-rank}(S)\leq 2VC(S)+1$.

As the dual sign rank is at most the sign rank, it follows that the VC dimension is at most the sign rank. This provides further motivation for studying the largest possible gap between sign rank and VC dimension; it is equivalent to the largest possible gap between the sign rank and the dual sign rank.

It is worth noting that there are some interesting classes of matrices for which these quantities are equal. One such example is the $2^{n}\times 2^{n}$ disjointness matrix $DISJ$, whose rows and columns are indexed by all subsets of $[n]$, and $DISJ_{x,y}=1$ if and only if $|x\cap y|>0$. For this matrix both the sign rank and the dual sign rank are exactly $n+1$.

2 Sign rank versus VC dimension

The VC dimension is at most the sign rank. On the other hand, it is long known that the sign rank is not bounded from above by any function of the VC dimension. Alon, Haussler, and Welzl provided examples of $N\times N$ matrices with VC dimension $2$ for which the sign rank tends to infinity with $N$. used ideas from together with estimates concerning the Zarankiewicz problem to show that many matrices with constant VC dimension (at least $4$) have high sign rank.

We further investigate the problem of determining or estimating the maximum possible sign rank of $N\times N$ matrices with VC dimension $d$. Denote this maximum by $f(N,d)$. We are mostly interested in fixed $d$ and $N$ tending to infinity.

We observe that there is a dichotomy between the behaviour of $f(N,d)$ when $d=1$ and when $d>1$. The value of $f(N,1)$ is $3$, but for $d>1$, the value of $f(N,d)$ tends to infinity with $N$. We now discuss the behaviour of $f(N,d)$ in more detail, and describe our results.

We start with the case $d=1$. The following theorem and claim imply that for all $N\geq 4$,

The following theorem which was proved by shows that for $d=1$, matrices with high sign rank do not exist. For completeness, we provide our simple and constructive proof in Section 3.2.1.

If the VC dimension of a sign matrix $M$ is one then its sign rank is at most $3$.

We also note that the bound $3$ is tight (see Section 3.2.1 for a proof).

For $N\geq 4$, the $N\times N$ signed identity matrix (i.e. the matrix with $1$ on the diagonal and $-1$ off the diagonal) has VC dimension one and sign rank $3$.

Next, we consider the case $d>1$, starting with lower bounds on $f(N,d)$. As mentioned above, two lower bounds were previously known: showed that $f(N,2)\geq\Omega(\log N)$. showed that $f(N,d)\geq\omega(N^{1-\frac{2}{d}-\frac{1}{2^{d/2}}})$, for every fixed $d$, which provides a nontrivial result only for $d\geq 4$. We prove the following stronger lower bound.

The following lower bounds on $f(N,d)$ hold:

which is close to $1/d$ for large $d$. The proofs are described in Section 3.2, where we also discuss the tightness of our arguments.

What about upper bounds on $f(N,d)$? It is shown in that for every matrix in a certain class of $N\times N$ matrices with constant VC dimension, the sign rank is at most $O(N^{1/2})$. The proof uses the connection between sign rank and communication complexity. However, there is no general upper bound for the sign rank of matrices of VC dimension $d$ in , and the authors explicitly mention the absence of such a result.

Here we prove the following upper bounds, using a concrete embedding of matrices with low VC dimension in real space.

In particular, this determines $f(N,2)$ up to a logarithmic factor:

The above results imply existence of sign matrices with high sign rank. However, their proofs use counting arguments and hence do not provide a method of certifying high sign rank for explicit matrices. In the next section we show how one can derive a lower bound for the sign rank of many explicit matrices.

3 Sign rank and spectral gaps

Spectral properties of boolean matrices are known to be deeply related to their combinatorial structure. Perhaps the best example is Cheeger’s inequality which relates spectral gaps to combinatorial expansion . Here, we describe connections between spectral properties of boolean matrices and the sign rank of their signed versions.

Proving strong lower bounds on the sign rank of sign matrices turned out to be a difficult task. Alon, Frankl, and Rödl were the first to prove that there are sign matrices with high sign rank, but they have not provided explicit examples. Later on, a breakthrough of showed how to prove lower bounds on the sign rank of explicit matrices, proving, specifically, that Hadamard matrices have high sign rank. proved that there is a function that is computed by a small depth three boolean circuit, but with high sign rank. It is worth mentioning that no explicit matrix whose sign rank is significantly larger than $N^{\frac{1}{2}}$ is known.

We focus on the case of regular matrices, but a similar discussion can be carried more generally. A boolean matrix is $\Delta$ regular if every row and every column in it has exactly $\Delta$ ones, and a sign matrix is $\Delta$ regular if its boolean version is $\Delta$ regular.

An $N\times N$ real matrix $M$ has $N$ singular values $\sigma_{1}\geq\sigma_{2}\geq\ldots\geq\sigma_{N}\geq 0$. The largest singular value of $M$ is also called its spectral norm $\|M\|=\sigma_{1}=\max\{\|Mx\|:\|x\|\leq 1\},$ where $\|x\|^{2}=\langle x,x\rangle$ with the standard inner product. If the ratio $\sigma_{2}(M)/\|M\|$ is bounded away from one, or small, we say that $M$ has a spectral gap.

We prove that if $B$ has a spectral gap then the sign rank of $S$ is high.

Let $B$ be a $\Delta$ regular $N\times N$ boolean matrix with $\Delta\leq N/2$, and let $S$ be its signed version. Then,

In many cases a spectral gap for $B$ implies that it has pseudorandom properties. This theorem is another manifestation of this phenomenon since random sign matrices have high sign rank (see ).

Our proof of Theorem 6 and its limitations are discussed in detail in Section 3.3.

Applications

Linear classifiers have been central in the study of machine learning since the introduction of the Perceptron algorithm in the 50’s and Support Vector Machines (SVM) in the 90’s . The rising of kernel methods in the 90’s enabled reducing many learning problems to the framework of halfspaces, making linear classifiers a central algorithmic tool.

These methods use the following two-step approach. First, embed the hypothesis class In this context we use the more common term “hypothesis class” instead of “matrix.” in halfspaces of an Euclidean space (each point corresponds to a vector and for every hypothesis $h$, the vectors corresponding to $h^{-1}(1)$ and the vectors corresponding to $h^{-1}(-1)$ are separated by a hyperplane). Second, apply a learning algorithm for halfspaces.

If the embedding is to a low dimensional space then a good generalization rate is implied. For embeddings to large dimensional spaces, SVM theory offers an alternative parameter, namely the margin The margin of the embedding is the minimum over all hypotheses $h$ of the distance between the convex hull of the vectors corresponding to $h^{-1}(1)$ and the convex hull of the vectors corresponding to $h^{-1}(-1)$. Indeed, a large margin also implies a good generalization rate. On the other hand, any embedding with a large margin can be projected to a low dimensional space using standard dimension reduction arguments .

Ben-David, Eiron, and Simon utilized it to argue that “…any universal learning machine, which transforms data to a Euclidean space and then applies linear (or large margin) classification, cannot preserve good generalization bounds in general.” Formally, they showed that: For any fixed $d>1$, most hypothesis classes $C\subseteq\{\pm 1\}^{N}$ of VC dimension $d$ have sign-rank of $N^{\Omega(1)}$. As discussed in Section 1.2, Theorem 4 quantitatively improves over their results.

Maximum classes with large sign rank

Let $C\subseteq\{\pm 1\}^{N}$ be a class with VC dimension $d$. The class $C$ is called maximum if it meets the Sauer-Shelah’s bound with equality Maximum classes are distinguished from maximal classes: A maximum class has the largest possible size among all classes of VC dimension $d$, and a maximal class is such that for every sign vector $v\notin C$, if $v$ is added to $C$ then the VC dimension is increased.. That is, $|C|=\sum_{i=0}^{d}{N\choose i}$. Maximum classes were studied in different contexts such as machine learning, geometry, and combinatorics (e.g. ).

Gärtner and Welzl gave a combinatorial characterization of maximum classes constructed using generic halfspaces. As an application of their characterization they note that hamming ball of radius $d$ is a maximum class that can not be realized this way. By Lemma 19, however, the hamming ball of radius $d$ has sign rank at most $2d+1$ (it is in fact exactly $2d+1$). It is therefore natural to ask whether every maximum class has sign rank which depends only on $d$. A similar question was also asked by . Theorem 8 in Section 2.2.1 gives a negative answer to this question, even when $d=2$ (when $d=1$, by Theorem 2 the sign rank is at most $3$).

2 Explicit examples

The spectral lower bound on sign rank gives many explicit examples of matrices with high sign rank, which come from known constructions of expander graphs and combinatorial designs. A rather simple such family of examples is finite projective geometries.

Let $d\geq 2$ and $n\geq 3$. Let $P$ be the set of points in a $d$ dimensional projective space of order $n$, and let $H$ be the set of hyperplanes in the space. For $d=2$, this is just a projective plane with points and lines. It is known (see, e.g., ) that

Let $A\in\{\pm 1\}^{P\times H}$ be the signed point-hyperplane incidence matrix:

The matrix $A$ is $N\times N$ with $N=N_{n,d}$, its VC dimension is $d$, and its sign rank is larger than

The theorem follows from known properties of projective spaces (see Section 3.4.1). A slightly weaker (but asymptotically equivalent) lower bound on the sign rank of $A$ was given by .

The sign rank of $A$ is at most $2N_{n,d-1}+1=O(N^{1-\frac{1}{d}})$, due to the observation in mentioned above. To see this, note that every point in the projective space is incident to $N_{n,d-1}$ hyperplanes.

Other explicit examples come from spectral graph theory. Here is a brief description of matrices that are even more restricted than having VC dimension $2$ but have high sign rank; no $3$ columns in them have more than $6$ distinct projections. An $(N,\Delta,\lambda)$-graph is a $\Delta$ regular graph on $N$ vertices so that the absolute value of every eigenvalue of the graph besides the top one is at most $\lambda$. There are several known constructions of $(N,\Delta,\lambda)$-graphs for which $\lambda\leq O(\sqrt{\Delta})$, that do not contain short cycles. Any such graph with $\Delta\geq N^{\Omega(1)}$ provides an example with sign rank at least $N^{\Omega(1)}$, and if there is no cycle of length at most $6$ then in the sign matrix we have at most $6$ distinct projections on any set of $3$ columns.

The class $R$ of all intervals is a maximum class of VC dimension $2$. Moreover, there exists a choice of linear orders for the lines in $L$ such that the resulting $R$ has sign rank $\Omega(N^{1/2}/\log N)$.

The proof of Theorem 8 is given in Section 3.4.1. The proof does not follow directly from Theorem 4 since it is not clear that the classes with VC dimension $2$ and large sign rank which are guaranteed to exist by Theorem 4 can be extended to a maximum class.

3 Computing the sign rank

Linear Programming (LP) is one of the most famous and useful problems in the class P. As a decision problem, an LP problem concerns determining the satisfiability of a system

Another related work of concerns the problem of computing the approximate rank of a sign matrix, for which they provide an approximation algorithm. They pose the problem of efficiently approximating the sign rank as an open problem.

Using an idea similar to the one in the proof of Theorem 5 we derive an approximation algorithm for the sign rank (see Section 3.4.2).

There exists a polynomial time algorithm that approximates the sign rank of a given $N$ by $N$ matrix up to a multiplicative factor of $c\cdot N/\log(N)$ where $c>0$ is a universal constant.

4 Communication complexity

We briefly explain the notions from communication complexity we use. For formal definitions, background and more details, see the textbook .

For a function $f$ and a distribution $\mu$ on its inputs, define $D_{\mu}(f)$ as the minimum communication complexity of a protocol that correctly computes $f$ with error $1/3$ over inputs from $\mu$. Define D^{\times}(f)=\max\{D_{\mu}(f):\text{\muis a product distribution}\}. Define the unbounded error communication complexity $U(f)$ of $f$ as the minimum communication complexity of a randomized private-coin In the public-coin model, every boolean function has unbounded communication complexity at most two. protocol that correctly computes $f$ with probability strictly larger than $1/2$ on every input.

Two works of showed that there are functions with small distributional communication complexity under product distributions, and large unbounded error communication complexity. In the separation is as strong as possible but it is not for an explicit function, and the separation in is not as strong but the underlying function is explicit.

The unbounded error communication complexity of $f$ is By taking larger values of $d$, the constant $\frac{1}{4}$ may be increased to $\frac{1}{2}-\frac{1}{2d}$. $U(f)\geq\frac{m}{4}-O(1)$. The distributional communication complexity of $f$ under product distributions is $D^{\times}(f)\leq O(1)$.

These two seemingly contradicting facts are a corollary of the high sign rank and the low VC dimension of $A$, using two known results. The upper bound on $D^{\times}(f)$ follows from the fact that $\text{VCdim}(A)=2$, and the work of which used the PAC learning algorithm to construct an efficient (one round) communication protocol for $f$ under product distributions. The lower bound on $U(f)$ follows from that $\text{sign-rank}(A)\geq\Omega(N^{1/4})$, and the result of that showed that unbounded error communication complexity is equivalent to the logarithm of the sign rank. See for more details.

5 Counting VC classes

Let $c(N,d)$ denote the number of classes $C\subseteq\{\pm 1\}^{N}$ with VC dimension $d$. We give the following estimate of $c(N,d)$ for constant $d$ and $N$ large enough. The proof is given in Section 3.4.3.

For every $d>0$, there is $N_{0}=N_{0}(d)$ such that for all $N>N_{0}$:

Let $m(N,d)$ denote the number of maximum classes $C\subseteq\{\pm 1\}^{N}$ of VC dimension $d$. The problem of estimating $m(N,d)$ was proposed by . We provide the following estimate (see Section 3.4.3).

For every $d>1$, there is $N_{0}=N_{0}(d)$ such that for all $N>N_{0}$:

The gap between our upper and lower bound is roughly a multiplicative factor of $d+1$ in the exponent. In the previous bounds given by the gap was a multiplicative factor of $N$ in the exponent.

6 Counting graphs

Here we describe an application of our method for proving Theorem 5 to counting graphs with a given forbidden substructure.

Let $G=(V,E)$ be a graph (not necessarily bipartite). The universal graph $U(d)$ is defined as the bipartite graph with two color classes $A$ and $B=2^{A}$ where $|A|=d$, and the edges are defined as $\{a,b\}$ iff $a\in b$. The graph $G$ is called $U(d)$-free if for all two disjoint sets of vertices $A,B\subset V$ so that $|A|=d$ and $|B|=2^{d}$, the bipartite graph consisting of all edges of $G$ between $A$ and $B$ is not isomorphic to $U(d)$. In Theorem 24 of , which improves Theorem 2 there, it is proved that for $d\geq 2$, the number of $U(d+1)$-free graphs on $N$ vertices is at most

The proof in is quite involved, consisting of several technical and complicated steps. Our methods give a different, quick proof of an improved estimate, replacing the $(\log N)^{d+2}$ term by a single $\log N$ term.

For every fixed $d\geq 1$, the number of $U(d+1)$-free graphs on $N$ vertices is at most $2^{O(N^{2-1/d}\log N)}$.

The proof of the theorem is given in Section 3.4.4.

7 Geometry

Roughly speaking, the corollary says that there are no efficient ways to embed finite planes in real space using half spaces.

Proofs

Here we discuss the connection between VC dimension and dual sign rank.

We start with an equivalent definition of dual sign rank, that is based on the following notion. We say that a set of columns $C$ is antipodally shattered in a sign matrix $S$ if for each $v\in\{\pm 1\}^{C}$, either $v$ or $-v$ appear as a row in the restriction of $S$ to the columns in $C$.

The set of columns $C$ is antipodally shattered in $S$ if and only if in every matrix $M$ with $\text{sign}(M)=S$ the columns in $C$ are linearly independent.

First, assume $C$ is such that there exists some $M$ with $\text{sign}(M)=S$ in which the columns in $C$ are linearly dependent. For a column $j\in C$, denote by $M(j)$ the $j$’th column in $M$. Let $\{\alpha_{j}:j\in C\}$ be a set of real numbers so that $\sum_{j\in C}\alpha_{j}M(j)=0$ and not all $\alpha_{j}$’s are zero. Consider the vector $v\in\{\pm 1\}^{C}$ such that $v_{j}=1$ if $\alpha_{j}\geq 0$ and $v_{j}=-1$ if $\alpha_{j}<0$. The restriction of $S$ to $C$ does not contain $v$ nor $-v$ as a row, which certifies that $C$ is not antipodally shattered by $S$.

The dual sign rank of $S$ is the maximum size of a set of columns that are antipodally shattered in $S$.

The left inequality: The VC dimension of $S$ is at most the maximum size of a set of columns that is antipodally shattered in $S$, which by the above claim equals the dual sign rank of $S$.

The right inequality: Let $C$ be a largest set of columns that is antipodally shattered in $S$. By the claim above, the dual sign rank of $S$ is $|C|$. Let $A\subseteq C$ such that $|A|=\lfloor|C|/2\rfloor$. If $A$ is shattered in $S$ then we are done. Otherwise, there exists some $v\in\{\pm 1\}^{A}$ that does not appear in $S$ restricted to $A$. Since $C$ is antipodally shattered by $S$, this implies that $S$ contains all patterns in $\{\pm 1\}^{C}$ whose restriction to $A$ is $-v$. In particular, $S$ shatters $C\setminus A$ which is of size at least $\lfloor|C|/2\rfloor$.

2 Sign rank versus VC dimension

In this section we study the maximum possible sign rank of $N\times N$ matrices with VC dimension $d$, presenting the proofs of Proposition 1 and Theorems 5 and 4. We also show that the arguments supply a new, short proof and an improved estimate for a problem in asymptotic enumeration of graphs studied by .

Our goal in this section is to show that sign matrices with VC dimension one have sign rank at most $3$, and that $3$ is tight. Before reading this section, it may be a nice exercise to prove that the sign rank of the $N\times N$ signed identity matrix is exactly three (for $N\geq 4$).

Our goal in this section is to embed $M$ with VC dimension one in the plane using half spaces. The embedding is constructive and uses the following known claim (see, e.g., Theorem 11 in ).

Let $M$ be an $R\times C$ sign matrix with VC dimension one so that no row appears twice in it, and every column $c$ is shattered (i.e. the two values $\pm 1$ appear in it). Then, there is a column $c_{0}\in[C]$ and a row $r_{0}\in[R]$ so that $M_{r_{0},c_{0}}\neq M_{r,c_{0}}$ for all $r\neq r_{0}$ in $[R]$.

For every column $c$, denote by $\text{\it ones}_{c}$ the number of rows $r\in[R]$ so that $M_{r,c}=1$, and let $m_{c}=\min\{\text{\it ones}_{c},R-\text{\it ones}_{c}\}$. Assume without loss of generality that $m_{1}\leq m_{c}$ for all $c$, and that $m_{1}=\text{\it ones}_{1}$. Since all columns are shattered, $m_{1}\geq 1$. To prove the claim, it suffices to show that $m_{1}\leq 1$.

Assume towards a contradiction that $m_{1}\geq 2$. For $b\in\{1,-1\}$, denote by $M^{(b)}$ the submatrix of $M$ consisting of all rows $r$ so that $M_{r,1}=b$. The matrix $M^{(1)}$ has at least two rows. Since all rows are different, there is a column $c\neq 1$ so that two rows in $M^{(1)}$ differ in $c$. Specifically, column $c$ is shattered in $M^{(1)}$. Since $\text{VCdim}(M)=1$, it follows that $c$ is not shattered in $M^{(-1)}$, which means that the value in column $c$ is the same for all rows of the matrix $M^{(-1)}$. Therefore, $m_{c}<m_{1}$, which is a contradiction. ∎

The lemma immediately implies Threorem 2 due to the connection to sign rank discussed above.

The proof follows by induction on $C$. If $C=1$, the claim trivially holds.

The inductive step: If there is a column that is not shattered, then we can remove it, apply induction, and then add a half space that either contains or does not contain all points, as necessary. So, we can assume all columns are shattered. By Claim 17, we can assume without loss of generality that $M_{1,1}=1$ but $M_{r,1}=-1$ for all $r\neq 1$.

This is the construction. Its correctness follows by induction, by the choice of the last added half space which separates $x$ from all other points, and since if $x_{0}$ exists it belongs to the same cell as $x$ in the embedding of $M^{\prime}$. ∎

We conclude the section by showing that the bound $3$ above cannot be improved.

Finally, the signed identity matrix is not a submatrix of $M$. To see this, note that the four rows of the signed identity matrix have pairwise hamming distance two, but there are no such four points (not even three points) on this cycle of length eight.

2.2 The upper bound

In this subsection we prove Theorem 5. The proof is short, but requires several ingredients. The first one has been mentioned already, and appears in . For a sign matrix $S$, let $SC(S)$ denote the maximum number of sign changes (SC) along a column of $S$. Define $SC^{*}(S)=\min SC(M)$ where the minimum is taken over all matrices $M$ obtained from $S$ by a permutation of the rows.

For any sign matrix $S$, $\text{sign-rank}(S)\leq SC^{*}(S)+1$.

Of course we can replace here rows by columns, but for our purpose the above version will do. The second result we need is a theorem of (see also ). As observed, for example, in , plugging in its proof a result of improves it by a logarithmic factor, yielding the result we describe next. For a function $g$ mapping positive integers to positive integers, we say that a sign matrix $S$ satisfies a primal shatter function $g$ if for any integer $t$ and any set $I$ of $m$ columns of $S$, the number of distinct projections of the rows of $S$ on $I$ is at most $g(t)$. The result of Welzl (after its optimization following ) can be stated as follows The statement in and the subsequent papers is formulated in terms of somewhat different notions, but it is not difficult to check that it is equivalent to the statement below..

Let $S$ be a sign matrix with $N$ rows that satisfies the primal shatter function $g(t)=ct^{d}$ for some constants $c\geq 0$ and $d>1$. Then $SC^{*}(S)\leq O(N^{1-1/d})$.

Let $S$ be an $N\times N$ sign matrix of VC dimension $d>1$. By Sauer’s lemma , it satisfies the primal shatter function $g(t)=t^{d}$. Hence, by Lemma 20, $SC^{*}(S)\leq O(N^{1-1/d})$. Therefore, by Lemma 19, $\text{sign-rank}(S)\leq O(N^{1-1/d})$. ∎

The proof of Theorem 5 works, with essentially no change, for a larger class of sign matrices than the ones with VC dimension $d$. Indeed, the proof shows that the sign rank of any $N\times N$ matrix with primal shatter function at most $ct^{d}$ for some fixed $c$ and $d>1$ is at most $O(N^{1-1/d}).$ In this statement the estimate is sharp for all integers $d$, up to a logarithmic factor. This follows from the construction in , which supplies $N\times N$ boolean matrices so that the number of $1$ entries in them is at least $\Omega(N^{2-1/d})$, and they contain no $d$ by $D=(d-1)!+1$ submatrices of $1$’s. These matrices satisfy the primal shatter function $g(t)=D{t\choose d}+\sum_{i=0}^{d-1}{t\choose i}$ (with room to spare). Indeed, if we have more than that many distinct projections on a set of $t$ columns, we can omit all projections of weight at most $d-1$. Each additional projection contains $1$’s in at least one set of size $d$, and the same $d$-set cannot be covered more than $D$ times. Plugging this matrix in the counting argument that gives a lower bound for the sign rank using Lemma 22 proven below supplies an $\Omega(N^{1-1/d}/\log N)$ lower bound for the sign rank of many $N\times N$ matrices with primal shatter function $O(t^{d})$.

We have seen in Lemma 19 that sign rank is at most of order $SC^{*}$. Moreover, for a fixed $r$, many of the $N\times N$ sign matrices with sign rank at most $r$ also have $SC^{*}$ at most $r$: Indeed, a simple counting argument shows that the number of $N\times N$ sign matrices $M$ with $SC(M)<r$ is

so, the set of $N\times N$ sign matrices with $SC^{*}(M)<r$ is a subset of size $2^{\Omega(rN\log N)}$ of all $N\times N$ sign matrices with sign rank at most $r$.

How many $N\times N$ matrices of sign rank at most $r$ are there? by Lemma 22 proved in the next section, this number is at most $2^{O(rN\log N)}$. So, the set of matrices with $SC^{*}<r$ is a rather large subset of the set of matrices with sign rank at most $r$.

Indeed, fix some order on the rows of $S$, that is, order the points $P=\{p_{1},\ldots,p_{N}\}$ with $N=|P|$. The key point is that one of the hyperplanes $h_{0}\in H$ is so that the number of $i\in[N-1]$ for which $S_{p_{i},h_{0}}\neq S_{p_{i+1},h_{0}}$ is at least $(n^{d}-1)/(d(n-1))$: For each $i$ there is at least one hyperplane $h$ that separates $p_{i}$ and $p_{i+1}$, that is, for which $S_{p_{i},h}\neq S_{p_{i+1},h}$. The number of such pairs of points is $n^{d}-1$, and the number of hyperplanes is just $d(n-1)$.

2.3 The lower bound

In this subsection we prove Theorem 4. Our approach follows the one of , which is based on known bounds for the number of sign patterns of real polynomials. A similar approach has been subsequently used by to derive lower bounds for $f(N,d)$ for $d\geq 4$, but here we do it in a slightly more sophisticated way and get better bounds.

Although we can use the estimate in for the number of sign matrices with a given sign rank, we prefer to describe the argument by directly applying a result of , described next.

For $x\in V$, the sign pattern of $P$ at $x$ is the vector

Let $s(P)$ be the total number of sign patterns of $P$ as $x$ ranges over all of $V$. This number is bounded from above by the number of connected components of $V$.

An $N\times N$ matrix $M$ is of rank at most $r$ iff it can be written as a product $M=M_{1}\cdot M_{2}$ of an $N\times r$ matrix $M_{1}$ by an $r\times N$ matrix $M_{2}$. Therefore, each entry of $M$ is a quadratic polynomial in the $2Nr$ variables describing the entries of $M_{1}$ and $M_{2}$. We thus deduce the following from Warren’s Theorem stated above. A similar argument has been used by .

Let $r\leq N/2$. Then, the number of $N\times N$ sign matrices of sign rank at most $r$ does not exceed $(O(N/r))^{2Nr}\leq 2^{O(rN\log N)}$.

For a fixed $r$, this bound for the logarithm of the above quantity is tight up to a constant factor: As argued in Subsection 3.2.2, there are at least some $2^{\Omega(rN\log N)}$ matrices of sign rank $r$.

In order to derive the statement of Theorem 4 from the last lemma it suffices to show that the number of $N\times N$ sign matrices of VC dimension $d$ is sufficiently large. We proceed to do so. It is more convenient to discuss boolean matrices in what follows (instead of their signed versions).

1. The case $d=2$: Consider the $N\times N$ incidence matrix $A$ of the projective plane with $N$ points and $N$ lines, considered in the previous sections. The number of $1$ entries in $A$ is $(1+o(1))N^{3/2}$, and it does not contain $J_{2\times 2}$ (the $2\times 2$ all $1$ matrix) as a submatrix, since there is only one line passing through any two given points. Therefore, any matrix obtained from it by replacing ones by zeros has VC dimension at most $2$, since every matrix of VC dimension $3$ must contain $J_{2\times 2}$ as a submatrix. This gives us $2^{(1+o(1))N^{3/2}}$ distinct $N\times N$ sign matrices of VC dimension at most $2$. Lemma 22 therefore establishes the assertion of Theorem 4, part 1.

2. The case $d=3$: Call a $5\times 4$ binary matrix heavy if its rows are the all $1$ row and the $4$ rows with Hamming weight $3$. Call a $5\times 4$ boolean matrix heavy-dominating if there is a heavy matrix which is smaller or equal to it in every entry.

We claim that there is a boolean $N\times N$ matrix $B$ so that the number of $1$ entries in it is at least $\Omega(N^{23/15})$, and it does not contain any heavy-dominating $5\times 4$ submatrix. Given such a matrix $B$, any matrix obtained from $B$ by replacing some of the ones by zeros have VC dimension at most $3$. This implies part 2 of Theorem 4, using Lemma 22 as before.

The existence of $B$ is proved by a probabilistic argument. Let $C$ be a random binary matrix in which each entry, randomly and independently, is $1$ with probability $p=\frac{1}{2N^{7/15}}$. Let $X$ be the random variable counting the number of $1$ entries of $C$ minus twice the number of $5\times 4$ heavy-dominant submatrices $C$ contains. By linearity of expectation,

Fix a matrix $C$ for which the value of $X$ is at least its expectation. Replace at most two $1$ entries by $0$ in each heavy-dominant $5\times 4$ submatrix in $C$ to get the required matrix $B$.

3. The case $d=4$: The basic idea is as before, but here there is an explicit construction that beats the probabilistic one. Indeed, constructed an $N\times N$ boolean matrix $B$ so that the number of $1$ entries in $B$ is at least $\Omega(N^{5/3})$ and it does not contain $J_{3\times 3}$ as a submatrix (see also for another construction). No set of $5$ rows in every matrix obtained from this one by replacing $1$’s by $0$’s can be shattered, implying the desired result as before.

4. The case $d>4$: The proof here is similar to the one in part 2. We prove by a probabilistic argument that there is an $N\times N$ binary matrix $B$ so that the number of $1$ entries in it is at least

and it contains no heavy-dominant submatrix. Here, heavy-dominant means a $1+(d+1)+{{d+1}\choose 2}$ by $d+1$ matrix that is bigger or equal in each entry than the matrix whose rows are all the distinct vectors of length $d+1$ and Hamming weight at least $d-1$. Any matrix obtained by replacing $1$’s by $0$’s in $B$ cannot have VC dimension exceeding $d$. The result follows, again, from Lemma 22.

We start as before with a random matrix $C$ in which each entry, randomly and independently, is chosen to be $1$ with probability

3 Sign rank and spectral gaps

The lower bound on the sign rank uses Forster’s argument , who showed how to relate sign rank to spectral norm. He proved that if $S$ is an $N\times N$ sign matrix then

We would like to apply Forster’s theorem to the matrix $S$ in our explicit examples. The spectral norm of $S$, however, is too large to be useful: If $S$ is $\Delta\leq N/3$ regular and $x$ is the all $1$ vector then $Sx=(2\Delta-N)x$ and so $\|S\|\geq N/3$. Applying Forster’s theorem to $S$ yields that its sign rank is $\Omega(1)$, which is not informative.

Our solution is based on the observation that Forster’s argument actually proves a stronger statement. His proof works as long as the entries of the matrix are not too close to zero, as was already noticed in . We therefore use a variant of the spectral norm of a sign matrix $S$ which we call star norm and denote by The minimizer belongs to a closed subset of the bounded set $\{M:\|M\|\leq\|S\|\}$.

Three comments seem in place. (i) We do not think of the star norm as a norm. (ii) It is always at most the spectral norm, $\|S\|^{*}\leq\|S\|$. (iii) Every $M$ in the above minimum satisfies $\text{sign-rank}(M)=\text{sign-rank}(S)$.

Let $S$ be an $N\times N$ sign matrix. Then,

For completeness, in Section 3.3.2 we provide a short proof of this theorem (which uses the main lemma from as a black box). To get any improvement using this theorem, we must have $\|S\|^{*}\ll\|S\|$. It is not a priori obvious that there is a matrix $S$ for which this holds. The following lemma shows that spectral gaps yield such examples.

Let $S$ be a $\Delta$ regular $N\times N$ sign matrix with $\Delta\leq N/2$, and $B$ its boolean version. Then,

In other words, every regular sign matrix whose boolean version has a spectral gap has a small star norm. Theorem 23 and Theorem 24 immediately imply Theorem 6. In Section 2.2, we provided concrete examples of matrices with a spectral gap, that have applications in communication complexity, learning theory and geometry.

Observe that since $N\geq 2\Delta$ it follows that $M_{i,j}S_{i,j}\geq 1$ for all $i,j$. So,

Since $B$ is regular, the all $1$ vector $y$ is a right singular vector of $B$ with singular value $\Delta$. Specifically, $My=0$. For every $x$, write $x=x_{1}+x_{2}$ where $x_{1}$ is the projection of $x$ on $y$ and $x_{2}$ is orthogonal to $y$. Thus,

Note that $\|B\|\leq\Delta$ (and hence $\|B\|=\Delta$). Indeed, since $B$ is regular, there are $\Delta$ permutation matrices $B^{(1)},\ldots,B^{(\Delta)}$ so that $B$ is their sum. The spectral norm of each $B^{(i)}$ is one. The desired bound follows by the triangle inequality.

Finally, since $x_{2}$ is orthogonal to $y$,

It is interesting to understand whether the approach above can give a better lower bound on sign rank. There are two parts to the argument: Forster’s argument, and the upper bound on $\|S\|^{*}$. We can try to separately improve each of the two parts.

Any improvement over Forster’s argument would be very interesting, but as mentioned there is no significant improvement over it even without the restriction induced by VC dimension, so we do not discuss it further.

To improve the second part, we would like to find examples with the biggest spectral gap possible. The Alon-Boppana theorem optimally describes limitations on spectral gaps. The second eigenvalue $\sigma$ of a $\Delta$ regular graph is not too small,

where the $o(1)$ term vanishes when $N$ tends to infinity (a similar statement holds when the diameter is large ). Specifically, the best lower bound on sign rank this approach can yield is roughly $\sqrt{\Delta}/2$, at least when $\Delta\leq N^{o(1)}$.

But what about general lower bounds on $\|S\|^{*}$? It is well known that any $N\times N$ sign matrix $S$ satisfies $\|S\|\geq\sqrt{N}$. We prove a generalization of this statement.

Let $S$ be an $N\times N$ sign matrix. For $i\in[N]$, let $\gamma_{i}$ be the minimum between the number of $1$’s and the number of $-1$’s in the i’th row. Let $\gamma=\gamma(S)=\max\{\gamma_{i}:i\in[N]\}$. Then,

This lemma provides limitations on the bound from Theorem 24. Indeed, $\gamma(S)\leq\frac{N}{2}$ and $\frac{N-\gamma}{\sqrt{\gamma}+1}$ is a monotone decreasing function of $\gamma$, which implies $\|S\|^{*}\geq\Omega(\sqrt{N})$. Interestingly, Lemma 25 and Theorem 24 provide a quantitively weaker but a more general statement than the Alon-Boppana theorem: If $B$ is a $\Delta$ regular $N\times N$ boolean matrix with $\Delta\leq N/2$, then

This bound is off by roughly a factor of two when the diameter of the graph is large. When the diameter is small, like in the case of the projective plane which we discuss in more detail below, this bound is actually almost tight: The second largest singular value of the boolean point-line incidence matrix of a projective plane of order $n$ is $\sqrt{n}$ while this matrix is $n+1$ regular (c.f., e.g., ).

It is perhaps worth noting that in fact here there is a simple argument that gives a slightly stronger result for boolean regular matrices. The sum of squares of the singular values of $B$ is the trace of $B^{t}B$, which is $N\Delta$. As the spectral norm is $\Delta$, the sum of squares of the other singular values is $N\Delta-\Delta^{2}=\Delta(N-\Delta)$, implying that

which is (slightly) larger than the bound above.

Let $M$ be a matrix so that $\|M\|=\|S\|^{*}$ and $M_{i,j}S_{i,j}\geq 1$ for all $i,j$. Assume without loss of generality Multiplying a row by $-1$ does not affect $\|S\|^{*}$. that $\gamma_{i}$ is the number of $-1$’s in the $i$’th row of $S$. If $\gamma=0$, then $S$ has only positive entries which implies $\|M\|\geq N$ as claimed. So, we may assume $\gamma\geq 1$. Let $t$ be the largest real so that

That is, if $\gamma=1$ then $t=\frac{N-\gamma}{2}$ and if $\gamma>1$ then

There are two cases to consider. One is that for all $i\in[N]$ we have $\sum_{j}M_{i,j}\geq t$. In this case, if $x$ is the all $1$ vector then

The second case is that there is $i\in[N]$ so that $\sum_{j}M_{i,j}<t$. Assume without loss of generality that $i=1$. Denote by $C$ the subset of the columns $j$ so that $M_{1,j}<0$. Thus,

Convexity of $x\mapsto x^{2}$ implies that

In this case, if $x$ is the vector with $1$ in the first entry and $0$ in all other entries then

Since $\|(M)^{T}\|=\|M\|$, it follows that $\|M\|\geq t$. ∎

3.2 Forster’s theorem

Here we provide a proof of Forster’s theorem, that is based on the following key lemma, which he proved.

where $I$ is the identity matrix, and $Bx\otimes Bx$ is the rank one matrix with $(i,j)$ entry $(Bx)_{i}(Bx)_{j}$.

The lemma shows that every $X$ in general position can be linearly mapped to $BX$ that is, in some sense, equidistributed. In a nutshell, the proof of the lemma is by finding $B_{1},B_{2},\ldots$ so that each $B_{i}$ makes $B_{i-1}X$ closer to being equidistributed, and finally using that the underlying object is compact, so that this process reaches its goal.

If necessary replace $X$ by $BX$ and $Y$ by $(B^{T})^{-1}Y$, and then normalize (the assumption required in the lemma that $X$ is in general position may be obtained by a slight perturbation of its vectors).

The proof continues by bounding $D=\sum_{x\in X,y\in Y}M_{x,y}\langle x,y\rangle$ in two different ways.

First, bound $D$ from above: Observe that for every two vectors $u,v$, Cauchy-Schwartz inequality implies

Second, bound $D$ from below: Since $|M_{x,y}|\geq 1$ and $|\langle x,y\rangle|\leq 1$ for all $x,y$, using (2),

4 Applications

It is well known that the VC dimension of $A$ is $d$, but we provide a brief explanation. The VC dimension is at least $d$ by considering any set of $d$ independent points (i.e. so that no strict subset of it spans it). The VC dimension is at most $d$ since every set of $d+1$ points is dependent in a $d$ dimensional space.

The lower bound on the sign rank follows immediately from Theorem 6, and the following known bound on the spectral gap of these matrices.

If $B$ is the boolean version of $A$ then

The proof is so short that we include it here.

We use the following two known properties (see, e.g., ) of projective spaces. Both the number of distinct hyperplanes through a point and the number of distinct points on a hyperplane are $N_{n,d-1}$. The number of hyperplanes through two distinct points is $N_{n,d-2}$.

The first property implies that $A$ is $\Delta=N_{n,d-1}$ regular. These properties also imply

where $J$ is the all $1$ matrix. Therefore, all singular values except the maximum one are $n^{\frac{d-1}{2}}$. ∎

Thus, $R$ is indeed a maximum class of VC dimension $2$.

Next we show that there exists a choice of a linear order for each line such that the resulting $R$ has sign rank $\Omega(N^{\frac{1}{2}}/\log N)$. By the proof of Theorem 4, case $d=2$, there is a choice of a subset for each line such that the resulting $N$ subsets form a class of sign rank $\Omega(N^{\frac{1}{2}}/\log N)$. We can therefore pick the linear orders in such a way that each of these $N$ subsets forms an interval, and the resulting maximum class (of all possible intervals with respect to these orders) has sign rank at least as large as $\Omega(N^{\frac{1}{2}}/\log N)$. ∎

4.2 Computing the sign rank

In this section we describe an efficient algorithm that approximates the sign rank (Theorem 9).

The algorithm uses the following notion. Let $V$ be a set. A pair $v,u\in V$ is crossed by a vector $c\in\{\pm 1\}^{V}$ if $c(v)\neq c(u)$. Let $T$ be a tree with vertex set $V=[N]$ and edge set $E$. Let $S$ be a $V\times[N]$ sign matrix. The stabbing number of $T$ in $S$ is the largest number of edges in $T$ that are crossed by the same column of $S$. For example, if $T$ is a path then $T$ defines a linear order (permutation) on $V$ and the stabbing number is the largest number of sign changes among all columns with respect to this order.

Welzl gave an efficient algorithm for computing a path $T$ with a low stabbing number for matrices $S$ with VC dimension $d$. The analysis of the algorithm can be improved by a logarithmic factor using a result of .

There exists a polynomial time algorithm such that given a $V\times[N]$ sign matrix $S$ with $|V|=N$, outputs a path on $V$ with stabbing number at most $200N^{1-1/d}$ where $d=VC(S)$.

For completeness, and since to the best of our knowledge no explicit proof of this theorem appears in print, we provide a description and analysis of the algorithm. We assume without loss of generality that the rows of $S$ are pairwise distinct.

We start by handling the case This analysis also provides an alternative proof for Lemma 18. $d=1$. In this case, we directly output a tree that is a path (i.e., a linear order on $V$). If $d=1$, then Claim 17 implies that there is a column with at most $2$ sign changes with respect to any order on $V$. The algorithm first finds by recursion a path $T$ for the matrix obtained from $S$ by removing this column, and outputs the same path $T$ for the matrix $S$ as well. By induction, the resulting path has stabbing number at most $2$ (when there is a single column the stabbing number can be made $1$).

For $d>1$, the algorithm constructs a sequence of $N$ forests $F_{0},F_{1},\ldots,F_{N-1}$ over the same vertex set $V$. The forest $F_{i}$ has exactly $i$ edges, and is defined by greedily adding an edge $e_{i}$ to $F_{i-1}$. As we prove below, the tree $F_{N-1}$ has a stabbing number at most $100N^{1-1/d}$. The tree $F_{N-1}$ is transformed to a path $T$ as follows. Let $v_{1},v_{2},\ldots,v_{2N-1}$ be an eulerian path in the graph obtained by doubling every edge in $F_{N-1}$. This path traverses each edge of $F_{N-1}$ exactly twice. Let $S^{\prime}$ be the matrix with $2N-1$ rows and $N$ columns obtained from $S$ be putting row $v_{i}$ in $S$ as row $i$, for $i\in[2N-1]$. The number of sign changes in each column in $S^{\prime}$ is at most $2\cdot 100N^{1-1/d}$. Finally, let $T$ be the path obtained from the eulerian path by leaving a single copy of each row of $S$. Since deleting rows from $S^{\prime}$ cannot increase the number of sign changes, the path $T$ is as stated.

The edge $e_{i}$ is chosen as follows. The algorithm maintains a probability distribution $p_{i}$ on $[N]$. The weight $w_{i}(e)$ of the pair $e=\{v,u\}$ is the probability mass of the columns $e$ crosses, that is, $w_{i}(e)=p_{i}(\{j\in[N]:S_{u,j}\neq S_{v,j}\})$. The algorithm chooses $e_{i}$ as an edge with minimum $w_{i}$-weight among all edges that are not in $F_{i-1}$ and do not close a cycle in $F_{i-1}$.

The distributions $p_{1},\ldots,p_{N}$ are chosen iteratively as follows. The first distribution $p_{1}$ is the uniform distribution on $[N]$. The distribution $p_{i+1}$ is obtained from $p_{i}$ by doubling the relative mass of each column that is crossed by $e_{i}$. That is, let $x_{i}=w_{i}(e_{i})$, and for every column $j$ that is crossed by $e_{i}$ define $p_{i+1}(j)=\frac{2p_{i}(j)}{1+x_{i}}$, and for every other column $j$ define $p_{i+1}(j)=\frac{p_{i}(j)}{1+x_{i}}$.