Metric Transforms and Low Rank Matrices via Representation Theory of the Real Hyperrectangle

Understand

In this paper, we develop a new technique which we call representation theory of the real hyperrectangle, which describes how to compute the eigenvectors and eigenvalues of certain matrices arising from hyperrectangles.

• We show that these matrices arise naturally when analyzing a number of different algorithmic tasks such as kernel methods, neural network training, natural language processing, and the design of algorithms using the polynomial method.
• We then use our new technique along with these connections to prove several new structural results in these areas, including: $\bullet$ A function is a positive definite Manhattan kernel if and only if it is a completely monotone function.
• These kernels are widely used across machine learning; one example is the Laplace kernel which is widely used in machine learning for chemistry.