OpenRaiser/Intern-Atlas huggingface dataset:
Combining Spot and Futures Markets: A Hybrid Market Approach to Dynamic Spectrum Access
Venue: arXiv cs.NI 2016
Year: 2016

Dynamic spectrum access is a new paradigm of secondary spectrum utilization and sharing. It allows unlicensed secondary users (SUs) to exploit opportunistically the under-utilized licensed spectrum. Market mechanism is a widely-used promising means to regulate the consuming behaviours of users and, hence, achieves the efficient allocation and consumption of limited resources. In this paper, we propose and study a hybrid secondary spectrum market consisting of both the futures market and the spot market, in which SUs (buyers) purchase under-utilized licensed spectrum from a spectrum regulator, either through predefined contracts via the futures market, or through spot transactions via the spot market. We focus on the optimal spectrum allocation among SUs in an exogenous hybrid market that maximizes the secondary spectrum utilization efficiency. The problem is challenging due to the stochasticity and asymmetry of network information. To solve this problem, we first derive an off-line optimal allocation policy that maximizes the ex-ante expected spectrum utilization efficiency based on the stochastic distribution of network information. We then propose an on-line VickreyCClarkeCGroves (VCG) auction that determines the real-time allocation and pricing of every spectrum based on the realized network information and the pre-derived off-line policy. We further show that with the spatial frequency reuse, the proposed VCG auction is NP-hard; hence, it is not suitable for on-line implementation, especially in a large-scale market. To this end, we propose a heuristics approach based on an on-line VCG-like mechanism with polynomial-time complexity, and further characterize the corresponding performance loss bound analytically. We finally provide extensive numerical results to evaluate the performance of the proposed solutions.
On the satisfiability problem for SPARQL patterns
Venue: arXiv cs.DB 2016
Year: 2016

The satisfiability problem for SPARQL patterns is undecidable in general, since the expressive power of SPARQL 1.0 is comparable with that of the relational algebra. The goal of this paper is to delineate the boundary of decidability of satisfiability in terms of the constraints allowed in filter conditions. The classes of constraints considered are bound-constraints, negated bound-constraints, equalities, nonequalities, constant-equalities, and constant-nonequalities. The main result of the paper can be summarized by saying that, as soon as inconsistent filter conditions can be formed, satisfiability is undecidable. The key insight in each case is to find a way to emulate the set difference operation. Undecidability can then be obtained from a known undecidability result for the algebra of binary relations with union, composition, and set difference. When no inconsistent filter conditions can be formed, satisfiability is efficiently decidable by simple checks on bound variables and on the use of literals. The paper also points out that satisfiability for the so-called `well-designed' patterns can be decided by a check on bound variables and a check for inconsistent filter conditions.
Limits of CSP Problems and Efficient Parameter Testing
Venue: arXiv cs.DS 2016
Year: 2016

We present a unified framework on the limits of constraint satisfaction problems (CSPs) and efficient parameter testing which depends only on array exchangeability and the method of cut decomposition without recourse to the weakly regular partitions. In particular, we formulate and prove a representation theorem for compact colored $r$-uniform directed hypergraph ($r$-graph) limits, and apply this to $r$CSP limits. We investigate the sample complexity of testable $r$-graph parameters, we discuss the generalized ground state energies and demonstrate that they are efficiently testable.
Computer Vision Approach for Low Cost, High Precision Measurement of Grapevine Trunk Diameter in Outdoor Conditions
Venue: arXiv cs.CV 2016
Year: 2016

Trunk diameter is a variable of agricultural interest, used mainly in the prediction of fruit trees production. It is correlated with leaf area and biomass of trees, and consequently gives a good estimate of the potential production of the plants. This work presents a low cost, high precision method for the measurement of trunk diameter of grapevines based on Computer Vision techniques. Several methods based on Computer Vision and other techniques are introduced in the literature. These methods present different advantages for crop management: they are amenable to be operated by unknowledgeable personnel, with lower operational costs; they result in lower stress levels to knowledgeable personnel, avoiding the deterioration of the measurement quality over time; and they make the measurement process amenable to be embedded in larger autonomous systems, allowing more measurements to be taken with equivalent costs. To date, all existing autonomous methods are either of low precision, or have a prohibitive cost for massive agricultural adoption, leaving the manual Vernier caliper or tape measure as the only choice in most situations. In this work we present a semi-autonomous measurement method that is susceptible to be fully automated, cost effective for mass adoption, and its precision is competitive (with slight improvements) over the caliper manual method.
Average-Case Optimal Approximate Circular String Matching
Venue: arXiv cs.DS 2016
Year: 2016

Approximate string matching is the problem of finding all factors of a text t of length n that are at a distance at most k from a pattern x of length m. Approximate circular string matching is the problem of finding all factors of t that are at a distance at most k from x or from any of its rotations. In this article, we present a new algorithm for approximate circular string matching under the edit distance model with optimal average-case search time O(n(k + log m)/m). Optimal average-case search time can also be achieved by the algorithms for multiple approximate string matching (Fredriksson and Navarro, 2004) using x and its rotations as the set of multiple patterns. Here we reduce the preprocessing time and space requirements compared to that approach.
PAC-Bayes Analysis of Multi-view Learning
Venue: arXiv cs.LG 2016
Year: 2016

This paper presents eight PAC-Bayes bounds to analyze the generalization performance of multi-view classifiers. These bounds adopt data dependent Gaussian priors which emphasize classifiers with high view agreements. The center of the prior for the first two bounds is the origin, while the center of the prior for the third and fourth bounds is given by a data dependent vector. An important technique to obtain these bounds is two derived logarithmic determinant inequalities whose difference lies in whether the dimensionality of data is involved. The centers of the fifth and sixth bounds are calculated on a separate subset of the training set. The last two bounds use unlabeled data to represent view agreements and are thus applicable to semi-supervised multi-view learning. We evaluate all the presented multi-view PAC-Bayes bounds on benchmark data and compare them with previous single-view PAC-Bayes bounds. The usefulness and performance of the multi-view bounds are discussed.
On semidefinite relaxations for the block model
Venue: arXiv cs.LG 2016
Year: 2016

The stochastic block model (SBM) is a popular tool for community detection in networks, but fitting it by maximum likelihood (MLE) involves a computationally infeasible optimization problem. We propose a new semidefinite programming (SDP) solution to the problem of fitting the SBM, derived as a relaxation of the MLE. We put ours and previously proposed SDPs in a unified framework, as relaxations of the MLE over various sub-classes of the SBM, revealing a connection to sparse PCA. Our main relaxation, which we call SDP-1, is tighter than other recently proposed SDP relaxations, and thus previously established theoretical guarantees carry over. However, we show that SDP-1 exactly recovers true communities over a wider class of SBMs than those covered by current results. In particular, the assumption of strong assortativity of the SBM, implicit in consistency conditions for previously proposed SDPs, can be relaxed to weak assortativity for our approach, thus significantly broadening the class of SBMs covered by the consistency results. We also show that strong assortativity is indeed a necessary condition for exact recovery for previously proposed SDP approaches and not an artifact of the proofs. Our analysis of SDPs is based on primal-dual witness constructions, which provides some insight into the nature of the solutions of various SDPs. We show how to combine features from SDP-1 and already available SDPs to achieve the most flexibility in terms of both assortativity and block-size constraints, as our relaxation has the tendency to produce communities of similar sizes. This tendency makes it the ideal tool for fitting network histograms, a method gaining popularity in the graphon estimation literature, as we illustrate on an example of a social networks of dolphins. We also provide empirical evidence that SDPs outperform spectral methods for fitting SBMs with a large number of blocks.
3DUNDERWORLD-SLS: An Open-Source Structured-Light Scanning System for Rapid Geometry Acquisition
Venue: arXiv cs.CV 2016
Year: 2016

Recently, there has been an increase in the demand of virtual 3D objects representing real-life objects. A plethora of methods and systems have already been proposed for the acquisition of the geometry of real-life objects ranging from those which employ active sensor technology, passive sensor technology or a combination of various techniques. In this paper we present the development of a 3D scanning system which is based on the principle of structured-light, without having particular requirements for specialized equipment. We discuss the intrinsic details and inherent difficulties of structured-light scanning techniques and present our solutions. Finally, we introduce our open-source scanning software system "3DUNDERWORLD-SLS" which implements the proposed techniques both in CPU and GPU. We have performed extensive testing with a wide range of models and report the results. Furthermore, we present a comprehensive evaluation of the system and a comparison with a high-end commercial 3D scanner.
Optimal Scheduling for Interference Mitigation by Range Information
Venue: arXiv cs.IT 2016
Year: 2016

The multiple access scheduling decides how the channel is shared among the nodes in the network. Typical scheduling algorithms aims at increasing the channel utilization and thereby throughput of the network. This paper describes several algorithms for generating an optimal schedule in terms of channel utilization for multiple access by utilizing range information in a fully connected network. We also provide detailed analysis for the proposed algorithms performance in terms of their complexity, convergence, and effect of non-idealities in the network. The performance of the proposed schemes are compared with non-aided methods to quantify the benefits of using the range information in the communication. The proposed methods have several favorable properties for the scalable systems. We show that the proposed techniques yields better channel utilization and throughput as the number of nodes in the network increases. We provide simulation results in support of this claim. The proposed methods indicate that the throughput can be increased on average by 3-10 times for typical network configurations.
Fault-Tolerant Approximate Shortest-Path Trees
Venue: arXiv cs.DS 2016
Year: 2016

The resiliency of a network is its ability to remain \emph{effectively} functioning also when any of its nodes or links fails. However, to reduce operational and set-up costs, a network should be small in size, and this conflicts with the requirement of being resilient. In this paper we address this trade-off for the prominent case of the {\em broadcasting} routing scheme, and we build efficient (i.e., sparse and fast) \emph{fault-tolerant approximate shortest-path trees}, for both the edge and vertex \emph{single-failure} case. In particular, for an $n$-vertex non-negatively weighted graph, and for any constant $\varepsilon >0$, we design two structures of size $O(\frac{n \log n}{\varepsilon^2})$ which guarantee $(1+\varepsilon)$-stretched paths from the selected source also in the presence of an edge/vertex failure. This favorably compares with the currently best known solutions, which are for the edge-failure case of size $O(n)$ and stretch factor 3, and for the vertex-failure case of size $O(n \log n)$ and stretch factor 3. Moreover, we also focus on the unweighted case, and we prove that an ordinary $(α,β)$-spanner can be slightly augmented in order to build efficient fault-tolerant approximate \emph{breadth-first-search trees}.
Content-Aware Network Coding over Device-to-Device Networks
Venue: arXiv cs.IT 2016
Year: 2016

Consider a scenario of broadcasting a common content to a group of cooperating mobile devices that are within proximity of each other. Devices in this group may receive partial content from the source due to packet losses over wireless broadcast links. We further consider that packet losses are different for different devices. The remaining missing content at each device can then be recovered, thanks to cooperation among the devices by exploiting device-to-device (D2D) connections. In this context, the minimum amount of time that can guarantee a complete acquisition of the common content at every device is referred to as the "completion time". It has been shown that instantly decodable network coding (IDNC) reduces the completion time as compared to no network coding in this scenario. Yet, for applications such as video streaming, not all packets have the same importance and not all devices are interested in the same quality of content. This problem is even more interesting when additional, but realistic constraints, such as strict deadline, bandwidth, or limited energy are added in the problem formulation. We assert that direct application of IDNC in such a scenario yields poor performance in terms of content quality and completion time. In this paper, we propose a novel Content and Loss-Aware IDNC scheme that improves content quality and network coding opportunities jointly by taking into account importance of each packet towards the desired quality of service (QoS) as well as the channel losses over D2D links. Our proposed Content and Loss-Aware IDNC (i) maximizes the quality under the completion time constraint, and (ii) minimizes the completion time under the quality constraint. We demonstrate the benefits of Content and Loss-Aware IDNC through simulations.
Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent
Venue: arXiv cs.DS 2016
Year: 2016

First-order methods play a central role in large-scale machine learning. Even though many variations exist, each suited to a particular problem, almost all such methods fundamentally rely on two types of algorithmic steps: gradient descent, which yields primal progress, and mirror descent, which yields dual progress. We observe that the performances of gradient and mirror descent are complementary, so that faster algorithms can be designed by LINEARLY COUPLING the two. We show how to reconstruct Nesterov's accelerated gradient methods using linear coupling, which gives a cleaner interpretation than Nesterov's original proofs. We also discuss the power of linear coupling by extending it to many other settings that Nesterov's methods cannot apply to.
Asymptotically Optimal Sampling-based Kinodynamic Planning
Venue: arXiv cs.RO 2016
Year: 2016

Sampling-based algorithms are viewed as practical solutions for high-dimensional motion planning. Recent progress has taken advantage of random geometric graph theory to show how asymptotic optimality can also be achieved with these methods. Achieving this desirable property for systems with dynamics requires solving a two-point boundary value problem (BVP) in the state space of the underlying dynamical system. It is difficult, however, if not impractical, to generate a BVP solver for a variety of important dynamical models of robots or physically simulated ones. Thus, an open challenge was whether it was even possible to achieve optimality guarantees when planning for systems without access to a BVP solver. This work resolves the above question and describes how to achieve asymptotic optimality for kinodynamic planning using incremental sampling-based planners by introducing a new rigorous framework. Two new methods, Stable Sparse-RRT (SST) and SST*, result from this analysis, which are asymptotically near-optimal and optimal, respectively. The techniques are shown to converge fast to high-quality paths, while they maintain only a sparse set of samples, which makes them computationally efficient. The good performance of the planners is confirmed by experimental results using dynamical systems benchmarks, as well as physically simulated robots.
Kernel Nonnegative Matrix Factorization Without the Curse of the Pre-image - Application to Unmixing Hyperspectral Images
Venue: arXiv cs.CV 2016
Year: 2016

The nonnegative matrix factorization (NMF) is widely used in signal and image processing, including bio-informatics, blind source separation and hyperspectral image analysis in remote sensing. A great challenge arises when dealing with a nonlinear formulation of the NMF. Within the framework of kernel machines, the models suggested in the literature do not allow the representation of the factorization matrices, which is a fallout of the curse of the pre-image. In this paper, we propose a novel kernel-based model for the NMF that does not suffer from the pre-image problem, by investigating the estimation of the factorization matrices directly in the input space. For different kernel functions, we describe two schemes for iterative algorithms: an additive update rule based on a gradient descent scheme and a multiplicative update rule in the same spirit as in the Lee and Seung algorithm. Within the proposed framework, we develop several extensions to incorporate constraints, including sparseness, smoothness, and spatial regularization with a total-variation-like penalty. The effectiveness of the proposed method is demonstrated with the problem of unmixing hyperspectral images, using well-known real images and results with state-of-the-art techniques.
Topological Similarity of Random Cell Complexes and Applications
Venue: arXiv cs.CG 2016
Year: 2016

Although random cell complexes occur throughout the physical sciences, there does not appear to be a standard way to quantify their statistical similarities and differences. The various proposals in the literature are usually motivated by the analysis of particular physical systems and do not necessarily apply to general situations. The central concepts in this paper---the swatch and the cloth---provide a description of the local topology of a cell complex that is general (any physical system that may be represented as a cell complex is admissible) and complete (any statistical question about the local topology may be answered from the cloth). Furthermore, this approach allows a distance to be defined that measures the similarity of the local topology of two cell complexes. The distance is used to identify a steady state of a model dislocation network evolving by energy minimization, and then to rigorously quantify the approach of the simulation to this steady state.
Optimal Fronthaul Quantization for Cloud Radio Positioning
Venue: arXiv cs.IT 2016
Year: 2016

Wireless positioning systems that are implemented by means of a Cloud Radio Access Networks (C-RANs) may provide cost-effective solutions, particularly for indoor localization. In a C-RAN, the baseband processing, including localization, is carried out at a centralized control unit (CU) based on quantized baseband signals received from the RUs over finite-capacity fronthaul links. In this paper, the problem of maximizing the localization accuracy over fronthaul quantization/compression is formulated by adopting the Cramér-Rao bound (CRB) on the localization accuracy as the performance metric of interest and information-theoretic bounds on the compression rate. The analysis explicitly accounts for the uncertainty of parameters at the CU via a robust, or worst-case, optimization formulation. The proposed algorithm leverages the Charnes-Cooper transformation and Difference-of-Convex (DC) programming, and is validated via numerical results.
Partially Independent Control Scheme for Spacecraft Rendezvous in Near-Circular Orbits
Venue: arXiv cs.SY 2016
Year: 2016

Due to the complexity and inconstancy of the space environment, accurate mathematical models for spacecraft rendezvous are difficult to obtain, which consequently complicates the control tasks. In this paper, a linearized time-variant plant model with external perturbations is adopted to approximate the real circumstance. To realize the robust stability with optimal performance cost, a partially independent control scheme is proposed, which consists of a robust anti-windup controller for the in-plane motion and a ${{H}_{\infty}}$ controller for the out-of-plane motion. Finally, a rendezvous simulation is given to corroborate the practicality and advantages of the partially independent control scheme over a coupled control scheme.
LTL Parameter Synthesis of Parametric Timed Automata
Venue: arXiv cs.FL 2016
Year: 2016

The parameter synthesis problem for parametric timed automata is undecidable in general even for very simple reachability properties. In this paper we introduce restrictions on parameter valuations under which the parameter synthesis problem is decidable for LTL properties. The investigated bounded integer parameter synthesis problem could be solved using an explicit enumeration of all possible parameter valuations. We propose an alternative symbolic zone-based method for this problem which results in a faster computation. Our technique extends the ideas of the automata-based approach to LTL model checking of timed automata. To justify the usefulness of our approach, we provide experimental evaluation and compare our method with explicit enumeration technique.
Zero Shot Recognition with Unreliable Attributes
Venue: arXiv cs.CV 2016
Year: 2016

In principle, zero-shot learning makes it possible to train a recognition model simply by specifying the category's attributes. For example, with classifiers for generic attributes like \emph{striped} and \emph{four-legged}, one can construct a classifier for the zebra category by enumerating which properties it possesses---even without providing zebra training images. In practice, however, the standard zero-shot paradigm suffers because attribute predictions in novel images are hard to get right. We propose a novel random forest approach to train zero-shot models that explicitly accounts for the unreliability of attribute predictions. By leveraging statistics about each attribute's error tendencies, our method obtains more robust discriminative models for the unseen classes. We further devise extensions to handle the few-shot scenario and unreliable attribute descriptions. On three datasets, we demonstrate the benefit for visual category learning with zero or few training examples, a critical domain for rare categories or categories defined on the fly.