OpenRaiser/Intern-Atlas huggingface dataset:
Spatially Coupled Turbo-Like Codes
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we introduce the concept of spatially coupled turbo-like codes (SC-TCs) as the spatial coupling of a number of turbo-like code ensembles. In particular, we consider the spatial coupling of Berrou et al. parallel concatenated codes (PCCs) and Benedetto et al. serially concatenated codes (SCCs). Furthermore, we propose two extensions of braided convolutional codes (BCCs), a class of turbo-like codes which have an inherent spatially coupled structure, to higher coupling memories, and show that these yield improved belief propagation (BP) thresholds as compared to the original BCC ensemble. We derive the exact density evolution (DE) equations for SC-TCs and analyze their asymptotic behavior on the binary erasure channel. We also consider the construction of families of rate-compatible SC-TC ensembles. Our numerical results show that threshold saturation of the belief propagation (BP) decoding threshold to the maximum a-posteriori threshold of the underlying uncoupled ensembles occurs for large enough coupling memory. The improvement of the BP threshold is especially significant for SCCs and BCCs, whose uncoupled ensembles suffer from a poor BP threshold. For a wide range of code rates, SC-TCs show close-to-capacity performance as the coupling memory increases. We further give a proof of threshold saturation for SC-TC ensembles with identical component encoders. In particular, we show that the DE of SC-TC ensembles with identical component encoders can be properly rewritten as a scalar recursion. This allows us to define potential functions and prove threshold saturation using the proof technique recently introduced by Yedla et al..
Optimal Compression of a Polyline with Segments and Arcs
Venue: arXiv cs.CG 2017
Year: 2017

This paper describes an efficient approach to constructing a resultant polyline with a minimum number of segments and arcs. While fitting an arc can be done with complexity O(1) (see [1] and [2]), the main complexity is in checking that the resultant arc is within the specified tolerance. There are additional tests to check for the ends and for changes in direction (see [3, section 3] and [4, sections II.C and II.D]). However, the most important part in reducing complexity is the ability to subdivide the polyline in order to limit the number of arc fittings [2]. The approach described in this paper finds a compressed polyline with a minimum number of segments and arcs.
New Order-Optimal Decentralized Coded Caching Schemes with Good Performance in the Finite File Size Regime
Venue: arXiv cs.IT 2017
Year: 2017

A decentralized coded caching scheme based on independent random content placement has been proposed by Maddah-Ali and Niesen, and has been shown to achieve an order-optimal memory-load tradeoff when the file size goes to infinity. It was then successively shown by Shanmugam et al. that in the practical operating regime where the file size is limited such scheme yields much less attractive load gain. In this paper, we propose a decentralized random coded caching scheme and a partially decentralized sequential coded caching scheme with different coordination requirements in the content placement phase. The proposed content placement and delivery methods aim at ensuring abundant coded-multicasting opportunities in the content delivery phase when the file size is finite. We first analyze the loads of the two proposed schemes and show that the sequential scheme outperforms the random scheme in the finite file size regime. We also show that both our proposed schemes outperform Maddah-Ali--Niesen's and Shanmugam et al.'s decentralized schemes for finite file size, when the number of users is sufficiently large. Then, we show that our schemes achieve the same memory-load tradeoff as Maddah-Ali--Niesen's decentralized scheme when the file size goes to infinity, and hence are also order optimal. Finally, we analyze the load gains of the two proposed schemes and characterize the corresponding required file sizes.
Unsupervised Classification in Hyperspectral Imagery with Nonlocal Total Variation and Primal-Dual Hybrid Gradient Algorithm
Venue: arXiv cs.CV 2017
Year: 2017

In this paper, a graph-based nonlocal total variation method (NLTV) is proposed for unsupervised classification of hyperspectral images (HSI). The variational problem is solved by the primal-dual hybrid gradient (PDHG) algorithm. By squaring the labeling function and using a stable simplex clustering routine, an unsupervised clustering method with random initialization can be implemented. The effectiveness of this proposed algorithm is illustrated on both synthetic and real-world HSI, and numerical results show that the proposed algorithm outperforms other standard unsupervised clustering methods such as spherical K-means, nonnegative matrix factorization (NMF), and the graph-based Merriman-Bence-Osher (MBO) scheme.
Unit Consistency, Generalized Inverses, and Effective System Design Methods
Venue: arXiv cs.NA 2017
Year: 2017

This paper examines the potential role of unit consistency as a system design principle. Unit-consistent generalized matrix inverses and unit-invariant matrix decompositions are derived in support of this principle. Applications of the methods described are illustrated with examples relating to nonlinear system identification and robustness to multiplicative noise for image database retrieval.
Stabbing line segments with disks: complexity and approximation algorithms
Venue: arXiv cs.CG 2017
Year: 2017

Computational complexity and approximation algorithms are reported for a problem of stabbing a set of straight line segments with the least cardinality set of disks of fixed radii $r>0$ where the set of segments forms a straight line drawing $G=(V,E)$ of a planar graph without edge crossings. Close geometric problems arise in network security applications. We give strong NP-hardness of the problem for edge sets of Delaunay triangulations, Gabriel graphs and other subgraphs (which are often used in network design) for $r\in [d_{\min},ηd_{\max}]$ and some constant $η$ where $d_{\max}$ and $d_{\min}$ are Euclidean lengths of the longest and shortest graph edges respectively. Fast $O(|E|\log|E|)$-time $O(1)$-approximation algorithm is proposed within the class of straight line drawings of planar graphs for which the inequality $r\geq ηd_{\max}$ holds uniformly for some constant $η>0,$ i.e. when lengths of edges of $G$ are uniformly bounded from above by some linear function of $r.$
Optimal Design of Robust Combinatorial Mechanisms for Substitutable Goods
Venue: arXiv cs.GT 2017
Year: 2017

In this paper we consider multidimensional mechanism design problem for selling discrete substitutable items to a group of buyers. Previous work on this problem mostly focus on stochastic description of valuations used by the seller. However, in certain applications, no prior information regarding buyers' preferences is known. To address this issue, we consider uncertain valuations and formulate the problem in a robust optimization framework: the objective is to minimize the maximum regret. For a special case of revenue-maximizing pricing problem we present a solution method based on mixed-integer linear programming formulation.
Reduced Switching Connectivity for Large Scale Antenna Selection
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we explore reduced-connectivity radio frequency (RF) switching networks for reducing the analog hardware complexity and switching power losses in antenna selection (AS) systems. In particular, we analyze different hardware architectures for implementing the RF switching matrices required in AS designs with a reduced number of RF chains. We explicitly show that fully-flexible switching matrices, which facilitate the selection of any possible subset of antennas and attain the maximum theoretical sum rates of AS, present numerous drawbacks such as the introduction of significant insertion losses, particularly pronounced in massive multiple-input multiple-output (MIMO) systems. Since these disadvantages make fully-flexible switching suboptimal in the energy efficiency sense, we further consider partially-connected switching networks as an alternative switching architecture with reduced hardware complexity, which we characterize in this work. In this context, we also analyze the impact of reduced switching connectivity on the analog hardware and digital signal processing of AS schemes that rely on channel power information. Overall, the analytical and simulation results shown in this paper demonstrate that partially-connected switching maximizes the energy efficiency of massive MIMO systems for a reduced number of RF chains, while fully-flexible switching offers sub-optimal energy efficiency benefits due to its significant switching power losses.
A Sensing Contribution-based Two-layer Game for Channel Selection and Spectrum Access in Cognitive Radio Ad-hoc Networks
Venue: arXiv cs.NI 2017
Year: 2017

In cognitive radio (CR) networks, the secondary users (SUs) sense the spectrum licensed to the primary users (PUs) to identify and possibly transmit over temporarily unoccupied channels. Cooperative sensing was proposed to improve the sensing accuracy, but in heterogeneous scenarios SUs do not contribute equally to the cooperative sensing result because they experience different received PU signal quality at their sensors. In this paper, a two-layer coalitional game is developed for distributed sensing and access in multichannel CR ad hoc networks where the SUs' transmission opportunities are commensurate with their sensing contributions, thus fostering cooperation and eliminating free-riders. Numerical results show that the proposed two-layer game is computationally efficient and outperforms previously investigated collaborative sensing and spectrum access approaches for heterogeneous multichannel CR networks in terms of energy efficiency, throughput, SU fairness, and complexity. Moreover, it is demonstrated that this game is robust to changes in the network topology and the number of SUs in low-mobility scenarios. Finally, we propose a new physical-layer approach to distributing the network-level miss-detection (MD) constraints fairly among the interfering SUs for guaranteed PU protection and demonstrate the performance advantages of the AND-rule combining of spectrum sensing results for heterogeneous SUs.
Combinatorial Aspects of the Distribution of Rough Objects
Venue: arXiv cs.AI 2017
Year: 2017

The inverse problem of general rough sets, considered by the present author in some of her earlier papers, in one of its manifestations is essentially the question of when an agent's view about crisp and non crisp objects over a set of objects has a rough evolution. In this research the nature of the problem is examined from number-theoretic and combinatorial perspectives under very few assumptions about the nature of data and some necessary conditions are proved.
Don't Walk, Skip! Online Learning of Multi-scale Network Embeddings
Venue: arXiv cs.SI 2017
Year: 2017

We present Walklets, a novel approach for learning multiscale representations of vertices in a network. In contrast to previous works, these representations explicitly encode multiscale vertex relationships in a way that is analytically derivable. Walklets generates these multiscale relationships by subsampling short random walks on the vertices of a graph. By `skipping' over steps in each random walk, our method generates a corpus of vertex pairs which are reachable via paths of a fixed length. This corpus can then be used to learn a series of latent representations, each of which captures successively higher order relationships from the adjacency matrix. We demonstrate the efficacy of Walklets's latent representations on several multi-label network classification tasks for social networks such as BlogCatalog, DBLP, Flickr, and YouTube. Our results show that Walklets outperforms new methods based on neural matrix factorization. Specifically, we outperform DeepWalk by up to 10% and LINE by 58% Micro-F1 on challenging multi-label classification tasks. Finally, Walklets is an online algorithm, and can easily scale to graphs with millions of vertices and edges.
Different approaches for identifying important concepts in probabilistic biomedical text summarization
Venue: arXiv cs.CL 2017
Year: 2017

Automatic text summarization tools help users in biomedical domain to acquire their intended information from various textual resources more efficiently. Some of the biomedical text summarization systems put the basis of their sentence selection approach on the frequency of concepts extracted from the input text. However, it seems that exploring other measures rather than the frequency for identifying the valuable content of the input document, and considering the correlations existing between concepts may be more useful for this type of summarization. In this paper, we describe a Bayesian summarizer for biomedical text documents. The Bayesian summarizer initially maps the input text to the Unified Medical Language System (UMLS) concepts, then it selects the important ones to be used as classification features. We introduce different feature selection approaches to identify the most important concepts of the text and to select the most informative content according to the distribution of these concepts. We show that with the use of an appropriate feature selection approach, the Bayesian biomedical summarizer can improve the performance of summarization. We perform extensive evaluations on a corpus of scientific papers in biomedical domain. The results show that the Bayesian summarizer outperforms the biomedical summarizers that rely on the frequency of concepts, the domain-independent and baseline methods based on the Recall-Oriented Understudy for Gisting Evaluation (ROUGE) metrics. Moreover, the results suggest that using the meaningfulness measure and considering the correlations of concepts in the feature selection step lead to a significant increase in the performance of summarization.
Multiobjective Optimization in a Quantum Adiabatic Computer
Venue: arXiv cs.DS 2017
Year: 2017

In this work we present a quantum algorithm for multiobjective combinatorial optimization. We show how to map a convex combination of objective functions onto a Hamiltonian and then use that Hamiltonian to prove that the quantum adiabatic algorithm of Farhi \emph{et al.} [arXiv:quant-ph/0001106] can find Pareto-optimal solutions in finite time provided certain convex combinations of objectives are used and the underlying multiobjective problem meets certain restrictions.
View Synthesis by Appearance Flow
Venue: arXiv cs.CV 2017
Year: 2017

We address the problem of novel view synthesis: given an input image, synthesizing new images of the same object or scene observed from arbitrary viewpoints. We approach this as a learning task but, critically, instead of learning to synthesize pixels from scratch, we learn to copy them from the input image. Our approach exploits the observation that the visual appearance of different views of the same instance is highly correlated, and such correlation could be explicitly learned by training a convolutional neural network (CNN) to predict appearance flows -- 2-D coordinate vectors specifying which pixels in the input view could be used to reconstruct the target view. Furthermore, the proposed framework easily generalizes to multiple input views by learning how to optimally combine single-view predictions. We show that for both objects and scenes, our approach is able to synthesize novel views of higher perceptual quality than previous CNN-based techniques.
Rate region boundary of the SISO Z-interference channel with improper signaling
Venue: arXiv cs.IT 2017
Year: 2017

This paper provides a complete characterization of the boundary of an achievable rate region, called the Pareto boundary, of the single-antenna Z interference channel (Z-IC), when interference is treated as noise and users transmit complex Gaussian signals that are allowed to be improper. By considering the augmented complex formulation, we derive a necessary and sufficient condition for improper signaling to be optimal. This condition is stated as a threshold on the interference channel coefficient, which is a function of the interfered user rate and which allows insightful interpretations into the behavior of the achievable rates in terms of the circularity coefficient (i.e., degree of impropriety). Furthermore, the optimal circularity coefficient is provided in closed form. The simplicity of the obtained characterization permits interesting insights into when and how improper signaling outperforms proper signaling in the single-antenna Z-IC. We also provide an in-depth discussion on the optimal strategies and the properties of the Pareto boundary.
Cumulative Activation in Social Networks
Venue: arXiv cs.SI 2017
Year: 2017

Most studies on influence maximization focus on one-shot propagation, i.e. the influence is propagated from seed users only once following a probabilistic diffusion model and users' activation are determined via single cascade. In reality it is often the case that a user needs to be cumulatively impacted by receiving enough pieces of information propagated to her before she makes the final purchase decision. In this paper we model such cumulative activation as the following process: first multiple pieces of information are propagated independently in the social network following the classical independent cascade model, then the user will be activated (and adopt the product) if the cumulative pieces of information she received reaches her cumulative activation threshold. Two optimization problems are investigated under this framework: seed minimization with cumulative activation (SM-CA), which asks how to select a seed set with minimum size such that the number of cumulatively active nodes reaches a given requirement $η$; influence maximization with cumulative activation (IM-CA), which asks how to choose a seed set with fixed budget to maximize the number of cumulatively active nodes. For SM-CA problem, we design a greedy algorithm that yields a bicriteria $O(\ln n)$-approximation when $η=n$, where $n$ is the number of nodes in the network. For both SM-CA problem with $η<n$ and IM-CA problem, we prove strong inapproximability results. Despite the hardness results, we propose two efficient heuristic algorithms for SM-CA and IM-CA respectively based on the reverse reachable set approach. Experimental results on different real-world social networks show that our algorithms significantly outperform baseline algorithms.
Incorporating Loose-Structured Knowledge into Conversation Modeling via Recall-Gate LSTM
Venue: arXiv cs.CL 2017
Year: 2017

Modeling human conversations is the essence for building satisfying chat-bots with multi-turn dialog ability. Conversation modeling will notably benefit from domain knowledge since the relationships between sentences can be clarified due to semantic hints introduced by knowledge. In this paper, a deep neural network is proposed to incorporate background knowledge for conversation modeling. Through a specially designed Recall gate, domain knowledge can be transformed into the extra global memory of Long Short-Term Memory (LSTM), so as to enhance LSTM by cooperating with its local memory to capture the implicit semantic relevance between sentences within conversations. In addition, this paper introduces the loose structured domain knowledge base, which can be built with slight amount of manual work and easily adopted by the Recall gate. Our model is evaluated on the context-oriented response selecting task, and experimental results on both two datasets have shown that our approach is promising for modeling human conversations and building key components of automatic chatting systems.
Human Action Localization with Sparse Spatial Supervision
Venue: arXiv cs.CV 2017
Year: 2017

We introduce an approach for spatio-temporal human action localization using sparse spatial supervision. Our method leverages the large amount of annotated humans available today and extracts human tubes by combining a state-of-the-art human detector with a tracking-by-detection approach. Given these high-quality human tubes and temporal supervision, we select positive and negative tubes with very sparse spatial supervision, i.e., only one spatially annotated frame per instance. The selected tubes allow us to effectively learn a spatio-temporal action detector based on dense trajectories or CNNs. We conduct experiments on existing action localization benchmarks: UCF-Sports, J-HMDB and UCF-101. Our results show that our approach, despite using sparse spatial supervision, performs on par with methods using full supervision, i.e., one bounding box annotation per frame. To further validate our method, we introduce DALY (Daily Action Localization in YouTube), a dataset for realistic action localization in space and time. It contains high quality temporal and spatial annotations for 3.6k instances of 10 actions in 31 hours of videos (3.3M frames). It is an order of magnitude larger than existing datasets, with more diversity in appearance and long untrimmed videos.
Backstepping Design for Incremental Stability of Stochastic Hamiltonian Systems with Jumps
Venue: arXiv cs.SY 2017
Year: 2017

Incremental stability is a property of dynamical systems ensuring the uniform asymptotic stability of each trajectory rather than a fixed equilibrium point or trajectory. Here, we introduce a notion of incremental stability for stochastic control systems and provide its description in terms of existence of a notion of so-called incremental Lyapunov functions. Moreover, we provide a backstepping controller design scheme providing controllers along with corresponding incremental Lyapunov functions rendering a class of stochastic control systems, namely, stochastic Hamiltonian systems with jumps, incrementally stable. To illustrate the effectiveness of the proposed approach, we design a controller making a spring pendulum system in a noisy environment incrementally stable.
Low-Sensitivity Functions from Unambiguous Certificates
Venue: arXiv cs.CC 2017
Year: 2017

We provide new query complexity separations against sensitivity for total Boolean functions: a power $3$ separation between deterministic (and even randomized or quantum) query complexity and sensitivity, and a power $2.22$ separation between certificate complexity and sensitivity. We get these separations by using a new connection between sensitivity and a seemingly unrelated measure called one-sided unambiguous certificate complexity ($UC_{min}$). We also show that $UC_{min}$ is lower-bounded by fractional block sensitivity, which means we cannot use these techniques to get a super-quadratic separation between $bs(f)$ and $s(f)$. We also provide a quadratic separation between the tree-sensitivity and decision tree complexity of Boolean functions, disproving a conjecture of Gopalan, Servedio, Tal, and Wigderson (CCC 2016). Along the way, we give a power $1.22$ separation between certificate complexity and one-sided unambiguous certificate complexity, improving the power $1.128$ separation due to Göös (FOCS 2015). As a consequence, we obtain an improved $Ω(\log^{1.22} n)$ lower-bound on the co-nondeterministic communication complexity of the Clique vs. Independent Set problem.