OpenRaiser/Intern-Atlas huggingface dataset:
A Unifying Survey of Reinforced, Sensitive and Stigmergic Agent-Based Approaches for E-GTSP
Venue: arXiv cs.AI 2014
Year: 2014

The Generalized Traveling Salesman Problem (GTSP) is one of the NP-hard combinatorial optimization problems. A variant of GTSP is E-GTSP where E, meaning equality, has the constraint: exactly one node from a cluster of a graph partition is visited. The main objective of the E-GTSP is to find a minimum cost tour passing through exactly one node from each cluster of an undirected graph. Agent-based approaches involving are successfully used nowadays for solving real life complex problems. The aim of the current paper is to illustrate some variants of agent-based algorithms including ant-based models with specific properties for solving E-GTSP.
A C++11 implementation of arbitrary-rank tensors for high-performance computing
Venue: arXiv cs.MS 2014
Year: 2014

This article discusses an efficient implementation of tensors of arbitrary rank by using some of the idioms introduced by the recently published C++ ISO Standard (C++11). With the aims at providing a basic building block for high-performance computing, a single Array class template is carefully crafted, from which vectors, matrices, and even higher-order tensors can be created. An expression template facility is also built around the array class template to provide convenient mathematical syntax. As a result, by using templates, an extra high-level layer is added to the C++ language when dealing with algebraic objects and their operations, without compromising performance. The implementation is tested running on both CPU and GPU.
Blind Image Deblurring by Spectral Properties of Convolution Operators
Venue: arXiv cs.CV 2014
Year: 2014

In this paper, we study the problem of recovering a sharp version of a given blurry image when the blur kernel is unknown. Previous methods often introduce an image-independent regularizer (such as Gaussian or sparse priors) on the desired blur kernel. We shall show that the blurry image itself encodes rich information about the blur kernel. Such information can be found through analyzing and comparing how the spectrum of an image as a convolution operator changes before and after blurring. Our analysis leads to an effective convex regularizer on the blur kernel which depends only on the given blurry image. We show that the minimizer of this regularizer guarantees to give good approximation to the blur kernel if the original image is sharp enough. By combining this powerful regularizer with conventional image deblurring techniques, we show how we could significantly improve the deblurring results through simulations and experiments on real images. In addition, our analysis and experiments help explaining a widely accepted doctrine; that is, the edges are good features for deblurring.
Thompson Sampling for Contextual Bandits with Linear Payoffs
Venue: arXiv cs.LG 2014
Year: 2014

Thompson Sampling is one of the oldest heuristics for multi-armed bandit problems. It is a randomized algorithm based on Bayesian ideas, and has recently generated significant interest after several studies demonstrated it to have better empirical performance compared to the state-of-the-art methods. However, many questions regarding its theoretical performance remained open. In this paper, we design and analyze a generalization of Thompson Sampling algorithm for the stochastic contextual multi-armed bandit problem with linear payoff functions, when the contexts are provided by an adaptive adversary. This is among the most important and widely studied versions of the contextual bandits problem. We provide the first theoretical guarantees for the contextual version of Thompson Sampling. We prove a high probability regret bound of $\tilde{O}(d^{3/2}\sqrt{T})$ (or $\tilde{O}(d\sqrt{T \log(N)})$), which is the best regret bound achieved by any computationally efficient algorithm available for this problem in the current literature, and is within a factor of $\sqrt{d}$ (or $\sqrt{\log(N)}$) of the information-theoretic lower bound for this problem.
On Revenue Maximization with Sharp Multi-Unit Demands
Venue: arXiv cs.GT 2014
Year: 2014

We consider markets consisting of a set of indivisible items, and buyers that have {\em sharp} multi-unit demand. This means that each buyer $i$ wants a specific number $d_i$ of items; a bundle of size less than $d_i$ has no value, while a bundle of size greater than $d_i$ is worth no more than the most valued $d_i$ items (valuations being additive). We consider the objective of setting prices and allocations in order to maximize the total revenue of the market maker. The pricing problem with sharp multi-unit demand buyers has a number of properties that the unit-demand model does not possess, and is an important question in algorithmic pricing. We consider the problem of computing a revenue maximizing solution for two solution concepts: competitive equilibrium and envy-free pricing. For unrestricted valuations, these problems are NP-complete; we focus on a realistic special case of "correlated values" where each buyer $i$ has a valuation $v_i\qual_j$ for item $j$, where $v_i$ and $\qual_j$ are positive quantities associated with buyer $i$ and item $j$ respectively. We present a polynomial time algorithm to solve the revenue-maximizing competitive equilibrium problem. For envy-free pricing, if the demand of each buyer is bounded by a constant, a revenue maximizing solution can be found efficiently; the general demand case is shown to be NP-hard.
Minimum Distortion Variance Concatenated Block Codes for Embedded Source Transmission
Venue: arXiv cs.MM 2014
Year: 2014

Some state-of-art multimedia source encoders produce embedded source bit streams that upon the reliable reception of only a fraction of the total bit stream, the decoder is able reconstruct the source up to a basic quality. Reliable reception of later source bits gradually improve the reconstruction quality. Examples include scalable extensions of H.264/AVC and progressive image coders such as JPEG2000. To provide an efficient protection for embedded source bit streams, a concatenated block coding scheme using a minimum mean distortion criterion was considered in the past. Although, the original design was shown to achieve better mean distortion characteristics than previous studies, the proposed coding structure was leading to dramatic quality fluctuations. In this paper, a modification of the original design is first presented and then the second order statistics of the distortion is taken into account in the optimization. More specifically, an extension scheme is proposed using a minimum distortion variance optimization criterion. This robust system design is tested for an image transmission scenario. Numerical results show that the proposed extension achieves significantly lower variance than the original design, while showing similar mean distortion performance using both convolutional codes and low density parity check codes.
On the Privacy of Optimization Approaches
Venue: arXiv cs.CR 2014
Year: 2014

Ensuring privacy of sensitive data is essential in many contexts, such as healthcare data, banks, e-commerce, wireless sensor networks, and social networks. It is common that different entities coordinate or want to rely on a third party to solve a specific problem. At the same time, no entity wants to publish its problem data during the solution procedure unless there is a privacy guarantee. Unlike cryptography and differential privacy based approaches, the methods based on optimization lack a quantification of the privacy they can provide. The main contribution of this paper is to provide a mechanism to quantify the privacy of a broad class of optimization approaches. In particular, we formally define a one-to-many relation, which relates a given adversarial observed message to an uncertainty set of the problem data. This relation quantifies the potential ambiguity on problem data due to the employed optimization approaches. The privacy definitions are then formalized based on the uncertainty sets. The properties of the proposed privacy measure is analyzed. The key ideas are illustrated with examples, including localization, average consensus, among others.
A Fragment of Dependence Logic Capturing Polynomial Time
Venue: arXiv cs.LO 2014
Year: 2014

In this paper we study the expressive power of Horn-formulae in dependence logic and show that they can express NP-complete problems. Therefore we define an even smaller fragment D-Horn* and show that over finite successor structures it captures the complexity class P of all sets decidable in polynomial time. Furthermore we study the question which of our results can ge generalized to the case of open formulae of D-Horn* and so-called downwards monotone polynomial time properties of teams.
Epigraphical splitting for solving constrained convex formulations of inverse problems with proximal tools
Venue: arXiv cs.NA 2014
Year: 2014

We propose a proximal approach to deal with a class of convex variational problems involving nonlinear constraints. A large family of constraints, proven to be effective in the solution of inverse problems, can be expressed as the lower level set of a sum of convex functions evaluated over different, but possibly overlapping, blocks of the signal. For such constraints, the associated projection operator generally does not have a simple form. We circumvent this difficulty by splitting the lower level set into as many epigraphs as functions involved in the sum. A closed half-space constraint is also enforced, in order to limit the sum of the introduced epigraphical variables to the upper bound of the original lower level set. In this paper, we focus on a family of constraints involving linear transforms of distance functions to a convex set or $\ell_{1,p}$ norms with $p\in \{1,2,\infty\}$. In these cases, the projection onto the epigraph of the involved function has a closed form expression. The proposed approach is validated in the context of image restoration with missing samples, by making use of constraints based on Non-Local Total Variation. Experiments show that our method leads to significant improvements in term of convergence speed over existing algorithms for solving similar constrained problems. A second application to a pulse shape design problem is provided in order to illustrate the flexibility of the proposed approach.
On solving large scale polynomial convex problems by randomized first-order algorithms
Venue: arXiv cs.DS 2014
Year: 2014

One of the most attractive recent approaches to processing well-structured large-scale convex optimization problems is based on smooth convex-concave saddle point reformu-lation of the problem of interest and solving the resulting problem by a fast First Order saddle point method utilizing smoothness of the saddle point cost function. In this paper, we demonstrate that when the saddle point cost function is polynomial, the precise gra-dients of the cost function required by deterministic First Order saddle point algorithms and becoming prohibitively computationally expensive in the extremely large-scale case, can be replaced with incomparably cheaper computationally unbiased random estimates of the gradients. We show that for large-scale problems with favourable geometry, this randomization accelerates, progressively as the sizes of the problem grow, the solution process. This extends significantly previous results on acceleration by randomization, which, to the best of our knowledge, dealt solely with bilinear saddle point problems. We illustrate our theoretical findings by instructive and encouraging numerical experiments.
Schulze and Ranked-Pairs Voting are Fixed-Parameter Tractable to Bribe, Manipulate, and Control
Venue: arXiv cs.GT 2014
Year: 2014

Schulze and ranked-pairs elections have received much attention recently, and the former has quickly become a quite widely used election system. For many cases these systems have been proven resistant to bribery, control, or manipulation, with ranked pairs being particularly praised for being NP-hard for all three of those. Nonetheless, the present paper shows that with respect to the number of candidates, Schulze and ranked-pairs elections are fixed-parameter tractable to bribe, control, and manipulate: we obtain uniform, polynomial-time algorithms whose degree does not depend on the number of candidates. We also provide such algorithms for some weighted variants of these problems.
Distribution of the Number of Retransmissions of Bounded Documents
Venue: arXiv cs.PF 2014
Year: 2014

Retransmission-based failure recovery represents a primary approach in existing communication networks that guarantees data delivery in the presence of channel failures. Recent work has shown that, when data sizes have infinite support, retransmissions can cause long (-tailed) delays even if all traffic and network characteristics are light-tailed. In this paper we investigate the practically important case of bounded data units 0 <= L_b <= b under the condition that the hazard functions of the distributions of data sizes and channel statistics are proportional. To this end, we provide an explicit and uniform characterization of the entire body of the retransmission distribution Pr[N_b > n] in both n and b. Our main discovery is that this distribution can be represented as the product of a power law and Gamma distribution. This rigorous approximation clearly demonstrates the coupling of a power law distribution, dominating the main body, and the Gamma distribution, determining the exponential tail. Our results are validated via simulation experiments and can be useful for designing retransmission-based systems with the required performance characteristics. From a broader perspective, this study applies to any other system, e.g., computing, where restart mechanisms are employed after a job processing failure.
Recursive Robust PCA or Recursive Sparse Recovery in Large but Structured Noise
Venue: arXiv cs.IT 2014
Year: 2014

This work studies the recursive robust principal components' analysis(PCA) problem. Here, "robust" refers to robustness to both independent and correlated sparse outliers. If the outlier is the signal-of-interest, this problem can be interpreted as one of recursively recovering a time sequence of sparse vectors, St, in the presence of large but structured noise, Lt. The structure that we assume on Lt is that Lt is dense and lies in a low dimensional subspace that is either fixed or changes "slowly enough". A key application where this problem occurs is in video surveillance where the goal is to separate a slowly changing background (Lt) from moving foreground objects (St) on-the-fly. To solve the above problem, we introduce a novel solution called Recursive Projected CS (ReProCS). Under mild assumptions, we show that, with high probability (w.h.p.), ReProCS can exactly recover the support set of St at all times; and the reconstruction errors of both St and Lt are upper bounded by a time-invariant and small value at all times.
The Algebraic Combinatorial Approach for Low-Rank Matrix Completion
Venue: arXiv cs.LG 2014
Year: 2014

We present a novel algebraic combinatorial view on low-rank matrix completion based on studying relations between a few entries with tools from algebraic geometry and matroid theory. The intrinsic locality of the approach allows for the treatment of single entries in a closed theoretical and practical framework. More specifically, apart from introducing an algebraic combinatorial theory of low-rank matrix completion, we present probability-one algorithms to decide whether a particular entry of the matrix can be completed. We also describe methods to complete that entry from a few others, and to estimate the error which is incurred by any method completing that entry. Furthermore, we show how known results on matrix completion and their sampling assumptions can be related to our new perspective and interpreted in terms of a completability phase transition.
Energy-Efficient Nonstationary Spectrum Sharing
Venue: arXiv cs.IT 2014
Year: 2014

We develop a novel design framework for energy-efficient spectrum sharing among autonomous users who aim to minimize their energy consumptions subject to minimum throughput requirements. Most existing works proposed stationary spectrum sharing policies, in which users transmit at fixed power levels. Since users transmit simultaneously under stationary policies, to fulfill minimum throughput requirements, they need to transmit at high power levels to overcome interference. To improve energy efficiency, we construct nonstationary spectrum sharing policies, in which the users transmit at time-varying power levels. Specifically, we focus on TDMA (time-division multiple access) policies in which one user transmits at each time (but not in a round-robin fashion). The proposed policy can be implemented by each user running a low-complexity algorithm in a decentralized manner. It achieves high energy efficiency even when the users have erroneous and binary feedback about their interference levels. Moreover, it can adapt to the dynamic entry and exit of users. The proposed policy is also deviation-proof, namely autonomous users will find it in their self-interests to follow it. Compared to existing policies, the proposed policy can achieve an energy saving of up to 90% when the number of users is high.
Degrees of Freedom of the 3-User Rank-Deficient MIMO Interference Channel
Venue: arXiv cs.IT 2014
Year: 2014

We provide the degrees of freedom (DoF) characterization for the $3$-user $M_T\times M_R$ multiple-input multiple-output (MIMO) interference channel (IC) with \emph{rank-deficient} channel matrices, where each transmitter is equipped with $M_T$ antennas and each receiver with $M_R$ antennas, and the interfering channel matrices from each transmitter to the other two receivers are of ranks $D_1$ and $D_2$, respectively. One important intermediate step for both the converse and achievability arguments is to convert the fully-connected rank-deficient channel into an equivalent partially-connected full-rank MIMO-IC by invertible linear transformations. As such, existing techniques developed for full-rank MIMO-IC can be incorporated to derive the DoF outer and inner bounds for the rank-deficient case. Our result shows that when the interfering links are weak in terms of the channel ranks, i.e., $D_1+D_2\leq \min(M_T, M_R)$, zero forcing is sufficient to achieve the optimal DoF. On the other hand, when $D_1+D_2> \min(M_T, M_R)$, a combination of zero forcing and interference alignment is in general required for DoF optimality. The DoF characterization obtained in this paper unifies several existing results in the literature.
On Top-$k$ Weighted SUM Aggregate Nearest and Farthest Neighbors in the $L_1$ Plane
Venue: arXiv cs.CG 2014
Year: 2014

In this paper, we study top-$k$ aggregate (or group) nearest neighbor queries using the weighted SUM operator under the $L_1$ metric in the plane. Given a set $P$ of $n$ points, for any query consisting of a set $Q$ of $m$ weighted points and an integer $k$, $ 1 \le k \le n$, the top-$k$ aggregate nearest neighbor query asks for the $k$ points of $P$ whose aggregate distances to $Q$ are the smallest, where the aggregate distance of each point $p$ of $P$ to $Q$ is the sum of the weighted distances from $p$ to all points of $Q$. We build an $O(n\log n\log\log n)$-size data structure in $O(n\log n \log\log n)$ time, such that each top-$k$ query can be answered in $O(m\log m+(k+m)\log^2 n)$ time. We also obtain other results with trade-off between preprocessing and query. Even for the special case where $k=1$, our results are better than the previously best method (in PODS 2012), which requires $O(n\log^2 n)$ preprocessing time, $O(n\log^2 n)$ space, and $O(m^2\log^3 n)$ query time. In addition, for the one-dimensional version of this problem, our approach can build an $O(n)$-size data structure in $O(n\log n)$ time that can support $O(\min\{k,\log m\}\cdot m+k+\log n)$ time queries. Further, we extend our techniques to the top-$k$ aggregate farthest neighbor queries, with the same bounds.
Corpus Development for Affective Video Indexing
Venue: arXiv cs.MM 2014
Year: 2014

Affective video indexing is the area of research that develops techniques to automatically generate descriptions of video content that encode the emotional reactions which the video content evokes in viewers. This paper provides a set of corpus development guidelines based on state-of-the-art practice intended to support researchers in this field. Affective descriptions can be used for video search and browsing systems offering users affective perspectives. The paper is motivated by the observation that affective video indexing has yet to fully profit from the standard corpora (data sets) that have benefited conventional forms of video indexing. Affective video indexing faces unique challenges, since viewer-reported affective reactions are difficult to assess. Moreover affect assessment efforts must be carefully designed in order to both cover the types of affective responses that video content evokes in viewers and also capture the stable and consistent aspects of these responses. We first present background information on affect and multimedia and related work on affective multimedia indexing, including existing corpora. Three dimensions emerge as critical for affective video corpora, and form the basis for our proposed guidelines: the context of viewer response, personal variation among viewers, and the effectiveness and efficiency of corpus creation. Finally, we present examples of three recent corpora and discuss how these corpora make progressive steps towards fulfilling the guidelines.
Dual techniques for scheduling on a machine with varying speed
Venue: arXiv cs.DS 2014
Year: 2014

We study scheduling problems on a machine with varying speed. Assuming a known speed function we ask for a cost-efficient scheduling solution. Our main result is a PTAS for minimizing the total weighted completion time in this setting. This also implies a PTAS for the closely related problem of scheduling to minimize generalized global cost functions. The key to our results is a re-interpretation of the problem within the well-known two-dimensional Gantt chart: instead of the standard approach of scheduling in the {\em time-dimension}, we construct scheduling solutions in the weight-dimension. We also consider a dynamic problem variant in which deciding upon the speed is part of the scheduling problem and we are interested in the tradeoff between scheduling cost and speed-scaling cost, which is typically the energy consumption. We observe that the optimal order is independent of the energy consumption and that the problem can be reduced to the setting where the speed of the machine is fixed, and thus admits a PTAS. Furthermore, we provide an FPTAS for the NP-hard problem variant in which the machine can run only on a fixed number of discrete speeds. Finally, we show how our results can be used to obtain a~$(2+\eps)$-approximation for scheduling preemptive jobs with release dates on multiple identical parallel machines.