OpenRaiser/Intern-Atlas huggingface dataset:
Fronthaul-Limited Uplink OFDMA in Ultra-Dense CRAN with Hybrid Decoding
Venue: arXiv cs.IT 2017
Year: 2017

In an ultra-dense cloud radio access network (UD-CRAN), a large number of remote radio heads (RRHs), typically employed as simple relay nodes, are distributed in a target area, which could even outnumber their served users. However, one major challenge is that the large amount of information required to be transferred between each RRH and the central processor (CP) for joint signal processing can easily exceed the capacity of the fronthaul links connecting them. This motivates our study in this paper on a new hybrid decoding scheme where in addition to quantizing and forwarding the received signals for joint decoding at the CP, i.e. forward-and-decode (FaD) as in the conventional CRAN, the RRHs can locally decode-and-forward (DaF) the user messages to save the fronthaul capacity. In particular, we consider the uplink transmission in an orthogonal frequency division multiple access (OFDMA)-based UD-CRAN, where the proposed hybrid decoding is performed on each OFDMA sub-channel (SC). We study a joint optimization of the processing mode selections (DaF or FaD), user-SC assignments and the users' transmit power allocations over all SCs to maximize their weighted-sum-rate subject to the RRHs' individual fronthaul capacity constraints and the users' individual power constraints. Although the problem is non-convex, we propose a Lagrange duality based solution, which can be efficiently computed with good accuracy. Further, we propose a low-complexity greedy algorithm which is shown to achieve close to the optimal performance under practical setups. Simulation results show the promising throughput gains of the proposed designs with hybrid decoding, compared to the existing schemes that perform either DaF or FaD at all SCs.
On the complexity of partial derivatives
Venue: arXiv cs.CC 2017
Year: 2017

The method of partial derivatives is one of the most successful lower bound methods for arithmetic circuits. It uses as a complexity measure the dimension of the span of the partial derivatives of a polynomial. In this paper, we consider this complexity measure as a computational problem: for an input polynomial given as the sum of its nonzero monomials, what is the complexity of computing the dimension of its space of partial derivatives? We show that this problem is #P-hard and we ask whether it belongs to #P. We analyze the "trace method", recently used in combinatorics and in algebraic complexity to lower bound the rank of certain matrices. We show that this method provides a polynomial-time computable lower bound on the dimension of the span of partial derivatives, and from this method we derive closed-form lower bounds. We leave as an open problem the existence of an approximation algorithm with reasonable performance guarantees.A slightly shorter version of this paper was presented at STACS'17. In this new version we have corrected a typo in Section 4.1, and added a reference to Shitov's work on tensor rank.
Wireless Information and Power Transfer: Nonlinearity, Waveform Design and Rate-Energy Tradeoff
Venue: arXiv cs.IT 2017
Year: 2017

The design of Wireless Information and Power Transfer (WIPT) has so far relied on an oversimplified and inaccurate linear model of the energy harvester. In this paper, we depart from this linear model and design WIPT considering the rectifier nonlinearity. We develop a tractable model of the rectifier nonlinearity that is flexible enough to cope with general multicarrier modulated input waveforms. Leveraging that model, we motivate and introduce a novel WIPT architecture relying on the superposition of multi-carrier unmodulated and modulated waveforms at the transmitter. The superposed WIPT waveforms are optimized as a function of the channel state information so as to characterize the rate-energy region of the whole system. Analysis and numerical results illustrate the performance of the derived waveforms and WIPT architecture and highlight that nonlinearity radically changes the design of WIPT. We make key and refreshing observations. First, analysis (confirmed by circuit simulations) shows that modulated and unmodulated waveforms are not equally suitable for wireless power delivery, namely modulation being beneficial in single-carrier transmissions but detrimental in multi-carrier transmissions. Second, a multicarrier unmodulated waveform (superposed to a multi-carrier modulated waveform) is useful to enlarge the rate-energy region of WIPT. Third, a combination of power splitting and time sharing is in general the best strategy. Fourth, a non-zero mean Gaussian input distribution outperforms the conventional capacity-achieving zero-mean Gaussian input distribution in multi-carrier transmissions. Fifth, the rectifier nonlinearity is beneficial to system performance and is essential to efficient WIPT design.
Learning to Recognize Objects by Retaining other Factors of Variation
Venue: arXiv cs.CV 2017
Year: 2017

Natural images are generated under many factors, including shape, pose, illumination etc. Most existing ConvNets formulate object recognition from natural images as a single task classification problem, and attempt to learn features useful for object categories, but invariant to other factors of variation as much as possible. These architectures do not explicitly learn other factors, like pose and lighting, instead, they usually discard them by pooling and normalization. In this work, we take the opposite approach: we train ConvNets for object recognition by retaining other factors (pose in our case) and learn them jointly with object category. We design a new multi-task leaning (MTL) ConvNet, named disentangling CNN (disCNN), which explicitly enforces the disentangled representations of object identity and pose, and is trained to predict object categories and pose transformations. We show that disCNN achieves significantly better object recognition accuracies than AlexNet trained solely to predict object categories on the iLab-20M dataset, which is a large scale turntable dataset with detailed object pose and lighting information. We further show that the pretrained disCNN/AlexNet features on iLab- 20M generalize to object recognition on both Washington RGB-D and ImageNet datasets, and the pretrained disCNN features are significantly better than the pretrained AlexNet features for fine-tuning object recognition on the ImageNet dataset.
Data-driven generation of spatio-temporal routines in human mobility
Venue: arXiv cs.SI 2017
Year: 2017

The generation of realistic spatio-temporal trajectories of human mobility is of fundamental importance in a wide range of applications, such as the developing of protocols for mobile ad-hoc networks or what-if analysis in urban ecosystems. Current generative algorithms fail in accurately reproducing the individuals' recurrent schedules and at the same time in accounting for the possibility that individuals may break the routine during periods of variable duration. In this article we present DITRAS (DIary-based TRAjectory Simulator), a framework to simulate the spatio-temporal patterns of human mobility. DITRAS operates in two steps: the generation of a mobility diary and the translation of the mobility diary into a mobility trajectory. We propose a data-driven algorithm which constructs a diary generator from real data, capturing the tendency of individuals to follow or break their routine. We also propose a trajectory generator based on the concept of preferential exploration and preferential return. We instantiate DITRAS with the proposed diary and trajectory generators and compare the resulting algorithm with real data and synthetic data produced by other generative algorithms, built by instantiating DITRAS with several combinations of diary and trajectory generators. We show that the proposed algorithm reproduces the statistical properties of real trajectories in the most accurate way, making a step forward the understanding of the origin of the spatio-temporal patterns of human mobility.
Tail Index for a Distributed Storage System with Pareto File Size Distribution
Venue: arXiv cs.IT 2017
Year: 2017

Distributed storage systems often employ erasure codes to achieve high data reliability while attaining space efficiency. Such storage systems are known to be susceptible to long tails in response time. It has been shown that in modern online applications such as Bing, Facebook, and Amazon, the long tail of latency is of particular concern, with $99.9$th percentile response times that are orders of magnitude worse than the mean. Taming tail latency is very challenging in erasure-coded storage systems since quantify tail latency (i.e., $x$th-percentile latency for arbitrary $x\in[0,1]$) has been a long-standing open problem. In this paper, we propose a mathematical model to quantify {\em tail index} of service latency for arbitrary erasure-coded storage systems, by characterizing the asymptotic behavior of latency distribution tails. When file size has a heavy tailed distribution, we find tail index, defined as the exponent at which latency tail probability diminishes to zero, in closed-form, and further show that a family of probabilistic scheduling algorithms are (asymptotically) optimal since they are able to achieve the exact tail index.
An Adaptive Parallel Algorithm for Computing Connected Components
Venue: arXiv cs.DC 2017
Year: 2017

We present an efficient distributed memory parallel algorithm for computing connected components in undirected graphs based on Shiloach-Vishkin's PRAM approach. We discuss multiple optimization techniques that reduce communication volume as well as load-balance the algorithm. We also note that the efficiency of the parallel graph connectivity algorithm depends on the underlying graph topology. Particularly for short diameter graph components, we observe that parallel Breadth First Search (BFS) method offers better performance. However, running parallel BFS is not efficient for computing large diameter components or large number of small components. To address this challenge, we employ a heuristic that allows the algorithm to quickly predict the type of the network by computing the degree distribution and follow the optimal hybrid route. Using large graphs with diverse topologies from domains including metagenomics, web crawl, social graph and road networks, we show that our hybrid implementation is efficient and scalable for each of the graph types. Our approach achieves a runtime of 215 seconds using 32K cores of Cray XC30 for a metagenomic graph with over 50 billion edges. When compared against the previous state-of-the-art method, we see performance improvements up to 24x.
Quantum Causal Graph Dynamics
Venue: arXiv cs.DM 2017
Year: 2017

Consider a graph having quantum systems lying at each node. Suppose that the whole thing evolves in discrete time steps, according to a global, unitary causal operator. By causal we mean that information can only propagate at a bounded speed, with respect to the distance given by the graph. Suppose, moreover, that the graph itself is subject to the evolution, and may be driven to be in a quantum superposition of graphs---in accordance to the superposition principle. We show that these unitary causal operators must decompose as a finite-depth circuit of local unitary gates. This unifies a result on Quantum Cellular Automata with another on Reversible Causal Graph Dynamics. Along the way we formalize a notion of causality which is valid in the context of quantum superpositions of time-varying graphs, and has a number of good properties. Keywords: Quantum Lattice Gas Automata, Block-representation, Curtis-Hedlund-Lyndon, No-signalling, Localizability, Quantum Gravity, Quantum Graphity, Causal Dynamical Triangulations, Spin Networks, Dynamical networks, Graph Rewriting.
Network structure and patterns of information diversity on Twitter
Venue: arXiv cs.SI 2017
Year: 2017

Social media have great potential to support diverse information sharing, but there is widespread concern that platforms like Twitter do not result in communication between those who hold contradictory viewpoints. Because users can choose whom to follow, prior research suggests that social media users exist in 'echo chambers' or become polarized. We seek evidence of this in a complete cross section of hyperlinks posted on Twitter, using previously validated measures of the political slant of news sources to study information diversity. Contrary to prediction, we find that the average account posts links to more politically moderate news sources than the ones they receive in their own feed. However, members of a tiny network core do exhibit cross-sectional evidence of polarization and are responsible for the majority of tweets received overall due to their popularity and activity, which could explain the widespread perception of polarization on social media.
A Numerical Investigation of Matrix-Free Implicit Time-Stepping Methods for Large CFD Simulations
Venue: arXiv cs.CE 2017
Year: 2017

This paper is concerned with the development and testing of advanced time-stepping methods suited for the integration of time-accurate, real-world applications of computational fluid dynamics (CFD). The performance of several time discretization methods is studied numerically with regards to computational efficiency, order of accuracy, and stability, as well as the ability to treat effectively stiff problems. We consider matrix-free implementations, a popular approach for time-stepping methods applied to large CFD applications due to its adherence to scalable matrix-vector operations and a small memory footprint. We compare explicit methods with matrix-free implementations of implicit, linearly-implicit, as well as Rosenbrock-Krylov methods. We show that Rosenbrock-Krylov methods are competitive with existing techniques excelling for a number of problem types and settings.
Peak-Piloted Deep Network for Facial Expression Recognition
Venue: arXiv cs.CV 2017
Year: 2017

Objective functions for training of deep networks for face-related recognition tasks, such as facial expression recognition (FER), usually consider each sample independently. In this work, we present a novel peak-piloted deep network (PPDN) that uses a sample with peak expression (easy sample) to supervise the intermediate feature responses for a sample of non-peak expression (hard sample) of the same type and from the same subject. The expression evolving process from non-peak expression to peak expression can thus be implicitly embedded in the network to achieve the invariance to expression intensities. A special purpose back-propagation procedure, peak gradient suppression (PGS), is proposed for network training. It drives the intermediate-layer feature responses of non-peak expression samples towards those of the corresponding peak expression samples, while avoiding the inverse. This avoids degrading the recognition capability for samples of peak expression due to interference from their non-peak expression counterparts. Extensive comparisons on two popular FER datasets, Oulu-CASIA and CK+, demonstrate the superiority of the PPDN over state-ofthe-art FER methods, as well as the advantages of both the network structure and the optimization strategy. Moreover, it is shown that PPDN is a general architecture, extensible to other tasks by proper definition of peak and non-peak samples. This is validated by experiments that show state-of-the-art performance on pose-invariant face recognition, using the Multi-PIE dataset.
Joint Source-Channel Secrecy Using Uncoded Schemes: Towards Secure Source Broadcast
Venue: arXiv cs.IT 2017
Year: 2017

This paper investigates a joint source-channel secrecy problem for the Shannon cipher broadcast system. We suppose list secrecy is applied, i.e., a wiretapper is allowed to produce a list of reconstruction sequences and the secrecy is measured by the minimum distortion over the entire list. For discrete communication cases, we propose a permutation-based uncoded scheme, which cascades a random permutation with a symbol-by-symbol mapping. Using this scheme, we derive an inner bound for the admissible region of secret key rate, list rate, wiretapper distortion, and distortions of legitimate users. For the converse part, we easily obtain an outer bound for the admissible region from an existing result. Comparing the outer bound with the inner bound shows that the proposed scheme is optimal under certain conditions. Besides, we extend the proposed scheme to the scalar and vector Gaussian communication scenarios, and characterize the corresponding performance as well. For these two cases, we also propose another uncoded scheme, orthogonal-transform-based scheme, which achieves the same performance as the permutation-based scheme. Interestingly, by introducing the random permutation or the random orthogonal transform into the traditional uncoded scheme, the proposed uncoded schemes, on one hand, provide a certain level of secrecy, and on the other hand, do not lose any performance in terms of the distortions for legitimate users.
A Cross-Entropy-based Method to Perform Information-based Feature Selection
Venue: arXiv cs.LG 2017
Year: 2017

From a machine learning point of view, identifying a subset of relevant features from a real data set can be useful to improve the results achieved by classification methods and to reduce their time and space complexity. To achieve this goal, feature selection methods are usually employed. These approaches assume that the data contains redundant or irrelevant attributes that can be eliminated. In this work, we propose a novel algorithm to manage the optimization problem that is at the foundation of the Mutual Information feature selection methods. Furthermore, our novel approach is able to estimate automatically the number of dimensions to retain. The quality of our method is confirmed by the promising results achieved on standard real data sets.
Mesh Denoising based on Normal Voting Tensor and Binary Optimization
Venue: arXiv cs.CV 2017
Year: 2017

This paper presents a tensor multiplication based smoothing algorithm that follows a two step denoising method. Unlike other traditional averaging approaches, our approach uses an element based normal voting tensor to compute smooth surfaces. By introducing a binary optimization on the proposed tensor together with a local binary neighborhood concept, our algorithm better retains sharp features and produces smoother umbilical regions than previous approaches. On top of that, we provide a stochastic analysis on the different kinds of noise based on the average edge length. The quantitative and visual results demonstrate the performance our method is better compared to state of the art smoothing approaches.
A Hierarchy of Lower Bounds for Sublinear Additive Spanners
Venue: arXiv cs.DS 2017
Year: 2017

Spanners, emulators, and approximate distance oracles can be viewed as lossy compression schemes that represent an unweighted graph metric in small space, say $\tilde{O}(n^{1+δ})$ bits. There is an inherent tradeoff between the sparsity parameter $δ$ and the stretch function $f$ of the compression scheme, but the qualitative nature of this tradeoff has remained a persistent open problem. In this paper we show that the recent additive spanner lower bound of Abboud and Bodwin is just the first step in a hierarchy of lower bounds that fully characterize the asymptotic behavior of the optimal stretch function $f$ as a function of $δ\in (0,1/3)$. Specifically, for any integer $k\ge 2$, any compression scheme with size $O(n^{1+\frac{1}{2^k-1} - ε})$ has a sublinear additive stretch function $f$: $$f(d) = d + Ω(d^{1-\frac{1}{k}}).$$ This lower bound matches Thorup and Zwick's (2006) construction of sublinear additive emulators. It also shows that Elkin and Peleg's $(1+ε,β)$-spanners have an essentially optimal tradeoff between $δ,ε,$ and $β$, and that the sublinear additive spanners of Pettie (2009) and Chechik (2013) are not too far from optimal. To complement these lower bounds we present a new construction of $(1+ε, O(k/ε)^{k-1})$-spanners with size $O((k/ε)^{h_k} kn^{1+\frac{1}{2^{k+1}-1}})$, where $h_k < 3/4$. This size bound improves on the spanners of Elkin and Peleg (2004), Thorup and Zwick (2006), and Pettie (2009). According to our lower bounds neither the size nor stretch function can be substantially improved.
Hierarchical Multi-resolution Mesh Networks for Brain Decoding
Venue: arXiv cs.NE 2017
Year: 2017

We propose a new framework, called Hierarchical Multi-resolution Mesh Networks (HMMNs), which establishes a set of brain networks at multiple time resolutions of fMRI signal to represent the underlying cognitive process. The suggested framework, first, decomposes the fMRI signal into various frequency subbands using wavelet transforms. Then, a brain network, called mesh network, is formed at each subband by ensembling a set of local meshes. The locality around each anatomic region is defined with respect to a neighborhood system based on functional connectivity. The arc weights of a mesh are estimated by ridge regression formed among the average region time series. In the final step, the adjacency matrices of mesh networks obtained at different subbands are ensembled for brain decoding under a hierarchical learning architecture, called, fuzzy stacked generalization (FSG). Our results on Human Connectome Project task-fMRI dataset reflect that the suggested HMMN model can successfully discriminate tasks by extracting complementary information obtained from mesh arc weights of multiple subbands. We study the topological properties of the mesh networks at different resolutions using the network measures, namely, node degree, node strength, betweenness centrality and global efficiency; and investigate the connectivity of anatomic regions, during a cognitive task. We observe significant variations among the network topologies obtained for different subbands. We, also, analyze the diversity properties of classifier ensemble, trained by the mesh networks in multiple subbands and observe that the classifiers in the ensemble collaborate with each other to fuse the complementary information freed at each subband. We conclude that the fMRI data, recorded during a cognitive task, embed diverse information across the anatomic regions at each resolution.
$H$-supermagic labelings for firecrackers, banana trees and flowers
Venue: arXiv cs.DM 2017
Year: 2017

A simple graph $G=(V,E)$ admits an $H$-covering if every edge in $E$ is contained in a subgraph $H'=(V',E')$ of $G$ which is isomorphic to $H$. In this case we say that $G$ is $H$-supermagic if there is a bijection $f:V\cup E\to\{1,\ldots\lvert V\rvert+\lvert E\rvert\}$ such that $f(V)=\{1,\ldots,\lvert V\rvert\}$ and $\sum_{v\in V(H')}f(v)+\sum_{e\in E(H')}f(e)$ is constant over all subgraphs $H'$ of $G$ which are isomorphic to $H$. In this paper, we show that for odd $n$ and arbitrary $k$, the firecracker $F_{k,n}$ is $F_{2,n}$-supermagic, the banana tree $B_{k,n}$ is $B_{1,n}$-supermagic and the flower $F_n$ is $C_3$-supermagic.