OpenRaiser/Intern-Atlas huggingface dataset:
Variable Earns Profit: Improved Adaptive Channel Estimation using Sparse VSS-NLMS Algorithms
Venue: arXiv cs.IT 2013
Year: 2013

Accurate channel estimation is essential for broadband wireless communications. As wireless channels often exhibit sparse structure, the adaptive sparse channel estimation algorithms based on normalized least mean square (NLMS) have been proposed, e.g., the zero-attracting NLMS (ZA-NLMS) algorithm and reweighted zero-attracting NLMS (RZA-NLMS). In these NLMS-based algorithms, the step size used to iteratively update the channel estimate is a critical parameter to control the estimation accuracy and the convergence speed (so the computational cost). However, invariable step-size (ISS) is usually used in conventional algorithms, which leads to provide performance loss or/and low convergence speed as well as high computational cost. To solve these problems, based on the observation that large step size is preferred for fast convergence while small step size is preferred for accurate estimation, we propose to replace the ISS by variable step size (VSS) in conventional NLMS-based algorithms to improve the adaptive sparse channel estimation in terms of bit error rate (BER) and mean square error (MSE) metrics. The proposed VSS-ZA-NLMS and VSS-RZA-NLMS algorithms adopt VSS, which can be adaptive to the estimation error in each iteration, i.e., large step size is used in the case of large estimation error to accelerate the convergence speed, while small step size is used when the estimation error is small to improve the steady-state estimation accuracy. Simulation results are provided to validate the effectiveness of the proposed scheme.
TOP-SPIN: TOPic discovery via Sparse Principal component INterference
Venue: arXiv cs.CV 2013
Year: 2013

We propose a novel topic discovery algorithm for unlabeled images based on the bag-of-words (BoW) framework. We first extract a dictionary of visual words and subsequently for each image compute a visual word occurrence histogram. We view these histograms as rows of a large matrix from which we extract sparse principal components (PCs). Each PC identifies a sparse combination of visual words which co-occur frequently in some images but seldom appear in others. Each sparse PC corresponds to a topic, and images whose interference with the PC is high belong to that topic, revealing the common parts possessed by the images. We propose to solve the associated sparse PCA problems using an Alternating Maximization (AM) method, which we modify for purpose of efficiently extracting multiple PCs in a deflation scheme. Our approach attacks the maximization problem in sparse PCA directly and is scalable to high-dimensional data. Experiments on automatic topic discovery and category prediction demonstrate encouraging performance of our approach.
Structural Learning for Template-free Protein Folding
Venue: arXiv cs.LG 2013
Year: 2013

The thesis is aimed to solve the template-free protein folding problem by tackling two important components: efficient sampling in vast conformation space, and design of knowledge-based potentials with high accuracy. We have proposed the first-order and second-order CRF-Sampler to sample structures from the continuous local dihedral angles space by modeling the lower and higher order conditional dependency between neighboring dihedral angles given the primary sequence information. A framework combining the Conditional Random Fields and the energy function is introduced to guide the local conformation sampling using long range constraints with the energy function. The relationship between the sequence profile and the local dihedral angle distribution is nonlinear. Hence we proposed the CNF-Folder to model this complex relationship by applying a novel machine learning model Conditional Neural Fields which utilizes the structural graphical model with the neural network. CRF-Samplers and CNF-Folder perform very well in CASP8 and CASP9. Further, a novel pairwise distance statistical potential (EPAD) is designed to capture the dependency of the energy profile on the positions of the interacting amino acids as well as the types of those amino acids, opposing the common assumption that this energy profile depends only on the types of amino acids. EPAD has also been successfully applied in the CASP 10 Free Modeling experiment with CNF-Folder, especially outstanding on some uncommon structured targets.
Implementation and Evaluation of Measurement-Based Admission Control Schemes Within a Converged Networks QoS Management Framework
Venue: arXiv cs.NI 2013
Year: 2013

Policy-based network management (PBNM) paradigms provide an effective tool for end-to-end resource management in converged next generation networks by enabling unified, adaptive and scalable solutions that integrate and co-ordinate diverse resource management mechanisms associated with heterogeneous access technologies. In our project, a PBNM framework for end-to-end QoS management in converged networks is being developed. The framework consists of distributed functional entities managed within a policy-based infrastructure to provide QoS and resource management in converged networks. Within any QoS control framework, an effective admission control scheme is essential for maintaining the QoS of flows present in the network. Measurement based admission control (MBAC) and parameter based admission control (PBAC) are two commonly used approaches. This paper presents the implementation and analysis of various measurement-based admission control schemes developed within a Java-based prototype of our policy-based framework. The evaluation is made with real traffic flows on a Linux-based experimental testbed where the current prototype is deployed. Our results show that unlike with classic MBAC or PBAC only schemes, a hybrid approach that combines both methods can simultaneously result in improved admission control and network utilization efficiency.
Cluster Based Cost Efficient Intrusion Detection System For Manet
Venue: arXiv cs.CR 2013
Year: 2013

Mobile ad-hoc networks are temporary wireless networks. Network resources are abnormally consumed by intruders. Anomaly and signature based techniques are used for intrusion detection. Classification techniques are used in anomaly based techniques. Intrusion detection techniques are used for the network attack detection process. Two types of intrusion detection systems are available. They are anomaly detection and signature based detection model. The anomaly detection model uses the historical transactions with attack labels. The signature database is used in the signature based IDS schemes. The mobile ad-hoc networks are infrastructure less environment. The intrusion detection applications are placed in a set of nodes under the mobile ad-hoc network environment. The nodes are grouped into clusters. The leader nodes are assigned for the clusters. The leader node is assigned for the intrusion detection process. Leader nodes are used to initiate the intrusion detection process. Resource sharing and lifetime management factors are considered in the leader election process. The system optimizes the leader election and intrusion detection process. The system is designed to handle leader election and intrusion detection process. The clustering scheme is optimized with coverage and traffic level. Cost and resource utilization is controlled under the clusters. Node mobility is managed by the system.
Decentralized Dynamics for Finite Opinion Games
Venue: arXiv cs.GT 2013
Year: 2013

Game theory studies situations in which strategic players can modify the state of a given system, due to the absence of a central authority. Solution concepts, such as Nash equilibrium, are defined to predict the outcome of such situations. In multi-player settings, it has been pointed out that to be realistic, a solution concept should be obtainable via processes that are decentralized and reasonably simple. Accordingly we look at the computation of solution concepts by means of decentralized dynamics. These are algorithms in which players move in turns to improve their own utility and the hope is that the system reaches an "equilibrium" quickly. We study these dynamics for the class of opinion games, recently introduced by Bindel et al. [Bindel et al., FOCS2011]. These are games, important in economics and sociology, that model the formation of an opinion in a social network. We study best-response dynamics and show upper and lower bounds on the convergence to Nash equilibria. We also study a noisy version of best-response dynamics, called logit dynamics, and prove a host of results about its convergence rate as the noise in the system varies. To get these results, we use a variety of techniques developed to bound the mixing time of Markov chains, including coupling, spectral characterizations and bottleneck ratio.
Trade-offs Computing Minimum Hub Cover toward Optimized Graph Query Processing
Venue: arXiv cs.DB 2013
Year: 2013

As techniques for graph query processing mature, the need for optimization is increasingly becoming an imperative. Indices are one of the key ingredients toward efficient query processing strategies via cost-based optimization. Due to the apparent absence of a common representation model, it is difficult to make a focused effort toward developing access structures, metrics to evaluate query costs, and choose alternatives. In this context, recent interests in covering-based graph matching appears to be a promising direction of research. In this paper, our goal is to formally introduce a new graph representation model, called Minimum Hub Cover, and demonstrate that this representation offers interesting strategic advantages, facilitates construction of candidate graphs from graph fragments, and helps leverage indices in novel ways for query optimization. However, similar to other covering problems, minimum hub cover is NP-hard, and thus is a natural candidate for optimization. We claim that computing the minimum hub cover leads to substantial cost reduction for graph query processing. We present a computational characterization of minimum hub cover based on integer programming to substantiate our claim and investigate its computational cost on various graph types.
A Parallel Simulated Annealing Approach for the Mirrored Traveling Tournament Problem
Venue: arXiv cs.DC 2013
Year: 2013

The Traveling Tournament Problem (TTP) is a benchmark problem in sports scheduling and has been extensively studied in recent years. The Mirrored Traveling Tournament Problem (mTTP) is variation of the TTP that represents certain types of sports scheduling problems where the main objective is to minimize the total distance traveled by all the participating teams. In this paper we test a parallel simulated annealing approach for solving the mTTP using OpenMP on shared memory systems and we found that this approach is superior especially with respect to the number of solution instances that are probed per second. We also see that there is significant speed up of 1.5x - 2.2x in terms of number of solutions explored per unit time.
Ordered Models of the Lambda Calculus
Venue: arXiv cs.LO 2013
Year: 2013

Answering a question by Honsell and Plotkin, we show that there are two equations between lambda terms, the so-called subtractive equations, consistent with lambda calculus but not simultaneously satisfied in any partially ordered model with bottom element. We also relate the subtractive equations to the open problem of the order-incompleteness of lambda calculus, by studying the connection between the notion of absolute unorderability in a specific point and a weaker notion of subtractivity (namely n-subtractivity) for partially ordered algebras. Finally we study the relation between n-subtractivity and relativized separation conditions in topological algebras, obtaining an incompleteness theorem for a general topological semantics of lambda calculus.
Context-aware Dynamic Discovery and Configuration of 'Things' in Smart Environments
Venue: arXiv cs.NI 2013
Year: 2013

The Internet of Things (IoT) is a dynamic global information network consisting of Internet-connected objects, such as RFIDs, sensors, actuators, as well as other instruments and smart appliances that are becoming an integral component of the future Internet. Currently, such Internet-connected objects or `things' outnumber both people and computers connected to the Internet and their population is expected to grow to 50 billion in the next 5 to 10 years. To be able to develop IoT applications, such `things' must become dynamically integrated into emerging information networks supported by architecturally scalable and economically feasible Internet service delivery models, such as cloud computing. Achieving such integration through discovery and configuration of `things' is a challenging task. Towards this end, we propose a Context-Aware Dynamic Discovery of {Things} (CADDOT) model. We have developed a tool SmartLink, that is capable of discovering sensors deployed in a particular location despite their heterogeneity. SmartLink helps to establish the direct communication between sensor hardware and cloud-based IoT middleware platforms. We address the challenge of heterogeneity using a plug in architecture. Our prototype tool is developed on an Android platform. Further, we employ the Global Sensor Network (GSN) as the IoT middleware for the proof of concept validation. The significance of the proposed solution is validated using a test-bed that comprises 52 Arduino-based Libelium sensors.
Semantic Sort: A Supervised Approach to Personalized Semantic Relatedness
Venue: arXiv cs.CL 2013
Year: 2013

We propose and study a novel supervised approach to learning statistical semantic relatedness models from subjectively annotated training examples. The proposed semantic model consists of parameterized co-occurrence statistics associated with textual units of a large background knowledge corpus. We present an efficient algorithm for learning such semantic models from a training sample of relatedness preferences. Our method is corpus independent and can essentially rely on any sufficiently large (unstructured) collection of coherent texts. Moreover, the approach facilitates the fitting of semantic models for specific users or groups of users. We present the results of extensive range of experiments from small to large scale, indicating that the proposed method is effective and competitive with the state-of-the-art.
On Improving the Balance between the Completion Time and Decoding Delay in Instantly Decodable Network Coded Systems
Venue: arXiv cs.IT 2013
Year: 2013

This paper studies the complicated interplay of the completion time (as a measure of throughput) and the decoding delay performance in instantly decodable network coded (IDNC) systems over wireless broadcast erasure channels with memory, and proposes two new algorithms that improve the balance between the completion time and decoding delay of broadcasting a block of packets. We first formulate the IDNC packet selection problem that provides joint control of the completion time and decoding delay as a statistical shortest path (SSP) problem. However, since finding the optimal packet selection policy using the SSP technique is computationally complex, we employ its geometric structure to find some guidelines and use them to propose two heuristic packet selection algorithms that can efficiently improve the balance between the completion time and decoding delay for broadcast erasure channels with a wide range of memory conditions. It is shown that each one of the two proposed algorithms is superior for a specific range of memory conditions. Furthermore, we show that the proposed algorithms achieve an improved fairness in terms of the decoding delay across all receivers.
The Third-Order Term in the Normal Approximation for the AWGN Channel
Venue: arXiv cs.IT 2013
Year: 2013

This paper shows that, under the average error probability formalism, the third-order term in the normal approximation for the additive white Gaussian noise channel with a maximal or equal power constraint is at least $\frac{1}{2} \log n + O(1)$. This matches the upper bound derived by Polyanskiy-Poor-Verdú (2010).
PLOS/Mozilla Scientific Code Review Pilot: Summary of Findings
Venue: arXiv cs.SE 2013
Year: 2013

PLOS and Mozilla conducted a month-long pilot study in which professional developers performed code reviews on software associated with papers published in PLOS Computational Biology. While the developers felt the reviews were limited by (a) lack of familiarity with the domain and (b) lack of two-way contact with authors, the scientists appreciated the reviews, and both sides were enthusiastic about repeating the experiment.
Joint recovery algorithms using difference of innovations for distributed compressed sensing
Venue: arXiv cs.IT 2013
Year: 2013

Distributed compressed sensing is concerned with representing an ensemble of jointly sparse signals using as few linear measurements as possible. Two novel joint reconstruction algorithms for distributed compressed sensing are presented in this paper. These algorithms are based on the idea of using one of the signals as side information; this allows to exploit joint sparsity in a more effective way with respect to existing schemes. They provide gains in reconstruction quality, especially when the nodes acquire few measurements, so that the system is able to operate with fewer measurements than is required by other existing schemes. We show that the algorithms achieve better performance with respect to the state-of-the-art.
Flexible Parallel Algorithms for Big Data Optimization
Venue: arXiv cs.DC 2013
Year: 2013

We propose a decomposition framework for the parallel optimization of the sum of a differentiable function and a (block) separable nonsmooth, convex one. The latter term is typically used to enforce structure in the solution as, for example, in Lasso problems. Our framework is very flexible and includes both fully parallel Jacobi schemes and Gauss-Seidel (Southwell-type) ones, as well as virtually all possibilities in between (e.g., gradient- or Newton-type methods) with only a subset of variables updated at each iteration. Our theoretical convergence results improve on existing ones, and numerical results show that the new method compares favorably to existing algorithms.
Recovery of Sparse Matrices via Matrix Sketching
Venue: arXiv cs.NA 2013
Year: 2013

In this paper, we consider the problem of recovering an unknown sparse matrix X from the matrix sketch Y = AX B^T. The dimension of Y is less than that of X, and A and B are known matrices. This problem can be solved using standard compressive sensing (CS) theory after converting it to vector form using the Kronecker operation. In this case, the measurement matrix assumes a Kronecker product structure. However, as the matrix dimension increases the associated computational complexity makes its use prohibitive. We extend two algorithms, fast iterative shrinkage threshold algorithm (FISTA) and orthogonal matching pursuit (OMP) to solve this problem in matrix form without employing the Kronecker product. While both FISTA and OMP with matrix inputs are shown to be equivalent in performance to their vector counterparts with the Kronecker product, solving them in matrix form is shown to be computationally more efficient. We show that the computational gain achieved by FISTA with matrix inputs over its vector form is more significant compared to that achieved by OMP.
Predictable Feature Analysis
Venue: arXiv cs.LG 2013
Year: 2013

Every organism in an environment, whether biological, robotic or virtual, must be able to predict certain aspects of its environment in order to survive or perform whatever task is intended. It needs a model that is capable of estimating the consequences of possible actions, so that planning, control, and decision-making become feasible. For scientific purposes, such models are usually created in a problem specific manner using differential equations and other techniques from control- and system-theory. In contrast to that, we aim for an unsupervised approach that builds up the desired model in a self-organized fashion. Inspired by Slow Feature Analysis (SFA), our approach is to extract sub-signals from the input, that behave as predictable as possible. These "predictable features" are highly relevant for modeling, because predictability is a desired property of the needed consequence-estimating model by definition. In our approach, we measure predictability with respect to a certain prediction model. We focus here on the solution of the arising optimization problem and present a tractable algorithm based on algebraic methods which we call Predictable Feature Analysis (PFA). We prove that the algorithm finds the globally optimal signal, if this signal can be predicted with low error. To deal with cases where the optimal signal has a significant prediction error, we provide a robust, heuristically motivated variant of the algorithm and verify it empirically. Additionally, we give formal criteria a prediction-model must meet to be suitable for measuring predictability in the PFA setting and also provide a suitable default-model along with a formal proof that it meets these criteria.
Efficiently Computing Edit Distance to Dyck Language
Venue: arXiv cs.DS 2013
Year: 2013

Given a string $σ$ over alphabet $Σ$ and a grammar $G$ defined over the same alphabet, how many minimum number of repairs: insertions, deletions and substitutions are required to map $σ$ into a valid member of $G$ ? We investigate this basic question in this paper for $Dyck(s)$. $Dyck(s)$ is a fundamental context free grammar representing the language of well-balanced parentheses with s different types of parentheses and has played a pivotal role in the development of theory of context free languages. Computing edit distance to $Dyck(s)$ significantly generalizes string edit distance problem and has numerous applications ranging from repairing semi-structured documents such as XML to memory checking, automated compiler optimization, natural language processing etc. In this paper we give the first near-linear time algorithm for edit distance computation to $Dyck(s)$ that achieves a nontrivial approximation factor of $O(\frac{1}ε\log{OPT}(\log{n})^{\frac{1}ε})$ in $O(n^{1+ε}\log{n})$ time. In fact, given there exists an algorithm for computing string edit distance on input of size $n$ in $α(n)$ time with $β(n)$-approximation factor, we can devise an algorithm for edit distance problem to $Dyck(s)$ running in $\tilde{O}(n^{1+ε}+α(n))$ and achieving an approximation factor of $O(\frac{1}εβ(n)\log{OPT})$. We show that the framework for efficiently approximating edit distance to $Dyck(s)$ can be applied to many other languages. We illustrate this by considering various memory checking languages which comprise of valid transcripts of stacks, queues, priority queues, double-ended queues etc. Therefore, any language that can be recognized by these data structures, can also be repaired efficiently by our algorithm.
Self-Dual codes from $(-1,1)$-matrices of skew symmetric type
Venue: arXiv cs.IT 2013
Year: 2013

Previously, self-dual codes have been constructed from weighing matrices, and in particular from conference matrices (skew and symmetric). In this paper, codes constructed from matrices of skew symmetric type whose determinants reach the Ehlich-Wojtas' bound are presented. A necessary and sufficient condition for these codes to be self-dual is given, and examples are provided for lengths up to 52.
Quantum Stabilizer Codes from Maximal Curves
Venue: arXiv cs.IT 2013
Year: 2013

A curve attaining the Hasse-Weil bound is called a maximal curve. Usually classical error-correcting codes obtained from a maximal curve have good parameters. However, the quantum stabilizer codes obtained from such classical error-correcting codes via Euclidean or Hermitian self-orthogonality do not always possess good parameters. In this paper, the Hermitian self-orthogonality of algebraic geometry codes obtained from two maximal curves is investigated. It turns out that the stabilizer quantum codes produced from such Hermitian self-orthogonal classical codes have good parameters.