Representation and Coding of Signal Geometry
This work addresses the need for efficient signal representation in applications where geometric relationships are more important than accurate signal reconstruction, offering a generalized framework that builds on existing methods like random Fourier kernels.
The paper tackles the problem of encoding signals to preserve pairwise distances and inner products, rather than minimizing signal distortion, by proposing a framework for designing and analyzing randomized embeddings that allow different precision for different distance ranges and enable controlled kernel inner product computations.
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.