OpenRaiser/Intern-Atlas huggingface dataset:
Optimization of Non Binary Parity Check Coefficients
Venue: arXiv cs.IT 2018
Year: 2018

This paper generalizes the method proposed by Poulliat et al. for the determination of the optimal Galois Field coefficients of a Non-Binary LDPC parity check constraint based on the binary image of the code. Optimal, or almost-optimal, parity check coefficients are given for check degree varying from 4 to 20 and Galois Field varying from GF(64) up to GF(1024). For all given sets of coefficients, no codeword of Hamming weight two exists. A reduced complexity algorithm to compute the binary Hamming weight 3 of a parity check is proposed. When the number of sets of coefficients is too high for an exhaustive search and evaluation, a local greedy search is performed. Explicit tables of coefficients are given. The proposed sets of coefficients can effectively replace the random selection of coefficients often used in NB-LDPC construction.
MonoPerfCap: Human Performance Capture from Monocular Video
Venue: arXiv cs.CV 2018
Year: 2018

We present the first marker-less approach for temporally coherent 3D performance capture of a human with general clothing from monocular video. Our approach reconstructs articulated human skeleton motion as well as medium-scale non-rigid surface deformations in general scenes. Human performance capture is a challenging problem due to the large range of articulation, potentially fast motion, and considerable non-rigid deformations, even from multi-view data. Reconstruction from monocular video alone is drastically more challenging, since strong occlusions and the inherent depth ambiguity lead to a highly ill-posed reconstruction problem. We tackle these challenges by a novel approach that employs sparse 2D and 3D human pose detections from a convolutional neural network using a batch-based pose estimation strategy. Joint recovery of per-batch motion allows to resolve the ambiguities of the monocular reconstruction problem based on a low dimensional trajectory subspace. In addition, we propose refinement of the surface geometry based on fully automatically extracted silhouettes to enable medium-scale non-rigid alignment. We demonstrate state-of-the-art performance capture results that enable exciting applications such as video editing and free viewpoint video, previously infeasible from monocular video. Our qualitative and quantitative evaluation demonstrates that our approach significantly outperforms previous monocular methods in terms of accuracy, robustness and scene complexity that can be handled.
An Adaptive Cluster-based Filtering Framework for Speckle Reduction of OCT Skin Images
Venue: arXiv cs.CV 2018
Year: 2018

Optical coherence tomography (OCT) has become a favorable device in the Dermatology discipline due to its moderate resolution and penetration depth. OCT images however contain a grainy pattern, called speckle, due to the use of a broadband source in the configuration of OCT. So far, a variety of filtering (de-speckling) techniques is introduced to reduce speckle in OCT images. Most of these methods are generic and can be applied to OCT images of different tissues. The ambition of this work is to provide a de-speckling framework specialized for filtering skin tissues for the community to utilize, adapt or build upon. In this paper, we present an adaptive cluster-based filtering framework, optimized for speckle reduction of OCT skin images. In this framework, by considering the layered structure of skin, first the OCT skin images are segmented into differentiable layers utilizing clustering algorithms, and then each cluster is de-speckled individually using adaptive filtering techniques. In this study, hierarchical clustering algorithm and adaptive Wiener filtering technique are utilized to develop the framework. The proposed method is tested on optical solid phantoms with predetermined optical properties. The method is also tested on healthy human skin images. The results show that the proposed cluster-based filtering method can effectively reduce the speckle and increase the signal-to-noise ratio and contrast while preserving the edges in the image. The proposed cluster-based filtering framework enables researchers to develop unsupervised learning solutions for de-speckling OCT skin images using adaptive filtering methods, or extend the framework to new applications.
An Approach to Quad Meshing Based on Harmonic Cross-Valued Maps and the Ginzburg-Landau Theory
Venue: arXiv cs.CG 2018
Year: 2018

A generalization of vector fields, referred to as N-direction fields or cross fields when N = 4, has been recently introduced and studied for geometry processing, with applications in quadrilateral (quad) meshing, texture mapping, and parameterization. We make the observation that cross field design for two-dimensional quad meshing is related to the well-known Ginzburg-Landau problem from mathematical physics. This yields a variety of theoretical tools for efficiently computing boundary-aligned quad meshes, with provable guarantees on the resulting mesh, such as the number of mesh defects and bounds on the defect locations. The procedure for generating the quad mesh is to (i) find a complex-valued "representation" field that minimizes the Ginzburg-Landau energy subject to a boundary constraint, (ii) convert the representation field into a boundary-aligned, smooth cross field, (iii) use separatrices of the cross field to partition the domain into four sided regions, and (iv) mesh each of these four-sided regions using standard techniques. Leveraging the Ginzburg-Landau theory, we prove that this procedure can be used to produce a cross field whose separatrices partition the domain into four sided regions. To minimize the Ginzburg-Landau energy for the representation field, we use an extension of the Merriman-Bence-Osher (MBO) threshold dynamics method, originally conceived as an algorithm to simulate mean curvature flow. Finally, we demonstrate the method on a variety of test domains.
Demand-Independent Optimal Tolls
Venue: arXiv cs.GT 2018
Year: 2018

Wardrop equilibria in nonatomic congestion games are in general inefficient as they do not induce an optimal flow that minimizes the total travel time. Network tolls are a prominent and popular way to induce an optimum flow in equilibrium. The classical approach to find such tolls is marginal cost pricing which requires the exact knowledge of the demand on the network. In this paper, we investigate under which conditions demand-independent optimum tolls exist that induce the system optimum flow for any travel demand in the network. We give several characterizations for the existence of such tolls both in terms of the cost structure and the network structure of the game. Specifically we show that demand-independent optimum tolls exist if and only if the edge cost functions are shifted monomials as used by the Bureau of Public Roads. Moreover, non-negative demand-independent optimum tolls exist when the network is a directed acyclic multi-graph. Finally, we show that any network with a single origin-destination pair admits demand-independent optimum tolls that, although not necessarily non-negative, satisfy a budget constraint.
ExaGeoStat: A High Performance Unified Software for Geostatistics on Manycore Systems
Venue: arXiv cs.DC 2018
Year: 2018

We present ExaGeoStat, a high performance framework for geospatial statistics in climate and environment modeling. In contrast to simulation based on partial differential equations derived from first-principles modeling, ExaGeoStat employs a statistical model based on the evaluation of the Gaussian log-likelihood function, which operates on a large dense covariance matrix. Generated by the parametrizable Matern covariance function, the resulting matrix is symmetric and positive definite. The computational tasks involved during the evaluation of the Gaussian log-likelihood function become daunting as the number n of geographical locations grows, as O(n2) storage and O(n3) operations are required. While many approximation methods have been devised from the side of statistical modeling to ameliorate these polynomial complexities, we are interested here in the complementary approach of evaluating the exact algebraic result by exploiting advances in solution algorithms and many-core computer architectures. Using state-of-the-art high performance dense linear algebra libraries associated with various leading edge parallel architectures (Intel KNLs, NVIDIA GPUs, and distributed-memory systems), ExaGeoStat raises the game for statistical applications from climate and environmental science. ExaGeoStat provides a reference evaluation of statistical parameters, with which to assess the validity of the various approaches based on approximation. The framework takes a first step in the merger of large-scale data analytics and extreme computing for geospatial statistical applications, to be followed by additional complexity reducing improvements from the solver side that can be implemented under the same interface. Thus, a single uncompromised statistical model can ultimately be executed in a wide variety of emerging exascale environments.
Distance-preserving Subgraphs of Interval Graphs
Venue: arXiv cs.DS 2018
Year: 2018

We consider the problem of finding small distance-preserving subgraphs of undirected, unweighted interval graphs with $k$ terminal vertices. To start with, we show that finding an optimal distance-preserving subgraph is $\mathsf{NP}$-hard for general graphs. Then, we show that every interval graph admits a subgraph with $O(k)$ branching vertices that approximates pairwise terminal distances up to an additive term of $+1$. We also present an interval graph $G_{\mathrm{int}}$ for which the $+1$ approximation is necessary to obtain the $O(k)$ upper bound on the number of branching vertices. In particular, any distance-preserving subgraph of $G_{\mathrm{int}}$ has $Ω(k\log k)$ branching vertices. Furthermore, we prove that every interval graph admits a distance-preserving subgraph with $O(k\log k)$ branching vertices, implying that the $Ω(k\log k)$ lower bound for interval graphs is tight. To conclude, we show that there exists an interval graph such that every optimal distance-preserving subgraph of it has $O(k)$ branching vertices and $Ω(k\log k)$ branching edges, thereby providing a separation between branching vertices and branching edges. The $O(k)$ bound for distance-approximating subgraphs follows from a naïve analysis of shortest paths in interval graphs. $G_{\mathrm{int}}$ is constructed using bit-reversal permutation matrices. The $O(k\log k)$ bound for distance-preserving subgraphs uses a divide-and-conquer approach. Finally, the separation between branching vertices and branching edges employs Hansel's lemma for graph covering.
The Dark Side(-Channel) of Mobile Devices: A Survey on Network Traffic Analysis
Venue: arXiv cs.CR 2018
Year: 2018

In recent years, mobile devices (e.g., smartphones and tablets) have met an increasing commercial success and have become a fundamental element of the everyday life for billions of people all around the world. Mobile devices are used not only for traditional communication activities (e.g., voice calls and messages) but also for more advanced tasks made possible by an enormous amount of multi-purpose applications (e.g., finance, gaming, and shopping). As a result, those devices generate a significant network traffic (a consistent part of the overall Internet traffic). For this reason, the research community has been investigating security and privacy issues that are related to the network traffic generated by mobile devices, which could be analyzed to obtain information useful for a variety of goals (ranging from device security and network optimization, to fine-grained user profiling). In this paper, we review the works that contributed to the state of the art of network traffic analysis targeting mobile devices. In particular, we present a systematic classification of the works in the literature according to three criteria: (i) the goal of the analysis; (ii) the point where the network traffic is captured; and (iii) the targeted mobile platforms. In this survey, we consider points of capturing such as Wi-Fi Access Points, software simulation, and inside real mobile devices or emulators. For the surveyed works, we review and compare analysis techniques, validation methods, and achieved results. We also discuss possible countermeasures, challenges and possible directions for future research on mobile traffic analysis and other emerging domains (e.g., Internet of Things). We believe our survey will be a reference work for researchers and practitioners in this research field.
Classical Music Composition Using State Space Models
Venue: arXiv cs.SD 2018
Year: 2018

Algorithmic composition of music has a long history and with the development of powerful deep learning methods, there has recently been increased interest in exploring algorithms and models to create art. We explore the utility of state space models, in particular hidden Markov models (HMMs) and variants, in composing classical piano pieces from the Romantic era and consider the models' ability to generate new pieces that sound like they were composed by a human. We find that the models we explored are fairly successful at generating new pieces that have largely consonant harmonies, especially when trained on original pieces with simple harmonic structure. However, we conclude that the major limitation in using these models to generate music that sounds like it was composed by a human is the lack of melodic progression in the composed pieces. We also examine the performance of the models in the context of music theory.
Parametric Identification Using Weighted Null-Space Fitting
Venue: arXiv cs.SY 2018
Year: 2018

In identification of dynamical systems, the prediction error method using a quadratic cost function provides asymptotically efficient estimates under Gaussian noise and additional mild assumptions, but in general it requires solving a non-convex optimization problem. An alternative class of methods uses a non-parametric model as intermediate step to obtain the model of interest. Weighted null-space fitting (WNSF) belongs to this class. It is a weighted least-squares method consisting of three steps. In the first step, a high-order ARX model is estimated. In a second least-squares step, this high-order estimate is reduced to a parametric estimate. In the third step, weighted least squares is used to reduce the variance of the estimates. The method is flexible in parametrization and suitable for both open- and closed-loop data. In this paper, we show that WNSF provides estimates with the same asymptotic properties as PEM with a quadratic cost function when the model orders are chosen according to the true system. Also, simulation studies indicate that WNSF may be competitive with state-of-the-art methods.
Boundaries as an Enhancement Technique for Physical Layer Security
Venue: arXiv cs.IT 2018
Year: 2018

In this paper, we study the receiver performance with physical layer security in a Poisson field of interferers. We compare the performance in two deployment scenarios: (i) the receiver is located at the corner of a quadrant, (ii) the receiver is located in the infinite plane. When the channel state information (CSI) of the eavesdropper is not available at the transmitter, we calculate the probability of secure connectivity using the Wyner coding scheme, and we show that hiding the receiver at the corner is beneficial at high rates of the transmitted codewords and detrimental at low transmission rates. When the CSI is available, we show that the average secrecy capacity is higher when the receiver is located at the corner, even if the intensity of interferers in this case is four times higher than the intensity of interferers in the bulk. Therefore boundaries can also be used as a secrecy enhancement technique for high data rate applications.
An OpenGL and C++ based function library for curve and surface modeling in a large class of extended Chebyshev spaces
Venue: arXiv cs.MS 2018
Year: 2018

We propose a platform-independent multi-threaded function library that provides data structures to generate, differentiate and render both the ordinary basis and the normalized B-basis of a user-specified extended Chebyshev (EC) space that comprises the constants and can be identified with the solution space of a constant-coefficient homogeneous linear differential equation defined on a sufficiently small interval. Using the obtained normalized B-bases, our library can also generate, (partially) differentiate, modify and visualize a large family of so-called B-curves and tensor product B-surfaces. Moreover, the library also implements methods that can be used to perform dimension elevation, to subdivide B-curves and B-surfaces by means of de Casteljau-like B-algorithms, and to generate basis transformations for the B-representation of arbitrary integral curves and surfaces that are described in traditional parametric form by means of the ordinary bases of the underlying EC spaces. Independently of the algebraic, exponential, trigonometric or mixed type of the applied EC space, the proposed library is numerically stable and efficient up to a reasonable dimension number and may be useful for academics and engineers in the fields of Approximation Theory, Computer Aided Geometric Design, Computer Graphics, Isogeometric and Numerical Analysis.
On the Capacity of Fractal D2D Social Networks With Hierarchical Communications
Venue: arXiv cs.IT 2018
Year: 2018

The maximum capacity of fractal D2D (device-to-device) social networks with both direct and hierarchical communications is studied in this paper. Specifically, the fractal networks are characterized by the direct social connection and the self-similarity. Firstly, for a fractal D2D social network with direct social communications, it is proved that the maximum capacity is $ Θ\left(\frac{1}{\sqrt{n\log n}}\right) $ if a user communicates with one of his/her direct contacts randomly, where $ n $ denotes the total number of users in the network, and it can reach up to $ Θ\left(\frac{1}{\log n}\right) $ if any pair of social contacts with distance $ d $ communicate according to the probability in proportion to $ d^{-β} $. Secondly, since users might get in touch with others without direct social connections through the inter-connected multiple users, the fractal D2D social network with these hierarchical communications is studied as well, and the related capacity is further derived. Our results show that this capacity is mainly affected by the correlation exponent $ε$ of the fractal structure. The capacity is reduced in proportional to $ \frac{1}{\log n} $ if $ 2<ε<3 $, while the reduction coefficient is $ \frac{1}{n} $ if $ ε=3 $.
On Almost Well-Covered Graphs of Girth at Least 6
Venue: arXiv cs.DM 2018
Year: 2018

We consider a relaxation of the concept of well-covered graphs, which are graphs with all maximal independent sets of the same size. The extent to which a graph fails to be well-covered can be measured by its independence gap, defined as the difference between the maximum and minimum sizes of a maximal independent set in $G$. While the well-covered graphs are exactly the graphs of independence gap zero, we investigate in this paper graphs of independence gap one, which we also call almost well-covered graphs. Previous works due to Finbow et al. (1994) and Barbosa et al. (2013) have implications for the structure of almost well-covered graphs of girth at least $k$ for $k\in \{7,8\}$. We focus on almost well-covered graphs of girth at least $6$. We show that every graph in this class has at most two vertices each of which is adjacent to exactly $2$ leaves. We give efficiently testable characterizations of almost well-covered graphs of girth at least $6$ having exactly one or exactly two such vertices. Building on these results, we develop a polynomial-time recognition algorithm of almost well-covered $\{C_3,C_4,C_5,C_7\}$-free graphs.
Greedy and Evolutionary Algorithms for Mining Relationship-Based Access Control Policies
Venue: arXiv cs.CR 2018
Year: 2018

Relationship-based access control (ReBAC) provides a high level of expressiveness and flexibility that promotes security and information sharing. We formulate ReBAC as an object-oriented extension of attribute-based access control (ABAC) in which relationships are expressed using fields that refer to other objects, and path expressions are used to follow chains of relationships between objects. ReBAC policy mining algorithms have potential to significantly reduce the cost of migration from legacy access control systems to ReBAC, by partially automating the development of a ReBAC policy from an existing access control policy and attribute data. This paper presents two algorithms for mining ReBAC policies from access control lists (ACLs) and attribute data represented as an object model: a greedy algorithm guided by heuristics, and a grammar-based evolutionary algorithm. An evaluation of the algorithms on four sample policies and two large case studies demonstrates their effectiveness.
Fault in your stars: An Analysis of Android App Reviews
Venue: arXiv cs.LG 2018
Year: 2018

Mobile app distribution platforms such as Google Play Store allow users to share their feedback about downloaded apps in the form of a review comment and a corresponding star rating. Typically, the star rating ranges from one to five stars, with one star denoting a high sense of dissatisfaction with the app and five stars denoting a high sense of satisfaction. Unfortunately, due to a variety of reasons, often the star rating provided by a user is inconsistent with the opinion expressed in the review. For example, consider the following review for the Facebook App on Android; "Awesome App". One would reasonably expect the rating for this review to be five stars, but the actual rating is one star! Such inconsistent ratings can lead to a deflated (or inflated) overall average rating of an app which can affect user downloads, as typically users look at the average star ratings while making a decision on downloading an app. Also, the app developers receive a biased feedback about the application that does not represent ground reality. This is especially significant for small apps with a few thousand downloads as even a small number of mismatched reviews can bring down the average rating drastically. In this paper, we conducted a study on this review-rating mismatch problem. We manually examined 8600 reviews from 10 popular Android apps and found that 20% of the ratings in our dataset were inconsistent with the review. Further, we developed three systems; two of which were based on traditional machine learning and one on deep learning to automatically identify reviews whose rating did not match with the opinion expressed in the review. Our deep learning system performed the best and had an accuracy of 92% in identifying the correct star rating to be associated with a given review.
Millimeter Wave Channel Measurements in a Railway Depot
Venue: arXiv cs.NI 2018
Year: 2018

Millimeter wave (mmWave) communication is a key enabling technology with the potential to deliver high capacity, high peak data rate communications for future railway services. Knowledge of the radio characteristics is of paramount importance for the successful deployment of such systems. In this paper mmWave channel measurements are reported for a railway environment using a wideband channel sounder operating at 60GHz. Highly directional antennas are deployed at both ends of the link. Data is reported for path loss, root mean square (RMS) delay spread and K-factor. Static and mobile measurements are considered. Analysis shows that the signal strength is strongly dependent (up to 25dB) on the azimuth orientation of the directional transmit and receive antennas. A path loss exponent of n=2.04 was extracted from the Line-of-Sight measurements with optimally aligned antennas. RMS delay spreads ranged from 1ns to 22ns depending on antenna alignment. 50% of the measured K-factors were found to be less than 6dB. We conclude this is the result of ground reflections in the vertical Tx-Rx plane.