arXiv research

We develop a sequential low-complexity inference procedure for Dirichlet process mixtures of Gaussians for online clustering and parameter estimation when the number of clusters are unknown a-priori. We present an easily computable, closed form parametric expression for the conditional likelihood, in which hyperparamet…

Low complexity decentralized neural net with centralized performance.

New algorithm outperforms existing ones in multi-player bandit problems without sensing.

We describe a method that infers whether statistical dependences between two observed variables X and Y are due to a "direct" causal link or only due to a connecting causal path that contains an unobserved variable of low complexity, e.g., a binary variable. This problem is motivated by statistical genetics. Given a ge…

Study shows low-complexity models can perform as well as state-of-the-art on small datasets.

C3 compresses images and videos with low complexity and high performance.

We prove that, except in some low-complexity cases, every locally injective simplicial map between pants graphs is induced by a $π_1$-injective embedding between the corresponding surfaces.

This paper investigates symmetric ribbon numbers of low-complexity knots.

The FloatSD technology has been shown to have excellent performance on low-complexity convolutional neural networks (CNNs) training and inference. In this paper, we applied FloatSD to recurrent neural networks (RNNs), specifically long short-term memory (LSTM). In addition to FloatSD weight representation, we quantized…

No free lunch theorems suggest inductive biases are needed, but we show neural networks prefer low-complexity data.

BASS efficiently learns time-varying graphs with low complexity and automatic tuning.

A cobordism between links in thickened surfaces consists of a surface $S$ and a $3$-manifold $M$, with $S$ properly embedded in $M \times I$. We show that there exist links in thickened surfaces such that if $(S,M)$ is a cobordism between them in which $S$ is simple, then $M$ must be complex. That is, there…

In this short note, we prove that on the three-sphere with any bumpy metric there exist at least four solutions of the Allen-Cahn equation with spherical interface and index at most two. The proof combines several recent results from the literature.

We propose a low-complexity sub-banded DSP architecture for digital backpropagation where the walk-off effect is compensated using simple delay elements. For a simulated 96-Gbaud signal and 2500 km optical link, our method achieves a 2.8 dB SNR improvement over linear equalization.

We propose reinforcement learning on simple networks consisting of random connections of spiking neurons (both recurrent and feed-forward) that can learn complex tasks with very little trainable parameters. Such sparse and randomly interconnected recurrent spiking networks exhibit highly non-linear dynamics that transf…

New iterative regularization method tackles non-smooth, non-strongly convex functionals.

Study shows pants graph automorphisms match mapping class groups of nonorientable surfaces.

In this paper, we study the sum rate maximization for successive zero-forcing dirty-paper coding (SZFDPC) with per-antenna power constraint (PAPC). Although SZFDPC is a low-complexity alternative to the optimal dirty paper coding (DPC), efficient algorithms to compute its sum rate are still open problems especially und…

Inverse problems and regularization theory is a central theme in contemporary signal processing, where the goal is to reconstruct an unknown signal from partial indirect, and possibly noisy, measurements of it. A now standard method for recovering the unknown signal is to solve a convex optimization problem that enforc…

This paper studies least-square regression penalized with partly smooth convex regularizers. This class of functions is very large and versatile allowing to promote solutions conforming to some notion of low-complexity. Indeed, they force solutions of variational problems to belong to a low-dimensional manifold (the so…

We present reconstruction algorithms for smooth signals with block sparsity from their compressed measurements. We tackle the issue of varying group size via group-sparse least absolute shrinkage selection operator (LASSO) as well as via latent group LASSO regularizations. We achieve smoothness in the signal via fusion…

New method estimates graphons from multiple networks with high accuracy and low complexity.

A new metric HCP distance for comparing distributions.

Neural networks generalize on simple data generated by a programming language.

Deep-n-Cheap automates deep learning model search for low complexity.

This paper focusses on "safe" screening techniques for the LASSO problem. Motivated by the need for low-complexity algorithms, we propose a new approach, dubbed "joint" screening test, allowing to screen a set of atoms by carrying out one single test. The approach is particularized to two different sets of atoms, respe…

Proposes efficient Bayesian logistic regression for large sparse datasets.

Greedy policy maximizes information in unknown linear systems.

We show that the genus problem for alternating knots with $n$ crossings has linear time complexity and is in Logspace$(n)$. Almost all alternating knots of given genus possess additional combinatorial structure, we call them standard. We show that the genus problem for these knots belongs to $TC^0$ circuit complexity c…

This article constructs the moduli stack of torsionfree $G$-jet-structures in homotopy type theory with one monadic modality. This yields a construction of this moduli stack for any $\infty$-topos equipped with any stable factorization systems. In the intended applications of this theory, the factorization systems are …

Given a matrix M of low-rank, we consider the problem of reconstructing it from noisy observations of a small, random subset of its entries. The problem arises in a variety of applications, from collaborative filtering (the `Netflix problem') to structure-from-motion and positioning. We study a low complexity algorithm…

By analyzing known presentations of the pure mapping groups of orientable surfaces of genus $g$ with $b$ boundary components and $n$ punctures, we show that these groups are isomorphic to some groups related to the braid groups and the Artin group of type $D_4$ in the cases when $g=0$ with $b$ and $n$ arbitrary, and wh…

We consider the problem of learning the structure of Ising models (pairwise binary Markov random fields) from i.i.d. samples. While several methods have been proposed to accomplish this task, their relative merits and limitations remain somewhat obscure. By analyzing a number of concrete examples, we show that low-comp…

Gaussian processes (GPs) are versatile tools that have been successfully employed to solve nonlinear estimation problems in machine learning, but that are rarely used in signal processing. In this tutorial, we present GPs for regression as a natural nonlinear extension to optimal Wiener filtering. After establishing th…

This paper examines the problem of locating outlier columns in a large, otherwise low-rank matrix, in settings where {}{the data} are noisy, or where the overall matrix has missing elements. We propose a randomized two-step inference framework, and establish sufficient conditions on the required sample complexities und…

We describe the first known mean-field study of landing probabilities for random walks on hypergraphs. In particular, we examine clique-expansion and tensor methods and evaluate their mean-field characteristics over a class of random hypergraph models for the purpose of seed-set community expansion. We describe paramet…

We consider the problem of learning the structure of Ising models (pairwise binary Markov random fields) from i.i.d. samples. While several methods have been proposed to accomplish this task, their relative merits and limitations remain somewhat obscure. By analyzing a number of concrete examples, we show that low-comp…

New algorithm reduces complexity for SPD manifold optimization.

In this paper we study the real time deployment of deep learning algorithms in low resource computational environments. As the use case, we compare the accuracy and speed of neural networks for smile detection using different neural network architectures and their system level implementation on NVidia Jetson embedded p…

In this letter, we derive the optimal discriminant functions for modulation classification based on the sampled distribution distance. The proposed method classifies various candidate constellations using a low complexity approach based on the distribution distance at specific testpoints along the cumulative distributi…

In this paper we are interested in computing representations of the fundamental group of a 3-manifold into PSL(3;C) (in particular in PSL(2;C); PSL(3;R) and PU(2; 1)). The representations are obtained by gluing decorated tetrahedra of flags. We list complete computations (giving 0-dimensional or 1-dimensional solution …

Paper tackles sample-efficient RL for linearly realizable MDPs with limited revisiting.

Spheres in curve graphs are connected, proving Gromov boundary linearity.

Biological evolution has distilled the experiences of many learners into the general learning algorithms of humans. Our novel meta reinforcement learning algorithm MetaGenRL is inspired by this process. MetaGenRL distills the experiences of many complex agents to meta-learn a low-complexity neural objective function th…

We introduce a balloon estimator in a generalized expectation-maximization method for estimating all parameters of a Gaussian mixture model given one data sample per mixture component. Instead of limiting explicitly the model size, this regularization strategy yields low-complexity sparse models where the number of eff…

We introduce GAMSEL (Generalized Additive Model Selection), a penalized likelihood approach for fitting sparse generalized additive models in high dimension. Our method interpolates between null, linear and additive models by allowing the effect of each variable to be estimated as being either zero, linear, or a low-co…

We propose a stochastic approximation (SA) based method with randomization of samples for policy evaluation using the least squares temporal difference (LSTD) algorithm. Our proposed scheme is equivalent to running regular temporal difference learning with linear function approximation, albeit with samples picked unifo…

Proposes isotonic recalibration for insurance pricing to ensure auto-calibration under low signal-to-noise ratio.