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, …
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,657 papers · 148 categories
Trend · papers per month
48 results for “permutation matrices”
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.
On meandric permutationsmath.AT
We found a way to code meanders and show they are idempotent.
problem Understanding and coding meandric permutations.
method We established a bijection between meanders and Gauss diagrams, and used this to construct matrices that are idempotent.
result Meandric permutations are idempotent over the field GF(2).
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.
problem Modeling and predicting financial correlation matrices from high-frequency data.
method Constructing permutation invariant Gaussian matrix models with 4 parameters, using graph theory and polynomial functions.
result The permutation invariant Gaussian matrix model predicts the expectation values of cubic and quartic polynomials with strong evidence of fit.
New method connects neural networks to diagrammatic algebra.
problem Constructing permutation equivariant neural networks.
method Schur-Weyl duality between symmetric group and partition algebra.
result Simple diagrammatic method for calculating weight matrices.
π-GNN learns soft permutations for graph representations, improving graph classification and regression.
problem Limitations of MPNNs in graph neural networks.
method Proposes π-GNN, which learns a soft permutation matrix for each graph, projecting graphs into a common vector space.
result π-GNN achieves performance competitive with state-of-the-art models on graph classification and regression tasks.
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.
problem Choosing structured linear transformations for efficiency and accuracy.
method Introduce kaleidoscope matrices that can capture any structured matrix with near-optimal space and time complexity. Learn these matrices automatically within end-to-end pipelines.
result Kaleidoscope matrices can 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.
problem Optimizing functions on large symmetric matrices using stochastic gradient descent.
method Deterministic limits of random curves on matrices, using graphons and stochastic differential equations.
result The limit is a gradient flow on graphons, extending classical McKean-Vlasov limits.
Paper recovers multi-subspace matrices from permuted data.
problem Recovering a multi-subspace matrix from permuted data with corrupted columns.
method Four-stage algorithm pipeline: outlier identification, subspace reconstruction, outlier classification, unsupervised sensing.
result The pipeline provides theoretical guarantees for reliable multi-subspace matrix recovery.
Derives formulae for general permutation equivariant layers and presents a second order graph variational encoder.
problem Tackles the limitation of previous equivariant neural networks by considering permutations of matrices.
method Derives formulae for general permutation equivariant layers, including matrix permutations. Presents a second order graph variational encoder.
result Latent distribution of equivariant generative models must be exchangeable.
Graph alignment problem solved with convex relaxations for correlated matrices.
problem Recovering hidden vertex permutations from correlated Gaussian matrices.
method Convex relaxations of the quadratic assignment problem over doubly stochastic matrices.
result The solution of the convex relaxation concentrates around the ground-truth permutation matrix for certain correlation parameters.
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…
Estimation of Monge Matricesmath.ST
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.
problem Finding sparse matrices on Stiefel manifold for optimisation.
method Modified Orthogonal Iteration algorithm for sparse global optimality.
result Proposed method finds globally optimal sparse Stiefel matrices.
UPCA solves data matrix completion with permuted columns.
problem Data matrix completion with permuted columns.
method Algebraic geometry and two-stage algorithm.
result UPCA recovers the ground-truth matrix from corrupted 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…
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…
A new bootstrapping method reduces key sizes and runtime in FHE.
problem Large plaintext evaluation in FHE increases bootstrapping complexity.
method New polynomial vector representation and monic monomial permutation matrices.
result Polynomial factor improvement in key size and constant factor in runtime.
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…
The crossing matrix of a braid on strands is the integer matrix with zero diagonal whose entry is the algebraic number (positive minus negative) of crossings by strand over strand . When restricted to the subgroup of pure braids, this defines a homomorphism onto the additive subgroup of $N…
This paper tackles fitting multilevel low rank matrices by addressing three problems.
problem Fitting a given matrix by an MLR matrix in the Frobenius norm.
method Factor fitting, rank allocation, and hierarchical partitioning.
result The proposed methods can fit a given matrix by an MLR matrix in the Frobenius norm.
This work tackles Bayesian neural networks by addressing loss landscape symmetries.
problem Understanding and optimizing the loss landscape of Bayesian neural networks.
method The approach involves extending marginalized loss barrier formalism to BNNs, proposing a matching algorithm to search for linearly connected solutions using permutation matrices and combinatorial optimization.
result Nearly zero marginalized loss barriers for linearly connected solutions were found.
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…
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.
problem Matching perturbed and permuted correlated VAR time series.
method Probabilistic framework modeling, maximum likelihood estimator (MLE), linear assignment, convex relaxations.
result Recovery guarantees for perfect or partial recovery of matching permutations, thresholds for .
Boolean matrix has been used to represent digital information in many fields, including bank transaction, crime records, natural language processing, protein-protein interaction, etc. Boolean matrix factorization (BMF) aims to find an approximation of a binary matrix as the Boolean product of two low rank Boolean matri…
The paper explores how low-degree polynomials can detect shuffled linear regression models.
problem Detecting multivariate shuffled linear regression models from independent Gaussian random matrices.
method Investigates the effectiveness of low-degree polynomial algorithms for distinguishing the model from independent Gaussian random matrices.
result Establishes a phase transition phenomenon in the performance of low-degree polynomial algorithms for distinguishing the model.
Convolutional neural networks (CNNs) have achieved breakthrough performances in a wide range of applications including image classification, semantic segmentation, and object detection. Previous research on characterizing the generalization ability of neural networks mostly focuses on fully connected neural networks (F…
New invariants derived from random matrices for words in free groups.
problem Defining and understanding new topological invariants for words in free groups.
method Defining and analyzing invariants from -random matrices and permutations.
result Presented new topological, combinatorial, and algebraic invariants of words.
Quandles with involutions that satisfy certain conditions, called good involutions, can be used to color non-orientable surface-knots. We use subgroups of signed permutation matrices to construct non-trivial good involutions on extensions of odd order dihedral quandles. For the smallest example of order 6 that is an ex…
Learning molecular energies using localized graph kernelsphysics.comp-ph
Recent machine learning methods make it possible to model potential energy of atomic configurations with chemical-level accuracy (as calculated from ab-initio calculations) and at speeds suitable for molecular dynam- ics simulation. Best performance is achieved when the known physical constraints are encoded in the mac…
Bayesian networks are a class of popular graphical models that encode causal and conditional independence relations among variables by directed acyclic graphs (DAGs). We propose a novel structure learning method, annealing on regularized Cholesky score (ARCS), to search over topological sorts, or permutations of nodes,…
This paper presents a new method for estimating high dimensional covariance matrices. The method, permuted rank-penalized least-squares (PRLS), is based on a Kronecker product series expansion of the true covariance matrix. Assuming an i.i.d. Gaussian random sample, we establish high dimensional rates of convergence to…
ButterflyFlow uses butterfly matrices for efficient invertible layers in normalizing flows.
problem Building efficient invertible layers for complex probability distributions.
method Proposes butterfly layers for invertible linear layers, leveraging their ability to capture complex structures.
result ButterflyFlow achieves strong density estimation and significantly better log-likelihoods on various datasets.
New neural networks learn graph symmetries.
problem Learning from graph data without considering vertex relations.
method Constructs equivariant neural networks to Aut(G) group.
result Characterizes learnable, linear, Aut(G)-equivariant functions.
New statistics improve kernel independence testing efficiency.
problem Improving efficiency in kernel independence testing.
method Adapting martingale MMD construction to joint independence problem.
result Two new statistics achieve finite-sample consistency with linear per-test cost.
Deep neural networks (DNNs) have been employed for designing wireless networks in many aspects, such as transceiver optimization, resource allocation, and information prediction. Existing works either use fully-connected DNN or the DNNs with specific structures that are designed in other domains. In this paper, we show…
In this work we study convex relaxations of quadratic optimisation problems over permutation matrices. While existing semidefinite programming approaches can achieve remarkably tight relaxations, they have the strong disadvantage that they lift the original -dimensional variable to an -d…
Study of braid varieties and their Legendrian isotopy.
problem Understanding the geometric properties of braid varieties.
method Examined four types of braids and their Legendrian links.
result Each open positroid stratum can be represented as an augmentation variety.
Cheap Permutation Testingmath.ST
Cheap permutation tests speed up distribution testing without sacrificing accuracy.
problem Efficiently testing distribution differences and independence.
method Group datapoints into bins and permute only these bins, using stored sufficient statistics.
result Cheap permutation tests maintain the accuracy and optimality of standard tests but are significantly faster.
C-OPH improves One Permutation Hashing by using a shorter circulant permutation.
problem Improving the accuracy of One Permutation Hashing (OPH) for Jaccard similarity estimation.
method Develops a new densification method using a shorter circulant permutation.
result Achieves the smallest estimation variance for Jaccard similarity.
Random permutations can offer faster convergence than with-replacement sampling for some functions.
problem Understanding when and how random permutations outperform with-replacement sampling in SGD convergence.
method Analyzing convergence rates for different function classes (1D strongly convex, general strongly convex, quadratic strongly convex).
result The optimal convergence gap between random and permutation-based SGD varies from exponential to nonexistent, depending on the function class.