OpenRaiser/Intern-Atlas huggingface dataset:
Dynamic Channel Acquisition in MU-MIMO
Venue: arXiv cs.IT 2014
Year: 2014

Multiuser multiple-input-multiple-output (MU-MIMO) systems are known to be hindered by dimensionality loss due to channel state information (CSI) acquisition overhead. In this paper, we investigate user-scheduling in MU-MIMO systems on account of CSI acquisition overhead, where a base station dynamically acquires user channels to avoid choking the system with CSI overhead. The genie-aided optimization problem (GAP) is first formulated to maximize the Lyapunov-drift every scheduling step, incorporating user queue information and taking channel fluctuations into consideration. The scheduling scheme based on GAP, namely the GAP-rule, is proved to be throughput-optimal but practically infeasible, and thus serves as a performance bound. In view of the implementation overhead and delay unfairness of the GAP-rule, the T-frame dynamic channel acquisition scheme and the power-law DCA scheme are further proposed to mitigate the implementation overhead and delay unfairness, respectively. Both schemes are based on the GAP-rule and proved throughput-optimal. To make the schemes practically feasible, we then propose the heuristic schemes, queue-based quantized-block-length user scheduling scheme (QQS), T-frame QQS, and power-law QQS, which are the practical versions of the aforementioned GAP-based schemes, respectively. The QQS-based schemes substantially decrease the complexity, and also perform fairly close to the optimum. Numerical results evaluate the proposed schemes under various system parameters.
Combinatorics and algorithms for augmenting graphs
Venue: arXiv cs.DM 2014
Year: 2014

The notion of augmenting graphs generalizes Berge's idea of augmenting chains, which was used by Edmonds in his celebrated solution of the maximum matching problem. This problem is a special case of the more general maximum independent set (MIS) problem. Recently, the augmenting graph approach has been successfully applied to solve MIS in various other special cases. However, our knowledge of augmenting graphs is still very limited, and we do not even know what the minimal infinite classes of augmenting graphs are. In the present paper, we find an answer to this question and apply it to extend the area of polynomial-time solvability of the maximum independent set problem.
Correlated Source Coded Sequences with Compromised Channel and Source Symbols using Shannon's Cipher System
Venue: arXiv cs.IT 2014
Year: 2014

Correlated sources are present in communication systems where protocols ensure that there is some predetermined information for sources to transmit. Here, two correlated sources across a channel with eavesdroppers are investigated, and conditions for perfect secrecy when some channel information and some source data symbols (the predetermined information) have been wiretapped are determined. The adversary in this situation has access to more information than if a link is wiretapped only and can thus determine more about a particular source. This scenario caters for an application where the eavesdropper has access to some preexisting information. We provide bounds for the channel and key rates for this scenario. Further, we provide a method to reduce the key lengths required for perfect secrecy.
Prognosis of Anterior Cruciate Ligament (ACL) Reconstruction: A Data Driven Approach
Venue: arXiv cs.CE 2014
Year: 2014

Individuals who suffer anterior cruciate ligament (ACL) injury are at higher risk of developing knee osteoarthritis (OA) and almost 50% display symptoms 10 to 20 years post injury. Anterior cruciate ligament reconstruction (ACLR) often does not protect against knee OA development. Accordingly, a multiscale formulation for Data Driven Prognosis (DDP) of post ACLR is developed. Unlike traditional predictive strategies that require controlled off-line measurements or training for determination of constitutive parameters to derive the transitional statistics, the proposed DDP algorithm relies solely on in situ measurements. The proposed DDP scheme is capable of predicting onset of instabilities. Since the need for off line testing (or training) is obviated, it can be easily implemented for ACLR, where such controlled a priori testing is almost impossible to conduct. The DDP algorithm facilitates hierarchical handling of the large data set, and can assess the state of recovery in post ACLR conditions based on data collected from stair ascent and descent exercises of subjects. The DDP algorithm identifies inefficient knee varus motion and knee rotation as primary difficulties experienced by some of the post ACLR population. In such cases, levels of energy dissipation rate at the knee, and its fluctuation may be used as measures for assessing progress after ACL reconstruction.
Generalized Adaptive Dictionary Learning via Domain Shift Minimization
Venue: arXiv cs.CV 2014
Year: 2014

Visual data driven dictionaries have been successfully employed for various object recognition and classification tasks. However, the task becomes more challenging if the training and test data are from contrasting domains. In this paper, we propose a novel and generalized approach towards learning an adaptive and common dictionary for multiple domains. Precisely, we project the data from different domains onto a low dimensional space while preserving the intrinsic structure of data from each domain. We also minimize the domain-shift among the data from each pair of domains. Simultaneously, we learn a common adaptive dictionary. Our algorithm can also be modified to learn class-specific dictionaries which can be used for classification. We additionally propose a discriminative manifold regularization which imposes the intrinsic structure of class specific features onto the sparse coefficients. Experiments on image classification show that our approach fares better compared to the existing state-of-the-art methods.
Fusion Tree Sorting
Venue: arXiv cs.DS 2014
Year: 2014

The sorting problem is one of the most relevant problems in computer science. Within the scope of modern computer science it has been studied for more than 70 years. In spite of these facts, new sorting algorithms have been developed in recent years. Among several types of sorting algorithms, some are quicker; others are more economic in relation to space, whereas others insert a few restrictions in relation to data input. This paper is aimed at explaining the fusion tree data structure, which is responsible for the first sorting algorithm with complexity time smaller than nlgn. The nlgn time complexity has led to some confusion and generated the wrong belief in part of the community of being the minimum possible for this type of problem.
User Capacity of Pilot-Contaminated TDD Massive MIMO Systems
Venue: arXiv cs.IT 2014
Year: 2014

Pilot contamination has been regarded as a main limiting factor of time division duplexing (TDD) massive multiple-input-multiple-output (Massive MIMO) systems, as it will make the signal-to-interference-plus-noise ratio (SINR) saturated. However, how pilot contamination will limit the user capacity of downlink Massive MIMO, i.e., the maximum number of admissible users, has not been addressed. This paper provides an explicit expression of the Massive MIMO user capacity in the pilot-contaminated regime where the number of users is larger than the pilot sequence length. Furthermore, the scheme for achieving the user capacity, i.e., the uplink pilot training sequence and downlink power allocation, has been identified. By using this capacity-achieving scheme, the SINR requirement of each user can be satisfied and energy-efficient transmission is feasible in the large-antenna-size (LAS) regime. Comparison with two non-capacity-achieving schemes highlights the superiority of our proposed scheme in terms of achieving higher user capacity.
Study of Citation Networks in Tribology Research
Venue: arXiv cs.DL 2014
Year: 2014

CitNetExplorer has been used to study the citation networks among the scientific publications on tribology during the 15 years period from 1998-2012. Three data sets from Web of Science have been analyzed: (1) Core publications of tribology research, (2) publications on nanotribology and (3) publications of Bharat Bhushan (a top-contributor to nanotribology research). Based on this study, some suggestions are made to improve the CitNetExplorer.
A Note on Signed k-Submatching in Graphs
Venue: arXiv cs.DM 2014
Year: 2014

Let $G$ be a graph of order $n$. For every $v\in V(G)$, let $E_G(v)$ denote the set of all edges incident with $v$. A signed $k$-submatching of $G$ is a function $f:E(G)\longrightarrow \{-1,1\}$, satisfying $f(E_G(v))\leq 1$ for at least $k$ vertices, where $f(S)=\sum_{e\in S}f(e)$, for each $ S\subseteq E(G)$. The maximum of the value of $f(E(G))$, taken over all signed $k$-submatching $f$ of $G$, is called the signed $k$-submatching number and is denoted by $β^k_S(G)$. In this paper, we prove that for every graph $G$ of order $n$ and for any positive integer $k \leq n$, $β^k_S (G) \geq n-k - ω(G)$, where $w(G)$ is the number of components of $G$. This settles a conjecture proposed by Wang. Also, we present a formula for the computation of $β_S^n(G)$.
Censorship is Futile
Venue: arXiv cs.CY 2014
Year: 2014

The Internet has become the new battle ground between authoritarian regimes and ordinary individuals who want unimpeded access to information. The immense popularity of online activism and citizen journalism enabled by social media has instigated state level players to partially or completely block access to the Internet. In return, individuals and organizations have been employing various anti-censorship tools to circumvent these restrictions. In this paper, we claim that censorship is futile as not only has it been ineffective in restricting access, it has also had the side-effect of popularising blocked content. Using data from Alexa Web Rankings, Google Trends, and YouTube Statistics, we quantify the ineffectiveness of state level censorship in Pakistan and Turkey and highlight the emergence of the Streisand Effect. We hope that our findings will, a) prove to governments and other players the futility of their actions, and b) aid citizens around the world in using legal measures to counteract censorship by showing its ineffectiveness.
Detection of transitions between broad phonetic classes in a speech signal
Venue: arXiv cs.SD 2014
Year: 2014

Detection of transitions between broad phonetic classes in a speech signal is an important problem which has applications such as landmark detection and segmentation. The proposed hierarchical method detects silence to non-silence transitions, high amplitude (mostly sonorants) to low ampli- tude (mostly fricatives/affricates/stop bursts) transitions and vice-versa. A subset of the extremum (minimum or maximum) samples between every pair of successive zero-crossings is selected above a second pass threshold, from each bandpass filtered speech signal frame. Relative to the mid-point (reference) of a frame, locations of the first and the last extrema lie on either side, if the speech signal belongs to a homogeneous segment; else, both these locations lie on the left or the right side of the reference, indicating a transition frame. When tested on the entire TIMIT database, of the transitions detected, 93.6% are within a tolerance of 20 ms from the hand labeled boundaries. Sonorant, unvoiced non-sonorant and silence classes and their respective onsets are detected with an accuracy of about 83.5% for the same tolerance. The results are as good as, and in some respects better than the state-of-the-art methods for similar tasks.
Sparsity Constrained Graph Regularized NMF for Spectral Unmixing of Hyperspectral Data
Venue: arXiv cs.CV 2014
Year: 2014

Hyperspectral images contain mixed pixels due to low spatial resolution of hyperspectral sensors. Mixed pixels are pixels containing more than one distinct material called endmembers. The presence percentages of endmembers in mixed pixels are called abundance fractions. Spectral unmixing problem refers to decomposing these pixels into a set of endmembers and abundance fractions. Due to nonnegativity constraint on abundance fractions, nonnegative matrix factorization methods (NMF) have been widely used for solving spectral unmixing problem. In this paper we have used graph regularized NMF (GNMF) method combined with sparseness constraint to decompose mixed pixels in hyperspectral imagery. This method preserves the geometrical structure of data while representing it in low dimensional space. Adaptive regularization parameter based on temperature schedule in simulated annealing method also has been used in this paper for the sparseness term. Proposed algorithm is applied on synthetic and real datasets. Synthetic data is generated based on endmembers from USGS spectral library. AVIRIS Cuprite dataset is used as real dataset for evaluation of proposed method. Results are quantified based on spectral angle distance (SAD) and abundance angle distance (AAD) measures. Results in comparison with other methods show that the proposed method can unmix data more effectively. Specifically for the Cuprite dataset, performance of the proposed method is approximately 10% better than the VCA and Sparse NMF in terms of root mean square of SAD.
Reduction of CRB in Arbitrary Pre-designed Arrays Using Alter an Element Position
Venue: arXiv cs.IT 2014
Year: 2014

Simultaneous estimation of range and angle of close emitters usually requires a multidimensional search. This paper offers an algorithm to improve the position of an element of any array designed on the basis of some certain or random rules. In the proposed method one element moves on its original direction, i.e., keeping the vertical distance to each source, to reach the constellation with less CRB. The performance of this method has been demonstrated through simulation and a comparison of the CRB with receptive signals covariance matrix determinant has been made before and after the use of this method.
A QPTAS for the Base of the Number of Triangulations of a Planar Point Set
Venue: arXiv cs.CG 2014
Year: 2014

The number of triangulations of a planar n point set is known to be $c^n$, where the base $c$ lies between $2.43$ and $30.$ The fastest known algorithm for counting triangulations of a planar n point set runs in $O^*(2^n)$ time. The fastest known arbitrarily close approximation algorithm for the base of the number of triangulations of a planar n point set runs in time subexponential in $n.$ We present the first quasi-polynomial approximation scheme for the base of the number of triangulations of a planar point set.
Affective Facial Expression Processing via Simulation: A Probabilistic Model
Venue: arXiv cs.CV 2014
Year: 2014

Understanding the mental state of other people is an important skill for intelligent agents and robots to operate within social environments. However, the mental processes involved in `mind-reading' are complex. One explanation of such processes is Simulation Theory - it is supported by a large body of neuropsychological research. Yet, determining the best computational model or theory to use in simulation-style emotion detection, is far from being understood. In this work, we use Simulation Theory and neuroscience findings on Mirror-Neuron Systems as the basis for a novel computational model, as a way to handle affective facial expressions. The model is based on a probabilistic mapping of observations from multiple identities onto a single fixed identity (`internal transcoding of external stimuli'), and then onto a latent space (`phenomenological response'). Together with the proposed architecture we present some promising preliminary results
Detecting Suicidal Ideation in Chinese Microblogs with Psychological Lexicons
Venue: arXiv cs.CL 2014
Year: 2014

Suicide is among the leading causes of death in China. However, technical approaches toward preventing suicide are challenging and remaining under development. Recently, several actual suicidal cases were preceded by users who posted microblogs with suicidal ideation to Sina Weibo, a Chinese social media network akin to Twitter. It would therefore be desirable to detect suicidal ideations from microblogs in real-time, and immediately alert appropriate support groups, which may lead to successful prevention. In this paper, we propose a real-time suicidal ideation detection system deployed over Weibo, using machine learning and known psychological techniques. Currently, we have identified 53 known suicidal cases who posted suicide notes on Weibo prior to their deaths.We explore linguistic features of these known cases using a psychological lexicon dictionary, and train an effective suicidal Weibo post detection model. 6714 tagged posts and several classifiers are used to verify the model. By combining both machine learning and psychological knowledge, SVM classifier has the best performance of different classifiers, yielding an F-measure of 68:3%, a Precision of 78:9%, and a Recall of 60:3%.
Tied Probabilistic Linear Discriminant Analysis for Speech Recognition
Venue: arXiv cs.CL 2014
Year: 2014

Acoustic models using probabilistic linear discriminant analysis (PLDA) capture the correlations within feature vectors using subspaces which do not vastly expand the model. This allows high dimensional and correlated feature spaces to be used, without requiring the estimation of multiple high dimension covariance matrices. In this letter we extend the recently presented PLDA mixture model for speech recognition through a tied PLDA approach, which is better able to control the model size to avoid overfitting. We carried out experiments using the Switchboard corpus, with both mel frequency cepstral coefficient features and bottleneck feature derived from a deep neural network. Reductions in word error rate were obtained by using tied PLDA, compared with the PLDA mixture model, subspace Gaussian mixture models, and deep neural networks.
More Tight Bounds for Active Self-Assembly Using an Insertion Primitive
Venue: arXiv cs.DS 2014
Year: 2014

We prove several limits on the behavior of a model of self-assembling particles introduced by Dabby and Chen (SODA 2013), called insertion systems, where monomers insert themselves into the middle of a growing linear polymer. First, we prove that the expressive power of these systems is equal to context-free grammars, answering a question posed by Dabby and Chen. Second, we give tight bounds on the maximum length and minimum expected time of constructed polymers in systems of three increasingly restricted classes. We prove that systems of $k$ monomer types can deterministically construct polymers of length $n = 2^{Θ(k^{3/2})}$ in $O(\log^{5/3}(n))$ expected time. We also prove that if non-deterministic construction of a finite number of polymers is permitted, then the expected construction time can be reduced to $O(\log^{3/2}(n))$ at the trade-off of decreasing the length to $2^{Θ(k)}$. If the system is allowed to construct an infinite number of polymers, then constructing polymers of unbounded length in $O(\log{n})$ expected time is possible. We follow these positive results with a set of lower bounds proving that these are the best possible polymer lengths and expected construction times.
High-level Reasoning and Low-level Learning for Grasping: A Probabilistic Logic Pipeline
Venue: arXiv cs.RO 2014
Year: 2014

While grasps must satisfy the grasping stability criteria, good grasps depend on the specific manipulation scenario: the object, its properties and functionalities, as well as the task and grasp constraints. In this paper, we consider such information for robot grasping by leveraging manifolds and symbolic object parts. Specifically, we introduce a new probabilistic logic module to first semantically reason about pre-grasp configurations with respect to the intended tasks. Further, a mapping is learned from part-related visual features to good grasping points. The probabilistic logic module makes use of object-task affordances and object/task ontologies to encode rules that generalize over similar object parts and object/task categories. The use of probabilistic logic for task-dependent grasping contrasts with current approaches that usually learn direct mappings from visual perceptions to task-dependent grasping points. We show the benefits of the full probabilistic logic pipeline experimentally and on a real robot.
Learning of Agent Capability Models with Applications in Multi-agent Planning
Venue: arXiv cs.AI 2014
Year: 2014

One important challenge for a set of agents to achieve more efficient collaboration is for these agents to maintain proper models of each other. An important aspect of these models of other agents is that they are often partial and incomplete. Thus far, there are two common representations of agent models: MDP based and action based, which are both based on action modeling. In many applications, agent models may not have been given, and hence must be learnt. While it may seem convenient to use either MDP based or action based models for learning, in this paper, we introduce a new representation based on capability models, which has several unique advantages. First, we show that learning capability models can be performed efficiently online via Bayesian learning, and the learning process is robust to high degrees of incompleteness in plan execution traces (e.g., with only start and end states). While high degrees of incompleteness in plan execution traces presents learning challenges for MDP based and action based models, capability models can still learn to {\em abstract} useful information out of these traces. As a result, capability models are useful in applications in which such incompleteness is common, e.g., robot learning human model from observations and interactions. Furthermore, when used in multi-agent planning (with each agent modeled separately), capability models provide flexible abstraction of actions. The limitation, however, is that the synthesized plan is incomplete and abstract.
Probabilistic Modeling of IEEE 802.11 Distributed Coordination Functions
Venue: arXiv cs.NI 2014
Year: 2014

We introduce and analyze a new Markov model of the IEEE 802.11 Distributed Coordination Function (DCF) for wireless networks. The new model is derived from a detailed DCF description where transition probabilities are determined by precise estimates of collision probabilities based on network topology and node states. For steady state calculations, we approximate joint probabilities from marginal probabilities using product approximations. To assess the quality of the model, we compare detailed equilibrium node states with results from realistic simulations of wireless networks. We find very close correspondence between the model and the simulations in a variety of representative network topologies.
Provably Manipulation-Resistant Reputation Systems
Venue: arXiv cs.GT 2014
Year: 2014

We consider a community of users who must make periodic decisions about whether to interact with one another. We propose a protocol which allows honest users to reliably interact with each other, while limiting the damage done by each malicious or incompetent user. The worst-case cost per user is sublinear in the average number of interactions per user and is independent of the number of users. Our guarantee holds simultaneously for every group of honest users. For example, multiple groups of users with incompatible tastes or preferences can coexist. As a motivating example, we consider a game where players have periodic opportunities to do one another favors but minimal ability to determine when a favor was done. In this setting, our protocol achieves nearly optimal collective welfare while remaining resistant to exploitation. Our results also apply to a collaborative filtering setting where users must make periodic decisions about whether to interact with resources such as movies or restaurants. In this setting, we guarantee that any set of honest users achieves a payoff nearly as good as if they had identified the optimal set of items in advance and then chosen to interact only with resources from that set.