We have seen a linear sketching estimate for $F_2$$F_2$F_(2)F_{2} estimation that uses $O(\log n)$$O(\log n)$O(log n)O(\log n) space. Indyk^[1] obtained a technically sophisticated and interesting sketch for $F_k$$F_k$F_(k)F_{k} estimation where $0<p\le 2$$0<p\le 2$0 < p <= 20<p \leq 2 (note that $p$$p$pp can be a real number) which uses polylog$(n)$$(n)$(n)(n) space. Since the details are rather technical we will only give the high-level approach and refer the reader to the paper and related notes for more details. Note that for $p>2$$p>2$p > 2p>2 there is a lower bound of $\mathrm{\Omega }\left(n^{1-2/p}\right)$$\mathrm{\Omega }\left(n^{1-2/p}\right)$Omega(n^(1-2//p))\Omega\left(n^{1-2 / p}\right) on the space required.

To describe the sketch for $0<p\le 2$$0<p\le 2$0 < p <= 20<p \leq 2 we will revisit the $F_2$$F_2$F_(2)F_{2} estimate via the JL Lemma approach that uses properties of the normal distribution.

Let $Z=\sum _{i\in [n]}{x}_i{Y}_i$$Z=\sum _{i\in [n]} x_i{Y}_i$Z=sum_(i in[n])x_(i)Y_(i)Z=\sum_{i \in[n]} x_{i} Y_{i} be the random variable that represents the value of $z$$z$zz at the end of the stream. The variable $Z$$Z$ZZ is a sum of independent normal variables and by the properties of the normal distribution $Z\sim \sqrt{\sum _i{x}_i^2}\cdot \mathcal{N}(0,1)$$Z\sim \sqrt{\sum _i x_i^2}\cdot \mathcal{N}(0,1)$Z∼sqrt(sum_(i)x_(i)^(2))*N(0,1)Z \sim \sqrt{\sum_{i} x_{i}^{2}} \cdot \mathcal{N}(0,1). Normal distribution is called 2-stable for this reason. More generally a distribution $\mathcal{D}$$\mathcal{D}$D\mathcal{D} is said to be $p$$p$pp-stable if the following property holds: Let $Z_1,Z_2,\dots ,Z_n$$Z_1,Z_2,\dots ,Z_n$Z_(1),Z_(2),dots,Z_(n)Z_{1}, Z_{2}, \ldots, Z_{n} be independent random variables distributed according to $\mathcal{D}$$\mathcal{D}$D\mathcal{D}. Then $\sum _i{x}_i{Z}_i$$\sum _i x_i{Z}_i$sum_(i)x_(i)Z_(i)\sum_{i} x_{i} Z_{i} has the same distribution as $\parallel x{\parallel }_{p}Z$$\parallel x{\parallel }_{p}Z$||x||_(p)Z\|x\|_{p} Z where $Z\sim \mathcal{D}$$Z\sim \mathcal{D}$Z∼DZ \sim \mathcal{D}. Note that a $p$$p$pp-stable distribution will be symmetric around $0$$0$00.

It is known that $p$$p$pp-stable distributions exist for all $p\in (0,2]$$p\in (0,2]$p in(0,2]p \in(0,2] and not for any $p>2$$p>2$p > 2p>2. The $p$$p$pp-stable distributions do not have, in general, an analytical formula except in some cases. We have already seen that the standard normal distribution is 2-stable. The 1-stable distribution is the Cauchy distribution which is the distribution of the ratio of two independent standard normal random variables. The density function of the Cauchy distribution is known to be $\frac{1}{\pi (1+x^2)}$$\frac{1}{\pi \left(1+x^2\right)}$(1)/(pi(1+x^(2)))\frac{1}{\pi\left(1+x^{2}\right)}; note that the Cauchy distribution does not have a finite mean or variance. We use ${\mathcal{D}}_p$${\mathcal{D}}_p$D_(p)\mathcal{D}_{p} to denote a $p$$p$pp-stable distribution.

Although a general $p$$p$pp-stable distribution does not have an analytical formula it is known that one can sample from ${\mathcal{D}}_p$${\mathcal{D}}_p$D_(p)\mathcal{D}_{p}. Chambers-Mallows-Stuck method is the following:

We need one more definition.

Definition 1 The median of a distribution $\mathcal{D}$$\mathcal{D}$D\mathcal{D} is $\theta$$\theta$theta\theta if for $Y\sim \mathcal{D},\mathrm{Pr}[Y\le \mu ]=1/2$$Y\sim \mathcal{D},\mathrm{Pr}[Y\le \mu ]=1/2$Y∼D,Pr[Y <= mu]=1//2Y \sim \mathcal{D}, \operatorname{Pr}[Y \leq \mu]=1 / 2. If $\varphi (x)$$\varphi (x)$phi(x)\phi(x) is the probability density function of $\mathcal{D}$$\mathcal{D}$D\mathcal{D} then we have ${\int }_{-\mathrm{\infty }}^{\mu }\varphi (x)dx=1/2$${\int }_{-\mathrm{\infty }}^{\mu } \varphi (x)dx=1/2$int_(-oo)^(mu)phi(x)dx=1//2\int_{-\infty}^{\mu} \phi(x) d x=1 / 2.

Note that a median may not be uniquely defined for a distribution. The distribution ${\mathcal{D}}_p$${\mathcal{D}}_p$D_(p)\mathcal{D}_{p} has a unique median and so we will use the terminology median $\left({\mathcal{D}}_p\right)$$\left({\mathcal{D}}_p\right)$(D_(p))\left(\mathcal{D}_{p}\right) to denote this quantity. For a distribution $\mathcal{D}$$\mathcal{D}$D\mathcal{D} we will refer to $|\mathcal{D}|$$|\mathcal{D}|$|D||\mathcal{D}| the distribution of the absolute value of a random variable drawn from $\mathcal{D}$$\mathcal{D}$D\mathcal{D}. If $\varphi (x)$$\varphi (x)$phi(x)\phi(x) is the density function of $\mathcal{D}$$\mathcal{D}$D\mathcal{D} then the density function of $|\mathcal{D}|$$|\mathcal{D}|$|D||\mathcal{D}| is given by $\psi$$\psi$psi\psi, where $\psi (x)=2\varphi (x)$$\psi (x)=2\varphi (x)$psi(x)=2phi(x)\psi(x)=2 \phi(x) if $x\ge 0$$x\ge 0$x >= 0x \geq 0 and $\psi (x)=0$$\psi (x)=0$psi(x)=0\psi(x)=0 if $x<0.$$x<0.$x < 0.x<0 .

By the $p$$p$pp-stability property we see that each $y_i\sim \parallel x{\parallel }_{p}Y$$y_i\sim \parallel x{\parallel }_{p}Y$y_(i)∼||x||_(p)Yy_{i} \sim\|x\|_{p} Y where $Y\sim {\mathcal{D}}_p$$Y\sim {\mathcal{D}}_p$Y∼D_(p)Y \sim \mathcal{D}_{p}. First, consider the case that $k=1$$k=1$k=1k=1. Then the output $\left|y_1\right|/$$\left|y_1\right|/$|y_(1)|//\left|y_{1}\right| / median $\left(\left|{\mathcal{D}}_p\right|\right)$$\left(\left|{\mathcal{D}}_p\right|\right)$(|D_(p)|)\left(\left|\mathcal{D}_{p}\right|\right) is distributed according to $c\left|{\mathcal{D}}_p\right|$$c\left|{\mathcal{D}}_p\right|$c|D_(p)|c\left|\mathcal{D}_{p}\right| where $c=\parallel x{\parallel }_p/$$c=\parallel x{\parallel }_p/$c=||x||_(p)//c=\|x\|_{p} /median$\left(\left|{\mathcal{D}}_p\right|\right)$$\left(\left|{\mathcal{D}}_p\right|\right)$(|D_(p)|)\left(\left|\mathcal{D}_{p}\right|\right). It is not hard to verify that the median of this distribution is $\parallel x{\parallel }_p$$\parallel x{\parallel }_p$||x||_(p)\|x\|_{p}. Thus, the algorithm take $k$$k$kk samples from this distribution and ouputs as the estimator the sample median. The lemma below shows that the sample median has good concentration properties.

Lemma 1 Let $ϵ>0$$ϵ>0$epsilon > 0\epsilon>0 and let $\mathcal{D}$$\mathcal{D}$D\mathcal{D} be a distribution with density function $\varphi$$\varphi$phi\phi and a unique median $\mu >0$$\mu >0$mu > 0\mu>0. Suppose $\varphi$$\varphi$phi\phi is absolutely continuous on $[(1-ϵ)\mu ,(1+ϵ)\mu ]$$[(1-ϵ)\mu ,(1+ϵ)\mu ]$[(1-epsilon)mu,(1+epsilon)mu][(1-\epsilon) \mu,(1+\epsilon) \mu] and let $\alpha =min\{\varphi (x)\mid xϵ$$\alpha =min\{\varphi (x)\mid xϵ$alpha=min{phi(x)∣x epsilon\alpha=\min \{\phi(x) \mid x \epsilon $[(1-ϵ)\mu ,(1+ϵ)\mu ]$$[(1-ϵ)\mu ,(1+ϵ)\mu ]$[(1-epsilon)mu,(1+epsilon)mu][(1-\epsilon) \mu,(1+\epsilon) \mu]. Let $Y=\mathrm{median}(Y_1,Y_2,\dots ,Y_k)$$Y=\mathrm{median}\left(Y_1,Y_2,\dots ,Y_k\right)$Y=median(Y_(1),Y_(2),dots,Y_(k))Y=\operatorname{median}\left(Y_{1}, Y_{2}, \ldots, Y_{k}\right) where $Y_1,\dots ,Y_k$$Y_1,\dots ,Y_k$Y_(1),dots,Y_(k)Y_{1}, \ldots, Y_{k} are independent samples from the distribution $\mathcal{D}$$\mathcal{D}$D\mathcal{D}. Then

We sketch the proof to upper bound $\mathrm{Pr}[Y\le (1-ϵ)\mu ]$$\mathrm{Pr}[Y\le (1-ϵ)\mu ]$Pr[Y <= (1-epsilon)mu]\operatorname{Pr}[Y \leq(1-\epsilon) \mu]. The other direction is similar. Note that by the definition of the median, $\mathrm{Pr}[Y_j\le \mu ]=1/2$$\mathrm{Pr}\left[Y_j\le \mu \right]=1/2$Pr[Y_(j) <= mu]=1//2\operatorname{Pr}\left[Y_{j} \leq \mu\right]=1 / 2. Hence

Let $\gamma ={\int }_{(1-ϵ)\mu }^{\mu }\varphi (x)dx$$\gamma ={\int }_{(1-ϵ)\mu }^{\mu } \varphi (x)dx$gamma=int_((1-epsilon)mu)^(mu)phi(x)dx\gamma=\int_{(1-\epsilon) \mu}^{\mu} \phi(x) d x. It is easy to see that $\gamma \ge \alpha ϵ\mu$$\gamma \ge \alpha ϵ\mu$gamma >= alpha epsilon mu\gamma \geq \alpha \epsilon \mu.

Let $I_j$$I_j$I_(j)I_{j} be the indicator event for $Y_i\le (1-ϵ)\mu$$Y_i\le (1-ϵ)\mu$Y_(i) <= (1-epsilon)muY_{i} \leq(1-\epsilon) \mu; we have $\mathbf{E}\left[I_j\right]=\mathrm{Pr}[Y_i\le (1-ϵ)\mu ]\le 1/2-\gamma$$\mathbf{E}\left[I_j\right]=\mathrm{Pr}\left[Y_i\le (1-ϵ)\mu \right]\le 1/2-\gamma$E[I_(j)]=Pr[Y_(i) <= (1-epsilon)mu] <= 1//2-gamma\mathbf{E}\left[I_{j}\right]=\operatorname{Pr}\left[Y_{i} \leq(1-\epsilon) \mu\right] \leq 1 / 2-\gamma. Let $I=\sum _j{I}_j$$I=\sum _j I_j$I=sum_(j)I_(j)I=\sum_{j} I_{j}; we have $\mathbf{E}[I]=k(1/2-\gamma )$$\mathbf{E}[I]=k(1/2-\gamma )$E[I]=k(1//2-gamma)\mathbf{E}[I]=k(1 / 2-\gamma). Since $Y$$Y$YY is the median of $Y_1,Y_2,\dots ,Y_k,Y\le (1-ϵ)\mu$$Y_1,Y_2,\dots ,Y_k,Y\le (1-ϵ)\mu$Y_(1),Y_(2),dots,Y_(k),Y <= (1-epsilon)muY_{1}, Y_{2}, \ldots, Y_{k}, Y \leq(1-\epsilon) \mu only if more than $k/2$$k/2$k//2k / 2 of $I_j$$I_j$I_(j)I_{j} are true which is the same as $\mathrm{Pr}[I>(1+\delta )\mathbf{E}[I]]$$\mathrm{Pr}[I>(1+\delta )\mathbf{E}[I]]$Pr[I > (1+delta)E[I]]\operatorname{Pr}[I>(1+\delta) \mathbf{E}[I]] where $1+\delta =\frac{1}{1-2\gamma }$$1+\delta =\frac{1}{1-2\gamma }$1+delta=(1)/(1-2gamma)1+\delta=\frac{1}{1-2 \gamma}. Now, via Chernoff bounds, this probability is at most $e^{-{\gamma }^{2}k/3}$$e^{-{\gamma }^{2}k/3}$e^(-gamma^(2)k//3)e^{-\gamma^{2} k / 3} for sufficiently small $\gamma$$\gamma$gamma\gamma.

We can now apply the lemma to the estimator output by the algorithm. We let $\varphi$$\varphi$phi\phi be the distribution of $c\left|{\mathcal{D}}_p\right|$$c\left|{\mathcal{D}}_p\right|$c|D_(p)|c\left|\mathcal{D}_{p}\right|. Recall that the median of this distribution if $\parallel x{\parallel }_p$$\parallel x{\parallel }_p$||x||_(p)\|x\|_{p} and the output of the algorithm is the median of $k$$k$kk indepenent samples from this distribution. Thus, from the lemma,

Let ${\varphi }^{\mathrm{\prime }}$${\varphi }^{\mathrm{\prime }}$phi^(')\phi^{\prime} be the distribution of $|{\mathcal{D}}_{\surd }|$$|{\mathcal{D}}_{\surd }|$|D_(√)||\mathcal{D}_{\surd}| and ${\mu }^{\mathrm{\prime }}$${\mu }^{\mathrm{\prime }}$mu^(')\mu^{\prime} be the median of ${\varphi }^{\mathrm{\prime }}$${\varphi }^{\mathrm{\prime }}$phi^(')\phi^{\prime}. Then it can be seen that $\mu \alpha ={\mu }^{\mathrm{\prime }}{\alpha }^{\mathrm{\prime }}$$\mu \alpha ={\mu }^{\mathrm{\prime }}{\alpha }^{\mathrm{\prime }}$mu alpha=mu^(')alpha^(')\mu \alpha=\mu^{\prime} \alpha^{\prime} where ${\alpha }^{\mathrm{\prime }}=min\{{\varphi }^{\mathrm{\prime }}(x)\mid (1-ϵ){\mu }^{\mathrm{\prime }}\le (1+ϵ){\mu }^{\mathrm{\prime }}\}$${\alpha }^{\mathrm{\prime }}=min\left\{{\varphi }^{\mathrm{\prime }}(x)\mid (1-ϵ){\mu }^{\mathrm{\prime }}\le (1+ϵ){\mu }^{\mathrm{\prime }}\right\}$alpha^(')=min{phi^(')(x)∣(1-epsilon)mu^(') <= (1+epsilon)mu^(')}\alpha^{\prime}=\min \left\{\phi^{\prime}(x) \mid(1-\epsilon) \mu^{\prime} \leq(1+\epsilon) \mu^{\prime}\right\}. Thus ${\mu }^{\mathrm{\prime }}{\alpha }^{\mathrm{\prime }}$${\mu }^{\mathrm{\prime }}{\alpha }^{\mathrm{\prime }}$mu^(')alpha^(')\mu^{\prime} \alpha^{\prime} depends only on ${\mathcal{D}}_p$${\mathcal{D}}_p$D_(p)\mathcal{D}_{p} and $ϵ$$ϵ$epsilon\epsilon. Letting this be $c_{p,ϵ}$$c_{p,ϵ}$c_(p,epsilon)c_{p, \epsilon} we have,

provided $k=\mathrm{\Omega }(c_{p,ϵ}\cdot \frac{1}{{ϵ}^2}\log \frac{1}{\delta })$$k=\mathrm{\Omega }(c_{p,ϵ}\cdot \frac{1}{{ϵ}^2}\log \frac{1}{\delta })$k=Omega(c_(p,epsilon)*(1)/(epsilon^(2))log (1)/(delta))k=\Omega(c_{p, \epsilon} \cdot \frac{1}{\epsilon^{2}} \log \frac{1}{\delta}).

Technical Issues: There are several technical issues that need to be addressed to obtain a proper algorithm from the preceding description. First, the algorithm as described requires one to store the entire matrix $M$$M$MM which is too large for streaming applications. Second, the constant $k$$k$kk depends on $c_{p,ϵ}$$c_{p,ϵ}$c_(p,epsilon)c_{p, \epsilon} which is not explicitly known since ${\mathcal{D}}_p$${\mathcal{D}}_p$D_(p)\mathcal{D}_{p} is not well-understood for general $p$$p$pp. To obtain a streaming algorithm, the very high-level idea is to derandomize the algorithm via the use of pseudorandom generators for small-space due to Nisan. See^[1:1] for more details.

We have seen various algorithm for estimating various $F_p$$F_p$F_(p)F_{p} norms for $p\ge 0$$p\ge 0$p >= 0p \geq 0. Note that $F_0$$F_0$F_(0)F_{0} corresponds to number of distinct elements. In the limit, as $p\to \mathrm{\infty },{\ell }_p$$p\to \mathrm{\infty },{\ell }_p$p rarr oo,ℓ_(p)p \rightarrow \infty, \ell_{p} norm of a vector $\mathbf{x}$$\mathbf{x}$x\mathbf{x} is the maximum of the absolute values of the entries of $\mathbf{x}$$\mathbf{x}$x\mathbf{x}. Thus, we can define the $F_{\mathrm{\infty }}$$F_{\mathrm{\infty }}$F_(oo)F_{\infty} norm to corresponds to finding the maximum frequency in $\mathbf{x}$$\mathbf{x}$x\mathbf{x}. More generally, we would like to find the frequent items in a stream which are also called "heavy hitters". In general, it is not feasible to estimate the heaviest frequency with limited space if it is too small relative to $m$$m$mm.

Suppose we have a stream $\sigma =a_1,a_2,\dots ,a_m$$\sigma =a_1,a_2,\dots ,a_m$sigma=a_(1),a_(2),dots,a_(m)\sigma=a_{1}, a_{2}, \ldots, a_{m} where $a_j\in [n]$$a_j\in [n]$a_(j)in[n]a_{j} \in[n], the simple setting and we want to find all elements in $[n]$$[n]$[n][n] such that $f_i>m/k$$f_i>m/k$f_(i) > m//kf_{i}>m / k. Note that there can be at most $k$$k$kk such elements. The simplest case is when $k=2$$k=2$k=2k=2 when we want to know whether there is a "majority" element. There is a simple deterministic algorithm that perhaps you have all seen for $k=2$$k=2$k=2k=2 in an algorithm class. The algorithm uses an associative array data structure of size $k$$k$kk.

We leave the following as an exercise to the reader.

Lemma 2 For each $i\in [n]$$i\in [n]$i in[n]i \in[n]:

The lemma implies that if $f_i>m/k$$f_i>m/k$f_(i) > m//kf_{i}>m / k then $i\in \mathit{\text{keys}}(D)$$i\in \mathit{\text{keys}}(D)$i in"keys"(D)i \in \textit{keys}(D) at the end of the algorithm. Thus one can use a second-pass over the data to compute the exact $f_i$$f_i$f_(i)f_{i} only for the $k$$k$kk itmes in $\mathit{\text{keys}}(D)$$\mathit{\text{keys}}(D)$"keys"(D)\textit{keys}(D). This gives an $O(kn)$$O(kn)$O(kn)O(k n) time two-pass algorithm for finding all items which have frequency at least $m/k$$m/k$m//km / k.

Bibliographic Notes: For more details on $F_p$$F_p$F_(p)F_{p} estimation when $0<p\le 2$$0<p\le 2$0 < p <= 20<p \leq 2 see the original paper of Indyk^[1:2], notes of Amit Chakrabarti (Chapter 7) and Lecture 4 of Jelani Nelson's course.