OpenRaiser/Intern-Atlas huggingface dataset:
Monitoring voltage collapse margin by measuring the area voltage across several transmission lines with synchrophasors
Venue: arXiv cs.SY 2014
Year: 2014

We consider the fast monitoring of voltage collapse margin using synchrophasor measurements at both ends of transmission lines that transfer power from two generators to two loads. This shows a way to extend the monitoring of a radial transmission line to multiple transmission lines. The synchrophasor voltages are combined into a single complex voltage difference across an area containing the transmission lines that can be monitored in the same way as a single transmission line. We identify ideal conditions under which this reduction to the single line case perfectly preserves the margin to voltage collapse, and give an example that shows that the error under practical non-ideal conditions is reasonably small.
Spatial Throughput Characterization in Cognitive Radio Networks with Threshold-Based Opportunistic Spectrum Access
Venue: arXiv cs.IT 2014
Year: 2014

This paper studies the opportunistic spectrum access (OSA) of the secondary users in a large-scale overlay cognitive radio (CR) network. Two threshold-based OSA schemes, namely the primary receiver assisted (PRA) protocol and the primary transmitter assisted (PTA) protocol, are investigated. Under the PRA/PTA protocol, a secondary transmitter (ST) is allowed to access the spectrum only when the maximum signal power of the received beacons/pilots sent from the active primary receivers/transmitters (PRs/PTs) is lower than a certain threshold. To measure the resulting transmission opportunity for the secondary users by the proposed OSA protocols, the concept of spatial opportunity, which is defined as the probability that an arbitrary location in the primary network is detected as a spatial spectrum hole, is introduced and then evaluated by applying tools from stochastic geometry. Based on spatial opportunity, the coverage (non-outage transmission) performance in the overlay CR network is analyzed. With the obtained results of spatial opportunity and coverage probability, we finally characterize the spatial throughput, which is defined as the average spatial density of successful transmissions in the primary/secondary network, under the PRA and PTA protocols, respectively.
Shortest Unique Substring Query Revisited
Venue: arXiv cs.DS 2014
Year: 2014

We revisit the problem of finding shortest unique substring (SUS) proposed recently by [6]. We propose an optimal $O(n)$ time and space algorithm that can find an SUS for every location of a string of size $n$. Our algorithm significantly improves the $O(n^2)$ time complexity needed by [6]. We also support finding all the SUSes covering every location, whereas the solution in [6] can find only one SUS for every location. Further, our solution is simpler and easier to implement and can also be more space efficient in practice, since we only use the inverse suffix array and longest common prefix array of the string, while the algorithm in [6] uses the suffix tree of the string and other auxiliary data structures. Our theoretical results are validated by an empirical study that shows our algorithm is much faster and more space-saving than the one in [6].
Efficient Random-Walk Methods for Approximating Polytope Volume
Venue: arXiv cs.CG 2014
Year: 2014

We experimentally study the fundamental problem of computing the volume of a convex polytope given as an intersection of linear inequalities. We implement and evaluate practical randomized algorithms for accurately approximating the polytope's volume in high dimensions (e.g. one hundred). To carry out this efficiently we experimentally correlate the effect of parameters, such as random walk length and number of sample points, on accuracy and runtime. Moreover, we exploit the problem's geometry by implementing an iterative rounding procedure, computing partial generations of random points and designing fast polytope boundary oracles. Our publicly available code is significantly faster than exact computation and more accurate than existing approximation methods. We provide volume approximations for the Birkhoff polytopes B_11,...,B_15, whereas exact methods have only computed that of B_10.
Generalized Approximate Message Passing for Cosparse Analysis Compressive Sensing
Venue: arXiv cs.IT 2014
Year: 2014

In cosparse analysis compressive sensing (CS), one seeks to estimate a non-sparse signal vector from noisy sub-Nyquist linear measurements by exploiting the knowledge that a given linear transform of the signal is cosparse, i.e., has sufficiently many zeros. We propose a novel approach to cosparse analysis CS based on the generalized approximate message passing (GAMP) algorithm. Unlike other AMP-based approaches to this problem, ours works with a wide range of analysis operators and regularizers. In addition, we propose a novel $\ell_0$-like soft-thresholder based on MMSE denoising for a spike-and-slab distribution with an infinite-variance slab. Numerical demonstrations on synthetic and practical datasets demonstrate advantages over existing AMP-based, greedy, and reweighted-$\ell_1$ approaches.
Asynchronous Physical-Layer Network Coding with Quasi-Cyclic Codes
Venue: arXiv cs.IT 2014
Year: 2014

Communication in the presence of bounded timing asynchronism which is known to the receiver but cannot be easily compensated is studied. Examples of such situations include point-to-point communication over inter-symbol interference (ISI) channels and asynchronous wireless networks. In these scenarios, although the receiver may know all the delays, it is often not be an easy task for the receiver to compensate the delays as the signals are mixed together. A novel framework called interleave/deinterleave transform (IDT) is proposed to deal with this problem. It is shown that the IDT allows one to design the delays so that quasi-cyclic (QC) codes with a proper shifting constraint can be used accordingly. When used in conjunction with QC codes, IDT provides significantly better performance than existing schemes relying solely on cyclic codes. Two instances of asynchronous physical-layer network coding, namely the integer-forcing equalization for ISI channels and asynchronous compute-and-forward, are then studied. For integer-forcing equalization, the proposed scheme provides improved performance over using cyclic codes. For asynchronous compute-and-forward, the proposed scheme shows that there is no loss in the achievable information due to delays which are integer multiples of the symbol duration. Further, the proposed approach shows that delays introduced by the channel can sometimes be exploited to obtain higher information rates than those obtainable in the synchronous case. The proposed IDT can be thought of as a generalization of the interleaving/deinterleaving idea proposed by Wang et al. which allows the use of QC codes thereby substantially increasing the design space.
Lessons Learned from Development of a Software Tool to Support Academic Advising
Venue: arXiv cs.CY 2014
Year: 2014

We detail some lessons learned while designing and testing a decision-theoretic advising support tool for undergraduates at a large state university. Between 2009 and 2011 we conducted two surveys of over 500 students in multiple majors and colleges. These surveys asked students detailed questions about their preferences concerning course selection, advising, and career paths. We present data from this study which may be helpful for faculty and staff who advise undergraduate students. We find that advising support software tools can augment the student-advisor relationship, particularly in terms of course planning, but cannot and should not replace in-person advising.
Multi-Parameter Decision Support with Data Transmission over GSM/GPRS Network: a Case Study of Landslide Monitoring
Venue: arXiv cs.NI 2014
Year: 2014

The planet Earth has hundreds of impact events, with some occurrences causing both in terms of human casualty as well as economic losses. Such attitudes of earth pushed the frontiers to develop innovative monitoring strategies for the earth system. To make that real, although, will require coherent and real-time data by observing the earth behavior contiguously. Wireless Sensor Network (WSN) appears to be the best suitable infrastructure to sense environmental parameters of our interests. In this event of earth observation, another important issue is the monitoring system with high level of precision. There are different types of sensors to measure the behavioral aspects of earth. The sensors integrated with WSN, provide an accurate and contiguous data for analysis and interpretation. This paper briefly addresses earth observation and areas of critical importance to people and society. A case study has also been carried out for disaster like Landslide in the North Eastern region of India. Application software has been developed for the said study for online data acquisition and analysis with pre-disaster early warning system. The system monitors the changing geotechnical condition of this region using various geo-technical sensors like Rain gauge, In-place Inclinometer, Tilt-meter, Piezo-meter and Crack meter. This paper also touches upon the aspects of data transmission over Global System for Mobile Communication (GSM) / General Packet Radio Service (GPRS) to a remote data center.
Logics for complexity classes
Venue: arXiv cs.CC 2014
Year: 2014

A new syntactic characterization of problems complete via Turing reductions is presented. General canonical forms are developed in order to define such problems. One of these forms allows us to define complete problems on ordered structures, and another form to define them on unordered non-Aristotelian structures. Using the canonical forms, logics are developed for complete problems in various complexity classes. Evidence is shown that there cannot be any complete problem on Aristotelian structures for several complexity classes. Our approach is extended beyond complete problems. Using a similar form, a logic is developed to capture the complexity class $NP\cap coNP$ which very likely contains no complete problem.
Generation, Implementation and Appraisal of an N-gram based Stemming Algorithm
Venue: arXiv cs.IR 2014
Year: 2014

A language independent stemmer has always been looked for. Single N-gram tokenization technique works well, however, it often generates stems that start with intermediate characters, rather than initial ones. We present a novel technique that takes the concept of N gram stemming one step ahead and compare our method with an established algorithm in the field, Porter's Stemmer. Results indicate that our N gram stemmer is not inferior to Porter's linguistic stemmer.
Hrushovski's Algorithm for Computing the Galois Group of a Linear Differential Equation
Venue: arXiv cs.SC 2014
Year: 2014

We present a detailed and simplified version of Hrushovski's algorithm that determines the Galois group of a linear differential equation. There are three major ingredients in this algorithm. The first is to look for a degree bound for proto-Galois groups, which enables one to compute one of them. The second is to determine the identity component of the Galois group that is the pullback of a torus to the proto-Galois group. The third is to recover the Galois group from its identity component and a finite Galois group.
Large-scale Multi-label Text Classification - Revisiting Neural Networks
Venue: arXiv cs.LG 2014
Year: 2014

Neural networks have recently been proposed for multi-label classification because they are able to capture and model label dependencies in the output layer. In this work, we investigate limitations of BP-MLL, a neural network (NN) architecture that aims at minimizing pairwise ranking error. Instead, we propose to use a comparably simple NN approach with recently proposed learning techniques for large-scale multi-label text classification tasks. In particular, we show that BP-MLL's ranking loss minimization can be efficiently and effectively replaced with the commonly used cross entropy error function, and demonstrate that several advances in neural network training that have been developed in the realm of deep learning can be effectively employed in this setting. Our experimental results show that simple NN models equipped with advanced techniques such as rectified linear units, dropout, and AdaGrad perform as well as or even outperform state-of-the-art approaches on six large-scale textual datasets with diverse characteristics.
Three Metrics for Measuring User Engagement with Online Media and a YouTube Case Study
Venue: arXiv cs.HC 2014
Year: 2014

This technical report discusses three metrics of user engagement with online media. They are Commenting frequency, Voting frequency, and Voting balance. These relative figures can be derived from established, basic statistics available for many services, prominently YouTube. The paper includes case a study of popular YouTube videos to illustrate the characteristics and usefulness of the measures. The study documents the range of observed values and their relationships. The empirical sample shows the three measures to be only moderately correlated with the original statistics despite the common numerators and denominators. The paper concludes by discussing future applications and the needs of the quantification of user interaction with new media services.
Vulnerability and power on networks
Venue: arXiv cs.SI 2014
Year: 2014

Inspired by socio-political scenarios, like dictatorships, in which a minority of people exercise control over a majority of weakly interconnected individuals, we propose vulnerability and power measures defined on groups of actors of networks. We establish an unexpected connection between network vulnerability and graph regularizability. We use the Shapley value of coalition games to introduce fresh notions of vulnerability and power at node level defined in terms of the corresponding measures at group level. We investigate the computational complexity of computing the defined measures, both at group and node levels, and provide effective methods to quantify them. Finally we test vulnerability and power on both artificial and real networks.
Universal Polar Codes for More Capable and Less Noisy Channels and Sources
Venue: arXiv cs.IT 2014
Year: 2014

We prove two results on the universality of polar codes for source coding and channel communication. First, we show that for any polar code built for a source $P_{X,Z}$ there exists a slightly modified polar code - having the same rate, the same encoding and decoding complexity and the same error rate - that is universal for every source $P_{X,Y}$ when using successive cancellation decoding, at least when the channel $P_{Y|X}$ is more capable than $P_{Z|X}$ and $P_X$ is such that it maximizes $I(X;Y) - I(X;Z)$ for the given channels $P_{Y|X}$ and $P_{Z|X}$. This result extends to channel coding for discrete memoryless channels. Second, we prove that polar codes using successive cancellation decoding are universal for less noisy discrete memoryless channels.
Adaptive Feature Ranking for Unsupervised Transfer Learning
Venue: arXiv cs.LG 2014
Year: 2014

Transfer Learning is concerned with the application of knowledge gained from solving a problem to a different but related problem domain. In this paper, we propose a method and efficient algorithm for ranking and selecting representations from a Restricted Boltzmann Machine trained on a source domain to be transferred onto a target domain. Experiments carried out using the MNIST, ICDAR and TiCC image datasets show that the proposed adaptive feature ranking and transfer learning method offers statistically significant improvements on the training of RBMs. Our method is general in that the knowledge chosen by the ranking function does not depend on its relation to any specific target domain, and it works with unsupervised learning and knowledge-based transfer.
Incremental Network Design with Maximum Flows
Venue: arXiv cs.DM 2014
Year: 2014

We study an incremental network design problem, where in each time period of the planning horizon an arc can be added to the network and a maximum flow problem is solved, and where the objective is to maximize the cumulative flow over the entire planning horizon. After presenting two mixed integer programming (MIP) formulations for this NP-complete problem, we describe several heuristics and prove performance bounds for some special cases. In a series of computational experiments, we compare the performance of the MIP formulations as well as the heuristics.
Structure Analysis on the $k$-error Linear Complexity for $2^n$-periodic Binary Sequences
Venue: arXiv cs.CR 2014
Year: 2014

In this paper, in order to characterize the critical error linear complexity spectrum (CELCS) for $2^n$-periodic binary sequences, we first propose a decomposition based on the cube theory. Based on the proposed $k$-error cube decomposition, and the famous inclusion-exclusion principle, we obtain the complete characterization of $i$th descent point (critical point) of the k-error linear complexity for $i=2,3$. Second, by using the sieve method and Games-Chan algorithm, we characterize the second descent point (critical point) distribution of the $k$-error linear complexity for $2^n$-periodic binary sequences. As a consequence, we obtain the complete counting functions on the $k$-error linear complexity of $2^n$-periodic binary sequences as the second descent point for $k=3,4$. This is the first time for the second and the third descent points to be completely characterized. In fact, the proposed constructive approach has the potential to be used for constructing $2^n$-periodic binary sequences with the given linear complexity and $k$-error linear complexity (or CELCS), which is a challenging problem to be deserved for further investigation in future.
Towards Using Unlabeled Data in a Sparse-coding Framework for Human Activity Recognition
Venue: arXiv cs.LG 2014
Year: 2014

We propose a sparse-coding framework for activity recognition in ubiquitous and mobile computing that alleviates two fundamental problems of current supervised learning approaches. (i) It automatically derives a compact, sparse and meaningful feature representation of sensor data that does not rely on prior expert knowledge and generalizes extremely well across domain boundaries. (ii) It exploits unlabeled sample data for bootstrapping effective activity recognizers, i.e., substantially reduces the amount of ground truth annotation required for model estimation. Such unlabeled data is trivial to obtain, e.g., through contemporary smartphones carried by users as they go about their everyday activities. Based on the self-taught learning paradigm we automatically derive an over-complete set of basis vectors from unlabeled data that captures inherent patterns present within activity data. Through projecting raw sensor data onto the feature space defined by such over-complete sets of basis vectors effective feature extraction is pursued. Given these learned feature representations, classification backends are then trained using small amounts of labeled training data. We study the new approach in detail using two datasets which differ in terms of the recognition tasks and sensor modalities. Primarily we focus on transportation mode analysis task, a popular task in mobile-phone based sensing. The sparse-coding framework significantly outperforms the state-of-the-art in supervised learning approaches. Furthermore, we demonstrate the great practical potential of the new approach by successfully evaluating its generalization capabilities across both domain and sensor modalities by considering the popular Opportunity dataset. Our feature learning approach outperforms state-of-the-art approaches to analyzing activities in daily living.
A Consensus-Focused Group Recommender System
Venue: arXiv cs.HC 2014
Year: 2014

In many cases, recommendations are consumed by groups of users rather than individuals. In this paper, we present a system which recommends social events to groups. The system helps groups to organize a joint activity and collectively select which activity to perform among several possible options. We also facilitate the consensus making, following the principle of group consensus decision making. Our system allows users to asynchronously vote, add and comment on alternatives. We observe social influence within groups through post-recommendation feedback during the group decision making process. We propose a decision cascading model and estimate such social influence, which can be used to improve the performance of group recommendation. We conduct experiments to measure the prediction performance of our model. The result shows that the model achieves better results than that of independent decision making model.
A Quadratically Convergent Algorithm for Structured Low-Rank Approximation
Venue: arXiv cs.NA 2014
Year: 2014

Structured Low-Rank Approximation is a problem arising in a wide range of applications in Numerical Analysis and Engineering Sciences. Given an input matrix $M$, the goal is to compute a matrix $M'$ of given rank $r$ in a linear or affine subspace $E$ of matrices (usually encoding a specific structure) such that the Frobenius distance $\lVert M-M'\rVert$ is small. We propose a Newton-like iteration for solving this problem, whose main feature is that it converges locally quadratically to such a matrix under mild transversality assumptions between the manifold of matrices of rank $r$ and the linear/affine subspace $E$. We also show that the distance between the limit of the iteration and the optimal solution of the problem is quadratic in the distance between the input matrix and the manifold of rank $r$ matrices in $E$. To illustrate the applicability of this algorithm, we propose a Maple implementation and give experimental results for several applicative problems that can be modeled by Structured Low-Rank Approximation: univariate approximate GCDs (Sylvester matrices), low-rank Matrix completion (coordinate spaces) and denoising procedures (Hankel matrices). Experimental results give evidence that this all-purpose algorithm is competitive with state-of-the-art numerical methods dedicated to these problems.