Top

Foundations of Computational Mathematics

Published in:

31-01-2022

A Common Variable Minimax Theorem for Graphs

Authors: Ronald R. Coifman, Nicholas F. Marshall, Stefan Steinerberger

Published in: Foundations of Computational Mathematics | Issue 2/2023

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Let \({\mathcal {G}} = \{G_1 = (V, E_1), \ldots , G_m = (V, E_m)\}\) be a collection of m graphs defined on a common set of vertices V but with different edge sets \(E_1, \ldots , E_m\). Informally, a function \(f :V \rightarrow {\mathbb {R}}\) is smooth with respect to \(G_k = (V,E_k)\) if \(f(u) \sim f(v)\) whenever \((u, v) \in E_k\). We study the problem of understanding whether there exists a nonconstant function that is smooth with respect to all graphs in \({\mathcal {G}}\), simultaneously, and how to find it if it exists.

previous article The Average Condition Number of Most Tensor Rank Decomposition Problems is Infinite

next article Explicit Computation of a Galois Representation Attached to an Eigenform Over from the of a Surface

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

M. Belkin and P. Niyogi, Laplacian eigenmaps and spectral techniques for embedding and clustering, NIPS 14, pp. 585-591 (2002)

X. Cai, F. Nie, H. Huang, and F. Kamangar, Heterogeneous image feature integration via multi-modal spectral clustering, in Proc. Comput. Vis. Pattern Recognit., 2011.

R. Coifman, S. Lafon, Diffusion maps. Appl. Comput. Harmon. Anal. 21(1), p. 5–30 (2006)MathSciNetCrossRefMATH

R. Coifman, S. Lafon, Geometric harmonics: a novel tool for multiscale outof-sample extension of empirical functions. Appl. Comput. Harmon. Anal. 21(1), p. 31–52 (2006)MathSciNetCrossRefMATH

X. Dong, P. Frossard, P. Vandergheynst, N. Nefedov, N. Clustering on multi-layer graphs via subspace analysis on Grassmann manifolds. IEEE Transactions on signal processing, 62, p. 905–918, (2013).

J. Emme, P. Hubert, Limit laws for random matrix products, Mathematical Research Letters 25 (2018), p.1205 – 1212MathSciNetCrossRefMATH

D. Eynard, A. Kovnatsky, M. Bronstein, K. Glashoff, A. Bronstein, Multimodal manifold analysis by simultaneous diagonalization of laplacians. IEEE Transactions on Pattern Analysis and Machine Intelligence, 37, p. 2505–2517 (2015).CrossRef

J. Liu, C. Wang, J. Gao, and J. Han, Multi-view clustering via joint nonnegative matrix factorization, in Proc. SDM, 2013.

A. Kumar, P. Rai, and H. Daume III, Co-regularized multi-view spectral clustering, in Proc. Neural Inf. Process. Syst., 2011.

10.

R. R. Lederman, R. Talmon, Learning the geometry of common latent variables using alternating-diffusion. Appl. Comput. Harmon. Anal. 44(3), p. 509–536 (2018)MathSciNetCrossRefMATH

11.

C. Ma and C.-H. Lee, Unsupervised anchor shot detection using multi-modal spectral clustering, in Proc. ICASSP, 2008.

12.

W. Tang, Z. Lu, and I. Dhillon, Clustering with multiple graphs, in Proc. Data Mining, 2009.

13.

O. Yair, F. Dietrich, R. Mulayoff, R. Talmon, I. Kevrekidis, Spectral Discovery of Jointly Smooth Features for Multimodal Data, arXiv:2004.04386

14.

A. Yeredor, Non-orthogonal joint diagonalization in the leastsquares sense with application in blind source separation, Trans. Signal Proc., vol. 50, no. 7, pp. 1545-1553, 2002.CrossRefMATH

15.

Richard Sinkhorn and Paul Knopp, Concerning nonnegative matrices and doubly stochastic matrices, Pacific J. Math. 21 (1967), 343–348.MathSciNetCrossRefMATH

Title: A Common Variable Minimax Theorem for Graphs
Authors: Ronald R. Coifman
Nicholas F. Marshall
Stefan Steinerberger
Publication date: 31-01-2022
Publisher: Springer US
Published in: Foundations of Computational Mathematics / Issue 2/2023
Print ISSN: 1615-3375
Electronic ISSN: 1615-3383
DOI: https://doi.org/10.1007/s10208-022-09558-8

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 2/2023

Halting Time is Predictable for Large Models: A Universality Property and Average-Case Analysis

Explicit Computation of a Galois Representation Attached to an Eigenform Over from the of a Surface

Continuum Limit of Lipschitz Learning on Graphs

Affine-Invariant Ensemble Transform Methods for Logistic Regression

Finite Element Systems for Vector Bundles: Elasticity and Curvature

The Average Condition Number of Most Tensor Rank Decomposition Problems is Infinite

Premium Partner