Search

The many-body $GW$ formalism, for the calculation of ionization potentials or electronic affinities, relies on the frequency-dependent dielectric function built from the electronic degrees of freedom. Considering the case of water as a solvent treated within the polarizable continuum model, we explore the impact of restricting the full frequency-dependence of the solvent electronic dielectric response to a frequency-independent $(\epsilon_\infty)$ optical dielectric constant. For solutes presenting small to large highest-occupied to lowest-unoccupied molecular orbital energy gaps, we show that such a restriction induces errors no larger than a few percent on the energy level shifts from the gas to the solvated phase. We further introduce a remarkably accurate single-pole model for mimicking the effect of the full frequency dependence of the water dielectric function in the visible-UV range. This allows a fully dynamical embedded $GW$ calculation with the only knowledge of the cavity reaction field calculated for the $\epsilon_\infty$ optical dielectric constant.

Continuum or discrete polarizable models for the study of optoelectronic processes in embedded subsystems rely mostly on the restriction of the surrounding electronic dielectric response to its low frequency limit. Such a description hinges on the assumption that the electrons in the surrounding medium react instantaneously to any excitation in the central subsystem, treating thus the environment in the adiabatic limit. Exploiting a recently developed embedded $GW$ formalism, with an environment described at the fully ab initio level, we assess the merits of the adiabatic limit with respect to an environment where the full dynamics of the dielectric response is considered. Further, we show how to properly take the static limit of the environment susceptibility, introducing the so-called Coulomb-hole and screened-exchange contributions to the reaction field. As a first application, we consider a C$_{60}$ molecule at the surface of a C$_{60}$ crystal, namely a case where the dynamics of the embedded and embedding subsystems are similar. The common adiabatic assumption, when properly treated, generates errors below $10\%$ on the polarization energy associated with frontier energy levels and associated energy gaps. Finally, we consider a water molecule inside a metallic nanotube, the worst case for the environment adiabatic limit. The error on the gap polarization energy remains below $10\%$, even though the error on the frontier orbitals polarization energies can reach a few tenths of an electronvolt.

Random diffusions are a popular tool in Monte-Carlo estimations, with well established algorithms such as Walk-on-Spheres (WoS) going back several decades. In this work, we introduce diffusion estimators for the problems of angular synchronization and smoothing on graphs, in the presence of a rotation associated to each edge. Unlike classical WoS algorithms that are point-wise estimators, our diffusion estimators allow for global estimations by propagating along the branches of random spanning subgraphs called multi-type spanning forests. Building upon efficient samplers based on variants of Wilson's algorithm, we show that our estimators outperform standard numerical-linear-algebra solvers in challenging instances, depending on the topology and density of the graph.

This paper introduces a new conservative fusion method to exploit the correlated components within the estimation errors. Fusion is the process of combining multiple estimates of a given state to produce a new estimate with a smaller MSE. To perform the optimal linear fusion, the (centralized) covariance associated with the errors of all estimates is required. If it is partially unknown, the optimal fusion cannot be computed. Instead, a solution is to perform a conservative fusion. A conservative fusion provides a gain and a bound on the resulting MSE matrix which guarantees that the error is not underestimated. A well-known conservative fusion is the Covariance Intersection fusion. It has been modified to exploit the uncorrelated components within the errors. In this paper, it is further extended to exploit the correlated components as well. The resulting fusion is integrated into standard distributed algorithms where it allows exploiting the process noise observed by all agents. The improvement is confirmed by simulations.

Topics play an important role in the global organisation of a conversation as what is currently discussed constrains the possible contributions of the participant. Understanding the way topics are organised in interaction would provide insight on the structure of dialogue beyond the sequence of utterances. However, studying this high-level structure is a complex task that we try to approach by first segmenting dialogues into smaller topically coherent sets of utterances. Understanding the interactions between these segments would then enable us to propose a model of topic organisation at a dialogue level. In this paper we work with open-domain conversations and try to reach a comparable level of accuracy as recent machine learning based topic segmentation models but with a formal approach. The features we identify as meaningful for this task help us understand better the topical structure of a conversation.

Global Navigation Satellite Systems (GNSS) are a widely used technology for positioning and navigation. GNSS positioning relies on pseudorange measurements from satellites to receivers. A pseudorange is the apparent distance between two agents deduced from the time-of-flight of a signal sent from one agent to the other. Because of the lack of synchronization between the agents' clocks, it is a biased version of their distance. This paper introduces a new rigidity theory adapted to pseudorange measurements. The peculiarity of pseudoranges is that they are asymmetrical measurements. Therefore, unlike other usual rigidities, the graphs of pseudorange frameworks are directed. In this paper, pseudorange rigidity is proved to be a generic property of the underlying undirected graph of constraints. The main result is a characterization of rigid pseudorange graphs as combinations of rigid distance graphs and connected graphs. This new theory is adapted for GNSS. It provides new insights into the minimum number of satellites needed to locate a receiver, and is applied to the localization of GNSS cooperative networks of receivers. The interests of asymmetrical constraints in the context of formation control are also discussed.

We present a many-body $GW$ formalism for quantum subsystems embedded in discrete polarizable environments containing up to several hundred thousand atoms described at a fully ab initio random phase approximation level. Our approach is based on a fragment approximation in the construction of the Green's function and independent-electron susceptibilities. Further, the environing fragments susceptibility matrices are reduced to a minimal but accurate representation preserving low order polarizability tensors through a constrained minimization scheme. This approach dramatically reduces the cost associated with inverting the Dyson equation for the screened Coulomb potential $W$, while preserving the description of short to long-range screening effects. The efficiency and accuracy of the present scheme is exemplified in the paradigmatic cases of fullerene bulk, surface, subsurface, and slabs with varying number of layers.

Linear fusion is a cornerstone of estimation theory. Optimal linear fusion was derived by Bar-Shalom and Campo in the 1980s. It requires knowledge of the cross-covariances between the errors of the estimators. In distributed or cooperative systems, these cross-covariances are difficult to compute. To avoid an underestimation of the errors when these cross-covariances are unknown, conservative fusions must be performed. A conservative fusion provides a fused estimator with a covariance bound which is guaranteed to be larger than the true (but not computable) covariance of the error. Previous research by Reinhardt et al. proved that, if no additional assumption is made about the errors of the estimators, the minimal bound for fusing two estimators is given by a fusion called Covariance Intersection (CI). In practice, the errors of the estimators often have an uncorrelated component, because the dynamic or measurement noise is assumed to be independent. In this context, CI is no longer the optimal method and an adaptation called Split Covariance Intersection (SCI) has been designed to take advantage from these uncorrelated components. The contribution of this paper is to prove that SCI is the optimal fusion rule for two estimators under the assumption that they have an uncorrelated component. It is proved that SCI provides the optimal covariance bound with respect to any increasing cost function. To prove the result, a minimal volume that should contain all conservative bounds is derived, and the SCI bounds are proved to be the only bounds that tightly circumscribe this minimal volume.

Cooperative localization is a promising solution to improve the accuracy and overcome the shortcomings of GNSS. Cooperation is often achieved by measuring the distance between users. To optimally integrate a distance measurement between two users into a navigation filter, the correlation between the errors of their estimates must be known. Unfortunately, in large scale networks the agents cannot compute these correlations and must use consistent filters. A consistent filter provides an upper bound on the covariance of the error of the estimator taking into account all the possible correlations. In this paper, a consistent linear filter for integrating a distance measurement is derived using Split Covariance Intersection. Its analysis shows that a distance measurement between two agents can only benefit one of them, i.e., only one of the two can use the distance measurement to improve its estimator. Furthermore, in some cases, none can. A necessary condition for an agent to benefit from the measurement is given for a general class of objective functions. When the objective function is the trace or the determinant, necessary and sufficient conditions are given.

Discourse processing suffers from data sparsity, especially for dialogues. As a result, we explore approaches to build discourse structures for dialogues, based on attention matrices from Pre-trained Language Models (PLMs). We investigate multiple tasks for fine-tuning and show that the dialogue-tailored Sentence Ordering task performs best. To locate and exploit discourse information in PLMs, we propose an unsupervised and a semi-supervised method. Our proposals achieve encouraging results on the STAC corpus, with F1 scores of 57.2 and 59.3 for unsupervised and semi-supervised methods, respectively. When restricted to projective trees, our scores improved to 63.3 and 68.1.

Discrete Determinantal Point Processes (DPPs) have a wide array of potential applications for subsampling datasets. They are however held back in some cases by the high cost of sampling. In the worst-case scenario, the sampling cost scales as O(n^3) where n is the number of elements of the ground set. A popular workaround to this prohibitive cost is to sample DPPs defined by low-rank kernels. In such cases, the cost of standard sampling algorithms scales as O(np^2 + nm^2) where m is the (average) number of samples of the DPP (usually m << n) and p the rank of the kernel used to define the DPP (m \leq p \leq n). The first term, O(np^2), comes from a SVD-like step. We focus here on the second term of this cost, O(nm^2), and show that it can be brought down to O(nm + m^3 log m) without loss on the sampling's exactness. In practice, we observe very substantial speedups compared to the classical algorithm as soon as n > 1000. The algorithm described here is a close variant of the standard algorithm for sampling continuous DPPs, and uses rejection sampling. In the specific case of projection DPPs, we also show that any additional sample can be drawn in time O(m^3 log m). Finally, an interesting by-product of the analysis is that a realisation from a DPP is typically contained in a subset of size O(m log m) formed using leverage score i.i.d. sampling., Comment: AISTATS 2023

We introduce new smoothing estimators for complex signals on graphs, based on a recently studied Determinantal Point Process (DPP). These estimators are built from subsets of edges and nodes drawn according to this DPP, making up trees and unicycles, i.e., connected components containing exactly one cycle. We provide a Julia implementation of these estimators and study their performance when applied to a ranking problem.

Adaptive Multi-Agent Systems (AMAS) transform dynamic problems into problems of local cooperation between agents. We present smapy, an ensemble based AMAS implementation for mobility prediction, whose agents are provided with machine learning models in addition to their cooperation rules. With a detailed methodology, we propose a framework to transform a classification problem into a cooperative tiling of the input variable space. We show that it is possible to use linear classifiers for online non-linear classification on three benchmark toy problems chosen for their different levels of linear separability, if they are integrated in a cooperative Multi-Agent structure. The results obtained show a significant improvement of the performance of linear classifiers in non-linear contexts in terms of classification accuracy and decision boundaries, thanks to the cooperative approach., Comment: 20th International Conference on Practical Applications of Agents and Multi-Agent Systems, Jul 2022, L'Aquila, Italy. arXiv admin note: substantial text overlap with arXiv:2209.06824

Self-Adaptive Multi-Agent Systems (AMAS) transform machine learning problems into problems of local cooperation between agents. We present smapy, an ensemble based AMAS implementation for mobility prediction, whose agents are provided with machine learning models in addition to their cooperation rules. With a detailed methodology, we show that it is possible to use linear models for nonlinear classification on a benchmark transport mode detection dataset, if they are integrated in a cooperative multi-agent structure. The results obtained show a significant improvement of the performance of linear models in non-linear contexts thanks to the multi-agent approach.

In this paper, we consider two of the currently popular semantic frameworks: Abstract Meaning Representation (AMR)a more abstract framework, and Universal Conceptual Cognitive Annotation (UCCA)-an anchored framework. We use a corpus-based approach to build two graph rewriting systems, a deterministic and a non-deterministic one, from the former to the latter framework. We present their evaluation and a number of ambiguities that we discovered while building our rules. Finally, we provide a discussion and some future work directions in relation to comparing semantic frameworks of different flavors.

This paper presents how the online tool GREW-MATCH can be used to make queries and visualise data from existing semantically annotated corpora. A dedicated syntax is available to construct simple to complex queries and execute them against a corpus. Such queries give transverse views of the annotated data, these views can help for checking the consistency of annotations in one corpus or across several corpora. GREW-MATCH can then be seen as an error mining tool: when inconsistencies are detected, it helps finding the sentences which should be fixed. Finally, GREW-MATCH can also be used as a side tool to assist annotation tasks helping to find annotation examples in existing corpora to be compared to the data to be annotated.

We present Dialogues in Games (DinG), a corpus of manual transcriptions of real-life, oral, spontaneous multi-party dialogues between French-speaking players of the board game Catan. Our objective is to make available a quality resource for French, composed of long dialogues, to facilitate their study in the style of (Asher et al., 2016). In a general dialogue setting, participants share personal information, which makes it impossible to disseminate the resource freely and openly. In DinG, the attention of the participants is focused on the game, which prevents them from talking about themselves. In addition, we are conducting a study on the nature of the questions in dialogue, through annotation (Cruz Blandon et al., 2019), in order to develop more natural automatic dialogue systems.

Depression is a serious mental illness that impacts the way people communicate, especially through their emotions, and, allegedly, the way they interact with others. This work examines depression signals in dialogs, a less studied setting that suffers from data sparsity. We hypothesize that depression and emotion can inform each other, and we propose to explore the influence of dialog structure through topic and dialog act prediction. We investigate a Multi-Task Learning (MTL) approach, where all tasks mentioned above are learned jointly with dialog-tailored hierarchical modeling. We experiment on the DAIC and DailyDialog corpora-both contain dialogs in English-and show important improvements over state-ofthe-art on depression detection (at best 70.6% F 1), which demonstrates the correlation of depression with emotion and dialog organization and the power of MTL to leverage information from different sources.

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 $\beta_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} + \beta_w - \beta_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.

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.

We study defect energy levels in hexagonal boron-nitride with varying number of layers using a fragment many-body $GW$ formalism, taking as examples the paradigmatic carbon-dimer and $C_BV_N$ defects. We show that a single layer can be fragmented in polarizable finite-size areas reproducing faithfully the effect of the dielectric environment, dramatically facilitating the study at the many-body level of point defects in the dilute limit. The evolution of defect energy levels from the monolayer to a $n$-layer system due to increased screening, labeled polarization energies, follow a simple $({\Delta P}/n + P_{\infty})$ behavior. The coefficients $\Delta P$ and $P_{\infty}$ are found to be close-to-universal, with opposite signs for holes and electrons, characterizing mainly the host and the position of the defect (surface or bulk), but hardly the defect type. Our results rationalize the evolution of defect energy levels with layers number, allowing to safely extrapolate results obtained for the monolayer to few-layers, surface or bulk \textit{h}-BN. The present many-body fragment approach further opens the door to studying disordered 2D layers., Comment: Published in Phys. Rev. Materials 6, 064008 (2022)

We investigate the cold and warm gas content, kinematics, and spatial distribution of six local massive elliptical galaxies to probe the origin of the multiphase gas in their atmospheres. We report new observations, including SOFIA [CII], ALMA CO, MUSE H$\alpha$+[NII] and VLA radio observations. These are complemented by a large suite of multiwavelength archival datasets, including thermodynamical properties of the hot gas and radio jets, which are leveraged to investigate the role of AGN feeding/feedback in regulating the multiphase gas content. Our galaxy sample shows a significant diversity in cool gas content, spanning filamentary and rotating structures. In our non-central galaxies, the distribution of such gas is often concentrated, at variance with the more extended features observed in central galaxies. Misalignment between the multiphase gas and stars suggest that stellar mass loss is not the primary driver. A fraction of the cool gas might be acquired via galaxy interactions, but we do not find quantitative evidence of mergers in most of our systems. Instead, key evidence supports the origin via condensation out of the diffuse halo. Comparing with Chaotic Cold Accretion (CCA) simulations, we find that our cool gas-free galaxies are likely in the overheated phase of the self-regulated AGN cycle, while for our galaxies with cool gas the k-plot and AGN power correlation corroborate the phase of CCA feeding in which the condensation rain is triggering more vigorous AGN heating. The related C-ratio further shows that central/non-central galaxies are expected to generate an extended/inner rain, consistent with our sample., Comment: 26 pages, 18 figures, 8 tables, accepted for publication in ApJ; typos corrected, reference added

Gaussian process (GP) regression is a fundamental tool in Bayesian statistics. It is also known as kriging and is the Bayesian counterpart to the frequentist kernel ridge regression. Most of the theoretical work on GP regression has focused on a large-$n$ asymptotics, i.e. as the amount of data increases. Fixed-sample analysis is much more difficult outside of simple cases, such as locations on a regular grid. In this work we perform a fixed-sample analysis that was first studied in the context of approximation theory by Driscoll & Fornberg (2002), called the ``flat limit''. In flat-limit asymptotics, the goal is to characterise kernel methods as the length-scale of the kernel function tends to infinity, so that kernels appear flat over the range of the data. Surprisingly, this limit is well-defined, and displays interesting behaviour: Driscoll & Fornberg showed that radial basis interpolation converges in the flat limit to polynomial interpolation, if the kernel is Gaussian. Subsequent work showed that this holds true in the multivariate setting as well, but that kernels other than the Gaussian may have (polyharmonic) splines as the limit interpolant. Leveraging recent results on the spectral behaviour of kernel matrices in the flat limit, we study the flat limit of Gaussian process regression. Results show that Gaussian process regression tends in the flat limit to (multivariate) polynomial regression, or (polyharmonic) spline regression, depending on the kernel. Importantly, this holds for both the predictive mean and the predictive variance, so that the posterior predictive distributions become equivalent. Our results have practical consequences: for instance, they show that optimal GP predictions in the sense of leave-one-out loss may occur at very large length-scales, which would be invisible to current implementations because of numerical difficulties.

Dynamic light scattering techniques are routinely used for numerous industrial and research applications, because they can give access to the motion spectrum of micro- and nano-objects, and therefore to particle sizes or visco-elastic properties. However, measurements are impossible when samples do not scatterer light enough, i.e. when there are too few scattering events due to excessively small scattering cross-sections and/or low concentrations of scatterers. Here, we propose to amplify light scattering efficiency by placing weakly scattering samples inside a Lambertian cavity with high reflectance walls. It produces a 3D isotropic and homogeneous light field that effectively elongates the scattering pathlength by 2 to 3 orders of magnitude, and leads to a dramatic increase in sensitivity. We could indeed measure the diffusion coefficient and size of particles ranging from 5nm to 20 microns with volume fractions as low at 10^(-9) in volumes as low as 100 microliters, and in solvents with refractive index mismatches down to 0.01. With a 10^(4) fold increase in sensitivity compared to classical techniques, we considerably expand the applications of light scattering to highly diluted samples, miniaturized microfluidics samples, and samples practically deemed non-scattering. Beyond the realm of current applications of light scattering techniques, our Cavity Amplified Scattering Spectroscopy method (CASS) and its outstanding sensitivity represent a major methodological step towards the study of problems such as the ballistic limit of Brownian motion, the internal dynamics of proteins, or the low frequency dielectric dynamics of liquids.

Large dimensional least-squares and regularised least-squares problems are expensive to solve. There exist many approximate techniques, some deterministic (like conjugate gradient), some stochastic (like stochastic gradient descent). Among the latter, a new class of techniques uses Determinantal Point Processes (DPPs) to produce unbiased estimators of the solution. In particular, they can be used to perform Tikhonov regularization on graphs using random spanning forests, a specific DPP. While the unbiasedness of these algorithms is attractive, their variance can be high. We show here that variance can be reduced by combining the stochastic estimator with a deterministic gradient-descent step, while keeping the property of unbiasedness. We apply this technique to Tikhonov regularization on graphs, where the reduction in variance is found to be substantial at very small extra cost.

Optical interferometry has proven extremely powerful to investigate some of the most fundamental laws of physics, using light with very precisely controlled geometry. In the past few decades, various speckle metrology methods have emerged to harness the interferometric properties of strongly disordered light instead, using time-domain analysis of speckle patterns at a maximum rate limited by the frequency of image acquisition. The present work is based on using a centimeter-sized quartz-powder cavity with an arbitrary shape that is engineered with very high Lambertian reflectivity. When filled with a coherent monochromatic photon gas, a statistically isotropic and homogeneous 3D speckle interference pattern is obtained. A single-mode fiber is then used in combination with photon number autocorrelation analysis to detect minute changes of the speckle decorrelation spectrum, caused either by cavity deformations or fluctuations of the dielectric tensor field inside. The decorrelation spectrum is acquired over 8 to 10 frequency decades below 100 MHz, with a sensitivity that is only limited by the intrinsic photon statistics and the extrinsic instrumental noises. With typically 1700 reflections and an average photon transit path length of 62m, our 3D stochastic interferometer yields a typical finesse of 10500, and cavity deformations are detected in an ergodic fashion over a six-decade dynamic range with a power noise floor of 4x{10}^{-3} pm^2 which corresponds to 2.7 pm at 1 kHz. The cavity also operates as a speckle fluctuation amplifier that reveals decorrelation spectra due to picometric thermal motions of colloids in both single and multiple scattering regimes with a typical 100-fold sensitivity gain compared to conventional light scattering techniques., Comment: 12 pages main, 27 pages with annex, 4 figures

Unintended biases in machine learning (ML) models are among the major concerns that must be addressed to maintain public trust in ML. In this paper, we address process fairness of ML models that consists in reducing the dependence of models on sensitive features, without compromising their performance. We revisit the framework FixOut that is inspired in the approach "fairness through unawareness" to build fairer models. We introduce several improvements such as automating the choice of FixOut's parameters. Also, FixOut was originally proposed to improve fairness of ML models on tabular data. We also demonstrate the feasibility of FixOut's workflow for models on textual data. We present several experimental results that illustrate the fact that FixOut improves process fairness on different classification settings., Comment: 10 pages, 2 figures, 11 tables, to be published in DSAA 2021

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., Comment: Most of this material first appeared in arXiv:2007.04117, which has been split into two. The presentation has been simplified and some material is new

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., Comment: Most of this material appeared in a previous arxiv submission (arXiv:2007.04117), two sections are new, and some things have been rephrased

Structure from Motion (SfM) often fails to estimate accurate poses in environments that lack suitable visual features. In such cases, the quality of the final 3D mesh, which is contingent on the accuracy of those estimates, is reduced. One way to overcome this problem is to combine data from a monocular camera with that of a LIDAR. This allows fine details and texture to be captured while still accurately representing featureless subjects. However, fusing these two sensor modalities is challenging due to their fundamentally different characteristics. Rather than directly fusing image features and LIDAR points, we propose to leverage common geometric features that are detected in both the LIDAR scans and image data, allowing data from the two sensors to be processed in a higher-level space. In particular, we propose to find correspondences between 3D lines extracted from LIDAR scans and 2D lines detected in images before performing a bundle adjustment to refine poses. We also exploit the detected and optimized line segments to improve the quality of the final mesh. We test our approach on the recently published dataset, Newer College Dataset. We compare the accuracy and the completeness of the 3D mesh to a ground truth obtained with a survey-grade 3D scanner. We show that our method delivers results that are comparable to a state-of-the-art LIDAR survey while not requiring highly accurate ground truth pose estimates.

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.