OpenRaiser/Intern-Atlas huggingface dataset:
Multidimensional Digital Smoothing Filters for Target Detection
Venue: arXiv cs.CV 2015
Year: 2015

Recursive, causal and non-causal, multidimensional digital filters, with infinite impulse responses and maximally flat magnitude and delay responses in the low-frequency region, are designed to negate correlated clutter and interference in the background and to accumulate power due to dim targets in the foreground of a surveillance sensor. Expressions relating mean impulse-response duration, frequency selectivity and group delay, to low-order linear-difference-equation coefficients are derived using discrete Laguerre polynomials and discounted least-squares regression, then verified through simulation.
Scheduling for Multi-Camera Surveillance in LTE Networks
Venue: arXiv cs.NI 2015
Year: 2015

Wireless surveillance in cellular networks has become increasingly important, while commercial LTE surveillance cameras are also available nowadays. Nevertheless, most scheduling algorithms in the literature are throughput, fairness, or profit-based approaches, which are not suitable for wireless surveillance. In this paper, therefore, we explore the resource allocation problem for a multi-camera surveillance system in 3GPP Long Term Evolution (LTE) uplink (UL) networks. We minimize the number of allocated resource blocks (RBs) while guaranteeing the coverage requirement for surveillance systems in LTE UL networks. Specifically, we formulate the Camera Set Resource Allocation Problem (CSRAP) and prove that the problem is NP-Hard. We then propose an Integer Linear Programming formulation for general cases to find the optimal solution. Moreover, we present a baseline algorithm and devise an approximation algorithm to solve the problem. Simulation results based on a real surveillance map and synthetic datasets manifest that the number of allocated RBs can be effectively reduced compared to the existing approach for LTE networks.
Communication Using a Large-Scale Array of Ubiquitous Antennas: A Geometry Approach
Venue: arXiv cs.IT 2015
Year: 2015

The recent trends of densification and centralized signal processing in radio access networks suggest that future networks may comprise ubiquitous antennas coordinated to form a network-wide gigantic array, referred to as the ubiquitous array (UA). In this paper, the UA communication techniques are designed and analyzed based on a geometric model. Specifically, the UA is modeled as a continuous circular/spherical array enclosing target users and free-space propagation is assumed. First, consider the estimation of multiuser UA channels induced by user locations. Given single pilot symbols, a novel channel estimation scheme is proposed that decomposes training signals into Fourier/Laplace series and thereby translates multiuser channel estimation into peak detection of a derive function of location. The process is shown to suppress noise. Moreover, it is proved that estimation error due to interference diminishes with the increasing minimum user-separation distance following the power law, where the exponent is 1/3 and 1 for the circular and spherical UA, respectively. If orthogonal pilot sequences are used, channel estimation is found to be perfect. Next, consider channel-conjugate data transmission that maximizes received signal power. The power of interference between two users is shown to decay with the increasing user-separation distance sub-linearly and super-linearly for the circular and spherical UA, respectively. Furthermore, a novel multiuser precoding design is proposed by exciting different phase modes of the UA and controlling the mode weight factors to null interference. The number of available degrees of freedom for interference nulling using the UA is proved to be proportional to the minimum user-separation distance.
Price Competition in Networked Markets: How do monopolies impact social welfare?
Venue: arXiv cs.GT 2015
Year: 2015

We study the efficiency of allocations in large markets with a network structure where every seller owns an edge in a graph and every buyer desires a path connecting some nodes. While it is known that stable allocations in such settings can be very inefficient, the exact properties of equilibria in markets with multiple sellers are not fully understood even in single-source single-sink networks. In this work, we show that for a large class of natural buyer demand functions, we are guaranteed the existence of an equilibrium with several desirable properties. The crucial insight that we gain into the equilibrium structure allows us to obtain tight bounds on efficiency in terms of the various parameters governing the market, especially the number of monopolies M. All of our efficiency results extend to markets without the network structure. While it is known that monopolies can cause large inefficiencies in general, our main results for single-source single-sink networks indicate that for several natural demand functions the efficiency only drops linearly with M. For example, for concave demand we prove that the efficiency loss is at most a factor 1+M/2 from the optimum, for demand with monotone hazard rate it is at most 1+M, and for polynomial demand the efficiency decreases logarithmically with M. In contrast to previous work that showed that monopolies may adversely affect welfare, our main contribution is showing that monopolies may not be as `evil' as they are made out to be; the loss in efficiency is bounded in many natural markets. Finally, we consider more general, multiple-source networks and show that in the absence of monopolies, mild assumptions on the network topology guarantee an equilibrium that maximizes social welfare.
Interactive Fingerprinting Codes and the Hardness of Preventing False Discovery
Venue: arXiv cs.CR 2015
Year: 2015

We show an essentially tight bound on the number of adaptively chosen statistical queries that a computationally efficient algorithm can answer accurately given $n$ samples from an unknown distribution. A statistical query asks for the expectation of a predicate over the underlying distribution, and an answer to a statistical query is accurate if it is "close" to the correct expectation over the distribution. This question was recently studied by Dwork et al., who showed how to answer $\tildeΩ(n^2)$ queries efficiently, and also by Hardt and Ullman, who showed that answering $\tilde{O}(n^3)$ queries is hard. We close the gap between the two bounds and show that, under a standard hardness assumption, there is no computationally efficient algorithm that, given $n$ samples from an unknown distribution, can give valid answers to $O(n^2)$ adaptively chosen statistical queries. An implication of our results is that computationally efficient algorithms for answering arbitrary, adaptively chosen statistical queries may as well be differentially private. We obtain our results using a new connection between the problem of answering adaptively chosen statistical queries and a combinatorial object called an interactive fingerprinting code. In order to optimize our hardness result, we give a new Fourier-analytic approach to analyzing fingerprinting codes that is simpler, more flexible, and yields better parameters than previous constructions.
Rank-metric codes and their duality theory
Venue: arXiv cs.IT 2015
Year: 2015

We compare the two duality theories of rank-metric codes proposed by Delsarte and Gabidulin, proving that the former generalizes the latter. We also give an elementary proof of MacWilliams identities for the general case of Delsarte rank-metric codes. The identities which we derive are very easy to handle, and allow us to re-establish in a very concise way the main results of the theory of rank-metric codes first proved by Delsarte employing the theory of association schemes and regular semilattices. We also show that our identities imply as a corollary the original MacWilliams identities established by Delsarte. We describe how the minimum and maximum rank of a rank-metric code relate to the minimum and maximum rank of the dual code, giving some bounds and characterizing the codes attaining them. Then we study optimal anticodes in the rank metric, describing them in terms of optimal codes (namely, MRD codes). In particular, we prove that the dual of an optimal anticode is an optimal anticode. Finally, as an application of our results to a classical problem in enumerative combinatorics, we derive both a recursive and an explicit formula for the number of $k \times m$ matrices over a finite field with given rank and $h$-trace.
The invariant extended Kalman filter as a stable observer
Venue: arXiv cs.SY 2015
Year: 2015

We analyze the convergence aspects of the invariant extended Kalman filter (IEKF), when the latter is used as a deterministic non-linear observer on Lie groups, for continuous-time systems with discrete observations. One of the main features of invariant observers for left-invariant systems on Lie groups is that the estimation error is autonomous. In this paper we first generalize this result by characterizing the (much broader) class of systems for which this property holds. Then, we leverage the result to prove for those systems the local stability of the IEKF around any trajectory, under the standard conditions of the linear case. One mobile robotics example and one inertial navigation example illustrate the interest of the approach. Simulations evidence the fact that the EKF is capable of diverging in some challenging situations, where the IEKF with identical tuning keeps converging.
Performance Evaluation of Flow Allocation with Successive Interference Cancelation for Random Access WMNs
Venue: arXiv cs.NI 2015
Year: 2015

In this study we explore the performance gain that can be achieved at the network level by employing successive interference cancelation (SIC) instead of treating interference as noise for random access wireless mesh networks with multi-packet reception capabilities. More precisely we explore both the throughput and the delay of a distributed flow allocation scheme aimed at maximizing average aggregate flow throughput while also providing bounded delay combined with SIC. Simulation results derived from three simple topologies show that the gain over treating interference as noise for this scheme can be up to $15\%$ for an SINR threshold value equal to $0.5$. For SINR threshold values as high as $2.0$ however, this gain is either insignificant or treating interference as noise proves a better practice. The reason is that although SIC improves the throughput on a specific link, it also increases the interference imposed on neighboring receivers. We also show that the gain of applying SIC is more profound in cases of a large degree of asymmetry among interfering links.
NetworkRepository: An Interactive Data Repository with Multi-scale Visual Analytics
Venue: arXiv cs.DL 2015
Year: 2015

Network Repository (NR) is the first interactive data repository with a web-based platform for visual interactive analytics. Unlike other data repositories (e.g., UCI ML Data Repository, and SNAP), the network data repository (networkrepository.com) allows users to not only download, but to interactively analyze and visualize such data using our web-based interactive graph analytics platform. Users can in real-time analyze, visualize, compare, and explore data along many different dimensions. The aim of NR is to make it easy to discover key insights into the data extremely fast with little effort while also providing a medium for users to share data, visualizations, and insights. Other key factors that differentiate NR from the current data repositories is the number of graph datasets, their size, and variety. While other data repositories are static, they also lack a means for users to collaboratively discuss a particular dataset, corrections, or challenges with using the data for certain applications. In contrast, we have incorporated many social and collaborative aspects into NR in hopes of further facilitating scientific research (e.g., users can discuss each graph, post observations, visualizations, etc.).
Memory Networks
Venue: arXiv cs.AI 2015
Year: 2015

We describe a new class of learning models called memory networks. Memory networks reason with inference components combined with a long-term memory component; they learn how to use these jointly. The long-term memory can be read and written to, with the goal of using it for prediction. We investigate these models in the context of question answering (QA) where the long-term memory effectively acts as a (dynamic) knowledge base, and the output is a textual response. We evaluate them on a large-scale QA task, and a smaller, but more complex, toy task generated from a simulated world. In the latter, we show the reasoning power of such models by chaining multiple supporting sentences to answer questions that require understanding the intension of verbs.
Maze solving Algorithm for line following robot and derivation of linear path distance from nonlinear path
Venue: arXiv cs.RO 2015
Year: 2015

In this paper we have discussed a unique general algorithm for exploring and solving any kind of line maze with another simple one for simple mazes without loops or loops having highest two branches none of which are inward. For the general algorithm, we need a method to map the whole maze, which is required if the maze is complex. The proposed maze mapping system is based on coordinate system and after mapping the whole maze as a graph in standard 'Adjacency-list representation' method, shortest path and shortest time path was extracted using Dijkstra's algorithm. In order to find the coordinates of the turning points and junctions, linear distance between the points are needed, for which wheel encoder was used. However, due to non-linear movement of robot, the directly measured distance from the encoder has some error and to remove this error an idea is built up which ended by deriving equations that gives us almost exact linear distance between two points from the reading of wheel encoder of the robot moving in a non-linear path.
Making the Best of Limited Memory in Multi-Player Discounted Sum Games
Venue: arXiv cs.GT 2015
Year: 2015

In this paper, we establish the existence of optimal bounded memory strategy profiles in multi-player discounted sum games. We introduce a non-deterministic approach to compute optimal strategy profiles with bounded memory. Our approach can be used to obtain optimal rewards in a setting where a powerful player selects the strategies of all players for Nash and leader equilibria, where in leader equilibria the Nash condition is waived for the strategy of this powerful player. The resulting strategy profiles are optimal for this player among all strategy profiles that respect the given memory bound, and the related decision problem is NP-complete. We also provide simple examples, which show that having more memory will improve the optimal strategy profile, and that sufficient memory to obtain optimal strategy profiles cannot be inferred from the structure of the game.
Optimal Adaptive Random Multiaccess in Energy Harvesting Wireless Sensor Networks
Venue: arXiv cs.IT 2015
Year: 2015

Wireless sensors can integrate rechargeable batteries and energy-harvesting (EH) devices to enable long-term, autonomous operation, thus requiring intelligent energy management to limit the adverse impact of energy outages. This work considers a network of EH wireless sensors, which report packets with a random utility value to a fusion center (FC) over a shared wireless channel. Decentralized access schemes are designed, where each node performs a local decision to transmit/discard a packet, based on an estimate of the packet's utility, its own energy level, and the scenario state of the EH process, with the objective to maximize the average long-term aggregate utility of the packets received at the FC. Due to the non-convex structure of the problem, an approximate optimization is developed by resorting to a mathematical artifice based on a game theoretic formulation of the multiaccess scheme, where the nodes do not behave strategically, but rather attempt to maximize a \emph{common} network utility with respect to their own policy. The symmetric Nash equilibrium (SNE) is characterized, where all nodes employ the same policy; its uniqueness is proved, and it is shown to be a local maximum of the original problem. An algorithm to compute the SNE is presented, and a heuristic scheme is proposed, which is optimal for large battery capacity. It is shown numerically that the SNE typically achieves near-optimal performance, within 3% of the optimal policy, at a fraction of the complexity, and two operational regimes of EH-networks are identified and analyzed: an energy-limited scenario, where energy is scarce and the channel is under-utilized, and a network-limited scenario, where energy is abundant and the shared wireless channel represents the bottleneck of the system.
Randomized Structural Sparsity via Constrained Block Subsampling for Improved Sensitivity of Discriminative Voxel Identification
Venue: arXiv cs.CV 2015
Year: 2015

In this paper, we consider voxel selection for functional Magnetic Resonance Imaging (fMRI) brain data with the aim of finding a more complete set of probably correlated discriminative voxels, thus improving interpretation of the discovered potential biomarkers. The main difficulty in doing this is an extremely high dimensional voxel space and few training samples, resulting in unreliable feature selection. In order to deal with the difficulty, stability selection has received a great deal of attention lately, especially due to its finite sample control of false discoveries and transparent principle for choosing a proper amount of regularization. However, it fails to make explicit use of the correlation property or structural information of these discriminative features and leads to large false negative rates. In other words, many relevant but probably correlated discriminative voxels are missed. Thus, we propose a new variant on stability selection "randomized structural sparsity", which incorporates the idea of structural sparsity. Numerical experiments demonstrate that our method can be superior in controlling for false negatives while also keeping the control of false positives inherited from stability selection.
Evolvability signatures of generative encodings: beyond standard performance benchmarks
Venue: arXiv cs.NE 2015
Year: 2015

Evolutionary robotics is a promising approach to autonomously synthesize machines with abilities that resemble those of animals, but the field suffers from a lack of strong foundations. In particular, evolutionary systems are currently assessed solely by the fitness score their evolved artifacts can achieve for a specific task, whereas such fitness-based comparisons provide limited insights about how the same system would evaluate on different tasks, and its adaptive capabilities to respond to changes in fitness (e.g., from damages to the machine, or in new situations). To counter these limitations, we introduce the concept of "evolvability signatures", which picture the post-mutation statistical distribution of both behavior diversity (how different are the robot behaviors after a mutation?) and fitness values (how different is the fitness after a mutation?). We tested the relevance of this concept by evolving controllers for hexapod robot locomotion using five different genotype-to-phenotype mappings (direct encoding, generative encoding of open-loop and closed-loop central pattern generators, generative encoding of neural networks, and single-unit pattern generators (SUPG)). We observed a predictive relationship between the evolvability signature of each encoding and the number of generations required by hexapods to adapt from incurred damages. Our study also reveals that, across the five investigated encodings, the SUPG scheme achieved the best evolvability signature, and was always foremost in recovering an effective gait following robot damages. Overall, our evolvability signatures neatly complement existing task-performance benchmarks, and pave the way for stronger foundations for research in evolutionary robotics.
Mixing Color Coding-Related Techniques
Venue: arXiv cs.DS 2015
Year: 2015

Narrow sieves, representative sets and divide-and-color are three breakthrough color coding-related techniques, which led to the design of extremely fast parameterized algorithms. We present a novel family of strategies for applying mixtures of them. This includes: (a) a mix of representative sets and narrow sieves; (b) a faster computation of representative sets under certain separateness conditions, mixed with divide-and-color and a new technique, "balanced cutting"; (c) two mixtures of representative sets, iterative compression and a new technique, "unbalanced cutting". We demonstrate our strategies by obtaining, among other results, significantly faster algorithms for $k$-Internal Out-Branching and Weighted 3-Set $k$-Packing, and a framework for speeding-up the previous best deterministic algorithms for $k$-Path, $k$-Tree, $r$-Dimensional $k$-Matching, Graph Motif and Partial Cover.
Stability for Receding-horizon Stochastic Model Predictive Control
Venue: arXiv cs.SY 2015
Year: 2015

A stochastic model predictive control (SMPC) approach is presented for discrete-time linear systems with arbitrary time-invariant probabilistic uncertainties and additive Gaussian process noise. Closed-loop stability of the SMPC approach is established by appropriate selection of the cost function. Polynomial chaos is used for uncertainty propagation through system dynamics. The performance of the SMPC approach is demonstrated using the Van de Vusse reactions.
Temporal Logic Control for Stochastic Linear Systems using Abstraction Refinement of Probabilistic Games
Venue: arXiv cs.SY 2015
Year: 2015

We consider the problem of computing the set of initial states of a dynamical system such that there exists a control strategy to ensure that the trajectories satisfy a temporal logic specification with probability 1 (almost-surely). We focus on discrete-time, stochastic linear dynamics and specifications given as formulas of the Generalized Reactivity(1) fragment of Linear Temporal Logic over linear predicates in the states of the system. We propose a solution based on iterative abstraction-refinement, and turn-based 2-player probabilistic games. While the theoretical guarantee of our algorithm after any finite number of iterations is only a partial solution, we show that if our algorithm terminates, then the result is the set of satisfying initial states. Moreover, for any (partial) solution our algorithm synthesizes witness control strategies to ensure almost-sure satisfaction of the temporal logic specification. We demonstrate our approach on an illustrative case study.
Feature Selection Based on Confidence Machine
Venue: arXiv cs.LG 2015
Year: 2015

In machine learning and pattern recognition, feature selection has been a hot topic in the literature. Unsupervised feature selection is challenging due to the loss of labels which would supply the related information.How to define an appropriate metric is the key for feature selection. We propose a filter method for unsupervised feature selection which is based on the Confidence Machine. Confidence Machine offers an estimation of confidence on a feature'reliability. In this paper, we provide the math model of Confidence Machine in the context of feature selection, which maximizes the relevance and minimizes the redundancy of the selected feature. We compare our method against classic feature selection methods Laplacian Score, Pearson Correlation and Principal Component Analysis on benchmark data sets. The experimental results demonstrate the efficiency and effectiveness of our method.