OpenRaiser/Intern-Atlas huggingface dataset:
On multi-time-step monolithic coupling algorithms for elastodynamics
Venue: arXiv cs.NA 2014
Year: 2014

We present a way of constructing multi-time-step monolithic coupling methods for elastodynamics. The governing equations for constrained multiple subdomains are written in dual Schur form and enforce the continuity of velocities at system time levels. The resulting equations will be in the form of differential-algebraic equations. To crystallize the ideas we shall employ Newmark family of time-stepping schemes. The proposed method can handle multiple subdomains, and allows different time-steps as well as different time stepping schemes from the Newmark family in different subdomains. We shall use the energy method to assess the numerical stability, and quantify the influence of perturbations under the proposed coupling method. We also discuss the conditions under which the proposed method will be energy preserving, and the conditions under which the method will be energy conserving. Several numerical examples are presented to illustrate the accuracy and stability properties of the proposed method. We shall also compare the proposed multi-time-step coupling method with some other similar methods available in the literature.
A DSATUR-based algorithm for the Equitable Coloring Problem
Venue: arXiv cs.DM 2014
Year: 2014

This paper describes a new exact algorithm for the Equitable Coloring Problem, a coloring problem where the sizes of two arbitrary color classes differ in at most one unit. Based on the well known DSatur algorithm for the classic Coloring Problem, a new pruning criterion arising from equity constraints is proposed and analyzed. The good performance of the algorithm is shown through computational experiments over random and benchmark instances.
Collaborative 20 Questions for Target Localization
Venue: arXiv cs.IT 2014
Year: 2014

We consider the problem of 20 questions with noise for multiple players under the minimum entropy criterion in the setting of stochastic search, with application to target localization. Each player yields a noisy response to a binary query governed by a certain error probability. First, we propose a sequential policy for constructing questions that queries each player in sequence and refines the posterior of the target location. Second, we consider a joint policy that asks all players questions in parallel at each time instant and characterize the structure of the optimal policy for constructing the sequence of questions. This generalizes the single player probabilistic bisection method for stochastic search problems. Third, we prove an equivalence between the two schemes showing that, despite the fact that the sequential scheme has access to a more refined filtration, the joint scheme performs just as well on average. Fourth, we establish convergence rates of the mean-square error (MSE) and derive error exponents. Lastly, we obtain an extension to the case of unknown error probabilities. This framework provides a mathematical model for incorporating a human in the loop for active machine learning systems.
Bounded Variability of Metric Temporal Logic
Venue: arXiv cs.LO 2014
Year: 2014

Previous work has shown that reasoning with real-time temporal logics is often simpler when restricted to models with bounded variability---where no more than v events may occur every V time units, for given v, V. When reasoning about formulas with intrinsic bounded variability, one can employ the simpler techniques that rely on bounded variability, without any loss of generality. What is then the complexity of algorithmically deciding which formulas have intrinsic bounded variability? In this paper, we study the problem with reference to Metric Temporal Logic (MTL). We prove that deciding bounded variability of MTL formulas is undecidable over dense-time models, but with a undecidability degree lower than generic dense-time MTL satisfiability. Over discrete-time models, instead, deciding MTL bounded variability has the same exponential-space complexity as satisfiability. To complement these negative results, we also briefly discuss small fragments of MTL that are more amenable to reasoning about bounded variability.
Extending Partial Representations of Interval Graphs
Venue: arXiv cs.DM 2014
Year: 2014

Interval graphs are intersection graphs of closed intervals of the real-line. The well-known computational problem, called recognition, asks whether an input graph $G$ can be represented by closed intervals, i.e., whether $G$ is an interval graph. There are several linear-time algorithms known for recognizing interval graphs, the oldest one is by Booth and Lueker [J. Comput. System Sci., 13 (1976)] based on PQ-trees. In this paper, we study a generalization of recognition, called partial representation extension. The input of this problem consists of a graph $G$ with a partial representation $\cal R'$ fixing the positions of some intervals. The problem asks whether it is possible to place the remaining interval and create an interval representation $\cal R$ of the entire graph $G$ extending $\cal R'$. We generalize the characterization of interval graphs by Fulkerson and Gross [Pac. J. Math., 15 (1965)] to extendible partial representations. Using it, we give a linear-time algorithm for partial representation extension based on a reordering problem of PQ-trees.
A Lower Bound for the Fisher Information Measure
Venue: arXiv cs.IT 2014
Year: 2014

The problem how to approximately determine the absolute value of the Fisher information measure for a general parametric probabilistic system is considered. Having available the first and second moment of the system output in a parametric form, it is shown that the information measure can be bounded from below through a replacement of the original system by a Gaussian system with equivalent moments. The presented technique is applied to a system of practical importance and the potential quality of the bound is demonstrated.
Relaxed Sparse Eigenvalue Conditions for Sparse Estimation via Non-convex Regularized Regression
Venue: arXiv cs.LG 2014
Year: 2014

Non-convex regularizers usually improve the performance of sparse estimation in practice. To prove this fact, we study the conditions of sparse estimations for the sharp concave regularizers which are a general family of non-convex regularizers including many existing regularizers. For the global solutions of the regularized regression, our sparse eigenvalue based conditions are weaker than that of L1-regularization for parameter estimation and sparseness estimation. For the approximate global and approximate stationary (AGAS) solutions, almost the same conditions are also enough. We show that the desired AGAS solutions can be obtained by coordinate descent (CD) based methods. Finally, we perform some experiments to show the performance of CD methods on giving AGAS solutions and the degree of weakness of the estimation conditions required by the sharp concave regularizers.
Local Convergence of an Algorithm for Subspace Identification from Partial Data
Venue: arXiv cs.NA 2014
Year: 2014

GROUSE (Grassmannian Rank-One Update Subspace Estimation) is an iterative algorithm for identifying a linear subspace of R^n from data consisting of partial observations of random vectors from that subspace. This paper examines local convergence properties of GROUSE, under assumptions on the randomness of the observed vectors, the randomness of the subset of elements observed at each iteration, and incoherence of the subspace with the coordinate directions. Convergence at an expected linear rate is demonstrated under certain assumptions. The case in which the full random vector is revealed at each iteration allows for much simpler analysis, and is also described. GROUSE is related to incremental SVD methods and to gradient projection algorithms in optimization.
The Size-Change Termination Principle for Constructor Based Languages
Venue: arXiv cs.LO 2014
Year: 2014

This paper describes an automatic termination checker for a generic first-order call-by-value language in ML style. We use the fact that value are built from variants and tuples to keep some information about how arguments of recursive call evolve during evaluation. The result is a criterion for termination extending the size-change termination principle of Lee, Jones and Ben-Amram that can detect size changes inside subvalues of arguments. Moreover the corresponding algorithm is easy to implement, making it a good candidate for experimentation.
On-line PCA with Optimal Regrets
Venue: arXiv cs.LG 2014
Year: 2014

We carefully investigate the on-line version of PCA, where in each trial a learning algorithm plays a k-dimensional subspace, and suffers the compression loss on the next instance when projected into the chosen subspace. In this setting, we analyze two popular on-line algorithms, Gradient Descent (GD) and Exponentiated Gradient (EG). We show that both algorithms are essentially optimal in the worst-case. This comes as a surprise, since EG is known to perform sub-optimally when the instances are sparse. This different behavior of EG for PCA is mainly related to the non-negativity of the loss in this case, which makes the PCA setting qualitatively different from other settings studied in the literature. Furthermore, we show that when considering regret bounds as function of a loss budget, EG remains optimal and strictly outperforms GD. Next, we study the extension of the PCA setting, in which the Nature is allowed to play with dense instances, which are positive matrices with bounded largest eigenvalue. Again we can show that EG is optimal and strictly better than GD in this setting.
Finite Element Based Tracking of Deforming Surfaces
Venue: arXiv cs.CV 2014
Year: 2014

We present an approach to robustly track the geometry of an object that deforms over time from a set of input point clouds captured from a single viewpoint. The deformations we consider are caused by applying forces to known locations on the object's surface. Our method combines the use of prior information on the geometry of the object modeled by a smooth template and the use of a linear finite element method to predict the deformation. This allows the accurate reconstruction of both the observed and the unobserved sides of the object. We present tracking results for noisy low-quality point clouds acquired by either a stereo camera or a depth camera, and simulations with point clouds corrupted by different error terms. We show that our method is also applicable to large non-linear deformations.
An Effect System for Algebraic Effects and Handlers
Venue: arXiv cs.PL 2014
Year: 2014

We present an effect system for core Eff, a simplified variant of Eff, which is an ML-style programming language with first-class algebraic effects and handlers. We define an expressive effect system and prove safety of operational semantics with respect to it. Then we give a domain-theoretic denotational semantics of core Eff, using Pitts's theory of minimal invariant relations, and prove it adequate. We use this fact to develop tools for finding useful contextual equivalences, including an induction principle. To demonstrate their usefulness, we use these tools to derive the usual equations for mutable state, including a general commutativity law for computations using non-interfering references. We have formalized the effect system, the operational semantics, and the safety theorem in Twelf.
Query Complexity of Approximate Nash Equilibria
Venue: arXiv cs.GT 2014
Year: 2014

We study the query complexity of approximate notions of Nash equilibrium in games with a large number of players $n$. Our main result states that for $n$-player binary-action games and for constant $\varepsilon$, the query complexity of an $\varepsilon$-well-supported Nash equilibrium is exponential in $n$. One of the consequences of this result is an exponential lower bound on the rate of convergence of adaptive dynamics to approxiamte Nash equilibrium.
Movers and Shakers: Kinetic Energy Harvesting for the Internet of Things
Venue: arXiv cs.ET 2014
Year: 2014

Numerous energy harvesting wireless devices that will serve as building blocks for the Internet of Things (IoT) are currently under development. However, there is still only limited understanding of the properties of various energy sources and their impact on energy harvesting adaptive algorithms. Hence, we focus on characterizing the kinetic (motion) energy that can be harvested by a wireless node with an IoT form factor and on developing energy allocation algorithms for such nodes. In this paper, we describe methods for estimating harvested energy from acceleration traces. To characterize the energy availability associated with specific human activities (e.g., relaxing, walking, cycling), we analyze a motion dataset with over 40 participants. Based on acceleration measurements that we collected for over 200 hours, we study energy generation processes associated with day-long human routines. We also briefly summarize our experiments with moving objects. We develop energy allocation algorithms that take into account practical IoT node design considerations, and evaluate the algorithms using the collected measurements. Our observations provide insights into the design of motion energy harvesters, IoT nodes, and energy harvesting adaptive algorithms.
Achievable Degrees of Freedom Region of the MIMO Relay Networks using the Detour Schemes
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we study the degrees of freedom (DoF) of the MIMO relay networks. We start with a general Y channel, where each user has $M_i$ antennas and aims to exchange messages with the other two users via a relay equipped with $N$ antennas. Then, we extend our work to a general 4-user MIMO relay network. Unlike most previous work which focused on the total DoF of the network, our aim here is to characterize the achievable DoF region as well. We develop an outer bound on the DoF region based on the notion of one sided genie. Then, we define a new achievable region using the Signal Space Alignment (SSA) and the Detour Schemes. Our achievable scheme achieves the upper bound for certain conditions relating $M_i$'s and $N$.
Resolution Proof Transformation for Compression and Interpolation
Venue: arXiv cs.LO 2014
Year: 2014

Verification methods based on SAT, SMT, and Theorem Proving often rely on proofs of unsatisfiability as a powerful tool to extract information in order to reduce the overall effort. For example a proof may be traversed to identify a minimal reason that led to unsatisfiability, for computing abstractions, or for deriving Craig interpolants. In this paper we focus on two important aspects that concern efficient handling of proofs of unsatisfiability: compression and manipulation. First of all, since the proof size can be very large in general (exponential in the size of the input problem), it is indeed beneficial to adopt techniques to compress it for further processing. Secondly, proofs can be manipulated as a flexible preprocessing step in preparation for interpolant computation. Both these techniques are implemented in a framework that makes use of local rewriting rules to transform the proofs. We show that a careful use of the rules, combined with existing algorithms, can result in an effective simplification of the original proofs. We have evaluated several heuristics on a wide range of unsatisfiable problems deriving from SAT and SMT test cases.
Approximate the k-Set Packing Problem by Local Improvements
Venue: arXiv cs.DS 2014
Year: 2014

We study algorithms based on local improvements for the $k$-Set Packing problem. The well-known local improvement algorithm by Hurkens and Schrijver has been improved by Sviridenko and Ward from $\frac{k}{2}+ε$ to $\frac{k+2}{3}$, and by Cygan to $\frac{k+1}{3}+ε$ for any $ε>0$. In this paper, we achieve the approximation ratio $\frac{k+1}{3}+ε$ for the $k$-Set Packing problem using a simple polynomial-time algorithm based on the method by Sviridenko and Ward. With the same approximation guarantee, our algorithm runs in time singly exponential in $\frac{1}{ε^2}$, while the running time of Cygan's algorithm is doubly exponential in $\frac{1}ε$. On the other hand, we construct an instance with locality gap $\frac{k+1}{3}$ for any algorithm using local improvements of size $O(n^{1/5})$, here $n$ is the total number of sets. Thus, our approximation guarantee is optimal with respect to results achievable by algorithms based on local improvements.
On the state complexity of semi-quantum finite automata
Venue: arXiv cs.FL 2014
Year: 2014

Some of the most interesting and important results concerning quantum finite automata are those showing that they can recognize certain languages with (much) less resources than corresponding classical finite automata \cite{Amb98,Amb09,AmYa11,Ber05,Fre09,Mer00,Mer01,Mer02,Yak10,ZhgQiu112,Zhg12}. This paper shows three results of such a type that are stronger in some sense than other ones because (a) they deal with models of quantum automata with very little quantumness (so-called semi-quantum one- and two-way automata with one qubit memory only); (b) differences, even comparing with probabilistic classical automata, are bigger than expected; (c) a trade-off between the number of classical and quantum basis states needed is demonstrated in one case and (d) languages (or the promise problem) used to show main results are very simple and often explored ones in automata theory or in communication complexity, with seemingly little structure that could be utilized.
Semantic Context Forests for Learning-Based Knee Cartilage Segmentation in 3D MR Images
Venue: arXiv cs.CV 2014
Year: 2014

The automatic segmentation of human knee cartilage from 3D MR images is a useful yet challenging task due to the thin sheet structure of the cartilage with diffuse boundaries and inhomogeneous intensities. In this paper, we present an iterative multi-class learning method to segment the femoral, tibial and patellar cartilage simultaneously, which effectively exploits the spatial contextual constraints between bone and cartilage, and also between different cartilages. First, based on the fact that the cartilage grows in only certain area of the corresponding bone surface, we extract the distance features of not only to the surface of the bone, but more informatively, to the densely registered anatomical landmarks on the bone surface. Second, we introduce a set of iterative discriminative classifiers that at each iteration, probability comparison features are constructed from the class confidence maps derived by previously learned classifiers. These features automatically embed the semantic context information between different cartilages of interest. Validated on a total of 176 volumes from the Osteoarthritis Initiative (OAI) dataset, the proposed approach demonstrates high robustness and accuracy of segmentation in comparison with existing state-of-the-art MR cartilage segmentation methods.
Exchangeable Equilibria, Part I: Symmetric Bimatrix Games
Venue: arXiv cs.GT 2014
Year: 2014

We introduce the notion of exchangeable equilibria of a symmetric bimatrix game, defined as those correlated equilibria in which players' strategy choices are conditionally independently and identically distributed given some hidden variable. We give several game-theoretic interpretations and a version of the "revelation principle". Geometrically, the set of exchangeable equilibria is convex and lies between the symmetric Nash equilibria and the symmetric correlated equilibria. Exchangeable equilibria can achieve higher expected utility than symmetric Nash equilibria.
Polynomial time approximation schemes for the traveling repairman and other minimum latency problems
Venue: arXiv cs.DS 2014
Year: 2014

We give a polynomial time, $(1+ε)$-approximation algorithm for the traveling repairman problem (TRP) in the Euclidean plane and on weighted trees. This improves on the known quasi-polynomial time approximation schemes for these problems. The algorithm is based on a simple technique that reduces the TRP to what we call the \emph{segmented TSP}. Here, we are given numbers $l_1,\dots,l_K$ and $n_1,\dots,n_K$ and we need to find a path that visits at least $n_h$ points within path distance $l_h$ from the starting point for all $h\in\{1,\dots,K\}$. A solution is $α$-approximate if at least $n_h$ points are visited within distance $αl_h$. It is shown that any algorithm that is $α$-approximate for \emph{every constant} $K$ in some metric space, gives an $α(1+ε)$-approximation for the TRP in the same metric space. Subsequently, approximation schemes are given for this segmented TSP problem in the plane and on weighted trees. The segmented TSP with only one segment ($K=1$) is equivalent to the $k$-TSP for which a $(2+ε)$-approximation is known for a general metric space. Hence, this approach through the segmented TSP gives new impulse for improving on the 3.59-approximation for TRP in a general metric space. A similar reduction applies to many other minimum latency problems. To illustrate the strength of this approach we apply it to the well-studied scheduling problem of minimizing total weighted completion time under precedence constraints, $1|prec|\sum w_{j}C_{j}$, and present a polynomial time approximation scheme for the case of interval order precedence constraints. This improves on the known $3/2$-approximation for this problem. Both approximation schemes apply as well if release dates are added to the problem.
Optimal Primary-Secondary user Cooperation Policies in Cognitive Radio Networks
Venue: arXiv cs.NI 2014
Year: 2014

In cognitive radio networks, secondary users (SUs) may cooperate with the primary user (PU), so that the success probability of PU transmissions are improved, while SUs obtain more transmission opportunities. Thus, SUs have to take intelligent decisions on whether to cooperate or not and with what power level, in order to maximize their throughput subject to average power constraints. Cooperation policies in this framework require the solution of a constrained Markov decision problem with infinite state space. In our work, we restrict attention to the class of stationary policies that take randomized decisions in every time slot based only on spectrum sensing. The proposed class of policies is shown to achieve the same set of SU rates as the more general policies, and enlarge the stability region of PU queue. Moreover, algorithms for the distributed calculation of the set of probabilities used by the proposed class of policies are presented.
A unified sparse matrix data format for efficient general sparse matrix-vector multiply on modern processors with wide SIMD units
Venue: arXiv cs.MS 2014
Year: 2014

Sparse matrix-vector multiplication (spMVM) is the most time-consuming kernel in many numerical algorithms and has been studied extensively on all modern processor and accelerator architectures. However, the optimal sparse matrix data storage format is highly hardware-specific, which could become an obstacle when using heterogeneous systems. Also, it is as yet unclear how the wide single instruction multiple data (SIMD) units in current multi- and many-core processors should be used most efficiently if there is no structure in the sparsity pattern of the matrix. We suggest SELL-C-sigma, a variant of Sliced ELLPACK, as a SIMD-friendly data format which combines long-standing ideas from General Purpose Graphics Processing Units (GPGPUs) and vector computer programming. We discuss the advantages of SELL-C-sigma compared to established formats like Compressed Row Storage (CRS) and ELLPACK and show its suitability on a variety of hardware platforms (Intel Sandy Bridge, Intel Xeon Phi and Nvidia Tesla K20) for a wide range of test matrices from different application areas. Using appropriate performance models we develop deep insight into the data transfer properties of the SELL-C-sigma spMVM kernel. SELL-C-sigma comes with two tuning parameters whose performance impact across the range of test matrices is studied and for which reasonable choices are proposed. This leads to a hardware-independent ("catch-all") sparse matrix format, which achieves very high efficiency for all test matrices across all hardware platforms.