OpenRaiser/Intern-Atlas huggingface dataset:
Universal decoding using a noisy codebook
Venue: arXiv cs.IT 2016
Year: 2016

We consider the topic of universal decoding with a decoder that does not have direct access to the codebook, but only to noisy versions of the various randomly generated codewords, a problem motivated by biometrical identification systems. Both the source that generates the original (clean) codewords, and the channel that corrupts them in generating the noisy codewords, as well as the main channel for communicating the messages, are all modeled by non-unifilar, finite-state systems (hidden Markov models). As in previous works on universal decoding, here too, the average error probability of our proposed universal decoder is shown to be as small as that of the optimal maximum likelihood (ML) decoder, up to a multiplicative factorthat is a sub-exponential function of the block length. It therefore has the same error exponent, whenever the ML decoder has a positive error exponent. The universal decoding metric is based on Lempel-Ziv (LZ) incremental parsing of each noisy codeword jointly with the given channel output vector, but this metric is somewhat different from the one proposed in earlier works on universal decoding for finite-state channels, by Ziv (1985) and by Lapidoth and Ziv (1998). The reason for the difference is that here, unlike in those earlier works, the probability distribution that governs the (noisy) codewords is, in general, not uniform across its support. This non-uniformity of the codeword distribution also makes our derivation more challenging. Another reason for the more challenging analysis is the fact that the effective induced channel between the noisy codeword of the transmitted message and the main channel output is not a finite-state channel in general.
SHA-1 and the Strict Avalanche Criterion
Venue: arXiv cs.CR 2016
Year: 2016

The Strict Avalanche Criterion (SAC) is a measure of both confusion and diffusion, which are key properties of a cryptographic hash function. This work provides a working definition of the SAC, describes an experimental methodology that can be used to statistically evaluate whether a cryptographic hash meets the SAC, and uses this to investigate the degree to which compression function of the SHA-1 hash meets the SAC. The results ($P < 0.01$) are heartening: SHA-1 closely tracks the SAC after the first 24 rounds, and demonstrates excellent properties of confusion and diffusion throughout.
Smart Computing and Sensing Technologies for Animal Welfare: A Systematic Review
Venue: arXiv cs.CY 2016
Year: 2016

Animals play a profoundly important and intricate role in our lives today. Dogs have been human companions for thousands of years, but they now work closely with us to assist the disabled, and in combat and search and rescue situations. Farm animals are a critical part of the global food supply chain, and there is increasing consumer interest in organically fed and humanely raised livestock, and how it impacts our health and environmental footprint. Wild animals are threatened with extinction by human induced factors, and shrinking and compromised habitat. This review sets the goal to systematically survey the existing literature in smart computing and sensing technologies for domestic, farm and wild animal welfare. We use the notion of \emph{animal welfare} in broad terms, to review the technologies for assessing whether animals are healthy, free of pain and suffering, and also positively stimulated in their environment. Also the notion of \emph{smart computing and sensing} is used in broad terms, to refer to computing and sensing systems that are not isolated but interconnected with communication networks, and capable of remote data collection, processing, exchange and analysis. We review smart technologies for domestic animals, indoor and outdoor animal farming, as well as animals in the wild and zoos. The findings of this review are expected to motivate future research and contribute to data, information and communication management as well as policy for animal welfare.
Miuz: measuring the impact of disconnecting a node
Venue: arXiv cs.SI 2016
Year: 2016

In this article we present Miuz, a robustness index for complex networks. Miuz measures the impact of disconnecting a node from the network while comparing the sizes of the remaining connected components. Strictly speaking, Miuz for a node is defined as the inverse of the size of the largest connected component divided by the sum of the sizes of the remaining ones. We tested our index in attack strategies where the nodes are disconnected in decreasing order of a specified metric. We considered Miuz and other well-known centrality measures such as betweenness, degree , and harmonic centrality. All of these metrics were compared regarding the behavior of the robust-ness (R-index) during the attacks. In an attempt to simulate the internet backbone, the attacks were performed in complex networks with power-law degree distributions (scale-free networks). Preliminary results show that attacks based on disconnecting a few number of nodes Miuz are more dangerous (decreasing the robustness) than the same attacks based on other centrality measures. We believe that Miuz, as well as other measures based on the size of the largest connected component, provides a good addition to other robustness metrics for complex networks.
An Error Covariance Splitting Technique for Multi-User MIMO Interference Environment
Venue: arXiv cs.IT 2016
Year: 2016

This paper investigates an error covariance matrix splitting technique for multiuser multiple input and multiple output (MIMO) interference downlink channel. Most of the related work has thus far considered the traditional error covariance matrix which has not been well-shaped for maximizing the system capacity. Thus, we split and propose a new iterative error covariance matrix to mitigate the system error and maximize the system capacity in this paper. Numerical results illustrate that our proposed method is strictly better than the traditional method.
Efficient computation of Laguerre polynomials
Venue: arXiv cs.NA 2016
Year: 2016

An efficient algorithm and a Fortran 90 module (LaguerrePol) for computing Laguerre polynomials $L^{(α)}_n(z)$ are presented. The standard three-term recurrence relation satisfied by the polynomials and different types of asymptotic expansions valid for $n$ large and $α$ small, are used depending on the parameter region. Based on tests of contiguous relations in the parameter $α$ and the degree $n$ satisfied by the polynomials, we claim that a relative accuracy close or better than $10^{-12}$ can be obtained using the module LaguerrePol for computing the functions $L^{(α)}_n(z)$ in the parameter range $z \ge 0$, $-1 < α\le 5$, $n \ge 0$.
Performance analysis of a non-beacon enabled IEEE 802.15.4 network with retransmission and ACK mode
Venue: arXiv cs.NI 2016
Year: 2016

The aim of our work is to evaluate the performance of non-beacon IEEE 802.15.4 networks with acknowledgement (ACK) mode and retransmission limits in a finer time unit. Moreover, we predict network performance parameters using backpropagation artificial neural networks (BP-ANNs) with respect to a given quality of service for real-world applications. Therefore, our proposed methods can assist the deployment of a star network with its performance specified in a more practical way. First, the discrete time Markov chain model and M/M/1/k queue are used to describe the full unslotted carrier sense multiple access with collision avoidance (CSMA/CA) algorithm in a non-beacon network. Considering MAC buffer size, unsaturated traffic, and saturated traffic, we build three analytical models to derive eight important performance metrics, e.g., throughput, delay, and reliability. In addition, extensive simulation results show the accuracy of the analytical models in throughput and reliability. Finally, we use the analytical data to train the BP-ANNs models to predict the key parameters such as node number and delay. All results from the simulation data used to test the BP-ANNs show the accuracy these models. Thus, these methods and results can be used to deploy star networks in application environments.
Deep Retinal Image Understanding
Venue: arXiv cs.CV 2016
Year: 2016

This paper presents Deep Retinal Image Understanding (DRIU), a unified framework of retinal image analysis that provides both retinal vessel and optic disc segmentation. We make use of deep Convolutional Neural Networks (CNNs), which have proven revolutionary in other fields of computer vision such as object detection and image classification, and we bring their power to the study of eye fundus images. DRIU uses a base network architecture on which two set of specialized layers are trained to solve both the retinal vessel and optic disc segmentation. We present experimental validation, both qualitative and quantitative, in four public datasets for these tasks. In all of them, DRIU presents super-human performance, that is, it shows results more consistent with a gold standard than a second human annotator used as control.
A Generic Logic for Proving Linearizability (Extended Version)
Venue: arXiv cs.PL 2016
Year: 2016

Linearizability is a commonly accepted notion of correctness for libraries of concurrent algorithms, and recent years have seen a number of proposals of program logics for proving it. Although these logics differ in technical details, they embody similar reasoning principles. To explicate these principles, we propose a logic for proving linearizability that is generic: it can be instantiated with different means of compositional reasoning about concurrency, such as separation logic or rely-guarantee. To this end, we generalise the Views framework for reasoning about concurrency to handle relations between programs, required for proving linearizability. We present sample instantiations of our generic logic and show that it is powerful enough to handle concurrent algorithms with challenging features, such as helping.
A New Approach to Constructing Quadratic Pseudo-Planar Functions over $\gf_{2^n}$
Venue: arXiv cs.IT 2016
Year: 2016

Planar functions over finite fields give rise to finite projective planes. They were also used in the constructions of DES-like iterated ciphers, error-correcting codes, and codebooks. They were originally defined only in finite fields with odd characteristic, but recently Zhou introduced pesudo-planar functions in even characteristic which yields similar applications. All known pesudo-planar functions are quadratic and hence they give presemifields. In this paper, a new approach to constructing quadratic pseudo-planar functions is given. Then five explicit families of pseudo-planar functions are constructed, one of which is a binomial, two of which are trinomials, and the other two are quadrinomials. All known pesudo-planar functions are revisited, some of which are generalized. These functions not only lead to projective planes, relative difference sets and presemifields, but also give optimal codebooks meeting the Levenstein bound, complete sets of mutually unbiased bases (MUB) and compressed sensing matrices with low coherence.
Embedding AC Power Flow in the Complex Plane Part II: A Reliable Framework for Voltage Collapse Analysis
Venue: arXiv cs.SY 2016
Year: 2016

Part II of this paper elaborates on the unique capability of the proposed power flow analysis framework to obtain the true solution corresponding to the stable operating point of a network. It explains the significance of obtaining the true solution for an accurate assessment of the voltage collapse margin. This feature distinguishes the framework from all iterative and non-iterative heuristic approaches as demonstrated in the context of a 7-bus network with Newton-Raphson, its variants and semidefinite and moment-based relaxations of power flow. Another important feature of this framework is that it obtains the true solution when it exists and declares its non-existence otherwise. This is demonstrated in the context of small networks and in comparison with heuristic approaches. This paper also explores how the proposed framework detects a limit-induced bifurcation where a network controller reaching its limit can initiate voltage collapse.
Joint Audio-Video Fingerprint Media Retrieval Using Rate-Coverage Optimization
Venue: arXiv cs.IR 2016
Year: 2016

In this work, we propose a joint audio-video fingerprint Automatic Content Recognition (ACR) technology for media retrieval. The problem is focused on how to balance the query accuracy and the size of fingerprint, and how to allocate the bits of the fingerprint to video frames and audio frames to achieve the best query accuracy. By constructing a novel concept called Coverage, which is highly correlated to the query accuracy, we are able to form a rate-coverage model to translate the original problem into an optimization problem that can be resolved by dynamic programming. To the best of our knowledge, this is the first work that uses joint audio-video fingerprint ACR technology for media retrieval with a theoretical problem formulation. Experimental results indicate that compared to reference algorithms, the proposed method has up to 25% query accuracy improvement while using 60% overall bit-rates, and 25% bit-rate reduction while achieving 85% accuracy, and it significantly outperforms the solution with single audio or video source fingerprint.
Vision-based Engagement Detection in Virtual Reality
Venue: arXiv cs.CV 2016
Year: 2016

User engagement modeling for manipulating actions in vision-based interfaces is one of the most important case studies of user mental state detection. In a Virtual Reality environment that employs camera sensors to recognize human activities, we have to know when user intends to perform an action and when not. Without a proper algorithm for recognizing engagement status, any kind of activities could be interpreted as manipulating actions, called "Midas Touch" problem. Baseline approach for solving this problem is activating gesture recognition system using some focus gestures such as waiving or raising hand. However, a desirable natural user interface should be able to understand user's mental status automatically. In this paper, a novel multi-modal model for engagement detection, DAIA, is presented. using DAIA, the spectrum of mental status for performing an action is quantized in a finite number of engagement states. For this purpose, a Finite State Transducer (FST) is designed. This engagement framework shows how to integrate multi-modal information from user biometric data streams such as 2D and 3D imaging. FST is employed to make the state transition smoothly using combination of several boolean expressions. Our FST true detection rate is 92.3% in total for four different states. Results also show FST can segment user hand gestures more robustly.
Efficient Volumetric Fusion of Airborne and Street-Side Data for Urban Reconstruction
Venue: arXiv cs.CV 2016
Year: 2016

Airborne acquisition and on-road mobile mapping provide complementary 3D information of an urban landscape: the former acquires roof structures, ground, and vegetation at a large scale, but lacks the facade and street-side details, while the latter is incomplete for higher floors and often totally misses out on pedestrian-only areas or undriven districts. In this work, we introduce an approach that efficiently unifies a detailed street-side Structure-from-Motion (SfM) or Multi-View Stereo (MVS) point cloud and a coarser but more complete point cloud from airborne acquisition in a joint surface mesh. We propose a point cloud blending and a volumetric fusion based on ray casting across a 3D tetrahedralization (3DT), extended with data reduction techniques to handle large datasets. To the best of our knowledge, we are the first to adopt a 3DT approach for airborne/street-side data fusion. Our pipeline exploits typical characteristics of airborne and ground data, and produces a seamless, watertight mesh that is both complete and detailed. Experiments on 3D urban data from multiple sources and different data densities show the effectiveness and benefits of our approach.
Incentive Engineering Framework for Crowdsourcing Systems
Venue: arXiv cs.HC 2016
Year: 2016

Significant effort has been made to understand user motivation and to elicit user participation in crowdsourcing systems. However, incentive engineering, i.e., designing incentives that can purposefully motivate users, is still an open question and remains one of the key challenges of crowdsourcing initiatives. In this work in progress, we propose a general and systematic incentive engineering framework that system designers can use to implement appropriate incentives in order to effect desirable user behaviours.
Fourier-sparse interpolation without a frequency gap
Venue: arXiv cs.DS 2016
Year: 2016

We consider the problem of estimating a Fourier-sparse signal from noisy samples, where the sampling is done over some interval $[0, T]$ and the frequencies can be "off-grid". Previous methods for this problem required the gap between frequencies to be above 1/T, the threshold required to robustly identify individual frequencies. We show the frequency gap is not necessary to estimate the signal as a whole: for arbitrary $k$-Fourier-sparse signals under $\ell_2$ bounded noise, we show how to estimate the signal with a constant factor growth of the noise and sample complexity polynomial in $k$ and logarithmic in the bandwidth and signal-to-noise ratio. As a special case, we get an algorithm to interpolate degree $d$ polynomials from noisy measurements, using $O(d)$ samples and increasing the noise by a constant factor in $\ell_2$.
Reconstructing Articulated Rigged Models from RGB-D Videos
Venue: arXiv cs.CV 2016
Year: 2016

Although commercial and open-source software exist to reconstruct a static object from a sequence recorded with an RGB-D sensor, there is a lack of tools that build rigged models of articulated objects that deform realistically and can be used for tracking or animation. In this work, we fill this gap and propose a method that creates a fully rigged model of an articulated object from depth data of a single sensor. To this end, we combine deformable mesh tracking, motion segmentation based on spectral clustering and skeletonization based on mean curvature flow. The fully rigged model then consists of a watertight mesh, embedded skeleton, and skinning weights.
Improved Algorithms for Computing $k$-Sink on Dynamic Path Networks
Venue: arXiv cs.DS 2016
Year: 2016

We present a novel approach to finding the $k$-sink on dynamic path networks with general edge capacities. Our first algorithm runs in $O(n \log n + k^2 \log^4 n)$ time, where $n$ is the number of vertices on the given path, and our second algorithm runs in $O(n \log^3 n)$ time. Together, they improve upon the previously most efficient $O(kn \log^2 n)$ time algorithm due to Arumugam et al. for all values of $k$. In the case where all the edges have the same capacity, we again present two algorithms that run in $O(n + k^2 \log^2n)$ time and $O(n \log n)$ time, respectively, and they together improve upon the previously best $O(kn)$ time algorithm due to Higashikawa et al. for all values of $k$.
Android Assistant EyeMate for Blind and Blind Tracker
Venue: arXiv cs.HC 2016
Year: 2016

At present many blind assistive systems have been implemented but there is no such kind of good system to navigate a blind person and also to track the movement of a blind person and rescue him/her if he/she is lost. In this paper, we have presented a blind assistive and tracking embedded system. In this system the blind person is navigated through a spectacle interfaced with an android application. The blind person is guided through Bengali/English voice commands generated by the application according to the obstacle position. Using voice command a blind person can establish voice call to a predefined number without touching the phone just by pressing the headset button. The blind assistive application gets the latitude and longitude using GPS and then sends them to a server. The movement of the blind person is tracked through another android application that points out the current position in Google map. We took distances from several surfaces like concrete and tiles floor in our experiment where the error rate is 5%.
Securely Outsourcing Large Scale Eigen Value Problem to Public Cloud
Venue: arXiv cs.CR 2016
Year: 2016

Cloud computing enables clients with limited computational power to economically outsource their large scale computations to a public cloud with huge computational power. Cloud has the massive storage, computational power and software which can be used by clients for reducing their computational overhead and storage limitation. But in case of outsourcing, privacy of client's confidential data must be maintained. We have designed a protocol for outsourcing large scale Eigen value problem to a malicious cloud which provides input/output data security, result verifiability and client's efficiency. As the direct computation method to find all eigenvectors is computationally expensive for large dimensionality, we have used power iterative method for finding the largest Eigen value and the corresponding Eigen vector of a matrix. For protecting the privacy, some transformations are applied to the input matrix to get encrypted matrix which is sent to the cloud and then decrypting the result that is returned from the cloud for getting the correct solution of Eigen value problem. We have also proposed result verification mechanism for detecting robust cheating and provided theoretical analysis and experimental result that describes high-efficiency, correctness, security and robust cheating resistance of the proposed protocol.
Coexistence in 5G: Analysis of Cross-Interference between OFDM/OQAM and Legacy Users
Venue: arXiv cs.IT 2016
Year: 2016

To optimize the use of the spectrum, it is expected that the next generation of wireless networks (5G) will enable coexistence of newly introduced services with legacy cellular networks. These new services, like Device-To-Device (D2D) communication, should require limited synchronization with the legacy cell to limit the amount of signaling overhead in the network. However, it is known that Cyclic Prefix-Orthogonal Frequency Division Multiplexing (CP-OFDM) used in Long Term Evolution-Advanced (LTE-A) is not fit for asynchronous environments. This has motivated the search for a new waveform, able to enhance coexistence with CP-OFDM. Namely, it has been widely suggested that new devices could use OFDM/Offset-Quadrature Amplitude Modulation (OFDM/OQAM) to reduce the interference they inject to legacy cellular users. However, values of interference are usually measured at the input antenna of the receiver, based on the PSD of the interfering signal. We showed in previous works that this measurement is not representative of the actual interference that is seen after the demodulation operations. Building on this finding, we provide in this paper the first exact closed forms of cross-interference between OFDM/OQAM and CP-OFDM users. Our results prove that using OFDM/OQAM only marginally reduces interference to legacy users, in contradiction with many results in the literature.