OpenRaiser/Intern-Atlas huggingface dataset:
A Verified Information-Flow Architecture
Venue: arXiv cs.PL 2016
Year: 2016

SAFE is a clean-slate design for a highly secure computer system, with pervasive mechanisms for tracking and limiting information flows. At the lowest level, the SAFE hardware supports fine-grained programmable tags, with efficient and flexible propagation and combination of tags as instructions are executed. The operating system virtualizes these generic facilities to present an information-flow abstract machine that allows user programs to label sensitive data with rich confidentiality policies. We present a formal, machine-checked model of the key hardware and software mechanisms used to dynamically control information flow in SAFE and an end-to-end proof of noninterference for this model. We use a refinement proof methodology to propagate the noninterference property of the abstract machine down to the concrete machine level. We use an intermediate layer in the refinement chain that factors out the details of the information-flow control policy and devise a code generator for compiling such information-flow policies into low-level monitor code. Finally, we verify the correctness of this generator using a dedicated Hoare logic that abstracts from low-level machine instructions into a reusable set of verified structured code generators.
Design and locomotion control of soft robot using friction manipulation and motor-tendon actuation
Venue: arXiv cs.RO 2016
Year: 2016

Robots built from soft materials can alter their shape and size in a particular profile. This shape-changing ability could be extremely helpful for rescue robots and those operating in unknown terrains and environments. In changing shape, soft materials also store and release elastic energy, a feature that can be exploited for effective robot movement. However, design and control of these moving soft robots are non-trivial. The research presents design methodology for a 3D-printed, motor-tendon actuated soft robot capable of locomotion. In addition to shape change, the robot uses friction manipulation mechanisms to effect locomotion. The motor-tendon actuators comprise of nylon tendons embedded inside the soft body structure along a given path with one end fixed on the body and the other attached to a motor. These actuators directly control the deformation of the soft body which influences the robot locomotion behavior. Static stress analysis is used as a tool for designing the shape of the paths of these tendons embedded inside the body. The research also presents a novel model-free learning-based control approach for soft robots which interact with the environment at discrete contact points. This approach involves discretization of factors dominating robot-environment interactions as states, learning of the results as robot transitions between these robot states and evaluation of desired periodic state control sequences optimizing a cost function corresponding to a locomotion task (rotation or translation). The clever discretization allows the framework to exist in robot's task space, hence, facilitating calculation of control sequences without modeling the actuator, body material or details of the friction mechanisms. The flexibility of the framework is experimentally explored by applying it to robots with different friction mechanisms and different shapes of tendon paths.
Localisation of directional scale-discretised wavelets on the sphere
Venue: arXiv cs.IT 2016
Year: 2016

Scale-discretised wavelets yield a directional wavelet framework on the sphere where a signal can be probed not only in scale and position but also in orientation. Furthermore, a signal can be synthesised from its wavelet coefficients exactly, in theory and practice (to machine precision). Scale-discretised wavelets are closely related to spherical needlets (both were developed independently at about the same time) but relax the axisymmetric property of needlets so that directional signal content can be probed. Needlets have been shown to satisfy important quasi-exponential localisation and asymptotic uncorrelation properties. We show that these properties also hold for directional scale-discretised wavelets on the sphere and derive similar localisation and uncorrelation bounds in both the scalar and spin settings. Scale-discretised wavelets can thus be considered as directional needlets.
RSCM Technology for Developing Runtime-Reconfigurable Telecommunication Applications
Venue: arXiv cs.SE 2016
Year: 2016

Runtime reconfiguration is a fundamental requirement of many telecommunication applications which also has been addressed by management standards like CMIP, 3GPP TS 32.602, and NETCONF. Two basic commands considered by these standards are CREATE and DELETE which operate on managed objects inside an application. The available configuration management technologies, like JMX, OSGi, and Fractal, do not support the CREATE and DELETE reconfiguration commands of the telecommunication standards. In this paper, we introduce a novel technology, called RSCM, for development of runtime reconfigurable applications complying with the telecommunication standards. The RSCM subagent takes the responsibility of loading the application from the configuration file, executing the runtime reconfiguration commands (including CREATE and DELETE), enforcing validity of the configuration state, and updating the configuration file according to the latest reconfiguration commands. We exploit the modular and object oriented features of the XML technology for storing the configuration state of a program in a configuration file. The software development process is tailored such that the design of XML schemas of managed classes is performed parallel to the design of software classes. In addition, a novel programming approach based on indirect referencing is proposed which allows safe and almost immediate deletion of managed objects at runtime. This indirect referencing mechanism affects the implementation of associations in class diagrams and prevents methods of a class to use the this pointer freely. The RSCM technology has been successfully used in several commercial telecommunication applications; including an SMS service center, an SMS gateway, and an SMS hub.
Adaptive-Robust Control of a Class of Uncertain Nonlinear Systems Utilizing Time-Delayed Input and Position Feedback
Venue: arXiv cs.SY 2016
Year: 2016

In this paper, the tracking control problem of a class of Euler-Lagrange systems subjected to unknown uncertainties is addressed and an adaptive-robust control strategy, christened as Time-Delayed Adaptive Robust Control (TARC) is presented. The proposed control strategy approximates the unknown dynamics through time-delayed logic, and the switching logic provides robustness against the approximation error. The novel adaptation law for the switching gain, in contrast to the conventional adaptive-robust control methodologies, does not require either nominal modelling or predefined bounds of the uncertainties. Also, the proposed adaptive law circumvents the overestimation-underestimation problem of switching gain. The state derivatives in the proposed control law is estimated from past data of the state to alleviate the measurement error when state derivatives are not available directly. Moreover, a new stability notion for time-delayed control is proposed which in turn provides a selection criterion for controller gain and sampling interval. Experimental result of the proposed methodology using a nonholonomic wheeled mobile robot (WMR) is presented and improved tracking accuracy of the proposed control law is noted compared to time-delayed control and adaptive sliding mode control.
Channel Vector Subspace Estimation from Low-Dimensional Projections
Venue: arXiv cs.IT 2016
Year: 2016

Massive MIMO is a variant of multiuser MIMO where the number of base-station antennas $M$ is very large (typically 100), and generally much larger than the number of spatially multiplexed data streams (typically 10). Unfortunately, the front-end A/D conversion necessary to drive hundreds of antennas, with a signal bandwidth of the order of 10 to 100 MHz, requires very large sampling bit-rate and power consumption. In order to reduce such implementation requirements, Hybrid Digital-Analog architectures have been proposed. In particular, our work in this paper is motivated by one of such schemes named Joint Spatial Division and Multiplexing (JSDM), where the downlink precoder (resp., uplink linear receiver) is split into the product of a baseband linear projection (digital) and an RF reconfigurable beamforming network (analog), such that only a reduced number $m \ll M$ of A/D converters and RF modulation/demodulation chains is needed. In JSDM, users are grouped according to the similarity of their channel dominant subspaces, and these groups are separated by the analog beamforming stage, where the multiplexing gain in each group is achieved using the digital precoder. Therefore, it is apparent that extracting the channel subspace information of the $M$-dim channel vectors from snapshots of $m$-dim projections, with $m \ll M$, plays a fundamental role in JSDM implementation. In this paper, we develop novel efficient algorithms that require sampling only $m = O(2\sqrt{M})$ specific array elements according to a coprime sampling scheme, and for a given $p \ll M$, return a $p$-dim beamformer that has a performance comparable with the best p-dim beamformer that can be designed from the full knowledge of the exact channel covariance matrix. We assess the performance of our proposed estimators both analytically and empirically via numerical simulations.
Multivariate Median Filters and Partial Differential Equations
Venue: arXiv cs.CV 2016
Year: 2016

Multivariate median filters have been proposed as generalisations of the well-established median filter for grey-value images to multi-channel images. As multivariate median, most of the recent approaches use the $L^1$ median, i.e.\ the minimiser of an objective function that is the sum of distances to all input points. Many properties of univariate median filters generalise to such a filter. However, the famous result by Guichard and Morel about approximation of the mean curvature motion PDE by median filtering does not have a comparably simple counterpart for $L^1$ multivariate median filtering. We discuss the affine equivariant Oja median and the affine equivariant transformation--retransformation $L^1$ median as alternatives to $L^1$ median filtering. We analyse multivariate median filters in a space-continuous setting, including the formulation of a space-continuous version of the transformation--retransformation $L^1$ median, and derive PDEs approximated by these filters in the cases of bivariate planar images, three-channel volume images and three-channel planar images. The PDEs for the affine equivariant filters can be interpreted geometrically as combinations of a diffusion and a principal-component-wise curvature motion contribution with a cross-effect term based on torsions of principal components. Numerical experiments are presented that demonstrate the validity of the approximation results.
The Continuous 1.5D Terrain Guarding Problem: Discretization, Optimal Solutions, and PTAS
Venue: arXiv cs.CG 2016
Year: 2016

In the NP-hard continuous 1.5D Terrain Guarding Problem (TGP) we are given an $x$-monotone chain of line segments in $\mathbb{R}^2$ (the terrain $T$) and ask for the minimum number of guards (located anywhere on $T$) required to guard all of $T$. We construct guard candidate and witness sets $G, W \subset T$ of polynomial size such that any feasible (optimal) guard cover $G^* \subseteq G$ for $W$ is also feasible (optimal) for the continuous TGP. This discretization allows us to (1) settle NP-completeness for the continuous TGP, (2) provide a Polynomial Time Approximation Scheme (PTAS) for the continuous TGP using the PTAS for the discrete TGP by Gibson et al., and (3) formulate the continuous TGP as an Integer Linear Program (IP). Furthermore, we propose several filtering techniques reducing the size of our discretization, allowing us to devise an efficient IP-based algorithm that reliably provides optimal guard placements for terrains with up to $10^6$ vertices within minutes on a standard desktop computer.
Concise Derivation of Complex Bayesian Approximate Message Passing via Expectation Propagation
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we address the problem of recovering complex-valued signals from a set of complex-valued linear measurements. Approximate message passing (AMP) is one state-of-the-art algorithm to recover real-valued sparse signals. However, the extension of AMP to complex-valued case is nontrivial and no detailed and rigorous derivation has been explicitly presented. To fill this gap, we extend AMP to complex Bayesian approximate message passing (CB-AMP) using expectation propagation (EP). This novel perspective leads to a concise derivation of CB-AMP without sophisticated transformations between the complex domain and the real domain. In addition, we have derived state evolution equations to predict the reconstruction performance of CB-AMP. Simulation results are presented to demonstrate the efficiency of CB-AMP and state evolution.
Polynomial Space Randomness in Analysis
Venue: arXiv cs.CC 2016
Year: 2016

We study the interaction between polynomial space randomness and a fundamental result of analysis, the Lebesgue differentiation theorem. We generalize Ko's framework for polynomial space computability in $\mathbb{R}^n$ to define \textit{weakly pspace-random} points, a new variant of polynomial space randomness. We show that the Lebesgue differentiation theorem holds for every weakly pspace-random point.
Energy-Efficient Object Detection using Semantic Decomposition
Venue: arXiv cs.CV 2016
Year: 2016

Machine-learning algorithms offer immense possibilities in the development of several cognitive applications. In fact, large scale machine-learning classifiers now represent the state-of-the-art in a wide range of object detection/classification problems. However, the network complexities of large-scale classifiers present them as one of the most challenging and energy intensive workloads across the computing spectrum. In this paper, we present a new approach to optimize energy efficiency of object detection tasks using semantic decomposition to build a hierarchical classification framework. We observe that certain semantic information like color/texture are common across various images in real-world datasets for object detection applications. We exploit these common semantic features to distinguish the objects of interest from the remaining inputs (non-objects of interest) in a dataset at a lower computational effort. We propose a 2-stage hierarchical classification framework, with increasing levels of complexity, wherein the first stage is trained to recognize the broad representative semantic features relevant to the object of interest. The first stage rejects the input instances that do not have the representative features and passes only the relevant instances to the second stage. Our methodology thus allows us to reject certain information at lower complexity and utilize the full computational effort of a network only on a smaller fraction of inputs to perform detection. We use color and texture as distinctive traits to carry out several experiments for object detection. Our experiments on the Caltech101/CIFAR10 dataset show that the proposed method yields 1.93x/1.46x improvement in average energy, respectively, over the traditional single classifier model.
Parallel Metric Tree Embedding based on an Algebraic View on Moore-Bellman-Ford
Venue: arXiv cs.DC 2016
Year: 2016

A \emph{metric tree embedding} of expected \emph{stretch~$α\geq 1$} maps a weighted $n$-node graph $G = (V, E, ω)$ to a weighted tree $T = (V_T, E_T, ω_T)$ with $V \subseteq V_T$ such that, for all $v,w \in V$, $\operatorname{dist}(v, w, G) \leq \operatorname{dist}(v, w, T)$ and $operatorname{E}[\operatorname{dist}(v, w, T)] \leq α\operatorname{dist}(v, w, G)$. Such embeddings are highly useful for designing fast approximation algorithms, as many hard problems are easy to solve on tree instances. However, to date the best parallel $(\operatorname{polylog} n)$-depth algorithm that achieves an asymptotically optimal expected stretch of $α\in \operatorname{O}(\log n)$ requires $\operatornameΩ(n^2)$ work and a metric as input. In this paper, we show how to achieve the same guarantees using $\operatorname{polylog} n$ depth and $\operatorname{\tilde{O}}(m^{1+ε})$ work, where $m = |E|$ and $ε> 0$ is an arbitrarily small constant. Moreover, one may further reduce the work to $\operatorname{\tilde{O}}(m + n^{1+ε})$ at the expense of increasing the expected stretch to $\operatorname{O}(ε^{-1} \log n)$. Our main tool in deriving these parallel algorithms is an algebraic characterization of a generalization of the classic Moore-Bellman-Ford algorithm. We consider this framework, which subsumes a variety of previous "Moore-Bellman-Ford-like" algorithms, to be of independent interest and discuss it in depth. In our tree embedding algorithm, we leverage it for providing efficient query access to an approximate metric that allows sampling the tree using $\operatorname{polylog} n$ depth and $\operatorname{\tilde{O}}(m)$ work. We illustrate the generality and versatility of our techniques by various examples and a number of additional results.
Confinement Control of Double Integrators using Partially Periodic Leader Trajectories
Venue: arXiv cs.MA 2016
Year: 2016

We consider a multi-agent confinement control problem in which a single leader has a purely repulsive effect on follower agents with double-integrator dynamics. By decomposing the leader's control inputs into periodic and aperiodic components, we show that the leader can be driven so as to guarantee confinement of the followers about a time-dependent trajectory in the plane. We use tools from averaging theory and an input-to-state stability type argument to derive conditions on the model parameters that guarantee confinement of the followers about the trajectory. For the case of a single follower, we show that if the follower starts at the origin, then the error in trajectory tracking can be made arbitrarily small depending on the frequency of the periodic control components and the rate of change of the trajectory. We validate our approach using simulations and experiments with a small mobile robot.
Proposal for an All-Spin Artificial Neural Network: Emulating Neural and Synaptic Functionalities Through Domain Wall Motion in Ferromagnets
Venue: arXiv cs.ET 2016
Year: 2016

Non-Boolean computing based on emerging post-CMOS technologies can potentially pave the way for low-power neural computing platforms. However, existing work on such emerging neuromorphic architectures have either focused on solely mimicking the neuron, or the synapse functionality. While memristive devices have been proposed to emulate biological synapses, spintronic devices have proved to be efficient at performing the thresholding operation of the neuron at ultra-low currents. In this work, we propose an All-Spin Artificial Neural Network where a single spintronic device acts as the basic building block of the system. The device offers a direct mapping to synapse and neuron functionalities in the brain while inter-layer network communication is accomplished via CMOS transistors. To the best of our knowledge, this is the first demonstration of a neural architecture where a single nanoelectronic device is able to mimic both neurons and synapses. The ultra-low voltage operation of low resistance magneto-metallic neurons enables the low-voltage operation of the array of spintronic synapses, thereby leading to ultra-low power neural architectures. Device-level simulations, calibrated to experimental results, was used to drive the circuit and system level simulations of the neural network for a standard pattern recognition problem. Simulation studies indicate energy savings by ~ 100x in comparison to a corresponding digital/ analog CMOS neuron implementation.
Frequency Selective Hybrid Precoding for Limited Feedback Millimeter Wave Systems
Venue: arXiv cs.IT 2016
Year: 2016

Hybrid analog/digital precoding offers a compromise between hardware complexity and system performance in millimeter wave (mmWave) systems. This type of precoding allows mmWave systems to leverage large antenna array gains that are necessary for sufficient link margin, while permitting low cost and power consumption hardware. Most prior work has focused on hybrid precoding for narrowband mmWave systems, with perfect or estimated channel knowledge at the transmitter. MmWave systems, however, will likely operate on wideband channels with frequency selectivity. Therefore, this paper considers wideband mmWave systems with a limited feedback channel between the transmitter and receiver. First, the optimal hybrid precoding design for a given RF codebook is derived. This provides a benchmark for any other heuristic algorithm and gives useful insights into codebook designs. Second, efficient hybrid analog/digital codebooks are developed for spatial multiplexing in wideband mmWave systems. Finally, a low-complexity yet near-optimal greedy frequency selective hybrid precoding algorithm is proposed based on Gram-Schmidt orthogonalization. Simulation results show that the developed hybrid codebooks and precoder designs achieve very good performance compared with the unconstrained solutions while requiring much less complexity.
Exploiting Multiple Levels of Parallelism in Sparse Matrix-Matrix Multiplication
Venue: arXiv cs.DC 2016
Year: 2016

Sparse matrix-matrix multiplication (or SpGEMM) is a key primitive for many high-performance graph algorithms as well as for some linear solvers, such as algebraic multigrid. The scaling of existing parallel implementations of SpGEMM is heavily bound by communication. Even though 3D (or 2.5D) algorithms have been proposed and theoretically analyzed in the flat MPI model on Erdos-Renyi matrices, those algorithms had not been implemented in practice and their complexities had not been analyzed for the general case. In this work, we present the first ever implementation of the 3D SpGEMM formulation that also exploits multiple (intra-node and inter-node) levels of parallelism, achieving significant speedups over the state-of-the-art publicly available codes at all levels of concurrencies. We extensively evaluate our implementation and identify bottlenecks that should be subject to further research.
Client Profiling for an Anti-Money Laundering System
Venue: arXiv cs.LG 2016
Year: 2016

We present a data mining approach for profiling bank clients in order to support the process of detection of anti-money laundering operations. We first present the overall system architecture, and then focus on the relevant component for this paper. We detail the experiments performed on real world data from a financial institution, which allowed us to group clients in clusters and then generate a set of classification rules. We discuss the relevance of the founded client profiles and of the generated classification rules. According to the defined overall agent-based architecture, these rules will be incorporated in the knowledge base of the intelligent agents responsible for the signaling of suspicious transactions.