Search

We consider the problem of privately estimating the mean of vectors distributed across different nodes of an unreliable wireless network, where communications between nodes can fail intermittently. We adopt a semi-decentralized setup, wherein to mitigate the impact of intermittently connected links, nodes can collaborate with their neighbors to compute a local consensus, which they relay to a central server. In such a setting, the communications between any pair of nodes must ensure that the privacy of the nodes is rigorously maintained to prevent unauthorized information leakage. We study the tradeoff between collaborative relaying and privacy leakage due to the data sharing among nodes and, subsequently, propose PriCER: Private Collaborative Estimation via Relaying -- a differentially private collaborative algorithm for mean estimation to optimize this tradeoff. The privacy guarantees of PriCER arise (i) implicitly, by exploiting the inherent stochasticity of the flaky network connections, and (ii) explicitly, by adding Gaussian perturbations to the estimates exchanged by the nodes. Local and central privacy guarantees are provided against eavesdroppers who can observe different signals, such as the communications amongst nodes during local consensus and (possibly multiple) transmissions from the relays to the central server. We substantiate our theoretical findings with numerical simulations. Our implementation is available at https://github.com/rajarshisaha95/private-collaborative-relaying., Comment: 14 pages, 6 figures. arXiv admin note: text overlap with arXiv:2303.00035

Collaborative inference in next-generation networks can enhance Artificial Intelligence (AI) applications, including autonomous driving, personal identification, and activity classification. This method involves a three-stage process: a) data acquisition through sensing, b) feature extraction, and c) feature encoding for transmission. Transmission of the extracted features entails the potential risk of exposing sensitive personal data. To address this issue, in this work a new privacy-protecting collaborative inference mechanism is developed. Under this mechanism, each edge device in the network protects the privacy of extracted features before transmitting them to a central server for inference. This mechanism aims to achieve two main objectives while ensuring effective inference performance: 1) reducing communication overhead, and 2) maintaining strict privacy guarantees during features transmission.

The prohibitive sizes of Large Language Models (LLMs) today make it difficult to deploy them on memory-constrained edge devices. This work introduces $\rm CALDERA$ -- a new post-training LLM compression algorithm that harnesses the inherent low-rank structure of a weight matrix $\mathbf{W}$ by approximating it via a low-rank, low-precision decomposition as $\mathbf{W} \approx \mathbf{Q} + \mathbf{L}\mathbf{R}$. Here, $\mathbf{L}$ and $\mathbf{R}$ are low rank factors, and the entries of $\mathbf{Q}$, $\mathbf{L}$ and $\mathbf{R}$ are quantized. The model is compressed by substituting each layer with its $\mathbf{Q} + \mathbf{L}\mathbf{R}$ decomposition, and the zero-shot performance of the compressed model is evaluated. Additionally, $\mathbf{L}$ and $\mathbf{R}$ are readily amenable to low-rank adaptation, consequently enhancing the zero-shot performance. $\rm CALDERA$ obtains this decomposition by formulating it as an optimization problem $\min_{\mathbf{Q},\mathbf{L},\mathbf{R}}\lVert(\mathbf{Q} + \mathbf{L}\mathbf{R} - \mathbf{W})\mathbf{X}^\top\rVert_{\rm F}^2$, where $\mathbf{X}$ is the calibration data, and $\mathbf{Q}, \mathbf{L}, \mathbf{R}$ are constrained to be representable using low-precision formats. Theoretical upper bounds on the approximation error of $\rm CALDERA$ are established using a rank-constrained regression framework, and the tradeoff between compression ratio and model performance is studied by analyzing the impact of target rank and quantization bit budget. Results illustrate that compressing LlaMa-$2$ $7$B/$70$B and LlaMa-$3$ $8$B models obtained using $\rm CALDERA$ outperforms existing post-training LLM compression techniques in the regime of less than $2.5$ bits per parameter. The implementation is available at: \href{https://github.com/pilancilab/caldera}{https://github.com/pilancilab/caldera}., Comment: 30 pages, 9 figures, 7 tables

We study the private online change detection problem for dynamic communities, using a censored block model (CBM). Focusing on the notion of edge differential privacy (DP), we seek to understand the fundamental tradeoffs between the privacy budget, detection delay, and exact community recovery of community labels. We establish the theoretical lower bound on the delay in detecting changes privately and propose an algorithm capable of identifying changes in the community structure, while maintaining user privacy. Further, we provide theoretical guarantees for the effectiveness of our proposed method by showing necessary and sufficient conditions on change detection and exact recovery under edge DP. Simulation and real data examples are provided to validate the proposed method.

Multi-agent cyberphysical systems enable new capabilities in efficiency, resilience, and security. The unique characteristics of these systems prompt a reevaluation of their security concepts, including their vulnerabilities, and mechanisms to mitigate these vulnerabilities. This survey paper examines how advancement in wireless networking, coupled with the sensing and computing in cyberphysical systems, can foster novel security capabilities. This study delves into three main themes related to securing multi-agent cyberphysical systems. First, we discuss the threats that are particularly relevant to multi-agent cyberphysical systems given the potential lack of trust between agents. Second, we present prospects for sensing, contextual awareness, and authentication, enabling the inference and measurement of ``inter-agent trust" for these systems. Third, we elaborate on the application of quantifiable trust notions to enable ``resilient coordination," where ``resilient" signifies sustained functionality amid attacks on multiagent cyberphysical systems. We refer to the capability of cyberphysical systems to self-organize, and coordinate to achieve a task as autonomy. This survey unveils the cyberphysical character of future interconnected systems as a pivotal catalyst for realizing robust, trust-centered autonomy in tomorrow's world.

We develop a resilient binary hypothesis testing framework for decision making in adversarial multi-robot crowdsensing tasks. This framework exploits stochastic trust observations between robots to arrive at tractable, resilient decision making at a centralized Fusion Center (FC) even when i) there exist malicious robots in the network and their number may be larger than the number of legitimate robots, and ii) the FC uses one-shot noisy measurements from all robots. We derive two algorithms to achieve this. The first is the Two Stage Approach (2SA) that estimates the legitimacy of robots based on received trust observations, and provably minimizes the probability of detection error in the worst-case malicious attack. Here, the proportion of malicious robots is known but arbitrary. For the case of an unknown proportion of malicious robots, we develop the Adversarial Generalized Likelihood Ratio Test (A-GLRT) that uses both the reported robot measurements and trust observations to estimate the trustworthiness of robots, their reporting strategy, and the correct hypothesis simultaneously. We exploit special problem structure to show that this approach remains computationally tractable despite several unknown problem parameters. We deploy both algorithms in a hardware experiment where a group of robots conducts crowdsensing of traffic conditions on a mock-up road network similar in spirit to Google Maps, subject to a Sybil attack. We extract the trust observations for each robot from actual communication signals which provide statistical information on the uniqueness of the sender. We show that even when the malicious robots are in the majority, the FC can reduce the probability of detection error to 30.5% and 29% for the 2SA and the A-GLRT respectively., Comment: 21 pages, 5 figures, 1 table. arXiv admin note: substantial text overlap with arXiv:2209.12285

This work considers the problem of Distributed Mean Estimation (DME) over networks with intermittent connectivity, where the goal is to learn a global statistic over the data samples localized across distributed nodes with the help of a central server. To mitigate the impact of intermittent links, nodes can collaborate with their neighbors to compute local consensus which they forward to the central server. In such a setup, the communications between any pair of nodes must satisfy local differential privacy constraints. We study the tradeoff between collaborative relaying and privacy leakage due to the additional data sharing among nodes and, subsequently, propose a novel differentially private collaborative algorithm for DME to achieve the optimal tradeoff. Finally, we present numerical simulations to substantiate our theoretical findings., Comment: 10 pages, 4 figures

This work focuses on the problem of distributed optimization in multi-agent cyberphysical systems, where a legitimate agents' iterates are influenced both by the values it receives from potentially malicious neighboring agents, and by its own self-serving target function. We develop a new algorithmic and analytical framework to achieve resilience for the class of problems where stochastic values of trust between agents exist and can be exploited. In this case we show that convergence to the true global optimal point can be recovered, both in mean and almost surely, even in the presence of malicious agents. Furthermore, we provide expected convergence rate guarantees in the form of upper bounds on the expected squared distance to the optimal value. Finally, numerical results are presented that validate our analytical convergence guarantees even when the malicious agents compose the majority of agents in the network and where existing methods fail to converge to the optimal nominal points.

We develop a resilient binary hypothesis testing framework for decision making in adversarial multi-robot crowdsensing tasks. This framework exploits stochastic trust observations between robots to arrive at tractable, resilient decision making at a centralized Fusion Center (FC) even when i) there exist malicious robots in the network and their number may be larger than the number of legitimate robots, and ii) the FC uses one-shot noisy measurements from all robots. We derive two algorithms to achieve this. The first is the Two Stage Approach (2SA) that estimates the legitimacy of robots based on received trust observations, and provably minimizes the probability of detection error in the worst-case malicious attack. Here, the proportion of malicious robots is known but arbitrary. For the case of an unknown proportion of malicious robots, we develop the Adversarial Generalized Likelihood Ratio Test (A-GLRT) that uses both the reported robot measurements and trust observations to estimate the trustworthiness of robots, their reporting strategy, and the correct hypothesis simultaneously. We exploit special problem structure to show that this approach remains computationally tractable despite several unknown problem parameters. We deploy both algorithms in a hardware experiment where a group of robots conducts crowdsensing of traffic conditions on a mock-up road network similar in spirit to Google Maps, subject to a Sybil attack. We extract the trust observations for each robot from actual communication signals which provide statistical information on the uniqueness of the sender. We show that even when the malicious robots are in the majority, the FC can reduce the probability of detection error to 30.5% and 29% for the 2SA and the A-GLRT respectively., Comment: 12 pages, 4 figures, extended version of conference submission

We present a semi-decentralized federated learning algorithm wherein clients collaborate by relaying their neighbors' local updates to a central parameter server (PS). At every communication round to the PS, each client computes a local consensus of the updates from its neighboring clients and eventually transmits a weighted average of its own update and those of its neighbors to the PS. We appropriately optimize these averaging weights to ensure that the global update at the PS is unbiased and to reduce the variance of the global update at the PS, consequently improving the rate of convergence. Numerical simulations substantiate our theoretical claims and demonstrate settings with intermittent connectivity between the clients and the PS, where our proposed algorithm shows an improved convergence rate and accuracy in comparison with the federated averaging algorithm., Comment: Accepted for presentation at the IEEE ISIT 2022. This is a conference version of arXiv:2202.11850

We present a composite wireless fading model encompassing multipath fading and shadowing based on fluctuating two-ray (FTR) fading and inverse gamma (IG) shadowing. We first determine an alternative framework for the statistical characterization and performance evaluation of the FTR fading model, which is based on the fact that the FTR fading distribution can be described as an underlying Rician Shadowed (RS) distribution with continuously varying parameter Kr (ratio of specular to diffuse components). We demonstrate that this new formulation permits to obtain a closed-form expression of the generalized moment generating function (GMGF) of the FTR model, from which the PDF and CDF of the composite IG/FTR model can be obtained in closed-form. The exact and asymptotic outage probability of the IG/FTR model are analyzed and verified by Monte Carlo simulations., Comment: This work has been submitted to the IEEE for publication. Copyright may be transferred without notice, after which this version may no longer be accessible. arXiv admin note: substantial text overlap with arXiv:2108.02990

Intermittent connectivity of clients to the parameter server (PS) is a major bottleneck in federated edge learning frameworks. The lack of constant connectivity induces a large generalization gap, especially when the local data distribution amongst clients exhibits heterogeneity. To overcome intermittent communication outages between clients and the central PS, we introduce the concept of collaborative relaying wherein the participating clients relay their neighbors' local updates to the PS in order to boost the participation of clients with poor connectivity to the PS. We propose a semi-decentralized federated learning framework in which at every communication round, each client initially computes a local consensus of a subset of its neighboring clients' updates, and eventually transmits to the PS a weighted average of its own update and those of its neighbors'. We appropriately optimize these local consensus weights to ensure that the global update at the PS is unbiased with minimal variance - consequently improving the convergence rate. Numerical evaluations on the CIFAR-10 dataset demonstrate that our collaborative relaying approach outperforms federated averaging-based benchmarks for learning over intermittently-connected networks such as when the clients communicate over millimeter wave channels with intermittent blockages.

High-dimensional models often have a large memory footprint and must be quantized after training before being deployed on resource-constrained edge devices for inference tasks. In this work, we develop an information-theoretic framework for the problem of quantizing a linear regressor learned from training data $(\mathbf{X}, \mathbf{y})$, for some underlying statistical relationship $\mathbf{y} = \mathbf{X}\boldsymbol{\theta} + \mathbf{v}$. The learned model, which is an estimate of the latent parameter $\boldsymbol{\theta} \in \mathbb{R}^d$, is constrained to be representable using only $Bd$ bits, where $B \in (0, \infty)$ is a pre-specified budget and $d$ is the dimension. We derive an information-theoretic lower bound for the minimax risk under this setting and propose a matching upper bound using randomized embedding-based algorithms which is tight up to constant factors. The lower and upper bounds together characterize the minimum threshold bit-budget required to achieve a performance risk comparable to the unquantized setting. We also propose randomized Hadamard embeddings that are computationally efficient and are optimal up to a mild logarithmic factor of the lower bound. Our model quantization strategy can be generalized and we show its efficacy by extending the method and upper-bounds to two-layer ReLU neural networks for non-linear regression. Numerical simulations show the improved performance of our proposed scheme as well as its closeness to the lower bound., Comment: 50 pages, 31 figures, 9 tables

A two-part successive syndrome-check decoding of polar codes is proposed with the first part successively refining the received codeword and the second part checking its syndrome. A new formulation of the successive-cancellation (SC) decoding algorithm is presented that allows for successively refining the received codeword by comparing the log-likelihood ratio value of a frozen bit with its predefined value. The syndrome of the refined received codeword is then checked for possible errors. In case there are no errors, the decoding process is terminated. Otherwise, the decoder continues to refine the received codeword. The proposed method is extended to the case of SC list (SCL) decoding by terminating the decoding process when the syndrome of the best candidate in the list indicates no errors. Simulation results show that the proposed method reduces the time-complexity of SC and SCL decoders and their fast variants, especially at high signal-to-noise ratios., Comment: 2021 Asilomar Conference on Signals, Systems, and Computers

We consider a centralized detection problem where sensors experience noisy measurements and intermittent connectivity to a centralized fusion center. The sensors collaborate locally within predefined sensor clusters and fuse their noisy sensor data to reach a common local estimate of the detected event in each cluster. The connectivity of each sensor cluster is intermittent and depends on the available communication opportunities of the sensors to the fusion center. Upon receiving the estimates from all the connected sensor clusters the fusion center fuses the received estimates to make a final determination regarding the occurrence of the event across the deployment area. We refer to this hybrid communication scheme as a \emph{cloud-cluster} architecture. We propose a method for optimizing the decision rule for each cluster and analyzing the expected detection performance resulting from our hybrid scheme. Our method is tractable and addresses the high computational complexity caused by heterogeneous sensors' and clusters' detection quality, heterogeneity in their communication opportunities, and non-convexity of the loss function. Our analysis shows that clustering the sensors provides resilience to noise in the case of low sensor communication probability with the cloud. For larger clusters, a steep improvement in detection performance is possible even for a low communication probability by using our cloud-cluster architecture., Comment: Accepted for publication in the IEEE Transactions on Wireless Communications. Preliminary results were presented in part at the IEEE Global Communications Conference 2020, arXiv:2005.12495

When humans collaborate with each other, they often make decisions by observing others and considering the consequences that their actions may have on the entire team, instead of greedily doing what is best for just themselves. We would like our AI agents to effectively collaborate in a similar way by capturing a model of their partners. In this work, we propose and analyze a decentralized Multi-Armed Bandit (MAB) problem with coupled rewards as an abstraction of more general multi-agent collaboration. We demonstrate that na\"ive extensions of single-agent optimal MAB algorithms fail when applied for decentralized bandit teams. Instead, we propose a Partner-Aware strategy for joint sequential decision-making that extends the well-known single-agent Upper Confidence Bound algorithm. We analytically show that our proposed strategy achieves logarithmic regret, and provide extensive experiments involving human-AI and human-robot collaboration to validate our theoretical findings. Our results show that the proposed partner-aware strategy outperforms other known methods, and our human subject studies suggest humans prefer to collaborate with AI agents implementing our partner-aware strategy., Comment: 14 pages, 13 figures. To be presented at "Thirty-Sixth AAAI Conference on Artificial Intelligence (AAAI) 2022". Also presented at "Artificial Intelligence for Human-Robot Interaction (AI-HRI) at AAAI Fall Symposium Series 2021"

We present two alternative formulations for the distribution of the fluctuating two-ray (FTR) fading model, which simplify its statistical characterization and subsequent use for performance evaluation. New expressions for the probability density function (PDF) and cumulative distribution function of the FTR model are obtained based on the observation that the FTR fading distribution is described, for arbitrary $m$, as an underlying Rician Shadowed (RS) distribution with continuously varying parameter $K$, while for the special case of $m$ being an integer, the FTR fading model is described in terms of a finite number of underlying squared Nakagami-$m$ distributions. It is shown that the chief statistics and any performance metric that are computed by averaging over the PDF of the FTR fading model can be expressed in terms of a finite-range integral over the corresponding statistic or performance metric for the RS (for arbitrary $m$) or the Nakagami-$m$ (for integer $m$) fading models, which have a simpler analytical characterization than the FTR model and for which many results are available in closed-form. New expressions for some Laplace-domain statistics of interest are also obtained; these are used to exemplify the practical relevance of this new formulation for performance analysis., Comment: This work has been submitted to the IEEE for publication. Copyright may be transferred without notice, after which this version may no longer be accessible

A low-complexity tree search approach is presented that achieves the maximum-likelihood (ML) decoding performance of Reed-Muller (RM) codes. The proposed approach generates a bit-flipping tree that is traversed to find the ML decoding result by performing successive-cancellation decoding after each node visit. A depth-first search (DFS) and a breadth-first search (BFS) scheme are developed and a log-likelihood-ratio-based bit-flipping metric is utilized to avoid redundant node visits in the tree. Several enhancements to the proposed algorithm are presented to further reduce the number of node visits. Simulation results confirm that the BFS scheme provides a lower average number of node visits than the existing tree search approach to decode RM codes.

We study first-order optimization algorithms under the constraint that the descent direction is quantized using a pre-specified budget of $R$-bits per dimension, where $R \in (0 ,\infty)$. We propose computationally efficient optimization algorithms with convergence rates matching the information-theoretic performance lower bounds for: (i) Smooth and Strongly-Convex objectives with access to an Exact Gradient oracle, as well as (ii) General Convex and Non-Smooth objectives with access to a Noisy Subgradient oracle. The crux of these algorithms is a polynomial complexity source coding scheme that embeds a vector into a random subspace before quantizing it. These embeddings are such that with high probability, their projection along any of the canonical directions of the transform space is small. As a consequence, quantizing these embeddings followed by an inverse transform to the original space yields a source coding method with optimal covering efficiency while utilizing just $R$-bits per dimension. Our algorithms guarantee optimality for arbitrary values of the bit-budget $R$, which includes both the sub-linear budget regime ($R < 1$), as well as the high-budget regime ($R \geq 1$), while requiring $O\left(n^2\right)$ multiplications, where $n$ is the dimension. We also propose an efficient relaxation of this coding scheme using Hadamard subspaces that requires a near-linear time, i.e., $O\left(n \log n\right)$ additions.Furthermore, we show that the utility of our proposed embeddings can be extended to significantly improve the performance of gradient sparsification schemes. Numerical simulations validate our theoretical claims. Our implementations are available at https://github.com/rajarshisaha95/DistOptConstrComm., Comment: 41 pages, 26 figures, 1 table. This work has been accepted for publication in the IEEE Journal on Selected Areas in Information Theory (JSAIT), Spl. issue on Distributed Coding and Computation

This work considers the problem of resilient consensus where stochastic values of trust between agents are available. Specifically, we derive a unified mathematical framework to characterize convergence, deviation of the consensus from the true consensus value, and expected convergence rate, when there exists additional information of trust between agents. We show that under certain conditions on the stochastic trust values and consensus protocol: 1) almost sure convergence to a common limit value is possible even when malicious agents constitute more than half of the network connectivity, 2) the deviation of the converged limit, from the case where there is no attack, i.e., the true consensus value, can be bounded with probability that approaches 1 exponentially, and 3) correct classification of malicious and legitimate agents can be attained in finite time almost surely. Further, the expected convergence rate decays exponentially with the quality of the trust observations between agents.

We present an introduction to model-based machine learning for communication systems. We begin by reviewing existing strategies for combining model-based algorithms and machine learning from a high level perspective, and compare them to the conventional deep learning approach which utilizes established deep neural network (DNN) architectures trained in an end-to-end manner. Then, we focus on symbol detection, which is one of the fundamental tasks of communication receivers. We show how the different strategies of conventional deep architectures, deep unfolding, and DNN-aided hybrid algorithms, can be applied to this problem. The last two approaches constitute a middle ground between purely model-based and solely DNN-based receivers. By focusing on this specific task, we highlight the advantages and drawbacks of each strategy, and present guidelines to facilitate the design of future model-based deep learning systems for communications., Comment: arXiv admin note: text overlap with arXiv:2002.07806

This paper characterizes the latency of the simplified successive-cancellation (SSC) decoding scheme for polar codes under hardware resource constraints. In particular, when the number of processing elements $P$ that can perform SSC decoding operations in parallel is limited, as is the case in practice, the latency of SSC decoding is $O\left(N^{1-1/\mu}+\frac{N}{P}\log_2\log_2\frac{N}{P}\right)$, where $N$ is the block length of the code and $\mu$ is the scaling exponent of the channel. Three direct consequences of this bound are presented. First, in a fully-parallel implementation where $P=\frac{N}{2}$, the latency of SSC decoding is $O\left(N^{1-1/\mu}\right)$, which is sublinear in the block length. This recovers a result from our earlier work. Second, in a fully-serial implementation where $P=1$, the latency of SSC decoding scales as $O\left(N\log_2\log_2 N\right)$. The multiplicative constant is also calculated: we show that the latency of SSC decoding when $P=1$ is given by $\left(2+o(1)\right) N\log_2\log_2 N$. Third, in a semi-parallel implementation, the smallest $P$ that gives the same latency as that of the fully-parallel implementation is $P=N^{1/\mu}$. The tightness of our bound on SSC decoding latency and the applicability of the foregoing results is validated through extensive simulations.

This survey paper focuses on modulation aspects of molecular communication, an emerging field focused on building biologically-inspired systems that embed data within chemical signals. The primary challenges in designing these systems are how to encode and modulate information onto chemical signals, and how to design a receiver that can detect and decode the information from the corrupted chemical signal observed at the destination. In this paper, we focus on modulation design for molecular communication via diffusion systems. In these systems, chemical signals are transported using diffusion, possibly assisted by flow, from the transmitter to the receiver. This tutorial presents recent advancements in modulation and demodulation schemes for molecular communication via diffusion. We compare five different modulation types: concentration-based, type-based, timing-based, spatial, and higher-order modulation techniques. The end-to-end system designs for each modulation scheme are presented. In addition, the key metrics used in the literature to evaluate the performance of these techniques are also presented. Finally, we provide a numerical bit error rate comparison of prominent modulation techniques using analytical models. We close the tutorial with a discussion of key open issues and future research directions for design of molecular communication via diffusion systems., Comment: Preprint of the accepted manuscript for publication in IEEE Surveys and Tutorials

Virtual cell optimization clusters cells into neighborhoods and performs optimized resource allocation over each neighborhood. In prior works we proposed resource allocation schemes to mitigate the interference caused by transmissions in the same virtual cell. This work aims at mitigating both the interference caused by the transmissions of users in the same virtual cell and the interference between transmissions in different virtual cells. We propose a resource allocation technique that reduces the number of users that cannot achieve their constant guaranteed bit rate, i.e., the "unsatisfied users", in an uplink virtual cell system with cooperative decoding. The proposed scheme requires only the knowledge of the number of users each base station serves and relies on creating the interference graph between base stations at the edges of virtual cells. Allocation of frequency bands to users is based on the number of users each base station would serve in a non cooperative setup. We evaluate the performance of our scheme for a mmWave system. Our numerical results show that our scheme decreases the number of users in the system whose rate falls below the guaranteed rate, set to $128$kbps, $256$kbps or $512$kbps, when compared with our previously proposed optimization methods.

In decentralized optimization, multiple nodes in a network collaborate to minimize the sum of their local loss functions. The information exchange between nodes required for this task, is often limited by network connectivity. We consider a setting in which communication between nodes is hindered by both (i) a finite rate-constraint on the signal transmitted by any node, and (ii) additive noise corrupting the signal received by any node. We propose a novel algorithm for this scenario: Decentralized Lazy Mirror Descent with Differential Exchanges (DLMD-DiffEx), which guarantees convergence of the local estimates to the optimal solution under the given communication constraints. A salient feature of DLMD-DiffEx is the introduction of additional proxy variables that are maintained by the nodes to account for the disagreement in their estimates due to channel noise and rate-constraints. Convergence to the optimal solution is attained by having nodes iteratively exchange these disagreement terms until consensus is achieved. In order to prevent noise accumulation during this exchange, DLMD-DiffEx relies on two sequences; one controlling the power of the transmitted signal, and the other determining the consensus rate. We provide clear insights on the design of these two sequences which highlights the interplay between consensus rate and noise amplification. We investigate the performance of DLMD-DiffEx both from a theoretical perspective as well as through numerical evaluations., Comment: 15 pages, 6 figures (To be published in the "IEEE Journal on Selected Areas in Communications (JSAC) Special Issue on Distributed Learning over Wireless Edge Networks")

We study a decentralized cooperative multi-agent multi-armed bandit problem with $K$ arms and $N$ agents connected over a network. In our model, each arm's reward distribution is same for all agents, and rewards are drawn independently across agents and over time steps. In each round, agents choose an arm to play and subsequently send a message to their neighbors. The goal is to minimize cumulative regret averaged over the entire network. We propose a decentralized Bayesian multi-armed bandit framework that extends single-agent Bayesian bandit algorithms to the decentralized setting. Specifically, we study an information assimilation algorithm that can be combined with existing Bayesian algorithms, and using this, we propose a decentralized Thompson Sampling algorithm and decentralized Bayes-UCB algorithm. We analyze the decentralized Thompson Sampling algorithm under Bernoulli rewards and establish a problem-dependent upper bound on the cumulative regret. We show that regret incurred scales logarithmically over the time horizon with constants that match those of an optimal centralized agent with access to all observations across the network. Our analysis also characterizes the cumulative regret in terms of the network structure. Through extensive numerical studies, we show that our extensions of Thompson Sampling and Bayes-UCB incur lesser cumulative regret than the state-of-art algorithms inspired by the Upper Confidence Bound algorithm. We implement our proposed decentralized Thompson Sampling under gossip protocol, and over time-varying networks, where each communication link has a fixed probability of failure., Comment: Submitted to IEEE Journal on Selected Areas in Information Theory (JSAIT) issue on Sequential, Active, and Reinforcement Learning

This paper formulates the polar-code construction problem for the successive-cancellation list (SCL) decoder as a maze-traversing game, which can be solved by reinforcement learning techniques. The proposed method provides a novel technique for polar-code construction that no longer depends on sorting and selecting bit-channels by reliability. Instead, this technique decides whether the input bits should be frozen in a purely sequential manner. The equivalence of optimizing the polar-code construction for the SCL decoder under this technique and maximizing the expected reward of traversing a maze is drawn. Simulation results show that the standard polar-code constructions that are designed for the successive-cancellation decoder are no longer optimal for the SCL decoder with respect to the frame error rate. In contrast, the simulations show that, with a reasonable amount of training, the game-based construction method finds code constructions that have lower frame-error rate for various code lengths and decoders compared to standard constructions., Comment: To be published in Proceedings of IEEE Globecom 2020

The design of methods for inference from time sequences has traditionally relied on statistical models that describe the relation between a latent desired sequence and the observed one. A broad family of model-based algorithms have been derived to carry out inference at controllable complexity using recursive computations over the factor graph representing the underlying distribution. An alternative model-agnostic approach utilizes machine learning (ML) methods. Here we propose a framework that combines model-based algorithms and data-driven ML tools for stationary time sequences. In the proposed approach, neural networks are developed to separately learn specific components of a factor graph describing the distribution of the time sequence, rather than the complete inference task. By exploiting stationary properties of this distribution, the resulting approach can be applied to sequences of varying temporal duration. Learned factor graph can be realized using compact neural networks that are trainable using small training sets, or alternatively, be used to improve upon existing deep inference systems. We present an inference algorithm based on learned stationary factor graphs, which learns to implement the sum-product scheme from labeled data, and can be applied to sequences of different lengths. Our experimental results demonstrate the ability of the proposed learned factor graphs to learn to carry out accurate inference from small training sets for sleep stage detection using the Sleep-EDF dataset, as well as for symbol detection in digital communications with unknown channels.

We consider a detection problem where sensors experience noisy measurements and intermittent communication opportunities to a centralized fusion center (or cloud). The objective of the problem is to arrive at the correct estimate of event detection in the environment. The sensors may communicate locally with other sensors (local clusters) where they fuse their noisy sensor data to estimate the detection of an event locally. In addition, each sensor cluster can intermittently communicate to the cloud, where a centralized fusion center fuses estimates from all sensor clusters to make a final determination regarding the occurrence of the event across the deployment area. We refer to this hybrid communication scheme as a cloud-cluster architecture. Minimizing the expected loss function of networks where noisy sensors are intermittently connected to the cloud, as in our hybrid communication scheme, has not been investigated to our knowledge. We leverage recently improved concentration inequalities to arrive at an optimized decision rule for each cluster and we analyze the expected detection performance resulting from our hybrid scheme. Our analysis shows that clustering the sensors provides resilience to noise in the case of low communication probability with the cloud. For larger clusters, a steep improvement in detection performance is possible even for a low communication probability by using our cloud-cluster architecture., Comment: This paper was accepted to the 2020 IEEE Global Communications Conference (IEEE GLOBECOM)

This work introduces the particle-intensity channel (PIC) as a model for molecular communication systems and characterizes the capacity limits as well as properties of the optimal (capacity-achieving) input distributions for such channels. In the PIC, the transmitter encodes information, in symbols of a given duration, based on the probability of particle release, and the receiver detects and decodes the message based on the number of particles detected during the symbol interval. In this channel, the transmitter may be unable to control precisely the probability of particle release, and the receiver may not detect all the particles that arrive. We model this channel using a generalization of the binomial channel and show that the capacity-achieving input distribution for this channel always has mass points at probabilities of particle release of zero and one. To find the capacity-achieving input distributions, we develop an efficient algorithm we call dynamic assignment Blahut-Arimoto (DAB). For diffusive particle transport, we also derive the conditions under which the input with two mass points is capacity-achieving., Comment: arXiv admin note: text overlap with arXiv:1705.08040

Fast SC decoding overcomes the latency caused by the serial nature of the SC decoding by identifying new nodes in the upper levels of the SC decoding tree and implementing their fast parallel decoders. In this work, we first present a novel sequence repetition node corresponding to a particular class of bit sequences. Most existing special node types are special cases of the proposed sequence repetition node. Then, a fast parallel decoder is proposed for this class of node. To further speed up the decoding process of general nodes outside this class, a threshold-based hard-decision-aided scheme is introduced. The threshold value that guarantees a given error-correction performance in the proposed scheme is derived theoretically. Analysis and hardware implementation results on a polar code of length $1024$ with code rates $1/4$, $1/2$, and $3/4$ show that our proposed algorithm reduces the required clock cycles by up to $8\%$, and leads to a $10\%$ improvement in the maximum operating frequency compared to state-of-the-art decoders without tangibly altering the error-correction performance. In addition, using the proposed threshold-based hard-decision-aided scheme, the decoding latency can be further reduced by $57\%$ at $\mathrm{E_b}/\mathrm{N_0} = 5.0$~dB., Comment: 14 pages, 8 figures, 5 tables, submitted to IEEE Transactions on Communications

The design of symbol detectors in digital communication systems has traditionally relied on statistical channel models that describe the relation between the transmitted symbols and the observed signal at the receiver. Here we review a data-driven framework to symbol detection design which combines machine learning (ML) and model-based algorithms. In this hybrid approach, well-known channel-model-based algorithms such as the Viterbi method, BCJR detection, and multiple-input multiple-output (MIMO) soft interference cancellation (SIC) are augmented with ML-based algorithms to remove their channel-model-dependence, allowing the receiver to learn to implement these algorithms solely from data. The resulting data-driven receivers are most suitable for systems where the underlying channel models are poorly understood, highly complex, or do not well-capture the underlying physics. Our approach is unique in that it only replaces the channel-model-based computations with dedicated neural networks that can be trained from a small amount of data, while keeping the general algorithm intact. Our results demonstrate that these techniques can yield near-optimal performance of model-based algorithms without knowing the exact channel input-output statistical relationship and in the presence of channel state information uncertainty., Comment: arXiv admin note: text overlap with arXiv:1905.10750

Many important schemes in signal processing and communications, ranging from the BCJR algorithm to the Kalman filter, are instances of factor graph methods. This family of algorithms is based on recursive message passing-based computations carried out over graphical models, representing a factorization of the underlying statistics. Consequently, in order to implement these algorithms, one must have accurate knowledge of the statistical model of the considered signals. In this work we propose to implement factor graph methods in a data-driven manner. In particular, we propose to use machine learning (ML) tools to learn the factor graph, instead of the overall system task, which in turn is used for inference by message passing over the learned graph. We apply the proposed approach to learn the factor graph representing a finite-memory channel, demonstrating the resulting ability to implement BCJR detection in a data-driven fashion. We demonstrate that the proposed system, referred to as BCJRNet, learns to implement the BCJR algorithm from a small training set, and that the resulting receiver exhibits improved robustness to inaccurate training compared to the conventional channel-model-based receiver operating under the same level of uncertainty. Our results indicate that by utilizing ML tools to learn factor graphs from labeled data, one can implement a broad range of model-based algorithms, which traditionally require full knowledge of the underlying statistics, in a data-driven fashion.

The scaling of coherent and non-coherent channel capacity is studied in a single-input multiple-output (SIMO) block Rayleigh fading channel as both the bandwidth and the number of receiver antennas go to infinity jointly with the transmit power fixed. The transmitter has no channel state information (CSI), while the receiver may have genie-provided CSI (coherent receiver), or the channel statistics only (non-coherent receiver). Our results show that if the available bandwidth is smaller than a threshold bandwidth which is proportional (up to leading order terms) to the square root of the number of antennas, there is no gap between the coherent capacity and the non-coherent capacity in terms of capacity scaling behavior. On the other hand, when the bandwidth is larger than this threshold, there is a capacity scaling gap. Since achievable rates using pilot symbols for channel estimation are subject to the non-coherent capacity bound, this work reveals that pilot-assisted coherent receivers in systems with a large number of receive antennas are unable to exploit excess spectrum above a given threshold for capacity gain., Comment: Published in IEEE Transactions on Wireless Communications

This paper analyzes the impact of non-Gaussian multipath component (MPC) amplitude distributions on the performance of Compressed Sensing (CS) channel estimators for OFDM systems. The number of dominant MPCs that any CS algorithm needs to estimate in order to accurately represent the channel is characterized. This number relates to a Compressibility Index (CI) of the channel that depends on the fourth moment of the MPC amplitude distribution. A connection between the Mean Squared Error (MSE) of any CS estimation algorithm and the MPC amplitude distribution fourth moment is revealed that shows a smaller number of MPCs is needed to well-estimate channels when these components have large fourth moment amplitude gains. The analytical results are validated via simulations for channels with lognormal MPCs such as the NYU mmWave channel model. These simulations show that when the MPC amplitude distribution has a high fourth moment, the well known CS algorithm of Orthogonal Matching Pursuit performs almost identically to the Basis Pursuit De-Noising algorithm with a much lower computational cost., Comment: Published in IEEE Transactions on Wireless Communications. arXiv admin note: text overlap with arXiv:1812.07236

This work proposes a new resource allocation optimization and network management framework for wireless networks using neighborhood-based optimization rather than fully centralized or fully decentralized methods. We propose hierarchical clustering with a minimax linkage criterion for the formation of the virtual cells. Once the virtual cells are formed, we consider two cooperation models: the interference coordination model and the coordinated multi-point decoding model. In the first model base stations in a virtual cell decode their signals independently, but allocate the communication resources cooperatively. In the second model base stations in the same virtual cell allocate the communication resources and decode their signals cooperatively. We address the resource allocation problem for each of these cooperation models. For the interference coordination model this problem is an NP-hard mixed-integer optimization problem whereas for the coordinated multi-point decoding model it is convex. Our numerical results indicate that proper design of the neighborhood-based optimization leads to significant gains in sum rate over fully decentralized optimization, yet may also have a significant sum rate penalty compared to fully centralized optimization. In particular, neighborhood-based optimization has a significant sum rate penalty compared to fully centralized optimization in the coordinated multi-point model, but not the interference coordination model., Comment: arXiv admin note: substantial text overlap with arXiv:1905.02891

This work analyzes the latency of the simplified successive cancellation (SSC) decoding scheme for polar codes proposed by Alamdar-Yazdi and Kschischang. It is shown that, unlike conventional successive cancellation decoding, where latency is linear in the block length, the latency of SSC decoding is sublinear. More specifically, the latency of SSC decoding is $O(N^{1-1/\mu})$, where $N$ is the block length and $\mu$ is the scaling exponent of the channel, which captures the speed of convergence of the rate to capacity. Numerical results demonstrate the tightness of the bound and show that most of the latency reduction arises from the parallel decoding of subcodes of rate $0$ or $1$., Comment: 20 pages, 6 figures, presented in part at ISIT 2020 and accepted in IEEE Transactions on Wireless Communications

This paper proposes to use a deep neural network (DNN)-based symbol detector for mmWave systems such that CSI acquisition can be bypassed. In particular, we consider a sliding bidirectional recurrent neural network (BRNN) architecture that is suitable for the long memory length of typical mmWave channels. The performance of the DNN detector is evaluated in comparison to that of the Viterbi detector. The results show that the performance of the DNN detector is close to that of the optimal Viterbi detector with perfect CSI, and that it outperforms the Viterbi algorithm with CSI estimation error. Further experiments show that the DNN detector is robust to a wide range of noise levels and varying channel conditions, and that a pretrained detector can be reliably applied to different mmWave channel realizations with minimal overhead.

Symbol detection plays an important role in the implementation of digital receivers. In this work, we propose ViterbiNet, which is a data-driven symbol detector that does not require channel state information (CSI). ViterbiNet is obtained by integrating deep neural networks (DNNs) into the Viterbi algorithm. We identify the specific parts of the Viterbi algorithm that are channel-model-based, and design a DNN to implement only those computations, leaving the rest of the algorithm structure intact. We then propose a meta-learning based approach to train ViterbiNet online based on recent decisions, allowing the receiver to track dynamic channel conditions without requiring new training samples for every coherence block. Our numerical evaluations demonstrate that the performance of ViterbiNet, which is ignorant of the CSI, approaches that of the CSI-based Viterbi algorithm, and is capable of tracking time-varying channels without needing instantaneous CSI or additional training data. Moreover, unlike conventional Viterbi detection, ViterbiNet is robust to CSI uncertainty, and it can be reliably implemented in complex channel models with constrained computational burden. More broadly, our results demonstrate the conceptual benefit of designing communication systems to that integrate DNNs into established algorithms., Comment: arXiv admin note: text overlap with arXiv:2002.07806

Nonlinearities can be introduced into communication systems by the physical components such as the power amplifier, or during signal propagation through a nonlinear channel. These nonlinearities can be compensated by a nonlinear equalizer at the receiver side. The nonlinear equalizer also operates on the additive noise, which can lead to noise enhancement. In this work we evaluate this trade-off between distortion reduction and noise-enhancement via nonlinear equalization techniques. We first, evaluate the trade-off between nonlinearity compensation and noise enhancement for the Volterra equalizer, and propose a method to determine the training SNR that optimizes this performance trade-off. We then propose a new approach for nonlinear equalization that alternates between neural networks (NNs) for nonlinearity compensation, and belief propagation (BP) for noise removal. This new approach achieves a 0.6 dB gain compared to the Volterra equalizer with the optimal training SNR, and a 1.7 dB gain compared to a system with no nonlinearity compensation., Comment: 6 pages, 4 figures

This work presents a new network optimization framework for cellular networks using neighborhood-based optimization. Under this optimization framework resources are allocated within virtual cells encompassing several base-stations and the users within their coverage areas. We form the virtual cells using hierarchical clustering with a minimax linkage criterion given a particular number of such cells. Once the virtual cells are formed, we consider an interference coordination model in which base-stations in a virtual cell jointly allocate the channels and power to users within the virtual cell. We propose two new schemes for solving this mixed integer NP-hard resource allocation problem. The first scheme transforms the problem into a continuous variables problem; the second scheme proposes a new channel allocation method and then alternately solves the channel allocation problem using this new method, and the power allocation problem. We evaluate the average system sum rate of these schemes for a variable number of virtual cells. These results quantify the sum-rate along a continuum of fully-centralized versus fully-distributed optimization for different clustering and resource allocation strategies. These results indicate that the penalty of fully-distributed optimization versus fully-centralized (cloud RAN) can be as high as 50%. However, if designed properly, a few base stations within a virtual cell using neighborhood-based optimization have almost the same performance as fully-centralized optimization., Comment: arXiv admin note: text overlap with arXiv:1901.06669, arXiv:1905.02184

This work presents a new resource allocation optimization framework for cellular networks using neighborhood-based optimization. Under this optimization framework resources are allocated within virtual cells encompassing several base-stations and the users within their coverage area. Incorporating the virtual cell concept enables the utilization of more sophisticated cooperative communication schemes such as coordinated multi-point decoding. We form the virtual cells using hierarchical clustering given a particular number of such cells. Once the virtual cells are formed, we consider a cooperative decoding scheme in which the base-stations in each virtual cell jointly decode the signals that they receive. We propose an iterative solution for the resource allocation problem resulting from the cooperative decoding within each virtual cell. Numerical results for the average system sum rate of our network design under hierarchical clustering are presented. These results indicate that virtual cells with neighborhood-based optimization leads to significant gains in sum rate over optimization within each cell, yet may also have a significant sum-rate penalty compared to fully-centralized optimization., Comment: Accepted to the International Symposium on Information Theory (ISIT-2019)

We present two modulation and detection techniques that are designed to allow for efficient equalization for channels that exhibit an arbitrary Doppler spread but no delay spread. These techniques are based on principles similar to techniques designed for time-invariant delay spread channels (e.g., Orthogonal Frequency Division Multiplexing or OFDM) and have the same computational complexity. Through numerical simulations, we show that effective equalization is possible for channels that exhibit a high Doppler spread and even a modest delay spread, whereas equalized OFDM exhibits a strictly worse performance in these environments. Our results indicate that, in rapidly time-varying channels, such as those found in high-mobility or mmWave deployments, new modulation coupled with appropriate channel estimation and equalization techniques may significantly outperform modulation and detection schemes that are designed for static or slowly time varying multipath channels., Comment: Submitted to IEEE Transactions on Wireless Communications

For nano-scale communications, there must be cooperation and simultaneous communication between nano devices. To this end, in this paper we investigate two-way (a.k.a. bi-directional) molecular communications between nano devices. If different types of molecules are used for the communication links, the two-way system eliminates the need to consider self-interference. However, in many systems, it is not feasible to use a different type of molecule for each communication link. Thus, we propose a two-way molecular communication system that uses a single type of molecule. We develop a channel model for this system and use it to analyze the proposed system's bit error rate, throughput, and self-interference. Moreover, we propose analog- and digital- self-interference cancellation techniques. The enhancement of link-level performance using these techniques is confirmed with both numerical and analytical results.

This paper focuses on molecular communication (MC) systems using two types of signaling molecules which may participate in a reversible bimolecular reaction in the channel. The motivation for studying these MC systems is that they can realize the concept of constructive and destructive signal superposition, which leads to favorable properties such as inter-symbol interference (ISI) reduction and avoiding environmental contamination due to continuous release of signaling molecules into the channel. This work first presents a general formulation for binary modulation schemes that employ two types of signaling molecules and proposes several modulation schemes as special cases. Moreover, two types of receivers are considered: a receiver that is able to observe both types of signaling molecules (2TM), and a simpler receiver that can observe only one type of signaling molecules (1TM). For both of these receivers, the maximum likelihood (ML) detector for general binary modulation is derived under the assumption that the detector has perfect knowledge of the ISI-causing sequence. In addition, two suboptimal detectors of different complexity are proposed, namely an ML-based detector that employs an estimate of the ISI-causing sequence and a detector that neglects the effect of ISI. The proposed detectors, except for the detector that neglects ISI for the 2TM receiver, require knowledge of the channel response (CR) of the considered MC system. Moreover, the CR is needed for performance evaluation of all proposed detectors. However, deriving the CR of MC systems with reactive signaling molecules is challenging since the underlying partial differential equations that describe the reaction-diffusion mechanism are coupled and non-linear. Therefore, we develop an algorithm for efficient computation of the CR and validate its accuracy via particle-based simulation., Comment: This paper has been accepted for publication in the IEEE Transactions on Molecular, Biological, and Multi-Scale Communications(Tmbmc). arXiv admin note: text overlap with arXiv:1711.00131

This work proposes a new resource allocation optimization framework for cellular networks using "fog" or neighborhood-based optimization rather than fully centralized or fully decentralized methods. In neighborhood-based optimization resources are allocated within virtual cells encompassing several base-stations and the users within their coverage area. As the number of base-stations within a virtual cell increases, the framework reverts to centralized optimization, and as this number decreases it reverts to decentralized optimization. We address two tasks that must be carried out in the fog optimization framework: forming the virtual cells and allocating the communication resources in each virtual cell effectively. We propose hierarchical clustering for the formation of the virtual cells given a particular number of such cells. Once the virtual cells are formed, we consider several optimization methods to solve the NP-hard joint channel access and power allocation problem within each virtual cell in order to maximize the sum rate of the entire system. We present numerical results for the system sum rate of each scheme under hierarchical clustering. Our results indicate that proper design of the fog optimization results in little degradation relative to centralized optimization even for a relatively large number of virtual cells. However, improper design leads to a significant decrease in sum rate relative to centralized optimization.

This paper proposes and analyzes a mmWave sparse channel estimation technique for OFDM systems that uses the Orthogonal Matching Pursuit (OMP) algorithm. This greedy algorithm retrieves one additional multipath component (MPC) per iteration until a stop condition is met. We obtain an analytical approximation for the OMP estimation error variance that grows with the number of retrieved MPCs (iterations). The OMP channel estimator error variance outperforms a classic maximum-likelihood (ML) non-sparse channel estimator by a factor of approximately $2\hat{L}/M$ where $\hat{L}$ is the number of retrieved MPCs (iterations) and $M$ the number of taps of the Discrete Equivalent Channel. When the MPC amplitude distribution is heavy-tailed, the channel power is concentrated in a subset of dominant MPCs. In this case OMP performs fewer iterations as it retrieves only these dominant large MPCs. Hence for this MPC amplitude distribution the estimation error advantage of OMP over ML is improved. In particular, for channels with MPCs that have lognormally-distributed amplitudes, the OMP estimator recovers approximately 5-15 dominant MPCs in typical mmWave channels, with 15-45 weak MPCs that remain undetected., Comment: Preprint submitted to IEEE ICC 2019

Two new asynchronous modulation techniques for molecular timing (MT) channels are proposed. One based on modulating information on the time between two consecutive releases of indistinguishable information particles, and one based on using distinguishable particles. For comparison, we consider the synchronized modulation scheme where information is encoded in the time of release and decoded from the time of arrival of particles. We show that all three modulation techniques result in a system that can be modeled as an additive noise channel, and we derive the expression for the probability density function of the noise. Next, we focus on binary communication and derive the associated optimal detection rules for each modulation. Since the noise associated with these modulations has an infinite variance, geometric power is used as a measure for the noise power, and we derive an expression for the geometric SNR (G-SNR) for each modulation scheme. Numerical evaluations indicate that for these systems the bit error rate (BER) is constant at a given G-SNR, similar to the relation between BER and SNR in additive Gaussian noise channels. We also demonstrate that the asynchronous modulation based on two distinguishable particles can achieve a BER performance close to the synchronized modulation scheme., Comment: This paper has been accepted for publication at IEEE Transactions on Molecular, Biological, and Multi-Scale Communications. arXiv admin note: text overlap with arXiv:1609.02109

In this paper, a distributed convex optimization algorithm, termed \emph{distributed coordinate dual averaging} (DCDA) algorithm, is proposed. The DCDA algorithm addresses the scenario of a large distributed optimization problem with limited communication among nodes in the network. Currently known distributed subgradient methods, such as the distributed dual averaging or the distributed alternating direction method of multipliers algorithms, assume that nodes can exchange messages of large cardinality. Such network communication capabilities are not valid in many scenarios of practical relevance. In the DCDA algorithm, on the other hand, communication of each coordinate of the optimization variable is restricted over time. For the proposed algorithm, we bound the rate of convergence under different communication protocols and network architectures. We also consider the extensions to the case of imperfect gradient knowledge and the case in which transmitted messages are corrupted by additive noise or are quantized. Relevant numerical simulations are also provided., Comment: Extended version of submission to IEEE ICASSP 2019

We present an algorithm that efficiently performs blind decoding of MIMO signals. That is, given no channel state information (CSI) at either the transmitter or receiver, our algorithm takes a block of samples and returns an estimate of the underlying data symbols. In prior work, the problem of blind decoding was formulated as a non-convex optimization problem. In this work, we present an algorithm that efficiently solves this non-convex problem in practical settings. This algorithm leverages concepts of linear and mixed-integer linear programming. Empirically, we show that our technique has an error performance close to that of zero-forcing with perfect CSI at the receiver. Initial estimates of the runtime of the algorithm presented in this work suggest that the real-time blind decoding of MIMO signals is possible for even modest-sized MIMO systems., Comment: submitted to IEEE Transaction on Wireless Communications