SYNTOLOGY HomeExplorerAtlasCodeMethodologyAboutDevelopersFeedPricing
Paper · 2102.12293 · ICML · 2021

Two-way kernel matrix puncturing: towards resource-efficient PCA and spectral clustering

Romain Couillet, Florent Chatelain, Nicolas Le Bihan

arXiv · PDF · Open in the Atlas

Code that ran

We have not lifted any functions out of this paper's repositories yet, so there is nothing we have run. The repositories linked to it are listed below.

Repositories linked to this paper

Some links come from the archived Papers with Code dataset (CC BY-SA 4.0): attribution and licence.

Abstract

The article introduces an elementary cost and storage reduction method for spectral clustering and principal component analysis. The method consists in randomly "puncturing" both the data matrix X ∈ C p×n (or R p×n ) and its corresponding kernel (Gram) matrix K through Bernoulli masks: S ∈ {0, 1} p×n for X and B ∈ {0, 1} n×n for K. The resulting "two-way punctured" kernel is thus given by K = 1 p [(X S) H (X S)] B. We demonstrate that, for X composed of independent columns drawn from a Gaussian mixture model, as n, p → ∞ with p/n → c 0 ∈ (0, ∞), the spectral behavior of K -its limiting eigenvalue distribution, as well as its isolated eigenvalues and eigenvectors -is fully tractable and exhibits a series of counter-intuitive phenomena. We notably prove, and empirically confirm on various real image databases, that it is possible to drastically puncture the data, thereby providing possibly huge computational and storage gains, for a virtually constant (clustering or PCA) performance. This preliminary study opens as such the path towards rethinking, from a large dimensional standpoint, computational and storage costs in elementary machine learning models.

For agents

The same record, over MCP at https://syntology.ai/mcp:

get_harvested_code_for_paper("2102.12293")
get_code_for_paper("2102.12293")
have("2102.12293")

The run record, dated, one paper per request, free:

curl https://syntology.ai/api/ran/2102.12293.json

A badge for a README (the split and the date, never a ratio):

[![Syntology run record](https://syntology.ai/api/ran/2102.12293.svg)](https://syntology.ai/paper/2102.12293)

Connect an agent — have() is free.