OpenRaiser/Intern-Atlas huggingface dataset:
The Theory of Computational Quasi-conformal Geometry on Point Clouds
Venue: arXiv cs.CG 2015
Year: 2015

Quasi-conformal (QC) theory is an important topic in complex analysis, which studies geometric patterns of deformations between shapes. Recently, computational QC geometry has been developed and has made significant contributions to medical imaging, computer graphics and computer vision. Existing computational QC theories and algorithms have been built on triangulation structures. In practical situations, many 3D acquisition techniques often produce 3D point cloud (PC) data of the object, which does not contain connectivity information. It calls for a need to develop computational QC theories on PCs. In this paper, we introduce the concept of computational QC geometry on PCs. We define PC quasi-conformal (PCQC) maps and their associated PC Beltrami coefficients (PCBCs). The PCBC is analogous to the Beltrami differential in the continuous setting. Theoretically, we show that the PCBC converges to its continuous counterpart as the density of the PC tends to zero. We also theoretically and numerically validate the ability of PCBCs to measure local geometric distortions of PC deformations. With these concepts, many existing QC based algorithms for geometry processing and shape analysis can be easily extended to PC data.
Assessing The Performance Bounds Of Local Feature Detectors: Taking Inspiration From Electronics Design Practices
Venue: arXiv cs.CV 2015
Year: 2015

Since local feature detection has been one of the most active research areas in computer vision, a large number of detectors have been proposed. This has rendered the task of characterizing the performance of various feature detection methods an important issue in vision research. Inspired by the good practices of electronic system design, a generic framework based on the improved repeatability measure is presented in this paper that allows assessment of the upper and lower bounds of detector performance in an effort to design more reliable and effective vision systems. This framework is then employed to establish operating and guarantee regions for several state-of-the art detectors for JPEG compression and uniform light changes. The results are obtained using a newly acquired, large image database (15092 images) with 539 different scenes. These results provide new insights into the behavior of detectors and are also useful from the vision systems design perspective.
Signal Processing Structures for Solving Conservative Constraint Satisfaction Problems
Venue: arXiv cs.NA 2015
Year: 2015

This primary purpose of this paper is to succinctly state a number of verifiable and tractable sufficient conditions under which a particular class of conservative signal processing structures may be readily used to solve a companion class of constraint satisfaction problems using both synchronous and asynchronous implementation protocols. In particular, the mentioned class of structures is shown to have desirable convergence and robustness properties with respect to various uncertainties involving communication and processing delays. Essential ingredients to the arguments herein involve blending together functional composition methods, conservation principles, asynchronous signal processing implementation protocols, and methods of homotopy. Numerical experiments complement the theoretical presentation and connections to optimization theory are made.
Several classes of cyclic codes with either optimal three weights or a few weights
Venue: arXiv cs.IT 2015
Year: 2015

Cyclic codes with a few weights are very useful in the design of frequency hopping sequences and the development of secret sharing schemes. In this paper, we mainly use Gauss sums to represent the Hamming weights of a general construction of cyclic codes. As applications, we obtain a class of optimal three-weight codes achieving the Griesmer bound, which generalizes a Vega's result in \cite{V1}, and several classes of cyclic codes with only a few weights, which solve the open problem in \cite{V1}.
Out-of-Band Radiation Measure for MIMO Arrays with Beamformed Transmission
Venue: arXiv cs.IT 2015
Year: 2015

The spatial characteristics of the out-of-band radiation that a multiuser MIMO system emits in the environment, due to its power amplifiers (modeled by a polynomial model) are nonlinear, is studied by deriving an analytical expression for the continuous-time cross-correlation of the transmit signals. At a random spatial point, the same power is received at any frequency on average with a MIMO base station as with a SISO base station when the two radiate the same amount of power. For a specific channel realization however, the received power depends on the channel. We show that the power received out-of-band only deviates little from the average in a MIMO system with multiple users and that the deviation can be significant with only one user. Using an ergodicity argument, we conclude that out-of-band radiation is less of a problem in massive MIMO, where total radiated power is lower compared to SISO systems and that requirements on spectral regrowth can be relaxed in MIMO systems without causing more total out-of-band radiation.
Dawn of the Selfie Era: The Whos, Wheres, and Hows of Selfies on Instagram
Venue: arXiv cs.SI 2015
Year: 2015

Online interactions are increasingly involving images, especially those containing human faces, which are naturally attention grabbing and more effective at conveying feelings than text. To understand this new convention of digital culture, we study the collective behavior of sharing selfies on Instagram and present how people appear in selfies and which patterns emerge from such interactions. Analysis of millions of photos shows that the amount of selfies has increased by 900 times from 2012 to 2014. Selfies are an effective medium to grab attention; they generate on average 1.1--3.2 times more likes and comments than other types of content on Instagram. Compared to other content, interactions involving selfies exhibit variations in homophily scores (in terms of age and gender) that suggest they are becoming more widespread. Their style also varies by cultural boundaries in that the average age and majority gender seen in selfies differ from one country to another. We provide explanations of such country-wise variations based on cultural and socioeconomic contexts.
Finite dynamical systems, hat games, and coding theory
Venue: arXiv cs.IT 2015
Year: 2015

The dynamical properties of finite dynamical systems (FDSs) have been investigated in the context of coding theoretic problems, such as network coding and index coding, and in the context of hat games, such as the guessing game and Winkler's hat game. In this paper, we relate the problems mentioned above to properties of FDSs, including the number of fixed points, their stability, and their instability. We first introduce the guessing dimension and the coset dimension of an FDS and their counterparts for digraphs. Based on the coset dimension, we then strengthen the existing equivalences between network coding and index coding. We also introduce the instability of FDSs and we study the stability and the instability of digraphs. We prove that the instability always reaches the size of a minimum feedback vertex set. We also obtain some non-stable bounds independent of the number of vertices of the graph. We then relate the stability and the instability to the guessing number. We also exhibit a class of sparse graphs with large girth that have high stability and high instability; our approach is code-theoretic and uses the guessing dimension. Finally, we prove that the affine instability is always asymptotically greater than or equal to the linear guessing number.
What's the point? Frame-wise Pointing Gesture Recognition with Latent-Dynamic Conditional Random Fields
Venue: arXiv cs.HC 2015
Year: 2015

We use Latent-Dynamic Conditional Random Fields to perform skeleton-based pointing gesture classification at each time instance of a video sequence, where we achieve a frame-wise pointing accuracy of roughly 83%. Subsequently, we determine continuous time sequences of arbitrary length that form individual pointing gestures and this way reliably detect pointing gestures at a false positive detection rate of 0.63%.
Safety-Constrained Reinforcement Learning for MDPs
Venue: arXiv cs.SE 2015
Year: 2015

We consider controller synthesis for stochastic and partially unknown environments in which safety is essential. Specifically, we abstract the problem as a Markov decision process in which the expected performance is measured using a cost function that is unknown prior to run-time exploration of the state space. Standard learning approaches synthesize cost-optimal strategies without guaranteeing safety properties. To remedy this, we first compute safe, permissive strategies. Then, exploration is constrained to these strategies and thereby meets the imposed safety requirements. Exploiting an iterative learning procedure, the resulting policy is safety-constrained and optimal. We show correctness and completeness of the method and discuss the use of several heuristics to increase its scalability. Finally, we demonstrate the applicability by means of a prototype implementation.
Ultra Dense Networks: The New Wireless Frontier for Enabling 5G Access
Venue: arXiv cs.IT 2015
Year: 2015

The extreme traffic load that future wireless networks are expected to accommodate requires a re-thinking of the system design. Initial estimations indicate that, different from the evolutionary path of previous cellular generations that was based on spectral efficiency improvements, the most substantial amount of future system performance gains will be obtained by means of network infrastructure densification. By increasing the density of operator-deployed infrastructure elements, along with incorporation of user-deployed access nodes and mobile user devices acting as "infrastructure prosumers", it is expected that having one or more access nodes exclusively dedicated to each user will become feasible, introducing the ultra dense network (UDN) paradigm. Although it is clear that UDNs are able to take advantage of the significant benefits provided by proximal transmissions and increased spatial reuse of system resources, at the same time, large node density and irregular deployment introduce new challenges, mainly due to the interference environment characteristics that are vastly different from previous cellular deployments. This article attempts to provide insights on fundamental issues related to UDN deployment, such as determining the infrastructure density required to support given traffic load requirements and the benefits of network-wise coordination, demonstrating the potential of UDNs for 5G wireless networks.
Bounded Control for Double Integrator in Quadrotor Dynamics
Venue: arXiv cs.SY 2015
Year: 2015

We construct a trajectory tracking controller for a quadrotor system by finding a coordinate change which transforms the quadrotor's vector field into that of a thrust propelled system. In a thrust propelled system, the goal is to stabilize its position around the origin, while the system is actuated by a one dimensional acceleration/thrust along a direction vector, by a time-varying gravity, and by the angular acceleration of the direction vector. For this system, a solution has been proposed in a companion article, submitted to ECC 2016, based on the implicit knowledge of a bounded controller for a double integrator system, and on the implicit knowledge of a Lyapunov function that guarantees the origin is asymptotically stable for the double integrator controlled by the bounded controller. We present two alternative bounded controllers for a double integrator system, and corresponding Lyapunov functions.
Optimal Large-MIMO Data Detection with Transmit Impairments
Venue: arXiv cs.IT 2015
Year: 2015

Real-world transceiver designs for multiple-input multiple-output (MIMO) wireless communication systems are affected by a number of hardware impairments that already appear at the transmit side, such as amplifier non-linearities, quantization artifacts, and phase noise. While such transmit-side impairments are routinely ignored in the data-detection literature, they often limit reliable communication in practical systems. In this paper, we present a novel data-detection algorithm, referred to as large-MIMO approximate message passing with transmit impairments (short LAMA-I), which takes into account a broad range of transmit-side impairments in wireless systems with a large number of transmit and receive antennas. We provide conditions in the large-system limit for which LAMA-I achieves the error-rate performance of the individually-optimal (IO) data detector. We furthermore demonstrate that LAMA-I achieves near-IO performance at low computational complexity in realistic, finite dimensional large-MIMO systems.
Utility Maximization for Single-Station User Association in Downlink Cellular Networks
Venue: arXiv cs.NI 2015
Year: 2015

We study network utility maximization (NUM) in the context of cellular single station association (SSA) policies, which assigns each mobile user (MU) to a single base station (BS). We measure an SSA policy in terms of the induced α-proportional fairness utility of each user's downlink rate, summed over all users. The general SSA NUM problem involves choosing an optimal association from MUs to BSs as well as an optimal allocation of BS resources to associated MUs. Finding an exact solution to such centralized user association problems is well-known to be NP-hard. Our contributions are as follows: i) we give an explicit solution for the optimal BS allocation for a given SSA, which establishes SSA NUM as a purely combinatiorial problem; ii) we establish the integrality gap for the association problem to be one, and prove the relaxation to be a non-convex optimization problem; iii) we provide both centralized and distributed greedy algorithms for SSA, both with and without the exchange of instantaneous rate information between users and stations. Our numerical results illustrate performance gains of three classes of solutions: i) SSA solutions obtained by greedy rounding of multi-station associations (a centralized convex program), ii) our centralized and distributed greedy algorithms with/without rate information exchanged, and iii) simple association heuristics.
Hierarchy of knowledge translation: from health problems to ad-hoc drug design
Venue: arXiv cs.SI 2015
Year: 2015

An innovative approach to analyze the complexity of translating novel molecular entities and nanomaterials into pharmaceutical alternatives (i.e., knowledge translation, KT) is discussed. First, some key concepts on the organization and translation of the biomedical knowledge (paradigms, homophily, power law distributions, hierarchy, modularity, and research fronts) are reviewed. Then, we propose a model for the knowledge translation (KT) in Drug Discovery that considers the complexity of interdisciplinary communication. Specifically, we address two highly relevant aspects: 1) A successful KT requires the emergence of organized bodies of inter-and transdisciplinary research, and 2) The hierarchical and modular topological organization of these bodies of knowledge. We focused on a set of previously-published studies on KT which rely on a combination of network analysis and computer-assisted analysis of the contents of scientific literature and patents. The selected studies provide a duo of complementary perspectives: the demand of knowledge (cervical cancer and Ebola hemorrhagic fever) and the supply of knowledge (liposomes and nanoparticles to treat cancer and the paradigmatic Doxil, the first nanodrug to be approved).
Hypergraph-Based Analysis of Clustered Cooperative Beamforming with Application to Edge Caching
Venue: arXiv cs.IT 2015
Year: 2015

The evaluation of the performance of clustered cooperative beamforming in cellular networks generally requires the solution of complex non-convex optimization problems. In this letter, a framework based on a hypergraph formalism is proposed that enables the derivation of a performance characterization of clustered cooperative beamforming in terms of per-user degrees of freedom (DoF) via the efficient solution of a coloring problem. An emerging scenario in which clusters of cooperative base stations (BSs) arise is given by cellular networks with edge caching. In fact, clusters of BSs that share the same requested files can jointly beamform the corresponding encoded signals. Based on this observation, the proposed framework is applied to obtain quantitative insights into the optimal use of cache and backhaul resources in cellular systems with edge caching. Numerical examples are provided to illustrate the merits of the proposed framework.
Optimal Temporal Logic Planning in Probabilistic Semantic Maps
Venue: arXiv cs.RO 2015
Year: 2015

This paper considers robot motion planning under temporal logic constraints in probabilistic maps obtained by semantic simultaneous localization and mapping (SLAM). The uncertainty in a map distribution presents a great challenge for obtaining correctness guarantees with respect to the linear temporal logic (LTL) specification. We show that the problem can be formulated as an optimal control problem in which both the semantic map and the logic formula evaluation are stochastic. Our first contribution is to reduce the stochastic control problem for a subclass of LTL to a deterministic shortest path problem by introducing a confidence parameter $delta$. A robot trajectory obtained from the deterministic problem is guaranteed to have minimum cost and to satisfy the logic specification in the true environment with probability $delta$. Our second contribution is to design an admissible heuristic function that guides the planning in the deterministic problem towards satisfying the temporal logic specification. This allows us to obtain an optimal and very efficient solution using the A* algorithm. The performance and correctness of our approach are demonstrated in a simulated semantic environment using a differential-drive robot.
Spectrum Sensing Under Hardware Constraints
Venue: arXiv cs.IT 2015
Year: 2015

Direct-conversion radio (DCR) receivers can offer highly integrated low-cost hardware solutions for spectrum sensing in cognitive radio systems. However, DCR receivers are susceptible to radio frequency (RF) impairments, such as in-phase and quadrature-phase imbalance, low-noise amplifier nonlinearities and phase noise, which limit the spectrum sensing capabilities. In this paper, we investigate the joint effects of RF impairments on energy detection based spectrum sensing for cognitive radio (CR) systems in multi-channel environments. In particular, we provide closed-form expressions for the evaluation of the detection and false alarm probabilities, assuming Rayleigh fading. Furthermore, we extend the analysis to the case of CR networks with cooperative sensing, where the secondary users suffer from different levels of RF imperfections, considering both scenarios of error free and imperfect reporting channel. Numerical and simulation results demonstrate the accuracy of the analysis as well as the detrimental effects of RF imperfections on the spectrum sensing performance, which bring significant losses in the spectrum~utilization.
Hollow Heaps
Venue: arXiv cs.DS 2015
Year: 2015

We introduce the hollow heap, a very simple data structure with the same amortized efficiency as the classical Fibonacci heap. All heap operations except delete and delete-min take $O(1)$ time, worst case as well as amortized; delete and delete-min take $O(\log n)$ amortized time on a heap of $n$ items. Hollow heaps are by far the simplest structure to achieve this. Hollow heaps combine two novel ideas: the use of lazy deletion and re-insertion to do decrease-key operations, and the use of a dag (directed acyclic graph) instead of a tree or set of trees to represent a heap. Lazy deletion produces hollow nodes (nodes without items), giving the data structure its name.
Efficient Unsupervised Temporal Segmentation of Motion Data
Venue: arXiv cs.CV 2015
Year: 2015

We introduce a method for automated temporal segmentation of human motion data into distinct actions and compositing motion primitives based on self-similar structures in the motion sequence. We use neighbourhood graphs for the partitioning and the similarity information in the graph is further exploited to cluster the motion primitives into larger entities of semantic significance. The method requires no assumptions about the motion sequences at hand and no user interaction is required for the segmentation or clustering. In addition, we introduce a feature bundling preprocessing technique to make the segmentation more robust to noise, as well as a notion of motion symmetry for more refined primitive detection. We test our method on several sensor modalities, including markered and markerless motion capture as well as on electromyograph and accelerometer recordings. The results highlight our system's capabilities for both segmentation and for analysis of the finer structures of motion data, all in a completely unsupervised manner.
Full-Duplex Radio for Uplink/Downlink Wireless Access with Spatially Random Nodes
Venue: arXiv cs.IT 2015
Year: 2015

A full-duplex (FD) multiple antenna access point (AP) communicating with single antenna half-duplex (HD) spatially random users to support simultaneous uplink (UL)/downlink (DL) transmissions is investigated. Since FD nodes are inherently constrained by the loopback interference (LI), we study precoding schemes for the AP based on maximum ratio combining (MRC)/maximal ratio transmission (MRT), zero-forcing and the optimal scheme for UL and DL sum rate maximization using tools from stochastic geometry. In order to shed insights into the system's performance, simple expressions for single antenna/perfect LI cancellation/negligible internode interference cases are also presented. We show that FD precoding at AP improves the UL/DL sum rate and hence a doubling of the performance of the HD mode is achievable. In particular, our results show that these impressive performance gains remain substantially intact even if the LI cancellation is imperfect. Furthermore, relative performance gap between FD and HD modes increases as the number of transmit/receive antennas becomes large, while with the MRC/MRT scheme, increasing the receive antenna number at FD AP, is more beneficial in terms of sum rate than increasing the transmit antenna number.
NXgraph: An Efficient Graph Processing System on a Single Machine
Venue: arXiv cs.DB 2015
Year: 2015

Recent studies show that graph processing systems on a single machine can achieve competitive performance compared with cluster-based graph processing systems. In this paper, we present NXgraph, an efficient graph processing system on a single machine. With the abstraction of vertex intervals and edge sub-shards, we propose the Destination-Sorted Sub-Shard (DSSS) structure to store a graph. By dividing vertices and edges into intervals and sub-shards, NXgraph ensures graph data access locality and enables fine-grained scheduling. By sorting edges within each sub-shard according to their destination vertices, NXgraph reduces write conflicts among different threads and achieves a high degree of parallelism. Then, three updating strategies, i.e., Single-Phase Update (SPU), Double-Phase Update (DPU), and Mixed-Phase Update (MPU), are proposed in this paper. NXgraph can adaptively choose the fastest strategy for different graph problems according to the graph size and the available memory resources to fully utilize the memory space and reduce the amount of data transfer. All these three strategies exploit streamlined disk access pattern. Extensive experiments on three real-world graphs and five synthetic graphs show that NXgraph can outperform GraphChi, TurboGraph, VENUS, and GridGraph in various situations. Moreover, NXgraph, running on a single commodity PC, can finish an iteration of PageRank on the Twitter graph with 1.5 billion edges in 2.05 seconds; while PowerGraph, a distributed graph processing system, needs 3.6s to finish the same task.