Edge Expansion and Spectral Gap of Nonnegative Matrices
The classic graphical Cheeger inequalities state that if $M$ is an $n\times n$ \emph{symmetric} doubly stochastic matrix, then $\frac{1-\lambda_{2}(M)}{2}\leq\phi(M)\leq\sqrt{2\cdot(1-\lambda_{2}(M))}$ where $\phi(M)=\min_{S\subseteq[n],|S|\leq n/2}\left(\frac{1}{|S|}\sum_{i\in S,j\not\in S}M_{i,j}\right)$ is the edge expansion of $M$, and $\lambda_{2}(M)$ is the second largest eigenvalue of $M$. We study the relationship between $\phi(A)$ and the spectral gap $1-\re\lambda_{2}(A)$ for \emph{any} doubly stochastic matrix $A$ (not necessarily symmetric), where $\lambda_{2}(A)$ is a nontrivial eigenvalue of $A$ with maximum real part. Fiedler showed that the upper bound on $\phi(A)$ is unaffected, i.e., $\phi(A)\leq\sqrt{2\cdot(1-\re\lambda_{2}(A))}$. With regards to the lower bound on $\phi(A)$, there are known constructions with $\phi(A)\in\Theta\left(\frac{1-\re\lambda_{2}(A)}{\log n}\right),$ indicating that at least a mild dependence on $n$ is necessary to lower bound $\phi(A)$. In our first result, we provide an \emph{exponentially} better construction of $n\times n$ doubly stochastic matrices $A_{n}$, for which $\phi(A_{n})\leq\frac{1-\re\lambda_{2}(A_{n})}{\sqrt{n}}.$ In fact, \emph{all} nontrivial eigenvalues of our matrices are $0$, even though the matrices are highly \emph{nonexpanding}. We further show that this bound is in the correct range (up to the exponent of $n$), by showing that for any doubly stochastic matrix $A$, $\phi(A)\geq\frac{1-\re\lambda_{2}(A)}{35\cdot n}.$ As a consequence, unlike the symmetric case, there is a (necessary) loss of a factor of $n^{\alpha}$ for $\frac{1}{2}\leq\alpha\leq1$ in lower bounding $\phi$ by the spectral gap in the nonsymmetric setting. Our second result extends these bounds to general matrices $R$ with nonnegative entries, to obtain a more »
Authors:
;
Award ID(s):
Publication Date:
NSF-PAR ID:
10190072
Journal Name:
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms
National Science Foundation
##### More Like this
1. The cumulative empirical spectral measure (CESM) $\Phi[\mathbf{A}] : \mathbb{R} \to [0,1]$ of a $n\times n$ symmetric matrix $\mathbf{A}$ is defined as the fraction of eigenvalues of $\mathbf{A}$ less than a given threshold, i.e., $\Phi[\mathbf{A}](x) := \sum_{i=1}^{n} \frac{1}{n} {\large\unicode{x1D7D9}}[ \lambda_i[\mathbf{A}]\leq x]$. Spectral sums $\operatorname{tr}(f[\mathbf{A}])$ can be computed as the Riemann–Stieltjes integral of $f$ against $\Phi[\mathbf{A}]$, so the task of estimating CESM arises frequently in a number of applications, including machine learning. We present an error analysis for stochastic Lanczos quadrature (SLQ). We show that SLQ obtains an approximation to the CESM within a Wasserstein distance of $t \: | \lambda_{\text{max}}[\mathbf{A}] - \lambda_{\text{min}}[\mathbf{A}] |$ with probability at least $1-\eta$, by applying the Lanczos algorithm for $\lceil 12 t^{-1} + \frac{1}{2} \rceil$ iterations to $\lceil 4 ( n+2 )^{-1}t^{-2} \ln(2n\eta^{-1}) \rceil$ vectors sampled independently and uniformly from the unit sphere. We additionally provide (matrix-dependent) a posteriori error bounds for the Wasserstein and Kolmogorov–Smirnov distances between the output of this algorithm and the true CESM. The quality of our bounds is demonstrated using numerical experiments.
2. Abstract

Given a sequence $\{Z_d\}_{d\in \mathbb{N}}$ of smooth and compact hypersurfaces in ${\mathbb{R}}^{n-1}$, we prove that (up to extracting subsequences) there exists a regular definable hypersurface $\Gamma \subset {\mathbb{R}}\textrm{P}^n$ such that each manifold $Z_d$ is diffeomorphic to a component of the zero set on $\Gamma$ of some polynomial of degree $d$. (This is in sharp contrast with the case when $\Gamma$ is semialgebraic, where for example the homological complexity of the zero set of a polynomial $p$ on $\Gamma$ is bounded by a polynomial in $\deg (p)$.) More precisely, given the above sequence of hypersurfaces, we construct a regular, compact, semianalytic hypersurface $\Gamma \subset {\mathbb{R}}\textrm{P}^{n}$ containing a subset $D$ homeomorphic to a disk, and a family of polynomials $\{p_m\}_{m\in \mathbb{N}}$ of degree $\deg (p_m)=d_m$ such that $(D, Z(p_m)\cap D)\sim ({\mathbb{R}}^{n-1}, Z_{d_m}),$ i.e. the zero set of $p_m$ in $D$ is isotopic to $Z_{d_m}$ in ${\mathbb{R}}^{n-1}$. This says that, up to extracting subsequences, the intersection of $\Gamma$ with a hypersurface of degree $d$ can be as complicated as we want. We call these ‘pathological examples’. In particular, we show that for every $0 \leq k \leq n-2$ and every sequence of natural numbers $a=\{a_d\}_{d\in \mathbb{N}}$ there is a regular, compact semianalyticmore »

3. The densest subgraph problem in a graph (\dsg), in the simplest form, is the following. Given an undirected graph $G=(V,E)$ find a subset $S \subseteq V$ of vertices that maximizes the ratio $|E(S)|/|S|$ where $E(S)$ is the set of edges with both endpoints in $S$. \dsg and several of its variants are well-studied in theory and practice and have many applications in data mining and network analysis. In this paper we study fast algorithms and structural aspects of \dsg via the lens of \emph{supermodularity}. For this we consider the densest supermodular subset problem (\dssp): given a non-negative supermodular function $f: 2^V \rightarrow \mathbb{R}_+$, maximize $f(S)/|S|$. For \dsg we describe a simple flow-based algorithm that outputs a $(1-\eps)$-approximation in deterministic $\tilde{O}(m/\eps)$ time where $m$ is the number of edges. Our algorithm is the first to have a near-linear dependence on $m$ and $1/\eps$ and improves previous methods based on an LP relaxation. It generalizes to hypergraphs, and also yields a faster algorithm for directed \dsg. Greedy peeling algorithms have been very popular for \dsg and several variants due to their efficiency, empirical performance, and worst-case approximation guarantees. We describe a simple peeling algorithm for \dssp and analyze its approximation guarantee inmore »
4. Abstract

In this paper, we consider discrete Schrödinger operators of the form, $$\begin{equation*} (Hu)(n) = u({n+1})+u({n-1})+V(n)u(n). \end{equation*}$$We view $H$ as a perturbation of the free operator $H_0$, where $(H_0u)(n)= u({n+1})+u({n-1})$. For $H_0$ (no perturbation), $\sigma _{\textrm{ess}}(H_0)=\sigma _{\textrm{ac}}(H)=[-2,2]$ and $H_0$ does not have eigenvalues embedded into $(-2,2)$. It is an interesting and important problem to identify the perturbation such that the operator $H_0+V$ has one eigenvalue (finitely many eigenvalues or countable eigenvalues) embedded into $(-2,2)$. We introduce the almost sign type potentials and develop the Prüfer transformation to address this problem, which leads to the following five results. 1: We obtain the sharp spectral transition for the existence of irrational type eigenvalues or rational type eigenvalues with even denominators.2: Suppose $\limsup _{n\to \infty } n|V(n)|=a<\infty .$ We obtain a lower/upper bound of $a$ such that $H_0+V$ has one rational type eigenvalue with odd denominator.3: We obtain the asymptotical behavior of embedded eigenvalues around the boundaries of $(-2,2)$.4: Given any finite set of points $\{ E_j\}_{j=1}^N$ in $(-2,2)$ with $0\notin \{ E_j\}_{j=1}^N+\{ E_j\}_{j=1}^N$, we construct the explicit potential $V(n)=\frac{O(1)}{1+|n|}$ such that $H=H_0+V$ has eigenvalues $\{ E_j\}_{j=1}^N$.5: Given any countable set of points $\{ E_j\}$ in $(-2,2)$ with $0\notin \{ E_j\}+\{ E_j\}$, andmore »

5. Abstract

Let $f(z) = \sum_{n=1}^\infty a_f(n)q^n$ be a holomorphic cuspidal newform with even integral weight $k\geq 2$, level N, trivial nebentypus and no complex multiplication. For all primes p, we may define $\theta_p\in [0,\pi]$ such that $a_f(p) = 2p^{(k-1)/2}\cos \theta_p$. The Sato–Tate conjecture states that the angles θp are equidistributed with respect to the probability measure $\mu_{\textrm{ST}}(I) = \frac{2}{\pi}\int_I \sin^2 \theta \; d\theta$, where $I\subseteq [0,\pi]$. Using recent results on the automorphy of symmetric power L-functions due to Newton and Thorne, we explicitly bound the error term in the Sato–Tate conjecture when f corresponds to an elliptic curve over $\mathbb{Q}$ of arbitrary conductor or when f has square-free level. In these cases, if $\pi_{f,I}(x) := \#\{p \leq x : p \nmid N, \theta_p\in I\}$ and $\pi(x) := \# \{p \leq x \}$, we prove the following bound: $$\left| \frac{\pi_{f,I}(x)}{\pi(x)} - \mu_{\textrm{ST}}(I)\right| \leq 58.1\frac{\log((k-1)N \log{x})}{\sqrt{\log{x}}} \qquad \text{for} \quad x \geq 3.$$ As an application, we give an explicit bound for the number of primes up to x that violate the Atkin–Serre conjecture for f.