OpenRaiser/Intern-Atlas huggingface dataset:
Missile Acceleration Controller Design using PI and Time-Delay Adaptive Feedback Linearization Methodology
Venue: arXiv cs.SY 2013
Year: 2013

A straight forward application of feedback linearization to the missile autopilot design for acceleration control may be limited due to the nonminimum characteristics and the model uncertainties. As a remedy, this paper presents a cascade structure of an acceleration controller based on approximate feedback linearization methodology with a time-delay adaptation scheme. The inner loop controller is constructed by applying feedback linearization to the approximate system which is a minimum phase system and provides the desired acceleration signal caused by the angle-of-attack. This controller is augmented by the time-delay adaptive law and the outer loop PI (proportional-integral) controller in order to adaptively compensate for feedback linearization error because of model uncertainty and in order to track the desired acceleration signal. The performance of the proposed method is examined through numerical simulations. Moreover, the proposed controller is tested by using an intercept scenario in 6DOF nonlinear simulations.
Learning Manifolds with K-Means and K-Flats
Venue: arXiv cs.LG 2013
Year: 2013

We study the problem of estimating a manifold from random samples. In particular, we consider piecewise constant and piecewise linear estimators induced by k-means and k-flats, and analyze their performance. We extend previous results for k-means in two separate directions. First, we provide new results for k-means reconstruction on manifolds and, secondly, we prove reconstruction bounds for higher-order approximation (k-flats), for which no known results were previously available. While the results for k-means are novel, some of the technical tools are well-established in the literature. In the case of k-flats, both the results and the mathematical tools are new.
Explicit tensors of border rank at least 2n-1
Venue: arXiv cs.CC 2013
Year: 2013

For odd n, I write down tensors in C^n\otimes C^n\otimes C^n of border rank 2n-1, showing the non-triviality of the Young-flattening equations of Landsberg-Ottaviani. I also study the border rank of the tensors of Alexeev et. al., showing the tensors their tensors T_{2^k}, despite having rank equal to 2^{k+1}-1, have border rank equal to 2^k, the minimum of any concise tensor. I also study the equations of Griesser.
Two Way Concurrent Buffer System without Deadlock in Various Time Models Using Timed Automata
Venue: arXiv cs.CR 2013
Year: 2013

Two way buffer system is a system that exhibits transfer of data using two buffers concurrently. It includes processes that synchronize to exchange data with each other along with executing certain delays between these synchronizations. In existing Tiny Two Way Buffer System, both generators produce packets in half duplex manner in no time, deterministic time, and non deterministic time. Analysis of the model for above time options leads the model in deadlock. The model can be out of the deadlock if timings in the model is incorporated in alternative fashion. The generators produce packets after a delay of 10 seconds. However, generator one has an initial shift of 5 seconds after which it begins sending a packet every 10 seconds. Hence, initial delay for generator one is 15 seconds and for generator two it is 10 seconds. Due to this initial shift, both generators produce packets alternatively and is deadlock free as the packets do not meet at the same time instant. Moreover, the existing system model is not concurrent and hence takes more time for packet transfer in every iteration. In this paper we have proposed a model of buffer system using an additional dummy buffer for transfer of data packets, we thus checking the model with various time models as no time, deterministic time and non deterministic time. The results of proposed model under above time models are in deadlock. We achieve deadlock free situation by introducing appropriate delay in various buffers of the proposed system, the delay timing is nondeterministic time. The new approach speeds up the transfer of packets, as a result the transfer of data becomes concurrent, deadlock free and hence the model proposed is time efficient. Simulation results shows that the proposed two way buffer system is fully concurrent and time efficient as compared to the existing buffer system.
Bad Communities with High Modularity
Venue: arXiv cs.SI 2013
Year: 2013

In this paper we discuss some problematic aspects of Newman's modularity function QN. Given a graph G, the modularity of G can be written as QN = Qf -Q0, where Qf is the intracluster edge fraction of G and Q0 is the expected intracluster edge fraction of the null model, i.e., a randomly connected graph with same expected degree distribution as G. It follows that the maximization of QN must accomodate two factors pulling in opposite directions: Qf favors a small number of clusters and Q0 favors many balanced (i.e., with approximately equal degrees) clusters. In certain cases the Q0 term can cause overestimation of the true cluster number; this is the opposite of the well-known under estimation effect caused by the "resolution limit" of modularity. We illustrate the overestimation effect by constructing families of graphs with a "natural" community structure which, however, does not maximize modularity. In fact, we prove that we can always find a graph G with a "natural clustering" V of G and another, balanced clustering U of G such that (i) the pair (G; U) has higher modularity than (G; V) and (ii) V and U are arbitrarily different.
On Universal Point Sets for Planar Graphs
Venue: arXiv cs.CG 2013
Year: 2013

A set P of points in R^2 is n-universal, if every planar graph on n vertices admits a plane straight-line embedding on P. Answering a question by Kobourov, we show that there is no n-universal point set of size n, for any n>=15. Conversely, we use a computer program to show that there exist universal point sets for all n<=10 and to enumerate all corresponding order types. Finally, we describe a collection G of 7'393 planar graphs on 35 vertices that do not admit a simultaneous geometric embedding without mapping, that is, no set of 35 points in the plane supports a plane straight-line embedding of all graphs in G.
Evolution and the structure of learning agents
Venue: arXiv cs.AI 2013
Year: 2013

This paper presents the thesis that all learning agents of finite information size are limited by their informational structure in what goals they can efficiently learn to achieve in a complex environment. Evolutionary change is critical for creating the required structure for all learning agents in any complex environment. The thesis implies that there is no efficient universal learning algorithm. An agent can go past the learning limits imposed by its structure only by slow evolutionary change or blind search which in a very complex environment can only give an agent an inefficient universal learning capability that can work only in evolutionary timescales or improbable luck.
Evolution of the Media Web
Venue: arXiv cs.IR 2013
Year: 2013

We present a detailed study of the part of the Web related to media content, i.e., the Media Web. Using publicly available data, we analyze the evolution of incoming and outgoing links from and to media pages. Based on our observations, we propose a new class of models for the appearance of new media content on the Web where different \textit{attractiveness} functions of nodes are possible including ones taken from well-known preferential attachment and fitness models. We analyze these models theoretically and empirically and show which ones realistically predict both the incoming degree distribution and the so-called \textit{recency property} of the Media Web, something that existing models did not do well. Finally we compare these models by estimating the likelihood of the real-world link graph from our data set given each model and obtain that models we introduce are significantly more likely than previously proposed ones. One of the most surprising results is that in the Media Web the probability for a post to be cited is determined, most likely, by its quality rather than by its current popularity.
Detecting and Characterizing Small Dense Bipartite-like Subgraphs by the Bipartiteness Ratio Measure
Venue: arXiv cs.DS 2013
Year: 2013

We study the problem of finding and characterizing subgraphs with small \textit{bipartiteness ratio}. We give a bicriteria approximation algorithm \verb|SwpDB| such that if there exists a subset $S$ of volume at most $k$ and bipartiteness ratio $θ$, then for any $0<ε<1/2$, it finds a set $S'$ of volume at most $2k^{1+ε}$ and bipartiteness ratio at most $4\sqrt{θ/ε}$. By combining a truncation operation, we give a local algorithm \verb|LocDB|, which has asymptotically the same approximation guarantee as the algorithm \verb|SwpDB| on both the volume and bipartiteness ratio of the output set, and runs in time $O(ε^2θ^{-2}k^{1+ε}\ln^3k)$, independent of the size of the graph. Finally, we give a spectral characterization of the small dense bipartite-like subgraphs by using the $k$th \textit{largest} eigenvalue of the Laplacian of the graph.
Automorphism of order 2p in binary self-dual extremal codes of length a multiple of 24
Venue: arXiv cs.IT 2013
Year: 2013

Let C be a binary self-dual code with an automorphism g of order 2p, where p is an odd prime, such that g^p is a fixed point free involution. If C is extremal of length a multiple of 24 all the involutions are fixed point free, except the Golay Code and eventually putative codes of length 120. Connecting module theoretical properties of a self-dual code C with coding theoretical ones of the subcode C(g^p) which consists of the set of fixed points of g^p, we prove that C is a projective F_2<g>-module if and only if a natural projection of C(g^p) is a self-dual code. We then discuss easy to handle criteria to decide if C is projective or not. As an application we consider in the last part extremal self-dual codes of length 120, proving that their automorphism group does not contain elements of order 38 and 58.
Identification of Sparse Linear Operators
Venue: arXiv cs.IT 2013
Year: 2013

We consider the problem of identifying a linear deterministic operator from its response to a given probing signal. For a large class of linear operators, we show that stable identifiability is possible if the total support area of the operator's spreading function satisfies D<=1/2. This result holds for an arbitrary (possibly fragmented) support region of the spreading function, does not impose limitations on the total extent of the support region, and, most importantly, does not require the support region to be known prior to identification. Furthermore, we prove that stable identifiability of almost all operators is possible if D<1. This result is surprising as it says that there is no penalty for not knowing the support region of the spreading function prior to identification. Algorithms that provably recover all operators with D<=1/2, and almost all operators with D<1 are presented.
Closed-set lattice of regular sets based on a serial and transitive relation through matroids
Venue: arXiv cs.AI 2013
Year: 2013

Rough sets are efficient for data pre-processing in data mining. Matroids are based on linear algebra and graph theory, and have a variety of applications in many fields. Both rough sets and matroids are closely related to lattices. For a serial and transitive relation on a universe, the collection of all the regular sets of the generalized rough set is a lattice. In this paper, we use the lattice to construct a matroid and then study relationships between the lattice and the closed-set lattice of the matroid. First, the collection of all the regular sets based on a serial and transitive relation is proved to be a semimodular lattice. Then, a matroid is constructed through the height function of the semimodular lattice. Finally, we propose an approach to obtain all the closed sets of the matroid from the semimodular lattice. Borrowing from matroids, results show that lattice theory provides an interesting view to investigate rough sets.
Smart Charging Technologies for Portable Electronic Devices
Venue: arXiv cs.OH 2013
Year: 2013

In this article we describe our efforts of extending demand-side control concepts to the application in portable electronic devices, such as laptop computers, mobile phones and tablet computers. As these devices feature built-in energy storage (in the form of batteries) and the ability to run complex control routines, they are ideal for the implementation of smart charging concepts. We developed a prototype of a smart laptop charger that controls the charging process depending on the locally measured frequency of the electricity grid. If this technique is incorporated into millions of devices in UK households, this will contribute significantly to the stability of the electricity grid, help to mitigate the power production fluctuations from renewable energy sources and avoid the high cost of building and maintaining conventional power plants as standby reserve.
First-principles multiway spectral partitioning of graphs
Venue: arXiv cs.DS 2013
Year: 2013

We consider the minimum-cut partitioning of a graph into more than two parts using spectral methods. While there exist well-established spectral algorithms for this problem that give good results, they have traditionally not been well motivated. Rather than being derived from first principles by minimizing graph cuts, they are typically presented without direct derivation and then proved after the fact to work. In this paper, we take a contrasting approach in which we start with a matrix formulation of the minimum cut problem and then show, via a relaxed optimization, how it can be mapped onto a spectral embedding defined by the leading eigenvectors of the graph Laplacian. The end result is an algorithm that is similar in spirit to, but different in detail from, previous spectral partitioning approaches. In tests of the algorithm we find that it outperforms previous approaches on certain particularly difficult partitioning problems.
Abelian Repetitions in Sturmian Words
Venue: arXiv cs.FL 2013
Year: 2013

We investigate abelian repetitions in Sturmian words. We exploit a bijection between factors of Sturmian words and subintervals of the unitary segment that allows us to study the periods of abelian repetitions by using classical results of elementary Number Theory. We prove that in any Sturmian word the superior limit of the ratio between the maximal exponent of an abelian repetition of period $m$ and $m$ is a number $\geq\sqrt{5}$, and the equality holds for the Fibonacci infinite word. We further prove that the longest prefix of the Fibonacci infinite word that is an abelian repetition of period $F_j$, $j>1$, has length $F_j(F_{j+1}+F_{j-1} +1)-2$ if $j$ is even or $F_j(F_{j+1}+F_{j-1})-2$ if $j$ is odd. This allows us to give an exact formula for the smallest abelian periods of the Fibonacci finite words. More precisely, we prove that for $j\geq 3$, the Fibonacci word $f_j$ has abelian period equal to $F_n$, where $n = \lfloor{j/2}\rfloor$ if $j = 0, 1, 2\mod{4}$, or $n = 1 + \lfloor{j/2}\rfloor$ if $ j = 3\mod{4}$.
Geocast into the Past: Towards a Privacy-Preserving Spatiotemporal Multicast for Cellular Networks
Venue: arXiv cs.CR 2013
Year: 2013

This article introduces the novel concept of Spatiotemporal Multicast (STM), which is the issue of sending a message to mobile devices that have been residing at a specific area during a certain time span in the past. A wide variety of applications can be envisioned for this concept, including crime investigation, disease control, and social applications. An important aspect of these applications is the need to protect the privacy of its users. In this article, we present an extensive overview of applications and objectives to be fulfilled by an STM service. Furthermore, we propose a first Cluster-based Spatiotemporal Multicast (CSTM) approach and provide a detailed discussion of its privacy features. Finally, we evaluate the performance of our scheme in a large-scale simulation setup.
Orthogononalization on a general purpose graphics processing unit with double double and quad double arithmetic
Venue: arXiv cs.MS 2013
Year: 2013

Our problem is to accurately solve linear systems on a general purpose graphics processing unit with double double and quad double arithmetic. The linear systems originate from the application of Newton's method on polynomial systems. Newton's method is applied as a corrector in a path following method, so the linear systems are solved in sequence and not simultaneously. One solution path may require the solution of thousands of linear systems. In previous work we reported good speedups with our implementation to evaluate and differentiate polynomial systems on the NVIDIA Tesla C2050. Although the cost of evaluation and differentiation often dominates the cost of linear system solving in Newton's method, because of the limited bandwidth of the communication between CPU and GPU, we cannot afford to send the linear system to the CPU for solving during path tracking. Because of large degrees, the Jacobian matrix may contain extreme values, requiring extended precision, leading to a significant overhead. This overhead of multiprecision arithmetic is our main motivation to develop a massively parallel algorithm. To allow overdetermined linear systems we solve linear systems in the least squares sense, computing the QR decomposition of the matrix by the modified Gram-Schmidt algorithm. We describe our implementation of the modified Gram-Schmidt orthogonalization method for the NVIDIA Tesla C2050, using double double and quad double arithmetic. Our experimental results show that the achieved speedups are sufficiently high to compensate for the overhead of one extra level of precision.
Confluence by Decreasing Diagrams -- Formalized
Venue: arXiv cs.LO 2013
Year: 2013

This paper presents a formalization of decreasing diagrams in the theorem prover Isabelle. It discusses mechanical proofs showing that any locally decreasing abstract rewrite system is confluent. The valley and the conversion version of decreasing diagrams are considered.
Learning Human Activities and Object Affordances from RGB-D Videos
Venue: arXiv cs.RO 2013
Year: 2013

Understanding human activities and object affordances are two very important skills, especially for personal robots which operate in human environments. In this work, we consider the problem of extracting a descriptive labeling of the sequence of sub-activities being performed by a human, and more importantly, of their interactions with the objects in the form of associated affordances. Given a RGB-D video, we jointly model the human activities and object affordances as a Markov random field where the nodes represent objects and sub-activities, and the edges represent the relationships between object affordances, their relations with sub-activities, and their evolution over time. We formulate the learning problem using a structural support vector machine (SSVM) approach, where labelings over various alternate temporal segmentations are considered as latent variables. We tested our method on a challenging dataset comprising 120 activity videos collected from 4 subjects, and obtained an accuracy of 79.4% for affordance, 63.4% for sub-activity and 75.0% for high-level activity labeling. We then demonstrate the use of such descriptive labeling in performing assistive tasks by a PR2 robot.
Learning Locality-Constrained Collaborative Representation for Face Recognition
Venue: arXiv cs.CV 2013
Year: 2013

The model of low-dimensional manifold and sparse representation are two well-known concise models that suggest each data can be described by a few characteristics. Manifold learning is usually investigated for dimension reduction by preserving some expected local geometric structures from the original space to a low-dimensional one. The structures are generally determined by using pairwise distance, e.g., Euclidean distance. Alternatively, sparse representation denotes a data point as a linear combination of the points from the same subspace. In practical applications, however, the nearby points in terms of pairwise distance may not belong to the same subspace, and vice versa. Consequently, it is interesting and important to explore how to get a better representation by integrating these two models together. To this end, this paper proposes a novel coding algorithm, called Locality-Constrained Collaborative Representation (LCCR), which improves the robustness and discrimination of data representation by introducing a kind of local consistency. The locality term derives from a biologic observation that the similar inputs have similar code. The objective function of LCCR has an analytical solution, and it does not involve local minima. The empirical studies based on four public facial databases, ORL, AR, Extended Yale B, and Multiple PIE, show that LCCR is promising in recognizing human faces from frontal views with varying expression and illumination, as well as various corruptions and occlusions.
A quantitative method for determining the robustness of complex networks
Venue: arXiv cs.SI 2013
Year: 2013

Most current studies estimate the invulnerability of complex networks using a qualitative method that analyzes the inaccurate decay rate of network efficiency. This method results in confusion over the invulnerability of various types of complex networks. By normalizing network efficiency and defining a baseline, this paper defines the invulnerability index as the integral of the difference between the normalized network efficiency curve and the baseline. This quantitative method seeks to establish a benchmark for the robustness and fragility of networks and to measure network invulnerability under both edge and node attacks. To validate the reliability of the proposed method, three small-world networks were selected as test beds. The simulation results indicate that the proposed invulnerability index can effectively and accurately quantify network resilience. The index should provide a valuable reference for determining network invulnerability in future research.
On the relation of nonanticipative rate distortion function and filtering theory
Venue: arXiv cs.IT 2013
Year: 2013

In this paper the relation between nonanticipative rate distortion function (RDF) and Bayesian filtering theory is investigated using the topology of weak convergence of probability measures on Polish spaces. The relation is established via an optimization on the space of conditional distributions of the so-called directed information subject to fidelity constraints. Existence of the optimal reproduction distribution of the nonanticipative RDF is shown, while the optimal nonanticipative reproduction conditional distribution for stationary processes is derived in closed form. The realization procedure of nonanticipative RDF which is equivalent to joint-source channel matching for symbol-by-symbol transmission is described, while an example is introduced to illustrate the concepts.