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 t
o $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.
We consider linear systems $Ax = b$ where $A in mathbb{R}^{m times n}$ consists of normalized rows, $|a_i|_{ell^2} = 1$, and where up to $beta m$ entries of $b$ have been corrupted (possibly by arbitrarily large numbers). Haddock, Needell, Rebrova an
d Swartworth propose a quantile-based Random Kaczmarz method and show that for certain random matrices $A$ it converges with high likelihood to the true solution. We prove a deterministic version by constructing, for any matrix $A$, a number $beta_A$ such that there is convergence for all perturbations with $beta < beta_A$. Assuming a random matrix heuristic, this proves convergence for tall Gaussian matrices with up to $sim 0.5%$ corruption (a number that can likely be improved).
Let $D subset mathbb{R}^d$ be a bounded, connected domain with smooth boundary and let $-Delta u = mu_1 u$ be the first nontrivial eigenfunction of the Laplace operator with Neumann boundary conditions. We prove $$ |u|_{L^{infty}(D)} leq 60 cdot |u|_
{L^{infty}(partial D)}.$$ This shows that the Hot Spots Conjecture cannot fail by an arbitrary factor. An example of Kleefeld shows that the optimal constant is at least $1 + 10^{-3}$.
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 sho
rt note is to point out an interesting phenomenon: if $phi_1, phi_2$ are delocalized eigenvectors of $L$ corresponding to large eigenvalues, then their (pointwise) product $phi_1 cdot phi_2$ is smooth (in the sense of small Dirichlet energy): highly oscillatory functions have largely matching oscillation patterns.
We study the MaxCut problem for graphs $G=(V,E)$. The problem is NP-hard, there are two main approximation algorithms with theoretical guarantees: (1) the Goemans & Williamson algorithm uses semi-definite programming to provide a 0.878MaxCut approxim
ation (which, if the Unique Games Conjecture is true, is the best that can be done in polynomial time) and (2) Trevisan proposed an algorithm using spectral graph theory from which a 0.614MaxCut approximation can be obtained. We discuss a new approach using a specific quadratic program and prove that its solution can be used to obtain at least a 0.502MaxCut approximation. The algorithm seems to perform well in practice.
We introduce a graph decomposition which exists for all simple, connected graphs $G=(V,E)$. The decomposition $V = A cup B cup C$ is such that each vertex in $A$ has more neighbors in $B$ than in $A$ and vice versa. $C$ is `balanced: each $v in C$ ha
s the same number of neighbours in $A$ and $B$. These decompositions arise naturally from the behavior of an associated dynamical system (`Randomized Rounding) on $(mathbb{S}^1)^{|V|}$. Connections to judicious partitions and the textsc{MaxCut} problem (in particular the Burer-Monteiro-Zhang heuristic) are being discussed.
We consider solutions of the nonlinear Poisson equation $$-Delta u = f(u)$$ in convex domains $Omega subset mathbb{R}^2$ with Dirichlet boundary conditions on $partial Omega$. Solutions of such equations are not usually concave. We show (for monotoni
cally increasing concave $f$) that if the curvature $kappa$ of the boundary is not too large, then $u$ is concave. For example, if $Omega subset mathbb{R}^2$ has measure $|Omega| = pi$ and $kappa leq sqrt{2}$, then the solution of $-Delta u = 1$ is concave. Or, if $|Omega| = pi$ and $kappa leq 1.3$, then the solution of $-Delta u = sqrt{1+u}$ is concave. It would be interesting to understand under which conditions (on the domain $Omega$ and the nonlinearity $f$) are solutions of the Poisson equation concave once the domain is `sufficiently round.
We study the problem of exact support recovery based on noisy observations and present Refined Least Squares (RLS). Given a set of noisy measurement $$ myvec{y} = myvec{X}myvec{theta}^* + myvec{omega},$$ and $myvec{X} in mathbb{R}^{N times D}$ which
is a (known) Gaussian matrix and $myvec{omega} in mathbb{R}^N$ is an (unknown) Gaussian noise vector, our goal is to recover the support of the (unknown) sparse vector $myvec{theta}^* in left{-1,0,1right}^D$. To recover the support of the $myvec{theta}^*$ we use an average of multiple least squares solutions, each computed based on a subset of the full set of equations. The support is estimated by identifying the most significant coefficients of the average least squares solution. We demonstrate that in a wide variety of settings our method outperforms state-of-the-art support recovery algorithms.
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.
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{theta_1, theta_2, dots, theta_nright} subset [0, 2pi]$, minima of the energy $$ f
(theta_1, dots, theta_n) = sum_{i,j=1}^{n} a_{ij} cos{(theta_i - theta_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{(theta_i - theta_j)}$ with an explicit function $g_{varepsilon}(theta_i - theta_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.
