  We present fast algorithms for sketching valuation functions. Let $N$
($|N|=n$) be some ground set and $v:2^N\rightarrow \mathbb R$ be a function. We
say that $\tilde v:2^N\rightarrow \mathbb R$ is an $\alpha$-sketch of $v$ if
for every set $S$ we have that $\frac {v(S)} {\alpha} \leq \tilde v(S) \leq
v(S)$ and $\tilde v$ can be described in $poly(n)$ bits.
  Goemans et al. [SODA'09] showed that if $v$ is submodular then there exists
an $\tilde O(\sqrt n)$-sketch that can be constructed using polynomially many
value queries (this is the best possible, as Balcan and Harvey [STOC'11] show
that no submodular function admit an $n^{\frac 1 3 - \epsilon}$-sketch). Based
on their work, Balcan et al. [COLT'12] and Badanidiyuru et al. [SODA'12] show
that if $v$ is subadditive then there exists an $\tilde O(\sqrt n)$-sketch that
can be constructed using polynomially many demand queries. All previous
sketches are based on complicated geometric constructions. The first step in
their constructions is proving the existence of a good sketch by finding an
ellipsoid that ``approximates'' $v$ well (this is done by applying John's
theorem to ensure the existence of an ellipsoid that is ``close'' to the
polymatroid that is associated with $v$). The second step is showing this
ellipsoid can be found efficiently, and this is done by repeatedly solving a
certain convex program to obtain better approximations of John's ellipsoid.
  In this paper, we give a much simpler, non-geometric proof for the existence
of good sketches, and utilize the proof to obtain much faster algorithms that
match the previously obtained approximation bounds. Specifically, we provide an
algorithm that finds $\tilde O(\sqrt n)$-sketch of a submodular function with
only $\tilde O(n^\frac{3}{2})$ value queries, and an algorithm that finds
$\tilde O(\sqrt n)$-sketch of a subadditive function with $O(n)$ demand and
value queries.
