  Kernel principal component analysis (KPCA) provides a concise set of basis
vectors which capture non-linear structures within large data sets, and is a
central tool in data analysis and learning. To allow for non-linear relations,
typically a full $n \times n$ kernel matrix is constructed over $n$ data
points, but this requires too much space and time for large values of $n$.
Techniques such as the Nystr\"om method and random feature maps can help
towards this goal, but they do not explicitly maintain the basis vectors in a
stream and take more space than desired. We propose a new approach for
streaming KPCA which maintains a small set of basis elements in a stream,
requiring space only logarithmic in $n$, and also improves the dependence on
the error parameter. Our technique combines together random feature maps with
recent advances in matrix sketching, it has guaranteed spectral norm error
bounds with respect to the original kernel matrix, and it compares favorably in
practice to state-of-the-art approaches.
