OpenRaiser/Intern-Atlas huggingface dataset:
Linearized Alternating Direction Method with Parallel Splitting and Adaptive Penalty for Separable Convex Programs in Machine Learning
Venue: arXiv cs.NA 2014
Year: 2014

Many problems in machine learning and other fields can be (re)for-mulated as linearly constrained separable convex programs. In most of the cases, there are multiple blocks of variables. However, the traditional alternating direction method (ADM) and its linearized version (LADM, obtained by linearizing the quadratic penalty term) are for the two-block case and cannot be naively generalized to solve the multi-block case. So there is great demand on extending the ADM based methods for the multi-block case. In this paper, we propose LADM with parallel splitting and adaptive penalty (LADMPSAP) to solve multi-block separable convex programs efficiently. When all the component objective functions have bounded subgradients, we obtain convergence results that are stronger than those of ADM and LADM, e.g., allowing the penalty parameter to be unbounded and proving the sufficient and necessary conditions} for global convergence. We further propose a simple optimality measure and reveal the convergence rate of LADMPSAP in an ergodic sense. For programs with extra convex set constraints, with refined parameter estimation we devise a practical version of LADMPSAP for faster convergence. Finally, we generalize LADMPSAP to handle programs with more difficult objective functions by linearizing part of the objective function as well. LADMPSAP is particularly suitable for sparse representation and low-rank recovery problems because its subproblems have closed form solutions and the sparsity and low-rankness of the iterates can be preserved during the iteration. It is also highly parallelizable and hence fits for parallel or distributed computing. Numerical experiments testify to the advantages of LADMPSAP in speed and numerical accuracy.
Complexity of Word Collocation Networks: A Preliminary Structural Analysis
Venue: arXiv cs.SI 2014
Year: 2014

In this paper, we explore complex network properties of word collocation networks (Ferret, 2002) from four different genres. Each document of a particular genre was converted into a network of words with word collocations as edges. We analyzed graphically and statistically how the global properties of these networks varied across different genres, and among different network types within the same genre. Our results indicate that the distributions of network properties are visually similar but statistically apart across different genres, and interesting variations emerge when we consider different network types within a single genre. We further investigate how the global properties change as we add more and more collocation edges to the graph of one particular genre, and observe that except for the number of vertices and the size of the largest connected component, network properties change in phases, via jumps and drops.
A Notion of Robustness for Cyber-Physical Systems
Venue: arXiv cs.SY 2014
Year: 2014

Robustness as a system property describes the degree to which a system is able to function correctly in the presence of disturbances, i.e., unforeseen or erroneous inputs. In this paper, we introduce a notion of robustness termed input-output dynamical stability for cyber-physical systems (CPS) which merges existing notions of robustness for continuous systems and discrete systems. The notion captures two intuitive aims of robustness: bounded disturbances have bounded effects and the consequences of a sporadic disturbance disappear over time. We present a design methodology for robust CPS which is based on an abstraction and refinement process. We suggest several novel notions of simulation relations to ensure the soundness of the approach. In addition, we show how such simulation relations can be constructed compositionally. The different concepts and results are illustrated throughout the paper with examples.
Perfect Permutation Codes with the Kendall's $τ$-Metric
Venue: arXiv cs.IT 2014
Year: 2014

The rank modulation scheme has been proposed for efficient writing and storing data in non-volatile memory storage. Error-correction in the rank modulation scheme is done by considering permutation codes. In this paper we consider codes in the set of all permutations on $n$ elements, $S_n$, using the Kendall's $τ$-metric. We prove that there are no perfect single-error-correcting codes in $S_n$, where $n>4$ is a prime or $4\leq n\leq 10$. We also prove that if such a code exists for $n$ which is not a prime then the code should have some uniform structure. We define some variations of the Kendall's $τ$-metric and consider the related codes and specifically we prove the existence of a perfect single-error-correcting code in $S_5$. Finally, we examine the existence problem of diameter perfect codes in $S_n$ and obtain a new upper bound on the size of a code in $S_n$ with even minimum Kendall's $τ$-distance.
Full characterisation of attractors of two intersected asynchronous Boolean automata cycles
Venue: arXiv cs.FL 2014
Year: 2014

The understanding of Boolean automata networks dynamics takes an important place in various domains of computer science such as computability, complexity and discrete dynamical systems. In this paper, we make a step further in this understanding by focusing on their cycles, whose necessity in networks is known as the brick of their complexity. We present new results that provide a characterisation of the transient and asymptotic dynamics, i.e. of the computational abilities, of asynchronous Boolean automata networks composed of two cycles that intersect at one automaton, the so-called double-cycles. To do so, we introduce an efficient formalism inspired by algorithms to define long sequences of updates, that allows a better description of their dynamics than previous works in this area.
A Core Calculus for Provenance
Venue: arXiv cs.PL 2014
Year: 2014

Provenance is an increasing concern due to the ongoing revolution in sharing and processing scientific data on the Web and in other computer systems. It is proposed that many computer systems will need to become provenance-aware in order to provide satisfactory accountability, reproducibility, and trust for scientific or other high-value data. To date, there is not a consensus concerning appropriate formal models or security properties for provenance. In previous work, we introduced a formal framework for provenance security and proposed formal definitions of properties called disclosure and obfuscation. In this article, we study refined notions of positive and negative disclosure and obfuscation in a concrete setting, that of a general-purpose programing language. Previous models of provenance have focused on special-purpose languages such as workflows and database queries. We consider a higher-order, functional language with sums, products, and recursive types and functions, and equip it with a tracing semantics in which traces themselves can be replayed as computations. We present an annotation-propagation framework that supports many provenance views over traces, including standard forms of provenance studied previously. We investigate some relationships among provenance views and develop some partial solutions to the disclosure and obfuscation problems, including correct algorithms for disclosure and positive obfuscation based on trace slicing.
The Frequent Paucity of Trivial Strings
Venue: arXiv cs.CC 2014
Year: 2014

A 1976 theorem of Chaitin can be used to show that arbitrarily dense sets of lengths n have a paucity of trivial strings (only a bounded number of strings of length n having trivially low plain Kolmogorov complexities). We use the probabilistic method to give a new proof of this fact. This proof is much simpler than previously published proofs, and it gives a tighter paucity bound.
DNACloud: A Potential Tool for storing Big Data on DNA
Venue: arXiv cs.ET 2014
Year: 2014

The term Big Data is usually used to describe huge amount of data that is generated by humans from digital media such as cameras, internet, phones, sensors etc. By building advanced analytics on the top of big data, one can predict many things about the user such as behavior, interest etc. However before one can use the data, one has to address many issues for big data storage. Two main issues are the need of large storage devices and the cost associated with it. Synthetic DNA storage seems to be an appropriate solution to address these issues of the big data. Recently in 2013, Goldman and his collegues from European Bioinformatics Institute demonstrated the use of the DNA as storage medium with capacity of storing 2.2 peta bytes of information on one gram of DNA and retrived the data successfully with low error rate. This significant step shows a promise for synthetic DNA storage as a useful technology for the future data storage. Motivated by this, we have developed a software called DNACloud which makes it easy to store the data on the DNA. In this work, we present detailed description of the software.
Unified Subharmonic Oscillation Conditions for Peak or Average Current Mode Control
Venue: arXiv cs.SY 2014
Year: 2014

This paper is an extension of the author's recent research in which only buck converters were analyzed. Similar analysis can be equally applied to other types of converters. In this paper, a unified model is proposed for buck, boost, and buck-boost converters under peak or average current mode control to predict the occurrence of subharmonic oscillation. Based on the unified model, the associated stability conditions are derived in closed forms. The same stability condition can be applied to buck, boost, and buck-boost converters. Based on the closed-form conditions, the effects of various converter parameters including the compensator poles and zeros on the stability can be clearly seen, and these parameters can be consolidated into a few ones. High-order compensators such as type-II and PI compensators are considered. Some new plots are also proposed for design purpose to avoid the instability. The instability is found to be associated with large crossover frequency. A conservative stability condition, agreed with the past research, is derived. The effect of the voltage loop ripple on the instability is also analyzed.
Hierarchical Clustering of Hyperspectral Images using Rank-Two Nonnegative Matrix Factorization
Venue: arXiv cs.CV 2014
Year: 2014

In this paper, we design a hierarchical clustering algorithm for high-resolution hyperspectral images. At the core of the algorithm, a new rank-two nonnegative matrix factorizations (NMF) algorithm is used to split the clusters, which is motivated by convex geometry concepts. The method starts with a single cluster containing all pixels, and, at each step, (i) selects a cluster in such a way that the error at the next step is minimized, and (ii) splits the selected cluster into two disjoint clusters using rank-two NMF in such a way that the clusters are well balanced and stable. The proposed method can also be used as an endmember extraction algorithm in the presence of pure pixels. The effectiveness of this approach is illustrated on several synthetic and real-world hyperspectral images, and shown to outperform standard clustering techniques such as k-means, spherical k-means and standard NMF.
Empirical Distribution of Equilibrium Play and Its Testing Application
Venue: arXiv cs.GT 2014
Year: 2014

We show that in any $n$-player $m$-action normal-form game, we can obtain an approximate equilibrium by sampling any mixed-action equilibrium a small number of times. We study three types of equilibria: Nash, correlated and coarse correlated. For each one of them we obtain upper and lower bounds on the number of samples required for the empirical distribution over the sampled action profiles to form an approximate equilibrium with probability close to one. These bounds imply that using a small number of samples we can test whether or not players are playing according to an approximate equilibrium, even in games where $n$ and $m$ are large. In addition, our results substantially improve previously known upper bounds on the support size of approximate equilibria in games with many players. In particular, for all the three types of equilibria we show the existence of approximate equilibrium with support size polylogarithmic in $n$ and $m$, whereas the previously best-known upper bounds were polynomial in $n$.
User Effects in Beam-Space MIMO
Venue: arXiv cs.IT 2014
Year: 2014

The performance and design of the novel single-RF-chain beam-space MIMO antenna concept is evaluated for the first time in the presence of the user. First, the variations of different performance parameters are evaluated when placing a beam-space MIMO antenna in close proximity to the user body in several typical operating scenarios. In addition to the typical degradation of conventional antennas in terms of radiation efficiency and impedance matching, it is observed that the user body corrupts the power balance and the orthogonality of the beam-space MIMO basis. However, capacity analyses show that throughput reduction mainly stems from the absorption in user body tissues rather than from the power imbalance and the correlation of the basis. These results confirm that the beam-space MIMO concept, so far only demonstrated in the absence of external perturbation, still performs very well in typical human body interaction scenarios.
Effective Data Aggregation Scheme for Large-scale Wireless Sensor Networks
Venue: arXiv cs.NI 2014
Year: 2014

Energy preservation is one of the most important challenges in wireless sensor networks. In most applications, sensor networks consist of hundreds or thousands nodes that are dispersed in a wide field. Hierarchical architectures and data aggregation methods are increasingly gaining more popularity in such large-scale networks. In this paper, we propose a novel adaptive Energy-Efficient Multi-layered Architecture (EEMA) protocol for large-scale sensor networks, wherein both hierarchical architecture and data aggregation are efficiently utilized. EEMA divides the network into some layers as well as each layer into some clusters, where the data are gathered in the first layer and are recursively aggregated in upper layers to reach the base station. Many criteria are wisely employed to elect head nodes, including the residual energy, centrality, and proximity to bottom-layer heads. The routing delay is mathematically analyzed. Performance evaluation is performed via simulations which confirms the effectiveness of the proposed EEMA protocol in terms of the network lifetime and reduced routing delay.
On the Listsize Capacity with Feedback
Venue: arXiv cs.IT 2014
Year: 2014

The listsize capacity of a discrete memoryless channel is the largest transmission rate for which the expectation---or, more generally, the $ρ$-th moment---of the number of messages that could have produced the output of the channel approaches one as the blocklength tends to infinity. We show that for channels with feedback this rate is upper-bounded by the maximum of Gallager's $E_0$ function divided by $ρ$, and that equality holds when the zero-error capacity of the channel is positive. To establish this inequality we prove that feedback does not increase the cutoff rate. Relationships to other notions of channel capacity are explored.
Faster Algorithms For Vertex Partitioning Problems Parameterized by Clique-width
Venue: arXiv cs.DM 2014
Year: 2014

Many NP-hard problems, such as Dominating Set, are FPT parameterized by clique-width. For graphs of clique-width $k$ given with a $k$-expression, Dominating Set can be solved in $4^k n^{O(1)}$ time. However, no FPT algorithm is known for computing an optimal $k$-expression. For a graph of clique-width $k$, if we rely on known algorithms to compute a $(2^{3k}-1)$-expression via rank-width and then solving Dominating Set using the $(2^{3k}-1)$-expression, the above algorithm will only give a runtime of $4^{2^{3k}} n^{O(1)}$. There have been results which overcome this exponential jump; the best known algorithm can solve Dominating Set in time $2^{O(k^2)} n^{O(1)}$ by avoiding constructing a $k$-expression [Bui-Xuan, Telle, and Vatshelle. Fast dynamic programming for locally checkable vertex subset and vertex partitioning problems. Theoret. Comput. Sci., 2013. doi:10.1016/j.tcs.2013.01.009]. We improve this to $2^{O(k\log k)}n^{O(1)}$. Indeed, we show that for a graph of clique-width $k$, a large class of domination and partitioning problems (LC-VSP), including Dominating Set, can be solved in $2^{O(k\log{k})} n^{O(1)}$. Our main tool is a variant of rank-width using the rank of a $0$-$1$ matrix over the rational field instead of the binary field.
The SPARQL2XQuery Interoperability Framework. Utilizing Schema Mapping, Schema Transformation and Query Translation to Integrate XML and the Semantic Web
Venue: arXiv cs.DB 2014
Year: 2014

The Web of Data is an open environment consisting of a great number of large inter-linked RDF datasets from various domains. In this environment, organizations and companies adopt the Linked Data practices utilizing Semantic Web (SW) technologies, in order to publish their data and offer SPARQL endpoints (i.e., SPARQL-based search services). On the other hand, the dominant standard for information exchange in the Web today is XML. The SW and XML worlds and their developed infrastructures are based on different data models, semantics and query languages. Thus, it is crucial to develop interoperability mechanisms that allow the Web of Data users to access XML datasets, using SPARQL, from their own working environments. It is unrealistic to expect that all the existing legacy data (e.g., Relational, XML, etc.) will be transformed into SW data. Therefore, publishing legacy data as Linked Data and providing SPARQL endpoints over them has become a major research challenge. In this direction, we introduce the SPARQL2XQuery Framework which creates an interoperable environment, where SPARQL queries are automatically translated to XQuery queries, in order to access XML data across the Web. The SPARQL2XQuery Framework provides a mapping model for the expression of OWL-RDF/S to XML Schema mappings as well as a method for SPARQL to XQuery translation. To this end, our Framework supports both manual and automatic mapping specification between ontologies and XML Schemas. In the automatic mapping specification scenario, the SPARQL2XQuery exploits the XS2OWL component which transforms XML Schemas into OWL ontologies. Finally, extensive experiments have been conducted in order to evaluate the schema transformation, mapping generation, query translation and query evaluation efficiency, using both real and synthetic datasets.
Dynamic autotuning of adaptive fast multipole methods on hybrid multicore CPU & GPU systems
Venue: arXiv cs.DC 2014
Year: 2014

We discuss an implementation of adaptive fast multipole methods targeting hybrid multicore CPU- and GPU-systems. From previous experiences with the computational profile of our version of the fast multipole algorithm, suitable parts are off-loaded to the GPU, while the remaining parts are threaded and executed concurrently by the CPU. The parameters defining the algorithm affects the performance and by measuring this effect we are able to dynamically balance the algorithm towards optimal performance. Our setup uses the dynamic nature of the computations and is therefore of general character.
Dynamic Network Formation with Incomplete Information
Venue: arXiv cs.SI 2014
Year: 2014

How do networks form and what is their ultimate topology? Most of the literature that addresses these questions assumes complete information: agents know in advance the value of linking to other agents, even with agents they have never met and with whom they have had no previous interaction (direct or indirect). This paper addresses the same questions under what seems to us to be the much more natural assumption of incomplete information: agents do not know in advance -- but must learn -- the value of linking to agents they have never met. We show that the assumption of incomplete information has profound implications for the process of network formation and the topology of networks that ultimately form. Under complete information, the networks that form and are stable typically have a star, wheel or core-periphery form, with high-value agents in the core. Under incomplete information, the presence of positive externalities (the value of indirect links) implies that a much wider collection of network topologies can emerge and be stable. Moreover, even when the topologies that emerge are the same, the locations of agents can be very different. For instance, when information is incomplete, it is possible for a hub-and-spokes network with a low-value agent in the center to form and endure permanently: an agent can achieve a central position purely as the result of chance rather than as the result of merit. Perhaps even more strikingly: when information is incomplete, a connected network could form and persist even if, when information were complete, no links would ever form, so that the final form would be a totally disconnected network. All of this can occur even in settings where agents eventually learn everything so that information, although initially incomplete, eventually becomes complete.
Topological-collaborative approach for disambiguating authors' names in collaborative networks
Venue: arXiv cs.SI 2014
Year: 2014

Concepts and methods of complex networks have been employed to uncover patterns in a myriad of complex systems. Unfortunately, the relevance and significance of these patterns strongly depends on the reliability of the data sets. In the study of collaboration networks, for instance, unavoidable noise pervading author's collaboration datasets arises when authors share the same name. To address this problem, we derive a hybrid approach based on authors' collaboration patterns and on topological features of collaborative networks. Our results show that the combination of strategies, in most cases, performs better than the traditional approach which disregards topological features. We also show that the main factor for improving the discriminability of homonymous authors is the average distance between authors. Finally, we show that it is possible to predict the weighting associated to each strategy compounding the hybrid system by examining the discrimination obtained from the traditional analysis of collaboration patterns. Once the methodology devised here is generic, our approach is potentially useful to classify many other networked systems governed by complex interactions.
Delay Learning Architectures for Memory and Classification
Venue: arXiv cs.NE 2014
Year: 2014

We present a neuromorphic spiking neural network, the DELTRON, that can remember and store patterns by changing the delays of every connection as opposed to modifying the weights. The advantage of this architecture over traditional weight based ones is simpler hardware implementation without multipliers or digital-analog converters (DACs) as well as being suited to time-based computing. The name is derived due to similarity in the learning rule with an earlier architecture called Tempotron. The DELTRON can remember more patterns than other delay-based networks by modifying a few delays to remember the most 'salient' or synchronous part of every spike pattern. We present simulations of memory capacity and classification ability of the DELTRON for different random spatio-temporal spike patterns. The memory capacity for noisy spike patterns and missing spikes are also shown. Finally, we present SPICE simulation results of the core circuits involved in a reconfigurable mixed signal implementation of this architecture.