Approximating Subadditive Hadamard Functions on Implicit
Matrices

arXiv:1511.00838v1 [cs.DS] 3 Nov 2015

Vladimir Braverman∗

Alan Roytman†

Gregory Vorsanger∗

Abstract
An important challenge in the streaming model is to maintain small-space approximations
of entrywise functions performed on a matrix that is generated by the outer product of two
vectors given as a stream. In other works, streams typically define matrices in a standard way
via a sequence of updates, as in the work of Woodruff [22] and others. We describe the matrix
formed by the outer product, and other matrices that do not fall into this category, as implicit
matrices. As such, we consider the general problem of computing over such implicit matrices with
Hadamard functions, which are functions applied entrywise on a matrix. In this paper, we apply
this generalization to provide new techniques for identifying independence between two vectors
in the streaming model. The previous state of the art algorithm of Braverman and Ostrovsky [9]
gave a (1 ± ǫ)-approximation for the L1 distance between the product and joint distributions,
using space O(log1024 (nm)ǫ−1024 ), where m is the length of the stream and n denotes the size
of the universe from which stream elements are drawn. Our general techniques include the L1
−7
distance as a special case, and we give an improved space bound of O(log12 (n) log2 ( nm
).
ǫ )ǫ

1

Introduction

Measuring Independence is a fundamental statistical problem that is well studied in computer
science. Traditional non-parametric methods of testing independence over empirical data usually
require space complexity that is polynomial in either the support size or input size. With large
datasets, these space requirements may be impractical, and designing small-space algorithms becomes desirable.
Measuring independence is a classic problem in the field of statistics (see Lehmann [17]) as
well as an important problem in databases. Further, the process of reading in a two-column
database table can be viewed as a stream of pairs. Thus, the streaming model is a natural choice
when approximating pairwise independence as memory is limited. Indeed, identifying correlations
between database columns by measuring the level of independence between columns is of importance
to the database and data warehouse community (see, e.g., [19] and [16], respectively).
In this paper we provide new techniques for measuring independence between two vectors in the
streaming model and present new tools to expand existing techniques. The topic of independence
was first studied in the streaming model by Indyk and McGregor [15] where the authors gave an
optimal algorithm for approximating the L2 distance between the product and joint distributions
of two random variables which generate a stream. In their work, they provided a sketch that is
∗
†

Department of Computer Science, Johns Hopkins University; vova@cs.jhu.edu, gregvorsanger@jhu.edu
School of Computer Science, Tel-Aviv University; alan.roytman@cs.tau.ac.il

1

pairwise independent, but not 4-wise independent, so analysis similar to that of Alon, Matias, and
Szegedy [3] cannot be applied directly. This work was continued by Braverman and Ostrovsky [9],
where the authors considered comparing among a stream of k-tuples and provided the first (1 ± ǫ)approximation for the L1 distance between the product and joint distributions. Their algorithm
1
log1024 (nm)) space for k = 2, where m
is currently the best known space bound, and uses O( ǫ1024
is the length of the stream and n denotes the size of the universe from which stream elements are
drawn. We present new methods, in the form of a general tool, that enable us to improve this
bound to O( ǫ17 log12 (n) log2 ( nm
ǫ )). In previous works, a central challenge has been maintaining an
approximation of the matrix that is generated by the outer product of the two streaming vectors.
As such, we consider computing functions on such an implicit matrix. While, matrices have been
studied previously in the streaming model (e.g., [22]), note that we cannot use standard linear
sketching techniques, as the entries of the matrix are given implicitly and thus these methods do
not apply directly.
Generalizing this specific motivating example, we consider the problem of obtaining a (1 ± ǫ)approximation of the L1 norm of the matrix g[A], where g[A] is the matrix A with a function g
applied to it entrywise. Such mappings g are called Hadamard functions (see [12, 13]). Note that
we sometimes abuse notation and apply the function g to scalar values instead of matrices (e.g.,
g(aij ) where aij is the (i, j)th entry in matrix A). We require the scalar form of function g to
be even, subadditive, non-negative,
P P and zero at the origin. Wethshow that, given a blackbox r(n)approximation of kg[A]k1 = i j g(aij ) (where aij is the (i, j) entry in matrix A) and a blackbox
(1 ± ǫ)-approximation of the aggregate of g applied entrywise to a vector obtained by summing
over all rows, we are able to improve the r(n)-approximation to a (1 ± ǫ)-approximation (where
r(n) is a sufficiently large monotonically increasing function of n). Hence, we give a reduction for
any such function g. Our reduction can be applied as long as such blackbox algorithms exist. An
interesting special case of our result is when the matrix is defined by the L1 distance between the
joint and product distributions, which corresponds to measuring independence in data streams.
Such algorithms are known for L1 , but not for Lp for 0 < p < 1. If such algorithms for the Lp
distance were to be designed, our reductions work and can be applied. Note that, while there
are a variety of ways to compute distances between distributions, the Lp distance is of particular
significance as evidenced in [14].

Motivating Problem
We begin by presenting our motivating problem, which concerns (approximately) measuring the
distance between the product and joint distributions of two random variables. That is, we attempt
to quantify how close two random variables X and Y over a universe [n] = {1, . . . , n} are to being
independent. There are many ways to measure the distance between distributions, but we focus
on the L1 distance. Recall that two random variables X and Y are independent if, for every i and
j, we have Pr[X = i ∧ Y = j] = Pr[X = i] Pr[Y = j]. In our model, we have a data stream D
which is presented as a sequence of m pairs a1 = (i1 , j1 ), a2 = (i2 , j2 ), . . . , am = (im , jm ). Each pair
ak = (ik , jk ) consists of two integers taken from the universe [n].
Intuitively, we imagine that the two random variables X and Y over the universe [n] generate
these pairs, and in particular, the frequencies of each pair (i, j) define an empirical joint distribution,
which is the fraction of pairs that equal (i, j). At the same time, the stream also defines the empirical
marginal distributions Pr[X = i], Pr[Y = j], namely the fraction of pairs of the form (i, ·) and (·, j),
respectively. We note that, even if the pairs are actually generated from two independent sources,
2

it may not be the case that the empirical distributions reflect this fact, although for sufficiently
long streams the joint distribution should approach the product of the marginal distributions for
each i and j. This fundamental problem has received considerable attention within the streaming
community, including the works of [9, 15].
Problem 1. Let X and Y be two random variables defined by the stream of m pairs a1 =
(i1 , j1 ), . . . , am = (im , jm ), where each ik , jk ∈ [n] for all k. Define the frequencies fi = |{k : ak =
(i, ·)}| and fj = |{k : ak = (·, j)}| (i.e., the frequency with which i appears in the first coordinate and
j appears in the second coordinate, respectively). Moreover, let fij = |{k : ak = (i, j)}| be the frequency with which the pair (i, j) appears in the stream. This naturally defines the joint distribution
f f
f
P r[X = i ∧ Y = j] = mij and the product of the marginal distributions P r[X = i]P r[Y = j] = mi 2j .
The L1 distance between the product and joint distributions is given by:
n X
n
X
fi fj
fij
− 2 .
m
m
i=1 j=1

If X and Y are independent, we should expect this sum to be close to 0, assuming the stream
is sufficiently long. As a generalization to this problem, we can view the n2 values which appear in
f
ff
the summation as being implicitly represented via an n×n matrix A, where entry aij = mij − mi 2j .
For the motivating problem, this matrix is given implicitly as it is not given up front and changes
over time according to the data stream (each new pair in the stream may change a particular
entry in the matrix). However, one can imagine settings in which these entries are defined through
other means. In practice, we may still be interested in computing approximate statistics over such
implicitly defined matrices.

Contributions and Techniques
Our main contributions in this paper make progress on two important problems:
1. For any subadditive, even Hadamard function g where g is non-negative and g(0) = 0, given
an implicitly defined n × n matrix A with entries aij , let g[A] be the matrix where the
(i, j)th entry is g(aij ). We
first to provide a general reduction framework for apP are
Pthe
n
proximating kg[A]k1 =
i=1
j=1 g(aij ) to within a (1 ± ǫ)-factor with constant success
probability. More formally, suppose we have two blackbox algorithms with the following
guarantees. One blackbox algorithm operates over
implicit matrix A and provides a very
P theP
good (≈ 1 ± ǫ) approximation to kg[JA]k1 = nj=1 g( ni=1 aij ) except with inverse polylogarithmic probability, where J = (1, . . . , 1) is the row vector of dimension n with every entry
equal to 1. The second blackbox algorithm operates over the implicit matrix A and solves
the problem we wish to solve (i.e., approximating kg[A]k1 ) with constant success probability,
although it does so with a multiplicative approximation ratio of r(n) (which may be worse
than (1 ± ǫ) in general). We show how to use these two blackbox algorithms and construct
an algorithm that achieves a (1 ± ǫ)-approximation of kg[A]k1 . If S1 , S2 denote the space
used
first and second blackbox algorithms,
respectively, then our algorithm uses space

 4by the
r (n)log 8 (n)
3
· (log (n) + S1 + log(n) · S2 ) . We state this formally in Theorem 1.
O
ǫ5

2. Given the contribution above, it follows that setting g(x) = |x| solves Problem 1, namely the
problem of measuring how close two random variables are to being independent, as long as
3

such blackbox algorithms exist. In particular, the work of Indyk [14] provides us with the first
blackbox algorithm, and the work of [15] provides us with the second blackbox algorithm for
this choice of g. Combining these results, we improve over the previous state of the art result
of Braverman and Ostrovsky [9] and give improved bounds for measuring independence
of


log(nm) 1024
random variables in the streaming model by reducing the space usage from O ( ǫ )

to O ǫ17 log12 (n) log2 ( nm
ǫ ) (see Table 1).
Previous Work

L1 approximation

IM08 [15]

log(n)

BO101 [9]

(1 ± ǫ)

Our Result

(1 ± ǫ)

Memory


log mǫ
O ǫ12 log nm
ǫ



log(nm) 1024
O
ǫ

O

1
ǫ7

log12 (n) log2

nm
ǫ



.

Table 1: Comparing Approximation Ratios and Space Complexity
Examples of such Hadamard functions which are subadditive, even, non-negative, and zero at
the origin include g(x) = |x|p , for any 0 < p ≤ 1. Note that our reduction in the first item can
only be applied to solve the problem of approximating kg[A]k1 if such blackbox algorithms exist,
but for some functions g this may not be the case. As a direct example of the tools we present,
we give a reduction for computing the Lp distance for 0 < p < 1 between the joint and product
distributions in the streaming model (as this function is even and subadditive). However, to the
best of our knowledge, such blackbox algorithms do not exist for computing the Lp distance. Thus,
as a corollary to our main result, the construction of such blackbox algorithms that are space
efficient would immediately yield an algorithm that measures independence according to the Lp
distance that is also space efficient.
Our techniques leverage concepts provided in [9, 15] and manipulates them to allow them to be
combined with the Recursive Sketches data structure [11] to gain a large improvement compared
to existing bounds. Note that we cannot use standard linear sketching techniques because the
entries of the matrix are given implicitly. Moreover, the sketch of Indyk and McGregor [15] is
pairwise independent, but not 4-wise independent. Therefore, we cannot apply the sketches of [3,15]
directly. We first present an algorithm, independent of the streaming model, for finding heavy rows
of a matrix norm given an arbitrary even subadditive Hadamard function g. We then apply the
Recursive Sum algorithm from [11] on top of our heavy rows algorithm to obtain our main result.

1.1

Related Work

In their seminal 1996 paper Alon, Matias and Szegedy [3] provided an optimal space approximation
for L2 . A key technical requirement of the sketch is the assumption of 4-wise independent random
variables. This technique is the building block for measuring the independence of data streams
using L2 distances as well.
1

The paper of [9] provides a general bound for the L1 distance for k-tuples, but we provide analysis for pairs of
elements, k = 2, in this paper. The bound in the table is for k = 2.

4

The problems of efficiently testing pairwise, or k-wise, independence were considered by Alon,
Andoni, Kaufman, Matulef, Rubinfeld and Xie [1]; Alon, Goldreich and Mansour [2]; Batu, Fortnow, Fischer, Kumar, Rubinfeld and White [4]; Batu, Kumar and Rubinfeld [7]; Batu, Fortnow,
Rubinfield, Smith and White [5] and [6]. They addressed the problem of minimizing the number
of samples needed to obtain a sufficient approximation, when the joint distribution is accessible
through a sampling procedure.
In their 2008 work, Indyk and McGregor [15] provided exciting results for identifying the correlation of two streams, providing an optimal bound for determining the L2 distance between the
product and joint distributions of two random variables.
In addition to the L2 result, Indyk and McGregor presented a log(n)-approximation for the
L1 distance. This bound was improved to a (1 ± ǫ)-approximation in the work of Braverman
1
log1024 (nm)) for pairs of elements.
and Ostrovsky [9] in which they provided a bound of O( ǫ1024
Further, they gave bounds for the comparison of multiple streaming vectors and determining kwise relationships for L1 distance. Additionally, in [8] Braverman et al. expanded the work of [15]
to k dimensions for L2 . While our paper only addresses computation on matrices resulting from
pairwise comparison (k = 2), we believe the techniques presented here can be expanded to tensors,
(i.e., when stream elements are k-tuples), similarly to [8]. Recently, McGregor and Vu [18] studied
a related problem regarding Bayesian networks in the streaming model.
Statistical Distance, L1 , is one of the most fundamental metrics for measuring the similarity of
two distributions. It has been the metric of choice in many of the above testing papers, as well as
others such as Rubinfeld and Servedio [20]; Sahai and Vadhan [21]. As such, a main focus of this
work is improving bounds for this measure in the streaming model.

2

Problem Definition and Notation

In this paper we focus on the problem of approximating even, subadditive, non-negative Hadamard
functions which are zero at the origin on implicitly defined matrices (e.g., the streaming model
implicitly defines matrices for us in the context of measuring independence). The main problem
we study in this paper is the following:
Problem 2. Let g be any even, subadditive, non-negative Hadamard function such that g(0) = 0.
Given any implicit matrix A, for any ǫ > 0, δ > 0, output a (1 ± ǫ)-approximation of kg[A]k1 except
with probability δ.
We now provide our main theorem, which solves Problem 2.
Theorem 1. Let g be any even, subadditive, non-negative Hadamard function g where g(0) = 0,
and fix ǫ > 0. Moreover, let A be an arbitrary matrix, and J be the all 1’s row vector J = (1, . . . , 1)
of dimension n. Suppose there are two blackbox algorithms with the following properties:
1. Blackbox Algorithm 1, for all ǫ′ > 0, returns a (1 ± ǫ′ )-approximation of kg[JA]k1 , except with
probability δ1 .
2. Blackbox Algorithm 2 returns an r(n)-approximation of kg[A]k1 , except with probability δ2
(where r(n) is a sufficiently large monotonically increasing function of n).

5

Then, there exists an algorithm that returns a (1 ± ǫ)-approximation of kg[A]k1 , except with
constant probability. If Blackbox Algorithm 1 uses space SP ACE1(n, δ1 , ǫ′ ), and Blackbox Algorithm
2 uses space SP ACE2(n, δ2 ), the resulting algorithm has space complexity


1 4
1 4
1 4
10
8
′
9
O 5 r (n) log (n) + 5 r (n) log (n)SP ACE1(n, δ1 , ǫ ) + 5 r (n) log (n)SP ACE2(n, δ2 ) ,
ǫ
ǫ
ǫ
where ǫ′ = 2ǫ , δ1 is a small constant, and δ2 is inverse polylogarithmic.
Note that we can reduce the constant failure probability to inverse polynomial failure probability
via standard techniques, at the cost of increasing our space bound by a logarithmic factor. Observe
that Problem 2 is a general case of Problem 1 where g(x) = |x| (i.e., L1 distance). In the streaming
model, we receive matrix A implicitly, but we conceptualize the problem as if the matrix were given
explicitly and then resolve this issue by assuming we have blackbox algorithms that operate over
the implicit matrix.
We define our stream such that each element in the stream ak is a pair of values (i, j):
Definition 1 (Stream). Let m, n be positive integers. A stream D = D(m,n) is a sequence of
length m, a1 , a2 , . . . , am , where each entry is a pair of values in {0, . . . , n}.
Let g : R → R be a non-negative, subadditive, and even function where g(0) = 0. Frequently,
we will need to discuss a matrix where g has been applied to every entry. We use the notations
from [12] which are in turn based on notations from [13].
Definition 2 (Hadamard Function). Given Matrix A of dimensions n × n a Hadamard function
g takes as input a matrix A and is applied entrywise to every entry of the matrix. The output is
matrix g[A]. Further, we note that the L1 norm of g[A] is equivalent to the value we aim to
n
n P
P
approximate, kg[A]k1 =
g(aij ).
i=1 j=1

We frequently use hash functions in our analysis, we now specify some notation. We sometimes
express a hash function H as a vector of values {h1 , h2 , ..., hn }. Multiplication of hash functions,
denoted H ′ = HAD(H a , H b ), is performed entrywise such that {h′1 = ha1 hb1 , ..., h′n = han hbn }.
We now define two additional matrices. All matrices in our definitions are of size n × n, and all
vectors are of size 1 × n. We denote by [n] the set {1, . . . , n}.
Definition 3 (Sampling Identity Matrix). Given a hash function H : [n] → {0, 1}, let hi = H(i).
The Sampling Identity Matrix IH with
( entries bij is defined as:
bii = hi
IH =
bij = 0 for i 6= j.
That is, the diagonal of IH are the values of H. When we multiply matrix IH by A, each row of IH A
is either the zero vector (corresponding to hi = 0) or the original row i in matrix A (corresponding
to hi = 1). We use the term “sampling” due to the fact that the hash functions we use throughout
this paper are random, and hence which rows remain untouched is random. The same observations
apply to columns when considering the matrix AIH .
Definition 4 (Row Aggregation Vector). A Row Aggregation Vector J is a 1 × n vector with
all entries equal to 1.
6

Thus, JA yields a vector V where each value vi is

Pn

j=1 aij .

Black Box Algorithm 1. (1 ± ǫ′ )-Approximation of g on a Row Aggregate Vector
Input: Matrix A, and hash function H.
Output: (1 ± ǫ′ )-approximation of kg[JIH A]k1 with probability (1 − δ1 ).
The space Black Box Algorithm 1 (BA1) uses is referred to as SP ACE1(n, δ1 , ǫ′ ) in our analysis.
Black Box Algorithm 2. r(n)-Approximation of kg[IH A]k1
Input: Matrix A and hash function H.
Output: An r(n)-approximation of kg[IH A]k1 with probability (1 − δ2 ).
The space Black Box Algorithm 2 (BA2) uses is referred to as SP ACE2(n, δ2 ) in our analysis.
Definition 5 (Complement Hash Function). For hash function H : [n] → {0, 1} define the Complement Hash Function H̄ as H̄(i) = 1 if and only if H(i) = 0.
Definition 6 (Threshold Functions). We define two threshold functions, which we denote by
2 (n)
4
and τ (n, ǫ) = 2rO(ǫ)
.
ρ(n, ǫ) = r (n)
ǫ
Definition 7 (Weight of a Row). The weight of row i in matrix A is uA,i , where uA,i =

n
P

aij .

j=1

Definition 8 (α-Heavy Rows). Row i is α-heavy for 0 < α < 1 if uA,i > αkAk1 .
Definition 9 (Key Row). We say row i is a Key Row if: uA,i > ρ(n, ǫ)(kAk1 − uA,i ).

While Definition 8 and Definition 9 are similar, we define them for convenience, as our algorithm
works by first finding key rows and then building on top of this to find α-heavy rows. We note
that, as long as ρ(n, ǫ) ≥ 1, a matrix can have at most one key row (since any matrix can have at
ρ(n,ǫ)
).
most α1 α-heavy rows, and a key row is α-heavy for α = 1+ρ(n,ǫ)

3

Subadditive Approximations

In this section we show that a (1 ± ǫ)-approximation of even, subadditive, non-negative Hadamard
functions which are zero at the origin are preserved under row or column aggregations in the
presence of sufficiently heavy rows or columns.
Theorem 2. Let B be an n × n matrix and let ǫ ∈ (0, 1) be a parameter. Recall that J is a row
vector with all entries equal to 1. Let gP
be any even, subadditive, non-negative
Hadamard function
P
which satisfies g(0) = 0. Denote ui = nj=1 g(bij ), and thus kg[B]k1 = ni=1 ui . If there is a row
h such that uh ≥ (1 − 2ǫ )kg[B]k1 then |uh − kg[JB]k1 | ≤ ǫkg[JB]k1 .
Proof. Denote V = JB. Without loss of generality assume u1 is the row such that u1 ≥ (1 −
1
ǫ
2 )kg[B]k1 . By subadditivity of g: kg[V ]k1 ≤ kg[B]k1 ≤ 1− 2ǫ u1 ≤ (1 + ǫ)u1 . Further, we have b1j =
Pn
Pn
( i=1 bij −P i=2 bij ). Since
Pn g is even and subadditive, and such functions are non-negative,
Pn
Pn we have
n
bij ) + i=2 g(bij ). Rearranging and summing over j, we get:
g(b
j=1 g ( i=1 bij ) ≥
Pn1j ) ≤ g ( i=1P
n
)
−
g(b
)).
(g(b
1,j
ij
j=1
i=2
7

Therefore:
kg[V ]k1 =

n
X
j=1

g

n
X
i=1

bij

!

≥

n
X

g(b1,j ) −

n
X

g(bij )

i=2

j=1

!!

= u1 − (kg[B]k1 − u1 ).

Finally:

kg[V ]k1 ≥ u1 − (kg[B]k1 − u1 ) = 2u1 − kg[B]k1 ≥ u1 (2 −

4

1
1−ǫ
≥ u1 (1 − ǫ).
ǫ ) = u1
1− 2
1 − 2ǫ

Algorithm for Finding Key Rows

Definition 10 (Algorithm for Finding Key Rows).
Input: Matrix A and Sampling Identity Matrix IH generated from hash function H.
Output: Pair (a, b), where the following holds for a, b, and the matrix W = IH A:
1. The pair is either (a, b) = (−1, 0) or (a, b) = (i, ũW,i ). Here, ũW,i is a (1 ± ǫ)-approximation
to uW,i and the index i is the correct corresponding row.
2. If there is a key row i0 for the matrix W , then a = i0 .
Before describing the algorithm and proving its correctness, we prove the following useful lemma
in Appendix A.
Lemma 1. Let U = (u1 , . . . , un ) be a vector with non-negative entries of dimension n and let H ′
′
be a pairwise independent hash function where H ′ : [n] → {0, 1} and P [H ′ (i) = 1]
P= P′ [H (i) =
1
′
′
′
0] = P
i H (i)ui and
2 . Denote by H̄ the hash function defined by H̄ (i) = 1 − H (i). Let X =
1
-heavy element with respect to U , then:
Y = i H̄ ′ (i)ui . If there is no 16

 

1
1
1
Pr X ≤ · kU k1 ∪ Y ≤ · kU k1
≤ .
4
4
4
Theorem 3. If there exist two black box algorithms as specified in Black Box Algorithms 1 and 2,
then there exists an algorithm that satisfies the requirements in Definition 10 with high probability.
Proof. We will prove that Algorithm 1 fits the description of Definition 10. Using standard methods
such as in [10], we have a loop that runs in parallel O(log(n)) times so that we can find the index
of a heavy element and return it, if there is one. To prove this theorem, we consider the following
three exhaustive and disjoint cases regarding the matrix g[IH A] (recall that H : [n] → {0, 1}):
1. The matrix has a key row (note that a matrix always has at most one key row).
2. The matrix has no α-heavy row for α = 1 − 8ǫ .
3. The matrix has an α-heavy row for α = 1 − 8ǫ , but there is no key row.

8

Algorithm 1 Algorithm Find-Key-Row
The algorithm takes as input matrix A and hash function H : [n] → {0, 1}
for ℓ = 1 to N = O(log n) do
Generate a pairwise independent, uniform hash function Hℓ : [n] → {0, 1}
Let T1 = HAD(H, Hℓ ), T0 = HAD(H, H̄ℓ )
Let y1 = BA2(A, T1 ), y0 = BA2(A, T0 ) (BA2 is run with constant failure probability δ2 )
if y0 ≥ τ (n, ǫ) · y1 then
bℓ = 0
else if y1 ≥ τ (n, ǫ) · y0 then
bℓ = 1
else
bℓ = 2
if |{ℓ : bℓ = 2}| ≥ 23 n then
Return (−1, 0)
else
if there is a row i such that i satisfies |{ℓ : Hℓ (i) = bℓ }| ≥ 43 · N then
Return (i, BA1(A, H)) (BA1 is run with ǫ′ = 2ǫ and δ1 is set to be inverse polylogarithmic)
else
Return (−1, 0)
We prove that the algorithm is correct in each case in Lemmas 4, 5, and 6, respectively. These
proofs can be found in Appendix B.
With the proof of these three cases, we are done proving that Algorithm 1 performs correctly.
We now analyze the space bound for Algorithm 1.

Lemma 2. Algorithm 1 uses O SP ACE1(n, δ1 , 2ǫ ) + log(n)(log2 (n) + SP ACE2(n, δ2 )) bits of
memory, where δ1 is inverse polylogarithmic and δ2 is a constant.
Proof. Note that, in order for our algorithm to succeed, we run BA1 with an error parameter of
ǫ′ = 2ǫ and a failure probability parameter δ1 which is inverse polylogarithmic. Moreover, we run
BA2 with a constant failure probability. We also require a number of random bits bounded by
O(log2 (n)) for generating each hash function Hℓ , as well as the space required to run BA2 in each
iteration of the loop. Since there are O(log n) parallel iterations, this gives the lemma.

4.1

Algorithm for Finding All α-Heavy Rows

Algorithm 1 only guarantees that we return key rows. Given a matrix A, we now show that this
algorithm can be used as a subroutine to find all α-heavy rows i with respect to the matrix g[A]
with high probability, along with a (1 ± ǫ)-approximation to the row weights ug[A],i for all i. In
order to do this, we apply an additional hash function H : [n] → [τ ] which essentially maps rows
of the matrix to some number of buckets τ (i.e., each bucket corresponds to a set of sampled rows
based on H), and then run Algorithm 1 for each bucket. The intuition for why the algorithm works
is that any α-heavy row i in the original matrix A is likely to be a key row for the matrix in the
corresponding bucket to which row i is mapped.Note that, eventually, we find α-heavy rows for
2
and is given below.
α = logǫ 3 n . The algorithm sets τ = O ρ(n,ǫ)αlog(n)
2
9

Algorithm 2 Algorithm Find-Heavy-Rows
This algorithm takes as input a matrix A and a value 0 < α < 1.


Generate a pairwise independent hash function H : [n] → [τ ], where τ = O ρ(n,ǫ)αlog(n)
2
for k = 1 to τ do
Let Hk : [n] → {0, 1} be the function defined by Hk (i) = 1 ⇐⇒ H(i) = k
Let Ck = Find-Key-Row(A, Hk )
Return {Ck : Ck 6= (−1, 0)}
Theorem 4. Algorithm 2 outputs a set of pairs Q = {(i1 , a1 ), . . . , (it , at )} for t ≤ τ which satisfy
the following properties, except with probability log1 n :
1. ∀j ∈ [t] : (1 − ǫ)ug[A],ij ≤ aj ≤ (1 ± ǫ)ug[A],ij .
2. ∀i ∈ [n]: If row i is α-heavy with respect to the matrix g[A], then ∃j ∈ [t] such that ij = i
(for any 0 < α < 1).
Proof. First, the number of pairs output by Algorithm 2 is at most the number of buckets, which
equals τ . Now, the first property is true due to the fact that Algorithm 1 has a high success
probability. In particular, as long as the failure probability is at most τ ·log1c (n) for some constant c
(which we ensure), then by union bound the probability that there exists a pair (ij , aj ) ∈ Q such
that aj is not a (1 ± ǫ)-approximation to ug[A],ij is at most inverse polylogarithmic.
Now, to ensure the second item, we need to argue that every α-heavy row gets mapped to its
own bucket with high probability, since if there is a collision the algorithm cannot find all α-heavy
rows. Moreover, we must argue that for each α-heavy row i with respect to the matrix g[A], if i is
mapped to bucket k by H, then row i is actually a key row in the corresponding sampled matrix
g[Ak ] (for ease of notation, we write Ak to denote the matrix Hk Ak ). More formally, suppose row
i is α-heavy. Then the algorithm must guarantee with high probability that, if H(i) = k, then row
i is a key row in the matrix g[Ak ]. If we prove these two properties, then the theorem holds (since
Algorithm 1 outputs a key row with high probability, if there is one).
Observe that there must be at most α1 rows which are α-heavy. In particular, let R be the set
of α heavy rows, and assume towards a contradiction that |R| > α1 . Then we have:
kg[A]k1 ≥

X
i∈R

ug[A],i ≥

X

αkg[A]k1 = α · kg[A]k1 · |R| > kg[A]k1 ,

i∈R

which is a contradiction. Hence, we seek to upper bound the probability of a collision when throwing
1
1
α balls into τ bins. By a Birthday paradox argument, this happens with probability at most 2·τ ·α2 ,
which can be upper bounded as follows:
1
1
ǫ
α2
=
= 4
,
≤
2
2
2τ α
2α ρ(n, ǫ) log(n)
2ρ(n, ǫ) log(n)
2r (n) log(n)
which is inverse polylogarithmically small.
Now, we argue that every α-heavy row i for the matrix g[A] is mapped to a sampled matrix such
that i is a key row in the sampled matrix with high probability. In particular, suppose H(i) = k,
implying that row i is mapped to bucket k. For ℓ 6= i, let Xℓ be the indicator random variable
10

which is 1 if and only if row ℓ is mapped to the same bucket as i, namely H(ℓ) = k (i.e., Xℓ = 1
means the sampled matrix g[Ak ] contains row i and row ℓ). If row i is not a key row for the matrix
g[Ak ], this means that ug[Ak ],i ≤ ρ(n, ǫ)(kg[Ak ]k1 − ug[Ak ],i ). Observe that, if row i is mapped
to bucket k, then we have ug[Ak ],i = ug[A],i . Hence, the the probability that row i is not a key
row for the sampled matrix g[Ak ] (assuming row i is mapped to bucket k) can be expressed as
Pr[ug[A],i ≤ ρ(n, ǫ)(kg[Ak ]k1 − ug[A],i )|H(i) = k]. By pairwise independence of H, and by Markov’s
inequality, we can write:
h
i
Pr ug[A],i ≤ ρ(n, ǫ)(kg[Ak ]k1 − ug[A],i ) H(i) = k




X
X
= Pr ug[A],i ≤ ρ(n, ǫ)
ug[A],ℓXℓ H(i) = k = Pr ug[A],i ≤ ρ(n, ǫ)
ug[A],ℓ Xℓ 
ℓ6=i

ℓ6=i

hP
i


P
ρ(n,
ǫ)E
u
X
X
ℓ
g[A],ℓ
ρ(n, ǫ) ℓ6=i ug[A],ℓ
ug[A],i
ℓ6=i
≤
=
= Pr 
ug[A],ℓXℓ ≥
ρ(n, ǫ)
ug[A],i
τ · ug[A],i
ℓ6=i

≤

ρ(n, ǫ)kg[A]k1
α2 ρ(n, ǫ)
α
=
≤
.
ατ kg[A]k1
4α · ρ(n, ǫ) log(n)
4 log(n)

log(n)
Here, we choose τ = 4ρ(n,ǫ)
, and get that the probability that a particular α-heavy row i is
α2
α
. Since there are at most α1
not a key row in its corresponding sampled matrix is at most 4 log(n)
rows which are α-heavy, by union bound the probability that there exists an α-heavy row that is
1
.
not a key row in its sampled matrix is at most 4 log(n)
Thus, in all, the probability that at least one bad event happens (i.e., there exists a pair (ij , aj )
such that aj is not a good approximation to ug[A],ij , there is a collision between α-heavy rows, or
1
. This gives
an α-heavy row is not a key row in its corresponding sampled matrix) is at most log(n)
the theorem.

4.2

Sum from α-Heavy Rows

We now have an algorithm that is able to find all α-heavy rows for α =
1
log n .

ǫ2
,
log3 n

except with probability

In the language of [11], by Theorem 4, our α-heavy rows algorithm outputs an (α, ǫ)-cover
with respect to the vector (ug[A],1 , ug[A],2 , . . . , ug[A],n ) except with probability log1 n , where ǫ > 0 and
α > 0. Hence, we can apply the Recursive Sum algorithm from [11] (see Appendix C for the formal
definition of an (α, ǫ)-cover, along with the Recursive Sum algorithm) to get a (1±ǫ)-approximation
2
of kg[A]k1 . Note that the Recursive Sum algorithm needs α = logǫ 3 n and a failure probability of at
most

1
log n ,

which we provide. Hence, we get the following theorem.

Theorem 5. The Recursive Sum Algorithm, using Algorithm 2 as a subroutine, returns a (1 ± ǫ)approximation of kg[A]k1 .

4.3

Space Bounds

Lemma 3. Recursive Sum, using Algorithm 2 as a subroutine as described in Section 4.2, uses
the following amount of memory, where ǫ′ = 2ǫ , δ1 is inverse polylogarithmic, and δ2 is a small

11

constant:


1 4
1 4
1 4
10
8
′
9
O 5 r (n) log (n) + 5 r (n) log (n)SP ACE1(n, δ1 , ǫ ) + 5 r (n) log (n)SP ACE2(n, δ2 ) .
ǫ
ǫ
ǫ


ρ(n,ǫ) log(n)
,
Proof. The final algorithm uses the space bound from Lemma 2, multiplied by τ = O
α2
4

2

7
1 4
where α = φǫ 3 , φ = O(log n), and ρ(n, ǫ) = r (n)
ǫ . This gives τ = ǫ5 r (n) log (n) to account for
the splitting required to find α-heavy rows in Section 4.1. Finally, a multiplicative cost of log(n) is
needed for Recursive Sum, giving the final bound.

5

Applications

We now apply our algorithm to the problem of determining the L1 distance between joint and
product distributions as described in Problem 1.

Space Bounds for Determining L1 Independence


fij
m

fi fj
m



Given an n × n matrix A with entries aij = g
, we have provided a method to approxi−
mate:


n X
n
X
fi fj
fij
−
g
.
m
m
i=1 j=1

Let g be the L1 distance, namely g(x) = |x|. We now state explicitly which blackbox algorithms
we use:

• Let Black Box Algorithm 1 (BA1) be the (1 ± ǫ)-approximation of L1 for vectors from [14].
The space of this algorithm is upper bounded by the number of random bits required and
m
1 −2
uses O(log( nm
δǫ ) log( δǫ ) log( δ )ǫ ) bits of memory.
• Let Black Box Algorithm 2 (BA2) be the r(n)-approximation, using the L1 sketch of the
distance between joint and product distributions from [15]. This algorithm does not have
a precise polylogarithmic bound provided, but we compute that it is upper bounded by
the random bits required to generate the Cauchy random variables similarly to BA1. This
m
1 −2
algorithm requires O(log( nm
δǫ ) log( δǫ ) log( δ )ǫ ) bits of memory.
These two algorithms match the definitions given in Section 2, thus we are able to give a bound
of O( ǫ17 log14 (n) log2 ( nm
ǫ )) on the space our algorithm requires. We can improve this slightly as
follows.
Corollary 1. Due to the nature of the truncated Cauchy distribution (see [15]), we can further
improve our space bound to O ǫ17 log12 (n) log2 ( nm
ǫ ) .

Proof. Due to the constant lower bound on the approximation of L1 , instead of r21(n) ≤ kg[W ]k1 ≤
r 2 (n), we get C ≤ kg[W ]k1 ≤ log2 (n) for some constant C. As the space cost from dividing the
matrix into submatrices as shown in Section 4.1 directly depends on these bounds, we only pay an
O(r 2 (n)) multiplicativefactor instead of an O(r 4 (n)) multiplicative factor and achieve a bound of
O ǫ17 log12 (n) log2 ( nm
ǫ ) .
12

References
[1] Noga Alon, Alexandr Andoni, Tali Kaufman, Kevin Matulef, Ronitt Rubinfeld, and Ning
Xie. Testing k-wise and almost k-wise independence. In Proceedings of the 39th annual ACM
Symposium on Theory of Computing, 2007.
[2] Noga Alon, Oded Goldreich, and Yishay Mansour. Almost k-wise independence versus k-wise
independence. Information Processing Letters, 88(3):107–110, 2003.
[3] Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. In Proceedings of the 28th annual ACM Symposium on Theory of Computing,
1996.
[4] Tuğkan Batu, Eldar Fischer, Lance Fortnow, Ravi Kumar, Ronitt Rubinfeld, and Patrick
White. Testing random variables for independence and identity. In Proceedings of the 42nd
annual IEEE Symposium on Foundations of Computer Science, 2001.
[5] Tuğkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, and Patrick White. Testing
that distributions are close. In Proceedings of the 41st annual IEEE Symposium on Foundations
of Computer Science, 2000.
[6] Tuğkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, and Patrick White. Testing
closeness of discrete distributions. Journal of the ACM, 60(1):4, 2013.
[7] Tuğkan Batu, Ravi Kumar, and Ronitt Rubinfeld. Sublinear algorithms for testing monotone
and unimodal distributions. In Proceedings of the 36th annual ACM Symposium on Theory of
Computing, 2004.
[8] Vladimir Braverman, Kai-Min Chung, Zhenming Liu, Michael Mitzenmacher, and Rafail Ostrovsky. AMS Without 4-Wise Independence on Product Domains. In Proceedings of the 27th
International Symposium on Theoretical Aspects of Computer Science, 2010.
[9] Vladimir Braverman and Rafail Ostrovsky. Measuring independence of datasets. In Proceedings
of the 42nd annual ACM Symposium on Theory of Computing, 2010.
[10] Vladimir Braverman and Rafail Ostrovsky. Zero-one frequency laws. In Proceedings of the
42nd ACM Symposium on Theory of Computing, 2010.
[11] Vladimir Braverman and Rafail Ostrovsky. Generalizing the layering method of Indyk and
Woodruff: Recursive sketches for frequency-based vectors on streams. In International Workshop on Approximation Algorithms for Combinatorial Optimization Problems. Springer, 2013.
[12] Dominique Guillot, Apoorva Khare, and Bala Rajaratnam. Complete characterization of
hadamard powers preserving loewner positivity, monotonicity, and convexity. Journal of Mathematical Analysis and Applications, 425(1):489–507, 2015.
[13] Roger A. Horn and Charles R. Johnson. Topics in matrix analysis. Cambridge University
Presss, Cambridge, 1991.
[14] Piotr Indyk. Stable distributions, pseudorandom generators, embeddings, and data stream
computation. Journal of the ACM, 53(3):307–323, 2006.
13

[15] Piotr Indyk and Andrew McGregor. Declaring independence via the sketching of sketches. In
Proceedings of the 19th annual ACM-SIAM Symposium on Discrete Algorithms, 2008.
[16] Ralph Kimball and Joe Caserta. The data warehouse etl toolkit: Practical techniques for
extracting, cleaning, conforming, and delivering data. 2004.
[17] Erich L. Lehmann and Joseph P. Romano. Testing statistical hypotheses. Springer Science &
Business Media, 2006.
[18] Andrew McGregor and Hoa T. Vu. Evaluating bayesian networks via data streams. In Proceedings of the 21st International Computing and Combinatorics Conference, 2015.
[19] Viswanath Poosala and Yannis E. Ioannidis. Selectivity estimation without the attribute value
independence assumption. In Proceedings of the 23rd International Conference on Very Large
Data Bases, 1997.
[20] Ronitt Rubinfeld and Rocco A. Servedio. Testing monotone high-dimensional distributions.
In Proceedings of the 37th annual ACM Symposium on Theory of Computing, 2005.
[21] Amit Sahai and Salil Vadhan. A complete problem for statistical zero knowledge. Journal of
the ACM, 50(2):196–249, 2003.
[22] David P. Woodruff. Sketching as a tool for numerical linear algebra. CoRR, abs/1411.4357,
2014.

A

Proof of of Lemma 1

Proof. Note that we always have the equality
X+Y =
P
H ′ (i))ui = kU k1 , and moreover E[X] = i ui E[H ′ (i)] =

1
2

i

1
· kU k21
4
i
i6=j


1X 2 1X
1 X 2 X
1X 2
=
ui +
ui uj −
ui .
ui +
ui uj  =
2
4
4
4

V ar[X] = E[X 2 ] − (E[X])2 =

X

E[(H ′ (i))2 ]u2i +

1
16 -heavy

V ar[X] =

X

i6=j

i

Using the fact that there is no
for all i, we have:

P
H ′ (i)ui + H̄ ′ (i)ui = i H ′ (i)ui + (1 −
· kU k1 . Also, observe that

P

E[H ′ (i)H ′ (j)]ui uj −

i

i6=j

i

element with respect to U , which implies that ui ≤

1 X 2 kU k1 X
kU k21
ui ≤
ui =
.
4
64
64
i

i

Now we can apply Chebyshev’s inequality to obtain:

 



1
kU k1
1
= Pr |X − E[X]| ≥
Pr X ≤ · kU k1 ∪ Y ≤ · kU k1
4
4
4
16 · kU k21
1
16 · V ar[X]
≤
= .
≤
2
2
4
kU k1
64 · kU k1

14

1
16 ·kU k1

B

Proof of Correctness of Algorithm 1

Throughout the lemmas, we imagine that the hash function H : [n] → {0, 1} is fixed, and hence
the matrix g[IH A] is fixed. All randomness is taken over the pairwise independent hash functions
Hℓ that are generated in parallel, along with both blackbox algorithms.
To ease the notation, we define
W = IH A, W1 = IT1 A, and W0 = IT2 A
(recall the notation from Algorithm 1 that T1 = HAD(H, Hℓ ) and T0 = HAD(H, H̄ℓ )). Finally,
for each row i in the matrix g[W ], we define the shorthand notation ui = ug[W ],i .
Lemma 4. If the matrix g[IH A] has a key row, Algorithm 1 correctly returns the index of the row
and a (1 ± ǫ)-approximation of kg[IH A]k1 except with inverse polylogarithmic probability.
Proof. Suppose the matrix g[IH A] has a key row, and let i0 be the index of this row. We prove
that we return a good approximation of ug[W ],i0 with high probability. In particular, we first argue
that, for a fixed iteration ℓ of the loop, we have the property that bℓ equals Hℓ (i0 ), and moreover
this holds with certainty. We assume without loss of generality that Hℓ (i0 ) = 1 (the case when
Hℓ (i0 ) = 0 is symmetric). In particular, this implies that the key row i0 appears in the matrix g[W1 ].
By definition of BA2, the following holds for y1 = BA2(A, T1 ) and y0 = BA2(A, T0 ), except
with probability 2δ2 (where δ2 is the failure probability of BA2):
y1 ≥

kg[W1 ]k1
and y0 ≤ kg[W0 ]k1 r(n).
r(n)

We have the following set of inequalities:
kg[W1 ]k1 ≥ ui0 > ρ(n, ǫ)(kg[W ]k1 − ui0 ) ≥ ρ(n, ǫ)kg[W0 ]k1 ,
where the first inequality follows since g is non-negative and the key row i0 appears in the matrix
g[W1 ] (and hence the L1 -norm of g[W1 ] is at least ui0 since it includes the row i0 ), the second
inequality follows by definition of i0 being a key row for the matrix W , and the last inequality
follows since the entries in row i0 of the matrix W0 are all zero (as Hℓ (i0 ) = 1) and the remaining
rows of W0 are sampled from W , along with the facts that g is non-negative and g(0) = 0.
Substituting for ρ(n, ǫ), and using the fact that y1 and y0 are good approximations for kg[W1 ]k1
and kg[W0 ]k1 (respectively), except with probability 2δ2 , we get:
y1 ≥

r 3 (n)
r 2 (n)
kg[W1 ]k1
>
· kg[W0 ]k1 ≥
· y0 ≥ τ (n, ǫ) · y0 ,
r(n)
ǫ
ǫ

and thus in this iteration of the loop we have bℓ = 1 except with probability 2δ2 (in the case that
Hℓ (i0 ) = 0, it is easy to verify by a similar argument that y0 ≥ τ (n, ǫ) · y1 , and hence we have
bℓ = 0). Hence, for the row i0 , we have the property that bℓ = Hℓ (i0 ) for a fixed ℓ, except with
probability 2δ2 . By the Chernoff bound, as long as δ2 is a sufficiently small constant, we have
bℓ = Hℓ (i0 ) for at least a 34 -fraction of iterations ℓ, except with inverse polynomial probability.
The only issue to consider is the case that there exists another row i 6= i0 with the same property,
namely bℓ = Hℓ (i) for a large fraction of iterations ℓ. However, if bℓ = Hℓ (i), it must be that at
least one of y1 , y0 is a bad approximation or Hℓ (i) = Hℓ (i0 ), which happens with probability at
15

most 2δ2 + 12 . Therefore, by the Chernoff bound, the probability that this happens for at least a
3
1
4 -fraction of iterations ℓ is at most 2O(log n) , which is inverse polynomially small. By applying the
n−1
union bound, the probability that there exists such a row is at most 2O(log
n) , which is at most an
inverse polynomial. Hence, in this case, the algorithm returns (i0 , BA1(A, H)) except with inverse
polynomial probability.
We now argue that ũg[W ],io = BA1(A, H) is a (1 ± ǫ)-approximation of ug[W ],i0 , except with
inverse polylogarithmic probability.
By definition of BA1, which we run with an error parameter

of ǫ′ = 2ǫ , it returns a 1 ± 2ǫ -approximation of kg[JW ]k1 except with inverse polylogarithmic
probability, where W = IH A. Moreover, since i0 is a key row, we have:
ui0 > ρ(n, ǫ)(kg[W ]k1 − ui0 ) ⇒ ui0 >


ǫ
ρ(n, ǫ)kg[W ]k1
kg[W ]k1 ,
≥ 1−
1 + ρ(n, ǫ)
8

where the last inequality follows as long as r 4 (n) ≥ 8 − ǫ. This implies that i0 is 1 −
with respect to the matrix g[W ], and hence we can apply Theorem 2 to get that:


1 + 2ǫ
ǫ

kg[JW ]k1 ≥ ũg[W ],i0
u
≥
1
+
(1 ± ǫ)ui0 ≥
i
0
2
1 − 4ǫ


1 − 2ǫ
ǫ
 ui0 ≥ (1 − ǫ)ui0 ,
≥ 1−
kg[JW ]k1 ≥
2
1 + 4ǫ

ǫ
8



-heavy

where the first inequality holds for any 0 < ǫ ≤1, the second inequality holds by Theorem 2,
the third inequality holds since ũg[W ],i0 is a 1 ± 2ǫ -approximation of kg[JW ]k1 , and the rest hold
for similar reasons. Hence, our algorithm returns a good approximation as long as BA1 succeeds.
Noting that this happens except with inverse polylogarithmic probability gives the lemma.
Lemma 5. If the input matrix has no α-heavy row, where α = 1 − 8ǫ , then with high probability
Algorithm 1 correctly returns (−1, 0).
Proof. In this case, we have no α-heavy row for α = 1 − 8ǫ , which implies that ui ≤ αkg[W ]k1 =
1 − 8ǫ kg[W ]k1 for each row i in the matrix g[W ]. In this case, we show the probability that
Algorithm 1 returns a false positive is small. That is, with high probability, in each iteration ℓ
of the loop the algorithm sets bℓ = 2, and hence it returns (−1, 0). We split this case into three
additional disjoint and exhaustive subcases, defined as follows:
1. For each row i, we have ui ≤

1
16 kg[W ]k1 .

2. There exists a row i with ui >

1
16 kg[W ]k1

and ∀j 6= i we have uj ≤

ǫ
128 ui .

1
ǫ
3. There exist two distinct rows i, j where ui > 16
kg[W ]k1 and uj > 128
ui .
P
P
We define X = i hℓi ui and Y = i h̄ℓi ui , where hℓi = Hℓ (i) and h̄ℓi = H̄ℓ (i). Hence, we have
X = kg[W1 ]k1 and Y = kg[W0 ]k1 , and moreover X + Y = kg[W ]k1 (recall that g[W1 ] = g[IT1 A]
and g[W0 ] = g[IT0 A]).
1
-heavy row, we can apply Lemma 1 to the vector
In the first subcase, where there is no 16
(u1 , . . . , un ) to get that:
 


kg[W ]k1
1
kg[W ]k1
∪ Y ≤
≤ .
Pr X ≤
4
4
4

16

By definition of BA2, the following holds for y1 = BA2(A, T1 ) and y0 = BA2(A, T0 ) except
with probability 2δ2 , where δ2 is the success probability of BA2:
kg[W0 ]k1
≤ y0 ≤ r(n)kg[W0 ]k1 .
r(n)

kg[W1 ]k1
≤ y1 ≤ r(n)kg[W1 ]k1 ,
r(n)
Hence, except with probability

1
4

+ 2δ2 , we have the following constraints on y0 and y1 :

3
· kg[W ]k1 ≤ 3r(n)X ≤ 3y1 r 2 (n) ≤ τ (n, ǫ) · y1 , and
4
3
y1 ≤ r(n)X ≤ r(n) · · kg[W ]k1 ≤ 3r(n)Y ≤ 3y0 r 2 (n) ≤ τ (n, ǫ) · y0 ,
4
y0 ≤ r(n)Y ≤ r(n) ·

1
in which case we set bℓ = 2. If δ2 is some small constant, say δ2 ≤ 32
, then for a fixed iteration
5
ℓ, we set bℓ = 2 except with probability 16 . Now, applying the Chernoff bound, we can show that
the probability of having more than a 25 -fraction of iterations ℓ with bℓ 6= 2 is at most an inverse
polynomial. Hence, in this subcase the algorithm outputs (−1, 0), except with inverse polynomial
probability.
1
ǫ
In the second
subcase, we have ui > 16
kg[W ]k1 and, for all j 6= i, uj ≤ 128
ui . Then, since ui is

ǫ
not 1 − 8 -heavy with respect to g[W ], we have:

uj ≤

ǫ
1
· ui ≤ (kg[W ]k1 − ui ).
128
16

Hence, we can apply Lemma 1 to the vector U = (u1 , . . . , ui−1 , 0, ui+1 , . . . , un ) P
(since kU k1 =
1
kU k1 ). Letting X ′ = j6=i hℓj uj and
kg[W ]k1 − ui , and moreover each entry in U is at most 16
P
Y ′ = j6=i h̄ℓj uj , we get that:
Pr



1
X ≤ · kU k1
4
′





1
∪ Y ≤ · kU k1
4
′



1
≤ .
4

ǫ
kg[W ]k1 and Y ≥ Y ′ > 14 (kg[W ]k1 − ui ) ≥
This implies that X ≥ X ′ > 14 (kg[W ]k1 − ui ) ≥ 32
ǫ
32 kg[W ]k1 . Moreover, except with probability 2δ2 , y1 and y0 are good approximations to kg[W1 ]k1
and kg[W0 ]k1 , respectively. Thus, except with probability 41 + 2δ2 , we have:



ǫ 
y0 ≤ r(n)Y ≤ r(n) 1 −
kg[W ]k1 ≤ r(n) 1 −
32


ǫ 
kg[W ]k1 ≤ r(n) 1 −
y1 ≤ r(n)X ≤ r(n) 1 −
32

ǫ 
·
32
ǫ 
·
32

32
32r 2 (n)
·X ≤
· y1 ≤ τ (n, ǫ) · y1 , and
ǫ
ǫ
32
32r 2 (n)
·Y ≤
· y0 ≤ τ (n, ǫ) · y0 .
ǫ
ǫ

This implies that, except with probability 14 + 2δ2 , the algorithm sets bℓ = 2 for each iteration ℓ.
Applying the Chernoff bound again, we see that the probability of having more than a 52 -fraction
of iterations ℓ with bℓ 6= 2 is at most an inverse polynomial. Thus, in this subcase, the algorithm
outputs (−1, 0) except with inverse polynomial probability.
1
We now consider the last subcase, where ui > 16
kg[W ]k1 and there exists j 6= i such that
ǫ
uj > 128 ui . Note that the probability that i and j get mapped to different matrices is given by
Pr[Hℓ (i) 6= Hℓ (j)] = 12 . Assume without loss of generality that Hℓ (j) = 1 (the case that Hℓ (j) = 0
is symmetric). In the event that i and j get mapped to difference matrices and y1 , y0 are good
17

approximations to kg[W1 ]k1 , kg[W0 ]k1 respectively, which happens with probability at least 21 − 2δ2 ,
we have:
uj
X
ǫ
ǫ
1
ǫ
ǫ
≥
≥
· ui ≥
·
· kg[W ]k1 ≥
·Y ≥
· y0
r(n)
r(n)
128r(n)
128r(n) 16
2048r(n)
2048r 2 (n)
2048r 2 (n)
=⇒ y0 ≤
· y1 ≤ τ (n, ǫ) · y1
ǫ
ui
ǫ
ǫ
1
ǫ
ǫ
Y
≥
≥
· ui ≥
·
· kg[W ]k1 ≥
·X ≥
· y1
y0 ≥
r(n)
r(n)
128r(n)
128r(n) 16
2048r(n)
2048r 2 (n)
2048r 2 (n)
=⇒ y1 ≤
· y0 ≤ τ (n, ǫ) · y0 .
ǫ
y1 ≥

Thus, except with probability at least 12 − 2δ2 , the algorithm sets bℓ = 2 for each iteration ℓ. We
apply the Chernoff bound again to get that bℓ = 2 for at least a 52 -fraction of iterations, except
with inverse polynomial probability. Hence, the algorithm outputs (−1, 0) except with inverse
polynomial probability.
Lemma 6. If the matrix g[IH A] does not have a key row but has an α-heavy row i0 , where α = 1− 8ǫ ,
then Algorithm 1 either returns (−1, 0) or returns a (1 ± ǫ)-approximation of uIH A,i0 and the
corresponding row i0 with high probability.
Proof. We know there is an α-heavy row, but not a key row. Note that there cannot be more than
one α-heavy row for α = 1 − 8ǫ . If the algorithm returns (−1, 0), then the lemma holds (note the
algorithm is allowed to return (−1, 0) since there is no key row). If the algorithm returns a pair
of the form (i, BA1(A, H)), we know from Theorem 2 that the approximation of the weight of the
α-heavy row is a (1 ± ǫ)-approximation of kg[W ]k1 as long as BA1 succeeds, which happens except
with inverse polylogarithmic probability (the argument that the approximation is good follows
similarly as in Lemma 4). We need only argue that we return the correct index, i0 . Again, the
argument follows similarly as in Lemma 4. In particular, if Hℓ (i) = bℓ for a fixed iteration ℓ, then
at least one of y0 , y1 is a bad approximation or Hℓ (i0 ) = Hℓ (i), which happens with probability
at most 2δ2 + 12 (where δ2 is the failure probability of BA2). We then apply the Chernoff bound,
similarly as before.
With Lemmas 4, 5, and 6, we are done proving that Algorithm 1 fits the description of Definition 10, except with inverse polylogarithmic probability.

C

Recursive Sketches

Definition of a Cover:
Definition 11. A non-empty set Q ∈ P airst , i.e., Q = {(i1 , w1 ), . . . , (it , wt )} for some t ∈ [n], is
an (α, ǫ)-cover with respect to the vector V ∈ [M ]n if the following is true:
1. ∀j ∈ [t] (1 − ǫ)vij ≤ wj ≤ (1 ± ǫ)vij .
2. ∀i ∈ [n] if vi is α-heavy then ∃j ∈ [t] such that ij = i.

18

Definition 12. Let D be a probability distribution on P airs. Let V ∈ [m]n be a fixed vector. We
say that D is δ-good with respect to V if for a random element Q of Pairs with distribution D the
following is true:
P (Q is an (α, ǫ)-cover of V ) ≥ 1 − δ.
Using P
notation from [11], for a vector V = (v1 , . . . , vn ), we let |V | denote the L1 norm of V ,
|V | = ni=1 vi . Consider Algorithm 6 from [11]:
Algorithm 3 Recursive Sum (D, ǫ)

1. Generate φ = O(log(n)) pairwise independent zero-one vectors H1 , . . . , Hφ . Denote by Dj
the stream DH1 H2 ...Hφ
2

2. Compute, in parallel, Qj = HH(Dj , φǫ 3 , ǫ, φ1 )
3. If F0 (Vφ ) > 1010 then output 0 and stop. Otherwise, compute precisely Yφ = |Vφ |
4. For each j = φ − 1, . . . , 0, compute
Yj = 2Yj+1 −

X

(1 − 2hji )wQj (i)

i∈Ind(Qj )

5. Output Y0

Theorem 4.1 from [11]:
Theorem 6. Algorithm 3 computes a (1 ± ǫ)-approximation of |V | and errs with probability at
1
)) bits of memory, where µ is the space
most 0.3. The algorithm uses O(log(n)µ(n, ǫ2 log13 (n) , ǫ, log(n)
required by the above algorithm HH.

19

