Data-Driven Linear Complexity Low-Rank Approximation of General Kernel Matrices: A Geometric Approach Article Swipe

MAKE IMPACT

Difeng Cai , Edmond Chow , Yuanzhe Xi · YOU? · · 2022 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2212.12674

A general, {\em rectangular} kernel matrix may be defined as $K_{ij} = κ(x_i,y_j)$ where $κ(x,y)$ is a kernel function and where $X=\{x_i\}_{i=1}^m$ and $Y=\{y_i\}_{i=1}^n$ are two sets of points. In this paper, we seek a low-rank approximation to a kernel matrix where the sets of points $X$ and $Y$ are large and are arbitrarily distributed, such as away from each other, ``intermingled'', identical, etc. Such rectangular kernel matrices may arise, for example, in Gaussian process regression where $X$ corresponds to the training data and $Y$ corresponds to the test data. In this case, the points are often high-dimensional. Since the point sets are large, we must exploit the fact that the matrix arises from a kernel function, and avoid forming the matrix, and thus ruling out most algebraic techniques. In particular, we seek methods that can scale linearly or nearly linear with respect to the size of data for a fixed approximation rank. The main idea in this paper is to {\em geometrically} select appropriate subsets of points to construct a low rank approximation. An analysis in this paper guides how this selection should be performed.

Type

preprint

Language

en

Landing Page

http://arxiv.org/abs/2212.12674

PDF

https://arxiv.org/pdf/2212.12674

OA Status

green

Related Works

10

OpenAlex ID

https://openalex.org/W4312225824

Raw OpenAlex JSON

OpenAlex ID

https://openalex.org/W4312225824

Canonical identifier for this work in OpenAlex

DOI

https://doi.org/10.48550/arxiv.2212.12674

Digital Object Identifier

Title

Data-Driven Linear Complexity Low-Rank Approximation of General Kernel Matrices: A Geometric Approach

Work title

Type

preprint

OpenAlex work type

Language

en

Primary language

Publication year

2022

Year of publication

Publication date

2022-12-24

Full publication date if available

Authors

Difeng Cai, Edmond Chow, Yuanzhe Xi

List of authors in order

Landing page

https://arxiv.org/abs/2212.12674

Publisher landing page

PDF URL

https://arxiv.org/pdf/2212.12674

Direct link to full text PDF

Open access

Yes

Whether a free full text is available

OA status

green

Open access status per OpenAlex

OA URL

https://arxiv.org/pdf/2212.12674

Direct OA link when available

Concepts

Kernel (algebra), Mathematics, Combinatorics, Rank (graph theory), Matrix (chemical analysis), Kernel method, Gaussian function, Data point, Gaussian, Algorithm, Computer science, Physics, Artificial intelligence, Materials science, Composite material, Quantum mechanics, Support vector machine

Top concepts (fields/topics) attached by OpenAlex

Cited by

0

Total citation count in OpenAlex

Related works (count)

10

Other works algorithmically related by OpenAlex

Full payload