OpenRaiser/Intern-Atlas huggingface dataset:
Statistical physics of linear and bilinear inference problems
Venue: arXiv cs.IT 2016
Year: 2016

The recent development of compressed sensing has led to spectacular advances in the understanding of sparse linear estimation problems as well as in algorithms to solve them. It has also triggered a new wave of developments in the related fields of generalized linear and bilinear inference problems, that have very diverse applications in signal processing and are furthermore a building block of deep neural networks. These problems have in common that they combine a linear mixing step and a nonlinear, probabilistic sensing step, producing indirect measurements of a signal of interest. Such a setting arises in problems as different as medical or astronomical imaging, clustering, matrix completion or blind source separation. The aim of this thesis is to propose efficient algorithms for this class of problems and to perform their theoretical analysis. To this end, it uses belief propagation, thanks to which high-dimensional distributions can be sampled efficiently, thus making a Bayesian approach to inference tractable. The resulting algorithms undergo phase transitions just as physical systems do. These phase transitions can be analyzed using the replica method, initially developed in statistical physics of disordered systems. The analysis reveals phases in which inference is easy, hard or impossible. These phases correspond to different energy landscapes of the problem. The main contributions of this thesis can be divided into three categories. First, the application of known algorithms to concrete problems: community detection, superposition codes and an innovative imaging system. Second, a new, efficient message-passing algorithm for a class of problems called blind sensor calibration. Third, a theoretical analysis of matrix compressed sensing and of instabilities in Bayesian bilinear inference algorithms.
Optimal Energy Allocation For Delay-Constrained Traffic Over Fading Multiple Access Channels
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we consider a multiple-access fading channel where $N$ users transmit to a single base station (BS) within a limited number of time slots. We assume that each user has a fixed amount of energy available to be consumed over the transmission window. We derive the optimal energy allocation policy for each user that maximizes the total system throughput under two different assumptions on the channel state information. First, we consider the offline allocation problem where the channel states are known a priori before transmission. We solve a convex optimization problem to maximize the sum-throughput under energy and delay constraints. Next, we consider the online allocation problem, where the channels are causally known to the BS and obtain the optimal energy allocation via dynamic programming when the number of users is small. We also develop a suboptimal resource allocation algorithm whose performance is close to the optimal one. Numerical results are presented showing the superiority of the proposed algorithms over baseline algorithms in various scenarios.
Coarse2Fine: Two-Layer Fusion For Image Retrieval
Venue: arXiv cs.MM 2016
Year: 2016

This paper addresses the problem of large-scale image retrieval. We propose a two-layer fusion method which takes advantage of global and local cues and ranks database images from coarse to fine (C2F). Departing from the previous methods fusing multiple image descriptors simultaneously, C2F is featured by a layered procedure composed by filtering and refining. In particular, C2F consists of three components. 1) Distractor filtering. With holistic representations, noise images are filtered out from the database, so the number of candidate images to be used for comparison with the query can be greatly reduced. 2) Adaptive weighting. For a certain query, the similarity of candidate images can be estimated by holistic similarity scores in complementary to the local ones. 3) Candidate refining. Accurate retrieval is conducted via local features, combining the pre-computed adaptive weights. Experiments are presented on two benchmarks, \emph{i.e.,} Holidays and Ukbench datasets. We show that our method outperforms recent fusion methods in terms of storage consumption and computation complexity, and that the accuracy is competitive to the state-of-the-arts.
Multi-Objective Design of State Feedback Controllers Using Reinforced Quantum-Behaved Particle Swarm Optimization
Venue: arXiv cs.NE 2016
Year: 2016

In this paper, a novel and generic multi-objective design paradigm is proposed which utilizes quantum-behaved PSO(QPSO) for deciding the optimal configuration of the LQR controller for a given problem considering a set of competing objectives. There are three main contributions introduced in this paper as follows. (1) The standard QPSO algorithm is reinforced with an informed initialization scheme based on the simulated annealing algorithm and Gaussian neighborhood selection mechanism. (2) It is also augmented with a local search strategy which integrates the advantages of memetic algorithm into conventional QPSO. (3) An aggregated dynamic weighting criterion is introduced that dynamically combines the soft and hard constraints with control objectives to provide the designer with a set of Pareto optimal solutions and lets her to decide the target solution based on practical preferences. The proposed method is compared against a gradient-based method, seven meta-heuristics, and the trial-and-error method on two control benchmarks using sensitivity analysis and full factorial parameter selection and the results are validated using one-tailed T-test. The experimental results suggest that the proposed method outperforms opponent methods in terms of controller effort, measures associated with transient response and criteria related to steady-state.
Massively parallel implementation in Python of a pseudo-spectral DNS code for turbulent flows
Venue: arXiv cs.MS 2016
Year: 2016

Direct Numerical Simulations (DNS) of the Navier Stokes equations is a valuable research tool in fluid dynamics, but there are very few publicly available codes and, due to heavy number crunching, codes are usually written in low-level languages. In this work a \textasciitilde{}100 line standard scientific Python DNS code is described that nearly matches the performance of pure C for thousands of processors and billions of unknowns. With optimization of a few routines in Cython, it is found to match the performance of a more or less identical solver implemented from scratch in C++. Keys to the efficiency of the solver are the mesh decomposition and three dimensional FFT routines, implemented directly in Python using MPI, wrapped through MPI for Python, and a serial FFT module (both numpy.fft or pyFFTW may be used). Two popular decomposition strategies, slab and pencil, have been implemented and tested.
Lecture Notes on the ARV Algorithm for Sparsest Cut
Venue: arXiv cs.DS 2016
Year: 2016

One of the landmarks in approximation algorithms is the $O(\sqrt{\log n})$-approximation algorithm for the Uniform Sparsest Cut problem by Arora, Rao and Vazirani from 2004. The algorithm is based on a semidefinite program that finds an embedding of the nodes respecting the triangle inequality. Their core argument shows that a random hyperplane approach will find two large sets of $Θ(n)$ many nodes each that have a distance of $Θ(1/\sqrt{\log n})$ to each other if measured in terms of $\|\cdot \|_2^2$. Here we give a detailed set of lecture notes describing the algorithm. For the proof of the Structure Theorem we use a cleaner argument based on expected maxima over $k$-neighborhoods that significantly simplifies the analysis.
PyCells for an Open Semiconductor Industry
Venue: arXiv cs.OH 2016
Year: 2016

In the modern semiconductor industry, automatic generation of parameterized and recurring layout structures plays an important role and should be present as a feature in Electronic Design Automation (EDA)-tools. Currently these layout generators are developed with a proprietary programming language and can be used with a specific EDA-tool. Therefore, the semiconductor companies find the development of the layout generators that can be used in all state of the art EDA-tools which support OpenAccess database appealing. The goal of this project is to develop computationally efficient layout generators with Python (PyCells), for ams AG technologies, that possess all the features of comprehensive layout generators.
Superintelligence cannot be contained: Lessons from Computability Theory
Venue: arXiv cs.CY 2016
Year: 2016

Superintelligence is a hypothetical agent that possesses intelligence far surpassing that of the brightest and most gifted human minds. In light of recent advances in machine intelligence, a number of scientists, philosophers and technologists have revived the discussion about the potential catastrophic risks entailed by such an entity. In this article, we trace the origins and development of the neo-fear of superintelligence, and some of the major proposals for its containment. We argue that such containment is, in principle, impossible, due to fundamental limits inherent to computing itself. Assuming that a superintelligence will contain a program that includes all the programs that can be executed by a universal Turing machine on input potentially as complex as the state of the world, strict containment requires simulations of such a program, something theoretically (and practically) infeasible.
A general framework for weighted sum-rate and common-rate optimization
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we propose a framework for solving a class of optimization problems encountered in a range of power allocation problems in wireless relay networks. In particular, power allocation for weighted sum-rate and common-rate optimization problems fall in this framework. Subject to some conditions on the region of feasible powers, the optimal solutions are analytically found. The optimization problems are posed in a general form and their solutions are shown to have applications in a number of practical scenarios. Numerical results verify the optimality of the analytical approach.
Lecture Notes on Channel Coding
Venue: arXiv cs.IT 2016
Year: 2016

These lecture notes on channel coding were developed for a one-semester course for graduate students of electrical engineering. Chapter 1 reviews the basic problem of channel coding. Chapters 2-5 are on linear block codes, cyclic codes, Reed-Solomon codes, and BCH codes, respectively. The notes are self-contained and were written with the intent to derive the presented results with mathematical rigor. The notes contain in total 68 homework problems, of which 20% require computer programming.
Modelling Context with User Embeddings for Sarcasm Detection in Social Media
Venue: arXiv cs.CL 2016
Year: 2016

We introduce a deep neural network for automated sarcasm detection. Recent work has emphasized the need for models to capitalize on contextual features, beyond lexical and syntactic cues present in utterances. For example, different speakers will tend to employ sarcasm regarding different subjects and, thus, sarcasm detection models ought to encode such speaker information. Current methods have achieved this by way of laborious feature engineering. By contrast, we propose to automatically learn and then exploit user embeddings, to be used in concert with lexical signals to recognize sarcasm. Our approach does not require elaborate feature engineering (and concomitant data scraping); fitting user embeddings requires only the text from their previous posts. The experimental results show that our model outperforms a state-of-the-art approach leveraging an extensive set of carefully crafted features.
Performance Models for Split-execution Computing Systems
Venue: arXiv cs.ET 2016
Year: 2016

Split-execution computing leverages the capabilities of multiple computational models to solve problems, but splitting program execution across different computational models incurs costs associated with the translation between domains. We analyze the performance of a split-execution computing system developed from conventional and quantum processing units (QPUs) by using behavioral models that track resource usage. We focus on asymmetric processing models built using conventional CPUs and a family of special-purpose QPUs that employ quantum computing principles. Our performance models account for the translation of a classical optimization problem into the physical representation required by the quantum processor while also accounting for hardware limitations and conventional processor speed and memory. We conclude that the bottleneck in this split-execution computing system lies at the quantum-classical interface and that the primary time cost is independent of quantum processor behavior.
User Association with Maximizing Sum Energy Efficiency for Massive MIMO Enabled Heterogeneous Cellular Networks
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we design an association scheme to maximize the sum energy efficiency for massive multiple-input and multiple-output (MIMO) enabled heterogeneous cellular networks (HCNs). Considering that the final formulated problem is in a sum-of-ratio form, we first need to transform it into a parametric nonfractional form, by which we can achieve its solution through a two-layer iterative algorithm. The outer layer searches the energy efficiency parameters and multipliers associated with signal-interference-plus-noise-ratio (SINR) constraints using Newton-like method, and the inner layer optimizes the association indices using Lagrange multiplier method. In fact, the inner layer doesn't need iterative steps when the SINR constraints are not involved in the original problem, and then the whole algorithm should be a one-layer iterative one. As for the two-layer iterative algorithm, we also give the corresponding convergence proof. Numerical results show that the proposed scheme significantly outperforms the existing one in system throughput and network energy efficiency. In addition, we also investigate the impacts of the number of massive antennas and the transmit power of each pico base station on these association performances.
Incorporating prior knowledge in medical image segmentation: a survey
Venue: arXiv cs.CV 2016
Year: 2016

Medical image segmentation, the task of partitioning an image into meaningful parts, is an important step toward automating medical image analysis and is at the crux of a variety of medical imaging applications, such as computer aided diagnosis, therapy planning and delivery, and computer aided interventions. However, the existence of noise, low contrast and objects' complexity in medical images are critical obstacles that stand in the way of achieving an ideal segmentation system. Incorporating prior knowledge into image segmentation algorithms has proven useful for obtaining more accurate and plausible results. This paper surveys the different types of prior knowledge that have been utilized in different segmentation frameworks. We focus our survey on optimization-based methods that incorporate prior information into their frameworks. We review and compare these methods in terms of the types of prior employed, the domain of formulation (continuous vs. discrete), and the optimization techniques (global vs. local). We also created an interactive online database of existing works and categorized them based on the type of prior knowledge they use. Our website is interactive so that researchers can contribute to keep the database up to date. We conclude the survey by discussing different aspects of designing an energy functional for image segmentation, open problems, and future perspectives.
A Visualization Method of Four Dimensional Polytopes by Oval Display of Parallel Hyperplane Slices
Venue: arXiv cs.GR 2016
Year: 2016

A method to visualize polytopes in a four dimensional euclidian space $(x,y,z,w)$ is proposed. A polytope is sliced by multiple hyperplanes that are parallel each other and separated by uniform intervals. Since the hyperplanes are perpendicular to the $w$ axis, the resulting multiple slices appear in the three-dimensional $(x,y,z)$ space and they are shown by the standard computer graphics. The polytope is rotated extrinsically in the four dimensional space by means of a simple input method based on keyboard typings. The multiple slices are placed on a parabola curve in the three-dimensional world coordinates. The slices in a view window form an oval appearance. Both the simple and the double rotations in the four dimensional space are applied to the polytope. All slices synchronously change their shapes when a rotation is applied to the polytope. The compact display in the oval of many slices with the help of quick rotations facilitate a grasp of the four dimensional configuration of the polytope.
Dynamic Flow Scheduling Strategy in Multihoming Video CDNs
Venue: arXiv cs.MM 2016
Year: 2016

Multihoming for a video Content Delivery Network (CDN) allows edge peering servers to deliver video chunks through different Internet Service Providers (ISPs), to achieve an improved quality of service (QoS) for video streaming users. However, since traditional strategies for a multihoming video CDN are simply designed according to static rules, e.g., simply sending traffic via a ISP which is the same as the ISP of client, they fail to dynamically allocate resources among different ISPs over time. In this paper, we perform measurement studies to demonstrate that such static allocation mechanism is inefficient to make full utilization of multiple ISPs' resources. To address this problem, we propose a dynamic flow scheduling strategy for multihoming video CDN. The challenge is to find the control parameters that can guide the ISP selection when performing flow scheduling. Using a data-driven approach, we find factors that have a major impact on the performance improvement in the dynamic flow scheduling. We further utilize an information gain approach to generate parameter combinations that can be used to guide the flow scheduling, i.e., to determine the ISP each request should be responded by. Our evaluation results demonstrate that our design effectively performs the flow scheduling. In particular, our design yields near optimal performance in a simulation of real-world multihoming setup.
Essential Constraints of Edge-Constrained Proximity Graphs
Venue: arXiv cs.CG 2016
Year: 2016

Given a plane forest $F = (V, E)$ of $|V| = n$ points, we find the minimum set $S \subseteq E$ of edges such that the edge-constrained minimum spanning tree over the set $V$ of vertices and the set $S$ of constraints contains $F$. We present an $O(n \log n )$-time algorithm that solves this problem. We generalize this to other proximity graphs in the constraint setting, such as the relative neighbourhood graph, Gabriel graph, $β$-skeleton and Delaunay triangulation. We present an algorithm that identifies the minimum set $S\subseteq E$ of edges of a given plane graph $I=(V,E)$ such that $I \subseteq CG_β(V, S)$ for $1 \leq β\leq 2$, where $CG_β(V, S)$ is the constraint $β$-skeleton over the set $V$ of vertices and the set $S$ of constraints. The running time of our algorithm is $O(n)$, provided that the constrained Delaunay triangulation of $I$ is given.
Trip-Based Public Transit Routing Using Condensed Search Trees
Venue: arXiv cs.DS 2016
Year: 2016

We study the problem of planning Pareto-optimal journeys in public transit networks. Most existing algorithms and speed-up techniques work by computing subjourneys to intermediary stops until the destination is reached. In contrast, the trip-based model focuses on trips and transfers between them, constructing journeys as a sequence of trips. In this paper, we develop a speed-up technique for this model inspired by principles behind existing state-of-the-art speed-up techniques, Transfer Pattern and Hub Labelling. The resulting algorithm allows us to compute Pareto-optimal (with respect to arrival time and number of transfers) 24-hour profiles on very large real-world networks in less than half a millisecond. Compared to the current state of the art for bicriteria queries on public transit networks, this is up to two orders of magnitude faster, while increasing preprocessing overhead by at most one order of magnitude.
Multipair Two-way Half-Duplex Relaying with Massive Arrays and Imperfect CSI
Venue: arXiv cs.IT 2016
Year: 2016

We consider a two-way half-duplex relaying system where multiple pairs of single antenna users exchange information assisted by a multi-antenna relay. Taking into account the practical constraint of imperfect channel estimation, we study the achievable sum spectral efficiency of the amplify-and-forward (AF) and decode-and-forward (DF) protocols, assuming that the relay employs simple maximum ratio processing. We derive an exact closed-form expression for the sum spectral efficiency of the AF protocol and a large-scale approximation for the sum spectral efficiency of the DF protocol when the number of relay antennas, $M$, becomes sufficiently large. In addition, we study how the transmit power scales with $M$ to maintain a desired quality-of-service. In particular, our results show that by using a large number of relay antennas, the transmit powers of the user, relay, and pilot symbol can be scaled down proportionally to $1/M^α$, $1/M^β$, and $1/M^γ$ for certain $α$, $β$, and $γ$, respectively. This elegant power scaling law reveals a fundamental tradeoff between the transmit powers of the user/relay and pilot symbol. Finally, capitalizing on the new expressions for the sum spectral efficiency, novel power allocation schemes are designed to further improve the sum spectral efficiency.
Deterministic Graph Exploration with Advice
Venue: arXiv cs.DS 2016
Year: 2016

We consider the task of graph exploration. An $n$-node graph has unlabeled nodes, and all ports at any node of degree $d$ are arbitrarily numbered $0,\dots, d-1$. A mobile agent has to visit all nodes and stop. The exploration time is the number of edge traversals. We consider the problem of how much knowledge the agent has to have a priori, in order to explore the graph in a given time, using a deterministic algorithm. This a priori information (advice) is provided to the agent by an oracle, in the form of a binary string, whose length is called the size of advice. We consider two types of oracles. The instance oracle knows the entire instance of the exploration problem, i.e., the port-numbered map of the graph and the starting node of the agent in this map. The map oracle knows the port-numbered map of the graph but does not know the starting node of the agent. We first consider exploration in polynomial time, and determine the exact minimum size of advice to achieve it. This size is $\log\log\log n -Θ(1)$, for both types of oracles. When advice is large, there are two natural time thresholds: $Θ(n^2)$ for a map oracle, and $Θ(n)$ for an instance oracle, that can be achieved with sufficiently large advice. We show that, with a map oracle, time $Θ(n^2)$ cannot be improved in general, regardless of the size of advice. We also show that the smallest size of advice to achieve this time is larger than $n^δ$, for any $δ<1/3$. For an instance oracle, advice of size $O(n\log n)$ is enough to achieve time $O(n)$. We show that, with any advice of size $o(n\log n)$, the time of exploration must be at least $n^ε$, for any $ε<2$, and with any advice of size $O(n)$, the time must be $Ω(n^2)$. We also investigate minimum advice sufficient for fast exploration of hamiltonian graphs.