OpenRaiser/Intern-Atlas huggingface dataset:
A Maximum A Posteriori Estimation Framework for Robust High Dynamic Range Video Synthesis
Venue: arXiv cs.CV 2016
Year: 2016

High dynamic range (HDR) image synthesis from multiple low dynamic range (LDR) exposures continues to be actively researched. The extension to HDR video synthesis is a topic of significant current interest due to potential cost benefits. For HDR video, a stiff practical challenge presents itself in the form of accurate correspondence estimation of objects between video frames. In particular, loss of data resulting from poor exposures and varying intensity make conventional optical flow methods highly inaccurate. We avoid exact correspondence estimation by proposing a statistical approach via maximum a posterior (MAP) estimation, and under appropriate statistical assumptions and choice of priors and models, we reduce it to an optimization problem of solving for the foreground and background of the target frame. We obtain the background through rank minimization and estimate the foreground via a novel multiscale adaptive kernel regression technique, which implicitly captures local structure and temporal motion by solving an unconstrained optimization problem. Extensive experimental results on both real and synthetic datasets demonstrate that our algorithm is more capable of delivering high-quality HDR videos than current state-of-the-art methods, under both subjective and objective assessments. Furthermore, a thorough complexity analysis reveals that our algorithm achieves better complexity-performance trade-off than conventional methods.
Lower Bounds for Differential Privacy from Gaussian Width
Venue: arXiv cs.DS 2016
Year: 2016

We study the optimal sample complexity of a given workload of linear queries under the constraints of differential privacy. The sample complexity of a query answering mechanism under error parameter $α$ is the smallest $n$ such that the mechanism answers the workload with error at most $α$ on any database of size $n$. Following a line of research started by Hardt and Talwar [STOC 2010], we analyze sample complexity using the tools of asymptotic convex geometry. We study the sensitivity polytope, a natural convex body associated with a query workload that quantifies how query answers can change between neighboring databases. This is the information that, roughly speaking, is protected by a differentially private algorithm, and, for this reason, we expect that a "bigger" sensitivity polytope implies larger sample complexity. Our results identify the mean Gaussian width as an appropriate measure of the size of the polytope, and show sample complexity lower bounds in terms of this quantity. Our lower bounds completely characterize the workloads for which the Gaussian noise mechanism is optimal up to constants as those having asymptotically maximal Gaussian width. Our techniques also yield an alternative proof of Pisier's Volume Number Theorem which also suggests an approach to improving the parameters of the theorem.
MIMO Channel Reconstruction from Lower Dimensional Multiple Antenna Measurements
Venue: arXiv cs.IT 2016
Year: 2016

A method for reconstructing multiple-input multiple-output (MIMO) channel correlation matrices from lower dimensional channel measurements is presented. Exploiting the symmetry of correlation matrix structure enables reproducing higher dimensional MIMO channel matrices from available lower order measurements. This leads to practically important applications allowing prediction of higher dimensional MIMO system capacity. In particular, we study Kronecker-type MIMO channels suitable for reconstructing full channel matrices from partial information about transmit-receive fading in spatial and polarimetric domains and analyze validity conditions for such models. One of the important channel conditions is Doppler frequency related to non-stationarity in the environment. We present simulations of cluster-type scattering model using 2x2 MIMO channel correlation matrices to predict performance of 2x4 MIMO system including recovery of angular power spectrum. An example of dual circular polarized 2x4 MIMO land mobile satellite measurements in 2.5 GHz frequency band illustrates applicability of the method to reconstruct spatial and polarimetric channel correlation matrices for estimating ergodic channel capacity from single-antenna or uni-polarized measurements.
A series of maximum entropy upper bounds of the differential entropy
Venue: arXiv cs.IT 2016
Year: 2016

We present a series of closed-form maximum entropy upper bounds for the differential entropy of a continuous univariate random variable and study the properties of that series. We then show how to use those generic bounds for upper bounding the differential entropy of Gaussian mixture models. This requires to calculate the raw moments and raw absolute moments of Gaussian mixtures in closed-form that may also be handy in statistical machine learning and information theory. We report on our experiments and discuss on the tightness of those bounds.
Hybrid Analog-Digital Transceiver Designs for Cognitive Large-Scale Antenna Array Systems
Venue: arXiv cs.IT 2016
Year: 2016

Milimeter wave (mmWave) band mobile communications can be a solution to the continuously increasing traffic demand in modern wireless systems. Even though mmWave bands are scarcely occupied, the design of a prospect transceiver should guarantee the efficient coexistence with the incumbent services in these bands. To that end, in this paper, two underlay cognitive transceiver designs are proposed that enable the mmWave spectrum access while controlling the interference to the incumbent users. MmWave systems usually require large antenna arrays to achieve satisfactory performance and thus, they cannot support fully digital transceiver designs due to high demands in hardware complexity and power consumption. Thus, in order to develop efficient solutions, the proposed approaches are based on a hybrid analog-digital pre-coding architecture. In such hybrid designs, the overall beamformer can be factorized in a low dimensional digital counterpart applied in the baseband and in an analog one applied in the RF domain. The first cognitive solution developed in this paper designs the cognitive hybrid pre-coder by maximizing the mutual information between its two ends subject to interference, power and hardware constraints related to the analog counterpart. The second solution aims at reduced complexity requirements and thus derives the hybrid pre-coder by minimizing the Frobenious norm of its difference to the optimal digital only one. A novel solution for the post-coder at the cognitive receiver part is further proposed here based on a hardware constrained Minimum Mean Square Error criterion. Simulations show that the performance of both the proposed hybrid approaches is very close to the one of the fully digital solution for typical wireless environments.
Dune-CurvilinearGrid: Parallel Dune Grid Manager for Unstructured Tetrahedral Curvilinear Meshes
Venue: arXiv cs.CG 2016
Year: 2016

We introduce the dune-curvilineargrid module. The module provides the self-contained, parallel grid manager, as well as the underlying elementary curvilinear geometry module dune-curvilineargeometry. This work is motivated by the need for reliable and scalable electromagnetic design of nanooptical devices. Curvilinear geometries improve both the accuracy of modeling smooth material boundaries, and the h/p-convergence rate of PDE solutions, reducing the necessary computational effort. dune-curvilineargrid provides a large spectrum of features for scalable parallel implementations of Finite Element and Boundary Integral methods over curvilinear tetrahedral geometries, including symbolic polynomial mappings and operations, recursive integration, sparse and dense grid communication, parallel timing and memory footprint diagnostics utilities. It is written in templated C++ using MPI for parallelization and ParMETIS for grid partitioning, and is provided as a module for the DUNE interface. The dune-curvilineargrid grid manager is continuously developed and improved, and so is this documentation. For the most recent version of the documentation, as well as the source code, please refer to the provided repositories and our website.
Approximation Algorithm for Cycle-Star Hub Network Design Problems and Cycle-Metric Labeling Problems
Venue: arXiv cs.DS 2016
Year: 2016

We consider a single allocation hub-and-spoke network design problem which allocates each non-hub node to exactly one of given hub nodes so as to minimize the total transportation cost. This paper deals with a case in which the hubs are located in a cycle, which is called a cycle-star hub network design problem. The problem is essentially equivalent to a cycle-metric labeling problem. The problem is useful in the design of networks in telecommunications and airline transportation systems.We propose a $2(1-1/h)$-approximation algorithm where $h$ denotes the number of hub nodes. Our algorithm solves a linear relaxation problem and employs a dependent rounding procedure. We analyze our algorithm by approximating a given cycle-metric matrix by a convex combination of Monge matrices.
Minimum energy control for complex networks
Venue: arXiv cs.SY 2016
Year: 2016

The aim of this paper is to shed light on the problem of controlling a complex network with minimal control energy. We show first that the control energy depends on the time constant of the modes of the network, and that the closer the eigenvalues are to the imaginary axis of the complex plane, the less energy is required for complete controllability. In the limit case of networks having all purely imaginary eigenvalues (e.g. networks of coupled harmonic oscillators), several constructive algorithms for minimum control energy driver node selection are developed. A general heuristic principle valid for any directed network is also proposed: the overall cost of controlling a network is reduced when the controls are concentrated on the nodes with highest ratio of weighted outdegree vs indegree.
Following Gaze Across Views
Venue: arXiv cs.CV 2016
Year: 2016

Following the gaze of people inside videos is an important signal for understanding people and their actions. In this paper, we present an approach for following gaze across views by predicting where a particular person is looking throughout a scene. We collect VideoGaze, a new dataset which we use as a benchmark to both train and evaluate models. Given one view with a person in it and a second view of the scene, our model estimates a density for gaze location in the second view. A key aspect of our approach is an end-to-end model that solves the following sub-problems: saliency, gaze pose, and geometric relationships between views. Although our model is supervised only with gaze, we show that the model learns to solve these subproblems automatically without supervision. Experiments suggest that our approach follows gaze better than standard baselines and produces plausible results for everyday situations.
Evaluating the Impact of AbuseHUB on Botnet Mitigation
Venue: arXiv cs.CR 2016
Year: 2016

This documents presents the final report of a two-year project to evaluate the impact of AbuseHUB, a Dutch clearinghouse for acquiring and processing abuse data on infected machines. The report was commissioned by the Netherlands Ministry of Economic Affairs, a co-funder of the development of AbuseHUB. AbuseHUB is the initiative of 9 Internet Service Providers, SIDN (the registry for the .nl top-level domain) and Surfnet (the national research and education network operator). The key objective of AbuseHUB is to improve the mitigation of botnets by its members. We set out to assess whether this objective is being reached by analyzing malware infection levels in the networks of AbuseHUB members and comparing them to those of other Internet Service Providers (ISPs). Since AbuseHUB members together comprise over 90 percent of the broadband market in the Netherlands, it also makes sense to compare how the country as a whole has performed compared to other countries. This report complements the baseline measurement report produced in December 2013 and the interim report from March 2015. We are using the same data sources as in the interim report, which is an expanded set compared to the earlier baseline report and to our 2011 study into botnet mitigation in the Netherlands.
Optimal mean-based algorithms for trace reconstruction
Venue: arXiv cs.CC 2016
Year: 2016

In the (deletion-channel) trace reconstruction problem, there is an unknown $n$-bit source string $x$. An algorithm is given access to independent traces of $x$, where a trace is formed by deleting each bit of~$x$ independently with probability~$δ$. The goal of the algorithm is to recover~$x$ exactly (with high probability), while minimizing samples (number of traces) and running time. Previously, the best known algorithm for the trace reconstruction problem was due to Holenstein~et~al.; it uses $\exp(\tilde{O}(n^{1/2}))$ samples and running time for any fixed $0 < δ< 1$. It is also what we call a "mean-based algorithm", meaning that it only uses the empirical means of the individual bits of the traces. Holenstein~et~al.~also gave a lower bound, showing that any mean-based algorithm must use at least $n^{\tildeΩ(\log n)}$ samples. In this paper we improve both of these results, obtaining matching upper and lower bounds for mean-based trace reconstruction. For any constant deletion rate $0 < δ< 1$, we give a mean-based algorithm that uses $\exp(O(n^{1/3}))$ time and traces; we also prove that any mean-based algorithm must use at least $\exp(Ω(n^{1/3}))$ traces. In fact, we obtain matching upper and lower bounds even for $δ$ subconstant and $ρ:= 1-δ$ subconstant: when $(\log^3 n)/n \ll δ\leq 1/2$ the bound is $\exp(-Θ(δn)^{1/3})$, and when $1/\sqrt{n} \ll ρ\leq 1/2$ the bound is $\exp(-Θ(n/ρ)^{1/3})$. Our proofs involve estimates for the maxima of Littlewood polynomials on complex disks. We show that these techniques can also be used to perform trace reconstruction with random insertions and bit-flips in addition to deletions. We also find a surprising result: for deletion probabilities $δ> 1/2$, the presence of insertions can actually help with trace reconstruction.
Automatic Lymphocyte Detection in H&E Images with Deep Neural Networks
Venue: arXiv cs.CV 2016
Year: 2016

Automatic detection of lymphocyte in H&E images is a necessary first step in lots of tissue image analysis algorithms. An accurate and robust automated lymphocyte detection approach is of great importance in both computer science and clinical studies. Most of the existing approaches for lymphocyte detection are based on traditional image processing algorithms and/or classic machine learning methods. In the recent years, deep learning techniques have fundamentally transformed the way that a computer interprets images and have become a matchless solution in various pattern recognition problems. In this work, we design a new deep neural network model which extends the fully convolutional network by combining the ideas in several recent techniques, such as shortcut links. Also, we design a new training scheme taking the prior knowledge about lymphocytes into consideration. The training scheme not only efficiently exploits the limited amount of free-form annotations from pathologists, but also naturally supports efficient fine-tuning. As a consequence, our model has the potential of self-improvement by leveraging the errors collected during real applications. Our experiments show that our deep neural network model achieves good performance in the images of different staining conditions or different types of tissues.
Dynamic Scheduling for Delay Guarantees for Heterogeneous Cognitive Radio Users
Venue: arXiv cs.IT 2016
Year: 2016

We study an uplink multi secondary user (SU) system having statistical delay constraints, and an average interference constraint to the primary user (PU). SUs with heterogeneous interference channel statistics, to the PU, experience heterogeneous delay performances since SUs causing low interference are scheduled more frequently than those causing high interference. We propose a scheduling algorithm that can provide arbitrary average delay guarantees to SUs irrespective of their statistical channel qualities. We derive the algorithm using the Lyapunov technique and show that it yields bounded queues and satisfy the interference constraints. Using simulations, we show its superiority over the Max-Weight algorithm.
Generalized Deep Image to Image Regression
Venue: arXiv cs.CV 2016
Year: 2016

We present a Deep Convolutional Neural Network architecture which serves as a generic image-to-image regressor that can be trained end-to-end without any further machinery. Our proposed architecture: the Recursively Branched Deconvolutional Network (RBDN) develops a cheap multi-context image representation very early on using an efficient recursive branching scheme with extensive parameter sharing and learnable upsampling. This multi-context representation is subjected to a highly non-linear locality preserving transformation by the remainder of our network comprising of a series of convolutions/deconvolutions without any spatial downsampling. The RBDN architecture is fully convolutional and can handle variable sized images during inference. We provide qualitative/quantitative results on $3$ diverse tasks: relighting, denoising and colorization and show that our proposed RBDN architecture obtains comparable results to the state-of-the-art on each of these tasks when used off-the-shelf without any post processing or task-specific architectural modifications.
Multiple Instance Learning: A Survey of Problem Characteristics and Applications
Venue: arXiv cs.CV 2016
Year: 2016

Multiple instance learning (MIL) is a form of weakly supervised learning where training instances are arranged in sets, called bags, and a label is provided for the entire bag. This formulation is gaining interest because it naturally fits various problems and allows to leverage weakly labeled data. Consequently, it has been used in diverse application fields such as computer vision and document classification. However, learning from bags raises important challenges that are unique to MIL. This paper provides a comprehensive survey of the characteristics which define and differentiate the types of MIL problems. Until now, these problem characteristics have not been formally identified and described. As a result, the variations in performance of MIL algorithms from one data set to another are difficult to explain. In this paper, MIL problem characteristics are grouped into four broad categories: the composition of the bags, the types of data distribution, the ambiguity of instance labels, and the task to be performed. Methods specialized to address each category are reviewed. Then, the extent to which these characteristics manifest themselves in key MIL application areas are described. Finally, experiments are conducted to compare the performance of 16 state-of-the-art MIL methods on selected problem characteristics. This paper provides insight on how the problem characteristics affect MIL algorithms, recommendations for future benchmarking and promising avenues for research.
Baby-Step Giant-Step Algorithms for the Symmetric Group
Venue: arXiv cs.SC 2016
Year: 2016

We study discrete logarithms in the setting of group actions. Suppose that $G$ is a group that acts on a set $S$. When $r,s \in S$, a solution $g \in G$ to $r^g = s$ can be thought of as a kind of logarithm. In this paper, we study the case where $G = S_n$, and develop analogs to the Shanks baby-step / giant-step procedure for ordinary discrete logarithms. Specifically, we compute two sets $A, B \subseteq S_n$ such that every permutation of $S_n$ can be written as a product $ab$ of elements $a \in A$ and $b \in B$. Our deterministic procedure is optimal up to constant factors, in the sense that $A$ and $B$ can be computed in optimal asymptotic complexity, and $|A|$ and $|B|$ are a small constant from $\sqrt{n!}$ in size. We also analyze randomized "collision" algorithms for the same problem.
BANDANA -- Body Area Network Device-to-device Authentication using Natural gAit
Venue: arXiv cs.CR 2016
Year: 2016

Secure spontaneous authentication between devices worn at arbitrary location on the same body is a challenging, yet unsolved problem. We propose BANDANA, the first-ever implicit secure device-to-device authentication scheme for devices worn on the same body. Our approach leverages instantaneous variation in acceleration patterns from gait sequences to extract always-fresh secure secrets. It enables secure spontaneous pairing of devices worn on the same body or interacted with. The method is robust against noise in sensor readings and active attackers. We demonstrate the robustness of BANDANA on two gait datasets and discuss the discriminability of intra- and inter-body cases, robustness to statistical bias, as well as possible attack scenarios.
On the Pragmatic Design of Literature Studies in Software Engineering: An Experience-based Guideline
Venue: arXiv cs.SE 2016
Year: 2016

Systematic literature studies have received much attention in empirical software engineering in recent years. They have become a powerful tool to collect and structure reported knowledge in a systematic and reproducible way. We distinguish systematic literature reviews to systematically analyze reported evidence in depth, and systematic mapping studies to structure a field of interest in a broader, usually quantified manner. Due to the rapidly increasing body of knowledge in software engineering, researchers who want to capture the published work in a domain often face an extensive amount of publications, which need to be screened, rated for relevance, classified, and eventually analyzed. Although there are several guidelines to conduct literature studies, they do not yet help researchers coping with the specific difficulties encountered in the practical application of these guidelines. In this article, we present an experience-based guideline to aid researchers in designing systematic literature studies with special emphasis on the data collection and selection procedures. Our guideline aims at providing a blueprint for a practical and pragmatic path through the plethora of currently available practices and deliverables capturing the dependencies among the single steps. The guideline emerges from various mapping studies and literature reviews conducted by the authors and provides recommendations for the general study design, data collection, and study selection procedures. Finally, we share our experiences and lessons learned in applying the different practices of the proposed guideline.
Segmentation of large images based on super-pixels and community detection in graphs
Venue: arXiv cs.CV 2016
Year: 2016

Image segmentation has many applications which range from machine learning to medical diagnosis. In this paper, we propose a framework for the segmentation of images based on super-pixels and algorithms for community identification in graphs. The super-pixel pre-segmentation step reduces the number of nodes in the graph, rendering the method the ability to process large images. Moreover, community detection algorithms provide more accurate segmentation than traditional approaches, such as those based on spectral graph partition. We also compare our method with two algorithms: a) the graph-based approach by Felzenszwalb and Huttenlocher and b) the contour-based method by Arbelaez. Results have shown that our method provides more precise segmentation and is faster than both of them.