OpenRaiser/Intern-Atlas huggingface dataset:
Matrix-valued Monge-Kantorovich Optimal Mass Transport
Venue: arXiv cs.SY 2013
Year: 2013

We formulate an optimal transport problem for matrix-valued density functions. This is pertinent in the spectral analysis of multivariable time-series. The "mass" represents energy at various frequencies whereas, in addition to a usual transportation cost across frequencies, a cost of rotation is also taken into account. We show that it is natural to seek the transportation plan in the tensor product of the spaces for the two matrix-valued marginals. In contrast to the classical Monge-Kantorovich setting, the transportation plan is no longer supported on a thin zero-measure set.
Bidirectional Collision Detection and Faster Deterministic Isomorphism Testing
Venue: arXiv cs.DS 2013
Year: 2013

In this work, we introduce bidirectional collision detection --- a new algorithmic tool that applies to the collision problems that arise in many isomorphism problems. For the group isomorphism problem, we show that bidirectional collision detection yields a deterministic n^((1 / 2) log n + O(1)) time algorithm whereas previously the n^(log n + O(1)) generator-enumeration algorithm was the best result for several decades. For the hard special case of solvable groups, we combine bidirectional collision detection with methods from the author's previous work to obtain a deterministic square-root speedup over the best previous algorithm. We also show a deterministic square-root speedup over the best previous algorithm for testing isomorphism of rings. We can even apply bidirectional collision detection to the graph isomorphism problem to obtain a deterministic T^(1 / sqrt(2)) speedup over the best previous deterministic algorithm. Although the space requirements for our algorithms are greater than those for previous deterministic isomorphism tests, we show time-space tradeoffs that interpolate between the resource requirements of our algorithms and previous work.
Unveiling the link between logical fallacies and web persuasion
Venue: arXiv cs.HC 2013
Year: 2013

In the last decade Human-Computer Interaction (HCI) has started to focus attention on forms of persuasive interaction where computer technologies have the goal of changing users behavior and attitudes according to a predefined direction. In this work, we hypothesize a strong connection between logical fallacies (forms of reasoning which are logically invalid but cognitively effective) and some common persuasion strategies adopted within web technologies. With the aim of empirically evaluating our hypothesis, we carried out a pilot study on a sample of 150 e-commerce websites.
Parametric Sensitivity Analysis for Biochemical Reaction Networks based on Pathwise Information Theory
Venue: arXiv cs.IT 2013
Year: 2013

Stochastic modeling and simulation provide powerful predictive methods for the intrinsic understanding of fundamental mechanisms in complex biochemical networks. Typically, such mathematical models involve networks of coupled jump stochastic processes with a large number of parameters that need to be suitably calibrated against experimental data. In this direction, the parameter sensitivity analysis of reaction networks is an essential mathematical and computational tool, yielding information regarding the robustness and the identifiability of model parameters. However, existing sensitivity analysis approaches such as variants of the finite difference method can have an overwhelming computational cost in models with a high-dimensional parameter space. We develop a sensitivity analysis methodology suitable for complex stochastic reaction networks with a large number of parameters. The proposed approach is based on Information Theory methods and relies on the quantification of information loss due to parameter perturbations between time-series distributions. For this reason, we need to work on path-space, i.e., the set consisting of all stochastic trajectories, hence the proposed approach is referred to as "pathwise". The pathwise sensitivity analysis method is realized by employing the rigorously-derived Relative Entropy Rate (RER), which is directly computable from the propensity functions. A key aspect of the method is that an associated pathwise Fisher Information Matrix (FIM) is defined, which in turn constitutes a gradient-free approach to quantifying parameter sensitivities. The structure of the FIM turns out to be block-diagonal, revealing hidden parameter dependencies and sensitivities in reaction networks.
GPU Acclerated Automated Feature Extraction from Satellite Images
Venue: arXiv cs.DC 2013
Year: 2013

The availability of large volumes of remote sensing data insists on higher degree of automation in feature extraction, making it a need of the hour.The huge quantum of data that needs to be processed entails accelerated processing to be enabled.GPUs, which were originally designed to provide efficient visualization, are being massively employed for computation intensive parallel processing environments. Image processing in general and hence automated feature extraction, is highly computation intensive, where performance improvements have a direct impact on societal needs. In this context, an algorithm has been formulated for automated feature extraction from a panchromatic or multispectral image based on image processing techniques. Two Laplacian of Guassian (LoG) masks were applied on the image individually followed by detection of zero crossing points and extracting the pixels based on their standard deviation with the surrounding pixels. The two extracted images with different LoG masks were combined together which resulted in an image with the extracted features and edges. Finally the user is at liberty to apply the image smoothing step depending on the noise content in the extracted image. The image is passed through a hybrid median filter to remove the salt and pepper noise from the image. This paper discusses the aforesaid algorithm for automated feature extraction, necessity of deployment of GPUs for the same; system-level challenges and quantifies the benefits of integrating GPUs in such environment. The results demonstrate that substantial enhancement in performance margin can be achieved with the best utilization of GPU resources and an efficient parallelization strategy. Performance results in comparison with the conventional computing scenario have provided a speedup of 20x, on realization of this parallelizing strategy.
Group Evolution Discovery in Social Networks
Venue: arXiv cs.SI 2013
Year: 2013

Group extraction and their evolution are among the topics which arouse the greatest interest in the domain of social network analysis. However, while the grouping methods in social networks are developed very dynamically, the methods of group evolution discovery and analysis are still uncharted territory on the social network analysis map. Therefore the new method for the group evolution discovery called GED is proposed in this paper. Additionally, the results of the first experiments on the email based social network together with comparison with two other methods of group evolution discovery are presented.
Rate-Distortion-Based Physical Layer Secrecy with Applications to Multimode Fiber
Venue: arXiv cs.CR 2013
Year: 2013

Optical networks are vulnerable to physical layer attacks; wiretappers can improperly receive messages intended for legitimate recipients. Our work considers an aspect of this security problem within the domain of multimode fiber (MMF) transmission. MMF transmission can be modeled via a broadcast channel in which both the legitimate receiver's and wiretapper's channels are multiple-input-multiple-output complex Gaussian channels. Source-channel coding analyses based on the use of distortion as the metric for secrecy are developed. Alice has a source sequence to be encoded and transmitted over this broadcast channel so that the legitimate user Bob can reliably decode while forcing the distortion of wiretapper, or eavesdropper, Eve's estimate as high as possible. Tradeoffs between transmission rate and distortion under two extreme scenarios are examined: the best case where Eve has only her channel output and the worst case where she also knows the past realization of the source. It is shown that under the best case, an operationally separate source-channel coding scheme guarantees maximum distortion at the same rate as needed for reliable transmission. Theoretical bounds are given, and particularized for MMF. Numerical results showing the rate distortion tradeoff are presented and compared with corresponding results for the perfect secrecy case.
Range Counting Coresets for Uncertain Data
Venue: arXiv cs.CG 2013
Year: 2013

We study coresets for various types of range counting queries on uncertain data. In our model each uncertain point has a probability density describing its location, sometimes defined as k distinct locations. Our goal is to construct a subset of the uncertain points, including their locational uncertainty, so that range counting queries can be answered by just examining this subset. We study three distinct types of queries. RE queries return the expected number of points in a query range. RC queries return the number of points in the range with probability at least a threshold. RQ queries returns the probability that fewer than some threshold fraction of the points are in the range. In both RC and RQ coresets the threshold is provided as part of the query. And for each type of query we provide coreset constructions with approximation-size tradeoffs. We show that random sampling can be used to construct each type of coreset, and we also provide significantly improved bounds using discrepancy-based approaches on axis-aligned range queries.
Cost-Effective Broadcast in Cellular Networks
Venue: arXiv cs.NI 2013
Year: 2013

In recent years, video-related services such as YouTube and Netflix have generated huge amounts of traffic and the network neutrality debate has emerged as a major issue. In this paper, we consider feasibility of using a hybrid of unicast and broadcast in cellular networks for high-traffic services (e.g., video streaming), from the perspective of cost effectiveness. To reflect spatial characteristics of base stations (BSs) and mobile users (MUs), we use the stochastic geometry approach where BSs and MUs are modeled as independent homogeneous Poisson point processes (PPPs). With these assumptions and results, we show how to cope with the trade-off between broadcast and unicast for providing the service with affordable cost levels and reduced network load. Moreover, we propose the so called periodic broadcasting service, where popular video contents are periodically broadcast over cellular networks. This service will make a positive impact on the network neutrality debate by stimulating cooperation between mobile network operators (MNOs) and content providers (CPs).
Sparse Coding and Dictionary Learning for Symmetric Positive Definite Matrices: A Kernel Approach
Venue: arXiv cs.LG 2013
Year: 2013

Recent advances suggest that a wide range of computer vision problems can be addressed more appropriately by considering non-Euclidean geometry. This paper tackles the problem of sparse coding and dictionary learning in the space of symmetric positive definite matrices, which form a Riemannian manifold. With the aid of the recently introduced Stein kernel (related to a symmetric version of Bregman matrix divergence), we propose to perform sparse coding by embedding Riemannian manifolds into reproducing kernel Hilbert spaces. This leads to a convex and kernel version of the Lasso problem, which can be solved efficiently. We furthermore propose an algorithm for learning a Riemannian dictionary (used for sparse coding), closely tied to the Stein kernel. Experiments on several classification tasks (face recognition, texture classification, person re-identification) show that the proposed sparse coding approach achieves notable improvements in discrimination accuracy, in comparison to state-of-the-art methods such as tensor sparse coding, Riemannian locality preserving projection, and symmetry-driven accumulation of local features.
On the Optimality of Linear Precoding for Secrecy in the MIMO Broadcast Channel
Venue: arXiv cs.IT 2013
Year: 2013

We study the optimality of linear precoding for the two-receiver multiple-input multiple-output (MIMO) Gaussian broadcast channel (BC) with confidential messages. Secret dirty-paper coding (SDPC) is optimal under an input covariance constraint, but there is no computable secrecy capacity expression for the general MIMO case under an average power constraint. In principle, for this case, the secrecy capacity region could be found through an exhaustive search over the set of all possible matrix power constraints. Clearly, this search, coupled with the complexity of dirty-paper encoding and decoding, motivates the consideration of low complexity linear precoding as an alternative. We prove that for a two-user MIMO Gaussian BC under an input covariance constraint, linear precoding is optimal and achieves the same secrecy rate region as S-DPC if the input covariance constraint satisfies a specific condition, and we characterize the corresponding optimal linear precoders. We then use this result to derive a closed-form sub-optimal algorithm based on linear precoding for an average power constraint. Numerical results indicate that the secrecy rate region achieved by this algorithm is close to that obtained by the optimal S-DPC approach with a search over all suitable input covariance matrices.
When Distributed Computation is Communication Expensive
Venue: arXiv cs.DS 2013
Year: 2013

We consider a number of fundamental statistical and graph problems in the message-passing model, where we have $k$ machines (sites), each holding a piece of data, and the machines want to jointly solve a problem defined on the union of the $k$ data sets. The communication is point-to-point, and the goal is to minimize the total communication among the $k$ machines. This model captures all point-to-point distributed computational models with respect to minimizing communication costs. Our analysis shows that exact computation of many statistical and graph problems in this distributed setting requires a prohibitively large amount of communication, and often one cannot improve upon the communication of the simple protocol in which all machines send their data to a centralized server. Thus, in order to obtain protocols that are communication-efficient, one has to allow approximation, or investigate the distribution or layout of the data sets.
A Health Monitoring System for Elder and Sick Persons
Venue: arXiv cs.CV 2013
Year: 2013

This paper discusses a vision based health monitoring system which would be very easy in use and deployment. Elder and sick people who are not able to talk or walk they are dependent on other human beings for their daily needs and need continuous monitoring. The developed system provides facility to the sick or elder person to describe his or her need to their caretaker in lingual description by showing particular hand gesture with the developed system. This system uses fingertip detection technique for gesture extraction and artificial neural network for gesture classification and recognition. The system is able to work in different light conditions and can be connected to different devices to announce users need on a distant location.
Product line Development Architectural Model
Venue: arXiv cs.SE 2013
Year: 2013

Products with new features need to be introduced on the market in a rapid pace and organizations need to speed up their development process. The ordinary way to develop products, one at a time, is not time efficient enough and is costly. Reuse has been suggested as a solution, but to achieve effective reuse within an organization a planned and proactive effort must be used. Product lines are the most promising technique and it increases productivity and software quality and decreases time-to-market. This paper describes the architecture of product line engineering process and also addresses what the design issues of product line architecture are and how a UML profile looks like for a product line by referring to the basic aspects of a case study, CelsiusTech in its Naval Product Line, SS2000.
A New Analysis of Compressive Sensing by Stochastic Proximal Gradient Descent
Venue: arXiv cs.DS 2013
Year: 2013

In this manuscript, we analyze the sparse signal recovery (compressive sensing) problem from the perspective of convex optimization by stochastic proximal gradient descent. This view allows us to significantly simplify the recovery analysis of compressive sensing. More importantly, it leads to an efficient optimization algorithm for solving the regularized optimization problem related to the sparse recovery problem. Compared to the existing approaches, there are two advantages of the proposed algorithm. First, it enjoys a geometric convergence rate and therefore is computationally efficient. Second, it guarantees that the support set of any intermediate solution generated by the proposed algorithm is concentrated on the support set of the optimal solution.
On Synchronization of Interdependent Networks
Venue: arXiv cs.SY 2013
Year: 2013

It is well-known that the synchronization of diffusively-coupled systems on networks strongly depends on the network topology. In particular, the so-called algebraic connectivity $μ_{N-1}$, or the smallest non-zero eigenvalue of the discrete Laplacian operator plays a crucial role on synchronization, graph partitioning, and network robustness. In our study, synchronization is placed in the general context of networks-of-networks, where single network models are replaced by a more realistic hierarchy of interdependent networks. The present work shows, analytically and numerically, how the algebraic connectivity experiences sharp transitions after the addition of sufficient links among interdependent networks.
Hands-free Evolution of 3D-printable Objects via Eye Tracking
Venue: arXiv cs.NE 2013
Year: 2013

Interactive evolution has shown the potential to create amazing and complex forms in both 2-D and 3-D settings. However, the algorithm is slow and users quickly become fatigued. We propose that the use of eye tracking for interactive evolution systems will both reduce user fatigue and improve evolutionary success. We describe a systematic method for testing the hypothesis that eye tracking driven interactive evolution will be a more successful and easier-to-use design method than traditional interactive evolution methods driven by mouse clicks. We provide preliminary results that support the possibility of this proposal, and lay out future work to investigate these advantages in extensive clinical trials.
Homogeneous Weights and Möbius Functions on Finite Rings
Venue: arXiv cs.IT 2013
Year: 2013

The homogeneous weights and the Möbius functions and Euler phi-functions on finite rings are discussed; some computational formulas for these functions on finite principal ideal rings are characterized; for the residue rings of integers, they are reduced to the classical number-theoretical Möbius functions and the classical number-theoretical Euler phi-functions.
Constraint Satisfaction over Generalized Staircase Constraints
Venue: arXiv cs.AI 2013
Year: 2013

One of the key research interests in the area of Constraint Satisfaction Problem (CSP) is to identify tractable classes of constraints and develop efficient solutions for them. In this paper, we introduce generalized staircase (GS) constraints which is an important generalization of one such tractable class found in the literature, namely, staircase constraints. GS constraints are of two kinds, down staircase (DS) and up staircase (US). We first examine several properties of GS constraints, and then show that arc consistency is sufficient to determine a solution to a CSP over DS constraints. Further, we propose an optimal O(cd) time and space algorithm to compute arc consistency for GS constraints where c is the number of constraints and d is the size of the largest domain. Next, observing that arc consistency is not necessary for solving a DSCSP, we propose a more efficient algorithm for solving it. With regard to US constraints, arc consistency is not known to be sufficient to determine a solution, and therefore, methods such as path consistency or variable elimination are required. Since arc consistency acts as a subroutine for these existing methods, replacing it by our optimal O(cd) arc consistency algorithm produces a more efficient method for solving a USCSP.
Extended Object Tracking with Random Hypersurface Models
Venue: arXiv cs.SY 2013
Year: 2013

The Random Hypersurface Model (RHM) is introduced that allows for estimating a shape approximation of an extended object in addition to its kinematic state. An RHM represents the spatial extent by means of randomly scaled versions of the shape boundary. In doing so, the shape parameters and the measurements are related via a measurement equation that serves as the basis for a Gaussian state estimator. Specific estimators are derived for elliptic and star-convex shapes.
Planning of Cellular Networks Enhanced by Energy Harvesting
Venue: arXiv cs.ET 2013
Year: 2013

We pose a novel cellular network planning problem, considering the use of renewable energy sources and a fundamentally new concept of energy balancing, and propose a novel algorithm to solve it. In terms of the network capital and operational expenditure, we conclude that savings can be made by enriching cellular infrastructure with energy harvesting sources, in comparison to traditional deployment methods.
Kadanoff Sand Pile Model. Avalanche Structure and Wave Shape
Venue: arXiv cs.DM 2013
Year: 2013

Sand pile models are dynamical systems describing the evolution from $N$ stacked grains to a stable configuration. It uses local rules to depict grain moves and iterate it until reaching a fixed configuration from which no rule can be applied. Physicists L. Kadanoff {\em et al} inspire KSPM, extending the well known {\em Sand Pile Model} (SPM). In KSPM($D$), we start from a pile of $N$ stacked grains and apply the rule: $D\!-\!1$ grains can fall from column $i$ onto columns $i+1,i+2,\dots,i+D\!-\!1$ if the difference of height between columns $i$ and $i\!+\!1$ is greater or equal to $D$. Toward the study of fixed points (stable configurations on which no grain can move) obtained from $N$ stacked grains, we propose an iterative study of KSPM evolution consisting in the repeated addition of one grain on a heap of sand, triggering an avalanche at each iteration. We develop a formal background for the study of avalanches, resumed in a finite state word transducer, and explain how this transducer may be used to predict the form of fixed points. Further precise developments provide a plain formula for fixed points of KSPM(3), showing the emergence of a wavy shape.
Object Tracking in Videos: Approaches and Issues
Venue: arXiv cs.CV 2013
Year: 2013

Mobile object tracking has an important role in the computer vision applications. In this paper, we use a tracked target-based taxonomy to present the object tracking algorithms. The tracked targets are divided into three categories: points of interest, appearance and silhouette of mobile objects. Advantages and limitations of the tracking approaches are also analyzed to find the future directions in the object tracking domain.