OpenRaiser/Intern-Atlas huggingface dataset:
Random Walk in a N-cube Without Hamiltonian Cycle to Chaotic Pseudorandom Number Generation: Theoretical and Practical Considerations
Venue: arXiv cs.CR 2017
Year: 2017

Designing a pseudorandom number generator (PRNG) is a difficult and complex task. Many recent works have considered chaotic functions as the basis of built PRNGs: the quality of the output would indeed be an obvious consequence of some chaos properties. However, there is no direct reasoning that goes from chaotic functions to uniform distribution of the output. Moreover, embedding such kind of functions into a PRNG does not necessarily allow to get a chaotic output, which could be required for simulating some chaotic behaviors. In a previous work, some of the authors have proposed the idea of walking into a $\mathsf{N}$-cube where a balanced Hamiltonian cycle has been removed as the basis of a chaotic PRNG. In this article, all the difficult issues observed in the previous work have been tackled. The chaotic behavior of the whole PRNG is proven. The construction of the balanced Hamiltonian cycle is theoretically and practically solved. An upper bound of the expected length of the walk to obtain a uniform distribution is calculated. Finally practical experiments show that the generators successfully pass the classical statistical tests.
Modelling community formation driven by the status of individual in a society
Venue: arXiv cs.MA 2017
Year: 2017

In human societies, people's willingness to compete and strive for better social status as well as being envious of those perceived in some way superior lead to social structures that are intrinsically hierarchical. Here we propose an agent-based, network model to mimic the ranking behaviour of individuals and its possible repercussions in human society. The main ingredient of the model is the assumption that the relevant feature of social interactions is each individual's keenness to maximise his or her status relative to others. The social networks produced by the model are homophilous and assortative, as frequently observed in human communities and most of the network properties seem quite independent of its size. However, it is seen that for small number of agents the resulting network consists of disjoint weakly connected communities while being highly assortative and homophilic. On the other hand larger networks turn out to be more cohesive with larger communities but less homophilic. We find that the reason for these changes is that larger network size allows agents to use new strategies for maximizing their social status allowing for more diverse links between them.
Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams
Venue: arXiv cs.DS 2017
Year: 2017

We consider the maximum matching problem in the semi-streaming model formalized by Feigenbaum, Kannan, McGregor, Suri, and Zhang that is inspired by giant graphs of today. As our main result, we give a two-pass $(1/2 + 1/16)$-approximation algorithm for triangle-free graphs and a two-pass $(1/2 + 1/32)$-approximation algorithm for general graphs; these improve the approximation ratios of $1/2 + 1/52$ for bipartite graphs and $1/2 + 1/140$ for general graphs by Konrad, Magniez, and Mathieu. In three passes, we achieve approximation ratios of $1/2 + 1/10$ for triangle-free graphs and $1/2 + 1/19.753$ for general graphs. We also give a multi-pass algorithm where we bound the number of passes precisely---we give a $(2/3 -\varepsilon)$-approximation algorithm that uses $2/(3\varepsilon)$ passes for triangle-free graphs and $4/(3\varepsilon)$ passes for general graphs. Our algorithms are simple and combinatorial, use $O(n \log n)$ space, and have $O(1)$ update time per edge. For general graphs, our multi-pass algorithm improves the best known deterministic algorithms in terms of the number of passes: --Ahn and Guha give a $(2/3 - \varepsilon)$-approximation algorithm that uses $O(\log(1/\varepsilon)/\varepsilon^2)$ passes, whereas our $(2/3 - \varepsilon)$-approximation algorithm uses $4/(3\varepsilon)$ passes; --they also give a $(1-\varepsilon)$-approximation algorithm that uses $O(\log n \cdot \mathrm{poly}(1/\varepsilon))$ passes, where $n$ is the number of vertices of the input graph; although our algorithm is $(2/3 - \varepsilon)$-approximation, our number of passes do not depend on $n$. Earlier multi-pass algorithms either have a large constant inside big-$O$ notation for the number of passes or the constant cannot be determined due to the involved analysis, so our multi-pass algorithm should use much fewer passes for approximation ratios bounded slightly below $2/3$.
Precoding for the Sparsely Spread MC-CDMA Downlink with Discrete-Alphabet Inputs
Venue: arXiv cs.IT 2017
Year: 2017

Sparse signatures have been proposed for the CDMA uplink to reduce multi-user detection complexity, but they have not yet been fully exploited for its downlink counterpart. In this work, we propose a Multi-Carrier CDMA (MC-CDMA) downlink communication, where regular sparse signatures are deployed in the frequency domain. Taking the symbol detection point of view, we formulate a problem appropriate for the downlink with discrete alphabets as inputs. The solution to the problem provides a power-efficient precoding algorithm for the base station, subject to minimum symbol error probability (SEP) requirements at the mobile stations. In the algorithm, signature sparsity is shown to be crucial for reducing precoding complexity. Numerical results confirm system-load-dependent power reduction gain from the proposed precoding over the zero-forcing precoding and the regularized zero-forcing precoding with optimized regularization parameter under the same SEP targets. For a fixed system load, it is also demonstrated that sparse MC-CDMA with a proper choice of sparsity level attains almost the same power efficiency and link throughput as that of dense MC-CDMA yet with reduced precoding complexity, thanks to the sparse signatures.
EEG Representation Using Multi-instance Framework on The Manifold of Symmetric Positive Definite Matrices for EEG-based Computer Aided Diagnosis
Venue: arXiv cs.LG 2017
Year: 2017

The generalization and robustness of an electroencephalogram (EEG)-based computer aided diagnostic system are crucial requirements in actual clinical practice. To reach these goals, we propose a new EEG representation that provides a more realistic view of brain functionality by applying multi-instance (MI) framework to consider the non-stationarity of the EEG signal. The non-stationary characteristic of EEG is considered by describing the signal as a bag of relevant and irrelevant concepts. The concepts are provided by a robust representation of homogenous segments of EEG signal using spatial covariance matrices. Due to the nonlinear geometry of the space of covariance matrices, we determine the boundaries of the homogeneous segments based on adaptive segmentation of the signal in a Riemannian framework. Each subject is described as a bag of covariance matrices of homogenous segments and the bag-level discriminative information is used for classification. To evaluate the performance of the proposed approach, we examine it in attention deficit hyperactivity/bipolar mood disorder detection and depression/normal diagnosis applications. Experimental results confirm the superiority of the proposed approach, which is gained due to the robustness of covariance descriptor, the effectiveness of Riemannian geometry, and the benefits of considering the inherent non-stationary nature of the brain.
A New View of Multi-User Hybrid Massive MIMO: Non-Orthogonal Angle Division Multiple Access
Venue: arXiv cs.IT 2017
Year: 2017

This paper presents a new view of multi-user (MU) hybrid massive multiple-input and multiple-output (MIMO) systems from array signal processing perspective. We first show that the instantaneous channel vectors corresponding to different users are asymptotically orthogonal if the angles of arrival (AOAs) of users are different. We then decompose the channel matrix into an angle domain basis matrix and a gain matrix. The former can be formulated by steering vectors and the latter has the same size as the number of RF chains, which perfectly matches the structure of hybrid precoding. A novel hybrid channel estimation is proposed by separately estimating the angle information and the gain matrix, which could significantly save the training overhead and substantially improve the channel estimation accuracy compared to the conventional beamspace approach. Moreover, with the aid of the angle domain matrix, the MU massive MIMO system can be viewed as a type of non-orthogonal angle division multiple access (ADMA) to simultaneously serve multiple users at the same frequency band. Finally, the performance of the proposed scheme is validated by computer simulation results.
Dichotomy for Real Holant$^c$ Problems
Venue: arXiv cs.CC 2017
Year: 2017

Holant problems capture a class of Sum-of-Product computations such as counting matchings. It is inspired by holographic algorithms and is equivalent to tensor networks, with counting CSP being a special case. A classification for Holant problems is more difficult to prove, not only because it implies a classification for counting CSP, but also due to the deeper reason that there exist more intricate polynomial time tractable problems in the broader framework. We discover a new family of constraint functions $\mathscr{L}$ which define polynomial time computable counting problems. These do not appear in counting CSP, and no newly discovered tractable constraints can be symmetric. It has a delicate support structure related to error-correcting codes. Local holographic transformations is fundamental in its tractability. We prove a complexity dichotomy theorem for all Holant problems defined by any real valued constraint function set on Boolean variables and contains two 0-1 pinning functions. Previously, dichotomy for the same framework was only known for symmetric constraint functions. he set $\mathscr{L}$ supplies the last piece of tractability. We also prove a dichotomy for a variant of counting CSP as a technical component toward this Holant dichotomy.
Towards Autonomous UAV Landing Based on Infrared Beacons and Particle Filtering
Venue: arXiv cs.RO 2017
Year: 2017

Autonomous fixed-wing UAV landing based on differential GPS is now a mainstream providing reliable and precise landing. But the task still remains challenging when GPS availability is limited like for military UAVs. We discuss a solution of this problem based on computer vision and dot markings along stationary or makeshift runway. We focus our attempts on using infrared beacons along with narrow-band filter as promising way to mark any makeshift runway and utilize particle filtering to fuse both IMU and visual data. We believe that unlike many other vision-based methods this solution is capable of tracking UAV position up to engines stop. System overview, algorithm description and it's evaluation on synthesized sequence along real recorded trajectory is presented.
Automatic Estimation of Fetal Abdominal Circumference from Ultrasound Images
Venue: arXiv cs.CV 2017
Year: 2017

Ultrasound diagnosis is routinely used in obstetrics and gynecology for fetal biometry, and owing to its time-consuming process, there has been a great demand for automatic estimation. However, the automated analysis of ultrasound images is complicated because they are patient-specific, operator-dependent, and machine-specific. Among various types of fetal biometry, the accurate estimation of abdominal circumference (AC) is especially difficult to perform automatically because the abdomen has low contrast against surroundings, non-uniform contrast, and irregular shape compared to other parameters.We propose a method for the automatic estimation of the fetal AC from 2D ultrasound data through a specially designed convolutional neural network (CNN), which takes account of doctors' decision process, anatomical structure, and the characteristics of the ultrasound image. The proposed method uses CNN to classify ultrasound images (stomach bubble, amniotic fluid, and umbilical vein) and Hough transformation for measuring AC. We test the proposed method using clinical ultrasound data acquired from 56 pregnant women. Experimental results show that, with relatively small training samples, the proposed CNN provides sufficient classification results for AC estimation through the Hough transformation. The proposed method automatically estimates AC from ultrasound images. The method is quantitatively evaluated, and shows stable performance in most cases and even for ultrasound images deteriorated by shadowing artifacts. As a result of experiments for our acceptance check, the accuracies are 0.809 and 0.771 with the expert 1 and expert 2, respectively, while the accuracy between the two experts is 0.905. However, for cases of oversized fetus, when the amniotic fluid is not observed or the abdominal area is distorted, it could not correctly estimate AC.
Software-Defined Network Controlled Switching between Millimeter Wave and Terahertz Small Cells
Venue: arXiv cs.NI 2017
Year: 2017

Small cells are a cost-effective way to reliably expand network coverage and provide significantly increased capacity for end users. The ultra-high bandwidth available at millimeter (mmWave) and Terahertz (THz) frequencies can effectively realize short-range wireless access links in small cells enabling potential uses cases such as driver-less cars, data backhauling and ultra-high-definition infotainment services. This paper describes a new software defined network (SDN) framework for vehicles equipped with transceivers capable of dynamically switching between THz and mmWave bands. We present a novel SDN controlled admission policy that preferentially handoffs between the mmWave and THz small cells, accommodates asymmetric uplink/downlink traffic, performs error recovery and handles distinct link states that arise due to motion along practical vehicular paths. We then analytically derive the resulting capacity of such a small cell network by accounting for the channel characteristics unique to both these spectrum bands, relative distance and the contact times between a given transceiver pair. We then formulate the optimal procedure for scheduling multiple vehicles at a given infrastructure tower, with regards to practical road congestion scenarios. The search for the optimal schedule is shown to be a NP-hard problem. Hence, we design a computationally-feasible polynomial-time scheduling algorithm that runs at the SDN controller and compare its performance against the optimal procedure and random access. Additionally, we present a simulation-based case study for the use case of data center backhauling in Boston city to showcase the benefits of our approach.
Sparse Approximation is Provably Hard under Coherent Dictionaries
Venue: arXiv cs.CC 2017
Year: 2017

It is well known that sparse approximation problem is \textsf{NP}-hard under general dictionaries. Several algorithms have been devised and analyzed in the past decade under various assumptions on the \emph{coherence} $μ$ of the dictionary represented by an $M \times N$ matrix from which a subset of $k$ column vectors is selected. All these results assume $μ=O(k^{-1})$. This article is an attempt to bridge the big gap between the negative result of \textsf{NP}-hardness under general dictionaries and the positive results under this restrictive assumption. In particular, it suggests that the aforementioned assumption might be asymptotically the best one can make to arrive at any efficient algorithmic result under well-known conjectures of complexity theory. In establishing the results, we make use of a new simple multilayered PCP which is tailored to give a matrix with small coherence combined with our reduction.
Robust Orchestration of Concurrent Application Workflows in Mobile Device Clouds
Venue: arXiv cs.DC 2017
Year: 2017

A hybrid mobile/fixed device cloud that harnesses sensing, computing, communication, and storage capabilities of mobile and fixed devices in the field as well as those of computing and storage servers in remote datacenters is envisioned. Mobile device clouds can be harnessed to enable innovative pervasive applications that rely on real-time, in-situ processing of sensor data collected in the field. To support concurrent mobile applications on the device cloud, a robust and secure distributed computing framework, called Maestro, is proposed. The key components of Maestro are (i) a task scheduling mechanism that employs controlled task replication in addition to task reallocation for robustness and (ii) Dedup for task deduplication among concurrent pervasive workflows. An architecture-based solution that relies on task categorization and authorized access to the categories of tasks is proposed for different levels of protection. Experimental evaluation through prototype testbed of Android- and Linux-based mobile devices as well as simulations is performed to demonstrate Maestro's capabilities.
Elastic Resource Management with Adaptive State Space Partitioning of Markov Decision Processes
Venue: arXiv cs.DC 2017
Year: 2017

Modern large-scale computing deployments consist of complex applications running over machine clusters. An important issue in these is the offering of elasticity, i.e., the dynamic allocation of resources to applications to meet fluctuating workload demands. Threshold based approaches are typically employed, yet they are difficult to configure and optimize. Approaches based on reinforcement learning have been proposed, but they require a large number of states in order to model complex application behavior. Methods that adaptively partition the state space have been proposed, but their partitioning criteria and strategies are sub-optimal. In this work we present MDP_DT, a novel full-model based reinforcement learning algorithm for elastic resource management that employs adaptive state space partitioning. We propose two novel statistical criteria and three strategies and we experimentally prove that they correctly decide both where and when to partition, outperforming existing approaches. We experimentally evaluate MDP_DT in a real large scale cluster over variable not-encountered workloads and we show that it takes more informed decisions compared to static and model-free approaches, while requiring a minimal amount of training data.
Computability and Complexity of Unconventional Computing Devices
Venue: arXiv cs.ET 2017
Year: 2017

We discuss some claims that certain UCOMP devices can perform hypercomputation (compute Turing-uncomputable functions) or perform super-Turing computation (solve NP-complete problems in polynomial time). We discover that all these claims rely on the provision of one or more unphysical resources.
Elementary $L^\infty$ error estimates for super-resolution de-noising
Venue: arXiv cs.IT 2017
Year: 2017

This paper studies the problem of recovering a discrete complex measure on the torus from a finite number of corrupted Fourier samples. We assume the support of the unknown discrete measure satisfies a minimum separation condition and we use convex regularization methods to recover approximations of the original measure. We focus on two well-known convex regularization methods, and for both, we establish an error estimate that bounds the smoothed-out error in terms of the target resolution and noise level. Our $L^\infty$ approximation rate is entirely new for one of the methods, and improves upon a previously established $L^1$ estimate for the other. We provide a unified analysis and an elementary proof of the theorem.
The Potential of Using Large Antenna Arrays on Intelligent Surfaces
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we consider capacities of single-antenna terminals communicating to large antenna arrays that are deployed on surfaces. That is, the entire surface is used as an intelligent receiving antenna array. Under the condition that the surface area is sufficiently large, the received signal after matched-filtering (MF) can be well approximated by an intersymbol interference (ISI) channel where channel taps are closely related to a sinc function. Based on such an approximation, we have derived the capacities for both one-dimensional (terminals on a line) and high dimensional (terminals on a plane or in a cube) terminal-deployments. In particular, we analyze the normalized capacity $\bar{\mathcal{C}}$, measured in nats/s/Hz/m$^2$, under the constraint that the transmit power per m$^2$, $\bar{P}$, is fixed. We show that when the user-density increases, the limit of $\bar{\mathcal{C}}$, achieved as the wavelength $λ$ approaches 0, is $\bar{P}/(2N_0)$ nats/s/Hz/m$^2$, where $N_0$ is the spatial power spectral density (PSD) of noise. In addition, we also show that the number of signal dimensions is $2/λ$ per meter deployed surface for the one-dimensional case, and $π/λ^2$ per m$^2$ deployed surface for two and three dimensional terminal-deployments.
The Stochastic Shortest Path Problem : A polyhedral combinatorics perspective
Venue: arXiv cs.DM 2017
Year: 2017

In this paper, we give a new framework for the stochastic shortest path problem in finite state and action spaces. Our framework generalizes both the frameworks proposed by Bertsekas and Tsitsikli and by Bertsekas and Yu. We prove that the problem is well-defined and (weakly) polynomial when (i) there is a way to reach the target state from any initial state and (ii) there is no transition cycle of negative costs (a generalization of negative cost cycles). These assumptions generalize the standard assumptions for the deterministic shortest path problem and our framework encapsulates the latter problem (in contrast with prior works). In this new setting, we can show that (a) one can restrict to deterministic and stationary policies, (b) the problem is still (weakly) polynomial through linear programming, (c) Value Iteration and Policy Iteration converge, and (d) we can extend Dijkstra's algorithm.
Supervised Learning Based Algorithm Selection for Deep Neural Networks
Venue: arXiv cs.DC 2017
Year: 2017

Many recent deep learning platforms rely on third-party libraries (such as cuBLAS) to utilize the computing power of modern hardware accelerators (such as GPUs). However, we observe that they may achieve suboptimal performance because the library functions are not used appropriately. In this paper, we target at optimizing the operations of multiplying a matrix with the transpose of another matrix (referred to as NT operation hereafter), which contribute about half of the training time of fully connected deep neural networks. Rather than directly calling the library function, we propose a supervised learning based algorithm selection approach named MTNN, which uses a gradient boosted decision tree to select one from two alternative NT implementations intelligently: (1) calling the cuBLAS library function; (2) calling our proposed algorithm TNN that uses an efficient out-of-place matrix transpose. We evaluate the performance of MTNN on two modern GPUs: NVIDIA GTX 1080 and NVIDIA Titan X Pascal. MTNN can achieve 96\% of prediction accuracy with very low computational overhead, which results in an average of 54\% performance improvement on a range of NT operations. To further evaluate the impact of MTNN on the training process of deep neural networks, we have integrated MTNN into a popular deep learning platform Caffe. Our experimental results show that the revised Caffe can outperform the original one by an average of 28\%. Both MTNN and the revised Caffe are open-source.