OpenRaiser/Intern-Atlas huggingface dataset:
Networked control systems in the presence of scheduling protocols and communication delays
Venue: arXiv cs.SY 2014
Year: 2014

This paper develops the time-delay approach to Networked Control Systems (NCSs) in the presence of variable transmission delays, sampling intervals and communication constraints. The system sensor nodes are supposed to be distributed over a network. Due to communication constraints only one node output is transmitted through the communication channel at once. The scheduling of sensor information towards the controller is ruled by a weighted Try-Once-Discard (TOD) or by Round-Robin (RR) protocols. Differently from the existing results on NCSs in the presence of scheduling protocols (in the frameworks of hybrid and discrete-time systems), we allow the communication delays to be greater than the sampling intervals. A novel hybrid system model for the closed-loop system is presented that contains {\it time-varying delays in the continuous dynamics and in the reset conditions}. A new Lyapunov-Krasovskii method, which is based on discontinuous in time Lyapunov functionals is introduced for the stability analysis of the delayed hybrid systems. Polytopic type uncertainties in the system model can be easily included in the analysis. The efficiency of the time-delay approach is illustrated on the examples of uncertain cart-pendulum and of batch reactor.
Parameter Estimation in SAR Imagery using Stochastic Distances and Asymmetric Kernels
Venue: arXiv cs.IT 2014
Year: 2014

In this paper we analyze several strategies for the estimation of the roughness parameter of the $\mathcal G_I^0$ distribution. It has been shown that this distribution is able to characterize a large number of targets in monopolarized SAR imagery, deserving the denomination of "Universal Model" It is indexed by three parameters: the number of looks (which can be estimated in the whole image), a scale parameter, and the roughness or texture parameter. The latter is closely related to the number of elementary backscatters in each pixel, one of the reasons for receiving attention in the literature. Although there are efforts in providing improved and robust estimates for such quantity, its dependable estimation still poses numerical problems in practice. We discuss estimators based on the minimization of stochastic distances between empirical and theoretical densities, and argue in favor of using an estimator based on the Triangular distance and asymmetric kernels built with Inverse Gaussian densities. We also provide new results regarding the heavytailedness of this distribution.
A RobustICA Based Algorithm for Blind Separation of Convolutive Mixtures
Venue: arXiv cs.LG 2014
Year: 2014

We propose a frequency domain method based on robust independent component analysis (RICA) to address the multichannel Blind Source Separation (BSS) problem of convolutive speech mixtures in highly reverberant environments. We impose regularization processes to tackle the ill-conditioning problem of the covariance matrix and to mitigate the performance degradation in the frequency domain. We apply an algorithm to separate the source signals in adverse conditions, i.e. high reverberation conditions when short observation signals are available. Furthermore, we study the impact of several parameters on the performance of separation, e.g. overlapping ratio and window type of the frequency domain method. We also compare different techniques to solve the frequency-domain permutation ambiguity. Through simulations and real world experiments, we verify the superiority of the presented convolutive algorithm among other BSS algorithms, including recursive regularized ICA (RR ICA), independent vector analysis (IVA).
Weakly monotone averaging functions
Venue: arXiv cs.AI 2014
Year: 2014

Monotonicity with respect to all arguments is fundamental to the definition of aggregation functions. It is also a limiting property that results in many important non-monotonic averaging functions being excluded from the theoretical framework. This work proposes a definition for weakly monotonic averaging functions, studies some properties of this class of functions and proves that several families of important non-monotonic means are actually weakly monotonic averaging functions. Specifically we provide sufficient conditions for weak monotonicity of the Lehmer mean and generalised mixture operators. We establish weak monotonicity of several robust estimators of location and conditions for weak monotonicity of a large class of penalty-based aggregation functions. These results permit a proof of the weak monotonicity of the class of spatial-tonal filters that include important members such as the bilateral filter and anisotropic diffusion. Our concept of weak monotonicity provides a sound theoretical and practical basis by which (monotone) aggregation functions and non-monotone averaging functions can be related within the same framework, allowing us to bridge the gap between these previously disparate areas of research.
Social Media Impact on Website Ranking
Venue: arXiv cs.SI 2014
Year: 2014

Internet is fast becoming critically important to commerce, industry and individuals. Search Engine (SE) is the most vital component for communication network and also used for discover information for users or people. Search engine optimization (SEO) is the process that is mostly used to increasing traffic from free, organic or natural listings on search engines and also helps to increase website ranking. It includes techniques like link building, directory submission, classified submission etc. but SMO, on the other hand, is the process of promoting your website on social media platforms. It includes techniques like RSS feeds, social news and bookmarking sites, video and blogging sites, as well as social networking sites, such as Facebook, Twitter, Google+, Tumblr, Pinterest, Instagram etc.Social media optimization is becoming increasingly important for search engine optimization, as search engines are increasingly utilizing the recommendations of users of social networks to rank pages in the search engine result pages. Since it is more difficult to tip the influence the search engines in this way. Social Media Optimization (SMO) may also use to generate traffic on a website, promote your business at the center of social marketing place and increase ranking.
Fast and Compact Distributed Verification and Self-Stabilization of a DFS Tree
Venue: arXiv cs.DC 2014
Year: 2014

We present algorithms for distributed verification and silent-stabilization of a DFS(Depth First Search) spanning tree of a connected network. Computing and maintaining such a DFS tree is an important task, e.g., for constructing efficient routing schemes. Our algorithm improves upon previous work in various ways. Comparable previous work has space and time complexities of $O(n\log Δ)$ bits per node and $O(nD)$ respectively, where $Δ$ is the highest degree of a node, $n$ is the number of nodes and $D$ is the diameter of the network. In contrast, our algorithm has a space complexity of $O(\log n)$ bits per node, which is optimal for silent-stabilizing spanning trees and runs in $O(n)$ time. In addition, our solution is modular since it utilizes the distributed verification algorithm as an independent subtask of the overall solution. It is possible to use the verification algorithm as a stand alone task or as a subtask in another algorithm. To demonstrate the simplicity of constructing efficient DFS algorithms using the modular approach, We also present a (non-sielnt) self-stabilizing DFS token circulation algorithm for general networks based on our silent-stabilizing DFS tree. The complexities of this token circulation algorithm are comparable to the known ones.
Standards for Graph Algorithm Primitives
Venue: arXiv cs.MS 2014
Year: 2014

It is our view that the state of the art in constructing a large collection of graph algorithms in terms of linear algebraic operations is mature enough to support the emergence of a standard set of primitive building blocks. This paper is a position paper defining the problem and announcing our intention to launch an open effort to define this standard.
Methodology For Detection of QRS Pattern Using Secondary Wavelets
Venue: arXiv cs.CV 2014
Year: 2014

Applications of wavelet transform to the field of health care signals have paved the way for implementing revolutionary approaches in detecting the presence of certain abnormalities in human health patterns. There were extensive studies carried out using primary wavelets in various signals like Electrocardiogram (ECG), sonogram etc. with a certain amount of success. On the other hand analysis using secondary wavelets which inherits the characteristics of a set of variations available in signals like ECG can be a promise to detect diseases with ease. Here a method to create a generalized adapted wavelet is presented which contains the information of QRS pattern collected from an anomaly sample space. The method has been tested and found to be successful in locating the position of R peak in noise embedded ECG signal.
Online Pattern Matching for String Edit Distance with Moves
Venue: arXiv cs.DS 2014
Year: 2014

Edit distance with moves (EDM) is a string-to-string distance measure that includes substring moves in addition to ordinal editing operations to turn one string to the other. Although optimizing EDM is intractable, it has many applications especially in error detections. Edit sensitive parsing (ESP) is an efficient parsing algorithm that guarantees an upper bound of parsing discrepancies between different appearances of the same substrings in a string. ESP can be used for computing an approximate EDM as the L1 distance between characteristic vectors built by node labels in parsing trees. However, ESP is not applicable to a streaming text data where a whole text is unknown in advance. We present an online ESP (OESP) that enables an online pattern matching for EDM. OESP builds a parse tree for a streaming text and computes the L1 distance between characteristic vectors in an online manner. For the space-efficient computation of EDM, OESP directly encodes the parse tree into a succinct representation by leveraging the idea behind recent results of a dynamic succinct tree. We experimentally test OESP on the ability to compute EDM in an online manner on benchmark datasets, and we show OESP's efficiency.
The Value of Help Bits in Randomized and Average-Case Complexity
Venue: arXiv cs.CC 2014
Year: 2014

"Help bits" are some limited trusted information about an instance or instances of a computational problem that may reduce the computational complexity of solving that instance or instances. In this paper, we study the value of help bits in the settings of randomized and average-case complexity. Amir, Beigel, and Gasarch (1990) show that for constant $k$, if $k$ instances of a decision problem can be efficiently solved using less than $k$ bits of help, then the problem is in P/poly. We extend this result to the setting of randomized computation: We show that the decision problem is in P/poly if using $\ell$ help bits, $k$ instances of the problem can be efficiently solved with probability greater than $2^{\ell-k}$. The same result holds if using less than $k(1 - h(α))$ help bits (where $h(\cdot)$ is the binary entropy function), we can efficiently solve $(1-α)$ fraction of the instances correctly with non-vanishing probability. We also extend these two results to non-constant but logarithmic $k$. In this case however, instead of showing that the problem is in P/poly we show that it satisfies "$k$-membership comparability," a notion known to be related to solving $k$ instances using less than $k$ bits of help. Next we consider the setting of average-case complexity: Assume that we can solve $k$ instances of a decision problem using some help bits whose entropy is less than $k$ when the $k$ instances are drawn independently from a particular distribution. Then we can efficiently solve an instance drawn from that distribution with probability better than $1/2$. Finally, we show that in the case where $k$ is super-logarithmic, assuming $k$-membership comparability of a decision problem, one cannot prove that the problem is in P/poly by a "black-box proof."
Big Data Dimensional Analysis
Venue: arXiv cs.DB 2014
Year: 2014

The ability to collect and analyze large amounts of data is a growing problem within the scientific community. The growing gap between data and users calls for innovative tools that address the challenges faced by big data volume, velocity and variety. One of the main challenges associated with big data variety is automatically understanding the underlying structures and patterns of the data. Such an understanding is required as a pre-requisite to the application of advanced analytics to the data. Further, big data sets often contain anomalies and errors that are difficult to know a priori. Current approaches to understanding data structure are drawn from the traditional database ontology design. These approaches are effective, but often require too much human involvement to be effective for the volume, velocity and variety of data encountered by big data systems. Dimensional Data Analysis (DDA) is a proposed technique that allows big data analysts to quickly understand the overall structure of a big dataset, determine anomalies. DDA exploits structures that exist in a wide class of data to quickly determine the nature of the data and its statical anomalies. DDA leverages existing schemas that are employed in big data databases today. This paper presents DDA, applies it to a number of data sets, and measures its performance. The overhead of DDA is low and can be applied to existing big data systems without greatly impacting their computing requirements.
Target Detection Performance of Spectrum Sharing MIMO Radars
Venue: arXiv cs.IT 2014
Year: 2014

Future wireless communication systems are envisioned to share radio frequency (RF) spectrum, with other services such as radars, in order to meet the growing spectrum demands. In this paper, we consider co-channel spectrum sharing between cellular systems and radars. We address the problem of target detection by radars that are subject to shape its waveform in a way that it does not cause interference to cellular systems. We consider a multiple-input multiple-output (MIMO) radar and a MIMO cellular communication system with $\mc K$ base stations (BS). We propose a spectrum sharing algorithm which steers radar nulls, by projecting radar waveform onto the null space of interference channel, towards a `selected' BS, thus, protecting it from radar interference. This BS is selected, among $\mc K$ BSs, on the basis of guaranteeing minimum waveform degradation. We study target detection capabilities of this null-space projected (NSP) waveform and compare it with the orthogonal waveform. We derive the generalized likelihood ratio test (GLRT) for target detection and derive detector statistic for NSP and orthogonal waveform. The target detection performance for NSP and orthogonal waveform is studied theoretically and via Monte Carlo simulations.
Sample Complexity Analysis for Learning Overcomplete Latent Variable Models through Tensor Methods
Venue: arXiv cs.LG 2014
Year: 2014

We provide guarantees for learning latent variable models emphasizing on the overcomplete regime, where the dimensionality of the latent space can exceed the observed dimensionality. In particular, we consider multiview mixtures, spherical Gaussian mixtures, ICA, and sparse coding models. We provide tight concentration bounds for empirical moments through novel covering arguments. We analyze parameter recovery through a simple tensor power update algorithm. In the semi-supervised setting, we exploit the label or prior information to get a rough estimate of the model parameters, and then refine it using the tensor method on unlabeled samples. We establish that learning is possible when the number of components scales as $k=o(d^{p/2})$, where $d$ is the observed dimension, and $p$ is the order of the observed moment employed in the tensor method. Our concentration bound analysis also leads to minimax sample complexity for semi-supervised learning of spherical Gaussian mixtures. In the unsupervised setting, we use a simple initialization algorithm based on SVD of the tensor slices, and provide guarantees under the stricter condition that $k\le βd$ (where constant $β$ can be larger than $1$), where the tensor method recovers the components under a polynomial running time (and exponential in $β$). Our analysis establishes that a wide range of overcomplete latent variable models can be learned efficiently with low computational and sample complexity through tensor decomposition methods.
Parametric Schemes for Prediction of Wideband MIMO Wireless Channels
Venue: arXiv cs.IT 2014
Year: 2014

Information on the future state of time varying frequency selective channels can significantly enhance the effectiveness of feedback in adaptive and limited feedback MIMO-OFDM systems. This paper investigates the parametric extrapolation of wideband MIMO channels using variations of the double directional MIMO model. We propose three predictors which estimate parameters of the channel using 4D, 3D and 2D extensions of the ESPRIT algorithm and predict future states of the channel using the models. Furthermore, using the vector formulation of the Cramer Rao lower bound for functions of parameters, we derive a bound on the prediction error in wideband MIMO channels. Numerical simulations are used to evaluate the performance of the proposed algorithms under different channel and transmission conditions, and a comparison is made with the derived error bound.
Correlating and Cross-linking Knowledge Threads in Informledge System for Creating New Knowledge
Venue: arXiv cs.AI 2014
Year: 2014

There has been a considerable advance in computing, to mimic the way in which the brain tries to comprehend and structure the information to retrieve meaningful knowledge. It is identified that neuronal entities hold whole of the knowledge that the species makes use of. We intended to develop a modified knowledge based system, termed as Informledge System (ILS) with autonomous nodes and intelligent links that integrate and structure the pieces of knowledge. We conceive that every piece of knowledge is a cluster of cross-linked and correlated structure. In this paper, we put forward the theory of the nodes depicting concepts, referred as Entity Concept State which in turn is dealt with Concept State Diagrams (CSD). This theory is based on an abstract framework provided by the concepts. The framework represents the ILS as the weighted graph where the weights attached with the linked nodes help in knowledge retrieval by providing the direction of connectivity of autonomous nodes present in knowledge thread traversal. Here for the first time in the process of developing Informledge, we apply tenor computation for creating intelligent combinatorial knowledge with cross mutation to create fresh knowledge which looks to be the fundamentals of a typical thought process.
The Dynamics of Offensive Messages in the World of Social Media: the Control of Cyberbullying on Twitter
Venue: arXiv cs.SI 2014
Year: 2014

The 21st century has redefined the way we communicate, our concept of individual and group privacy, and the dynamics of acceptable behavioral norms. The messaging dynamics on Twitter, an internet social network, has opened new ways/modes of spreading information. As a result cyberbullying or in general, the spread of offensive messages, is a prevalent problem. The aim of this report is to identify and evaluate conditions that would dampen the role of cyberbullying dynamics on Twitter. We present a discrete-time non-linear compartmental model to explore how the introduction of a Quarantine class may help to hinder the spread of offensive messages. We based the parameters of this model on recent Twitter data related to a topic that communities would deem most offensive, and found that for Twitter a level of quarantine can always be achieved that will immediately suppress the spread of offensive messages, and that this level of quarantine is independent of the number of offenders spreading the message. We hope that the analysis of this dynamic model will shed some insights into the viability of new models of methods for reducing cyberbullying in public social networks.
Reducing the Complexity of Quantified Formulas via Variable Elimination
Venue: arXiv cs.LO 2014
Year: 2014

We present a general simplification of quantified SMT formulas using variable elimination. The simplification is based on an analysis of the ground terms occurring as arguments in function applications. We use this information to generate a system of set constraints, which is then solved to compute a set of sufficient ground terms for each variable. Universally quantified variables with a finite set of sufficient ground terms can be eliminated by instantiating them with the computed ground terms. The resulting SMT formula contains potentially fewer quantifiers and thus is potentially easier to solve. We describe how a satisfying model of the resulting formula can be modified to satisfy the original formula. Our experiments show that in many cases, this simplification considerably improves the solving time, and our evaluations using Z3 and CVC4 indicate that the idea is not specific to a particular solver, but can be applied in general.
Personalized PageRank with Node-dependent Restart
Venue: arXiv cs.IR 2014
Year: 2014

Personalized PageRank is an algorithm to classify the improtance of web pages on a user-dependent basis. We introduce two generalizations of Personalized PageRank with node-dependent restart. The first generalization is based on the proportion of visits to nodes before the restart, whereas the second generalization is based on the probability of visited node just before the restart. In the original case of constant restart probability, the two measures coincide. We discuss interesting particular cases of restart probabilities and restart distributions. We show that the both generalizations of Personalized PageRank have an elegant expression connecting the so-called direct and reverse Personalized PageRanks that yield a symmetry property of these Personalized PageRanks.
Spectral Approaches to Nearest Neighbor Search
Venue: arXiv cs.DS 2014
Year: 2014

We study spectral algorithms for the high-dimensional Nearest Neighbor Search problem (NNS). In particular, we consider a semi-random setting where a dataset $P$ in $\mathbb{R}^d$ is chosen arbitrarily from an unknown subspace of low dimension $k\ll d$, and then perturbed by fully $d$-dimensional Gaussian noise. We design spectral NNS algorithms whose query time depends polynomially on $d$ and $\log n$ (where $n=|P|$) for large ranges of $k$, $d$ and $n$. Our algorithms use a repeated computation of the top PCA vector/subspace, and are effective even when the random-noise magnitude is {\em much larger} than the interpoint distances in $P$. Our motivation is that in practice, a number of spectral NNS algorithms outperform the random-projection methods that seem otherwise theoretically optimal on worst case datasets. In this paper we aim to provide theoretical justification for this disparity.