arXiv research

A new bootstrapping method reduces key sizes and runtime in FHE.

ShuffleNet is a state-of-the-art light weight convolutional neural network architecture. Its basic operations include group, channel-wise convolution and channel shuffling. However, channel shuffling is manually designed empirically. Mathematically, shuffling is a multiplication by a permutation matrix. In this paper, …

To each dynamic equivalence of two control systems is associated an infinite permutation matrix. We investigate how such matrices are related to the existence of dynamic equivalences.

We found a way to code meanders and show they are idempotent.

Many matching, tracking, sorting, and ranking problems require probabilistic reasoning about possible permutations, a set that grows factorially with dimension. Combinatorial optimization algorithms may enable efficient point estimation, but fully Bayesian inference poses a severe challenge in this high-dimensional, di…

The paper models financial correlation matrices using permutation invariant Gaussian models and predicts market anomalies.

New method connects neural networks to diagrammatic algebra.

Generalized Laurent monomials for nonrational spaces.

π-GNN learns soft permutations for graph representations, improving graph classification and regression.

Many problems at the intersection of combinatorics and computer science require solving for a permutation that optimally matches, ranks, or sorts some data. These problems usually have a task-specific, often non-differentiable objective function that data-driven algorithms can use as a learning signal. In this paper, w…

Kaleidoscope matrices improve model quality and inference speed.

Semi-direct products of finite groups have permutation representations that are constructed from the permutation representations of their constituents. One can envision these in a metaphoric sense in which a rope is made from a bundle of threads. In this way, subgroups and quotients are easily visualized. The general i…

Sorting input objects is an important step in many machine learning pipelines. However, the sorting operator is non-differentiable with respect to its inputs, which prohibits end-to-end gradient-based optimization. In this work, we propose NeuralSort, a general-purpose continuous relaxation of the output of the sorting…

The paper studies stochastic optimization on matrices and its limits as dimensions grow.

Paper recovers multi-subspace matrices from permuted data.

Derives formulae for general permutation equivariant layers and presents a second order graph variational encoder.

Graph alignment problem solved with convex relaxations for correlated matrices.

Given a matrix the seriation problem consists in permuting its rows in such way that all its columns have the same shape, for example, they are monotone increasing. We propose a statistical approach to this problem where the matrix of interest is observed with noise and study the corresponding minimax rate of estimatio…

Monge matrices and their permuted versions known as pre-Monge matrices naturally appear in many domains across science and engineering. While the rich structural properties of such matrices have long been leveraged for algorithmic purposes, little is known about their impact on statistical estimation. In this work, we …

We consider the problem of noisy matrix completion, in which the goal is to reconstruct a structured matrix whose entries are partially observed in noise. Standard approaches to this underdetermined inverse problem are based on assuming that the underlying matrix has low rank, or is well-approximated by a low rank matr…

New algorithm finds sparse matrices on Stiefel manifold for optimisation.

We present here a result of Monomialization of real analytic two-symmetric tensor fields over regular real analytic surfaces. We apply it to the (extension of the pull-back of the) inner metric of a resolved surface of a real analytic surface singularity. Doing so we recover Hsiang & Pati property at each point of the …

UPCA solves data matrix completion with permuted columns.

The paper connects knot volume to $A$-polynomial structure.

We prove a version of Jonsson-Mustaţǎ's Conjecture, which says for any graded sequence of ideals, there exists a quasi-monomial valuation computing its log canonical threshold. As a corollary, we confirm Chi Li's conjecture that a minimizer of the normalized volume function is always quasi-monomial. Applying our techni…

Scattering networks maximize separation on low-dimensional data.

It is of increasing importance to develop learning methods for ranking. In contrast to many learning objectives, however, the ranking problem presents difficulties due to the fact that the space of permutations is not smooth. In this paper, we examine the class of rank-linear objective functions, which includes popular…

Sigma-Pi-Sigma neural networks (SPSNNs) as a kind of high-order neural networks can provide more powerful mapping capability than the traditional feedforward neural networks (Sigma-Sigma neural networks). In the existing literature, in order to reduce the number of the Pi nodes in the Pi layer, a special multinomial P_…

Generating point clouds, e.g., molecular structures, in arbitrary rotations, translations, and enumerations remains a challenging task. Meanwhile, neural networks utilizing symmetry invariant layers have been shown to be able to optimize their training objective in a data-efficient way. In this spirit, we present an ar…

We propose an end-to-end deep learning learning model for graph classification and representation learning that is invariant to permutation of the nodes of the input graphs. We address the challenge of learning a fixed size graph representation for graphs of varying dimensions through a differentiable node attention po…

Paper defines and computes a new weight system for gl_N Lie algebra.

Many applications, including rank aggregation, crowd-labeling, and graphon estimation, can be modeled in terms of a bivariate isotonic matrix with unknown permutations acting on its rows and/or columns. We consider the problem of estimating an unknown matrix in this class, based on noisy observations of (possibly, a su…

Study stability thresholds of big line bundles, proving bounds and generalizing results.

POUnets combine partitions of unity and monomials for efficient deep learning.

We prove that the Kontsevich tetrahedral flow $\dot{\mathcal{P}} = \mathcal{Q}_{a:b} (\mathcal{P})$, the right-hand side of which is a linear combination of two differential monomials of degree four in a bi-vector $\mathcal{P}$ on an affine real Poisson manifold $N^n$, does infinitesimally preserve the space of Poisson…

The crossing matrix of a braid on $N$ strands is the $N\times N$ integer matrix with zero diagonal whose $i,j$ entry is the algebraic number (positive minus negative) of crossings by strand $i$ over strand $j$ . When restricted to the subgroup of pure braids, this defines a homomorphism onto the additive subgroup of $N…

We develope in great computational details the classical Cartan equivalence problem for Levi-nondegenerate C^6-smooth real hypersurfaces M^3 in C^2, performing all calculations effectively in terms of a (local) graphing function \varphi. In particular, we present explicitly the unique (complex) essential invariant J of…

This paper tackles fitting multilevel low rank matrices by addressing three problems.

This work tackles Bayesian neural networks by addressing loss landscape symmetries.

In the modern age, rankings data is ubiquitous and it is useful for a variety of applications such as recommender systems, multi-object tracking and preference learning. However, most rankings data encountered in the real world is incomplete, which prevents the direct application of existing modelling tools for complet…

In the last decade, the approximate vanishing ideal and its basis construction algorithms have been extensively studied in computer algebra and machine learning as a general model to reconstruct the algebraic variety on which noisy data approximately lie. In particular, the basis construction algorithms developed in ma…

Gaussian latent tree models, or more generally, Gaussian latent forest models have Fisher-information matrices that become singular along interesting submodels, namely, models that correspond to subforests. For these singularities, we compute the real log-canonical thresholds (also known as stochastic complexities or l…

We propose a novel approach to addressing the vanishing (or exploding) gradient problem in deep neural networks. We construct a new architecture for deep neural networks where all layers (except the output layer) of the network are a combination of rotation, permutation, diagonal, and activation sublayers which are all…

Matching correlated VAR time series databases by recovering matching permutations.

Power-law spectrum of random feature model is preserved in neural networks.

We consider a generalization of low-rank matrix completion to the case where the data belongs to an algebraic variety, i.e. each data point is a solution to a system of polynomial equations. In this case the original matrix is possibly high-rank, but it becomes low-rank after mapping each column to a higher dimensional…

We find finite presentations for the automorphism group of the Artin pure braid group and the automorphism group of the pure braid group associated to the full monomial group.

Given a klt singularity $x\in (X, D)$, we show that a quasi-monomial valuation $v$ with a finitely generated associated graded ring is the minimizer of the normalized volume function $\widehat{\rm vol}_{(X,D),x}$, if and only if $v$ induces a degeneration to a K-semistable log Fano cone singularity. Moreover, such a mi…