OpenRaiser/Intern-Atlas huggingface dataset:
Online Learning Sensing Matrix and Sparsifying Dictionary Simultaneously for Compressive Sensing
Venue: arXiv cs.LG 2018
Year: 2018

This paper considers the problem of simultaneously learning the Sensing Matrix and Sparsifying Dictionary (SMSD) on a large training dataset. To address the formulated joint learning problem, we propose an online algorithm that consists of a closed-form solution for optimizing the sensing matrix with a fixed sparsifying dictionary and a stochastic method for learning the sparsifying dictionary on a large dataset when the sensing matrix is given. Benefiting from training on a large dataset, the obtained compressive sensing (CS) system by the proposed algorithm yields a much better performance in terms of signal recovery accuracy than the existing ones. The simulation results on natural images demonstrate the effectiveness of the suggested online algorithm compared with the existing methods.
Community detection, link prediction, and layer interdependence in multilayer networks
Venue: arXiv cs.SI 2018
Year: 2018

Complex systems are often characterized by distinct types of interactions between the same entities. These can be described as a multilayer network where each layer represents one type of interaction. These layers may be interdependent in complicated ways, revealing different kinds of structure in the network. In this work we present a generative model, and an efficient expectation-maximization algorithm, which allows us to perform inference tasks such as community detection and link prediction in this setting. Our model assumes overlapping communities that are common between the layers, while allowing these communities to affect each layer in a different way, including arbitrary mixtures of assortative, disassortative, or directed structure. It also gives us a mathematically principled way to define the interdependence between layers, by measuring how much information about one layer helps us predict links in another layer. In particular, this allows us to bundle layers together to compress redundant information, and identify small groups of layers which suffice to predict the remaining layers accurately. We illustrate these findings by analyzing synthetic data and two real multilayer networks, one representing social support relationships among villagers in South India and the other representing shared genetic substrings material between genes of the malaria parasite.
High Speed Elephant Flow Detection Under Partial Information
Venue: arXiv cs.NI 2018
Year: 2018

In this paper we introduce a new framework to detect elephant flows at very high speed rates and under uncertainty. The framework provides exact mathematical formulas to compute the detection likelihood and introduces a new flow reconstruction lemma under partial information. These theoretical results lead to the design of BubbleCache, a new elephant flow detection algorithm designed to operate near the optimal tradeoff between computational scalability and accuracy by dynamically tracking the traffic's natural cutoff sampling rate. We demonstrate on a real world 100 Gbps network that the BubbleCache algorithm helps reduce the computational cost by a factor of 1000 and the memory requirements by a factor of 100 while detecting the top flows on the network with very high probability.
Distributed Load Shedding for Microgrid with Compensation Support via Wireless Network
Venue: arXiv cs.SY 2018
Year: 2018

Due to the limited generation and finite inertia, microgrid suffers from the large frequency and voltage deviation which can lead to system collapse. Thus, reliable load shedding to keep frequency stable is required. Wireless network, benefiting from the high flexibility and low deployment cost, is considered as a promising technology for fine-grained management. In this paper, for balancing the supply-demand and reducing the load-shedding amount, a distributed load shedding solution via wireless network is proposed. Firstly, active power coordination of different priority loads is formulated as an optimisation problem. To solve it, a distributed load shedding algorithm based on subgradient method (DLSS) is developed for gradually shedding loads. Using this method, power compensation can be utilised and has more time to lower the power deficit so as to reduce the load-shedding amount. Secondly, to increase the response rate and enhance the reliability of our method, a multicast metropolis schedule based on TDMA (MMST) is developed. In this protocol, time slots are dedicatedly allocated and a checking and retransmission mechanism is utilised. Finally, the proposed solution is evaluated by NS3-Matlab co-simulator. The numerical results demonstrate the feasibility and effectiveness of our solution.
Accurate Learning or Fast Mixing? Dynamic Adaptability of Caching Algorithms
Venue: arXiv cs.NI 2018
Year: 2018

Typical analysis of content caching algorithms using the metric of steady state hit probability under a stationary request process does not account for performance loss under a variable request arrival process. In this work, we consider adaptability of caching algorithms from two perspectives: (a) the accuracy of learning a fixed popularity distribution, and (b) the speed of learning items' popularity. In order to attain this goal, we compute the distance between the stationary distributions of several popular algorithms with that of a genie-aided algorithm that has knowledge of the true popularity ranking, which we use as a measure of learning accuracy. We then characterize the mixing time of each algorithm, i.e., the time needed to attain the stationary distribution, which we use as a measure of learning efficiency. We merge both measures above to obtain the "learning error" representing both how quickly and how accurately an algorithm learns the optimal caching distribution, and use this to determine the trade-off between these two objectives of many popular caching algorithms. Informed by the results of our analysis, we propose a novel hybrid algorithm, Adaptive-LRU (A-LRU), that learns both faster and better the changes in the popularity. We show numerically that it also outperforms all other candidate algorithms when confronted with either a dynamically changing synthetic request process or using real world traces.
Feedback Capacity over Networks
Venue: arXiv cs.SY 2018
Year: 2018

In this paper, we investigate the fundamental limitations of feedback mechanism in dealing with uncertainties for network systems. The study of maximum capability of feedback control was pioneered in Xie and Guo (2000) for scalar systems with nonparametric nonlinear uncertainty. In a network setting, nodes with unknown and nonlinear dynamics are interconnected through a directed interaction graph. Nodes can design feedback controls based on all available information, where the objective is to stabilize the network state. Using information structure and decision pattern as criteria, we specify three categories of network feedback laws, namely the global-knowledge/global-decision, network-flow/local-decision, and local-flow/local-decision feedback. We establish a series of network capacity characterizations for these three fundamental types of network control laws. First of all, we prove that for global-knowledge/global-decision and network-flow/local-decision control where nodes know the information flow across the entire network, there exists a critical number $\big(3/2+\sqrt{2}\big)/\|A_{\mathrm{G}}\|_\infty$, where $3/2+\sqrt{2}$ is as known as the Xie-Guo constant and $A_{\mathrm{G}}$ is the network adjacency matrix, defining exactly how much uncertainty in the node dynamics can be overcome by feedback. Interestingly enough, the same feedback capacity can be achieved under max-consensus enhanced local flows where nodes only observe information flows from neighbors as well as extreme (max and min) states in the network. Next, for local-flow/local-decision control, we prove that there exists a structure-determined value being a lower bound of the network feedback capacity. These results reveal the important connection between network structure and fundamental capabilities of in-network feedback control.
K-means Algorithm over Compressed Binary Data
Venue: arXiv cs.IT 2018
Year: 2018

We consider a network of binary-valued sensors with a fusion center. The fusion center has to perform K-means clustering on the binary data transmitted by the sensors. In order to reduce the amount of data transmitted within the network, the sensors compress their data with a source coding scheme based on binary sparse matrices. We propose to apply the K-means algorithm directly over the compressed data without reconstructing the original sensors measurements, in order to avoid potentially complex decoding operations. We provide approximated expressions of the error probabilities of the K-means steps in the compressed domain. From these expressions, we show that applying the K-means algorithm in the compressed domain enables to recover the clusters of the original domain. Monte Carlo simulations illustrate the accuracy of the obtained approximated error probabilities, and show that the coding rate needed to perform K-means clustering in the compressed domain is lower than the rate needed to reconstruct all the measurements.
Simplified and Space-Optimal Semi-Streaming for $(2+ε)$-Approximate Matching
Venue: arXiv cs.DS 2018
Year: 2018

In a recent breakthrough, Paz and Schwartzman (SODA'17) presented a single-pass ($2+ε$)-approximation algorithm for the maximum weight matching problem in the semi-streaming model. Their algorithm uses $O(n\log^2 n)$ bits of space, for any constant $ε>0$. We present two simplified and more intuitive analyses, for essentially the same algorithm, which also improve the space complexity to the optimal bound of $O(n\log n)$ bits --- this is optimal as the output matching requires $Ω(n\log n)$ bits. Our analyses rely on a simple use of the primal-dual method and a simple accounting method.
Operational Decision Support in the Presence of Uncertainties
Venue: arXiv cs.SY 2018
Year: 2018

This book addresses the scientific domains of operations research, information science and statistics with a focus on engineering applications. The purpose of this book is to report on the implications of the loop equations formulation of the state estimation procedure of the network systems, for the purpose of the implementation of Decision Support (DS) systems for the operational control of the network systems. In general an operational DS comprises a series of standalone applications from which the mathematical modeling and simulation of the distribution systems and the managing of the uncertainty in the decision-making process are essential in order to obtain efficient control and monitoring of the distribution systems. The mathematical modeling and simulation forms the basis for detailed optimization of the network operations and the second one uses uncertainty based reasoning in order to reduce the complexity of the network system and to increase the credibility of its model. This book reports on the integration of the two aspects of operational DS into a single computational framework of loop network equations. The proposed DS system will be validated using case studies taken from the water industry. The optimal control of water distribution systems is an important problem because the models are non-linear and large-scale and measurements are prone to errors and very often they are incomplete.
Comprehensive Review of Audio Steganalysis Methods
Venue: arXiv cs.MM 2018
Year: 2018

Recently, merging signal processing techniques with information security services has found a lot of attention. Steganography and steganalysis are among those trends. Like their counterparts in cryptology, steganography and steganalysis are in a constant battle. Steganography methods try to hide the presence of covert messages in innocuous-looking data, whereas steganalysis methods try to reveal existence of such messages and to break steganography methods. The stream nature of audio signals, their popularity, and their wide spread usage make them very suitable media for steganography. This has led to a very rich literature on both steganography and steganalysis of audio signals. This paper intends to conduct a comprehensive review of audio steganalysis methods aggregated over near fifteen years. Furthermore, we implement some of the most recent audio steganalysis methods and conduct a comparative analysis on their performances. Finally, the paper provides some possible directions for future researches on audio steganalysis.
Disentangling group and link persistence in Dynamic Stochastic Block models
Venue: arXiv cs.SI 2018
Year: 2018

We study the inference of a model of dynamic networks in which both communities and links keep memory of previous network states. By considering maximum likelihood inference from single snapshot observations of the network, we show that link persistence makes the inference of communities harder, decreasing the detectability threshold, while community persistence tends to make it easier. We analytically show that communities inferred from single network snapshot can share a maximum overlap with the underlying communities of a specific previous instant in time. This leads to time-lagged inference: the identification of past communities rather than present ones. Finally we compute the time lag and propose a corrected algorithm, the Lagged Snapshot Dynamic (LSD) algorithm, for community detection in dynamic networks. We analytically and numerically characterize the detectability transitions of such algorithm as a function of the memory parameters of the model and we make a comparison with a full dynamic inference.
Separable Codes for the Symmetric Multiple-Access Channel
Venue: arXiv cs.IT 2018
Year: 2018

A binary matrix is called an s-separable code for the disjunctive multiple-access channel (disj-MAC) if Boolean sums of sets of s columns are all distinct. The well-known issue of the combinatorial coding theory is to obtain upper and lower bounds on the rate of s-separable codes for disj-MAC. In our paper, we generalize the problem and discuss upper and lower bounds on the rate of q-ary s-separable codes for models of noiseless symmetric MAC, i.e., when at each time instant the output signal of MAC is a symmetric function of its s input signals.
Feedback capacity and coding for the BIBO channel with a no-repeated-ones input constraint
Venue: arXiv cs.IT 2018
Year: 2018

In this paper, a general binary-input binary-output (BIBO) channel is investigated in the presence of feedback and input constraints. The feedback capacity and the optimal input distribution of this setting are calculated for the case of an $(1,\infty)$-RLL input constraint, that is, the input sequence contains no consecutive ones. These results are obtained via explicit solution of a corresponding dynamic programming optimization problem. A simple coding scheme is designed based on the principle of posterior matching, which was introduced by Shayevitz and Feder for memoryless channels. The posterior matching scheme for our input-constrained setting is shown to achieve capacity using two new ideas: \textit{message history}, which captures the memory embedded in the setting, and \textit{message splitting}, which eases the analysis of the scheme. Additionally, in the special case of an S-channel, we give a very simple zero-error coding scheme that is shown to achieve capacity. For the input-constrained BSC, we show using our capacity formula that feedback increases capacity when the cross-over probability is small.
Optimizing MDS Coded Caching in Wireless Networks with Device-to-Device Communication
Venue: arXiv cs.IT 2018
Year: 2018

We consider the caching of content in the mobile devices in a dense wireless network using maximum distance separable (MDS) codes. We focus on an area, served by a base station (BS), where mobile devices move around according to a random mobility model. Users requesting a particular file download coded packets from caching devices within a communication range, using device-to-device communication. If additional packets are required to decode the file, these are downloaded from the BS. We analyze the device mobility and derive a good approximation of the distribution of caching devices within the communication range of mobile devices at any given time. We then optimize the MDS codes to minimize the network load under a cache size constraint and show that using optimized MDS codes results in significantly lower network load compared to when caching the most popular files. We further show numerically that caching coded packets of each file on all mobile devices, i.e., maximal spreading, is optimal.
Coding for Segmented Edit Channels
Venue: arXiv cs.IT 2018
Year: 2018

This paper considers insertion and deletion channels with the additional assumption that the channel input sequence is implicitly divided into segments such that at most one edit can occur within a segment. No segment markers are available in the received sequence. We propose code constructions for the segmented deletion, segmented insertion, and segmented insertion-deletion channels based on subsets of Varshamov-Tenengolts codes chosen with pre-determined prefixes and/or suffixes. The proposed codes, constructed for any finite alphabet, are zero-error and can be decoded segment-by-segment. We also derive an upper bound on the rate of any zero-error code for the segmented edit channel, in terms of the segment length. This upper bound shows that the rate scaling of the proposed codes as the segment length increases is the same as that of the maximal code.
A PTAS for the Time-Invariant Incremental Knapsack problem
Venue: arXiv cs.DS 2018
Year: 2018

The Time-Invariant Incremental Knapsack problem (IIK) is a generalization of Maximum Knapsack to a discrete multi-period setting. At each time, capacity increases and items can be added, but not removed from the knapsack. The goal is to maximize the sum of profits over all times. IIK models various applications including specific financial markets and governmental decision processes. IIK is strongly NP-hard and there has been work on giving approximation algorithms for some special cases. In this paper, we settle the complexity of IIK by designing a PTAS based on rounding a disjuncive formulation, and provide several extensions of the technique.
Discrete Convexity in Joint Winner Property
Venue: arXiv cs.DM 2018
Year: 2018

In this paper, we reveal a relation between joint winner property (JWP) in the field of valued constraint satisfaction problems (VCSPs) and M${}^\natural$-convexity in the field of discrete convex analysis (DCA). We introduce the M${}^\natural$-convex completion problem, and show that a function $f$ satisfying the JWP is Z-free if and only if a certain function $\overline{f}$ associated with $f$ is M${}^\natural$-convex completable. This means that if a function is Z-free, then the function can be minimized in polynomial time via M${}^\natural$-convex intersection algorithms. Furthermore we propose a new algorithm for Z-free function minimization, which is faster than previous algorithms for some parameter values.
A Comprehensive Survey on Bengali Phoneme Recognition
Venue: arXiv cs.SD 2018
Year: 2018

Hidden Markov model based various phoneme recognition methods for Bengali language is reviewed. Automatic phoneme recognition for Bengali language using multilayer neural network is reviewed. Usefulness of multilayer neural network over single layer neural network is discussed. Bangla phonetic feature table construction and enhancement for Bengali speech recognition is also discussed. Comparison among these methods is discussed.
A Covert Queueing Channel in Round Robin Schedulers
Venue: arXiv cs.IT 2018
Year: 2018

We study a covert queueing channel (CQC) between two users sharing a round robin scheduler. Such a covert channel can arise when users share a resource such as a computer processor or a router arbitrated by a round robin policy. We present an information-theoretic framework to model and derive the maximum reliable data transmission rate, i.e., the capacity of this channel, for both noiseless and noisy setups. Our results show that seemingly isolated users can communicate with a high rate over the covert channel and demonstrate the possibility of significant information leakage and privacy threats brought by CQCs in round robin schedulers. Moreover, we propose practical finite-length code constructions, which achieve the capacity limit.
Integrating Reviews into Personalized Ranking for Cold Start Recommendation
Venue: arXiv cs.IR 2018
Year: 2018

Item recommendation task predicts a personalized ranking over a set of items for each individual user. One paradigm is the rating-based methods that concentrate on explicit feedbacks and hence face the difficulties in collecting them. Meanwhile, the ranking-based methods are presented with rated items and then rank the rated above the unrated. This paradigm takes advantage of widely available implicit feedback. It, however, usually ignores a kind of important information: item reviews. Item reviews not only justify the preferences of users, but also help alleviate the cold-start problem that fails the collaborative filtering. In this paper, we propose two novel and simple models to integrate item reviews into Bayesian personalized ranking. In each model, we make use of text features extracted from item reviews using word embeddings. On top of text features we uncover the review dimensions that explain the variation in users' feedback and these review factors represent a prior preference of users. Experiments on six real-world data sets show the benefits of leveraging item reviews on ranking prediction. We also conduct analyses to understand the proposed models.
A proposal about the meaning of scale, scope and resolution in the context of the interpretation process
Venue: arXiv cs.IT 2018
Year: 2018

When considering perceptions, the observation scale and resolution are closely related properties. There is consensus in considering resolution as the density of elementary pieces of information in a specified information space. Differently, with the concept of scale, several conceptions compete for a consistent meaning. Scale is typically regarded as way to indicate the degree of detail in which an observation is performed. But surprisingly, there is not a unified definition of scale as a description's property. This paper offers a precise definition of scale, and a method to quantify it as a property associated to the interpretation of a description. To complete the parameters needed to describe the perception of a description, the concepts of scope and resolution are also exposed with an exact meaning. A model describing the recursive process of interpretation, based on evolving steps of scale, scope and resolution, is introduced. The model relies on the conception of observation scale and its association to the selection of symbols. Five experiments illustrate the application of these concepts, showing that resolution, scale and scope integrate the set of properties to define any point of view from which an observation is performed and interpreted.