BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Pierre-Olivier Amblard

Pierre-Olivier Amblard contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.PRData Structures and AlgorithmsDiscrete Mathematicsmath.STStatistics Theoryeess.SPMachine Learningmath.COmath.MGmath.OCMethodology

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
10works
0followers
11topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

10 published item(s)

preprint2022arXiv

Conic Frameworks Infinitesimal Rigidity

This paper introduces new structures called conic frameworks and their rigidity. They are composed by agents and a set of directed constraints between pairs of agents. When the structure cannot be flexed while preserving the constraints, it is said to be rigid. If only smooth deformations are considered a sufficient condition for rigidity is called infinitesimal rigidity. In conic frameworks, each agent $u$ has a spatial position $x_u$ and a clock offset represented by a bias $β_u$. If the constraint from Agent $u$ to Agent $w$ is in the framework, the pseudo-range from $u$ to $w$, defined as ${\left\lVert{x_u - x_w}\right\rVert} + β_w - β_u$, is set. Pseudo-ranges appear when measuring inter-agent distances using a Time-of-Arrival method. This paper completely characterizes infinitesimal rigidity of conic frameworks whose agents are in general position. Two characterizations are introduced: one for unidimensional frameworks, the other for multidimensional frameworks. They both rely on the graph of constraints and use a decoupling between space and bias variables. In multidimensional cases, this new conic paradigm sharply reduces the minimal number of constraints required to maintain a formation with respect to classical Two-Way Ranging methods.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Determinantal Point Processes in the Flat Limit

Determinantal point processes (DPPs) are repulsive point processes where the interaction between points depends on the determinant of a positive-semi definite matrix. In this paper, we study the limiting process of L-ensembles based on kernel matrices, when the kernel function becomes flat (so that every point interacts with every other point, in a sense). We show that these limiting processes are best described in the formalism of extended L-ensembles and partial projection DPPs, and the exact limit depends mostly on the smoothness of the kernel function. In some cases, the limiting process is even universal, meaning that it does not depend on specifics of the kernel function, but only on its degree of smoothness. Since flat-limit DPPs are still repulsive processes, this implies that practically useful families of DPPs exist that do not require a spatial length-scale parameter.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Determinantal Point Processes in the Flat Limit: Extended L-ensembles, Partial-Projection DPPs and Universality Classes

Determinantal point processes (DPPs) are repulsive point processes where the interaction between points depends on the determinant of a positive-semi definite matrix. The contributions of this paper are two-fold. First of all, we introduce the concept of extended L-ensemble, a novel representation of DPPs. These extended L-ensembles are interesting objects because they fix some pathologies in the usual formalism of DPPs, for instance the fact that projection DPPs are not L-ensembles. Every (fixed-size) DPP is an (fixed-size) extended L-ensemble, including projection DPPs. This new formalism enables to introduce and analyze a subclass of DPPs, called partial-projection DPPs. Secondly, with these new definitions in hand, we first show that partial-projection DPPs arise as perturbative limits of L-ensembles, that is, limits in $\varepsilon \rightarrow 0$ of L-ensembles based on matrices of the form $\varepsilon \mathbf{A} + \mathbf{B}$ where $\mathbf{B}$ is low-rank. We generalise this result by showing that partial-projection DPPs also arise as the limiting process of L-ensembles based on kernel matrices, when the kernel function becomes flat (so that every point interacts with every other point, in a sense). We show that the limiting point process depends mostly on the smoothness of the kernel function. In some cases, the limiting process is even universal, meaning that it does not depend on specifics of the kernel function, but only on its degree of smoothness.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Extended L-ensembles: a new representation for Determinantal Point Processes

Determinantal point processes (DPPs) are a class of repulsive point processes, popular for their relative simplicity. They are traditionally defined via their marginal distributions, but a subset of DPPs called "L-ensembles" have tractable likelihoods and are thus particularly easy to work with. Indeed, in many applications, DPPs are more naturally defined based on the L-ensemble formulation rather than through the marginal kernel. The fact that not all DPPs are L-ensembles is unfortunate, but there is a unifying description. We introduce here extended L-ensembles, and show that all DPPs are extended L-ensembles (and vice-versa). Extended L-ensembles have very simple likelihood functions, contain L-ensembles and projection DPPs as special cases. From a theoretical standpoint, they fix some pathologies in the usual formalism of DPPs, for instance the fact that projection DPPs are not L-ensembles. From a practical standpoint, they extend the set of kernel functions that may be used to define DPPs: we show that conditional positive definite kernels are good candidates for defining DPPs, including DPPs that need no spatial scale parameter. Finally, extended L-ensembles are based on so-called ``saddle-point matrices'', and we prove an extension of the Cauchy-Binet theorem for such matrices that may be of independent interest.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Graph Tikhonov Regularization and Interpolation via Random Spanning Forests

Novel Monte Carlo estimators are proposed to solve both the Tikhonov regularization (TR) and the interpolation problems on graphs. These estimators are based on random spanning forests (RSF), the theoretical properties of which enable to analyze the estimators' theoretical mean and variance. We also show how to perform hyperparameter tuning for these RSF-based estimators. TR is a component in many well-known algorithms, and we show how the proposed estimators can be easily adapted to avoid expensive intermediate steps in generalized semi-supervised learning, label propagation, Newton's method and iteratively reweighted least squares. In the experiments, we illustrate the proposed methods on several problems and provide observations on their run time.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Variance Reduction for Inverse Trace Estimation via Random Spanning Forests

The trace $\tr(q(\ma{L} + q\ma{I})^{-1})$, where $\ma{L}$ is a symmetric diagonally dominant matrix, is the quantity of interest in some machine learning problems. However, its direct computation is impractical if the matrix size is large. State-of-the-art methods include Hutchinson's estimator combined with iterative solvers, as well as the estimator based on random spanning forests (a random process on graphs). In this work, we show two ways of improving the forest-based estimator via well-known variance reduction techniques, namely control variates and stratified sampling. Implementing these techniques is easy, and provides substantial variance reduction, yielding comparable or better performance relative to state-of-the-art algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Determinantal Point Processes for Coresets

When faced with a data set too large to be processed all at once, an obvious solution is to retain only part of it. In practice this takes a wide variety of different forms, and among them "coresets" are especially appealing. A coreset is a (small) weighted sample of the original data that comes with the following guarantee: a cost function can be evaluated on the smaller set instead of the larger one, with low relative error. For some classes of problems, and via a careful choice of sampling distribution (based on the so-called "sensitivity" metric), iid random sampling has turned to be one of the most successful methods for building coresets efficiently. However, independent samples are sometimes overly redundant, and one could hope that enforcing diversity would lead to better performance. The difficulty lies in proving coreset properties in non-iid samples. We show that the coreset property holds for samples formed with determinantal point processes (DPP). DPPs are interesting because they are a rare example of repulsive point processes with tractable theoretical properties, enabling us to prove general coreset theorems. We apply our results to both the k-means and the linear regression problems, and give extensive empirical evidence that the small additional computational cost of DPP sampling comes with superior performance over its iid counterpart. Of independent interest, we also provide analytical formulas for the sensitivity in the linear regression and 1-means cases.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Projections of determinantal point processes

Let $\mathbf x=\{x^{(1)},\dots,x^{(n)}\}$ be a space filling-design of $n$ points defined in $[0{,}1]^d$. In computer experiments, an important property seeked for $\mathbf x$ is a nice coverage of $[0{,}1]^d$. This property could be desirable as well as for any projection of $\mathbf x$ onto $[0{,}1]^ι$ for $ι<d$ . Thus we expect that $\mathbf x_I=\{x_I^{(1)},\dots,x_I^{(n)}\}$, which represents the design $\mathbf x$ with coordinates associated to any index set $I\subseteq\{1,\dots,d\}$, remains regular in $[0{,}1]^ι$ where $ι$ is the cardinality of $I$. This paper examines the conservation of nice coverage by projection using spatial point processes, and more specifically using the class of determinantal point processes. We provide necessary conditions on the kernel defining these processes, ensuring that the projected point process $\mathbf{X}_I$ is repulsive, in the sense that its pair correlation function is uniformly bounded by 1, for all $I\subseteq\{1,\dots,d\}$. We present a few examples, compare them using a new normalized version of Ripley&#39;s function. Finally, we illustrate the interest of this research for Monte-Carlo integration.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Smoothing graph signals via random spanning forests

Another facet of the elegant link between random processes on graphs and Laplacian-based numerical linear algebra is uncovered: based on random spanning forests, novel Monte-Carlo estimators for graph signal smoothing are proposed. These random forests are sampled efficiently via a variant of Wilson&#39;s algorithm --in time linear in the number of edges. The theoretical variance of the proposed estimators are analyzed, and their application to several problems are considered, such as Tikhonov denoising of graph signals or semi-supervised learning for node classification on graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

VAR estimators using binary measurements

In this paper, two novel algorithms to estimate a Gaussian Vector Autoregressive (VAR) model from 1-bit measurements are introduced. They are based on the Yule-Walker scheme modified to account for quantisation. The scalar case has been studied before. The main difficulty when going from the scalar to the vector case is how to estimate the ratios of the variances of pairwise components of the VAR model. The first method overcomes this difficulty by requiring the quantisation to be non-symmetric: each component of the VAR model output is replaced by a binary &#34;zero&#34; or a binary &#34;one&#34; depending on whether its value is greater than a strictly positive threshold. Different components of the VAR model can have different thresholds. As the choice of these thresholds has a strong influence on the performance, this first method is best suited for applications where the variance of each time series is approximately known prior to choosing the corresponding threshold. The second method relies instead on symmetric quantisations of not only each component of the VAR model but also on the pairwise differences of the components. These additional measurements are equivalent to a ranking of the instantaneous VAR model output, from the smallest component to the largest component. This avoids the need for choosing thresholds but requires additional hardware for quantising the components in pairs. Numerical simulations show the efficiency of both schemes.

0 citations0 reviewsNo code linkedOpen access