OpenRaiser/Intern-Atlas huggingface dataset:
A Geometric Framework for Stochastic Shape Analysis
Venue: arXiv cs.CV 2018
Year: 2018

We introduce a stochastic model of diffeomorphisms, whose action on a variety of data types descends to stochastic evolution of shapes, images and landmarks. The stochasticity is introduced in the vector field which transports the data in the Large Deformation Diffeomorphic Metric Mapping (LDDMM) framework for shape analysis and image registration. The stochasticity thereby models errors or uncertainties of the flow in following the prescribed deformation velocity. The approach is illustrated in the example of finite dimensional landmark manifolds, whose stochastic evolution is studied both via the Fokker-Planck equation and by numerical simulations. We derive two approaches for inferring parameters of the stochastic model from landmark configurations observed at discrete time points. The first of the two approaches matches moments of the Fokker-Planck equation to sample moments of the data, while the second approach employs an Expectation-Maximisation based algorithm using a Monte Carlo bridge sampling scheme to optimise the data likelihood. We derive and numerically test the ability of the two approaches to infer the spatial correlation length of the underlying noise.
A minimal representation for continuous functions
Venue: arXiv cs.LO 2018
Year: 2018

Kawamura and Cook specified the least set of information about a continuous function on the unit interval which is needed for fast function evaluation. This paper presents a variation of their result. To make the above statement precise, one has to specify what a "set of information" is and what "fast" should mean. Kawamura and Cook use polynomial-time computability in the sense of second-order complexity theory to define what "fast" means but do not use the most general "sets of information" this framework is able to handle. Instead they require codes to be length-monotone. This paper removes the additional premise of length-monotonicity, and instead imposes further conditions on the speed of the evaluation: The operation should now be computable in "hyper-linear" time. This means that the running time can not contain any iterations of the length function and, while an arbitrary polynomial may be applied to its value, on the argument side at most a shift by a constant is allowed. This is a very restrictive notion, but one can check that the Kawamura and Cook representation allows for hyper-linear time evaluation. The paper proves that it is not minimal with this property by providing the minimal set of information necessary for hyper-linear evaluation and proving that it is not polynomial-time equivalent to any encoding using only length-monotone names. Ultimatively, this is due to a failure of polynomial-time computability of an upper bound to a modulus of continuity. Indeed this failure seems to reflect the behavior of software based on the ideas of computable analysis appropriately and was one of the reasons for a closer investigation in the first place.
An improved explicit scheme for whole-building hygrothermal simulation
Venue: arXiv cs.CE 2018
Year: 2018

Implicit schemes require important sub-iterations when dealing with highly nonlinear problems such as the combined heat and moisture transfer through porous building elements. The computational cost rises significantly when the whole-building is simulated, especially when there is important coupling among the building elements themselves with neighbouring zones and with HVAC (Heating Ventilation and Air Conditioning) systems. On the other hand, the classical Euler explicit scheme is generally not used because its stability condition imposes very fine time discretisation. Hence, this paper explores the use of an improved explicit approach - the Dufort-Frankel scheme - to overcome the disadvantage of the classical explicit one and to bring benefits that cannot be obtained by implicit methods. The Dufort-Frankel approach is first compared to the classical Euler implicit and explicit schemes to compute the solution of nonlinear heat and moisture transfer through porous materials. Then, the analysis of the Dufort-Frankel unconditionally stable explicit scheme is extended to the coupled heat and moisture balances on the scale of a one- and a two-zone building models. The Dufort-Frankel scheme has the benefits of being unconditionally stable, second-order accurate in time O(dt^2) and to compute explicitly the solution at each time step, avoiding costly sub-iterations. This approach may reduce the computational cost by twenty, as well as it may enable perfect synchronism for whole-building simulation and co-simulation.
Born to Learn: the Inspiration, Progress, and Future of Evolved Plastic Artificial Neural Networks
Venue: arXiv cs.NE 2018
Year: 2018

Biological plastic neural networks are systems of extraordinary computational capabilities shaped by evolution, development, and lifetime learning. The interplay of these elements leads to the emergence of adaptive behavior and intelligence. Inspired by such intricate natural phenomena, Evolved Plastic Artificial Neural Networks (EPANNs) use simulated evolution in-silico to breed plastic neural networks with a large variety of dynamics, architectures, and plasticity rules: these artificial systems are composed of inputs, outputs, and plastic components that change in response to experiences in an environment. These systems may autonomously discover novel adaptive algorithms, and lead to hypotheses on the emergence of biological adaptation. EPANNs have seen considerable progress over the last two decades. Current scientific and technological advances in artificial neural networks are now setting the conditions for radically new approaches and results. In particular, the limitations of hand-designed networks could be overcome by more flexible and innovative solutions. This paper brings together a variety of inspiring ideas that define the field of EPANNs. The main methods and results are reviewed. Finally, new opportunities and developments are presented.
Advanced Quantizer Designs for FDD-Based FD-MIMO Systems Using Uniform Planar Arrays
Venue: arXiv cs.IT 2018
Year: 2018

Massive multiple-input multiple-output (MIMO) systems, which utilize a large number of antennas at the base station, are expected to enhance network throughput by enabling improved multiuser MIMO techniques. To deploy many antennas in reasonable form factors, base stations are expected to employ antenna arrays in both horizontal and vertical dimensions, which is known as full-dimension (FD) MIMO. The most popular two-dimensional array is the uniform planar array (UPA), where antennas are placed in a grid pattern. To exploit the full benefit of massive MIMO in frequency division duplexing (FDD), the downlink channel state information (CSI) should be estimated, quantized, and fed back from the receiver to the transmitter. However, it is difficult to accurately quantize the channel in a computationally efficient manner due to the high dimensionality of the massive MIMO channel. In this paper, we develop both narrowband and wideband CSI quantizers for FD-MIMO taking the properties of realistic channels and the UPA into consideration. To improve quantization quality, we focus on not only quantizing dominant radio paths in the channel, but also combining the quantized beams. We also develop a hierarchical beam search approach, which scans both vertical and horizontal domains jointly with moderate computational complexity. Numerical simulations verify that the performance of the proposed quantizers is better than that of previous CSI quantization techniques.
A Two-Step Distribution System State Estimator with Grid Constraints and Mixed Measurements
Venue: arXiv cs.SY 2018
Year: 2018

In this work we study the problem of State Estimation(SE) in large-scale, 3-phase coupled, unbalanced distribution systems. More specifically, we address the problem of including mixed real-time measurements, synchronized and unsynchronized, from phasor measurement units and smart meters, into existing solutions. We propose a computationally efficient two-step method to update a prior solution using the measurements, while taking into account physical constraint caused by buses with no loads. We test the method on a benchmark test feeder to illustrate the effectiveness of the approach.
Audio-Visual Speech Enhancement Using Multimodal Deep Convolutional Neural Networks
Venue: arXiv cs.SD 2018
Year: 2018

Speech enhancement (SE) aims to reduce noise in speech signals. Most SE techniques focus only on addressing audio information. In this work, inspired by multimodal learning, which utilizes data from different modalities, and the recent success of convolutional neural networks (CNNs) in SE, we propose an audio-visual deep CNNs (AVDCNN) SE model, which incorporates audio and visual streams into a unified network model. We also propose a multi-task learning framework for reconstructing audio and visual signals at the output layer. Precisely speaking, the proposed AVDCNN model is structured as an audio-visual encoder-decoder network, in which audio and visual data are first processed using individual CNNs, and then fused into a joint network to generate enhanced speech (the primary task) and reconstructed images (the secondary task) at the output layer. The model is trained in an end-to-end manner, and parameters are jointly learned through back-propagation. We evaluate enhanced speech using five instrumental criteria. Results show that the AVDCNN model yields a notably superior performance compared with an audio-only CNN-based SE model and two conventional SE approaches, confirming the effectiveness of integrating visual information into the SE process. In addition, the AVDCNN model also outperforms an existing audio-visual SE model, confirming its capability of effectively combining audio and visual information in SE.
BB8: A Scalable, Accurate, Robust to Partial Occlusion Method for Predicting the 3D Poses of Challenging Objects without Using Depth
Venue: arXiv cs.CV 2018
Year: 2018

We introduce a novel method for 3D object detection and pose estimation from color images only. We first use segmentation to detect the objects of interest in 2D even in presence of partial occlusions and cluttered background. By contrast with recent patch-based methods, we rely on a "holistic" approach: We apply to the detected objects a Convolutional Neural Network (CNN) trained to predict their 3D poses in the form of 2D projections of the corners of their 3D bounding boxes. This, however, is not sufficient for handling objects from the recent T-LESS dataset: These objects exhibit an axis of rotational symmetry, and the similarity of two images of such an object under two different poses makes training the CNN challenging. We solve this problem by restricting the range of poses used for training, and by introducing a classifier to identify the range of a pose at run-time before estimating it. We also use an optional additional step that refines the predicted poses. We improve the state-of-the-art on the LINEMOD dataset from 73.7% to 89.3% of correctly registered RGB frames. We are also the first to report results on the Occlusion dataset using color images only. We obtain 54% of frames passing the Pose 6D criterion on average on several sequences of the T-LESS dataset, compared to the 67% of the state-of-the-art on the same sequences which uses both color and depth. The full approach is also scalable, as a single network can be trained for multiple objects simultaneously.
Local Algorithms for Hierarchical Dense Subgraph Discovery
Venue: arXiv cs.SI 2018
Year: 2018

Finding the dense regions of a graph and relations among them is a fundamental problem in network analysis. Core and truss decompositions reveal dense subgraphs with hierarchical relations. The incremental nature of algorithms for computing these decompositions and the need for global information at each step of the algorithm hinders scalable parallelization and approximations since the densest regions are not revealed until the end. In a previous work, Lu et al. proposed to iteratively compute the $h$-indices of neighbor vertex degrees to obtain the core numbers and prove that the convergence is obtained after a finite number of iterations. This work generalizes the iterative $h$-index computation for truss decomposition as well as nucleus decomposition which leverages higher-order structures to generalize core and truss decompositions. In addition, we prove convergence bounds on the number of iterations. We present a framework of local algorithms to obtain the core, truss, and nucleus decompositions. Our algorithms are local, parallel, offer high scalability, and enable approximations to explore time and quality trade-offs. Our shared-memory implementation verifies the efficiency, scalability, and effectiveness of our local algorithms on real-world networks.
Faster Base64 Encoding and Decoding Using AVX2 Instructions
Venue: arXiv cs.MS 2018
Year: 2018

Web developers use base64 formats to include images, fonts, sounds and other resources directly inside HTML, JavaScript, JSON and XML files. We estimate that billions of base64 messages are decoded every day. We are motivated to improve the efficiency of base64 encoding and decoding. Compared to state-of-the-art implementations, we multiply the speeds of both the encoding (~10x) and the decoding (~7x). We achieve these good results by using the single-instruction-multiple-data (SIMD) instructions available on recent Intel processors (AVX2). Our accelerated software abides by the specification and reports errors when encountering characters outside of the base64 set. It is available online as free software under a liberal license.
Brief Notes on Hard Takeoff, Value Alignment, and Coherent Extrapolated Volition
Venue: arXiv cs.AI 2018
Year: 2018

I make some basic observations about hard takeoff, value alignment, and coherent extrapolated volition, concepts which have been central in analyses of superintelligent AI systems.
Finite State Multiple-Access Wiretap Channel with Delayed Feedback
Venue: arXiv cs.IT 2018
Year: 2018

Recently, it has been shown that the time-varying multiple-access channel (MAC) with perfect channel state information (CSI) at the receiver and delayed feedback CSI at the transmitters can be modeled as the finite state MAC (FS-MAC) with delayed state feedback, where the time variation of the channel is characterized by the statistics of the underlying state process. To study the fundamental limit of the secure transmission over multi-user wireless communication systems, we re-visit the FS-MAC with delayed state feedback by considering an external eavesdropper, which we call the finite state multiple-access wiretap channel (FS-MAC-WT) with delayed feedback. The main contribution of this paper is to show that taking full advantage of the delayed channel output feedback helps to increase the secrecy rate region of the FS-MAC-WT with delayed state feedback, and the results of this paper are further illustrated by a degraded Gaussian fading example.
Using Convolutional Codes for Key Extraction in SRAM Physical Unclonable Functions
Venue: arXiv cs.IT 2018
Year: 2018

Physical Unclonable Functions (PUFs) exploit variations in the manufacturing process to derive bit sequences from integrated circuits, which can be used as secure cryptographic keys. Instead of storing the keys in an insecure, non-volatile memory, they can be reproduced when needed. Since the reproduced sequences are not stable due to physical reasons, error correction must be applied. Recently, convolutional codes were shown to be suitable for key reproduction in PUFs based on SRAM. This work shows how to further decrease the reconstruction failure probability and PUF implementation size using codes with larger memory length and decoding concepts such as soft-information and list decoding.
Decentralizing MVCC by Leveraging Visibility
Venue: arXiv cs.DB 2018
Year: 2018

Multiversion Concurrency Control (MVCC) is a widely adopted concurrency control mechanism in database systems, which usually utilizes timestamps to resolve conflicts between transactions. However, centralized allocation of timestamps is a potential bottleneck for parallel transaction management. This bottleneck is becoming increasingly visible with the rapidly growing degree of parallelism of today's computing platforms. This paper introduces Visibility based Concurrency Control (ViCC), a series of CC mechanisms that allow transactions to determine their timestamps autonomously, without relying on centralized coordination. As such, ViCC can scale well, rendering it suitable for various multicore and MPP platforms. Extensive experiments are conducted to demonstrate its advantage over existing approaches.
On the equivalence between multiclass processor sharing and random order scheduling policies
Venue: arXiv cs.PF 2018
Year: 2018

Consider a single server system serving a multiclass population. Some popular scheduling policies for such system are the discriminatory processor sharing (DPS), discriminatory random order service (DROS), generalized processor sharing (GPS) and weighted fair queueing (WFQ). In this paper, we propose two classes of policies, namely MPS (multiclass processor sharing) and MROS (multiclass random order service), that generalize the four policies mentioned above. For the special case when the multiclass population arrive according to Poisson processes and have independent and exponential service requirement with parameter $μ$, we show that the tail of the sojourn time distribution for a class $i$ customer in a system with the MPS policy is a constant multiple of the tail of the waiting time distribution of a class $i$ customer in a system with the MROS policy. This result implies that for a class $i$ customer, the tail of the sojourn time distribution in a system with the DPS (GPS) scheduling policy is a constant multiple of the tail of the waiting time distribution in a system with the DROS (respectively WFQ) policy.
Improved Decoding and Error Floor Analysis of Staircase Codes
Venue: arXiv cs.IT 2018
Year: 2018

Staircase codes play an important role as error-correcting codes in optical communications. In this paper, a low-complexity method for resolving stall patterns when decoding staircase codes is described. Stall patterns are the dominating contributor to the error floor in the original decoding method. Our improvement is based on locating stall patterns by intersecting non-zero syndromes and flipping the corresponding bits. The approach effectively lowers the error floor and allows for a new range of block sizes to be considered for optical communications at a certain rate or, alternatively, a significantly decreased error floor for the same block size. Further, an improved error floor analysis is introduced which provides a more accurate estimation of the contributions to the error floor.
Some observations on the logical foundations of inductive theorem proving
Venue: arXiv cs.LO 2018
Year: 2018

In this paper we study the logical foundations of automated inductive theorem proving. To that aim we first develop a theoretical model that is centered around the difficulty of finding induction axioms which are sufficient for proving a goal. Based on this model, we then analyze the following aspects: the choice of a proof shape, the choice of an induction rule and the language of the induction formula. In particular, using model-theoretic techniques, we clarify the relationship between notions of inductiveness that have been considered in the literature on automated inductive theorem proving. This is a corrected version of the paper arXiv:1704.01930v5 published originally on Nov.~16, 2017.
A semidiscrete version of the Citti-Petitot-Sarti model as a plausible model for anthropomorphic image reconstruction and pattern recognition
Venue: arXiv cs.CV 2018
Year: 2018

In his beautiful book [66], Jean Petitot proposes a sub-Riemannian model for the primary visual cortex of mammals. This model is neurophysiologically justified. Further developments of this theory lead to efficient algorithms for image reconstruction, based upon the consideration of an associated hypoelliptic diffusion. The sub-Riemannian model of Petitot and Citti-Sarti (or certain of its improvements) is a left-invariant structure over the group $SE(2)$ of rototranslations of the plane. Here, we propose a semi-discrete version of this theory, leading to a left-invariant structure over the group $SE(2,N)$, restricting to a finite number of rotations. This apparently very simple group is in fact quite atypical: it is maximally almost periodic, which leads to much simpler harmonic analysis compared to $SE(2).$ Based upon this semi-discrete model, we improve on previous image-reconstruction algorithms and we develop a pattern-recognition theory that leads also to very efficient algorithms in practice.
Odd Yao-Yao Graphs are Not Spanners
Venue: arXiv cs.CG 2018
Year: 2018

It is a long standing open problem whether Yao-Yao graphs $\mathsf{YY}_{k}$ are all spanners [li2002sparse]. Bauer and Damian [bauer2013infinite] showed that all $\mathsf{YY}_{6k}$ for $k \geq 6$ are spanners. Li and Zhan [li2016almost] generalized their result and proved that all even Yao-Yao graphs $\mathsf{YY}_{2k}$ are spanners (for $k\geq 42$). However, their technique cannot be extended to odd Yao-Yao graphs, and whether they are spanners are still elusive. In this paper, we show that, surprisingly, for any integer $k \geq 1$, there exist odd Yao-Yao graph $\mathsf{YY}_{2k+1}$ instances, which are not spanners.
Error Bounds for Uplink and Downlink 3D Localization in 5G mmWave Systems
Venue: arXiv cs.IT 2018
Year: 2018

Location-aware communication systems are expected to play a pivotal part in the next generation of mobile communication networks. Therefore, there is a need to understand the localization limits in these networks, particularly, using millimeter-wave technology (mmWave). Towards that, we address the uplink and downlink localization limits in terms of 3D position and orientation error bounds for mmWave multipath channels. We also carry out a detailed analysis of the dependence of the bounds of different systems parameters. Our key findings indicate that the uplink and downlink behave differently in two distinct ways. First of all, the error bounds have different scaling factors with respect to the number of antennas in the uplink and downlink. Secondly, uplink localization is sensitive to the orientation angle of the user equipment (UE), whereas downlink is not. Moreover, in the considered outdoor scenarios, the non-line-of-sight paths generally improve localization when a line-of-sight path exists. Finally, our numerical results show that mmWave systems are capable of localizing a UE with sub-meter position error, and sub-degree orientation error.
Eigenvalues of symmetric tridiagonal interval matrices revisited
Venue: arXiv cs.NA 2018
Year: 2018

In this short note, we present a novel method for computing exact lower and upper bounds of eigenvalues of a symmetric tridiagonal interval matrix. Compared to the known methods, our approach is fast, simple to present and to implement, and avoids any assumptions. Our construction explicitly yields those matrices for which particular lower and upper bounds are attained.