skip to main content


Title: On the behavior of 1-Laplacian ratio cuts on nearly rectangular domains
Abstract

The $p$-Laplacian has attracted more and more attention in data analysis disciplines in the past decade. However, there is still a knowledge gap about its behavior, which limits its practical application. In this paper, we are interested in its iterative behavior in domains contained in two-dimensional Euclidean space. Given a connected set $\varOmega _0 \subset \mathbb{R}^2$, define a sequence of sets $(\varOmega _n)_{n=0}^{\infty }$ where $\varOmega _{n+1}$ is the subset of $\varOmega _n$ where the first eigenfunction of the (properly normalized) Neumann $p$-Laplacian $ -\varDelta ^{(p)} \phi = \lambda _1 |\phi |^{p-2} \phi $ is positive (or negative). For $p=1$, this is also referred to as the ratio cut of the domain. We conjecture that these sets converge to the set of rectangles with eccentricity bounded by 2 in the Gromov–Hausdorff distance as long as they have a certain distance to the boundary $\partial \varOmega _0$. We establish some aspects of this conjecture for $p=1$ where we prove that (1) the 1-Laplacian spectral cut of domains sufficiently close to rectangles is a circular arc that is closer to flat than the original domain (leading eventually to quadrilaterals) and (2) quadrilaterals close to a rectangle of aspect ratio $2$ stay close to quadrilaterals and move closer to rectangles in a suitable metric. We also discuss some numerical aspects and pose many open questions.

 
more » « less
Award ID(s):
1352353 1312874
NSF-PAR ID:
10205611
Author(s) / Creator(s):
 ;  ;  
Publisher / Repository:
Oxford University Press
Date Published:
Journal Name:
Information and Inference: A Journal of the IMA
ISSN:
2049-8772
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract

    It has been recently established in David and Mayboroda (Approximation of green functions and domains with uniformly rectifiable boundaries of all dimensions.arXiv:2010.09793) that on uniformly rectifiable sets the Green function is almost affine in the weak sense, and moreover, in some scenarios such Green function estimates are equivalent to the uniform rectifiability of a set. The present paper tackles a strong analogue of these results, starting with the “flagship degenerate operators on sets with lower dimensional boundaries. We consider the elliptic operators$$L_{\beta ,\gamma } =- {\text {div}}D^{d+1+\gamma -n} \nabla $$Lβ,γ=-divDd+1+γ-nassociated to a domain$$\Omega \subset {\mathbb {R}}^n$$ΩRnwith a uniformly rectifiable boundary$$\Gamma $$Γof dimension$$d < n-1$$d<n-1, the now usual distance to the boundary$$D = D_\beta $$D=Dβgiven by$$D_\beta (X)^{-\beta } = \int _{\Gamma } |X-y|^{-d-\beta } d\sigma (y)$$Dβ(X)-β=Γ|X-y|-d-βdσ(y)for$$X \in \Omega $$XΩ, where$$\beta >0$$β>0and$$\gamma \in (-1,1)$$γ(-1,1). In this paper we show that the Green functionGfor$$L_{\beta ,\gamma }$$Lβ,γ, with pole at infinity, is well approximated by multiples of$$D^{1-\gamma }$$D1-γ, in the sense that the function$$\big | D\nabla \big (\ln \big ( \frac{G}{D^{1-\gamma }} \big )\big )\big |^2$$|D(ln(GD1-γ))|2satisfies a Carleson measure estimate on$$\Omega $$Ω. We underline that the strong and the weak results are different in nature and, of course, at the level of the proofs: the latter extensively used compactness arguments, while the present paper relies on some intricate integration by parts and the properties of the “magical distance function from David et al. (Duke Math J, to appear).

     
    more » « less
  2. 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 in a fashion that unifies several existing results. Boob et al.\ \cite{bgpstww-20} developed an \emph{iterative} peeling algorithm for \dsg which appears to work very well in practice, and made a conjecture about its convergence to optimality. We affirmatively answer their conjecture, and in fact prove that a natural generalization of their algorithm converges to a $(1-\eps)$-approximation for \emph{any} supermodular function $f$; the key to our proof is to consider an LP formulation that is derived via the \Lovasz extension of a supermodular function. For \dsg the bound on the number of iterations we prove is $O(\frac{\Delta \ln |V|}{\lambda^*}\cdot \frac{1}{\eps^2})$ where $\Delta$ is the maximum degree and $\lambda^*$ is the optimum value. Our work suggests that iterative peeling can be an effective heuristic for several objectives considered in the literature. Finally, we show that the $2$-approximation for densest-at-least-$k$ subgraph \cite{ks-09} extends to the supermodular setting. We also give a unified analysis of the peeling algorithm for this problem, and via this analysis derive an approximation guarantee for a generalization of \dssp to maximize $f(S)/g(|S|)$ for a concave function $g$. 
    more » « less
  3. Abstract

    Let$$\phi $$ϕbe a positive map from the$$n\times n$$n×nmatrices$$\mathcal {M}_n$$Mnto the$$m\times m$$m×mmatrices$$\mathcal {M}_m$$Mm. It is known that$$\phi $$ϕis 2-positive if and only if for all$$K\in \mathcal {M}_n$$KMnand all strictly positive$$X\in \mathcal {M}_n$$XMn,$$\phi (K^*X^{-1}K) \geqslant \phi (K)^*\phi (X)^{-1}\phi (K)$$ϕ(KX-1K)ϕ(K)ϕ(X)-1ϕ(K). This inequality is not generally true if$$\phi $$ϕis merely a Schwarz map. We show that the corresponding tracial inequality$${{\,\textrm{Tr}\,}}[\phi (K^*X^{-1}K)] \geqslant {{\,\textrm{Tr}\,}}[\phi (K)^*\phi (X)^{-1}\phi (K)]$$Tr[ϕ(KX-1K)]Tr[ϕ(K)ϕ(X)-1ϕ(K)]holds for a wider class of positive maps that is specified here. We also comment on the connections of this inequality with various monotonicity statements that have found wide use in mathematical physics, and apply it, and a close relative, to obtain some new, definitive results.

     
    more » « less
  4. Tauman Kalai, Yael (Ed.)
    Over the last two decades, a significant line of work in theoretical algorithms has made progress in solving linear systems of the form 𝐋𝐱 = 𝐛, where 𝐋 is the Laplacian matrix of a weighted graph with weights w(i,j) > 0 on the edges. The solution 𝐱 of the linear system can be interpreted as the potentials of an electrical flow in which the resistance on edge (i,j) is 1/w(i,j). Kelner, Orrechia, Sidford, and Zhu [Kelner et al., 2013] give a combinatorial, near-linear time algorithm that maintains the Kirchoff Current Law, and gradually enforces the Kirchoff Potential Law by updating flows around cycles (cycle toggling). In this paper, we consider a dual version of the algorithm that maintains the Kirchoff Potential Law, and gradually enforces the Kirchoff Current Law by cut toggling: each iteration updates all potentials on one side of a fundamental cut of a spanning tree by the same amount. We prove that this dual algorithm also runs in a near-linear number of iterations. We show, however, that if we abstract cut toggling as a natural data structure problem, this problem can be reduced to the online vector-matrix-vector problem (OMv), which has been conjectured to be difficult for dynamic algorithms [Henzinger et al., 2015]. The conjecture implies that the data structure does not have an O(n^{1-ε}) time algorithm for any ε > 0, and thus a straightforward implementation of the cut-toggling algorithm requires essentially linear time per iteration. To circumvent the lower bound, we batch update steps, and perform them simultaneously instead of sequentially. An appropriate choice of batching leads to an Õ(m^{1.5}) time cut-toggling algorithm for solving Laplacian systems. Furthermore, we show that if we sparsify the graph and call our algorithm recursively on the Laplacian system implied by batching and sparsifying, we can reduce the running time to O(m^{1 + ε}) for any ε > 0. Thus, the dual cut-toggling algorithm can achieve (almost) the same running time as its primal cycle-toggling counterpart. 
    more » « less
  5. null (Ed.)
    A bstract Non-analyticity in co-moving momenta within the non-Gaussian bispectrum is a distinctive sign of on-shell particle production during inflation, presenting a unique opportunity for the “direct detection” of particles with masses as large as the inflationary Hubble scale ( H ). However, the strength of such non-analyticity ordinarily drops exponentially by a Boltzmann-like factor as masses exceed H . In this paper, we study an exception provided by a dimension-5 derivative coupling of the inflaton to heavy-particle currents, applying it specifically to the case of two real scalars. The operator has a “chemical potential” form, which harnesses the large kinetic energy scale of the inflaton, $$ {\overset{\cdot }{\phi}}_0^{1/2}\approx 60H $$ ϕ ⋅ 0 1 / 2 ≈ 60 H , to act as an efficient source of scalar particle production. Derivative couplings of inflaton ensure radiative stability of the slow-roll potential, which in turn maintains (approximate) scale-invariance of the inflationary correlations. We show that a signal not suffering Boltzmann suppression can be obtained in the bispectrum with strength f NL ∼ $$ \mathcal{O} $$ O (0 . 01–10) for an extended range of scalar masses $$ \lesssim {\overset{\cdot }{\phi}}_0^{1/2} $$ ≲ ϕ ⋅ 0 1 / 2 , potentially as high as 10 15 GeV, within the sensitivity of upcoming LSS and more futuristic 21-cm experiments. The mechanism does not invoke any particular fine-tuning of parameters or breakdown of perturbation-theoretic control. The leading contribution appears at tree-level , which makes the calculation analytically tractable and removes the loop-suppression as compared to earlier chemical potential studies of non-zero spins. The steady particle production allows us to infer the effective mass of the heavy particles and the chemical potential from the variation in bispectrum oscillations as a function of co-moving momenta. Our analysis sets the stage for generalization to heavy bosons with non-zero spin. 
    more » « less