  Approaches to signal representation and coding theory have traditionally
focused on how to best represent signals using parsimonious representations
that incur the lowest possible distortion. Classical examples include linear
and non-linear approximations, sparse representations, and rate-distortion
theory. Very often, however, the goal of processing is to extract specific
information from the signal, and the distortion should be measured on the
extracted information. The corresponding representation should, therefore,
represent that information as parsimoniously as possible, without necessarily
accurately representing the signal itself.
  In this paper, we examine the problem of encoding signals such that
sufficient information is preserved about their pairwise distances and their
inner products. For that goal, we consider randomized embeddings as an encoding
mechanism and provide a framework to analyze their performance. We also
demonstrate that it is possible to design the embedding such that it represents
different ranges of distances with different precision. These embeddings also
allow the computation of kernel inner products with control on their inner
product-preserving properties. Our results provide a broad framework to design
and analyze embeddins, and generalize existing results in this area, such as
random Fourier kernels and universal embeddings.
