OpenRaiser/Intern-Atlas huggingface dataset:
Assessing 3D scan quality in Virtual Reality through paired-comparisons psychophysics test
Venue: arXiv cs.HC 2017
Year: 2017

Consumer 3D scanners and depth cameras are increasingly being used to generate content and avatars for Virtual Reality (VR) environments and avoid the inconveniences of hand modeling; however, it is sometimes difficult to evaluate quantitatively the mesh quality at which 3D scans should be exported, and whether the object perception might be affected by its shading. We propose using a paired-comparisons test based on psychophysics of perception to do that evaluation. As psychophysics is not subject to opinion, skill level, mental state, or economic situation it can be considered a quantitative way to measure how people perceive the mesh quality. In particular, we propose using the psychophysical measure for the comparison of four different levels of mesh quality (1K, 5K, 10K and 20K triangles). We present two studies within subjects: in one we investigate the quality perception variations of seeing an object in a regular screen monitor against an stereoscopic Head Mounted Display (HMD); while in the second experiment we aim at detecting the effects of shading into quality perception. At each iteration of the pair-test comparisons participants pick the mesh that they think had higher quality; by the end of the experiment we compile a preference matrix. The matrix evidences the correlation between real quality and assessed quality. Regarding the shading mode, we find an interaction with quality and shading when the model has high definition. Furthermore, we assess the subjective realism of the most/least preferred scans using an Immersive Augmented Reality (IAR) video-see-through setup. Results show higher levels of realism were perceived through the HMD than when using a monitor, although the quality was similarly perceived in both systems.
Distributed Multi-Relay Selection in Accumulate-then-Forward Energy Harvesting Relay Networks
Venue: arXiv cs.IT 2017
Year: 2017

This paper investigates a wireless-powered cooperative network (WPCN) consisting of one source-destination pair and multiple decode-and-forward (DF) relays. We develop an energy threshold based multi-relay selection (ETMRS) scheme for the considered WPCN. The proposed ETMRS scheme can be implemented in a fully distributed manner as the relays only need local information to switch between energy harvesting and information forwarding modes. By modeling the charging/discharging behaviours of the finite-capacity battery at each relay as a finite-state Markov Chain (MC), we derive an analytical expression for the system outage probability of the proposed ETMRS scheme over mixed Nakagami-$m$ and Rayleigh fading channels. Based on the derived expression, the optimal energy thresholds for all the relays corresponding to the minimum system outage probability can be obtained via an exhaustive search. However, this approach becomes computationally prohibitive when the number of relays and the associated number of battery energy levels is large. To resolve this issue, we propose a heuristic approach to optimize the energy threshold for each relay. To gain some useful insights for practical relay design, we also derive the upper bound for system outage probability corresponding to the case that all relays are equipped with infinite-capacity batteries. Numerical results validate our theoretical analysis. It is shown that the proposed heuristic approach can achieve a near-optimal system performance and our ETMRS scheme outperforms the existing single-relay selection scheme and common energy threshold scheme.
Throughput Analysis of Massive MIMO Uplink with Low-Resolution ADCs
Venue: arXiv cs.IT 2017
Year: 2017

We investigate the uplink throughput achievable by a multiple-user (MU) massive multiple-input multiple-output (MIMO) system in which the base station is equipped with a large number of low-resolution analog-to-digital converters (ADCs). Our focus is on the case where neither the transmitter nor the receiver have any a priori channel state information. This implies that the fading realizations have to be learned through pilot transmission followed by channel estimation at the receiver, based on coarsely quantized observations. We propose a novel channel estimator, based on Bussgang's decomposition, and a novel approximation to the rate achievable with finite-resolution ADCs, both for the case of finite-cardinality constellations and of Gaussian inputs, that is accurate for a broad range of system parameters. Through numerical results, we illustrate that, for the 1-bit quantized case, pilot-based channel estimation together with maximal-ratio combing or zero-forcing detection enables reliable multi-user communication with high-order constellations in spite of the severe nonlinearity introduced by the ADCs. Furthermore, we show that the rate achievable in the infinite-resolution (no quantization) case can be approached using ADCs with only a few bits of resolution. We finally investigate the robustness of low-ADC-resolution MU-MIMO uplink against receive power imbalances between the different users, caused for example by imperfect power control.
Cooperative Hierarchical Caching in 5G Cloud Radio Access Networks (C-RANs)
Venue: arXiv cs.IT 2017
Year: 2017

Over the last few years, Cloud Radio Access Network (C-RAN) has arisen as a transformative architecture for 5G cellular networks that brings the flexibility and agility of cloud computing to wireless communications. At the same time, content caching in wireless networks has become an essential solution to lower the content-access latency and backhaul traffic loading, which translate into user Quality of Experience (QoE) improvement and network cost reduction. In this article, a novel Cooperative Hierarchical Caching (CHC) framework in C-RAN is introduced where contents are jointly cached at the BaseBand Unit (BBU) and at the Radio Remote Heads (RRHs). Unlike in traditional approaches, the cache at the BBU, cloud cache, presents a new layer in the cache hierarchy, bridging the latency/capacity gap between the traditional edge-based and core-based caching schemes. Trace-driven simulations reveal that CHC yields up to 80% improvement in cache hit ratio, 21% decrease in average content-access latency, and 20% reduction in backhaul traffic load compared to the edge-only caching scheme with the same total cache capacity. Before closing the article, several challenges and promising opportunities for deploying content caching in C-RAN are highlighted towards a content-centric mobile wireless network.
Efficient Second Order Online Learning by Sketching
Venue: arXiv cs.LG 2017
Year: 2017

We propose Sketched Online Newton (SON), an online second order learning algorithm that enjoys substantially improved regret guarantees for ill-conditioned data. SON is an enhanced version of the Online Newton Step, which, via sketching techniques enjoys a running time linear in the dimension and sketch size. We further develop sparse forms of the sketching methods (such as Oja's rule), making the computation linear in the sparsity of features. Together, the algorithm eliminates all computational obstacles in previous second order online learning approaches.
Ensemble Robustness and Generalization of Stochastic Deep Learning Algorithms
Venue: arXiv cs.LG 2017
Year: 2017

The question why deep learning algorithms generalize so well has attracted increasing research interest. However, most of the well-established approaches, such as hypothesis capacity, stability or sparseness, have not provided complete explanations (Zhang et al., 2016; Kawaguchi et al., 2017). In this work, we focus on the robustness approach (Xu & Mannor, 2012), i.e., if the error of a hypothesis will not change much due to perturbations of its training examples, then it will also generalize well. As most deep learning algorithms are stochastic (e.g., Stochastic Gradient Descent, Dropout, and Bayes-by-backprop), we revisit the robustness arguments of Xu & Mannor, and introduce a new approach, ensemble robustness, that concerns the robustness of a population of hypotheses. Through the lens of ensemble robustness, we reveal that a stochastic learning algorithm can generalize well as long as its sensitiveness to adversarial perturbations is bounded in average over training examples. Moreover, an algorithm may be sensitive to some adversarial examples (Goodfellow et al., 2015) but still generalize well. To support our claims, we provide extensive simulations for different deep learning algorithms and different network architectures exhibiting a strong correlation between ensemble robustness and the ability to generalize.
Finite-Frequency Model Order Reduction of Linear Systems via Parameterized Frequency-dependent Balanced Truncation
Venue: arXiv cs.SY 2017
Year: 2017

Balanced truncation is one of the most common model order reduction schemes. In this paper, we study finite-frequency model order reduction (FF-MOR) problems of linear continuous-time systems within the framework of balanced truncation method. Firstly, we construct a family of parameterized frequency-dependent (PFD) mappings which generate discrete-time PFD mapped systems and continuous-time PFD mapped systems of the given continuous-time system. The relationships between the maximum singular value of the given system over pre-specified frequency ranges and the maximum singular value of the PFD mapped systems over entire frequency range are established. By exploiting the properties of the discrete-time PFD mapped systems, a new parameterized frequency-dependent balanced truncation (PFDBT) method providing finite-frequency type error bound with respect to the maximum singular value of the approximation error systems are developed. Examples are included for illustration.
Beyond Good and Evil: Formalizing the Security Guarantees of Compartmentalizing Compilation
Venue: arXiv cs.CR 2017
Year: 2017

Compartmentalization is good security-engineering practice. By breaking a large software system into mutually distrustful components that run with minimal privileges, restricting their interactions to conform to well-defined interfaces, we can limit the damage caused by low-level attacks such as control-flow hijacking. When used to defend against such attacks, compartmentalization is often implemented cooperatively by a compiler and a low-level compartmentalization mechanism. However, the formal guarantees provided by such compartmentalizing compilation have seen surprisingly little investigation. We propose a new security property, secure compartmentalizing compilation (SCC), that formally characterizes the guarantees provided by compartmentalizing compilation and clarifies its attacker model. We reconstruct our property by starting from the well-established notion of fully abstract compilation, then identifying and lifting three important limitations that make standard full abstraction unsuitable for compartmentalization. The connection to full abstraction allows us to prove SCC by adapting established proof techniques; we illustrate this with a compiler from a simple unsafe imperative language with procedures to a compartmentalized abstract machine.
On the insertion time of random walk cuckoo hashing
Venue: arXiv cs.DS 2017
Year: 2017

Cuckoo Hashing is a hashing scheme invented by Pagh and Rodler. It uses $d\geq 2$ distinct hash functions to insert items into the hash table. It has been an open question for some time as to the expected time for Random Walk Insertion to add items. We show that if the number of hash functions $d=O(1)$ is sufficiently large, then the expected insertion time is $O(1)$ per item.
Spectrum graph coloring and applications to WiFi channel assignment
Venue: arXiv cs.DM 2017
Year: 2017

We introduce and explore a family of vertex-coloring problems which, surprisingly enough, have not been considered before despite stemming from the problem of Wi-Fi channel assignment. Given a spectrum of colors, endowed with a matrix of interferences between each pair of colors, the Threshold Spectrum Coloring problem fixes the number of colors available and aims to minimize the interference threshold, i.e., the maximum of the interferences at the vertices. Conversely, the Chromatic Spectrum Coloring problem fixes a threshold and aims to minimize the number of colors for which respecting that threshold is possible. As main theoretical results, we prove tight upper bounds for the solutions to each problem. Since both problems turn out to be NP-hard, we complete the scene with experimental results. We propose a DSATUR-based heuristic and study its performance to minimize the maximum vertex interference in Wi-Fi channel assignment, both for randomly generated graphs and for a real-world scenario. Further, for all these graphs we experimentally check the goodness of the theoretical bounds.
Peak Criterion for Choosing Gaussian Kernel Bandwidth in Support Vector Data Description
Venue: arXiv cs.LG 2017
Year: 2017

Support Vector Data Description (SVDD) is a machine-learning technique used for single class classification and outlier detection. SVDD formulation with kernel function provides a flexible boundary around data. The value of kernel function parameters affects the nature of the data boundary. For example, it is observed that with a Gaussian kernel, as the value of kernel bandwidth is lowered, the data boundary changes from spherical to wiggly. The spherical data boundary leads to underfitting, and an extremely wiggly data boundary leads to overfitting. In this paper, we propose empirical criterion to obtain good values of the Gaussian kernel bandwidth parameter. This criterion provides a smooth boundary that captures the essential geometric features of the data.
Geo-spatial Location Spoofing Detection for Internet of Things
Venue: arXiv cs.CR 2017
Year: 2017

We develop a new location spoofing detection algorithm for geo-spatial tagging and location-based services in the Internet of Things (IoT), called Enhanced Location Spoofing Detection using Audibility (ELSA) which can be implemented at the backend server without modifying existing legacy IoT systems. ELSA is based on a statistical decision theory framework and uses two-way time-of-arrival (TW-TOA) information between the user's device and the anchors. In addition to the TW-TOA information, ELSA exploits the implicit available audibility information to improve detection rates of location spoofing attacks. Given TW-TOA and audibility information, we derive the decision rule for the verification of the device's location, based on the generalized likelihood ratio test. We develop a practical threat model for delay measurements spoofing scenarios, and investigate in detail the performance of ELSA in terms of detection and false alarm rates. Our extensive simulation results on both synthetic and real-world datasets demonstrate the superior performance of ELSA compared to conventional non-audibility-aware approaches.
Consensus in Rooted Dynamic Networks with Short-Lived Stability
Venue: arXiv cs.DC 2017
Year: 2017

We consider the problem of solving consensus using deterministic algorithms in a synchronous dynamic network with unreliable, directional point-to-point links, which are under the control of a message adversary. In contrast to a large body of existing work that focuses on oblivious message adversaries where the communication graphs are picked from a predefined set, we consider message adversaries where guarantees about stable periods that occur only eventually can be expressed. We reveal to what extent such eventual stability is necessary and sufficient, that is, we present the shortest period of stability that permits solving consensus, a result that should prove quite useful in systems that exhibit erratic boot-up phases or recover after repeatedly occurring, massive transient faults. Contrary to the case of longer stability periods, where we show how standard algorithmic techniques for solving consensus can be employed, the short-lived nature of the stability phase forces us to use more unusual algorithmic methods that avoid waiting explicitly for the stability period to occur.
Local Rademacher Complexity-based Learning Guarantees for Multi-Task Learning
Venue: arXiv cs.LG 2017
Year: 2017

We show a Talagrand-type concentration inequality for Multi-Task Learning (MTL), using which we establish sharp excess risk bounds for MTL in terms of distribution- and data-dependent versions of the Local Rademacher Complexity (LRC). We also give a new bound on the LRC for norm regularized as well as strongly convex hypothesis classes, which applies not only to MTL but also to the standard i.i.d. setting. Combining both results, one can now easily derive fast-rate bounds on the excess risk for many prominent MTL methods, including---as we demonstrate---Schatten-norm, group-norm, and graph-regularized MTL. The derived bounds reflect a relationship akeen to a conservation law of asymptotic convergence rates. This very relationship allows for trading off slower rates w.r.t. the number of tasks for faster rates with respect to the number of available samples per task, when compared to the rates obtained via a traditional, global Rademacher analysis.
On Planar Valued CSPs
Venue: arXiv cs.CC 2017
Year: 2017

We study the computational complexity of planar valued constraint satisfaction problems (VCSPs), which require the incidence graph of the instance be planar. First, we show that intractable Boolean VCSPs have to be self-complementary to be tractable in the planar setting, thus extending a corresponding result of Dvorak and Kupec [ICALP'15] from CSPs to VCSPs. Second, we give a complete complexity classification of conservative planar VCSPs on arbitrary finite domains. In this case planarity does not lead to any new tractable cases and thus our classification is a sharpening of the classification of conservative VCSPs by Kolmogorov and Zivny [JACM'13].
Correlation Hashing Network for Efficient Cross-Modal Retrieval
Venue: arXiv cs.CV 2017
Year: 2017

Hashing is widely applied to approximate nearest neighbor search for large-scale multimodal retrieval with storage and computation efficiency. Cross-modal hashing improves the quality of hash coding by exploiting semantic correlations across different modalities. Existing cross-modal hashing methods first transform data into low-dimensional feature vectors, and then generate binary codes by another separate quantization step. However, suboptimal hash codes may be generated since the quantization error is not explicitly minimized and the feature representation is not jointly optimized with the binary codes. This paper presents a Correlation Hashing Network (CHN) approach to cross-modal hashing, which jointly learns good data representation tailored to hash coding and formally controls the quantization error. The proposed CHN is a hybrid deep architecture that constitutes a convolutional neural network for learning good image representations, a multilayer perception for learning good text representations, two hashing layers for generating compact binary codes, and a structured max-margin loss that integrates all things together to enable learning similarity-preserving and high-quality hash codes. Extensive empirical study shows that CHN yields state of the art cross-modal retrieval performance on standard benchmarks.
On closure operators related to maximal tricliques in tripartite hypergraphs
Venue: arXiv cs.DM 2017
Year: 2017

Triadic Formal Concept Analysis (3FCA) was introduced by Lehman and Wille almost two decades ago. And many researchers work in Data Mining and Formal Concept Analysis using the notions of closed sets, Galois and closure operators, closure systems, but up-to-date even though that different researchers actively work on mining triadic and n-ary relations, a proper closure operator for enumeration of triconcepts, i.e. maximal triadic cliques of tripartite hypergaphs, was not introduced. In this paper we show that the previously introduced operators for obtaining triconcepts and maximal connected and complete sets (MCCSs) are not always consistent and provide the reader with a definition of valid closure operator and associated set system. Moreover, we study the difficulties of related problems from order-theoretic and combinatorial point view as well as provide the reader with justifications of the complexity classes of these problems.
Improving patch-based scene text script identification with ensembles of conjoined networks
Venue: arXiv cs.CV 2017
Year: 2017

This paper focuses on the problem of script identification in scene text images. Facing this problem with state of the art CNN classifiers is not straightforward, as they fail to address a key characteristic of scene text instances: their extremely variable aspect ratio. Instead of resizing input images to a fixed aspect ratio as in the typical use of holistic CNN classifiers, we propose here a patch-based classification framework in order to preserve discriminative parts of the image that are characteristic of its class. We describe a novel method based on the use of ensembles of conjoined networks to jointly learn discriminative stroke-parts representations and their relative importance in a patch-based classification scheme. Our experiments with this learning procedure demonstrate state-of-the-art results in two public script identification datasets. In addition, we propose a new public benchmark dataset for the evaluation of multi-lingual scene text end-to-end reading systems. Experiments done in this dataset demonstrate the key role of script identification in a complete end-to-end system that combines our script identification method with a previously published text detector and an off-the-shelf OCR engine.
On Distributed Computing for Functions with Certain Structures
Venue: arXiv cs.IT 2017
Year: 2017

The problem of distributed function computation is studied, where functions to be computed is not necessarily symbol-wise. A new method to derive a converse bound for distributed computing is proposed; from the structure of functions to be computed, information that is inevitably conveyed to the decoder is identified, and the bound is derived in terms of the optimal rate needed to send that information. The class of informative functions is introduced, and, for the class of smooth sources, the optimal rate for computing those functions is characterized. Furthermore, for i.i.d. sources with joint distribution that may not be full support, functions that are composition of symbol-wise function and the type of a sequence are considered, and the optimal rate for computing those functions is characterized in terms of the hypergraph entropy. As a byproduct, our method also provides a conceptually simple proof of the known fact that computing a Boolean function may require as large rate as reproducing the entire source.
A One-Hop Information Based Geographic Routing Protocol for Delay Tolerant MANETs
Venue: arXiv cs.NI 2017
Year: 2017

Delay and Disruption Tolerant Networks (DTNs) may lack continuous network connectivity. Routing in DTNs is thus a challenge since it must handle network partitioning, long delays, and dynamic topology. Meanwhile, routing protocols of the traditional Mobile Ad hoc NETworks (MANETs) cannot work well due to the failure of its assumption that most network connections are available. In this article, a geographic routing protocol is proposed for MANETs in delay tolerant situations, by using no more than one-hop information. A utility function is designed for implementing the under-controlled replication strategy. To reduce the overheads caused by message flooding, we employ a criterion so as to evaluate the degree of message redundancy. Consequently a message redundancy coping mechanism is added to our routing protocol. Extensive simulations have been conducted and the results show that when node moving speed is relatively low, our routing protocol outperforms the other schemes such as Epidemic, Spray and Wait, FirstContact in delivery ratio and average hop count, while introducing an acceptable overhead ratio into the network.