OpenRaiser/Intern-Atlas huggingface dataset:
Sparsity-aware sphere decoding: Algorithms and complexity analysis
Venue: arXiv cs.IT 2014
Year: 2014

Integer least-squares problems, concerned with solving a system of equations where the components of the unknown vector are integer-valued, arise in a wide range of applications. In many scenarios the unknown vector is sparse, i.e., a large fraction of its entries are zero. Examples include applications in wireless communications, digital fingerprinting, and array-comparative genomic hybridization systems. Sphere decoding, commonly used for solving integer least-squares problems, can utilize the knowledge about sparsity of the unknown vector to perform computationally efficient search for the solution. In this paper, we formulate and analyze the sparsity-aware sphere decoding algorithm that imposes $\ell_0$-norm constraint on the admissible solution. Analytical expressions for the expected complexity of the algorithm for alphabets typical of sparse channel estimation and source allocation applications are derived and validated through extensive simulations. The results demonstrate superior performance and speed of sparsity-aware sphere decoder compared to the conventional sparsity-unaware sphere decoding algorithm. Moreover, variance of the complexity of the sparsity-aware sphere decoding algorithm for binary alphabets is derived. The search space of the proposed algorithm can be further reduced by imposing lower bounds on the value of the objective function. The algorithm is modified to allow for such a lower bounding technique and simulations illustrating efficacy of the method are presented. Performance of the algorithm is demonstrated in an application to sparse channel estimation, where it is shown that sparsity-aware sphere decoder performs close to theoretical lower limits.
Towards a Multi-criteria Development Distribution Model: An Analysis of Existing Task Distribution Approaches
Venue: arXiv cs.SE 2014
Year: 2014

Distributing development tasks in the context of global software development bears both many risks and many opportunities. Nowadays, distributed development is often driven by only a few factors or even just a single factor such as workforce costs. Risks and other relevant factors such as workforce capabilities, the innovation potential of different regions, or cultural factors are often not recognized sufficiently. This could be improved by using empirically-based multi-criteria distribution models. Currently, there is a lack of such decision models for distributing software development work. This article focuses on mechanisms for such decision support. First, requirements for a distribution model are formulated based on needs identified from practice. Then, distribution models from different domains are surveyed, compared, and analyzed in terms of suitability. Finally, research questions and directions for future work are given.
Determination of subject-specific muscle fatigue rates under static fatiguing operations
Venue: arXiv cs.RO 2014
Year: 2014

Cumulative local muscle fatigue may lead to potential musculoskeletal disorder (MSD) risks {\color{red}, and subject-specific muscle fatigability needs to be considered to reduce potential MSD risks.} This study was conducted to determine local muscle fatigue rate at shoulder joint level based on an exponential function derived from a muscle fatigue model. Forty male subjects participated in a fatiguing operation under a static posture with a range of relative force levels (14% - 33%). Remaining maximum muscle strengths were measured after different fatiguing sessions. The time course of strength decline was fitted to the exponential function. Subject-specific fatigue rates of shoulder joint moment strength were determined. Good correspondence ($R^2>0.8$) was found in the regression of the majority (35 out of 40 subjects). Substantial inter-individual variability in fatigue rate was found and discussed.
Analysis of a heterogeneous social network of humans and cultural objects
Venue: arXiv cs.SI 2014
Year: 2014

Modern online social platforms enable their members to be involved in a broad range of activities like getting friends, joining groups, posting/commenting resources and so on. In this paper we investigate whether a correlation emerges across the different activities a user can take part in. To perform our analysis we focused on aNobii, a social platform with a world-wide user base of book readers, who like to post their readings, give ratings, review books and discuss them with friends and fellow readers. aNobii presents a heterogeneous structure: i) part social network, with user-to-user interactions, ii) part interest network, with the management of book collections, and iii) part folksonomy, with books that are tagged by the users. We analyzed a complete and anonymized snapshot of aNobii and we focused on three specific activities a user can perform, namely her tagging behavior, her tendency to join groups and her aptitude to compile a wishlist reporting the books she is planning to read. In this way each user is associated with a tag-based, a group-based and a wishlist-based profile. Experimental analysis carried out by means of Information Theory tools like entropy and mutual information suggests that tag-based and group-based profiles are in general more informative than wishlist-based ones. Furthermore, we discover that the degree of correlation between the three profiles associated with the same user tend to be small. Hence, user profiling cannot be reduced to considering just any one type of user activity (although important) but it is crucial to incorporate multiple dimensions to effectively describe users preferences and behavior.
Binary Excess Risk for Smooth Convex Surrogates
Venue: arXiv cs.LG 2014
Year: 2014

In statistical learning theory, convex surrogates of the 0-1 loss are highly preferred because of the computational and theoretical virtues that convexity brings in. This is of more importance if we consider smooth surrogates as witnessed by the fact that the smoothness is further beneficial both computationally- by attaining an {\it optimal} convergence rate for optimization, and in a statistical sense- by providing an improved {\it optimistic} rate for generalization bound. In this paper we investigate the smoothness property from the viewpoint of statistical consistency and show how it affects the binary excess risk. We show that in contrast to optimization and generalization errors that favor the choice of smooth surrogate loss, the smoothness of loss function may degrade the binary excess risk. Motivated by this negative result, we provide a unified analysis that integrates optimization error, generalization bound, and the error in translating convex excess risk into a binary excess risk when examining the impact of smoothness on the binary excess risk. We show that under favorable conditions appropriate choice of smooth convex loss will result in a binary excess risk that is better than $O(1/\sqrt{n})$.
Periodic Behaviors in Constrained Multi-agent Systems
Venue: arXiv cs.SY 2014
Year: 2014

In this paper, we provide two discrete-time multi-agent models which generate periodic behaviors. The first one is a multi-agent system of identical double integrators with input saturation constraints, while the other one is a multi-agent system of identical neutrally stable system with input saturation constraints. In each case, we show that if the feedback gain parameters of the local controller satisfy a certain condition, the multi-agent system exhibits a periodic solution.
Correlated Orienteering Problem and it Application to Persistent Monitoring Tasks
Venue: arXiv cs.RO 2014
Year: 2014

We propose a novel non-linear extension to the Orienteering Problem (OP), called the Correlated Orienteering Problem (COP). We use COP to model the planning of informative tours for the persistent monitoring of a spatiotemporal field with time-invariant spatial correlations, in which the tours are constrained to have limited length. Our focus in this paper is QCOP a quadratic COP formulation that only looks at correlations between neighboring nodes in a node network. The main feature of QCOP is a quadratic utility function capturing the said spatial correlation. QCOP may be solved using mixed integer quadratic programming (MIQP), with the resulting anytime algorithm capable of planning multiple disjoint tours that maximize the quadratic utility. In particular, our algorithm can quickly plan a near-optimal tour over a network with up to $150$ nodes. Besides performing extensive simulation studies to verify the algorithm's correctness and characterize its performance, we also successfully applied it to two realistic persistent monitoring tasks: (i) estimation over a synthetic spatiotemporal field, and (ii) estimating the temperature distribution in the state of Massachusetts.
Direct Processing of Run Length Compressed Document Image for Segmentation and Characterization of a Specified Block
Venue: arXiv cs.CV 2014
Year: 2014

Extracting a block of interest referred to as segmenting a specified block in an image and studying its characteristics is of general research interest, and could be a challenging if such a segmentation task has to be carried out directly in a compressed image. This is the objective of the present research work. The proposal is to evolve a method which would segment and extract a specified block, and carry out its characterization without decompressing a compressed image, for two major reasons that most of the image archives contain images in compressed format and decompressing an image indents additional computing time and space. Specifically in this research work, the proposal is to work on run-length compressed document images.
Dictionary learning for fast classification based on soft-thresholding
Venue: arXiv cs.CV 2014
Year: 2014

Classifiers based on sparse representations have recently been shown to provide excellent results in many visual recognition and classification tasks. However, the high cost of computing sparse representations at test time is a major obstacle that limits the applicability of these methods in large-scale problems, or in scenarios where computational power is restricted. We consider in this paper a simple yet efficient alternative to sparse coding for feature extraction. We study a classification scheme that applies the soft-thresholding nonlinear mapping in a dictionary, followed by a linear classifier. A novel supervised dictionary learning algorithm tailored for this low complexity classification architecture is proposed. The dictionary learning problem, which jointly learns the dictionary and linear classifier, is cast as a difference of convex (DC) program and solved efficiently with an iterative DC solver. We conduct experiments on several datasets, and show that our learning algorithm that leverages the structure of the classification problem outperforms generic learning procedures. Our simple classifier based on soft-thresholding also competes with the recent sparse coding classifiers, when the dictionary is learned appropriately. The adopted classification scheme further requires less computational time at the testing stage, compared to other classifiers. The proposed scheme shows the potential of the adequately trained soft-thresholding mapping for classification and paves the way towards the development of very efficient classification methods for vision problems.
Euler/X: A Toolkit for Logic-based Taxonomy Integration
Venue: arXiv cs.LO 2014
Year: 2014

We introduce Euler/X, a toolkit for logic-based taxonomy integration. Given two taxonomies and a set of alignment constraints between them, Euler/X provides tools for detecting, explaining, and reconciling inconsistencies; finding all possible merges between (consistent) taxonomies; and visualizing merge results. Euler/X employs a number of different underlying reasoning systems, including first-order reasoners (Prover9 and Mace4), answer set programming (DLV and Potassco), and RCC reasoners (PyRCC8). We demonstrate the features of Euler/X and provide experimental results showing its feasibility on various synthetic and real-world examples.
Ad Hoc Networking With Cost-Effective Infrastructure: Generalized Capacity Scaling
Venue: arXiv cs.IT 2014
Year: 2014

Capacity scaling of a large hybrid network with unit node density, consisting of $n$ wireless ad hoc nodes, base stations (BSs) equipped with multiple antennas, and one remote central processor (RCP), is analyzed when wired backhaul links between the BSs and the RCP are rate-limited. We deal with a general scenario where the number of BSs, the number of antennas at each BS, and the backhaul link rate can scale at arbitrary rates relative to $n$ (i.e., we introduce three scaling parameters). We first derive the minimum backhaul link rate required to achieve the same capacity scaling law as in the infinite-capacity backhaul link case. Assuming an arbitrary rate scaling of each backhaul link, a generalized achievable throughput scaling law is then analyzed in the network based on using one of pure multihop, hierarchical cooperation, and two infrastructure-supported routing protocols, and moreover, three-dimensional information-theoretic operating regimes are explicitly identified according to the three scaling parameters. In particular, we show the case where our network having a power limitation is also fundamentally in the degrees-of-freedom- or infrastructure-limited regime, or both. In addition, a generalized cut-set upper bound under the network model is derived by cutting not only the wireless connections but also the wired connections. It is shown that our upper bound matches the achievable throughput scaling even under realistic network conditions such that each backhaul link rate scales slower than the aforementioned minimum-required backhaul link rate.
Key parameters generation of the navigation data of GPS Simulator
Venue: arXiv cs.IT 2014
Year: 2014

The development of the GPS (Global Positioning System) signal simulator involving to a number of key technologies, in which the generation of navigation message has important significance. Based on analysis of the structure of GPS navigation data, the paper researches the production of telemetry word and handover word, parity check code, time parameters and star clock. Using disturbing force equation and Lagrange planetary motion equation extrapolate ephemeris parameters whose feasibility is verified through the Matlab software finally.
PTIME Computation of Transitive Closures of Octagonal Relations
Venue: arXiv cs.LO 2014
Year: 2014

Computing transitive closures of integer relations is the key to finding precise invariants of integer programs. In this paper, we study difference bounds and octagonal relations and prove that their transitive closure is a PTIME-computable formula in the existential fragment of Presburger arithmetic. This result marks a significant complexity improvement, as the known algorithms have EXPTIME worst case complexity.
Ubiquitous Smart Home System Using Android Application
Venue: arXiv cs.CY 2014
Year: 2014

This paper presents a flexible standalone, low-cost smart home system, which is based on the Android app communicating with the micro-web server providing more than the switching functionalities. The Arduino Ethernet is used to eliminate the use of a personal computer (PC) keeping the cost of the overall system to a minimum while voice activation is incorporated for switching functionalities. Devices such as light switches, power plugs, temperature sensors, humidity sensors, current sensors, intrusion detection sensors, smoke/gas sensors and sirens have been integrated in the system to demonstrate the feasibility and effectiveness of the proposed smart home system. The smart home app is tested and it is able to successfully perform the smart home operations such as switching functionalities, automatic environmental control and intrusion detection, in the later case where an email is generated and the siren goes on.
A Framework for Enhancing Performance and Handling Run-Time Uncertainty in Self-Adaptive Systems
Venue: arXiv cs.SE 2014
Year: 2014

Self-adaptivity allows software systems to autonomously adjust their behavior during run-time to reduce the cost complexities caused by manual maintenance. In this paper, a framework for building an external adaptation engine for self-adaptive software systems is proposed. In order to improve the quality of self-adaptive software systems, this research addresses two challenges in self-adaptive software systems. The first challenge is to provide better performance of the adaptation engine by managing the complexity of the adaptation space efficiently and the second challenge is handling run-time uncertainty that hinders the adaptation process. This research utilizes Case-based Reasoning as an adaptation engine along with utility functions for realizing the managed system's requirements.
Handwritten Character Recognition In Malayalam Scripts- A Review
Venue: arXiv cs.CV 2014
Year: 2014

Handwritten character recognition is one of the most challenging and ongoing areas of research in the field of pattern recognition. HCR research is matured for foreign languages like Chinese and Japanese but the problem is much more complex for Indian languages. The problem becomes even more complicated for South Indian languages due to its large character set and the presence of vowels modifiers and compound characters. This paper provides an overview of important contributions and advances in offline as well as online handwritten character recognition of Malayalam scripts.
Surfaces Representation with Sharp Features Using Sqrt(3) and Loop Subdivision Schemes
Venue: arXiv cs.CG 2014
Year: 2014

This paper presents a hybrid algorithm that combines features form both Sqrt(3) and Loop Subdivision schemes. The algorithm aims at preserving sharp features and trim regions, during the surfaces subdivision, using a set of rules. The implementation is nontrivial due to the computational, topological, and smoothness constraints, which should be satisfied by the underlying surface. The fundamental innovation, in this research work, is the ability to preserve sharp features anywhere on a surface. In addition, the resulting representation remains within the multiresolution subdivision framework. Preserving the original representation has a core advantage that all the applicable operations to the multiresolution subdivision surfaces can subsequently be applied to the edited model. Experimental results, including surfaces coarsening and smoothing, were performed using the proposed algorithm for validation purposes, and the results revealed that the proposed algorithm outperforms the other recent state of the art algorithms.
Virtual Backbone Trees for Most Minimal Energy Consumption and Increasing Network Lifetime In WSNs
Venue: arXiv cs.NI 2014
Year: 2014

Virtual backbone trees have been used for efficient communication between sink node and any other node in the deployed area. But all the proposed virtual backbone trees are not fully energy efficient and EVBTs have few flaws associated with them. In this paper two such virtual backbones are proposed. The motive behind the first algorithm, Most Minimal Energy Virtual Backbone Tree (MMEVBT), is to minimise the energy consumption when packets are transmitted between sink and a target sensor node. The energy consumption is most minimal and optimal and it is shown why it always has minimal energy consumption during any transfer of packet between every node with the sink node. For every node, route path with most minimal energy consumption is identified and a new tree node is elected only when a better minimal energy consumption route is identified for a node to communicate with the sink and vice versa. By moving sink periodically it is ensured the battery of the nodes near sink is not completely drained out. Another backbone construction algorithm is proposed which maximises the network lifetime by increasing the lifetime of all tree nodes. Simulations are done in NS2 to practically test the algorithms and the results are discussed in detail.
Split Architecture for Large Scale Wide Area Networks
Venue: arXiv cs.NI 2014
Year: 2014

This report defines a carrier-grade split architecture based on requirements identified during the SPARC project. It presents the SplitArchitecture proposal, the SPARC concept for Software Defined Networking (SDN) introduced for large-scale wide area networks such as access/aggregation networks, and evaluates technical issues against architectural trade-offs. First we present the control and management architecture of the proposed SplitArchitecture. Here, we discuss a recursive control architecture consisting of hierarchically stacked control planes and provide initial considerations regarding network management integration to SDN in general and SplitArchitecture in particular. Next, OpenFlow extensions to support the carrier-grade SplitArchitecture are discussed. These are: a) Openness & Extensibility; b) Virtualization; c) OAM; d) Resiliency approaches; e) Bootstrapping and topology discovery; f) Service creation; g) Energy-efficient networking; h) QoS aspects; and i) Multilayer aspects. In addition, we discuss selected deployment and adoption scenarios faced by modern operator networks, such as service creation scenarios and peering aspects, i.e., how to interconnect with legacy networks. Finally, we indicate how our SplitArchitecture approach meets carrier grade scalability requirements in access/aggregation network scenarios
Coordination Avoidance in Database Systems (Extended Version)
Venue: arXiv cs.DB 2014
Year: 2014

Minimizing coordination, or blocking communication between concurrently executing operations, is key to maximizing scalability, availability, and high performance in database systems. However, uninhibited coordination-free execution can compromise application correctness, or consistency. When is coordination necessary for correctness? The classic use of serializable transactions is sufficient to maintain correctness but is not necessary for all applications, sacrificing potential scalability. In this paper, we develop a formal framework, invariant confluence, that determines whether an application requires coordination for correct execution. By operating on application-level invariants over database states (e.g., integrity constraints), invariant confluence analysis provides a necessary and sufficient condition for safe, coordination-free execution. When programmers specify their application invariants, this analysis allows databases to coordinate only when anomalies that might violate invariants are possible. We analyze the invariant confluence of common invariants and operations from real-world database systems (i.e., integrity constraints) and applications and show that many are invariant confluent and therefore achievable without coordination. We apply these results to a proof-of-concept coordination-avoiding database prototype and demonstrate sizable performance gains compared to serializable execution, notably a 25-fold improvement over prior TPC-C New-Order performance on a 200 server cluster.
Information-theoretically Optimal Sparse PCA
Venue: arXiv cs.IT 2014
Year: 2014

Sparse Principal Component Analysis (PCA) is a dimensionality reduction technique wherein one seeks a low-rank representation of a data matrix with additional sparsity constraints on the obtained representation. We consider two probabilistic formulations of sparse PCA: a spiked Wigner and spiked Wishart (or spiked covariance) model. We analyze an Approximate Message Passing (AMP) algorithm to estimate the underlying signal and show, in the high dimensional limit, that the AMP estimates are information-theoretically optimal. As an immediate corollary, our results demonstrate that the posterior expectation of the underlying signal, which is often intractable to compute, can be obtained using a polynomial-time scheme. Our results also effectively provide a single-letter characterization of the sparse PCA problem.