Why are random Fourier features efficient? I am trying to understand Random Features for Large-Scale Kernel Machines. In particular, I don't follow the following logic: kernel methods can be viewed as optimizing the coefficients in a weighted sum,
$$
f(\mathbf{x}, \boldsymbol{\alpha}) = \sum_{n=1}^{N} \alpha_n k(\mathbf{x}, \mathbf{x}_n) \tag{1}
$$
Let $\mathbf{x} \in \mathbb{R}^D$ and let $K < D$. Rahimi and Recht propose a map $\mathbf{z}: \mathbb{R}^D \mapsto \mathbb{R}^K$ such that
\begin{align}
\mathbf{w}_j &\sim \mathcal{N}(\mathbf{0}, \mathbf{I})
\\
\hat{k}(\mathbf{x}, \mathbf{y}) &= \sum_{j=1}^{J} \mathbf{z}(\mathbf{x}; \mathbf{w}_j)^{\top} \mathbf{z}(\mathbf{y}; \mathbf{w}_j).
\end{align}
Cool so far. Here's what I don't undertstand. Rahimi then claims here that if we plug in $\hat{k}$ into Equation $1$, we get an approximation,
$$
\hat{f}(\mathbf{x}, \boldsymbol{\alpha}) = \sum_{j=1}^J \beta_j \mathbf{z}(\mathbf{x}; \mathbf{w}_j).
$$
Question: I don't see how we get to eliminate the sum over $N$. I would have expected:
$$
\hat{f}(\mathbf{x}, \boldsymbol{\alpha}) = \sum_{n=1}^{N} \alpha_n \sum_{j=1}^{J} \mathbf{z}(\mathbf{x}; \mathbf{w}_j)^{\top} \mathbf{z}(\mathbf{x}_n; \mathbf{w}_j).
$$
I could possibly rearrange the sums, but I still don't see how we can eliminate the sum over $N$,
$$
\hat{f}(\mathbf{x}, \boldsymbol{\alpha}) = \sum_{j=1}^{J} \mathbf{z}(\mathbf{x}; \mathbf{w}_j)^{\top} \underbrace{\sum_{n=1}^{N} \alpha_n \mathbf{z}(\mathbf{x}_n; \mathbf{w}_j)}_{\beta_j??}.
$$
What am I missing?
 A: So this kind of looks like a case of notational abuse to me. 
Quick Review of Dual Formulation of SVMs and Kernel Trick
For standard, basic vanilla support vector machines, we deal only with binary classification. As is typical, our two class labels will be encoded by the set $\mathcal{Y} = \{+1, -1\}$. I'll also use the notation $[m] = \{1, 2, \dots, m\}$. Our training data set is a sample of size $m$ of the form $S = \{(\mathbf{x}_{i}, y_{i}) \ |\ i \in [m], \  \mathbf{x}_{i} \in \mathbb{R}^{D},\ y_{i} \in \mathcal{Y} \} $.
After reformulating the problem in Lagrange dual form,  enforcing the KKT conditions, and simplifying with some algebra, the optimization problem can be written succinctly as:
$$\max_{\alpha} \sum_{i = 1}^{m}\alpha_{i} - \frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m} \alpha_{i}\alpha_{j}y_{i}y_{j}(\mathbf{x}_{i}\cdot\mathbf{x}_{j}) \tag{1}\\
\text{subject to}:\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\\  \alpha_{i} \geq 0\ \ \forall i\in [m]\\ \sum_{i=1}^{m}\alpha_{i}y_{i}=0$$
The support vectors are the sample points $\mathbf{x}_{i}\in\mathbb{R}^{D}$ where $\alpha_{i} \neq 0$. All the other points not on the marginal hyperplanes have $\alpha_{i} = 0$.
The Kernel trick comes from replacing the standard Euclidean inner product in the objective function $(1)$ with a inner product in a projection space representable by a kernel function: 
$$k(\mathbf{x}, \mathbf{y}) = \phi(\mathbf{x}) \cdot \phi(\mathbf{y})\\ \text{where}\ \  \phi(\mathbf{x}) \in \mathbb{R}^{D_{1}}$$
This generalization let's us deal with nonlinearly separable situations since if we take $D_{1} > D$, we can find a linear separator in this higher-dimensional $D_{1}$ space corresponding to a nonlinear separator in our original $D$⁠-dimensional space.
Correcting Notational Abuse
Let's look at these inner products a little more closely. The Euclidean inner product is the familiar sum:
$$\mathbf{x}_{i}\cdot\mathbf{x}_{j} = \sum_{t=1}^{D}x_{i,t}x_{j,t} $$
So we see that the objective function $(1)$ really has this $D$ term sum nested inside the double sum. If I write $\phi(\mathbf{x}) = \large{(} \normalsize{\phi_{1}(\mathbf{x}), \phi_{2}(\mathbf{x}), \dots, \phi_{D_{1}}(\mathbf{x})}  \large{)} $, then the kernel inner-product similarly looks like:
$$\phi(\mathbf{x}_{i})\cdot\phi(\mathbf{x}_{j}) = \sum_{t=1}^{D_{1}}\phi_{t}(\mathbf{x}_{i})\phi_{t}(\mathbf{x}_{j}) \tag{2} $$
So from $(2)$ we are reminded that projecting into this higher-dimensional space means that there are more terms in the inner product. The 'trick' in the kernel trick is that appropriately chosen projections $\phi$ and spaces $\mathbb{R}^{D_{1}}$ let us sidestep this more computationally intensive inner product because we can just use the kernel function $k$ on the points in the original space $\mathbb{R}^{D}$ (for example, as long as the kernel satisfies Mercer's condition). 
Ok, everything up to this point has pretty much been reviewing standard material. What Rahimi's random features method does is instead of using a kernel which is equivalent to projecting to a higher  $D_{1}$⁠-⁠dimensional space, we project into a lower $K$-dimensional space using the fixed projection functions $\mathbf{z}$ with random weights $\mathbf{w}_{j}$. So rather than having a single projection $\phi(\mathbf{x})$ for each point $\mathbf{x}$, we instead have a randomized collection $\mathbf{z}(\mathbf{x}, \mathbf{w_{j}})$ for $j \in [J]$. In terms of the component notation, earlier we had:
$$\phi(\mathbf{x}) = \large{(}\normalsize \phi_{1}(\mathbf{x}), \dots, \phi_{D_{1}}(\mathbf{x} ) \large{)} \tag{3}, $$
whereas now we have:
$$
\mathbf{z}(\mathbf{x}, \mathbf{w}_{1}) = \large{(}\normalsize z_{1}(\mathbf{x}, \mathbf{w}_{1}), \dots, z_{K}(\mathbf{x}, \mathbf{w}_{1})\large{)}
\\ \vdots \tag{4}\\ 
\mathbf{z}(\mathbf{x}, \mathbf{w}_{J}) = \large{(}\normalsize z_{1}(\mathbf{x}, \mathbf{w}_{J}), \dots, z_{K}(\mathbf{x}, \mathbf{w}_{J})\large{)}$$
As they allude to in one of the three papers Rahimi places in this trilogy, I forget which one, the components of projection functions of $(4)$ can now be viewed as $J$-dimensional vector valued instead of scalar valued in $(3)$. So now you're replacing your $D_{1}$-dimensional projection with $J$ individual $K$-dimensional projections, and substituted your $D_{1}$ term sum with a $JK$ term sum in each inner product.
So now your inner product is in fact a double sum, over both the $J$ components of each projection and the $K$ dimensions of the space:
$$
\hat{k}(\mathbf{x}, \mathbf{y}) = \sum_{t=1}^{K} \sum_{j=1}^{J} \beta_{j}z_{t}(\mathbf{x})z_{t}(\mathbf{y}) \tag{5}
 $$
Contrast this with the single sum representing the kernel equivalent inner product in $(2)$.
Hopefully tracking each index separately clarified things for you. As for why this is 'efficient,' since the $K$-dimensional projection is lower-dimensional, that's less computational overhead than figuring out the typical higher $D_{1}$ dimensional projection. Also, since you're randomly generating $J$ of these projections, assuming your random generation is computationally cheap, you get an effective ensemble of support vectors pretty easily.
