OpenRaiser/Intern-Atlas huggingface dataset:
EPOBF: Energy Efficient Allocation of Virtual Machines in High Performance Computing Cloud
Venue: arXiv cs.DC 2014
Year: 2014

Cloud computing has become more popular in provision of computing resources under virtual machine (VM) abstraction for high performance computing (HPC) users to run their applications. A HPC cloud is such cloud computing environment. One of challenges of energy efficient resource allocation for VMs in HPC cloud is tradeoff between minimizing total energy consumption of physical machines (PMs) and satisfying Quality of Service (e.g. performance). On one hand, cloud providers want to maximize their profit by reducing the power cost (e.g. using the smallest number of running PMs). On the other hand, cloud customers (users) want highest performance for their applications. In this paper, we focus on the scenario that scheduler does not know global information about user jobs and user applications in the future. Users will request shortterm resources at fixed start times and non interrupted durations. We then propose a new allocation heuristic (named Energy-aware and Performance per watt oriented Bestfit (EPOBF)) that uses metric of performance per watt to choose which most energy-efficient PM for mapping each VM (e.g. maximum of MIPS per Watt). Using information from Feitelson's Parallel Workload Archive to model HPC jobs, we compare the proposed EPOBF to state of the art heuristics on heterogeneous PMs (each PM has multicore CPU). Simulations show that the EPOBF can reduce significant total energy consumption in comparison with state of the art allocation heuristics.
Convergence Constrained Multiuser Transmitter-Receiver Optimization in Single Carrier FDMA
Venue: arXiv cs.IT 2014
Year: 2014

Convergence constrained power allocation (CCPA) in single carrier multiuser (MU) single-input multiple-output (SIMO) systems with turbo equalization is considered in this paper. In order to exploit full benefit of the iterative receiver, its convergence properties need to be considered also at the transmitter side. The proposed scheme can guarantee that the desired quality of service (QoS) is achieved after sufficient amount of iterations. We propose two different successive convex approximations for solving the non-convex power minimization problem subject to user specific QoS constraints. The results of extrinsic information transfer (EXIT) chart analysis demonstrate that the proposed CCPA scheme can achieve the design objective. Numerical results show that the proposed schemes can achieve superior performance in terms of power consumption as compared to linear receivers with and without precoding as well as to the iterative receiver without precoding.
Information Loss and Anti-Aliasing Filters in Multirate Systems
Venue: arXiv cs.IT 2014
Year: 2014

This work investigates the information loss in a decimation system, i.e., in a downsampler preceded by an anti-aliasing filter. It is shown that, without a specific signal model in mind, the anti-aliasing filter cannot reduce information loss, while, e.g., for a simple signal-plus-noise model it can. For the Gaussian case, the optimal anti-aliasing filter is shown to coincide with the one obtained from energetic considerations. For a non-Gaussian signal corrupted by Gaussian noise, the Gaussian assumption yields an upper bound on the information loss, justifying filter design principles based on second-order statistics from an information-theoretic point-of-view.
When "I cut, you choose" method implies intransitivity
Venue: arXiv cs.GT 2014
Year: 2014

There is a common belief that humans and many animals follow transitive inference (choosing A over C on the basis of knowing that A is better than B and B is better than C). Transitivity seems to be the essence of rational choice. We present a theoretical model of a repeated game in which the players make a choice between three goods (e.g. food). The rules of the game refer to the simple procedure of fair division among two players, known as the "I cut, you choose" mechanism which has been widely discussed in the literature. In this game one of the players has to make intransitive choices in order to achieve the optimal result (for him/her and his/her co-player). The point is that an intransitive choice can be rational. Previously, an increase in the significance of intransitive strategies was achieved by referring to models of quantum games. We show that \textit{relevant intransitive strategies} also appear in the classic description of decision algorithms.
A Geometric Approach to Sound Source Localization from Time-Delay Estimates
Venue: arXiv cs.SD 2014
Year: 2014

This paper addresses the problem of sound-source localization from time-delay estimates using arbitrarily-shaped non-coplanar microphone arrays. A novel geometric formulation is proposed, together with a thorough algebraic analysis and a global optimization solver. The proposed model is thoroughly described and evaluated. The geometric analysis, stemming from the direct acoustic propagation model, leads to necessary and sufficient conditions for a set of time delays to correspond to a unique position in the source space. Such sets of time delays are referred to as feasible sets. We formally prove that every feasible set corresponds to exactly one position in the source space, whose value can be recovered using a closed-form localization mapping. Therefore we seek for the optimal feasible set of time delays given, as input, the received microphone signals. This time delay estimation problem is naturally cast into a programming task, constrained by the feasibility conditions derived from the geometric analysis. A global branch-and-bound optimization technique is proposed to solve the problem at hand, hence estimating the best set of feasible time delays and, subsequently, localizing the sound source. Extensive experiments with both simulated and real data are reported; we compare our methodology to four state-of-the-art techniques. This comparison clearly shows that the proposed method combined with the branch-and-bound algorithm outperforms existing methods. These in-depth geometric understanding, practical algorithms, and encouraging results, open several opportunities for future work.
Sparse Time-Frequency decomposition by dictionary learning
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we propose a time-frequency analysis method to obtain instantaneous frequencies and the corresponding decomposition by solving an optimization problem. In this optimization problem, the basis to decompose the signal is not known. Instead, it is adapted to the signal and is determined as part of the optimization problem. In this sense, this optimization problem can be seen as a dictionary learning problem. This dictionary learning problem is solved by using the Augmented Lagrangian Multiplier method (ALM) iteratively. We further accelerate the convergence of the ALM method in each iteration by using the fast wavelet transform. We apply our method to decompose several signals, including signals with poor scale separation, signals with outliers and polluted by noise and a real signal. The results show that this method can give accurate recovery of both the instantaneous frequencies and the intrinsic mode functions.
Effective Secrecy: Reliability, Confusion and Stealth
Venue: arXiv cs.IT 2014
Year: 2014

A security measure called effective security is defined that includes strong secrecy and stealth communication. Effective secrecy ensures that a message cannot be deciphered and that the presence of meaningful communication is hidden. To measure stealth we use resolvability and relate this to binary hypothesis testing. Results are developed for wire-tap channels and broadcast channels with confidential messages.
Beamforming Design for Joint Localization and Data Transmission in Distributed Antenna System
Venue: arXiv cs.IT 2014
Year: 2014

A distributed antenna system is studied whose goal is to provide data communication and positioning functionalities to Mobile Stations (MSs). Each MS receives data from a number of Base Stations (BSs), and uses the received signal not only to extract the information but also to determine its location. This is done based on Time of Arrival (TOA) or Time Difference of Arrival (TDOA) measurements, depending on the assumed synchronization conditions. The problem of minimizing the overall power expenditure of the BSs under data throughput and localization accuracy requirements is formulated with respect to the beamforming vectors used at the BSs. The analysis covers both frequency-flat and frequency-selective channels, and accounts also for robustness constraints in the presence of parameter uncertainty. The proposed algorithmic solutions are based on rank-relaxation and Difference-of-Convex (DC) programming.
Hardness Amplification and the Approximate Degree of Constant-Depth Circuits
Venue: arXiv cs.CC 2014
Year: 2014

We establish a generic form of hardness amplification for the approximability of constant-depth Boolean circuits by polynomials. Specifically, we show that if a Boolean circuit cannot be pointwise approximated by low-degree polynomials to within constant error in a certain one-sided sense, then an OR of disjoint copies of that circuit cannot be pointwise approximated even with very high error. As our main application, we show that for every sequence of degrees $d(n)$, there is an explicit depth-three circuit $F: \{-1,1\}^n \to \{-1,1\}$ of polynomial-size such that any degree-$d$ polynomial cannot pointwise approximate $F$ to error better than $1-\exp\left(-\tildeΩ(nd^{-3/2})\right)$. As a consequence of our main result, we obtain an $\exp\left(-\tildeΩ(n^{2/5})\right)$ upper bound on the the discrepancy of a function in AC$^0$, and an $\exp\left(\tildeΩ(n^{2/5})\right)$ lower bound on the threshold weight of AC$^0$, improving over the previous best results of $\exp\left(-Ω(n^{1/3})\right)$ and $\exp\left(Ω(n^{1/3})\right)$ respectively. Our techniques also yield a new lower bound of $Ω\left(n^{1/2}/\log^{(d-2)/2}(n)\right)$ on the approximate degree of the AND-OR tree of depth $d$, which is tight up to polylogarithmic factors for any constant $d$, as well as new bounds for read-once DNF formulas. In turn, these results imply new lower bounds on the communication and circuit complexity of these classes, and demonstrate strong limitations on existing PAC learning algorithms.
Computer simulations reveal complex distribution of haemodynamic forces in a mouse retina model of angiogenesis
Venue: arXiv cs.CE 2014
Year: 2014

There is currently limited understanding of the role played by haemodynamic forces on the processes governing vascular development. One of many obstacles to be overcome is being able to measure those forces, at the required resolution level, on vessels only a few micrometres thick. In the current paper, we present an in silico method for the computation of the haemodynamic forces experienced by murine retinal vasculature (a widely used vascular development animal model) beyond what is measurable experimentally. Our results show that it is possible to reconstruct high-resolution three-dimensional geometrical models directly from samples of retinal vasculature and that the lattice-Boltzmann algorithm can be used to obtain accurate estimates of the haemodynamics in these domains. We generate flow models from samples obtained at postnatal days (P) 5 and 6. Our simulations show important differences between the flow patterns recovered in both cases, including observations of regression occurring in areas where wall shear stress gradients exist. We propose two possible mechanisms to account for the observed increase in velocity and wall shear stress between P5 and P6: i) the measured reduction in typical vessel diameter between both time points, ii) the reduction in network density triggered by the pruning process. The methodology developed herein is applicable to other biomedical domains where microvasculature can be imaged but experimental flow measurements are unavailable or difficult to obtain.
Scalable Recommendation with Poisson Factorization
Venue: arXiv cs.IR 2014
Year: 2014

We develop a Bayesian Poisson matrix factorization model for forming recommendations from sparse user behavior data. These data are large user/item matrices where each user has provided feedback on only a small subset of items, either explicitly (e.g., through star ratings) or implicitly (e.g., through views or purchases). In contrast to traditional matrix factorization approaches, Poisson factorization implicitly models each user's limited attention to consume items. Moreover, because of the mathematical form of the Poisson likelihood, the model needs only to explicitly consider the observed entries in the matrix, leading to both scalable computation and good predictive performance. We develop a variational inference algorithm for approximate posterior inference that scales up to massive data sets. This is an efficient algorithm that iterates over the observed entries and adjusts an approximate posterior over the user/item representations. We apply our method to large real-world user data containing users rating movies, users listening to songs, and users reading scientific papers. In all these settings, Bayesian Poisson factorization outperforms state-of-the-art matrix factorization methods.
Embed and Conquer: Scalable Embeddings for Kernel k-Means on MapReduce
Venue: arXiv cs.LG 2014
Year: 2014

The kernel $k$-means is an effective method for data clustering which extends the commonly-used $k$-means algorithm to work on a similarity matrix over complex data structures. The kernel $k$-means algorithm is however computationally very complex as it requires the complete data matrix to be calculated and stored. Further, the kernelized nature of the kernel $k$-means algorithm hinders the parallelization of its computations on modern infrastructures for distributed computing. In this paper, we are defining a family of kernel-based low-dimensional embeddings that allows for scaling kernel $k$-means on MapReduce via an efficient and unified parallelization strategy. Afterwards, we propose two methods for low-dimensional embedding that adhere to our definition of the embedding family. Exploiting the proposed parallelization strategy, we present two scalable MapReduce algorithms for kernel $k$-means. We demonstrate the effectiveness and efficiency of the proposed algorithms through an empirical evaluation on benchmark data sets.
User recommendation in reciprocal and bipartite social networks -- a case study of online dating
Venue: arXiv cs.SI 2014
Year: 2014

Many social networks in our daily life are bipartite networks built on reciprocity. How can we recommend users/friends to a user, so that the user is interested in and attractive to recommended users? In this research, we propose a new collaborative filtering model to improve user recommendations in reciprocal and bipartite social networks. The model considers a user's "taste" in picking others and "attractiveness" in being picked by others. A case study of an online dating network shows that the new model has good performance in recommending both initial and reciprocal contacts.
Packet Travel Times in Wireless Relay Chains under Spatially and Temporally Dependent Interference
Venue: arXiv cs.NI 2014
Year: 2014

We investigate the statistics of the number of time slots $T$ that it takes a packet to travel through a chain of wireless relays. Derivations are performed assuming an interference model for which interference possesses spatiotemporal dependency properties. When using this model, results are harder to arrive at analytically, but they are more realistic than the ones obtained in many related works that are based on independent interference models. First, we present a method for calculating the distribution of $T$. As the required computations are extensive, we also obtain simple expressions for the expected value $\mathrm{E} [T]$ and variance $\mathrm{var} [T]$. Finally, we calculate the asymptotic limit of the average speed of the packet. Our numerical results show that spatiotemporal dependence has a significant impact on the statistics of the travel time $T$. In particular, we show that, with respect to the independent interference case, $\mathrm{E} [T]$ and $\mathrm{var} [T]$ increase, whereas the packet speed decreases.
Local reductions
Venue: arXiv cs.CC 2014
Year: 2014

We reduce non-deterministic time $T \ge 2^n$ to a 3SAT instance $ϕ$ of quasilinear size $|ϕ| = T \cdot \log^{O(1)} T$ such that there is an explicit circuit $C$ that on input an index $i$ of $\log |ϕ|$ bits outputs the $i$th clause, and each output bit of $C$ depends on $O(1)$ input bits. The previous best result was $C$ in NC$^1$. Even in the simpler setting of polynomial size $|ϕ| = \poly(T)$ the previous best result was $C$ in AC$^0$. More generally, for any time $T \ge n$ and parameter $r \leq n$ we obtain $\log_2 |ϕ| = \max(\log T, n/r) + O(\log n) + O(\log\log T)$ and each output bit of $C$ is a decision tree of depth $O(\log r)$. As an application, we tighten Williams' connection between satisfiability algorithms and circuit lower bounds (STOC 2010; SIAM J. Comput. 2013).
Performance of General STCs over Spatially Correlated MIMO Single-keyhole Channels
Venue: arXiv cs.IT 2014
Year: 2014

For MIMO Rayleigh channels, it has been shown that transmitter correlations always degrade the performance of general space-time codes (STCs) in high SNR regimes. In this correspondence, however, we show that when MIMO channels experience single-keyhole conditions, the effect of spatial correlations between transmission antennas is more sophisticated for general STCs: when $M>N$ (i.e., the number of transmission antennas is greater than the number of receiving antennas), depending on how the correlation matrix $\mathbf{P}$ beamforms the code word difference matrix $\mathbfΔ$, the PEP performance of general STCs can be either degraded or improved in high SNR regimes. We provide a new measure, which is based on the eigenvalues of $\mathbfΔ$ and the numbers of transmission and receiving antennas, to exam if there exists certain correlation matrices that can improve the performance of general STCs in high SNR regimes. Previous studies on the effect of spatial correlations over single-keyhole channels only concentrated on orthogonal STCs, while our study here is for general STCs and can also be used to explain previous findings for orthogonal STCs.
When Equivalence and Bisimulation Join Forces in Probabilistic Automata
Venue: arXiv cs.LO 2014
Year: 2014

Probabilistic automata were introduced by Rabin in 1963 as language acceptors. Two automata are equivalent if and only if they accept each word with the same probability. On the other side, in the process algebra community, probabilistic automata were re-proposed by Segala in 1995 which are more general than Rabin's automata. Bisimulations have been proposed for Segala's automata to characterize the equivalence between them. So far the two notions of equivalences and their characteristics have been studied most independently. In this paper, we consider Segala's automata, and propose a novel notion of distribution based bisimulation by joining the existing equivalence and bisimilarities. Our bisimulation bridges the two closely related concepts in the community, and provides a uniform way of studying their characteristics. We demonstrate the utility of our definition by studying distribution based bisimulation metrics, which gives rise to a robust notion of equivalence for Rabin's automata.
First Workshop on Sustainable Software for Science: Practice and Experiences (WSSSPE): Submission and Peer-Review Process, and Results
Venue: arXiv cs.SE 2014
Year: 2014

This technical report discusses the submission and peer-review process used by the First Workshop on on Sustainable Software for Science: Practice and Experiences (WSSSPE) and the results of that process. It is intended to record both this alternative model as well as the papers associated with the workshop that resulted from that process.
On the length of integers in telescopers for proper hypergeometric terms
Venue: arXiv cs.SC 2014
Year: 2014

We show that the number of digits in the integers of a creative telescoping relation of expected minimal order for a bivariate proper hypergeometric term has essentially cubic growth with the problem size. For telescopers of higher order but lower degree we obtain a quintic bound. Experiments suggest that these bounds are tight. As applications of our results, we give an improved bound on the maximal possible integer root of the leading coefficient of a telescoper, and the first discussion of the bit complexity of creative telescoping.
Blind Deconvolution with Non-local Sparsity Reweighting
Venue: arXiv cs.CV 2014
Year: 2014

Blind deconvolution has made significant progress in the past decade. Most successful algorithms are classified either as Variational or Maximum a-Posteriori ($MAP$). In spite of the superior theoretical justification of variational techniques, carefully constructed $MAP$ algorithms have proven equally effective in practice. In this paper, we show that all successful $MAP$ and variational algorithms share a common framework, relying on the following key principles: sparsity promotion in the gradient domain, $l_2$ regularization for kernel estimation, and the use of convex (often quadratic) cost functions. Our observations lead to a unified understanding of the principles required for successful blind deconvolution. We incorporate these principles into a novel algorithm that improves significantly upon the state of the art.
Interactive Distributed Detection: Architecture and Performance Analysis
Venue: arXiv cs.IT 2014
Year: 2014

This paper studies the impact of interactive fusion on detection performance in tandem fusion networks with conditionally independent observations. Within the Neyman-Pearson framework, two distinct regimes are considered: the fixed sample size test and the large sample test. For the former, it is established that interactive distributed detection may strictly outperform the one-way tandem fusion structure. However, for the large sample regime, it is shown that interactive fusion has no improvement on the asymptotic performance characterized by the Kullback-Leibler (KL) distance compared with the simple one-way tandem fusion. The results are then extended to interactive fusion systems where the fusion center and the sensor may undergo multiple steps of memoryless interactions or that involve multiple peripheral sensors, as well as to interactive fusion with soft sensor outputs.
On the Mixed H2/H-infinity Loop Shaping Trade-offs in Fractional Order Control of the AVR System
Venue: arXiv cs.SY 2014
Year: 2014

This paper looks at frequency domain design of a fractional order (FO) PID controller for an Automatic Voltage Regulator (AVR) system. Various performance criteria of the AVR system are formulated as system norms and is then coupled with an evolutionary multi-objective optimization (MOO) algorithm to yield Pareto optimal design trade-offs. The conflicting performance measures consist of the mixed H2/H-infinity designs for objectives like set-point tracking, load disturbance and noise rejection, controller effort and as such are an exhaustive study of various conflicting design objectives. A fuzzy logic based mechanism is used to identify the best compromise solution on the Pareto fronts. The advantages and disadvantages of using a FOPID controller over the conventional PID controller, which are popular for industrial use, are enunciated from the presented simulations. The relevance and impact of FO controller design from the perspective of the dynamics of AVR control loop is also discussed.