BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Stefan Steinerberger

Stefan Steinerberger appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.CAmath.APmath.COmath.SPMachine Learningmath.NADiscrete Mathematicsmath.FAmath.MGmath.OCmath-phmath.MPmath.NTmath.PRmath.CVNumerical AnalysisComputational Geometrymath.DGmath.DScond-mat.dis-nnData Structures and Algorithmsecon.EMecon.THmath.HOmath.STnlin.CDphysics.data-anStatistics Theory

Catalog footprint

What is connected

71works
28topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

71 published item(s)

preprint2024arXiv

Nonlinear recursions on the reals and a problem of Graham

We study sequences $(x_n)_{n=1}^{\infty}$ of reals given by $x_{n+1} = f(x)$ where $$f(x) = x - \sum_{i=1}^{m} \frac{α_i}{x - β_i},$$ where $α_1, \dots, α_m \in \mathbb{R}_{>0}$ and $β_1, \dots, β_m \in \mathbb{R}$ are arbitrary. A special case is $x_{n+1} = x_n - 1/x_n$ due to Ronald Graham for which Chamberland \& Martelli showed that the dynamics is chaotic (topologically conjugate to the doubling map). We prove that the general nonlinear recursion, despite being potentially chaotic, is effective at ensuring that most iterates end up close to one of the poles $β_i$ relatively quickly. More precisely, for a positive proportion of initial values $x \in \mathbb{R}$, the sequence gets very close (distance $\lesssim |x|^{-1}$) to one of the poles $β_i$ within a relatively small ($\lesssim x^2$) number of iteration steps.

0 citations0 reviewsNo code linkedOpen access
preprint2023arXiv

Local sign changes of polynomials

The trigonometric monomial $\cos(\left\langle k, x \right\rangle)$ on $\mathbb{T}^d$, a harmonic polynomial $p: \mathbb{S}^{d-1} \rightarrow \mathbb{R}$ of degree $k$ and a Laplacian eigenfunction $-Δf = k^2 f$ have root in each ball of radius $\sim \|k\|^{-1}$ or $\sim k^{-1}$, respectively. We extend this to linear combinations and show that for any trigonometric polynomials on $\mathbb{T}^d$, any polynomial $p \in \mathbb{R}[x_1, \dots, x_d]$ restricted to $\mathbb{S}^{d-1}$ and any linear combination of global Laplacian eigenfunctions on $ \mathbb{R}^d$ with $d \in \left\{2,3\right\}$ the same property holds for any ball whose radius is given by the sum of the inverse constituent frequencies. We also refine the fact that an eigenfunction $- Δϕ= λϕ$ in $Ω\subset \mathbb{R}^n$ has a root in each $B(x, α_n λ^{-1/2})$ ball: the positive and negative mass in each $B(x,β_n λ^{-1/2})$ ball cancel when integrated against $\|x-y\|^{2-n}$.

0 citations0 reviewsNo code linkedOpen access
preprint2023arXiv

Some Remarks on the Erdős Distinct Subset Sums Problem

Let $\left\{a_1, \dots, a_n\right\} \subset \mathbb{N}$ be a set of positive integers, $a_n$ denoting the largest element, so that for any two of the $2^n$ subsets the sum of all elements is distinct. Erdős asked whether this implies $a_n \geq c \cdot 2^n$ for some universal $c>0$. We prove, slightly extending a result of Elkies, that for any $a_1, \dots, a_n \in \mathbb{R}_{>0}$ $$ \int_{\mathbb{R}} \left( \frac{\sin{ x}}{ x} \right)^2 \prod_{i=1}^{n} \cos{( a_i x)^2} dx \geq \fracπ{2^{n}}$$ with equality if and only if all subset sums are $1-$separated. This leads to a new proof of the currently best lower bound $a_n \geq \sqrt{2/πn} \cdot 2^n$. The main new insight is that having distinct subset sums and $a_n$ small requires the random variable $X = \pm a_1 \pm a_2 \pm \dots \pm a_n$ to be close to Gaussian in a precise sense.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

An Agmon estimate for Schrödinger operators on Graphs

The Agmon estimate shows that eigenfunctions of Schrödinger operators, $ -Δϕ+ V ϕ= E ϕ$, decay exponentially in the `classically forbidden' region where the potential exceeds the energy level $\left\{x: V(x) > E \right\}$. Moreover, the size of $|ϕ(x)|$ is bounded in terms of a weighted (Agmon) distance between $x$ and the allowed region. We derive such a statement on graphs when $-Δ$ is replaced by the Graph Laplacian $L = D-A$: we identify an explicit Agmon metric and prove a pointwise decay estimate in terms of the Agmon distance.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Approximate Solutions of Linear Systems at a Universal Rate

Let $A \in \mathbb{R}^{n \times n}$ be invertible, $x \in \mathbb{R}^n$ unknown and $b =Ax $ given. We are interested in approximate solutions: vectors $y \in \mathbb{R}^n$ such that $\|Ay - b\|$ is small. We prove that for all $0< \varepsilon <1 $ there is a composition of $k$ orthogonal projections onto the $n$ hyperplanes generated by the rows of $A$, where $$k \leq 2 \log\left(\frac{1}{\varepsilon} \right) \frac{ n}{ \varepsilon^{2}}$$ which maps the origin to a vector $y\in \mathbb{R}^n$ satisfying $\| A y - Ax\| \leq \varepsilon \cdot \|A\| \cdot \| x\|$. We note that this upper bound on $k$ is independent of the matrix $A$. This procedure is stable in the sense that $\|y\| \leq 2\|x\|$. The existence proof is based on a probabilistically refined analysis of the Random Kaczmarz method which seems to achieve this rate when solving for $A x = b$ with high likelihood.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Curvature on Graphs via Equilibrium Measures

We introduce a notion of curvature on finite, combinatorial graphs. It can be easily computed by solving a linear system of equations. We show that graphs with curvature bounded below by $K>0$ have diameter bounded by $\mbox{diam}(G) \leq 2/K$ (a Bonnet-Myers theorem), that $\mbox{diam}(G) = 2/K$ implies that $G$ has constant curvature (a Cheng theorem) and that there is a spectral gap $λ_1 \geq K/(2n)$ (a Lichnerowicz theorem). It is computed for several families of graphs and often coincides with Ollivier curvature or Lin-Lu-Yau curvature. The von Neumann minimax theorem features prominently in the proofs.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Eigenvector Phase Retrieval: Recovering eigenvectors from the absolute value of their entries

We consider the eigenvalue problem $Ax = λx$ where $A \in \mathbb{R}^{n \times n}$ and the eigenvalue is also real $λ\in \mathbb{R}$. If we are given $A$, $λ$ and, additionally, the absolute value of the entries of $x$ (the vector $(|x_i|)_{i=1}^n$), is there a fast way to recover $x$? In particular, can this be done quicker than computing $x$ from scratch? This may be understood as a special case of the phase retrieval problem. We present a randomized algorithm which provably converges in expectation whenever $λ$ is a simple eigenvalue. The problem should become easier when $|λ|$ is large and we discuss another algorithm for that case as well.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Intrinsic Sparsity of Kantorovich Solutions

Let $X,Y$ be two finite sets of points having $\#X = m$ and $\#Y = n$ points with $μ= (1/m) \sum_{i=1}^{m} δ_{x_i}$ and $ν= (1/n) \sum_{j=1}^{n} δ_{y_j}$ being the associated uniform probability measures. A result of Birkhoff implies that if $m = n$, then the Kantorovich problem has a solution which also solves the Monge problem: optimal transport can be realized with a bijection $π: X \rightarrow Y$. This is impossible when $m \neq n$. We observe that when $m \neq n$, there exists a solution of the Kantorovich problem such that the mass of each point in $X$ is moved to at most $n/\gcd(m,n)$ different points in $Y$ and that, conversely, each point in $Y$ receives mass from at most $m/\gcd(m,n)$ points in $X$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

May the force be with you

Modern methods in dimensionality reduction are dominated by nonlinear attraction-repulsion force-based methods (this includes t-SNE, UMAP, ForceAtlas2, LargeVis, and many more). The purpose of this paper is to demonstrate that all such methods, by design, come with an additional feature that is being automatically computed along the way, namely the vector field associated with these forces. We show how this vector field gives additional high-quality information and propose a general refinement strategy based on ideas from Morse theory. The efficiency of these ideas is illustrated specifically using t-SNE on synthetic and real-life data sets.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

On Combinatorial Properties of Greedy Wasserstein Minimization

We discuss a phenomenon where Optimal Transport leads to a remarkable amount of combinatorial regularity. Consider infinite sequences $(x_k)_{k=1}^{\infty}$ in $[0,1]$ constructed in a greedy manner: given $x_1, \dots, x_n$, the new point $x_{n+1}$ is chosen so as to minimize the Wasserstein distance $W_2$ between the empirical measure of the $n+1$ points and the Lebesgue measure, $$x_{n+1} = \arg\min_x ~W_2\left( \frac{1}{n+1} \sum_{k=1}^{n} δ_{x_k} + \frac{δ_{x}}{n+1}, dx\right).$$ This leads to fascinating sequences (for example: $x_{n+1} = (2k+1)/(2n+2)$ for some $k \in \mathbb{Z}$) which coincide with sequences recently introduced by Ralph Kritzinger in a different setting. Numerically, the regularity of these sequences rival the best known constructions from Combinatorics or Number Theory. We prove a regularity result below the square root barrier.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Sums of Distances on Graphs and Embeddings into Euclidean Space

Let $G=(V,E)$ be a finite, connected graph. We consider a greedy selection of vertices: given a list of vertices $x_1, \dots, x_k$, take $x_{k+1}$ to be any vertex maximizing the sum of distances to the existing vertices and iterate: we keep adding the `most remote' vertex. The frequency with which the vertices of the graph appear in this sequence converges to a set of probability measures with nice properties. The support of these measures is, generically, given by a rather small number of vertices $m \ll |V|$. We prove that this suggests that the graph $G$ is at most '$m$-dimensional' by exhibiting an explicit $1-$Lipschitz embedding $ϕ: G \rightarrow \ell^1(\mathbb{R}^m)$ with good properties.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

The Boundary of a Graph and its Isoperimetric Inequality

We define, for any graph $G=(V,E)$, a boundary $\partial G \subseteq V$. The definition coincides with what one would expected for the discretization of (sufficiently nice) Euclidean domains and contains all vertices from the Chartrand-Erwin-Johns-Zhang boundary. Moreover, it satisfies an isoperimetric principle stating that graphs with many vertices have a large boundary unless they contain long paths: we show that for graphs with maximal degree $Δ$ $$ | \partial G| \geq \frac{1}{2Δ} \frac{|V|}{\mbox{diam}(G)}.$$ For graphs discretizing Euclidean domains, one has $\mbox{diam}(G) \sim |V|^{1/d}$ and recovers the scaling of the classical Euclidean isoperimetric principle.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

The product of two high-frequency Graph Laplacian eigenfunctions is smooth

In the continuous setting, we expect the product of two oscillating functions to oscillate even more (generically). On a graph $G=(V,E)$, there are only $|V|$ eigenvectors of the Laplacian $L=D-A$, so one oscillates `the most'. The purpose of this short note is to point out an interesting phenomenon: if $ϕ_1, ϕ_2$ are delocalized eigenvectors of $L$ corresponding to large eigenvalues, then their (pointwise) product $ϕ_1 \cdot ϕ_2$ is smooth (in the sense of small Dirichlet energy): highly oscillatory functions have largely matching oscillation patterns.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

A common variable minimax theorem for graphs

Let $\mathcal{G} = \{G_1 = (V, E_1), \dots, 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, \dots, 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.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

A Pointwise Inequality for Derivatives of Solutions of the Heat Equation in Bounded Domains

Let $u(t,x)$ be a solution of the heat equation in $\mathbb{R}^n$. Then, each $k-$th derivative also solves the heat equation and satisfies a maximum principle, the largest $k-$th derivative of $u(t,x)$ cannot be larger than the largest $k-$th derivative of $u(0,x)$. We prove an analogous statement for the solution of the heat equation on bounded domains $Ω\subset \mathbb{R}^n$ with Dirichlet boundary conditions. As an application, we give a new and fairly elementary proof of the sharp growth of the second derivatives of Laplacian eigenfunction $-Δϕ_k = λ_k ϕ_k$ with Dirichlet conditions on smooth domains $Ω\subset \mathbb{R}^n$.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Finding Structure in Sequences of Real Numbers via Graph Theory: a Problem List

We investigate a method of generating a graph $G=(V,E)$ out of an ordered list of $n$ distinct real numbers $a_1, \dots, a_n$. These graphs can be used to test for the presence of interesting structure in the sequence. We describe sequences exhibiting intricate hidden structure that was discovered this way. Our list includes sequences of Deutsch, Erdős, Freud & Hegyvari, Recaman, Quet, Zabolotskiy and Zizka. Since our observations are mostly empirical, each sequence in the list is an open problem.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Max-Cut via Kuramoto-type Oscillators

We consider the Max-Cut problem. Let $G = (V,E)$ be a graph with adjacency matrix $(a_{ij})_{i,j=1}^{n}$. Burer, Monteiro & Zhang proposed to find, for $n$ angles $\left\{θ_1, θ_2, \dots, θ_n\right\} \subset [0, 2π]$, minima of the energy $$ f(θ_1, \dots, θ_n) = \sum_{i,j=1}^{n} a_{ij} \cos{(θ_i - θ_j)}$$ because configurations achieving a global minimum leads to a partition of size 0.878 Max-Cut(G). This approach is known to be computationally viable and leads to very good results in practice. We prove that by replacing $\cos{(θ_i - θ_j)}$ with an explicit function $g_{\varepsilon}(θ_i - θ_j)$ global minima of this new functional lead to a $(1-\varepsilon)$Max-Cut(G). This suggests some interesting algorithms that perform well. It also shows that the problem of finding approximate global minima of energy functionals of this type is NP-hard in general.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Neural Collapse with Cross-Entropy Loss

We consider the variational problem of cross-entropy loss with $n$ feature vectors on a unit hypersphere in $\mathbb{R}^d$. We prove that when $d \geq n - 1$, the global minimum is given by the simplex equiangular tight frame, which justifies the neural collapse behavior. We also prove that as $n \rightarrow \infty$ with fixed $d$, the minimizing points will distribute uniformly on the hypersphere and show a connection with the frame potential of Benedetto & Fickus.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

On Concavity of Solutions of the Nonlinear Poisson Equation

We consider the nonlinear Poisson equation $-Δu = f(u)$ in domains $Ω\subset \mathbb{R}^n$ with Dirichlet boundary conditions on $\partial Ω$. We show (for monotonically increasing concave $f$ with small Lipschitz constant) that if $D^2 u$ is negative semi-definite on the boundary, then $u$ is concave. A conjecture of Saint Venant from 1856 (proven by Polya in 1948) is that among all domains $Ω$ of fixed measure, the solution of $-Δu =1$ assumes its largest maximum when $Ω$ is a ball. We extend this to $-Δu =f(u)$ for monotonically increasing $f$ with small Lipschitz constant.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

t-SNE, Forceful Colorings and Mean Field Limits

t-SNE is one of the most commonly used force-based nonlinear dimensionality reduction methods. This paper has two contributions: the first is forceful colorings, an idea that is also applicable to other force-based methods (UMAP, ForceAtlas2,...). In every equilibrium, the attractive and repulsive forces acting on a particle cancel out: however, both the size and the direction of the attractive (or repulsive) forces acting on a particle are related to its properties: the force vector can serve as an additional feature. Secondly, we analyze the case of t-SNE acting on a single homogeneous cluster (modeled by affinities coming from the adjacency matrix of a random k-regular graph); we derive a mean-field model that leads to interesting questions in classical calculus of variations. The model predicts that, in the limit, the t-SNE embedding of a single perfectly homogeneous cluster is not a point but a thin annulus of diameter $\sim k^{-1/4} n^{-1/4}$. This is supported by numerical results. The mean field ansatz extends to other force-based dimensionality reduction methods.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A Nonlocal Transport Equation Modeling Complex Roots of Polynomials under Differentiation

Let $p_n:\mathbb{C} \rightarrow \mathbb{C}$ be a random complex polynomial whose roots are sampled i.i.d. from a radial distribution $u(r) r dr$ in the complex plane. A natural question is how the distribution of roots evolves under repeated (say $n/2-$times) differentiation of the polynomial. We conjecture a mean-field expansion for the evolution of $ψ(s) = u(s) s$ $$ \frac{\partial ψ}{\partial t} = \frac{\partial}{\partial x} \left( \left( \frac{1}{x} \int_{0}^{x} ψ(s) ds \right)^{-1} ψ(x) \right).$$ The evolution of $ψ(s) \equiv 1$ corresponds to the evolution of random Taylor polynomials $$ p_n(z) = \sum_{k=0}^{n}{ γ_k \frac{z^k}{k!}} \quad \mbox{where} \quad γ_k \sim \mathcal{N}_{\mathbb{C}}(0,1).$$ We discuss some numerical examples suggesting that this particular solution may be stable. We prove that the solution is linearly stable. The linear stability analysis reduces to the classical Hardy integral inequality. Many open problems are discussed.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A Semicircle Law for Derivatives of Random Polynomials

Let $x_1, \dots, x_n$ be $n$ independent and identically distributed random variables with mean zero, unit variance, and finite moments of all remaining orders. We study the random polynomial $p_n$ having roots at $x_1, \dots, x_n$. We prove that for $\ell \in \mathbb{N}$ fixed as $n \rightarrow \infty$, the $(n-\ell)-$th derivative of $p_n^{}$ behaves like a Hermite polynomial: for $x$ in a compact interval,$${n^{\ell/2}} \frac{\ell!}{n!} \cdot p_n^{(n-\ell)}\left( \frac{x}{\sqrt{n}}\right) \rightarrow He_{\ell}(x + γ_n),$$ where $He_{\ell}$ is the $\ell-$th probabilists' Hermite polynomial and $γ_n$ is a random variable converging to the standard $\mathcal{N}(0,1)$ Gaussian as $n \rightarrow \infty$. Thus, there is a universality phenomenon when differentiating a random polynomial many times: the remaining roots follow a Wigner semicircle distribution.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

A Spectral Approach to the Shortest Path Problem

Let $G=(V,E)$ be a simple, connected graph. One is often interested in a short path between two vertices $u,v$. We propose a spectral algorithm: construct the function $ϕ:V \rightarrow \mathbb{R}_{\geq 0}$ $$ ϕ= \arg\min_{f:V \rightarrow \mathbb{R} \atop f(u) = 0, f \not\equiv 0} \frac{\sum_{(w_1, w_2) \in E}{(f(w_1)-f(w_2))^2}}{\sum_{w \in V}{f(w)^2}}.$$ $ϕ$ can also be understood as the smallest eigenvector of the Laplacian Matrix $L=D-A$ after the $u-$th row and column have been removed. We start in the point $v$ and construct a path from $v$ to $u$: at each step, we move to the neighbor for which $ϕ$ is the smallest. This algorithm provably terminates and results in a short path from $v$ to $u$, often the shortest. The efficiency of this method is due to a discrete analogue of a phenomenon in Partial Differential Equations that is not well understood. We prove optimality for trees and discuss a number of open questions.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Conservation Laws for the Density of Roots of Polynomials under Differentiation

Let $p_n(x)$ be a polynomial of degree $n$ having $n$ distinct, real roots distributed according to a nice probability distribution $u(0,x)dx$ on $\mathbb{R}$. One natural problem is to understand the density $u(t,x)$ of the roots of the $(t\cdot n)-$th derivative of $p_n$ where $0 < t < 1$ as $n \rightarrow \infty$. We derive an \textit{infinite} number of conversation laws for the evolution of $u(t,x)$. The first three are \begin{align*} \int_{\mathbb{R}}{ u(t,x) ~ dx} = 1-t, \qquad \qquad \int_{\mathbb{R}}{ u(t,x) x ~ dx} = \left(1-t\right)\int_{\mathbb{R}}{ u(0,x) x~ dx}, \qquad \int_{\mathbb{R}} \int_{\mathbb{R}} u(t,x) (x-y)^2 u(t,y) ~ dx dy = (1-t)^3 \int_{\mathbb{R}} \int_{\mathbb{R}} u(0,x) (x-y)^2 u(0,y) ~ dx dy. \end{align*} The author suggested that $u(t,x)$ might evolve according to a nonlocal evolution equation involving the Hilbert transform; this has been verified for two special closed form solutions -- these conservation laws thus point to interesting identities for the Hilbert transform. We discuss many open problems.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Fourier Uncertainty Principles, Scale Space Theory and the Smoothest Average

Let $f \in L^{2}(\mathbb{R}^n)$ and suppose we are interested in computing its average at a fixed scale. This is easy: we pick the density $u_{}$ of a probability distribution with mean 0 and some moment at the desired scale and compute the convolution $u_{} * f$. Is there a particularly natural choice for $u$? This question is studied in scale space theory and the Gaussian is a popular answer. We were interested whether a canonical choice for $u$ can arise from a new axiom: having fixed a scale, the average should oscillate as little as possible, i.e. $$ u_{} = \arg\min_{u_{}} \sup_{f \in L^2(\mathbb{R}^n)} \frac{\| \nabla (u_{} *f) \|_{L^2(\mathbb{R}^n)}}{\|f\|_{L^2(\mathbb{R}^n)}}.$$ This optimal function turns out to be a minimizer of an uncertainty principle: for $α> 0$ and $β> n/2$, there exists $c_{α, β,n} > 0$ such that for all $u \in L^1(\mathbb{R}^n)$ $$ \| |ξ|^β \cdot \widehat{u}\|^α_{L^{\infty}(\mathbb{R}^n)} \cdot \| |x|^α \cdot u \|^β_{L^1(\mathbb{R}^n)} \geq c_{α, β,n} \|u\|_{L^1(\mathbb{R}^n)}^{α+ β}.$$ For $β= 1$, any nonnegative extremizer of the inequality serves as the best averaging function in the sense above, $β\neq 1$ corresponds to other derivatives. For $(n, β)=(1,1)$ we use the Shannon-Whittaker formula to prove that the characteristic function $u(x) = χ_{[-1/2,1/2]}$ is a local minimizer among functions defined on $[-1/2,1/2]$ for $α\in \left\{2,3,4,5,6\right\}$. We provide a sufficient condition for general $α$ in terms of a sign pattern for the hypergeometric function $_1F_2$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Non-Convex Planar Harmonic Maps

We formulate a novel characterization of a family of invertible maps between two-dimensional domains. Our work follows two classic results: The Radó-Kneser-Choquet (RKC) theorem, which establishes the invertibility of harmonic maps into a convex planer domain; and Tutte's embedding theorem for planar graphs - RKC's discrete counterpart - which proves the invertibility of piecewise linear maps of triangulated domains satisfying a discrete-harmonic principle, into a convex planar polygon. In both theorems, the convexity of the target domain is essential for ensuring invertibility. We extend these characterizations, in both the continuous and discrete cases, by replacing convexity with a less restrictive condition. In the continuous case, Alessandrini and Nesi provide a characterization of invertible harmonic maps into non-convex domains with a smooth boundary by adding additional conditions on orientation preservation along the boundary. We extend their results by defining a condition on the normal derivatives along the boundary, which we call the cone condition; this condition is tractable and geometrically intuitive, encoding a weak notion of local invertibility. The cone condition enables us to extend Alessandrini and Nesi to the case of harmonic maps into non-convex domains with a piecewise-smooth boundary. In the discrete case, we use an analog of the cone condition to characterize invertible discrete-harmonic piecewise-linear maps of triangulations. This gives an analog of our continuous results and characterizes invertible discrete-harmonic maps in terms of the orientation of triangles incident on the boundary.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On Eigenvectors of Random Band Matrices with Large Band

We study random, symmetric $N \times N$ band matrices with a band of size $W$ and Bernoulli random variables as entries. This interpolates between nearest neighbour interaction $W = 1$ and Wigner matrices $W = N$. Eigenvectors are known to be localized for $W \ll N^{1/8}$, delocalized for $W \gg N^{4/5}$ and it is conjectured that the transition for the bulk occurs at $W \sim N^{1/2}$. Eigenvalues in the spectral edge change their behavior at $W \sim N^{5/6}$ but nothing is known about the associated eigenvectors. We show that up to $W \ll N^{5/7}$ any random matrix has with large probability some eigenvectors in the spectral edge, which either exhibit mass concentration or interact strongly on a small scale.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On Matrix Rearrangement Inequalities

Given two symmetric and positive semidefinite square matrices $A, B$, is it true that any matrix given as the product of $m$ copies of $A$ and $n$ copies of $B$ in a particular sequence must be dominated in the spectral norm by the ordered matrix product $A^m B^n$? For example, is $$ \| AABAABABB \| \leq \| AAAAABBBB \|\ ? $$ Drury has characterized precisely which disordered words have the property that an inequality of this type holds for all matrices $A,B$. However, the $1$-parameter family of counterexamples Drury constructs for these characterizations is comprised of $3 \times 3$ matrices, and thus as stated the characterization applies only for $N \times N$ matrices with $N \geq 3$. In contrast, we prove that for $2 \times 2$ matrices, the general rearrangement inequality holds for all disordered words. We also show that for larger $N \times N$ matrices, the general rearrangement inequality holds for all disordered words, for most $A,B$ (in a sense of full measure) that are sufficiently small perturbations of the identity.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On the Regularization Effect of Stochastic Gradient Descent applied to Least Squares

We study the behavior of stochastic gradient descent applied to $\|Ax -b \|_2^2 \rightarrow \min$ for invertible $A \in \mathbb{R}^{n \times n}$. We show that there is an explicit constant $c_{A}$ depending (mildly) on $A$ such that $$ \mathbb{E} ~\left\| Ax_{k+1}-b\right\|^2_{2} \leq \left(1 + \frac{c_{A}}{\|A\|_F^2}\right) \left\|A x_k -b \right\|^2_{2} - \frac{2}{\|A\|_F^2} \left\|A^T A (x_k - x)\right\|^2_{2}.$$ This is a curious inequality: the last term has one more matrix applied to the residual $u_k - u$ than the remaining terms: if $x_k - x$ is mainly comprised of large singular vectors, stochastic gradient descent leads to a quick regularization. For symmetric matrices, this inequality has an extension to higher-order Sobolev spaces. This explains a (known) regularization phenomenon: an energy cascade from large singular values to small singular values smoothes.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On Vickrey's Income Averaging

We consider a small set of axioms for income averaging -- recursivity, continuity, and the boundary condition for the present. These properties yield a unique averaging function that is the density of the reflected Brownian motion with a drift started at the current income and moving over the past incomes. When averaging is done over the short past, the weighting function is asymptotically converging to a Gaussian. When averaging is done over the long horizon, the weighing function converges to the exponential distribution. For all intermediate averaging scales, we derive an explicit solution that interpolates between the two.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Positive-definite Functions, Exponential Sums and the Greedy Algorithm: a curious Phenomenon

We describe a curious dynamical system that results in sequences of real numbers in $[0,1]$ with seemingly remarkable properties. Let the function $f:\mathbb{T} \rightarrow \mathbb{R}$ satisfy $\hat{f}(k) \geq c|k|^{-2}$ and define a sequence via $$ x_n = \arg\min_x \sum_{k=1}^{n-1}{f(x-x_k)}.$$ Such sequences $(x_n)_{n=1}^{\infty}$ seem to be astonishingly regularly distributed in various ways (satisfying favorable exponential sum estimates; every interval $J \subset [0,1]$ contains $\sim |J|n$ elements). We prove $$ W_2\left( \frac{1}{n} \sum_{k=1}^{n}{δ_{x_k}}, dx\right) \leq \frac{c}{\sqrt{n}},$$ where $W_2$ is the 2-Wasserstein distance. Much stronger results seem to be true and it seems like an interesting problem to understand this dynamical system better. We obtain optimal results in dimension $d \geq 3$: using $G(x,y)$ to denote the Green's function of the Laplacian on a compact manifold, we show that $$ x_n = \arg\min_{x \in M} \sum_{k=1}^{n-1}{G(x,x_k)} \quad \mbox{satisfies} \quad W_2\left( \frac{1}{n} \sum_{k=1}^{n}{δ_{x_k}}, dx\right) \lesssim \frac{1}{n^{1/d}}.$$

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Regularized Potentials of Schrödinger Operators and a Local Landscape Function

We study localization properties of low-lying eigenfunctions $$(-Δ+V) ϕ= λϕ\qquad \mbox{in}~Ω$$ for rapidly varying potentials $V$ in bounded domains $Ω\subset \mathbb{R}^d$. Filoche & Mayboroda introduced the landscape function $(-Δ+ V)u=1$ and showed that the function $u$ has remarkable properties: localized eigenfunctions prefer to localize in the local maxima of $u$. Arnold, David, Filoche, Jerison \& Mayboroda showed that $1/u$ arises naturally as the potential in a related equation. Motivated by these questions, we introduce a one-parameter family of regularized potentials $V_t$ that arise from convolving $V$ with the radial kernel $$ V_t(x) = V * \left( \frac{1}{t} \int_0^t \frac{ \exp\left( - \|\cdot\|^2/ (4s) \right)}{(4 πs )^{d/2}} ds \right).$$ We prove that for eigenfunctions $(-Δ+V) ϕ= λϕ$ this regularization $V_t$ is, in a precise sense, the canonical effective potential on small scales. The landscape function $u$ respects the same type of regularization. This allows allows us to derive landscape-type functions out of solutions of the equation $(-Δ+ V)u = f$ for a general right-hand side $f:Ω\rightarrow \mathbb{R}_{>0}$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Spectral Clustering Revisited: Information Hidden in the Fiedler Vector

We are interested in the clustering problem on graphs: it is known that if there are two underlying clusters, then the signs of the eigenvector corresponding to the second largest eigenvalue of the adjacency matrix can reliably reconstruct the two clusters. We argue that the vertices for which the eigenvector has the largest and the smallest entries, respectively, are unusually strongly connected to their own cluster and more reliably classified than the rest. This can be regarded as a discrete version of the Hot Spots conjecture and should be useful in applications. We give a rigorous proof for the stochastic block model and several examples.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

The smoothest average: Dirichlet, Fejér and Chebyshev

We are interested in the ``smoothest'' averaging that can be achieved by convolving functions $f \in \ell^2(\mathbb{Z})$ with an averaging function $u$. More precisely, suppose $u:\{-n, \ldots, n\} \to \mathbb{R}$ is a symmetric function normalized to $\sum_{k=-n}^{n}u(k) = 1$. We show that every convolution operator is not-too-smooth, in the sense that $$\sup_{f \in \ell^2(\mathbb{Z})} \frac{\| \nabla (f*u)\|_{\ell^2(\mathbb{Z})}}{\|f\|_{\ell^2}}\geq \frac{2}{2n+1},$$ and we show that equality holds if and only if $u$ is constant on the interval $\{-n, \ldots, n\}$. In the setting where smoothness is measured by the $\ell^2$-norm of the discrete second derivative and we further restrict our attention to functions $u$ with nonnegative Fourier transform, we establish the inequality $$\sup_{f \in \ell^2(\mathbb{Z})} \frac{\| Δ(f*u)\|_{\ell^2(\mathbb{Z})}}{\|f\|_{\ell^2(\mathbb{Z})}} \geq \frac{4}{(n+1)^2},$$ with equality if and only if $u$ is the triangle function $u(k)=(n+1-|k|)/(n+1)^2$. We also discuss a continuous analogue and several open problems.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Three Convolution Inequalities on the Real Line with Connections to Additive Combinatorics

We discuss three convolution inequalities that are connected to additive combinatorics. Cloninger and the second author showed that for nonnegative $f \in L^1(-1/4, 1/4)$, $$ \max_{-1/2 \leq t \leq 1/2} \int_{\mathbb{R}}{f(t-x) f(x) dx} \geq 1.28 \left( \int_{-1/4}^{1/4}{f(x) dx}\right)^2$$ which is related to $g-$Sidon sets (1.28 cannot be replaced by 1.52). We prove a dual statement, related to difference bases, and show that for $f \in L^1(\mathbb{R})$, $$ \min_{0 \leq t \leq 1}\int_{\mathbb{R}}{f(x) f(x+t) dx} \leq 0.42 \|f\|_{L^1}^2,$$ where the constant 1/2 is trivial, 0.42 cannot be replaced by 0.37. This suggests a natural conjecture about the asymptotic structure of $g-$difference bases. Finally, we show for all functions $f \in L^1(\mathbb{R}) \cap L^2(\mathbb{R})$, $$ \int_{-\frac{1}{2}}^{\frac{1}{2}}{ \int_{\mathbb{R}}{f(x) f(x+t) dx}dt} \leq 0.91 \|f\|_{L^1}\|f\|_{L^2}$$

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Using Expander Graphs to test whether samples are i.i.d

The purpose of this note is to point out that the theory of expander graphs leads to an interesting test whether $n$ real numbers $x_1, \dots, x_n$ could be $n$ independent samples of a random variable. To any distinct, real numbers $x_1, \dots, x_n$, we associate a 4-regular graph $G$ as follows: using $π$ to denote the permutation ordering the elements, $x_{π(1)} < x_{π(2)} < \dots < x_{π(n)}$, we build a graph on $\left\{1, \dots, n\right\}$ by connecting $i$ and $i+1$ (cyclically) and $π(i)$ and $π(i+1)$ (cyclically). If the numbers are i.i.d. samples, then a result of Friedman implies that $G$ is close to Ramanujan. This suggests a test for whether these numbers are i.i.d: compute the second largest (in absolute value) eigenvalue of the adjacency matrix. The larger $λ- 2\sqrt{3}$, the less likely it is for the numbers to be i.i.d. We explain why this is a reasonable test and give many examples.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Wasserstein Distance, Fourier Series and Applications

We study the Wasserstein metric $W_p$, a notion of distance between two probability distributions, from the perspective of Fourier Analysis and discuss applications. In particular, we bound the Earth Mover Distance $W_1$ between the distribution of quadratic residues in a finite field $\mathbb{F}_p$ and uniform distribution by $\lesssim p^{-1/2}$ (the Polya-Vinogradov inequality implies $\lesssim p^{-1/2} \log{p}$). We also show for continuous $f:\mathbb{T} \rightarrow \mathbb{R}_{}$ with mean value 0 $$ (\mbox{number of roots of}~f) \cdot \left( \sum_{k=1}^{\infty}{ \frac{ |\hat{f}(k)|^2}{k^2}}\right)^{\frac{1}{2}} \gtrsim \frac{\|f\|^{2}_{L^1(\mathbb{T})}}{\|f\|_{L^{\infty}(\mathbb{T})}}.$$ Moreover, we show that for a Laplacian eigenfunction $-Δ_g ϕ_λ = λϕ_λ$ on a compact Riemannian manifold $W_p\left(\max\left\{ϕ_λ, 0\right\}dx, \max\left\{-ϕ_λ, 0\right\} dx\right) \lesssim_p \sqrt{\logλ/λ} \|ϕ_λ\|_{L^1}^{1/p}$ which is at most a factor $\sqrt{\logλ}$ away from sharp. Several other problems are discussed.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Heavy-tailed kernels reveal a finer cluster structure in t-SNE visualisations

T-distributed stochastic neighbour embedding (t-SNE) is a widely used data visualisation technique. It differs from its predecessor SNE by the low-dimensional similarity kernel: the Gaussian kernel was replaced by the heavy-tailed Cauchy kernel, solving the "crowding problem" of SNE. Here, we develop an efficient implementation of t-SNE for a $t$-distribution kernel with an arbitrary degree of freedom $ν$, with $ν\to\infty$ corresponding to SNE and $ν=1$ corresponding to the standard t-SNE. Using theoretical analysis and toy examples, we show that $ν<1$ can further reduce the crowding problem and reveal finer cluster structure that is invisible in standard t-SNE. We further demonstrate the striking effect of heavier-tailed kernels on large real-life data sets such as MNIST, single-cell RNA-sequencing data, and the HathiTrust library. We use domain knowledge to confirm that the revealed clusters are meaningful. Overall, we argue that modifying the tail heaviness of the t-SNE kernel can yield additional insight into the cluster structure of the data.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Leaky Roots and Stable Gauss-Lucas Theorems

Let $p:\mathbb{C} \rightarrow \mathbb{C}$ be a polynomial. The Gauss-Lucas theorem states that its critical points, $p'(z) = 0$, are contained in the convex hull of its roots. A recent quantitative version Totik shows that if almost all roots are contained in a bounded convex domain $K \subset \mathbb{C}$, then almost all roots of the derivative $p'$ are in a $\varepsilon-$neighborhood $K_{\varepsilon}$ (in a precise sense). We prove another quantitative version: if a polynomial $p$ has $n$ roots in $K$ and $\lesssim c_{K, \varepsilon} (n/\log{n})$ roots outside of $K$, then $p'$ has at least $n-1$ roots in $K_{\varepsilon}$. This establishes, up to a logarithm, a conjecture of the first author: we also discuss an open problem whose solution would imply the full conjecture.

0 citations0 reviewsNo code linkedOpen access
preprint2017arXiv

On the location of maximal of solutions of Schrödinger's equation

We prove an inequality with applications to solutions of the Schrödinger equation. There is a universal constant $c>0$, such that if $Ω\subset \mathbb{R}^2$ is simply connected, $u:Ω\rightarrow \mathbb{R}$ vanishes on the boundary $\partial Ω$, and $|u|$ assumes a maximum in $x_0 \in Ω$, then $$ \inf_{y \in \partial Ω}{ \| x_0 - y\|} \geq c \left\| \frac{Δu}{u} \right\|^{-1/2}_{L^{\infty}(Ω)}.$$ It was conjectured by Pólya \& Szegő (and proven, independently, by Makai and Hayman) that a membrane vibrating at frequency $λ$ contains a disk of size $\sim λ^{-1/2}$. Our inequality implies a refined result: the point on the membrane that achieves the maximal amplitude is at distance $\sim λ^{-1/2}$ from the boundary. We also give an extension to higher dimensions (generalizing results of Lieb and Georgiev \& Mukherjee): if $u$ solves $-Δu = Vu$ on $Ω\subset \mathbb{R}^n$ with Dirichlet boundary conditions, then the ball $B$ with radius $\sim \|V\|_{L^{\infty}(Ω)}^{-1/2}$ centered at the point in which $|u|$ assumes a maximum is almost fully contained in $Ω$ in the sense that $|B \cap Ω| \geq 0.99 |B|.$

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A Hidden Signal in the Ulam sequence

The Ulam sequence is defined as $a_1 =1, a_2 = 2$ and $a_n$ being the smallest integer that can be written as the sum of two distinct earlier elements in a unique way. This gives $$1, 2, 3, 4, 6, 8, 11, 13, 16, 18, 26, 28, 36, 38, 47, \dots$$ Ulam remarked that understanding the sequence, which has been described as 'quite erratic', seems difficult and indeed nothing is known. We report the empirical discovery of a surprising global rigidity phenomenon: there seems to exist a real $α\sim 2.5714474995\dots$ such that $$\left\{αa_n: n\in \mathbb{N}\right\} \quad \mbox{mod}~2π\quad \mbox{generates an absolutely continuous \textit{non-uniform} measure}$$ supported on a subset of $\mathbb{T}$. Indeed, for the first $10^7$ elements of Ulam's sequence, $$ \cos{\left( 2.5714474995~ a_n\right)} < 0 \qquad \mbox{for all}~a_n \notin \left\{2, 3, 47, 69\right\}.$$ The same phenomenon arises for some other initial conditions $a_1, a_2$: the distribution functions look very different from each other and have curious shapes. A similar but more subtle phenomenon seems to arise in Lagarias' variant of MacMahon's 'primes of measurement' sequence.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Carrier frequencies, holomorphy and unwinding

We prove that functions of intrinsic-mode type (a classical models for signals) behave essentially like holomorphic functions: adding a pure carrier frequency $e^{int}$ ensures that the anti-holomorphic part is much smaller than the holomorphic part $ \| P_{-}(f)\|_{L^2} \ll \|P_{+}(f)\|_{L^2}.$ This enables us to use techniques from complex analysis, in particular the \textit{unwinding series}. We study its stability and convergence properties and show that the unwinding series can stabilize and show that the unwinding series can provide a high resolution time-frequency representation, which is robust to noise.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Directional Poincare inequalities along mixing flows

We provide a refinement of the Poincaré inequality on the torus $\mathbb{T}^d$: there exists a Lebesgue-null set $\mathcal{B} \subset \mathbb{T}^d$ of directions such that for every $α\in \mathcal{B}$ there is a $c_α > 0$ with $$ \|\nabla f\|_{L^2(\mathbb{T}^d)}^{d-1} \| \left\langle \nabla f, α\right\rangle\|_{L^2(\mathbb{T}^d)} \geq c_α\|f\|_{L^2(\mathbb{T}^d)}^{d} \qquad\mbox{for all}~f\in H^1(\mathbb{T}^d)~\mbox{with mean 0.}$$ The derivative $\left\langle \nabla f, α\right\rangle$ does not detect any oscillation in directions orthogonal to $α$, however, for certain $α$ the geodesic flow in direction $α$ is sufficiently ergodic to compensate for that defect. On the two-dimensional torus $\mathbb{T}^2$ the inequality holds for $α= (1, \sqrt{2})$ but fails for $α= (1,e)$. Similar results should hold at a great level of generality on very general domains.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Fast Escape in Incompressible Vector Fields

Swimmers caught in a rip current flowing away from the shore are advised to swim orthogonally to the current to escape it. We describe a mathematical principle in a similar spirit. More precisely, we consider flows $γ$ in the plane induced by incompressible vector fields $\textbf{v}:\mathbb{R}^2 \rightarrow \mathbb{R}^2$ satisfying $ c_1 < \|v\| < c_2.$ The length $\ell$ a flow curve $\dot γ(t) = \textbf{v}(γ(t))$ until $γ$ leaves a disk of radius 1 centered at the initial position can be as long as $\ell \sim c_2/c_1$. The same is true for the orthogonal flow $\textbf{v}^{\perp} = (-\textbf{v}_2, \textbf{v}_1)$. We show that a combination does strictly better: there always exists a curve flowing first along $\textbf{v}^{\perp}$ and then along $\textbf{v}$ which escapes the unit disk before reaching the length $ \sqrt{4πc_2 / c_1}$. Moreover, if the escape length of $\textbf{v}$ is uniformly $\sim c_2/c_1$, then the escape length of $\textbf{v}^{\perp}$ is uniformly $\sim 1$ (allowing for a fast escape from the current). We also prove an elementary quantitative Poincaré-Bendixson theorem that seems to be new.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Hermite polynomials, linear flows on the torus, and an uncertainty principle for roots

We study a recent result of Bourgain, Clozel and Kahane, a version of which states that a sufficiently nice function $f:\mathbb{R} \rightarrow \mathbb{R}$ that coincides with its Fourier transform and vanishes at the origin has a root in the interval $(c, \infty)$, where the optimal $c$ satisfies $0.41 \leq c \leq 0.64$. A similar result holds in higher dimensions. We improve the one-dimensional result to $0.45 \leq c \leq 0.594$, and the lower bound in higher dimensions. We also prove that extremizers exist, and have infinitely many double roots. With this purpose in mind, we establish a new structure statement about Hermite polynomials which relates their pointwise evaluation to linear flows on the torus, and applies to other families of orthogonal polynomials as well.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Nonlinear phase unwinding of functions

We study a natural nonlinear analogue of Fourier series. Iterative Blaschke factorization allows one to formally write any holomorphic function $F$ as a series which successively unravels or unwinds the oscillation of the function $$ F = a_1 B_1 + a_2 B_1 B_2 + a_3 B_1 B_2 B_3 + \dots$$ where $a_i \in \mathbb{C}$ and $B_i$ is a Blaschke product. Numerical experiments point towards rapid convergence of the formal series but the actual mechanism by which this is happening has yet to be explained. We derive a family of inequalities and use them to prove convergence for a large number of function spaces: for example, we have convergence in $L^2$ for functions in the Dirichlet space $\mathcal{D}$. Furthermore, we present a numerically efficient way to expand a function without explicit calculations of the Blaschke zeroes going back to Guido and Mary Weiss.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On Suprema of Autoconvolutions with an Application to Sidon sets

Let $f$ be a nonnegative function supported on $(-1/4, 1/4)$. We show $$ \sup_{x \in \mathbb{R}}{\int_{\mathbb{R}}{f(t)f(x-t)dt}} \geq 1.28\left(\int_{-1/4}^{1/4}{f(x)dx} \right)^2,$$ where 1.28 improves on a series of earlier results. The inequality arises naturally in additive combinatorics in the study of Sidon sets. We derive a relaxation of the problem that reduces to a finite number of cases and yields slightly stronger results. Our approach should be able to prove lower bounds that are arbitrary close to the sharp result. Currently, the bottleneck in our approach is runtime: new ideas might be able to significantly speed up the computation.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On the Diffusion Geometry of Graph Laplacians and Applications

We study directed, weighted graphs $G=(V,E)$ and consider the (not necessarily symmetric) averaging operator $$ (\mathcal{L}u)(i) = -\sum_{j \sim_{} i}{p_{ij} (u(j) - u(i))},$$ where $p_{ij}$ are normalized edge weights. Given a vertex $i \in V$, we define the diffusion distance to a set $B \subset V$ as the smallest number of steps $d_{B}(i) \in \mathbb{N}$ required for half of all random walks started in $i$ and moving randomly with respect to the weights $p_{ij}$ to visit $B$ within $d_{B}(i)$ steps. Our main result is that the eigenfunctions interact nicely with this notion of distance. In particular, if $u$ satisfies $\mathcal{L}u = λu$ on $V$ and $$ B = \left\{ i \in V: - \varepsilon \leq u(i) \leq \varepsilon \right\} \neq \emptyset,$$ then, for all $i \in V$, $$ d_{B}(i) \log{\left( \frac{1}{|1-λ|} \right) } \geq \log{\left( \frac{ |u(i)| }{\|u\|_{L^{\infty}}} \right)} - \log{\left(\frac{1}{2} + \varepsilon\right)}.$$ $d_B(i)$ is a remarkably good approximation of $|u|$ in the sense of having very high correlation. The result implies that the classical one-dimensional spectral embedding preserves particular aspects of geometry in the presence of clustered data. We also give a continuous variant of the result which has a connection to the hot spots conjecture.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Optimal Gabor frame bounds for separable lattices and estimates for Jacobi theta functions

We study sharp frame bounds of Gabor frames with the standard Gaussian window and prove that the square lattice optimizes both the lower and the upper frame bound among all rectangular lattices. This proves a conjecture of Floch, Alard & Berrou (as reformulated by Strohmer & Beaver). The proof is based on refined log-convexity/concavity estimates for the Jacobi theta functions $θ_3$ and $θ_4$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Refined Heinz-Kato-Löwner inequalities

A version of the Cauchy-Schwarz inequality in operator theory is the following: for any two symmetric, positive definite matrices $A,B \in \mathbb{R}^{n \times n}$ and arbitrary $X \in \mathbb{R}^{n \times n}$ $$ \|AXB\| \leq \|A^2 X\|^{\frac{1}{2}} \|X B^2\|^{\frac{1}{2}}.$$ This inequality is classical and equivalent to the celebrated Heinz-Löwner, Heinz-Kato and Cordes inequalities. We characterize cases of equality: in particular, after factoring out the symmetry coming from multiplication with scalars $ \|A^2 X\| = 1 = \|X B^2\|$, the case of equality requires that $A$ and $B$ have a common eigenvalue $λ_i = μ_j$. We also derive improved estimates and show that if either $λ_i λ_j = μ_k^2$ or $λ_i^2 = μ_j μ_k$ does not have a solution, i.e. if $d > 0$ where \begin{align*} d &= \min_{1 \leq i,j,k \leq n} \{ | \log{ λ_i} + \log{ λ_j} - 2\log{ μ_k}|:λ_i, λ_j \in σ(A), μ_k \in σ(B) \} &+\min_{1 \leq i,j,k \leq n}\{ | 2\log{λ_i} - \log{ μ_j} - \log{μ_k } |:λ_i \in σ(A), μ_j, μ_k \in σ(B) \}, \end{align*} then there is an improved inequality $$ \|AXB\| \leq (1 - c_{n,d})\|A^2 X\|^{\frac{1}{2}} \|X B^2\|^{\frac{1}{2}}$$ for some $c_{n,d} > 0$ that only depends only on $n$ and $d$. We obtain similar results for the McIntosh inequality and the Cordes inequality and expect the method to have many further applications.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Spectral Echolocation via the Wave Embedding

Spectral embedding uses eigenfunctions of the discrete Laplacian on a weighted graph to obtain coordinates for an embedding of an abstract data set into Euclidean space. We propose a new pre-processing step of first using the eigenfunctions to simulate a low-frequency wave moving over the data and using both position as well as change in time of the wave to obtain a refined metric to which classical methods of dimensionality reduction can then applied. This is motivated by the behavior of waves, symmetries of the wave equation and the hunting technique of bats. It is shown to be effective in practice and also works for other partial differential equations -- the method yields improved results even for the classical heat equation.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Stability Estimates for Truncated Fourier and Laplace Transforms

We prove sharp stability estimates for the Truncated Laplace Transform and Truncated Fourier Transform. The argument combines an approach recently introduced by Alaifari, Pierce and the second author for the truncated Hilbert transform with classical results of Bertero, Grünbaum, Landau, Pollak and Slepian. In particular, we prove there is a universal constant $c >0$ such that for all $f \in L^2(\mathbb{R})$ with compact support in $[-1,1]$ normalized to $\|f\|_{L^2[-1,1]} = 1$ $$ \int_{-1}^{1}{|\widehat{f}(ξ)|^2dξ} \gtrsim \left(c\left\|f_x \right\|_{L^2[-1,1]} \right)^{- c\left\|f_x \right\|_{L^2[-1,1]}}$$ The inequality is sharp in the sense that there is an infinite sequence of orthonormal counterexamples if $c$ is chosen too small. The question whether and to which extent similar inequalities hold for generic families of integral operators remains open.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Well-distributed great circles on S^2

Let $C_1, \dots, C_n$ denote the $1/n-$neighborhood of $n$ great circles on $\mathbb{S}^2$. We are interested in how much these areas have to overlap and prove the sharp bounds $$ \sum_{i, j = 1 \atop i \neq j}^{n}{|C_i \cap C_j|^s} \gtrsim_s \begin{cases} n^{2 - 2s} \qquad &\mbox{if}~0 \leq s < 2 \\ n^{-2} \log{n} \qquad &\mbox{if}~s = 2\\ n^{1- 3s/2} \qquad &\mbox{if}~s > 2. \end{cases} .$$ For $s=1$ there are arrangements for which the sum of mutual overlap is uniformly bounded (for the analogous problem in $\mathbb{R}^2$ the lower bound is $\gtrsim \log{n}$) and there are strong connections to minimal energy configurations of $n$ charged electrons on $\mathbb{S}^2$ (the J. J. Thomson problem).

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A Rigidity Phenomenon for the Hardy-Littlewood Maximal Function

The Hardy-Littlewood maximal function $\mathcal{M}$ and the trigonometric function $\sin{x}$ are two central objects in harmonic analysis. We prove that $\mathcal{M}$ characterizes $\sin{x}$ in the following way: let $f \in C^α(\mathbb{R}, \mathbb{R})$ be a periodic function and $α> 1/2$. If there exists a real number $0 < γ< \infty$ such that the averaging operator $$ (A_xf)(r) = \frac{1}{2r}\int_{x-r}^{x+r}{f(z)dz}$$ has a critical point in $r = γ$ for every $x \in \mathbb{R}$, then $$f(x) = a+b\sin{(cx + d)} \qquad \mbox{for some}~a,b,c,d \in \mathbb{R}.$$ This statement can be used to derive a characterization of trigonometric functions as those nonconstant functions for which the computation of the maximal function $\mathcal{M}$ is as simple as possible. The proof uses the Lindemann-Weierstrass theorem from transcendental number theory.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Localization of Quantum States and Landscape Functions

Eigenfunctions in inhomogeneous media can have strong localization properties. Filoche \& Mayboroda showed that the function $u$ solving $(-Δ+ V)u = 1$ controls the behavior of eigenfunctions $(-Δ+ V)ϕ= λϕ$ via the inequality $$|ϕ(x)| \leq λu(x) \|ϕ\|_{L^{\infty}}.$$ This inequality has proven to be remarkably effective in predicting localization and recently Arnold, David, Jerison, Mayboroda \& Filoche connected $1/u$ to decay properties of eigenfunctions. We aim to clarify properties of the landscape: the main ingredient is a localized variation estimate obtained from writing $ϕ(x)$ as an average over Brownian motion $ω(\cdot)$ in started in $x$ $$ϕ(x) = \mathbb{E}_{x}\left(ϕ(ω(t)) e^{λt-\int_{0}^{t}{V(ω(z))dz}} \right).$$ This variation estimate will guarantee that $ϕ$ has to change at least by a factor of 2 in a small ball, which implicitly creates a landscape whose relationship with $1/u$ we discuss.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Lower bounds for the truncated Hilbert transform

Given two intervals $I, J \subset \mathbb{R}$, we ask whether it is possible to reconstruct a real-valued function $f \in L^2(I)$ from knowing its Hilbert transform $Hf$ on $J$. When neither interval is fully contained in the other, this problem has a unique answer (the nullspace is trivial) but is severely ill-posed. We isolate the difficulty and show that by restricting $f$ to functions with controlled total variation, reconstruction becomes stable. In particular, for functions $f \in H^1(I)$, we show that $$ \|Hf\|_{L^2(J)} \geq c_1 \exp{\left(-c_2 \frac{\|f_x\|_{L^2(I)}}{\|f\|_{L^2(I)}}\right)} \| f \|_{L^2(I)} ,$$ for some constants $c_1, c_2 > 0$ depending only on $I, J$. This inequality is sharp, but we conjecture that $\|f_x\|_{L^2(I)}$ can be replaced by $\|f_x\|_{L^1(I)}$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Lower bounds on nodal sets of eigenfunctions via the heat flow

We study the size of nodal sets of Laplacian eigenfunctions on compact Riemannian manifolds without boundary and recover the currently optimal lower bound by comparing the heat flow of the eigenfunction with that of an artifically constructed diffusion process. The same method should apply to a number of other questions; for example, we prove a sharp result saying that a nodal domain cannot be entirely contained in a small neighbourhood of a 'reasonably flat' surface. We expect the arising concepts to have more connections to classical theory and pose some conjectures in that direction.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On the Discrepancy of Jittered Sampling

We study the discrepancy of jittered sampling sets: such a set $\mathcal{P} \subset [0,1]^d$ is generated for fixed $m \in \mathbb{N}$ by partitioning $[0,1]^d$ into $m^d$ axis aligned cubes of equal measure and placing a random point inside each of the $N = m^d$ cubes. We prove that, for $N$ sufficiently large, $$ \frac{1}{10}\frac{d}{N^{\frac{1}{2} + \frac{1}{2d}}} \leq \mathbb{E} D_N^*(\mathcal{P}) \leq \frac{\sqrt{d} (\log{N})^{\frac{1}{2}}}{N^{\frac{1}{2} + \frac{1}{2d}}},$$ where the upper bound with an unspecified constant $C_d$ was proven earlier by Beck. Our proof makes crucial use of the sharp Dvoretzky-Kiefer-Wolfowitz inequality and a suitably taylored Bernstein inequality; we have reasons to believe that the upper bound has the sharp scaling in $N$. Additional heuristics suggest that jittered sampling should be able to improve known bounds on the inverse of the star-discrepancy in the regime $N \gtrsim d^d$. We also prove a partition principle showing that every partition of $[0,1]^d$ combined with a jittered sampling construction gives rise to a set whose expected squared $L^2-$discrepancy is smaller than that of purely random points.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Prescribing the nodal set of the first eigenfunction in each conformal class

We consider the problem of prescribing the nodal set of the first nontrivial eigenfunction of the Laplacian in a conformal class. Our main result is that, given a separating closed hypersurface $Σ$ in a compact Riemannian manifold $(M,g_0)$ of dimension $d \geq 3$, there is a metric $g$ on $M$ conformally equivalent to $g_0$ and with the same volume such that the nodal set of its first nontrivial eigenfunction is a $C^0$-small deformation of $Σ$ (i.e., $Φ(Σ)$ with $Φ: M \to M$ a diffeomorphism arbitrarily close to the identity in the $C^0$ norm).

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Sharp L^1 Poincare inequalities correspond to optimal hypersurface cuts

Let $Ω\subset \mathbb{R}^n$ be a convex. If $u: Ω\rightarrow \mathbb{R}$ has mean 0, then we have the classical Poincaré inequality $$ \|u \|_{L^p} \leq c_p \mbox{diam}(Ω) \| \nabla u \|_{L^p}$$ with sharp constants $c_2 = 1/π$ (Payne \& Weinberger, 1960) and $c_1 = 1/2$ (Acosta \& Duran, 2005) independent of the dimension. The sharp constants $c_p$ for $1 < p < 2$ have recently been found by Ferone, Nitsch \& Trombetti (2012). The purpose of this short paper is to prove a much stronger inequality in the endpoint $L^1$: we combine results of Cianchi and Kannan, Lovász \& Simonovits to show that $$\left\|u\right\|_{L^{1}(Ω)} \leq \frac{2}{\log{2}} M_{}(Ω) \left\|\nabla u\right\|_{L^{1}(Ω)}$$ where $M_{}(Ω)$ is the average distance between a point in $Ω$ and the center of gravity of $Ω$. If $Ω$ is a simplex, this yields an improvement by a factor of $\sim \sqrt{n}$ in $n$ dimensions. By interpolation, this implies that that for every convex $Ω\subset \mathbb{R}^n$ and every $u:Ω\rightarrow \mathbb{R}$ with mean 0 $$ \left\|u\right\|_{L^{p}(Ω)}\leq \left(\frac{2}{\log{2}} M_{}(Ω) \right)^{\frac{1}{p}}\mbox{diam}(Ω)^{1-\frac{1}{p}}\left\|\nabla u\right\|_{L^{p}(Ω)}. $$

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A filtering technique for Markov chains with applications to spectral embedding

Spectral methods have proven to be a highly effective tool in understanding the intrinsic geometry of a high-dimensional data set $\left\{x_i \right\}_{i=1}^{n} \subset \mathbb{R}^d$. The key ingredient is the construction of a Markov chain on the set, where transition probabilities depend on the distance between elements, for example where for every $1 \leq j \leq n$ the probability of going from $x_j$ to $x_i$ is proportional to $$ p_{ij} \sim \exp \left( -\frac{1}{\varepsilon}\|x_i -x_j\|^2_{\ell^2(\mathbb{R}^d)}\right) \qquad \mbox{where}~\varepsilon>0~\mbox{is a free parameter}.$$ We propose a method which increases the self-consistency of such Markov chains before spectral methods are applied. Instead of directly using a Markov transition matrix $P$, we set $p_{ii} = 0$ and rescale, thereby obtaining a transition matrix $P^*$ modeling a non-lazy random walk. We then create a new transition matrix $Q = (q_{ij})_{i,j=1}^{n}$ by demanding that for fixed $j$ the quantity $q_{ij}$ be proportional to $$ q_{ij} \sim \min((P^*)_{ij}, ((P^*)^2)_{ij}, \dots, ((P^*)^k)_{ij}) \qquad \mbox{where usually}~ k=2.$$ We consider several classical data sets, show that this simple method can increase the efficiency of spectral methods and prove that it can correct randomly introduced errors in the kernel.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A Remark on Disk Packings and Numerical Integration of Harmonic Functions

We are interested in the following problem: given an open, bounded domain $Ω\subset \mathbb{R}^2$, what is the largest constant $α= α(Ω) > 0$ such that there exist an infinite sequence of disks $B_1, B_2, \dots, B_N, \dots \subset \mathbb{R}^2$ and a sequence $(n_i)$ with $n_i \in \left\{1,2\right\}$ such that $$ \sup_{N \in \mathbb{N}}{N^α\left\| χ_Ω - \sum_{i=1}^{N}{(-1)^{n_i}χ_{B_i}}\right\|_{L^1(\mathbb{R}^2)}} < \infty,$$ where $χ$ denotes the characteristic function? We prove that certain (somewhat peculiar) domains $Ω\subset \mathbb{R}^2$ satisfy the property with $α= 0.53$. For these domains there exists a sequence of points $(x_i)_{i=1}^{\infty}$ in $Ω$ with weights $(a_i)_{i=1}^{\infty}$ such that for all harmonic functions $u:\mathbb{R}^2 \rightarrow \mathbb{R}$ $$ \left|\int_Ω{u(x)dx} - \sum_{i=1}^{N}{a_i u(x_i)}\right| \leq C_Ω\frac{\|u\|_{L^{\infty}(Ω)}}{N^{0.53}},$$ where $C_Ω$ depends only on $Ω$. This gives a Quasi-Monte-Carlo method for harmonic functions which improves on the probabilistic Monte-Carlo bound $\|u\|_{L^{2}(Ω)}/N^{0.5}$ \textit{without} introducing a dependence on the total variation. We do not know which decay rates are optimal.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

An uncertainty principle on compact manifolds

Breitenberger's uncertainty principle on the torus $\mathbb{T}$ and its higher-dimensional analogue on $\mathbb{S}^{d-1}$ are well understood. We give describe an entire family of uncertainty principles on compact manifolds $(M,g)$, which includes the classical Heisenberg-Weyl uncertainty principle (for $M=B(0,1) \subset \mathbb{R}^d$ the unit ball with the flat metric) and the Goh-Goodman uncertainty principle (for $M=\mathbb{S}^{d-1}$ with the canonical metric) as special cases. This raises a new geometric problem related to small-curvature low-distortion embeddings: given a function $f:M \rightarrow \mathbb{R}$, which uncertainty principle in our family yields the best result? We give a (far from optimal) answer for the torus, discuss disconnected manifolds and state a variety of other open problems.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Convolution Estimates for Singular Measures and Some Global Nonlinear Brascamp-Lieb Inequalities

We give a $L^2\times L^2 \rightarrow L^2$ convolution estimate for singular measures supported on transversal hypersurfaces in $\mathbb{R}^n$, which improves earlier results of Bejenaru, Herr & Tataru as well as Bejenaru & Herr. The arising quantities are relevant in the study of the validity of bilinear estimates for dispersive partial differential equations. We also prove a class of global, nonlinear Brascamp-Lieb inequalities with explicit constants in the same spirit.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Local Extrema in Quantum Chaos

We numerically investigate the distribution of extrema of 'chaotic' Laplacian eigenfunctions on two-dimensional manifolds. Our contribution is two-fold: (a) we count extrema on grid graphs with a small number of randomly added edges and show the behavior to coincide with the 1957 prediction of Longuet-Higgins for the continuous case and (b) compute the regularity of their spatial distribution using \textit{discrepancy}, which is a classical measure from the theory of Monte Carlo integration. The first part suggests that grid graphs with randomly added edges should behave like two-dimensional surfaces with ergodic geodesic flow; in the second part we show that the extrema are more regularly distributed in space than the grid $\mathbb{Z}^2$.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

New Bounds for the Traveling Salesman Constant

Let $X_1, X_2, \dots, X_n$ be independent and uniformly distributed random variables in the unit square $[0,1]^2$ and let $L(X_1, \dots, X_n)$ be the length of the shortest traveling salesman path through these points. In 1959, Beardwood, Halton $\&$ Hammersley proved the existence of a universal constant $β$ such that $$ \lim_{n \rightarrow \infty}{n^{-1/2}L(X_1, \dots, X_n)} = β\qquad \mbox{almost surely.}$$ The best bounds for $β$ are still the ones originally established by Beardwood, Halton $\&$ Hammersley $0.625 \leq β\leq 0.922$. We slightly improve both upper and lower bounds.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

A geometric uncertainty principle with an application to Pleijel's estimate

Consider partitions of an open, bounded domain in $\mathbb{R}^n$. Then an average element of the partition has either its Fraenkel asymmetry or its deviation from the smallest element in the partition bounded away from 0 by a universal constant. As an application, we give an (unspecified) improvement of Pleijel's estimate on the number of nodal domains of a Laplacian eigenfunction similar to recent work of Bourgain and improve a bound coming from spectral partition problems.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Dispersion dynamics for the defocusing generalized Korteweg-de Vries equation

We study dispersion for the defocusing gKdV equation. It is expected that it is not possible for the bulk of the $L^2-$mass to concentrate in a small interval for a long time. We study a variance-type functional exploiting Tao's monotonicity formula in the spirit of earlier work by Tao as well as Kwon & Shao and quantify its growth in terms of sublevel estimates.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Minimal Periods for Ordinary Differential Equations in Strictly Convex Banach Spaces and Explicit Bounds for some l^p-Spaces

Let x(t) be a non-constant T-periodic solution to the ordinary differential equation x'= f(x) in a Banach space X where f is assumed to be Lipschitz continuous with constant L. Then there exists a constant c such that T L >= c, with c only depending on X. It is known that c >= 6 in any Banach space and that c = 2π in any Hilbert space, but whereas the bound of c = 2 pi is sharp in any Hilbert space, there exists only one known example of a Banach space such that c = 6 is optimal. In this paper, we show that the inequality is in fact strict in any strictly convex Banach space. Moreover, we improve the lower bound for l^p(R^n) and L^p(M, μ) for a range of p close to p = 2 by using a form of Wirtinger's inequality for functions in W^{1,p}([0, T ], L^p(M, μ)).

0 citations0 reviewsNo code linkedOpen access