OpenRaiser/Intern-Atlas huggingface dataset:
Fast Greedy Approaches for Compressive Sensing of Large-Scale Signals
Venue: arXiv cs.DS 2016
Year: 2016

Cost-efficient compressive sensing is challenging when facing large-scale data, {\em i.e.}, data with large sizes. Conventional compressive sensing methods for large-scale data will suffer from low computational efficiency and massive memory storage. In this paper, we revisit well-known solvers called greedy algorithms, including Orthogonal Matching Pursuit (OMP), Subspace Pursuit (SP), Orthogonal Matching Pursuit with Replacement (OMPR). Generally, these approaches are conducted by iteratively executing two main steps: 1) support detection and 2) solving least square problem. To reduce the cost of Step 1, it is not hard to employ the sensing matrix that can be implemented by operator-based strategy instead of matrix-based one and can be speeded by fast Fourier Transform (FFT). Step 2, however, requires maintaining and calculating a pseudo-inverse of a sub-matrix, which is random and not structural, and, thus, operator-based matrix does not work. To overcome this difficulty, instead of solving Step 2 by a closed-form solution, we propose a fast and cost-effective least square solver, which combines a Conjugate Gradient (CG) method with our proposed weighted least square problem to iteratively approximate the ground truth yielded by a greedy algorithm. Extensive simulations and theoretical analysis validate that the proposed method is cost-efficient and is readily incorporated with the existing greedy algorithms to remarkably improve the performance for large-scale problems.
Repairing Reed-Solomon Codes
Venue: arXiv cs.IT 2016
Year: 2016

We study the performance of Reed-Solomon (RS) codes for the \em exact repair problem \em in distributed storage. Our main result is that, in some parameter regimes, Reed-Solomon codes are optimal regenerating codes, among MDS codes with linear repair schemes. Moreover, we give a characterization of MDS codes with linear repair schemes which holds in any parameter regime, and which can be used to give non-trivial repair schemes for RS codes in other settings. More precisely, we show that for $k$-dimensional RS codes whose evaluation points are a finite field of size $n$, there are exact repair schemes with bandwidth $(n-1)\log((n-1)/(n-k))$ bits, and that this is optimal for any MDS code with a linear repair scheme. In contrast, the naive (commonly implemented) repair algorithm for this RS code has bandwidth $k\log(n)$ bits. When the entire field is used as evaluation points, the number of nodes $n$ is much larger than the number of bits per node (which is $O(\log(n))$), and so this result holds only when the degree of sub-packetization is small. However, our method applies in any parameter regime, and to illustrate this for high levels of sub-packetization we give an improved repair scheme for a specific (14,10)-RS code used in the Facebook Hadoop Analytics cluster.
On the Expressive Power of Deep Learning: A Tensor Analysis
Venue: arXiv cs.NE 2016
Year: 2016

It has long been conjectured that hypotheses spaces suitable for data that is compositional in nature, such as text or images, may be more efficiently represented with deep hierarchical networks than with shallow ones. Despite the vast empirical evidence supporting this belief, theoretical justifications to date are limited. In particular, they do not account for the locality, sharing and pooling constructs of convolutional networks, the most successful deep learning architecture to date. In this work we derive a deep network architecture based on arithmetic circuits that inherently employs locality, sharing and pooling. An equivalence between the networks and hierarchical tensor factorizations is established. We show that a shallow network corresponds to CP (rank-1) decomposition, whereas a deep network corresponds to Hierarchical Tucker decomposition. Using tools from measure theory and matrix algebra, we prove that besides a negligible set, all functions that can be implemented by a deep network of polynomial size, require exponential size in order to be realized (or even approximated) by a shallow network. Since log-space computation transforms our networks into SimNets, the result applies directly to a deep learning architecture demonstrating promising empirical performance. The construction and theory developed in this paper shed new light on various practices and ideas employed by the deep learning community.
Network analysis of named entity co-occurrences in written texts
Venue: arXiv cs.CL 2016
Year: 2016

The use of methods borrowed from statistics and physics to analyze written texts has allowed the discovery of unprecedent patterns of human behavior and cognition by establishing links between models features and language structure. While current models have been useful to unveil patterns via analysis of syntactical and semantical networks, only a few works have probed the relevance of investigating the structure arising from the relationship between relevant entities such as characters, locations and organizations. In this study, we represent entities appearing in the same context as a co-occurrence network, where links are established according to a null model based on random, shuffled texts. Computational simulations performed in novels revealed that the proposed model displays interesting topological features, such as the small world feature, characterized by high values of clustering coefficient. The effectiveness of our model was verified in a practical pattern recognition task in real networks. When compared with traditional word adjacency networks, our model displayed optimized results in identifying unknown references in texts. Because the proposed representation plays a complementary role in characterizing unstructured documents via topological analysis of named entities, we believe that it could be useful to improve the characterization of written texts (and related systems), specially if combined with traditional approaches based on statistical and deeper paradigms.
STDP as presynaptic activity times rate of change of postsynaptic activity
Venue: arXiv cs.NE 2016
Year: 2016

We introduce a weight update formula that is expressed only in terms of firing rates and their derivatives and that results in changes consistent with those associated with spike-timing dependent plasticity (STDP) rules and biological observations, even though the explicit timing of spikes is not needed. The new rule changes a synaptic weight in proportion to the product of the presynaptic firing rate and the temporal rate of change of activity on the postsynaptic side. These quantities are interesting for studying theoretical explanation for synaptic changes from a machine learning perspective. In particular, if neural dynamics moved neural activity towards reducing some objective function, then this STDP rule would correspond to stochastic gradient descent on that objective function.
Stochastic Content-Centric Multicast Scheduling for Cache-Enabled Heterogeneous Cellular Networks
Venue: arXiv cs.IT 2016
Year: 2016

Caching at small base stations (SBSs) has demonstrated significant benefits in alleviating the backhaul requirement in heterogeneous cellular networks (HetNets). While many existing works focus on what contents to cache at each SBS, an equally important problem is what contents to deliver so as to satisfy dynamic user demands given the cache status. In this paper, we study optimal content delivery in cache-enabled HetNets by taking into account the inherent multicast capability of wireless medium. We consider stochastic content multicast scheduling to jointly minimize the average network delay and power costs under a multiple access constraint. We establish a content-centric request queue model and formulate this stochastic optimization problem as an infinite horizon average cost Markov decision process (MDP). By using \emph{relative value iteration} and special properties of the request queue dynamics, we characterize some properties of the value function of the MDP. Based on these properties, we show that the optimal multicast scheduling policy is of threshold type. Then, we propose a structure-aware optimal algorithm to obtain the optimal policy. We also propose a low-complexity suboptimal policy, which possesses similar structural properties to the optimal policy, and develop a low-complexity algorithm to obtain this policy.
Finding Perfect Matchings in Bipartite Hypergraphs
Venue: arXiv cs.DS 2016
Year: 2016

Haxell's condition is a natural hypergraph analog of Hall's condition, which is a well-known necessary and sufficient condition for a bipartite graph to admit a perfect matching. That is, when Haxell's condition holds it forces the existence of a perfect matching in the bipartite hypergraph. Unlike in graphs, however, there is no known polynomial time algorithm to find the hypergraph perfect matching that is guaranteed to exist when Haxell's condition is satisfied. We prove the existence of an efficient algorithm to find perfect matchings in bipartite hypergraphs whenever a stronger version of Haxell's condition holds. Our algorithm can be seen as a generalization of the classical Hungarian algorithm for finding perfect matchings in bipartite graphs. The techniques we use to achieve this result could be of use more generally in other combinatorial problems on hypergraphs where disjointness structure is crucial, e.g. Set Packing.
Bilingual Distributed Word Representations from Document-Aligned Comparable Data
Venue: arXiv cs.CL 2016
Year: 2016

We propose a new model for learning bilingual word representations from non-parallel document-aligned data. Following the recent advances in word representation learning, our model learns dense real-valued word vectors, that is, bilingual word embeddings (BWEs). Unlike prior work on inducing BWEs which heavily relied on parallel sentence-aligned corpora and/or readily available translation resources such as dictionaries, the article reveals that BWEs may be learned solely on the basis of document-aligned comparable data without any additional lexical resources nor syntactic information. We present a comparison of our approach with previous state-of-the-art models for learning bilingual word representations from comparable data that rely on the framework of multilingual probabilistic topic modeling (MuPTM), as well as with distributional local context-counting models. We demonstrate the utility of the induced BWEs in two semantic tasks: (1) bilingual lexicon extraction, (2) suggesting word translations in context for polysemous words. Our simple yet effective BWE-based models significantly outperform the MuPTM-based and context-counting representation models from comparable data as well as prior BWE-based models, and acquire the best reported results on both tasks for all three tested language pairs.
Analysis of a Planetary Scale Scientific Collaboration Dataset Reveals Novel Patterns
Venue: arXiv cs.SI 2016
Year: 2016

Scientific collaboration networks are an important component of scientific output and contribute significantly to expanding our knowledge and to the economy and gross domestic product of nations. Here we examine a dataset from the Mendeley scientific collaboration network. We analyze this data using a combination of machine learning techniques and dynamical models. We find interesting clusters of countries with different characteristics of collaboration. Some of these clusters are dominated by developed countries that have higher number of self connections compared with connections to other countries. Another cluster is dominated by impoverished nations that have mostly connections and collaborations with other countries but fewer self connections. We also propose a complex systems dynamical model that explains these characteristics. Our model explains how the scientific collaboration networks of impoverished and developing nations change over time. We also find interesting patterns in the behaviour of countries that may reflect past foreign policies and contemporary geopolitics. Our model and analysis gives insights and guidelines into how scientific development of developing countries can be guided. This is intimately related to fostering economic development of impoverished nations and creating a richer and more prosperous society.
Secure Communication Via a Wireless Energy Harvesting Untrusted Relay
Venue: arXiv cs.IT 2016
Year: 2016

The broadcast nature of the wireless medium allows unintended users to eavesdrop the confidential information transmission. In this regard, we investigate the problem of secure communication between a source and a destination via a wireless energy harvesting untrusted node which acts as a helper to relay the information; however, the source and destination nodes wish to keep the information confidential from the relay node. To realize the positive secrecy rate, we use destination-assisted jamming. Being an energy-starved node, the untrusted relay harvests energy from the received radio frequency signals, which include the source's information signal and the destination's jamming signal. Thus, we utilize the jamming signal efficiently by leveraging it as a useful energy source. At the relay, to enable energy harvesting and information processing, we adopt power splitting (PS) and time switching (TS) policies. To evaluate the secrecy performance of this proposed scenario, we derive analytical expressions for two important metrics, viz., the secrecy outage probability and the ergodic secrecy rate. The numerical analysis reveals the design insights into the effects of different system parameters like power splitting ratio, energy harvesting time, target secrecy rate, transmit signal-to-noise ratio (SNR), relay location, and energy conversion efficiency factor, on the secrecy performance. Specifically, the PS policy achieves better optimal secrecy outage probability and optimal ergodic secrecy rate than that of the TS policy at higher target secrecy rate and transmit SNR, respectively.
Energy Efficiency in MIMO Underlay and Overlay Device-to-Device Communications and Cognitive Radio Systems
Venue: arXiv cs.IT 2016
Year: 2016

This paper addresses the problem of resource allocation for systems in which a primary and a secondary link share the available spectrum by an underlay or overlay approach. After observing that such a scenario models both cognitive radio and D2D communications, we formulate the problem as the maximization of the secondary energy efficiency subject to a minimum rate requirement for the primary user. This leads to challenging non-convex, fractional problems. In the underlay scenario, we obtain the global solution by means of a suitable reformulation. In the overlay scenario, two algorithms are proposed. The first one yields a resource allocation fulfilling the first-order optimality conditions of the resource allocation problem, by solving a sequence of easier fractional problems. The second one enjoys a weaker optimality claim, but an even lower computational complexity. Numerical results demonstrate the merits of the proposed algorithms both in terms of energy-efficient performance and complexity, also showing that the two proposed algorithms for the overlay scenario perform very similarly, despite the different complexity.
From local averaging to emergent global behaviors: the fundamental role of network interconnections
Venue: arXiv cs.SY 2016
Year: 2016

Distributed averaging is one of the simplest and most studied network dynamics. Its applications range from cooperative inference in sensor networks, to robot formation, to opinion dynamics. A number of fundamental results and examples scattered through the literature are gathered here and originally presented, emphasizing the deep interplay between the network interconnection structure and the emergent global behavior.
A Communication-Free Master-Slave Microgrid with Power Sharing
Venue: arXiv cs.SY 2016
Year: 2016

In this paper a design of a master-slave microgrid consisting of grid-supporting current source inverters and a synchronous generator is proposed. The inverters are following the frequency of the grid imposed by the synchronous generator. Hence, the proposed structure of the microgrid is steadily synchronized. We show that the method achieves power sharing without the need of communication. Furthermore, no change in operation mode is needed during transitions of the microgrid between islanded and grid-connected modes.
Conditional Deep Learning for Energy-Efficient and Enhanced Pattern Recognition
Venue: arXiv cs.CV 2016
Year: 2016

Deep learning neural networks have emerged as one of the most powerful classification tools for vision related applications. However, the computational and energy requirements associated with such deep nets can be quite high, and hence their energy-efficient implementation is of great interest. Although traditionally the entire network is utilized for the recognition of all inputs, we observe that the classification difficulty varies widely across inputs in real-world datasets; only a small fraction of inputs require the full computational effort of a network, while a large majority can be classified correctly with very low effort. In this paper, we propose Conditional Deep Learning (CDL) where the convolutional layer features are used to identify the variability in the difficulty of input instances and conditionally activate the deeper layers of the network. We achieve this by cascading a linear network of output neurons for each convolutional layer and monitoring the output of the linear network to decide whether classification can be terminated at the current stage or not. The proposed methodology thus enables the network to dynamically adjust the computational effort depending upon the difficulty of the input data while maintaining competitive classification accuracy. We evaluate our approach on the MNIST dataset. Our experiments demonstrate that our proposed CDL yields 1.91x reduction in average number of operations per input, which translates to 1.84x improvement in energy. In addition, our results show an improvement in classification accuracy from 97.5% to 98.9% as compared to the original network.
Message-Passing Receiver for Joint Channel Estimation and Decoding in 3D Massive MIMO-OFDM Systems
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we address the message-passing receiver design for the 3D massive MIMO-OFDM systems. With the aid of the central limit argument and Taylor-series approximation, a computationally efficient receiver that performs joint channel estimation and decoding is devised by the framework of expectation propagation. Specially, the local belief defined at the channel transition function is expanded up to the second order with Wirtinger calculus, to transform the messages sent by the channel transition function to a tractable form. As a result, the channel impulse response (CIR) between each pair of antennas is estimated by Gaussian message passing. In addition, a variational expectation-maximization (EM)-based method is derived to learn the channel power-delay-profile (PDP). The proposed joint algorithm is assessed in 3D massive MIMO systems with spatially correlated channels, and the empirical results corroborate its superiority in terms of performance and complexity.
Optimizing Energy Storage Participation in Emerging Power Markets
Venue: arXiv cs.SY 2016
Year: 2016

The growing amount of intermittent renewables in power generation creates challenges for real-time matching of supply and demand in the power grid. Emerging ancillary power markets provide new incentives to consumers (e.g., electrical vehicles, data centers, and others) to perform demand response to help stabilize the electricity grid. A promising class of potential demand response providers includes energy storage systems (ESSs). This paper evaluates the benefits of using various types of novel ESS technologies for a variety of emerging smart grid demand response programs, such as regulation services reserves (RSRs), contingency reserves, and peak shaving. We model, formulate and solve optimization problems to maximize the net profit of ESSs in providing each demand response. Our solution selects the optimal power and energy capacities of the ESS, determines the optimal reserve value to provide as well as the ESS real-time operational policy for program participation. Our results highlight that applying ultra-capacitors and flywheels in RSR has the potential to be up to 30 times more profitable than using common battery technologies such as LI and LA batteries for peak shaving.
Efficient Sampling Set Selection for Bandlimited Graph Signals Using Graph Spectral Proxies
Venue: arXiv cs.IT 2016
Year: 2016

We study the problem of selecting the best sampling set for bandlimited reconstruction of signals on graphs. A frequency domain representation for graph signals can be defined using the eigenvectors and eigenvalues of variation operators that take into account the underlying graph connectivity. Smoothly varying signals defined on the nodes are of particular interest in various applications, and tend to be approximately bandlimited in the frequency basis. Sampling theory for graph signals deals with the problem of choosing the best subset of nodes for reconstructing a bandlimited signal from its samples. Most approaches to this problem require a computation of the frequency basis (i.e., the eigenvectors of the variation operator), followed by a search procedure using the basis elements. This can be impractical, in terms of storage and time complexity, for real datasets involving very large graphs. We circumvent this issue in our formulation by introducing quantities called graph spectral proxies, defined using the powers of the variation operator, in order to approximate the spectral content of graph signals. This allows us to formulate a direct sampling set selection approach that does not require the computation and storage of the basis elements. We show that our approach also provides stable reconstruction when the samples are noisy or when the original signal is only approximately bandlimited. Furthermore, the proposed approach is valid for any choice of the variation operator, thereby covering a wide range of graphs and applications. We demonstrate its effectiveness through various numerical experiments.
Hybrid Spintronic-CMOS Spiking Neural Network With On-Chip Learning: Devices, Circuits and Systems
Venue: arXiv cs.ET 2016
Year: 2016

Over the past decade Spiking Neural Networks (SNN) have emerged as one of the popular architectures to emulate the brain. In SNN, information is temporally encoded and communication between neurons is accomplished by means of spikes. In such networks, spike-timing dependent plasticity mechanisms require the online programming of synapses based on the temporal information of spikes transmitted by spiking neurons. In this work, we propose a spintronic synapse with decoupled spike transmission and programming current paths. The spintronic synapse consists of a ferromagnet-heavy metal heterostructure where programming current through the heavy metal generates spin-orbit torque to modulate the device conductance. Low programming energy and fast programming times demonstrate the efficacy of the proposed device as a nanoelectronic synapse. We perform a simulation study based on an experimentally benchmarked device-simulation framework to demonstrate the interfacing of such spintronic synapses with CMOS neurons and learning circuits operating in transistor sub-threshold region to form a network of spiking neurons that can be utilized for pattern recognition problems.