OpenRaiser/Intern-Atlas huggingface dataset:
Compressive Computed Tomography Reconstruction through Denoising Approximate Message Passing
Venue: arXiv cs.DS 2020
Year: 2020

X-ray Computed Tomography (CT) reconstruction from a sparse number of views is a useful way to reduce either the radiation dose or the acquisition time, for example in fixed-gantry CT systems, however this results in an ill-posed inverse problem whose solution is typically computationally demanding. Approximate Message Passing (AMP) techniques represent the state of the art for solving under-sampling Compressed Sensing problems with random linear measurements but there are still not clear solutions on how AMP should be modified and how it performs with real world problems. This paper investigates the question of whether we can employ an AMP framework for real sparse view CT imaging? The proposed algorithm for approximate inference in tomographic reconstruction incorporates a number of advances from within the AMP community, resulting in the Denoising Generalized Approximate Message Passing CT algorithm (D-GAMP-CT). Specifically, this exploits the use of sophisticated image denoisers to regularize the reconstruction. While in order to reduce the probability of divergence the (Radon) system and Poisson non-linear noise model are treated separately, exploiting the existence of efficient preconditioners for the former and the generalized noise modelling in GAMP for the latter. Experiments with simulated and real CT baggage scans confirm that the performance of the proposed algorithm outperforms statistical CT optimization solvers.
Semiring Programming: A Declarative Framework for Generalized Sum Product Problems
Venue: arXiv cs.AI 2020
Year: 2020

To solve hard problems, AI relies on a variety of disciplines such as logic, probabilistic reasoning, machine learning and mathematical programming. Although it is widely accepted that solving real-world problems requires an integration amongst these, contemporary representation methodologies offer little support for this. In an attempt to alleviate this situation, we introduce a new declarative programming framework that provides abstractions of well-known problems such as SAT, Bayesian inference, generative models, and convex optimization. The semantics of programs is defined in terms of first-order structures with semiring labels, which allows us to freely combine and integrate problems from different AI disciplines.
The Power of Data Reduction for Matching
Venue: arXiv cs.DS 2020
Year: 2020

Finding maximum-cardinality matchings in undirected graphs is arguably one of the most central graph primitives. For $m$-edge and $n$-vertex graphs, it is well-known to be solvable in $O(m\sqrt{n})$ time; however, for several applications this running time is still too slow. We investigate how linear-time (and almost linear-time) data reduction (used as preprocessing) can alleviate the situation. More specifically, we focus on (almost) linear-time kernelization. We start a deeper and systematic study both for general graphs and for bipartite graphs. Our data reduction algorithms easily comply (in form of preprocessing) with every solution strategy (exact, approximate, heuristic), thus making them attractive in various settings.
Improved Parallel Construction of Wavelet Trees and Rank/Select Structures
Venue: arXiv cs.DC 2020
Year: 2020

Existing parallel algorithms for wavelet tree construction have a work complexity of $O(n\logσ)$. This paper presents parallel algorithms for the problem with improved work complexity. Our first algorithm is based on parallel integer sorting and has either $O(n\log\log n\lceil\logσ/\sqrt{\log n\log\log n}\rceil)$ work and polylogarithmic depth, or $O(n\lceil\logσ/\sqrt{\log n}\rceil)$ work and sub-linear depth. We also describe another algorithm that has $O(n\lceil\logσ/\sqrt{\log n} \rceil)$ work and $O(σ+\log n)$ depth. We then show how to use similar ideas to construct variants of wavelet trees (arbitrary-shaped binary trees and multiary trees) as well as wavelet matrices in parallel with lower work complexity than prior algorithms. Finally, we show that the rank and select structures on binary sequences and multiary sequences, which are stored on wavelet tree nodes, can be constructed in parallel with improved work bounds, matching those of the best existing sequential algorithms for constructing rank and select structures.
Supervised-Learning-Aided Communication Framework for MIMO Systems with Low-Resolution ADCs
Venue: arXiv cs.IT 2020
Year: 2020

This paper considers a multiple-input-multiple-output (MIMO) system with low-resolution analog-to-digital converters (ADCs). In this system, we propose a novel communication framework that is inspired by supervised learning. The key idea of the proposed framework is to learn the non-linear input-output system, formed by the concatenation of a wireless channel and a quantization function used at the ADCs, for data detection. In this framework, a conventional channel estimation process is replaced by a system learning process, in which the conditional probability mass functions (PMFs) of the nonlinear system are empirically learned by sending the repetitions of all possible data signals as pilot signals. Then the subsequent data detection process is performed based on the empirical conditional PMFs obtained during the system learning. To reduce both the training overhead and the detection complexity, we also develop a supervised-learning-aided successive-interference-cancellation method. In this method, a data signal vector is divided into two subvectors with reduced dimensions. Then these two subvectors are successively detected based on the conditional PMFs that are learned using artificial noise signals and an estimated channel. For the case of one-bit ADCs, we derive an analytical expression for vector-error-rate of the proposed framework under perfect channel knowledge at the receiver. Simulations demonstrate the detection error reduction of the proposed framework compared to conventional detection techniques that are based on channel estimation.
Sums of Uncertainty: Refinements Go Gradual
Venue: arXiv cs.PL 2020
Year: 2020

A long-standing shortcoming of statically typed functional languages is that type checking does not rule out pattern-matching failures (run-time match exceptions). Refinement types distinguish different values of datatypes; if a program annotated with refinements passes type checking, pattern-matching failures become impossible. Unfortunately, refinement is a monolithic property of a type, exacerbating the difficulty of adding refinement types to nontrivial programs. Gradual typing has explored how to incrementally move between static typing and dynamic typing. We develop a type system of gradual sums that combines refinement with imprecision. Then, we develop a bidirectional version of the type system, which rules out excessive imprecision, and give a type-directed translation to a target language with explicit casts. We prove that the static sublanguage cannot have match failures, that a well-typed program remains well-typed if its type annotations are made less precise, and that making annotations less precise causes target programs to fail later. Several of these results correspond to criteria for gradual typing given by Siek et al. (2015).
How to overcome the Courant-Friedrichs-Lewy condition of explicit discretizations?
Venue: arXiv cs.NA 2020
Year: 2020

This manuscript contains some thoughts on the discretization of the classical heat equation. Namely, we discuss the advantages and disadvantages of explicit and implicit schemes. Then, we show how to overcome some disadvantages while preserving some advantages. However, since there is no free lunch, there is a price to pay for any improvement in the numerical scheme. This price will be thoroughly discussed below. In particular, we like explicit discretizations for the ease of their implementation even for nonlinear problems. Unfortunately, when these schemes are applied to parabolic equations, severe stability limits appear for the time step magnitude making the explicit simulations prohibitively expensive. Implicit schemes remove the stability limit, but each time step requires now the solution of linear (at best) or even nonlinear systems of equations. However, there exists a number of tricks to overcome (or at least to relax) severe stability limitations of explicit schemes without going into the trouble of fully implicit ones. The purpose of this manuscript is just to inform the readers about these alternative techniques to extend the stability limits. It was not written for classical scientific publication purposes.
GOTM: a Goal-Oriented Framework for Capturing Uncertainty of Medical Treatments
Venue: arXiv cs.AI 2020
Year: 2020

It has been widely recognized that uncertainty is an inevitable aspect of diagnosis and treatment of medical disorders. Such uncertainties hence, need to be considered in computerized medical models. The existing medical modeling techniques however, have mainly focused on capturing uncertainty associated with diagnosis of medical disorders while ignoring uncertainty of treatments. To tackle this issue, we have proposed using a fuzzy-based modeling and description technique for capturing uncertainties in treatment plans. We have further contributed a formal framework which allows for goal-oriented modeling and analysis of medical treatments.
Mobile Data Transactions in Device-to-Device Communication Networks: Pricing and Auction
Venue: arXiv cs.NI 2020
Year: 2020

Device-to-Device (D2D) communication is offering smart phone users a choice to share files with each other without communicating with the cellular network. In this paper, we discuss the behaviors of two characters in the D2D data transaction model from an economic point of view: the data buyers who wish to buy a certain quantity of data, as well as the data sellers who wish to sell data through the D2D network. The optimal price and purchasing strategies are analyzed and deduced based on game theory.
Complex Network Theoretical Analysis on Information Dissemination over Vehicular Networks
Venue: arXiv cs.NI 2020
Year: 2020

How to enhance the communication efficiency and quality on vehicular networks is one critical important issue. While with the larger and larger scale of vehicular networks in dense cities, the real-world datasets show that the vehicular networks essentially belong to the complex network model. Meanwhile, the extensive research on complex networks has shown that the complex network theory can both provide an accurate network illustration model and further make great contributions to the network design, optimization and management. In this paper, we start with analyzing characteristics of a taxi GPS dataset and then establishing the vehicular-to-infrastructure, vehicle-to-vehicle and the hybrid communication model, respectively. Moreover, we propose a clustering algorithm for station selection, a traffic allocation optimization model and an information source selection model based on the communication performances and complex network theory.
Extensible Datasort Refinements
Venue: arXiv cs.PL 2020
Year: 2020

Refinement types turn typechecking into lightweight verification. The classic form of refinement type is the datasort refinement, in which datasorts identify subclasses of inductive datatypes. Existing type systems for datasort refinements require that all the refinements of a type be specified when the type is declared; multiple refinements of the same type can be obtained only by duplicating type definitions, and consequently, duplicating code. We enrich the traditional notion of a signature, which describes the inhabitants of datasorts, to allow re-refinement via signature extension, without duplicating definitions. Since arbitrary updates to a signature can invalidate the inversion principles used to check case expressions, we develop a definition of signature well-formedness that ensures that extensions maintain existing inversion principles. This definition allows different parts of a program to extend the same signature in different ways, without conflicting with each other. Each part can be type-checked independently, allowing separate compilation.
Deep Neural Networks for Czech Multi-label Document Classification
Venue: arXiv cs.CL 2020
Year: 2020

This paper is focused on automatic multi-label document classification of Czech text documents. The current approaches usually use some pre-processing which can have negative impact (loss of information, additional implementation work, etc). Therefore, we would like to omit it and use deep neural networks that learn from simple features. This choice was motivated by their successful usage in many other machine learning fields. Two different networks are compared: the first one is a standard multi-layer perceptron, while the second one is a popular convolutional network. The experiments on a Czech newspaper corpus show that both networks significantly outperform baseline method which uses a rich set of features with maximum entropy classifier. We have also shown that convolutional network gives the best results.
Basis to develop a platform for multiple-scale complex systems modeling and visualization: MoNet
Venue: arXiv cs.SE 2020
Year: 2020

This work presents some characteristics of MoNet, a digital platform for the modeling and visualization of complex systems. Emphasis is on the ideas that allowed the successful progressive development of this modeling platform, which goes along with the implementation of applications to the modeling of several studied systems. The platform can represent different aspects of systems modeled at different observation scales. This tool offers advantages in the sense of favoring the perception of the phenomenon of the emergence of information, associated with changes of scale. This paper also includes some criteria used for the construction of this modeling platform. The power of current computers has made practical representing graphic resources such as shapes, line thickness, overlaying-text tags, colors, and transparencies, in the graphical modeling of systems. By visualizing diagrams conveniently designed to highlight contrasts, these modeling platforms allow the recognition of patterns that drive our understanding of systems and their structure. Graphs reflecting the benefits of the tool regarding the visualization of systems at different scales of observation are presented to illustrate the application of the platform.
Improved Converses and Gap Results for Coded Caching
Venue: arXiv cs.IT 2020
Year: 2020

Improved lower bounds on the average and the worst-case rate-memory tradeoffs for the Maddah-Ali&Niesen coded caching scenario are presented. For any number of users and files and for arbitrary cache sizes, the multiplicative gap between the exact rate-memory tradeoff and the new lower bound is less than 2.315 in the worst-case scenario and less than 2.507 in the average-case scenario.
GNSS Signal Authentication via Power and Distortion Monitoring
Venue: arXiv cs.CR 2020
Year: 2020

We propose a simple low-cost technique that enables civil Global Positioning System (GPS) receivers and other civil global navigation satellite system (GNSS) receivers to reliably detect carry-off spoofing and jamming. The technique, which we call the Power-Distortion detector, classifies received signals as interference-free, multipath-afflicted, spoofed, or jammed according to observations of received power and correlation function distortion. It does not depend on external hardware or a network connection and can be readily implemented on many receivers via a firmware update. Crucially, the detector can with high probability distinguish low-power spoofing from ordinary multipath. In testing against over 25 high-quality empirical data sets yielding over 900,000 separate detection tests, the detector correctly alarms on all malicious spoofing or jamming attacks while maintaining a <0.6% single-channel false alarm rate.
Convex Relaxations of Chance Constrained AC Optimal Power Flow
Venue: arXiv cs.SY 2020
Year: 2020

High penetration of renewable energy sources and the increasing share of stochastic loads require the explicit representation of uncertainty in tools such as the optimal power flow (OPF). Current approaches follow either a linearized approach or an iterative approximation of non-linearities. This paper proposes a semidefinite relaxation of a chance constrained AC-OPF which is able to provide guarantees for global optimality. Using a piecewise affine policy, we can ensure tractability, accurately model large power deviations, and determine suitable corrective control policies for active power, reactive power, and voltage. We state a tractable formulation for two types of uncertainty sets. Using a scenario-based approach and making no prior assumptions about the probability distribution of the forecast errors, we obtain a robust formulation for a rectangular uncertainty set. Alternatively, assuming a Gaussian distribution of the forecast errors, we propose an analytical reformulation of the chance constraints suitable for semidefinite programming. We demonstrate the performance of our approach on the IEEE 24 and 118 bus system using realistic day-ahead forecast data and obtain tight near-global optimality guarantees.
Deep Forest
Venue: arXiv cs.LG 2020
Year: 2020

Current deep learning models are mostly build upon neural networks, i.e., multiple layers of parameterized differentiable nonlinear modules that can be trained by backpropagation. In this paper, we explore the possibility of building deep models based on non-differentiable modules. We conjecture that the mystery behind the success of deep neural networks owes much to three characteristics, i.e., layer-by-layer processing, in-model feature transformation and sufficient model complexity. We propose the gcForest approach, which generates \textit{deep forest} holding these characteristics. This is a decision tree ensemble approach, with much less hyper-parameters than deep neural networks, and its model complexity can be automatically determined in a data-dependent way. Experiments show that its performance is quite robust to hyper-parameter settings, such that in most cases, even across different data from different domains, it is able to get excellent performance by using the same default setting. This study opens the door of deep learning based on non-differentiable modules, and exhibits the possibility of constructing deep models without using backpropagation.
On recursive computation of coprime factorizations of rational matrices
Venue: arXiv cs.SY 2020
Year: 2020

General computational methods based on descriptor state-space realizations are proposed to compute coprime factorizations of rational matrices with minimum degree denominators. The new methods rely on recursive pole dislocation techniques, which allow to successively place all poles of the factors into a "good" region of the complex plane. The resulting McMillan degree of the denominator factor is equal to the number of poles lying in the complementary "bad" region and therefore is minimal. The developed pole dislocation techniques are instrumental for devising numerically reliable procedures for the computation of coprime factorizations with proper and stable factors of arbitrary improper rational matrices and coprime factorizations with inner denominators. Implementation aspects of the proposed algorithms are discussed and illustrative examples are given.
A survey of embedding models of entities and relationships for knowledge graph completion
Venue: arXiv cs.CL 2020
Year: 2020

Knowledge graphs (KGs) of real-world facts about entities and their relationships are useful resources for a variety of natural language processing tasks. However, because knowledge graphs are typically incomplete, it is useful to perform knowledge graph completion or link prediction, i.e. predict whether a relationship not in the knowledge graph is likely to be true. This paper serves as a comprehensive survey of embedding models of entities and relationships for knowledge graph completion, summarizing up-to-date experimental results on standard benchmark datasets and pointing out potential future research directions.
Sparse Signal Recovery via Generalized Entropy Functions Minimization
Venue: arXiv cs.IT 2020
Year: 2020

Compressive sensing relies on the sparse prior imposed on the signal of interest to solve the ill-posed recovery problem in an under-determined linear system. The objective function used to enforce the sparse prior information should be both effective and easily optimizable. Motivated by the entropy concept from information theory, in this paper we propose the generalized Shannon entropy function and Rényi entropy function of the signal as the sparsity promoting regularizers. Both entropy functions are nonconvex, non-separable. Their local minimums only occur on the boundaries of the orthants in the Euclidean space. Compared to other popular objective functions, minimizing the generalized entropy functions adaptively promotes multiple high-energy coefficients while suppressing the rest low-energy coefficients. The corresponding optimization problems can be recasted into a series of reweighted $l_1$-norm minimization problems and then solved efficiently by adapting the FISTA. Sparse signal recovery experiments on both the simulated and real data show the proposed entropy functions minimization approaches perform better than other popular approaches and achieve state-of-the-art performances.
A Proof of the CSP Dichotomy Conjecture
Venue: arXiv cs.CC 2020
Year: 2020

Many natural combinatorial problems can be expressed as constraint satisfaction problems. This class of problems is known to be NP-complete in general, but certain restrictions on the form of the constraints can ensure tractability. The standard way to parameterize interesting subclasses of the constraint satisfaction problem is via finite constraint languages. The main problem is to classify those subclasses that are solvable in polynomial time and those that are NP-complete. It was conjectured that if a constraint language has a weak near unanimity polymorphism then the corresponding constraint satisfaction problem is tractable, otherwise it is NP-complete. In the paper we present an algorithm that solves Constraint Satisfaction Problem in polynomial time for constraint languages having a weak near unanimity polymorphism, which proves the remaining part of the conjecture.
A MALL Geometry of Interaction Based on Indexed Linear Logic
Venue: arXiv cs.LO 2020
Year: 2020

We construct a geometry of interaction (GoI: dynamic modeling of Gentzen-style cut elimination) for multiplicative-additive linear logic (MALL) by employing Bucciarelli-Ehrhard indexed linear logic MALL(I) to handle the additives. Our construction is an extension to the additives of the Haghverdi-Scott categorical formulation (a multiplicative GoI situation in a traced monoidal category) for Girard's original GoI 1. The indices are shown to serve not only in their original denotational level, but also at a finer grained dynamic level so that the peculiarities of additive cut elimination such as superposition, erasure of subproofs, and additive (co-) contraction can be handled with the explicit use of indices. Proofs are interpreted as indexed subsets in the category Rel, but without the explicit relational composition; instead, execution formulas are run pointwise on the interpretation at each index, w.r.t symmetries of cuts, in a traced monoidal category with a reflexive object and a zero morphism. The sets of indices diminish overall when an execution formula is run, corresponding to the additive cut-elimination procedure (erasure), and allowing recovery of the relational composition. The main theorem is the invariance of the execution formulas along cut elimination so that the formulas converge to the denotations of (cut-free) proofs.