OpenRaiser/Intern-Atlas huggingface dataset:
Bloom Filters, Adaptivity, and the Dictionary Problem
Venue: arXiv cs.DS 2018
Year: 2018

The Bloom filter---or, more generally, an approximate membership query data structure (AMQ)---maintains a compact, probabilistic representation of a set S of keys from a universe U. An AMQ supports lookups, inserts, and (for some AMQs) deletes. A query for an x in S is guaranteed to return "present." A query for x not in S returns "absent" with probability at least 1-epsilon, where epsilon is a tunable false positive probability. If a query returns "present," but x is not in S, then x is a false positive of the AMQ. Because AMQs have a nonzero probability of false-positives, they require far less space than explicit set representations. AMQs are widely used to speed up dictionaries that are stored remotely (e.g., on disk/across a network). Most AMQs offer weak guarantees on the number of false positives they will return on a sequence of queries. The false-positive probability of epsilon holds only for a single query. It is easy for an adversary to drive an AMQ's false-positive rate towards 1 by simply repeating false positives. This paper shows what it takes to get strong guarantees on the number of false positives. We say that an AMQs is adaptive if it guarantees a false-positive probability of epsilon for every query, regardless of answers to previous queries. First, we prove that it is impossible to build a small adaptive AMQ, even when the AMQ is immediately told whenever it returns a false positive. We then show how to build an adaptive AMQ that partitions its state into a small local component and a larger remote component. In addition to being adaptive, the local component of our AMQ dominates existing AMQs in all regards. It uses optimal space up to lower-order terms and supports queries and updates in worst-case constant time, with high probability. Thus, we show that adaptivity has no cost.
ENGINE:Cost Effective Offloading in Mobile Edge Computing with Fog-Cloud Cooperation
Venue: arXiv cs.NI 2018
Year: 2018

Mobile Edge Computing (MEC) as an emerging paradigm utilizing cloudlet or fog nodes to extend remote cloud computing to the edge of the network, is foreseen as a key technology towards next generation wireless networks. By offloading computation intensive tasks from resource constrained mobile devices to fog nodes or the remote cloud, the energy of mobile devices can be saved and the computation capability can be enhanced. For fog nodes, they can rent the resource rich remote cloud to help them process incoming tasks from mobile devices. In this architecture, the benefit of short computation and computation delay of mobile devices can be fully exploited. However, existing studies mostly assume fog nodes possess unlimited computing capacity, which is not practical, especially when fog nodes are also energy constrained mobile devices. To provide incentive of fog nodes and reduce the computation cost of mobile devices, we provide a cost effective offloading scheme in mobile edge computing with the cooperation between fog nodes and the remote cloud with task dependency constraint. The mobile devices have limited budget and have to determine which task should be computed locally or sent to the fog. To address this issue, we first formulate the offloading problem as a task finish time inimization problem with given budgets of mobile devices, which is NP-hard. We then devise two more algorithms to study the network performance. Simulation results show that the proposed greedy algorithm can achieve the near optimal performance. On average, the Brute Force method and the greedy algorithm outperform the simulated annealing algorithm by about 28.13% on the application finish time.
Adaptive Beam-Frequency Allocation Algorithm with Position Uncertainty for Millimeter-Wave MIMO Systems
Venue: arXiv cs.NI 2018
Year: 2018

Envisioned for fifth generation (5G) systems, millimeter-wave (mmWave) communications are under very active research worldwide. Although pencil beams with accurate beamtracking may boost the throughput of mmWave systems, this poses great challenges in the design of radio resource allocation for highly mobile users. In this paper, we propose a joint adaptive beam-frequency allocation algorithm that takes into account the position uncertainty inherent to high mobility and/or unstable users as, e.g., Unmanned Aerial Vehicles (UAV), for whom this is a major problem. Our proposed method provides an optimized beamwidth selection under quality of service (QoS) requirements for maximizing system proportional fairness, under user position uncertainty. The rationale of our scheme is to adapt the beamwidth such that the best trade-off among system performance (narrower beam) and robustness to uncertainty (wider beam) is achieved. Simulation results show that the proposed method largely enhances the system performance compared to reference algorithms, by an appropriate adaptation of the mmWave beamwidths, even under severe uncertainties and imperfect channel state information (CSIs).
End-to-end Lung Nodule Detection in Computed Tomography
Venue: arXiv cs.CV 2018
Year: 2018

Computer aided diagnostic (CAD) system is crucial for modern med-ical imaging. But almost all CAD systems operate on reconstructed images, which were optimized for radiologists. Computer vision can capture features that is subtle to human observers, so it is desirable to design a CAD system op-erating on the raw data. In this paper, we proposed a deep-neural-network-based detection system for lung nodule detection in computed tomography (CT). A primal-dual-type deep reconstruction network was applied first to convert the raw data to the image space, followed by a 3-dimensional convolutional neural network (3D-CNN) for the nodule detection. For efficient network training, the deep reconstruction network and the CNN detector was trained sequentially first, then followed by one epoch of end-to-end fine tuning. The method was evaluated on the Lung Image Database Consortium image collection (LIDC-IDRI) with simulated forward projections. With 144 multi-slice fanbeam pro-jections, the proposed end-to-end detector could achieve comparable sensitivity with the reference detector, which was trained and applied on the fully-sampled image data. It also demonstrated superior detection performance compared to detectors trained on the reconstructed images. The proposed method is general and could be expanded to most detection tasks in medical imaging.
Social welfare and profit maximization from revealed preferences
Venue: arXiv cs.GT 2018
Year: 2018

Consider the seller's problem of finding optimal prices for her $n$ (divisible) goods when faced with a set of $m$ consumers, given that she can only observe their purchased bundles at posted prices, i.e., revealed preferences. We study both social welfare and profit maximization with revealed preferences. Although social welfare maximization is a seemingly non-convex optimization problem in prices, we show that (i) it can be reduced to a dual convex optimization problem in prices, and (ii) the revealed preferences can be interpreted as supergradients of the concave conjugate of valuation, with which subgradients of the dual function can be computed. We thereby obtain a simple subgradient-based algorithm for strongly concave valuations and convex cost, with query complexity $O(m^2/ε^2)$, where $ε$ is the additive difference between the social welfare induced by our algorithm and the optimum social welfare. We also study social welfare maximization under the online setting, specifically the random permutation model, where consumers arrive one-by-one in a random order. For the case where consumer valuations can be arbitrary continuous functions, we propose a price posting mechanism that achieves an expected social welfare up to an additive factor of $O(\sqrt{mn})$ from the maximum social welfare. Finally, for profit maximization (which may be non-convex in simple cases), we give nearly matching upper and lower bounds on the query complexity for separable valuations and cost (i.e., each good can be treated independently).
A Linear Variational Principle for Riemann Mappings and Discrete Conformality
Venue: arXiv cs.CG 2018
Year: 2018

We consider Riemann mappings from bounded Lipschitz domains in the plane to a triangle. We show that in this case the Riemann mapping has a linear variational principle: it is the minimizer of the Dirichlet energy over an appropriate affine space. By discretizing the variational principle in a natural way we obtain discrete conformal maps which can be computed by solving a sparse linear system. We show that these discrete conformal maps converge to the Riemann mapping in $H^1$, even for non-Delaunay triangulations. Additionally, for Delaunay triangulations the discrete conformal maps converge uniformly and are known to be bijective. As a consequence we show that the Riemann mapping between two bounded Lipschitz domains can be uniformly approximated by composing the Riemann mappings between each Lipschitz domain and the triangle.
Convolutional Normalizing Flows
Venue: arXiv cs.LG 2018
Year: 2018

Bayesian posterior inference is prevalent in various machine learning problems. Variational inference provides one way to approximate the posterior distribution, however its expressive power is limited and so is the accuracy of resulting approximation. Recently, there has a trend of using neural networks to approximate the variational posterior distribution due to the flexibility of neural network architecture. One way to construct flexible variational distribution is to warp a simple density into a complex by normalizing flows, where the resulting density can be analytically evaluated. However, there is a trade-off between the flexibility of normalizing flow and computation cost for efficient transformation. In this paper, we propose a simple yet effective architecture of normalizing flows, ConvFlow, based on convolution over the dimensions of random input vector. Experiments on synthetic and real world posterior inference problems demonstrate the effectiveness and efficiency of the proposed method.
Spatial Characteristics of Distortion Radiated from Antenna Arrays with Transceiver Nonlinearities
Venue: arXiv cs.IT 2018
Year: 2018

The distortion from massive MIMO (multiple-input--multiple-output) base stations with nonlinear amplifiers is studied and its radiation pattern is derived. The distortion is analyzed both in-band and out-of-band. By using an orthogonal Hermite representation of the amplified signal, the spatial cross-correlation matrix of the nonlinear distortion is obtained. It shows that, if the input signal to the amplifiers has a dominant beam, the distortion is beamformed in the same way as that beam. When there are multiple beams without any one being dominant, it is shown that the distortion is practically isotropic. The derived theory is useful to predict how the nonlinear distortion will behave, to analyze the out-of-band radiation, to do reciprocity calibration, and to schedule users in the frequency plane to minimize the effect of in-band distortion.
Remote Sensing Image Fusion Based on Two-stream Fusion Network
Venue: arXiv cs.CV 2018
Year: 2018

Remote sensing image fusion (also known as pan-sharpening) aims at generating high resolution multi-spectral (MS) image from inputs of a high spatial resolution single band panchromatic (PAN) image and a low spatial resolution multi-spectral image. Inspired by the astounding achievements of convolutional neural networks (CNNs) in a variety of computer vision tasks, in this paper, we propose a two-stream fusion network (TFNet) to address the problem of pan-sharpening. Unlike previous CNN based methods that consider pan-sharpening as a super resolution problem and perform pan-sharpening in pixel level, the proposed TFNet aims to fuse PAN and MS images in feature level and reconstruct the pan-sharpened image from the fused features. The TFNet mainly consists of three parts. The first part is comprised of two networks extracting features from PAN and MS images, respectively. The subsequent network fuses them together to form compact features that represent both spatial and spectral information of PAN and MS images, simultaneously. Finally, the desired high spatial resolution MS image is recovered from the fused features through an image reconstruction network. Experiments on Quickbird and \mbox{GaoFen-1} satellite images demonstrate that the proposed TFNet can fuse PAN and MS images, effectively, and produce pan-sharpened images competitive with even superior to state of the arts.
Fairness and Transmission-Aware Caching and Delivery Policies in OFDMA-Based HetNets
Venue: arXiv cs.IT 2018
Year: 2018

Recently, wireless edge caching has been emerged as a promising technology for future wireless networks to cope with exponentially increasing demands for high data rate and low latency multimedia services by proactively storing contents at the network edge. Here, we aim to design efficient cache placement and delivery strategies for an orthogonal frequency division multiple access (OFDMA)-based cache-enabled heterogeneous cellular network (C-HetNet) which operates in two separated phases: caching phase (CP) and delivery phase (DP). Since guaranteeing fairness among mobile users (MUs) is not well investigated in cache-assisted wireless networks, we first propose two delay-based fairness schemes called proportional fairness (PF) and min-max fairness (MMF). The PF scheme deals with minimizing the total weighted latency of MUs while MMF aims at minimizing the maximum latency among them. In the CP, we propose a novel proactive fairness and transmission-aware cache placement strategy (CPS) corresponding to each target fairness scheme by exploiting the flexible wireless access and backhaul transmission opportunities. Specifically, we jointly perform the allocation of physical resources as storage and radio, and user association to improve the flexibility of the CPSs. Moreover, In the DP of each fairness scheme, an efficient delivery policy is proposed based on the arrival requests of MUs, CSI, and caching status. Numerical assessments demonstrate that our proposed CPSs outperform the total latency of MUs up to 27% compared to the conventional baseline popular CPSs.
A compressed dynamic self-index for highly repetitive text collections
Venue: arXiv cs.DS 2018
Year: 2018

We present a novel compressed dynamic self-index for highly repetitive text collections. Signature encoding is a compressed dynamic self-index for highly repetitive texts and has a large disadvantage that the pattern search for short patterns is slow. We improve this disadvantage for faster pattern search by leveraging an idea behind truncated suffix tree and present the first compressed dynamic self-index named TST-index that supports not only fast pattern search but also dynamic update operation of index for highly repetitive texts. Experiments using a benchmark dataset of highly repetitive texts show that the pattern search of TST-index is significantly improved.
Toward perfect reads: self-correction of short reads via mapping on de Bruijn graphs
Venue: arXiv cs.DS 2018
Year: 2018

Motivations Short-read accuracy is important for downstream analyses such as genome assembly and hybrid long-read correction. Despite much work on short-read correction, present-day correctors either do not scale well on large data sets or consider reads as mere suites of k-mers, without taking into account their full-length read information. Results We propose a new method to correct short reads using de Bruijn graphs, and implement it as a tool called Bcool. As a first st ep, Bcool constructs a compacted de Bruijn graph from the reads. This graph is filtered on the basis of k-mer abundance then of unitig abundance, thereby removing from most sequencing errors. The cleaned graph is then used as a reference on which the reads are mapped to correct them. We show that this approach yields more accurate reads than k-mer-spectrum correctors while being scalable to human-size genomic datasets and beyond. Availability and Implementation The implementation is open source and available at http://github.com/Malfoy/BCOOL under the Affero GPL license. Contact Antoine Limasset antoine.limasset@gmail.com & Jean-François Flot jflot@ulb.ac.be & Pierre Peterlongo pierre.peterlongo@inria.fr
On Strong Equilibria and Improvement Dynamics in Network Creation Games
Venue: arXiv cs.GT 2018
Year: 2018

We study strong equilibria in network creation games. These form a classical and well-studied class of games where a set of players form a network by buying edges to their neighbors at a cost of a fixed parameter $α$. The cost of a player is defined to be the cost of the bought edges plus the sum of distances to all the players in the resulting graph. We identify and characterize various structural properties of strong equilibria, which lead to a characterization of the set of strong equilibria for all $α$ in the range $(0,2)$. For $α> 2$, Andelman et al. (2009) prove that a star graph in which every leaf buys one edge to the center node is a strong equilibrium, and conjecture that in fact any star is a strong equilibrium. We resolve this conjecture in the affirmative. Additionally, we show that when $α$ is large enough ($\geq 2n$) there exist non-star trees that are strong equilibria. For the strong price of anarchy, we provide precise expressions when $α$ is in the range $(0,2)$, and we prove a lower bound of $3/2$ when $α\geq 2$. Lastly, we aim to characterize under which conditions (coalitional) improvement dynamics may converge to a strong equilibrium. To this end, we study the (coalitional) finite improvement property and (coalitional) weak acyclicity property. We prove various conditions under which these properties do and do not hold. Some of these results also hold for the class of pure Nash equilibria.
Predicting Chroma from Luma in AV1
Venue: arXiv cs.MM 2018
Year: 2018

Chroma from luma (CfL) prediction is a new and promising chroma-only intra predictor that models chroma pixels as a linear function of the coincident reconstructed luma pixels. In this paper, we present the CfL predictor adopted in Alliance Video 1 (AV1), a royalty-free video codec developed by the Alliance for Open Media (AOM). The proposed CfL distinguishes itself from prior art not only by reducing decoder complexity, but also by producing more accurate predictions. On average, CfL reduces the BD-rate, when measured with CIEDE2000, by 5% for still images and 2% for video sequences.
Stability and Stabilization of Fractional-order Systems with Different Derivative Orders: An LMI Approach
Venue: arXiv cs.SY 2018
Year: 2018

Stability and stabilization analysis of fractional-order linear time-invariant (FO-LTI) systems with different derivative orders is studied in this paper. First, by using an appropriate linear matrix function, a single-order equivalent system for the given different-order system is introduced by which a new stability condition is obtained that is easier to check in practice than the conditions known up to now. Then the stabilization problem of fractional-order linear systems with different fractional orders via a dynamic output feedback controller with a predetermined order is investigated, utilizing the proposed stability criterion. The linear matrix inequality based procedure of developing stabilizing output feedback control is preserved in spite of the complexity of assuming the most complete linear controller model, with direct feedthrough parameter. The proposed stability and stabilization theorems are applicable to FO-LTI systems with different fractional orders in one or both of and intervals. Eventually, some numerical examples are presented to confirm the obtained analytical results.
CUR Decompositions, Similarity Matrices, and Subspace Clustering
Venue: arXiv cs.LG 2018
Year: 2018

A general framework for solving the subspace clustering problem using the CUR decomposition is presented. The CUR decomposition provides a natural way to construct similarity matrices for data that come from a union of unknown subspaces $\mathscr{U}=\underset{i=1}{\overset{M}\bigcup}S_i$. The similarity matrices thus constructed give the exact clustering in the noise-free case. Additionally, this decomposition gives rise to many distinct similarity matrices from a given set of data, which allow enough flexibility to perform accurate clustering of noisy data. We also show that two known methods for subspace clustering can be derived from the CUR decomposition. An algorithm based on the theoretical construction of similarity matrices is presented, and experiments on synthetic and real data are presented to test the method. Additionally, an adaptation of our CUR based similarity matrices is utilized to provide a heuristic algorithm for subspace clustering; this algorithm yields the best overall performance to date for clustering the Hopkins155 motion segmentation dataset.
Souper: A Synthesizing Superoptimizer
Venue: arXiv cs.PL 2018
Year: 2018

If we can automatically derive compiler optimizations, we might be able to sidestep some of the substantial engineering challenges involved in creating and maintaining a high-quality compiler. We developed Souper, a synthesizing superoptimizer, to see how far these ideas might be pushed in the context of LLVM. Along the way, we discovered that Souper's intermediate representation was sufficiently similar to the one in Microsoft Visual C++ that we applied Souper to that compiler as well. Shipping, or about-to-ship, versions of both compilers contain optimizations suggested by Souper but implemented by hand. Alternately, when Souper is used as a fully automated optimization pass it compiles a Clang compiler binary that is about 3 MB (4.4%) smaller than the one compiled by LLVM.
Grothendieck constant is norm of Strassen matrix multiplication tensor
Venue: arXiv cs.CC 2018
Year: 2018

We show that two important quantities from two disparate areas of complexity theory --- Strassen's exponent of matrix multiplication $ω$ and Grothendieck's constant $K_G$ --- are intimately related. They are different measures of size for the same underlying object --- the matrix multiplication tensor, i.e., the $3$-tensor or bilinear operator $μ_{l,m,n} : \mathbb{F}^{l \times m} \times \mathbb{F}^{m \times n} \to \mathbb{F}^{l \times n}$, $(A,B) \mapsto AB$ defined by matrix-matrix product over $\mathbb{F} = \mathbb{R}$ or $\mathbb{C}$. It is well-known that Strassen's exponent of matrix multiplication is the greatest lower bound on (the log of) a tensor rank of $μ_{l,m,n}$. We will show that Grothendieck's constant is the least upper bound on a tensor norm of $μ_{l,m,n}$, taken over all $l, m, n \in \mathbb{N}$. Aside from relating the two celebrated quantities, this insight allows us to rewrite Grothendieck's inequality as a norm inequality \[ \lVertμ_{l,m,n}\rVert_{1,2,\infty} =\max_{X,Y,M\neq0}\frac{|\operatorname{tr}(XMY)|}{\lVert X\rVert_{1,2}\lVert Y\rVert_{2,\infty}\lVert M\rVert_{\infty,1}}\le K_G. \] We prove that Grothendieck's inequality is unique: If we generalize the $(1,2,\infty)$-norm to arbitrary $p,q, r \in [1, \infty]$, \[ \lVertμ_{l,m,n}\rVert_{p,q,r}=\max_{X,Y,M\neq0}\frac{|\operatorname{tr}(XMY)|}{\|X\|_{p,q}\|Y\|_{q,r}\|M\|_{r,p}}, \] then $(p,q,r )=(1,2,\infty)$ is, up to cyclic permutations, the only choice for which $\lVertμ_{l,m,n}\rVert_{p,q,r}$ is uniformly bounded by a constant independent of $l,m,n$.