arXiv research

This paper speeds up spectral clustering for large graphs by dilating their eigenspectrum.

We develop an improved bound for the approximation error of the Nyström method under the assumption that there is a large eigengap in the spectrum of kernel matrix. This is based on the empirical observation that the eigengap has a significant impact on the approximation error of the Nyström method. Our approach is bas…

We consider the problem of principal component analysis (PCA) in a streaming stochastic setting, where our goal is to find a direction of approximate maximal variance, based on a stream of i.i.d. data points in $\reals^d$. A simple and computationally cheap algorithm for this is stochastic gradient descent (SGD), which…

A new GCN variant tackles large eigengaps in dense graphs and hypergraphs.

We identify spectral conditions for reliable neural probe interpretation.

Spectral clustering algorithms typically require a priori selection of input parameters such as the number of clusters, a scaling parameter for the affinity measure, or ranges of these values for parameter tuning. Despite efforts for automating the process of spectral clustering, the task of grouping data in multi-scal…

We study $k$-GenEV, the problem of finding the top $k$ generalized eigenvectors, and $k$-CCA, the problem of finding the top $k$ vectors in canonical-correlation analysis. We propose algorithms $\mathtt{LazyEV}$ and $\mathtt{LazyCCA}$ to solve the two problems with running times linearly dependent on the input size and…

The study of which mapping class group elements can be realized as affine automorphisms of dilation surfaces.

We find the minimum dilatation of pseudo-Anosov braids with many strands.

Closed geodesics densely cover a circle in dilation surfaces.

The dilatation of a pseudo-Anosov braid is a conjugacy invariant. In this paper, we study the dilatation of a special family of pseudo-Anosov braids. We prove an inductive formula to compute their dilatation, a monotonicity and an asymptotic behavior of the dilatation for this family of braids. We also give an example …

This paper describes a family of pseudo-Anosov braids with small dilatation. The smallest dilatations occurring for braids with 3, 4 and 5 strands appear in this family. A pseudo-Anosov braid with 2g+1 strands determines a hyperelliptic mapping class with the same dilatation on a genus-g surface. Penner showed that log…

Horizon saddle connections imply dense hyperbolic geodesics on dilation surfaces.

Vanilla convolutional neural networks are known to provide superior performance not only in image recognition tasks but also in natural language processing and time series analysis. One of the strengths of convolutional layers is the ability to learn features about spatial relations in the input domain using various pa…

For any nonorientable closed surface, we determine the minimal dilatation among pseudo-Anosov mapping classes arising from Penner's construction. We deduce that the sequence of minimal Penner dilatations has exactly two accumulation points, in contrast to the case of orientable surfaces where there is only one accumula…

In this paper we study the minimum dilatation pseudo-Anosov mapping classes coming from fibrations over the circle of a single 3-manifold, the mapping torus for the "simplest pseudo-Anosov braid". The dilatations that arise include the minimum dilatations for orientable mapping classes for genus g=2,3,4,5,8 as well as …

The paper explores inequalities for strongly-convex sets in weighted Riemannian manifolds.

Maximal dilatation found on nonorientable surfaces.

Constructs moduli spaces for complex affine and dilation surfaces.

Based on the notion of dilatation structure arXiv:math/0608536, we give an intrinsic treatment to sub-riemannian geometry, started in the paper arXiv:0706.3644 . Here we prove that regular sub-riemannian manifolds admit dilatation structures. From the existence of normal frames proved by Bellaiche we deduce the rest of…

We study streaming principal component analysis (PCA), that is to find, in $O(dk)$ space, the top $k$ eigenvectors of a $d\times d$ hidden matrix $\bf Σ$ with online vectors drawn from covariance matrix $\bf Σ$. We provide $\textit{global}$ convergence for Oja's algorithm which is popularly used in practice but lacks t…

We study normed groupoids with dilations and their induced deformations.

Dilation surfaces are generalizations of translation surfaces where the geometric structure is modelled on the complex plane up to affine maps whose linear part is real. They are the geometric framework to study suspensions of affine interval exchange maps. However, though the $SL(2,\mathbb{R})$-action is ergodic in co…

We find the minimum dilatation of pseudo-Anosov homeomorphisms that stabilize an orientable foliation on surfaces of genus three, four, or five, and provide a lower bound for genus six to eight. Our technique also simplifies Cho and Ham's proof of the least dilatation of pseudo-Anosov homeomorphisms on a genus two surf…

Computes minimal dilatation for Thurston maps on surfaces.

We exhibit low-dilatation families of surface homeomorphisms among monodromies of Lorenz knots.

This paper concerns a family of pseudo-Anosov braids with dilatations arbitrarily close to one. The associated graph maps and train tracks have stable "star-like" shapes, and the characteristic polynomials of their transition matrices form Salem-Boyd sequences. These examples show that the logarithms of least dilatatio…

The Hopf invariant is linked to null-homotopy properties of maps.

We consider the quasiconformal dilatation of projective transformations of the real projective plane. For non-affine transformations, the contour lines of dilatation form a hyperbolic pencil of circles, and these are the only circles that are mapped to circles. We apply this result to analyze the dilatation of the circ…

This note gives a brief survey of the minimum dilatation problem for pseudo-Anosov mapping classes, and the first explicit train track description of an infinite family of pseudo-Anosov mapping classes with orientable stable foliations and the conjectural minimum dilatation for closed surfaces of even genus $g \ge 2$.

A relation between the dilatation of pseudo-Anosov braids and fixed point theory was studied by Ivanov. In this paper we reveal a new relationship between the above two subjects by showing a formula for the dilatation of pseudo-Anosov braids by means of the representations of braid groups due to B. Jiang and H. Zheng.

The study improves bounds on pseudo-Anosov maps and certifies minimum and accumulation points of normalized dilatations.

For all orientable closed surfaces, we determine the minimal dilatation among mapping classes arising from Penner's construction. We also discuss generalisations to surfaces with punctures.

We introduce length dilatation structures on metric spaces, tempered dilatation structures and coherent projections and explore the relations between these objects and the Radon-Nikodym property and Gamma-convergence of length functionals. Then we show that the main properties of sub-riemannian spaces can be obtained f…

We study the minimal dilatation of pseudo-Anosov pure surface braids and provide upper and lower bounds as a function of genus and the number of punctures. For a fixed number of punctures, these bounds tend to infinity as the genus does. We also bound the dilatation of pseudo-Anosov pure surface braids away from zero a…

It has been known since 1981 that if one fixes an orientable surface $S$ of genus $g$, then there is a real number $λ_{min,g} > 1$ that is the dilatation of a pA diffeomorphism of $S$, and every other pA diffeomorphism of $S$ has dilatation $\geq λ_{min,g}$. We will show how a little-known theorem about digraphs gives …

We construct homotopically non-trivial maps from S^m to S^n with arbitrarily small 3-dilation for certain pairs (m,n). The simplest example is m=4, n=3. Other examples include arbitrarily large values of m and n. We show that a homotopy class in pi_7(S^4) can be represented by maps with arbitrarily small 4-dilation if …

This text is an introduction to dilation surfaces. We attempt to expose some geometric and dynamical aspects of the subject: moduli spaces, directional foliations and the Teichmüller flow.

The paper calculates Veech groups for triangulable structures on the sphere.

It has been known since 1981 that if one fixes an orientable surface $S$ of genus $g$, then there is a real number $λ_{min,g} > 1$ that is the dilatation of a pA diffeomorphism of $S$, and every other pA diffeomorphism of $S$ has dilatation $\geq λ_{min,g}$. We will show how a little-known theorem about digraphs gives …

We study the coarse geometry of the moduli space of dilation tori with two singularities and the dynamical properties of the action of the Teichmuller flow on this moduli space. This leads to a proof that the vertical foliation of a dilation torus is almost always Morse-Smale. As a corollary, we get that the generic pi…

Constructing transitive nilpotent Lie algebras from dilations and analyzing their prolongations.

Multivariate time series classification is a high value and well-known problem in machine learning community. Feature extraction is a main step in classification tasks. Traditional approaches employ hand-crafted features for classification while convolutional neural networks (CNN) are able to extract features automatic…

The study explores dilating set properties across Euclidean and hyperbolic geometries.

Answering a question of Farb-Leininger-Margalit, we give explicit lower bounds for the dilatations of pseudo-Anosov mapping classes lying in the kth term of the Johnson filtration of the mapping class group.

Study Agol cycles on 2-punctured torus and 5-punctured sphere, finding new dilatation formula.

We prove a new lower bound for the dilatation of an arbitrary pseudo-Anosov map on a surface of genus g with n punctures. Our bound improves the former super-exponential dependence on the genus by a polynomial dependence.

A filling curve $γ$ on a based surface $S$ determines a pseudo-Anosov homeomorphism $P(γ)$ of $S$ via the process of "point-pushing along $γ$." We consider the relationship between the self-intersection number $i(γ)$ of $γ$ and the dilatation of $P(γ)$; our main result is that the dilatation is bounded between $(i(γ)+1…