# Efficiently approximating sum of 2-norms

Suppose I have a real vector $\bf x$ of length $KN$, where $K<<N$. Let's say I break this vector $\bf x$ up into $N$ vectors each of length $K$,

$${\bf x}_1,...{\bf x}_n.$$

Now I would like to approximate the sum of their 2-norms:

$$f(K, N, {\bf x})\approx \sum_{n=1}^N\left |\right |{\bf x}_n\left |\right |_2.$$

Where $f$ can be very efficiently computed (when compared to computing the sum of 2-norms). Is there a standard way to do this?

• Since computing norms maps very efficiently onto current hardware (pretty much by design), you'd be hard pressed to come up with a significantly better way than using standard functions and sub-indexing. You probably should add more background about what you're actually doing (is $N$ extraordinarily large (how large)? do you for some reason (which?) need to implement this yourself without using libraries? do you fear round-off error (why)?) – Christian Clason Aug 18 '16 at 22:25
• @ChristianClason, $N$ will probably around 5 orders of magnitude larger than $K$. Basically I just have to do this a relatively larger number of times so I was hoping I could avoid some of the cost. My assumption was that all those square root operations would be expensive. – Thoth Aug 18 '16 at 22:31
• Premature optimization is the root of all evil :) Implement everything using standard tools, make sure it works correctly, then profile the whole code. If it then in fact turns out that this step is the bottleneck (as in, the slowest step and also actually a problem), then you can worry about finding faster ways. (Also, you only need $K$ square roots, so it is very unlikely to be the most expensive part.) – Christian Clason Aug 19 '16 at 6:26
• @ChristianClason I need $N$ square roots, but otherwise you're right it's probably not likely to be a significant bottleneck. – Thoth Aug 19 '16 at 10:12
• Sorry, you're right, I misread. Anyway, there are hardware-level instructions for computing square roots, even vectorized (such as AVX's VSQRTSD), which you are unlikely to beat with even an approximate method implemented in a higher-level language. – Christian Clason Aug 19 '16 at 10:19

If you just want an approximation to the sum of their norms, you can choose a random sample of $m$ of the indices (i.e., a random set $S \subseteq \{1,2,\dots,N\}$ of size $m$) and compute

$$f(\textbf{x}) = \sum_{n \in S} \| x_n \|_2.$$

By a standard central limit theorem argument, $f(\textbf{x})$ will be a reasonable approximation to the sum of the norms; the larger that $m$ is, the better an approximation it will be. The time to compute $\tilde{f}(\textbf{x})$ might be significantly less than the time to compute the sum of the norms, depending on how $\mathbf{x}$ is stored and depending on the value of $m$.