  We consider the following oblivious sketching problem: given $\epsilon \in
(0,1/3)$ and $n \geq d/\epsilon^2$, design a distribution $\mathcal{D}$ over
$\mathbb{R}^{k \times nd}$ and a function $f: \mathbb{R}^k \times
\mathbb{R}^{nd} \rightarrow \mathbb{R}$, so that for any $n \times d$ matrix
$A$, $$\Pr_{S \sim \mathcal{D}} [(1-\epsilon) \|A\|_{op} \leq f(S(A),S) \leq
(1+\epsilon)\|A\|_{op}] \geq 2/3,$$ where $\|A\|_{op}$ is the operator norm of
$A$ and $S(A)$ denotes $S \cdot A$, interpreting $A$ as a vector in
$\mathbb{R}^{nd}$. We show a tight lower bound of $k = \Omega(d^2/\epsilon^2)$
for this problem. Our result considerably strengthens the result of Nelson and
Nguyen (ICALP, 2014), as it (1) applies only to estimating the operator norm,
which can be estimated given any OSE, and (2) applies to distributions over
general linear operators $S$ which treat $A$ as a vector and compute $S(A)$,
rather than the restricted class of linear operators corresponding to matrix
multiplication. Our technique also implies the first tight bounds for
approximating the Schatten $p$-norm for even integers $p$ via general linear
sketches, improving the previous lower bound from $k = \Omega(n^{2-6/p})$
[Regev, 2014] to $k = \Omega(n^{2-4/p})$. Importantly, for sketching the
operator norm up to a factor of $\alpha$, where $\alpha - 1 = \Omega(1)$, we
obtain a tight $k = \Omega(n^2/\alpha^4)$ bound, matching the upper bound of
Andoni and Nguyen (SODA, 2013), and improving the previous $k =
\Omega(n^2/\alpha^6)$ lower bound. Finally, we also obtain the first lower
bounds for approximating Ky Fan norms.
