Keywords:Learning and Inference, Network Games and Algorithms, Machine Learning and Learning Theory Abstract: In recent years, people have increasingly turned to social networks like Twitter and Facebook for news. In contrast to traditional news sources, these platforms allow users to simultaneously read news articles and share opinions with other users. Among other effects, this has led to the rise of fake news, sometimes spread via bots (automated social media accounts masquerading as real users). In this work, we devise and analyze a mathematical model describing such platforms. The model includes a large number of agents attempting to learn an underlying true state of the world in an iterative fashion. The beliefs of the agents about the true state are updated based on noisy observations of the true state and the beliefs of a subset of other agents on the graph, and may include a special type of agent we call bots, who attempt to convince others of an erroneous true state rather than learn (modeling users spreading fake news). This process continues for a finite number of iterations, the learning horizon. Our analysis details three cases for the outcome of this process: agents may learn the true state, mistake the erroneous state promoted by the bots as true, or believe the state falls between the true and erroneous states. Which outcome occurs depends on the relationship between the number of bots and the learning horizon. This leads to several interesting results; e.g., agents can initially learn the true state but later forget it and believe the erroneous state to be true.

Keywords:Learning and Inference, Machine Learning and Learning Theory, Information Theory and Statistics Abstract: We consider the task of tensor estimation, i.e. estimating a low-rank 3-order n x n x n tensor from noisy observations of randomly chosen entries in the sparse regime. In the context of matrix (2-order tensor) estimation, a variety of algorithms have been proposed and analyzed in the literature including the popular collaborative filtering algorithm that is extremely well utilized in practice. However, in the context of tensor estimation, there is limited progress. No natural extensions of collaborative filtering are known beyond flattening the tensor into a matrix and applying standard collaborative filtering. As the main contribution of this work, we introduce a generalization of the collaborative filtering algorithm for the setting of tensor estimation and argue that it achieves sample complexity that (nearly) matches the conjectured lower bound on the sample complexity. Interestingly, our generalization uses the matrix obtained from the flattened tensor to compute similarity as in the classical collaborative filtering but by defining a novel graph using it. The algorithm recovers the tensor with mean-squared-error (MSE) decaying to 0 as long as each entry is observed independently with probability p = Omega(n^{-3/2 + epsilon}) for any arbitrarily small epsilon > 0. It turns out that p = Omega(n^{-3/2}) is the conjectured lower bound as well as the "connectivity threshold" of the graph used in our algorithm.

Keywords:Optimization, Machine Learning and Learning Theory Abstract: A Data Processing Network (DPN) streams massive volumes of data collected and stored by the network to multiple processing units to compute desired results in a timely fashion. Due to ever-increasing traffic, distributed cache nodes can be deployed to store hot data and rapidly deliver them for consumption. However, prior work on caching policies has primarily focused on the potential gains in network performance, e.g., cache hit ratio and download latency, while neglecting the impact of cache on data processing and consumption. In this paper, we propose a novel framework, DeepChunk, which leverages deep Q-learning for chunk-based caching in DPN. We show that cache policies must be optimized for both network performance during data delivery and processing efficiency during data consumption. Specifically, DeepChunk utilizes a model-free approach by jointly learning limited network, data streaming, and processing statistics at runtime and making cache update decisions under the guidance of powerful deep Q-learning. It enables a joint optimization of multiple objectives including chunk hit ratio, stall time, and object download time while being self-adaptive under the time-varying workload and network conditions. We build a prototype implementation of DeepChunk with Ceph, a popular distributed object storage system. Our extensive experiments and evaluation demonstrate significant improvement, i.e., 43% in total reward and 39% in processing stall time, over baseline policies.

Keywords:Learning and Inference, Machine Learning and Learning Theory Abstract: Learning relevant features is important for interpreting data in a machine learning model. Comparing with selecting a relevant feature subset for the entire data, instancewise feature selection is more flexible for model interpretation. However current instancewise feature selection approaches are complex and suffer from high computational cost. We consider instancewise feature selection under supervised learning framework. We design a compact and interpretable neural network to approach the problem. To reduce the computational cost and gain better interpretability, we group relevant features and construct a mixture of neural networks. Using softmax as activation function for sub-model selection, the model membership can be learned accurately through gradient descent. To the best of our knowledge, our model is the first interpretable deep neural network model for instancewise feature selection using end-to-end training.

Keywords:Coding Techniques and Applications, Machine Learning and Learning Theory Abstract: In this paper, we use reinforcement learning to find effective decoding strategies for binary linear codes. We start by reviewing several iterative decoding algorithms that involve a decision-making process at each step, including bit-flipping (BF) decoding, residual belief propagation, and anchor decoding. We then illustrate how such algorithms can be mapped to Markov decision processes allowing for data-driven learning of optimal decision strategies, rather than basing decisions on heuristics or intuition. As a case study, we consider BF decoding for both the binary symmetric and additive white Gaussian noise channel. Our results show that learned BF decoders can offer a range of performance-complexity trade-offs for the considered Reed-Muller and BCH codes, and achieve near-optimal performance in some cases. We also demonstrate learning convergence speed-ups when biasing the learning process towards correct decoding decisions, as opposed to relying only on random explorations and past knowledge.

Keywords:Coding Theory, Computational Models and Representations, Statistical Signal Processing Abstract: A novel deep learning framework for lossy compression is proposed. The framework is based on Deep AutoEncoder (DAE) stacked of Restricted Boltzmann Machines (RBMs), which form Deep Belief Networks (DBNs). The proposed DAE-compression scheme is one variant of the known fixed-distortion scheme, where the distortion is fixed and the compression rate is left to optimize. The fixed distortion is achieved by the DBN Blahut-Arimoto algorithm to approximate the Nth-order rate distortion approximating posterior. The trained DBNs are then unrolled to create a DAE, which produces an encoder and a reproducer. The unrolled DAE is fine-tuned with back-propagation through the whole autoencoder to minimize reconstruction errors.

Keywords:Optimization Abstract: We study the projection onto the set of feasible inputs and the set of feasible solutions of a polynomial optimisation problem (POP). Our motivation is increasing the robustness of solvers for POP: Without a priori guarantees of feasibility of a particular instance, one should like to perform the projection onto the set of feasible inputs prior to running a solver. Without a certificate of optimality, one should like to project the output of the solver onto the set of feasible solutions subsequently. We study the computational complexity, formulations, and convexifications of the projections. Our results are illustrated on IEEE test cases of Alternating Current Optimal Power Flow (ACOPF) problem.

Keywords:Adaptive Control and Automation, Machine Learning and Learning Theory Abstract: This paper focuses on application of subspace identification methods to predict the thermal dynamics of bioimplants, e.g. UEA. Recursive subspace identification method implemented in this paper predicts the temperature readings of heat sensors in an online fashion within a finite time window and updates the system parameters iteratively to improve the performance of the algorithm. Algorithm validation is realized using COMSOL software simulations as well as using an in vitro experimental system. Both simulation and experimental results indicate that the proposed method can accurately predict the thermal dynamics of the system. The experimental results show online prediction of the thermal effect with a mean squared error of 1.569e-2°C for randomly generated Gaussian inputs and 3.46e-3°C for square wave inputs after adaptive filters converge.

Keywords:Optimization, Robust and Nonlinear Control Abstract: This note presents a methodology for the design and the implementation of robust sampled-data systems with maximal sampling periods. The methodology applies to nonlinear input-affine systems. It is shown that optimal outcomes can be approximated by bang-bang controllers that are easy to design and implement.

Keywords:Complex Networked Systems, Decentralized Control Systems Abstract: In this work we study the Laplacian controllability of a class of connected simple graphs. Consider two k-vertex threshold graphs, each with its own unique repeated degree. Suppose the multiplicities of the repeated degrees in the first and second graphs are m_1 and m_2 respectively, where m_1geq m_2. If the two threshold graphs are interconnected via a new edge, it is shown that the minimum number of controllers to render the resulting graph Laplacian controllable is m_1-1 if m_1>m_2, and is 2m_1-3 otherwise. The method to add this new edge and to connect these controllers to ensure the controllability is presented. Numerical examples are provided to illustrate our results.

Keywords:Machine Learning and Learning Theory, Optimization, Learning and Inference Abstract: In this paper, we consider the problem of unsupervised video object segmentation via background subtraction. Specifically, we pose the nonsemantic extraction of a video's moving objects as a nonconvex optimization problem via a sum of sparse and low-rank matrices. The resulting formulation, a nonnegative variant of robust principal component analysis, is more computationally tractable than its commonly employed convex relaxation, although not generally solvable to global optimality. In spite of this limitation, we derive intuitive and interpretable conditions on the video data under which the uniqueness and global optimality of the object segmentation are guaranteed using local search methods. We illustrate these novel optimality criteria through example segmentations using real video data.

Keywords:Data Analytics, Learning and Inference, Complex Networked Systems Abstract: This work investigates the interplay between different types of user interactions on Twitter, with respect to predicting missing or unseen interactions. For example, given a set of retweet interactions between Twitter users, how accurately can we predict reply interactions? Is it more difficult to predict retweet or quote interactions between a pair of accounts? Also, which features of interaction patterns are most important to enable accurate prediction of specific Twitter interactions? Our empirical study of Twitter interactions contributes initial answers to these questions. We have crawled an extensive dataset of Twitter accounts and their follow, quote, retweet, reply interactions over a period of a month. Using a machine learning framework, we find we can accurately predict many interactions of Twitter users. Interestingly, the most predictive features vary with the user profiles, and are not the same across all users. For example, for a pair of users that interact with a large number of other Twitter users, we find that certain “higher-dimensional” triads, i.e., triads that involve multiple types of interactions, are very informative, whereas for less active Twitter users, certain in-degrees and out-degrees play a major role. Finally, we provide various other insights on Twitter user behavior.

Our code and data are available at https://github.com/twittermancer/.

Keywords:Network Games and Algorithms, Distributed and Large-Scale Systems Abstract: Much recent work on autonomous vehicles has focused on the ability of autonomous vehicles to form platoons, decreasing average vehicle headways and thereby increasing road capacities. However, it has recently been noted that autonomous vehicles could also effectively reduce passenger throughput despite the benefits of platooning due to a variety of effects, including the presence of unoccupied vehicles and the fact that increased road capacities can inadvertently lead to increases in aggregate congestion through various selfish routing paradoxes. This paper poses a model of urban traffic congestion in which occupants may choose to exit their vehicles at a workplace and then send the vehicle on to park itself - thus leading to an increased presence of unoccupied vehicles in urban centers. We show how this sets the stage for a tragedy of the commons, as it has the potential to amplify the already-present congestion externalities and how this can lead to increased aggregate congestion for a wide range of parameter values.

Keywords:Detection and Estimation, Statistical Signal Processing, Signal Acquisition, Coding, and Retrieval Abstract: Sparse signals are encountered in a broad range of applications. In order to process these signals using digital hardware, they must be first quantized using an analog-to-digital convertor (ADC), which typically operates in a serial scalar manner. In this work, we propose a method for serial quantization of sparse signals (SeQuanS) inspired by group testing theory, which is designed to reliably and accurately quantize sparse signals acquired in a sequential manner using serial scalar ADCs. Unlike previously proposed approaches which combine quantization and compressed sensing (CS), our SeQuanS scheme updates its representation on each incoming analog sample and does not require the complete signal to be observed and stored in analog prior to quantization. We characterize the asymptotic tradeoff between accuracy and quantization rate of SeQuanS as well as its computational burden. Our numerical results demonstrate that SeQuanS is capable of achieving substantially improved representation accuracy over previous CS-based schemes without requiring the complete set of analog signal samples to be observed prior to its quantization, making it an attractive approach for acquiring sparse time sequences.

Keywords:Machine Learning and Learning Theory, Signal Acquisition, Coding, and Retrieval, Learning and Inference Abstract: In compressed sensing, a primary problem to solve is to reconstruct a high-dimensional sparse signal from a small number of observations. In this work, we develop a new sparse signal recovery algorithm using reinforcement learning (RL) and Monte Carlo Tree Search (MCTS). Similarly to OMP, our RL+MCTS algorithm chooses the support of the signal sequentially. The key novelty is that the proposed algorithm learns how to choose the next support as opposed to following a pre-designed rule as in OMP. Empirical results are provided to demonstrate the superior performance of the proposed RL+MCTS algorithm over existing sparse signal recovery algorithms.

Keywords:Learning and Inference, Network Games and Algorithms Abstract: We revisit the Whittle index policy for scheduling web crawlers for ephemeral content proposed in Avrachenkov and Borkar, IEEE Trans. Control of Network Systems 5(1), 2016, and develop a reinforcement learning scheme for it based on LSPE(0). The scheme leverages the known structural properties of the Whittle index policy.

Keywords:Computational Models and Representations, Robust and Nonlinear Control, Statistical Signal Processing Abstract: A novel approach is employed to obtain closed-form and exact expressions for the time response of LTI systems of arbitrary order in terms of the univariate Fox H-Function. This presents a convenient and efficient method to study the system output to a variety of test functions, including the step, impulse, sinusoidal, exponential and ramp response, simply by altering the parameters of the H-Function. The resulting expressions are verified for accuracy by comparing the system response with simulations of different models. The representation of the time response as an H-Function allows us to obtain the time response of fractional order systems by approximating fractional operators with higher order rational transfer functions. Furthermore, it also leads to a novel expression for the expected value of the output of a fractional order system when driven by a wide-sense stationary (WSS) random process, which is verified against Monte-Carlo simulations.

Keywords:Robotics, Complex Networked Systems, Decentralized Control Systems Abstract: This paper develops a controller synthesis approach for a multi-agent system (MAS) with intermittent communication. We adopt a leader-follower scheme, where a mobile leader with absolute position sensors switches among a set of followers without absolute position sensors to provide each follower with intermittent state information. We model the MAS as a switched system. The followers are to asymptotically reach a predetermined consensus state. To guarantee the stability of the switched system and the consensus of the followers, we derive maximum and minimal dwell-time conditions to constrain the intervals between consecutive time instants at which the leader should provide state information to the same follower. Furthermore, the leader needs to satisfy practical constraints such as charging its battery and staying in specific regions of interest. Both the maximum and minimum dwell-time conditions and these practical constraints can be expressed by metric temporal logic (MTL) specifications. We iteratively compute the optimal control inputs such that the leader satisfies the MTL specifications, while guaranteeing stability and consensus of the followers. We implement the proposed method on a case study with three mobile robots as the followers and one quadrotor as the leader.

Keywords:Robust and Nonlinear Control Abstract: The article deals with linear differential equations with periodic impulsive action in a Banach space. The moments of impulsive action are assumed to satisfy the ADT condition. On the basis of a new comparison principle, the study of this equation is reduced to the study of an auxiliary linear impulsive differential equation with periodic sequence of dwell-times. This equation is a perturbation of some linear periodic differential equation. Separately, cases when the phase space is semi-ordered with the help of a solid, normal and unflattened cone, and considered linear impulsive differential equation is positive with respect to the cone are considered. In these cases, a linear Lyapunov function is constructed. The second case is when the phase space is a Hilbert space. Here, the Lyapunov function is constructed in the quadratic form. The sufficient conditions for the asymptotic stability of linear impulsive differential equations are established. Examples of the application of these results are given.

Keywords:Robust and Nonlinear Control Abstract: The paper proposes a mathematical framework to be used for the homogenization of the Hybrid Dynamical Systems (HDS) state space. This is based on new mathematical paradigms like non-archimedean valued spaces, p-adic rational numbers and rigid algebraic geometry. Although the mathematical concepts are rather complex we believe the value they bring to solving our problem makes it worthwhile. Here we show how a HDS consisting of two sub-systems could be modeled as a Tate curve, cite{Tate}. This paper is a continuation of cite{malta}. We extend and detail here the mathematical framework of embedding a HDS into a Tate curve.

Keywords:Robust and Nonlinear Control, Adaptive Control and Automation, Optimization Abstract: This paper considers observer-based controller design for systems involving input derivatives. First, we analyze the class of systems with derivative inputs which appear naturally or in connection to other class of systems such as singular systems. Due to the presence of input derivatives, we provide a procedure to eliminate the derivative inputs in order to facilitate the process of stabilization by state feedback. The elimination procedure transfers the input derivatives in the output equations. However, we show that the observer can also be designed by using change of variables avoiding derivative inputs in the final observer equation. Consequently, we construct the observer based controller design and establish separation principle for input derivative systems. Numerical example is provided to support the theoretical result.

Keywords:Robust and Nonlinear Control, Optimization, Adaptive Control and Automation Abstract: We present a nonlinear discrete time feedback control design by searching over a family of controls and associated candidate quadratic control Lyapunov functions parameterized by the symmetric positive definite matrices using an ensemble Kalman search. Then we propose a novel relaxation of the control which can be used to tune for a particular implementation. We show that the proposed family of controls are globally exponentially stable for linear systems, and test the controls on both a linear and nonlinear example.

Keywords:Machine Learning and Learning Theory, Optimization Abstract: Gaussian Process based Model Predictive Control (GP-MPC), where the system model is learned from data by a Gaussian Process (GP) statistical model, has gained increasing interests in the control community. This is due to the modeling flexibility of GPs and their ability to provide probabilistic estimates of prediction uncertainty, which can be used to assess and guarantee the performance or safety of a control system. However, GP-MPC optimization problems are typically non-convex and highly demanding, and scales poorly with the model size, causing unsatisfactory solving performance, even with state-of-the-art solvers. These drawbacks hinder the application of GP-MPC in large-scale systems and in real-time control. Our previous work has developed a new concept, linearized Gaussian Process (linGP), and a linGP-based Sequential Convex Programming (linGP-SCP) algorithm that can accelerate solving GP-MPC problems significantly. However, the algorithm ignored uncertainty propagation in its multi-step GP predictions, resulting in over-confident predictions and an over-optimistic, even unsafe, control system. This paper completes linGP-SCP by incorporating uncertainty propagation into GP-MPC and overcoming the computational challenge of uncertainty propagation to maintain the scalability and good performance of the overall algorithm. The improved algorithm is validated in two numerical examples, including a real-time control example of swinging up a single-arm pendulum.

Keywords:Information Theory Abstract: In covert communication, a transmitter attempts to send a message over a channel while avoiding detection from a warden. We investigate here how the warden's knowledge of the code used by the transmitter and the receiver influences the optimal number of bits that can be covertly and reliably sent. We formulate the problem in three scenarios: the warden completely knows the code, the warden knows only the rate and an upper-bound on the probability of error at the decoder, and the warden has access to previous samples of its channel when the code was used. The first scenario corresponds to the standard model in covert communication. For the second scenario, we characterize the number of bits that can be transmitted reliably subject to a covertness constraint up to the first-order of asymptotics. Finally, for the third scenario, we provide lower- and upper-bound on the number of bits that can be transmitted reliably subject to a covertness constraint for two scalings of the number of observed samples.

Keywords:Information Theory, Information Theory and Statistics Abstract: We investigate the concavity deficit of the entropy functional. Some properties of the skew-divergence are developed and a ``skew'' chi-square divergence is introduced. Various relationships between these f-divergences are established, including a reverse Pinsker type inequality for the skew divergence, which in turn yields a sharpening on the upper bound for the entropic concavity deficit.

Keywords:Information Theory Abstract: We extend the framework of empirical coordination to a distributed setup where for a given action by nature, multiple descriptions of the action of the decoder are available. We adopt the coding strategy applied by El Gamal and Cover in [1] to get a lower bound of the coordination region. Then, we improve this region by applying the coding scheme applied by Zhang and Berger in [2].

Keywords:Information Theory, Information Theory and Statistics, Information Theoretic Approaches in Wireless Communications Abstract: The achievability and converse bounds on the throughput of covert communication over AWGN channels are investigated in this paper. By re-visiting cite{Polyanskiy}, several new achievability bounds on maximal and average probability of error based on random coding scheme are presented, which leads to results on achievability bounds when the codewords are generated from Gaussian distribution and then selected from a subset under maximal power constraint. The bounds provide us the framework for analyzing the maximal throughput under covert constraint of total variation distance.

Keywords:Information Theory, Decentralized Control Systems, Detection and Estimation Abstract: We consider the following communication scenario. An encoder causally observes the Wiener process and decides when and what to transmit about it. A decoder makes real-time estimation of the process using causally received codewords. We determine the causal encoding and decoding policies that minimize the mean-square estimation error, under the long-term communication rate constraint of R bit/s. We show that an optimal encoding policy can be implemented as a causal sampling policy followed by a compressing policy. We prove that the optimal encoding policy samples the Wiener process once the innovation passes either sqrt(1/R) or -sqrt(1/R), and compresses the sign of the innovation (SOI) using a 1-bit codeword. The SOI coding scheme achieves the operational distortion-rate function equal to 1/6R. This is better than the distortion-rate tradeoff achieved in the limit of infinite delay by the best non-causal code, because the SOI coding scheme leverages free timing information supplied by the zero-delay channel between the encoder and the decoder. The key is the event-triggered nature of the SOI sampling policy. In contrast, the distortion-rate tradeoffs achieved with deterministic sampling policies are worse: we prove that the causal informational distortion-rate function in that scenario is 5/6R, achieved by the uniform sampling policy with sampling interval 1/R. The optimal strategy is to sample the process as fast as possible and to transmit 1-bit codewords without delay.

Keywords:Information Theory Abstract: In this paper, we consider the multi-server setting of Private Information Retrieval with Private Coded Side Information (PIR-PCSI) problem. In this problem, there is a database of K messages whose copies are replicated across N servers, and there is a user who knows a random linear combination of a random subset of M messages in the database as side information. The user wishes to download one message from the servers, while protecting the identities of both the demand message and the messages contributing to the side information. We assume that the servers know the number of messages contributing to the user's side information in advance, whereas the indices of these messages and their coefficients in the side information are not known to any of the servers a priori.

Our goal is to characterize (or derive a lower bound on) the capacity, i.e., the maximum achievable download rate, for the following two settings. In the first setting, the set of messages contributing to the linear combination available to the user as side information, does not include the message demanded by the user. In the second setting, the demand message is one of the messages that form the user's side information. The proposed achievability schemes and proof techniques leverage ideas from both our recent methods proposed for the single-server PIR-PCSI problem as well as the techniques proposed by Sun and Jafar for multi-server private computation problem.

Keywords:Information Theory Abstract: We study the biometric identification systems without privacy leakage. Privacy preserving biometric identification systems that involve helper data, secret keys and private keys are considered. The helper data are stored in a public database and can be used to support the user identification. The secret key is either stored in an encrypted database or handed to the user, which can be used for authentication. Since the helper data are public and releasing the biometric information invokes privacy issues, the public helper data can only leak a negligible amount of biometric information. To achieve this, we use private keys to mask the helper data such that the public helper data contain as little as possible information about the biometrics. Moreover, a two-stage extension is also studied, where the clustering method is used such that the search complexity in the identification phase can be reduced.

Keywords:Statistical Signal Processing, Detection and Estimation, Learning and Inference Abstract: Eye-blinks are known to substantially contaminate EEG signals, and thereby severely impact the decoding of EEG signals in various medical and scientific applications. In this work, we consider the problem of eye-blink detection that can then be employed to reliably remove eye-blinks from EEG signals. We propose a fully automated and unsupervised eye-blink detection algorithm, Blink that self-learns user-specific brainwave profiles for eye-blinks. Hence, Blink does away with any user training or manual inspection requirements. Blink functions on a single channel EEG, and is capable of estimating the start and end timestamps of eye-blinks in a precise manner. We collect four different eye-blink datasets and annotate 2300+ eye-blinks to evaluate the robustness performance of Blink across headsets (OpenBCI and Muse), eye-blink types (voluntary and involuntary), and various user activities (watching a video, reading an article, and attending to an external stimulation). The Blink algorithm performs consistently with an accuracy of over 98% for all the tasks with an average precision of 0.934. The source code and annotated datasets are released publicly for reproducibility and further research. To the best of our knowledge, this is the first ever annotated eye-blink EEG dataset released in the public domain.

Keywords:Statistical Signal Processing, Learning and Inference, Data Analytics Abstract: We introduce contrastive multivariate singular spectrum analysis, a novel unsupervised method for dimensionality reduction and signal decomposition of time series data. By utilizing an appropriate background dataset, the method transforms a target time series dataset in a way that evinces the sub-signals that are enhanced in the target dataset, as opposed to only those that account for the greatest variance. This shifts the goal from finding signals that explain the most variance to signals that matter the most to the analyst. We demonstrate our method on an illustrative synthetic example, as well as show the utility of our method in the downstream clustering of real electrocardiogram and electromyogram signals. We end with a physical interpretation of the algorithm.

Keywords:Statistical Signal Processing, Detection and Estimation Abstract: We consider the problem of adaptive blind separation of two sources from their instantaneous mixtures. We focus on the case where the two sources are not necessarily independent. By analyzing a general form of adaptive algorithms we show that separation is possible not only for independent sources but also for sources that are dependent provided their joint pdf satisfies certain symmetry conditions. We also identify the class of dependent sources that are non-separable, namely, the counterpart of Gaussian sources of the independent case. We corroborate our theoretical analysis with a number of simulations and give examples of dependent sources that can be easily separated.

Keywords:Detection and Estimation, Statistical Signal Processing Abstract: Receiver operating characteristics (ROCs) are a well-established representation of the tradeoff between detection and false alarm probabilities in classical binary hypothesis testing. We use classical ROCs as motivation for two types of operating characteristics for binary hypothesis testing in quantum systems -- decision operating characteristics (QDOCs) and measurement operating characteristics (QMOCs). Both are described in the context of a framework we propose that encompasses binary hypothesis testing in both classical and quantum systems. Helstrom's well-known result regarding distinguishing between two quantum density operators with minimum probability of error is interpreted in this framework, which leads to the observation that there are many different ways of distinguishing between two quantum density operators with minimum probability of error. One option is Helstrom's optimal standard measurement, others use non-standard measurements. Using the concept of Parseval frames, we define a constructive procedure for generating both standard and non-standard measurements that achieve minimum probability of error.

Keywords:Statistical Signal Processing, Distributed and Large-Scale Systems, Machine Learning and Learning Theory Abstract: In this work, we consider the problem of distributed approximation of functions over multiple-access channels with additive noise. In contrast to previous works, we take fast fading into account and give explicit probability bounds for the approximation error allowing us to derive bounds on the number of channel uses that are needed to approximate a function up to a given approximation accuracy. Neither the fading nor the noise process is limited to Gaussian distributions. Instead, we consider sub-gaussian random variables which include Gaussian as well as many other distributions of practical relevance. The results are motivated by and have immediate applications to a) computing predictors in models for distributed machine learning and b) the max-consensus problem in ultra-dense networks.

Keywords:Statistical Signal Processing, Signal Acquisition, Coding, and Retrieval Abstract: Compressive sensing (CS) can recover a sparse signal x reliably under an indefinite linear system. However, corruption with noise can severely damage the system performance. For Gaussian deviation, a noise whitening method is often used which leads to the noise folding phenomenon, increasing the noise energy greatly. In this paper, we introduce a different approach and design a new optimization model to recover x with ell_{infty} norm. Moreover, in our setup, the signal (prior to corruption by noise) is only pseudo sparse. We analyze the solution exactness and show that a unique solution close to the true values of pseudo-sparse signals can be obtained in an indefinite system with uniform magnitude noise. We then relax the uniform-magnitude assumption and use Gaussian noise in simulations. We show that, compared to the noise-whitening method, our method can reduce almost 50% of the noise by only sacrificing less than 0.3% of the support-set recovery rate.

Keywords:Wireless Communication Systems, Network Games and Algorithms, Sensor Networks in Communications Abstract: We consider a setting where multiple active sources send real-time updates over a single-hop wireless broadcast network to a monitoring station. Our goal is to design a scheduling policy that minimizes the time-average of general non-decreasing cost functions of Age of Information.

We use a Whittle index based approach to find low complexity scheduling policies that have good performance, for reliable as well as unreliable channels. We prove that for a system with two sources, having possibly different cost functions and reliable channels, the Whittle index policy is exactly optimal. For reliable channels, we also derive structural properties of an optimal policy, that suggest that the performance of the Whittle index policy may be close to optimal in general. These results might also be of independent interest in the study of restless multi-armed bandit problems with similar underlying structure. Finally, we provide simulations comparing the Whittle index policy with optimal scheduling policies found using dynamic programming, which support our results.

Keywords:Wireless Communication Systems, Machine Learning and Learning Theory, Adaptive Control and Automation Abstract: We consider a multicast scheme recently proposed for a wireless downlink [1]. It was shown earlier that power control can significantly improve its performance. However for this system, obtaining optimal power control is intractable because of a very large state space. Therefore in this paper we use deep reinforcement learning where we use function approximation of the Q-function via a deep neural network. We show that optimal power control can be learnt for reasonably large systems via this approach. The average power constraint is ensured via a Lagrange multiplier, which is also learnt. In the longer version of the paper [2], we also demonstrate that our learning algorithm can be modified to allow the optimal control to track the time varying system statistics.

Keywords:Wireless Communication Systems Abstract: In this paper, we consider a wireless network setting where a base station (BS) employs a single unmanned aerial vehicle (UAV) mobile relay to disseminate information to multiple users in the presence of multiple adversaries. The BS, which is on the ground, has no direct link to the users or the adversaries, who are also on the ground. We optimize the joint transmit power of the BS and the UAV, and the UAV trajectory. We introduce the information causality constraint and maximize the average worst-case secrecy rate in the presence of the adversaries. The formulated average worst-case secrecy rate optimization problem is not convex and is solved sub-optimally. First, we optimize transmit power of the BS and the UAV under a given UAV trajectory. Then, we optimize the UAV trajectory under the sub-optimal UAV and BS transmit power. An efficient algorithm solves the average worst-case secrecy rate maximization problem iteratively until it converges. Finally, simulation results are provided, which demonstrate the correspondence of the UAV optimal track and transmit power allocation to what is suggested by the previous theoretic results.

Keywords:Wireless Communication Systems, Information Theory, Information Theory and Statistics Abstract: To make huge bandwidths in the license free mmWave band available for consumer products like WLAN, novel physical challenges have to be overcome. Spatial sparsity, pathloss and expensive implementation of analog hardware have lead to the concept of hybrid analog and digital architectures that are well known in the technical community by now. In contrast to classical MIMO systems in the legacy bands, where signal processing can be done fully digital (FD), hybrid concepts come with constraints in terms of flexibility, performance and signal processing overhead. Thus, as soon as progress in hardware- and material science will allow to produce cost- and energy efficient RF components, the ability to implement FD MIMO designs in the mmWave bands will allow to overcome those constraints. In our paper we investigate how typical mmWave channels allow to make use of FD MIMO in terms of performance improvements and up to which number of spatial streams gains can be expected. We analyze achievable rates based on the channel model of the latest WLAN standard IEEE 802.11ay in the scenario of an indoor conference room and application oriented design parameters. Further, we compare results to a more basic narrowband channel model, often used in academia. Results show that when 2 spatial separated antenna arrays in a FD system are used, rate improvements of up to ≈92% under LOS-, and ≈79% under NLOS-conditions can be expected, if 10 spatial streams rather than 2 are transmitted.

Keywords:Wireless Communication Systems, Information Theory and Statistics Abstract: We characterize the stability, metastability, and the stationary regime of traffic dynamics in a single-cell uplink wireless system. The traffic is represented in terms of spatial birth-death processes, in which users arrive as a Poisson point process in time and space, each with a file to transmit to the base station. The service rate of each user is based on its signal to interference plus noise ratio, where the interference is from other active users in the cell. Once the file is fully transmitted, the user leaves the cell. We derive the necessary and sufficient condition for network stability, which is independent of the specific path loss function as long as it satisfies mild boundedness conditions. A novel observation, shown through mean-field analysis and simulations, is that for a certain range of arrival rates, the network appears stable for possibly a long time, but can suddenly become unstable. This property is called metastability which is widely known in statistical physics but rarely observed in wireless communication. Finally, using mean-field analysis, we propose a heuristic characterization of the network steady-state regime when it exists, and demonstrate that it is tight for the whole range of arrival rates.

Keywords:Sensor Networks in Communications, Performance Analysis, Sensor Networks Abstract: In this paper, we study how to collect fresh data in time-varying networks with power constrained users. We measure data freshness from the perspective of the central controller by using the metric Age of Information, namely the time elapsed since the generation time-stamp of the freshest information. We wonder what is the minimum AoI performance the network can achieve and how to design scheduling algorithms to approach it. To answer these questions when scheduling decisions are restricted to bandwidth constraint, we first decouple the multi-user scheduling problem into a single user constrained Markov decision process (CMDP) through relaxation of the hard bandwidth constraint. Next we exploit the threshold structure of the optimal policy for the decoupled single user CMDP and obtain the optimum solution through linear programming (LP). Finally, an asymptotic optimal truncated policy that can satisfy the hard bandwidth constraint is built upon the optimal solution to each of the decoupled single-user sub-problem. The performance is verified through simulations. Our investigation shows that to obtain a small AoI performance, the scheduler exploits good channels to schedule users supported by limited power. Users equipped with enough transmission power are updated in a timely manner such that the bandwidth constraint can be satisfied.