Imitation learning (IL) learns a policy from expert trajectories, serving as a fundamental paradigm in both large language model training and embodied AI. This process is challenging due to the nature of sequential decision-making where errors can accumulate and distributions may shift over horizons. However, it has been found that a kind of IL approach, adversarial imitation learning (AIL), can have exceptional empirical performance. With just one expert trajectory, AIL often matches the expert performance even in a long horizon, on tasks such as robotic locomotion control. There are two fundamental yet unsolved questions: why does AIL perform well with so few trajectories, and why does it maintain good performance over long horizons? Previous theoretical results fail to answer these questions as they are meaningful only in large sample regime (i.e., lots of expert trajectories) and have dependence on the decision horizon. In this paper, we analyze a total-variation-distance-based AIL (called TV-AIL), showing a horizon-free imitation gap ${\mathcal {O}}(\min \lbrace 1, \sqrt{|{\mathcal {S}}|/N} \rbrace )$O(min{1,|S|/N}) on a class of instances abstracted from robotic locomotion control tasks. Here $|{\mathcal {S}}|$|S| is the state space size for a Markov Decision Process (MDP), and $N$N is the number of expert trajectories. We emphasize two important features of our bound. First, this bound is meaningful in both small and large sample regimes. Second, this bound suggests that the imitation gap of TV-AIL does not increase with the decision horizon. Together, our bound can therefore explain the empirical observations and provide insights into how AIL addresses the distribution shift issue. Our analysis leverages the multi-stage policy optimization structure in TV-AIL and presents a new stage-coupled analysis. This tool also helps analyze the worst-case imitation gap of TV-AIL, disclosing its limitations in general MDPs.

Large Language Models (LLMs) typically rely on Supervised Fine-Tuning (SFT) to specialize in downstream tasks, with the Cross Entropy (CE) loss being the de facto choice. However, CE maximizes the likelihood of observed data without accounting for alternative possibilities. As such, CE usually leads to reduced diversity in the model's outputs, which hinders further development that requires sampling to explore better responses. To address this limitation, this paper introduces a new game-theoretic formulation for SFT. In this framework, an auxiliary variable is introduced to regulate the learning process. We prove that the proposed game-theoretic approach connects to the problem of reverse KL minimization with entropy regularization. This regularization prevents over-memorization of training data and promotes output diversity. To implement this framework, we develop GEM, a new training algorithm that is computationally efficient as CE by leveraging some unique properties of LLMs. Empirical studies of pre-trained models from 3B to 70B parameters show that GEM achieves comparable downstream performance to CE while significantly enhancing output diversity. This increased diversity translates to performance gains in test-time compute scaling for chat and code generation tasks. Moreover, we observe that preserving output diversity has the added benefit of mitigating forgetting, as maintaining diverse outputs encourages models to retain pre-trained knowledge throughout the training process.

We propose Adam-mini, an optimizer that achieves on-par or better performance than AdamW with $50$% less memory footprint. Adam-mini reduces memory by cutting down the learning rate resources in Adam (i.e., $1/\sqrt{v}$). By delving into the Hessian structure of neural nets, we find Adam’s $v$ might not function at its full potential as effectively as we expected. We find that $\geq 99.9$% of these learning rates in $v$ could be harmlessly removed if we (1) carefully partition the parameters into blocks following our proposed principle on Hessian structure; (2) assign a single but good learning rate to each parameter block. We then provide one simple way to find good learning rates and propose Adam-mini. Empirically, we verify that Adam-mini performs on par or better than AdamW on various language models sized from 39M to 13B for pre-training, supervised fine-tuning, and RLHF. The reduced memory footprint of Adam-mini also alleviates communication overheads among GPUs, thereby increasing throughput. For instance, Adam-mini achieves $49.6$% higher throughput than AdamW when pre-training Llama 2-7B on $2\times$ A800-80GB GPUs, which saves 33% wall-clock time for pre-training.

The Max-$k$-Cut problem is a fundamental combinatorial optimization challenge that generalizes the classic $\mathcal{NP}$-complete Max-Cut problem. While relaxation techniques are commonly employed to tackle Max-$k$-Cut, they often lack guarantees of equivalence between the solutions of the original problem and its relaxation. To address this issue, we introduce the Relax-Optimize-and-Sample (ROS) framework. In particular, we begin by relaxing the discrete constraints to the continuous probability simplex form. Next, we pre-train and fine-tune a graph neural network model to efficiently optimize the relaxed problem. Subsequently, we propose a sampling-based construction algorithm to map the continuous solution back to a high-quality Max-$k$-Cut solution. By integrating geometric landscape analysis with statistical theory, we establish the consistency of function values between the continuous solution and its mapped counterpart. Extensive experimental results on random regular graphs and the Gset benchmark demonstrate that the proposed ROS framework effectively scales to large instances with up to $20,000$ nodes in just a few seconds, outperforming state-of-the-art algorithms. Furthermore, ROS exhibits strong generalization capabilities across both in-distribution and out-of-distribution instances, underscoring its effectiveness for large-scale optimization tasks.

Thompson Sampling is a principled method for balancing exploration and exploitation, but its real-world adoption faces computational challenges in large-scale or non-conjugate settings. While ensemble-based approaches offer partial remedies, they typically require prohibitively large ensemble sizes. We propose Ensemble++, a scalable exploration framework using a novel shared-factor ensemble architecture with random linear combinations. For linear bandits, we provide theoretical guarantees showing that Ensemble++ achieves regret comparable to exact Thompson Sampling with only $\Theta(d \log T)$ ensemble sizes--significantly outperforming prior methods. Crucially, this efficiency holds across both compact and finite action sets with either time-invariant or time-varying contexts without configuration changes. We extend this theoretical foundation to nonlinear rewards by replacing fixed features with learnable neural representations while preserving the same incremental update principle, effectively bridging theory and practice for real-world tasks. Comprehensive experiments across linear, quadratic, neural, and GPT-based contextual bandits validate our theoretical findings and demonstrate Ensemble++'s superior regret-computation tradeoff versus state-of-the-art methods.

In this paper, we consider the network slicing () problem which aims to map multiple customized virtual network requests (also called services) to a common shared network infrastructure and manage network resources to meet diverse quality of service (QoS) requirements. We propose a mixed-integer nonlinear programming (MINLP) formulation for the considered NS problem that can flexibly route the traffic flow of the services on multiple paths and provide end-to-end delay and reliability guarantees for all services. To overcome the computational difficulty due to the intrinsic nonlinearity in the MINLP formulation, we transform the formulation into an equivalent mixed-integer linear programming () formulation and further show that their continuous relaxations are equivalent. In sharp contrast to the continuous relaxation of the formulation which is a nonconvex nonlinear programming problem, the continuous relaxation of the formulation is a polynomial-time solvable linear programming problem, which significantly facilitates the algorithmic design. Based on the newly proposed formulation, we develop a customized column generation () algorithm for solving the problem. The proposed algorithm is a decomposition-based algorithm and is particularly suitable for solving large-scale problems. Numerical results demonstrate the efficacy of the proposed formulations and the proposed algorithm.

This work advances randomized exploration in reinforcement learning (RL) with function approximation modeled by linear mixture MDPs. We establish the first prior-dependent Bayesian regret bound for RL with function approximation; and refine the Bayesian regret analysis for posterior sampling reinforcement learning (PSRL), presenting an upper bound of $\tilde{\mathcal{O}}(d\sqrt{H^3 T \log T})$, where $d$ represents the dimensionality of the transition kernel, $H$ the planning horizon, and $T$ the total number of interactions. This signifies a methodological enhancement by optimizing the $\mathcal{O}(\sqrt{\log T})$ factor over the previous benchmark (Osband and Van Roy, 2014) specified to linear mixture MDPs. Our approach, leveraging a value-targeted model learning perspective, introduces a decoupling argument and a variance reduction technique, moving beyond traditional analyses reliant on confidence sets and concentration inequalities to formalize Bayesian regret bounds more effectively.

We propose HyperAgent, a reinforcement learning (RL) algorithm based on the hypermodel framework for exploration in RL. HyperAgent allows for the efficient incremental approximation of posteriors associated with an optimal action-value function ($Q^\star$) without the need for conjugacy and follows the greedy policies w.r.t. these approximate posterior samples. We demonstrate that HyperAgent offers robust performance in large-scale deep RL benchmarks. It can solve Deep Sea hard exploration problems with episodes that optimally scale with problem size and exhibits significant efficiency gains in the Atari suite. Implementing HyperAgent requires minimal code addition to well-established deep RL frameworks like DQN. We theoretically prove that, under tabular assumptions, HyperAgent achieves logarithmic per-step computational complexity while attaining sublinear regret, matching the best known randomized tabular RL algorithm.

Reinforcement Learning from Human Feedback (RLHF) is key to aligning Large Language Models (LLMs), typically paired with the Proximal Policy Optimization (PPO) algorithm. While PPO is a powerful method designed for general reinforcement learning tasks, it is overly sophisticated for LLMs, leading to laborious hyper-parameter tuning and significant computation burdens. To make RLHF efficient, we present ReMax, which leverages 3 properties of RLHF: fast simulation, deterministic transitions, and trajectory-level rewards. These properties are not exploited in PPO, making it less suitable for RLHF. Building on the renowned REINFORCE algorithm, ReMax does not require training an additional value model as in PPO and is further enhanced with a new variance reduction technique. ReMax offers several benefits over PPO: it is simpler to implement, eliminates more than 4 hyper-parameters in PPO, reduces GPU memory usage, and shortens training time. ReMax can save about 46% GPU memory than PPO when training a 7B model and enables training on A800-80GB GPUs without the memory-saving offloading technique needed by PPO. Applying ReMax to a Mistral-7B model resulted in a 94.78% win rate on the AlpacaEval leaderboard and a 7.739 score on MT-bench, setting a new SOTA for open-source 7B models. These results show the effectiveness of ReMax while addressing the limitations of PPO in LLMs.

In adversarial machine learning, neural networks suffer from a significant issue known as robust overfitting, where the robust test accuracy decreases over epochs (Rice et al., 2020). Recent research conducted by Xing et al., 2021;Xiao et al., 2022 has focused on studying the uniform stability of adversarial training. Their investigations revealed that SGD-based adversarial training fails to exhibit uniform stability, and the derived stability bounds align with the observed phenomenon of robust overfitting in experiments. This finding motivates us to develop uniformly stable algorithms specifically tailored for adversarial training. To this aim, we introduce Moreau envelope-$\mathcal{A}$ (ME-$\mathcal{A}$), a variant of the Moreau Envelope-type algorithm. We employ a Moreau envelope function to reframe the original problem as a min-min problem, separating the non-strong convexity and non-smoothness of the adversarial loss. Then, this approach alternates between solving the inner and outer minimization problems to achieve uniform stability without incurring additional computational overhead. In practical scenarios, we demonstrate the efficacy of ME-$\mathcal{A}$ in mitigating the issue of robust overfitting. Beyond its application in adversarial training, this represents a fundamental result in uniform stability analysis, as ME-$\mathcal{A}$ is the first algorithm to exhibit uniform stability for weakly-convex, non-smooth problems.

Adam is widely adopted in practical applications due to its fast convergence. However, its theoretical analysis is still far from satisfactory. Existing convergence analyses for Adam rely on the bounded smoothness assumption, referred to as the L-smooth condition. Unfortunately, this assumption does not hold for many deep learning tasks. Moreover, we believe that this assumption obscures the true benefit of Adam, as the algorithm can adapt its update magnitude according to local smoothness. This important feature of Adam becomes irrelevant when assuming globally bounded smoothness. This paper studies the convergence of randomly reshuffled Adam (RR Adam) with diminishing learning rate, which is the major version of Adam adopted in deep learning tasks. We present the first convergence analysis of RR Adam without the bounded smoothness assumption. We demonstrate that RR Adam can maintain its convergence properties when smoothness is linearly bounded by the gradient norm, referred to as the (L0, L1)-smooth condition. We further compare Adam to SGD when both methods use diminishing learning rate. We refine the existing lower bound of SGD and show that SGD can be slower than Adam. To our knowledge, this is the first time that Adam and SGD are rigorously compared in the same setting and the advantage of Adam is revealed.

SGD performs worse than Adam by a significant margin on Transformers, but the reason remains unclear. In this work, we provide an explanation through the lens of Hessian: (i) Transformers are "heterogeneous'': the Hessian spectrum across parameter blocks vary dramatically, a phenomenon we call "block heterogeneity"; (ii) Heterogeneity hampers SGD: SGD performs worse than Adam on problems with block heterogeneity. To validate (i) and (ii), we check various Transformers, CNNs, MLPs, and quadratic problems, and find that SGD can perform on par with Adam on problems without block heterogeneity, but performs worse than Adam when the heterogeneity exists. Our initial theoretical analysis indicates that SGD performs worse because it applies one single learning rate to all blocks, which cannot handle the heterogeneity among blocks. This limitation could be ameliorated if we use coordinate-wise learning rates, as designed in Adam.

We study the regret guarantee for risk-sensitive reinforcement learning (RSRL) via distributional reinforcement learning (DRL) methods. In particular, we consider finite episodic Markov decision processes whose objective is the entropic risk measure (EntRM) of return. By leveraging a key property of the EntRM, the independence property, we establish the risk-sensitive distributional dynamic programming framework. We then propose two novel DRL algorithms that implement optimism through two different schemes, including a model-free one and a model-based one. We prove that they both attain $\tilde{\mathcal{O}}\left(\frac{\exp(|\beta| H)-1}{|\beta|}H\sqrt{S^2AK}\right)$ regret upper bound, where $S$, $A$, $K$, $H$, $T=KH$, and $\beta$ represent the number of states, actions, episodes, time horizon, number of total time-steps, and risk parameter respectively. It matches RSVI2, with novel distributional analysis that focuses on the distributions of returns rather than the risk values associated with these returns. To the best of our knowledge, this is the first regret analysis that bridges DRL and RSRL in terms of sample complexity. To address the computational inefficiencies inherent in the model-free DRL algorithm, we propose an alternative DRL algorithm with distribution representation. This approach effectively represents any bounded distribution using a refined distribution class. It significantly amplifies computational efficiency while maintaining the established regret bounds. We also prove a tighter minimax lower bound of $\Omega\left(\frac{\exp(\beta H/6)-1}{\beta }\sqrt{SAT}\right)$ for the $\beta>0$ case, which recovers the tight lower bound $\Omega(H\sqrt{SAT})$ in the risk-neutral setting.

Intelligent surfaces (ISs) have emerged as a key technology to empower a wide range of appealing applications for wireless networks, due to their low cost, high energy efficiency, flexibility of deployment, and capability of constructing favorable wireless channels/radio environments. Moreover, the recent advent of several new IS architectures further expanded their electromagnetic functionalities from passive reflection to active amplification, simultaneous reflection, and refraction, as well as holographic beamforming. However, the research on ISs is still in rapid progress and there have been recent technological advances in ISs and their emerging applications that are worthy of a timely review. Thus, in this article, we provide a comprehensive survey on the recent development and advances of ISs-aided wireless networks. Specifically, we start with an overview on the anticipated use cases of ISs in future wireless networks such as 6G, followed by a summary of the recent standardization activities related to ISs. Then, the main design issues of the commonly adopted reflection-based IS and their state-of-the-art solutions are presented in detail, including reflection optimization, deployment, signal modulation, wireless sensing, and integrated sensing and communications. Finally, recent progress and new challenges in advanced IS architectures are discussed to inspire future research.

In the fifth-generation new radio (5G NR) frequency division duplex (FDD) massive multiple-input and multiple-output (MIMO) systems, downlink beamforming relies on the acquisition of downlink channel state information (CSI). Codebook based limited feedback schemes have been proposed and widely used in practice to recover the downlink CSI with low communication overhead. In such schemes, the performance of downlink beamforming is determined by the codebook design and the codebook indicator feedback. However, limited by the quantization quality of the codebook, directly utilizing the codeword indicated by the feedback as the beamforming vector cannot achieve high performance. Therefore, other feedback values, such as channel qualification indicator (CQI), should be considered to enhance beamforming. In this paper, we present the relation between CQI and the optimal beamforming vectors, based on which an empirical Bayes based intelligent tuning-free algorithm is devised to learn the optimal beamforming vector and the associated regularization parameter. The proposed algorithm can handle different communication scenarios of MIMO systems, including single stream and multiple streams data transmission scenarios. Numerical results have shown the excellent performance of the proposed algorithm in terms of both beamforming vector acquisition and regularization parameter learning.

Conventional policy for configuring an intelligent reflecting surface (IRS) typically requires channel state information (CSI), thus incurring substantial overhead costs and facing incompatibility with the current network protocols. This paper proposes a blind beamforming strategy in the absence of CSI, aiming to boost the minimum signal-to-noise ratio (SNR) among all the receiver positions, namely the coverage enhancement. Although some existing works already consider the IRS-assisted coverage enhancement without CSI, they assume certain position-channel models through which the channels can be recovered from the geographic locations. In contrast, our approach solely relies on the received signal power data, not assuming any position-channel model. We examine the achievability and converse of the proposed blind beamforming method. If the IRS has N reflective elements and there are U receiver positions, then our method guarantees the minimum SNR of$\Omega (N^{2}/U)$—which is fairly close to the upper bound$O(N+N^{2}\sqrt {\ln (NU)}/\sqrt [{4}]{U})$. Aside from the simulation results, we justify the practical use of blind beamforming in a field test at 2.6 GHz. According to the real-world experiment, the proposed blind beamforming method boosts the minimum SNR across seven random positions in a conference room by 18.22 dB, while the position-based method yields a boost of 12.08 dB.

Localized channel modeling is crucial for offline performance optimization of wireless networks, but existing channel models are not well suited for wireless network optimization. In this paper, we propose a physics-based and data-driven localized statistical channel model for wireless network optimization. The proposed channel modeling solely relies on the reference signal receiving power (RSRP). The key is to build the statistical relationship between the RSRP and the angular power spectrum (APS). Based on it, we formulate the task of channel modeling as a sparse recovery problem where the non-zero entries of the APS indicate the channel paths’ powers and angles of departure. Although such problem typically can be handled by orthogonal matching pursuit (OMP)-type algorithms, our problem is more challenging due to the non-uniform and closely parallel columns of the coefficient matrix. To address these issues, we propose the weighted non-negative OMP (WNOMP) and the second-order-statistics-based WNOMP (SWOMP) algorithms. The WNOMP algorithm can alleviate the effect of non-uniform columns, while the SWOMP algorithm can further identify the closely parallel columns correctly. Finally, comprehensive experiments based on synthetic and real-world RSRP are presented to demonstrate that the proposed methods outperform classic methods in terms of accuracy and mean absolute error (MAE).

Channel acquisition is a major challenge faced by the conventional beamforming methods when dealing with multiple intelligent reflecting surfaces (IRSs), because the number of unknown channels grows exponentially with the number of IRSs. This work proposes to sidestep channel estimation and to configure the IRSs blindly based on the statistical information which is extracted from a set of random samples of the received signal power. The proposed blind beamforming method has provable performance in terms of the signal-to-noise ratio (SNR) boost. For instance, it yields a quartic SNR boost of$\Theta(N^{4})$for a double-IRS system under certain condition, where$N$is the number of reflected elements of each IRS. We remark that the above$\Theta(N^{4})$result is more sophisticated than the existing ones about the double-IRS system in the literature. Furthermore, we numerically demonstrate the advantage of the proposed blind beamforming method through prototype tests with multiple IRSs.

Spiking Neural Networks (SNNs) are promising energy-efficient models for neuromorphic computing. For training the non-differentiable SNN methods, the backpropagation through time (BPTT) with surrogate gradients (SG) method has achieved high performance. However, this method suffers from considerable memory cost and training time during training. In this paper, we propose the Spatial Learning Through Time (SLTT) method that can achieve high performance while greatly improving training efficiency compared with BPTT. First, we show that the backpropagation of SNNs through the temporal domain contributes just a little to the final calculated gradients. Thus, we propose to ignore the unimportant routes in the computational graph during backpropagation. The proposed method reduces the number of scalar multiplications and achieves a small memory occupation that is independent of the total time steps. Furthermore, we propose a variant of SLTT, called SLTT-K, that allows backpropagation only at K time steps, then the required number of scalar multiplications is further reduced and is independent of the total time steps. Experiments on both static and neuromorphic datasets demonstrate superior training efficiency and performance of our SLTT. In particular, our method achieves state-of-the-art accuracy on ImageNet, while the memory cost and training time are reduced by more than 70% and 50%, respectively, compared with BPTT. Our code is available at https://github.com/qymeng94/SLTT.

We present a distribution optimization framework that significantly improves confidence bounds for various risk measures compared to previous methods. Our framework encompasses popular risk measures such as the entropic risk measure, conditional value at risk (CVaR), spectral risk measure, distortion risk measure, equivalent certainty, and rank-dependent expected utility, which are well established in risk-sensitive decision-making literature. To achieve this, we introduce two estimation schemes based on concentration bounds derived from the empirical distribution, specifically using either the Wasserstein distance or the supremum distance. Unlike traditional approaches that add or subtract a confidence radius from the empirical risk measures, our proposed schemes evaluate a specific transformation of the empirical distribution based on the distance. Consequently, our confidence bounds consistently yield tighter results compared to previous methods. We further verify the efficacy of the proposed framework by providing tighter problem-dependent regret bound for the CVaR bandit.

Imitation learning (IL) algorithms excel in acquiring high-quality policies from expert data for sequential decision-making tasks. But, their effectiveness is hampered when faced with limited expert data. To tackle this challenge, a novel framework called (offline) IL with supplementary data has been proposed, which enhances learning by incorporating an additional yet imperfect dataset obtained inexpensively from sub-optimal policies. Nonetheless, learning becomes challenging due to the potential inclusion of out-of-expert-distribution samples. In this work, we propose a mathematical formalization of this framework, uncovering its limitations. Our theoretical analysis reveals that a naive approach—applying the behavioral cloning (BC) algorithm concept to the combined set of expert and supplementary data—may fall short of vanilla BC, which solely relies on expert data. This deficiency arises due to the distribution shift between the two data sources. To address this issue, we propose a new importance-sampling-based technique for selecting data within the expert distribution. We prove that the proposed method eliminates the gap of the naive approach, highlighting its efficacy when handling imperfect data. Empirical studies demonstrate that our method outperforms previous state-of-the-art methods in tasks including robotic locomotion control, Atari video games, and image classification. Overall, our work underscores the potential of improving IL by leveraging diverse data sources through effective data selection.

Deep neural networks (DNNs) are vulnerable to adversarial attacks. It is found empirically that adversarially robust generalization is crucial in establishing defense algorithms against adversarial attacks. Therefore, it is interesting to study the theoretical guarantee of robust generalization. This paper focuses on norm-based complexity, based on a PAC-Bayes approach (Neyshabur et al., 2017). The main challenge lies in extending the key ingredient, which is a weight perturbation bound in standard settings, to the robust settings. Existing attempts heavily rely on additional strong assumptions, leading to loose bounds. In this paper, we address this issue and provide a spectrally-normalized robust generalization bound for DNNs. Compared to existing bounds, our bound offers two significant advantages: Firstly, it does not depend on additional assumptions. Secondly, it is considerably tighter, aligning with the bounds of standard generalization. Therefore, our result provides a different perspective on understanding robust generalization: The mismatch terms between standard and robust generalization bounds shown in previous studies do not contribute to the poor robust generalization. Instead, these disparities solely due to mathematical issues. Finally, we extend the main result to adversarial robustness against general non-$\ell_p$ attacks and other neural network architectures.

Imitation learning (IL) has proven to be an effective method for learning good policies from expert demonstrations. Adversarial imitation learning (AIL), a subset of IL methods, is particularly promising, but its theoretical foundation in the presence of unknown transitions has yet to be fully developed. This paper explores the theoretical underpinnings of AIL in this context, where the stochastic and uncertain nature of environment transitions presents a challenge. We examine the expert sample complexity and interaction complexity required to recover good policies. To this end, we establish a framework connecting reward-free exploration and AIL, and propose an algorithm, MB-TAIL, that achieves the minimax optimal expert sample complexity of $\widetilde{\mathcal{O}} (H^{3/2} |\mathcal{S}|/\varepsilon)$ and interaction complexity of $\widetilde{\mathcal{O}} (H^{3} |\mathcal{S}|^2 |\mathcal{A}|/\varepsilon^2)$. Here, $H$ represents the planning horizon, $|\mathcal{S}|$ is the state space size, $|\mathcal{A}|$ is the action space size, and $\varepsilon$ is the desired imitation gap. MB-TAIL is the first algorithm to achieve this level of expert sample complexity in the unknown transition setting and improves upon the interaction complexity of the best-known algorithm, OAL, by $\mathcal{O} (H)$. Additionally, we demonstrate the generalization ability of MB-TAIL by extending it to the function approximation setting and proving that it can achieve expert sample and interaction complexity independent of $|\mathcal{S}|$.

This paper proposes a blind beamforming strategy for intelligent reflecting surface (IRS), aiming to boost the signal-to-noise ratio (SNR) by coordinating phase shifts across the reflective elements in the absence of channel information. Differing from most existing approaches that first estimate channels and then optimize phase shifts, the proposed blind beamforming method explores the wireless environment by extracting statistical features directly from random samples of the received signal power, without acquiring channel station information (CSI). This new method just requires a polynomial number of random samples to provide a quadratic SNR boost in the number of reflective elements without CSI, whereas the standard random-max sampling algorithm can only achieve a linear boost under the same condition. Moreover, we interpret blind beamforming from a least-squares point of view. Field tests demonstrate the significant advantages of the proposed blind beamforming approach over the benchmark methods in enhancing wireless transmission.

Spiking Neural Network (SNN) is a promising energy-efficient AI model when implemented on neuromorphic hardware. However, it is a challenge to efficiently train SNNs due to their non-differentiability. Most existing methods either suffer from high latency (i.e., long simulation time steps), or cannot achieve as high performance as Artificial Neural Networks (ANNs). In this paper, we propose the Differentiation on Spike Representation (DSR) method, which could achieve high performance that is competitive to ANNs yet with low latency. First, we encode the spike trains into spike representation using (weighted) firing rate coding. Based on the spike representation, we systematically derive that the spiking dynamics with common neural models can be represented as some sub-differentiable mapping. With this viewpoint, our proposed DSR method trains SNNs through gradients of the mapping and avoids the common non-differentiability problem in SNN training. Then we analyze the error when representing the specific mapping with the forward computation of the SNN. To reduce such error, we propose to train the spike threshold in each layer, and to introduce a new hyperparameter for the neural models. With these components, the DSR method can achieve state-of-the-art SNN performance with low latency on both static and neuromorphic datasets, including CIFAR-10, CIFAR-100, ImageNet, and DVS-CIFAR10.

In this paper, we consider the network slicing problem which attempts to map multiple customized virtual network requests (also called services) to a common shared network infrastructure and allocate network resources to meet diverse quality of service (QoS) requirements. We first propose a mixed integer nonlinear program (MINLP) formulation for this problem that optimizes the network resource consumption while jointly considers QoS requirements, flow routing, and resource budget constraints. In particular, the proposed formulation is able to flexibly route the traffic flow of the services on multiple paths and provide end-to-end (E2E) delay and reliability guarantees for all services. Due to the intrinsic nonlinearity, the MINLP formulation is computationally difficult to solve. To over-come this difficulty, we then propose a mixed integer linear program (MILP) formulation and show that the two formulations and their continuous relaxations are equivalent. Different from the continuous relaxation of the MINLP formulation which is a nonconvex nonlinear programming problem, the continuous relaxation of the MILP formulation is a polynomial time solvable linear programming problem, which makes the MILP formulation much more computationally solvable. Numerical results demonstrate the effectiveness and efficiency of the proposed formulations over existing ones.

Localizing the root cause of network faults is crucial to network operation and maintenance (O&M). Significant operational expenses will be saved if the root cause can be identified agilely and accurately. However, this is challenging for human beings due to the complicated wireless environments and network architectures. Resorting to data analysis and machine learning is promising but remains difficult due to various practical issues, such as the lack of well-labeled samples, hybrid fault behaviors, missing data, and so on. In this paper, we introduce a novel real-world dataset for wireless communication network fault diagnosis. The goal is to infer the root cause timely when we observe certain symptoms in a network. Several baseline methods are provided.

In adversarial machine learning, deep neural networks can fit the adversarial examples on the training dataset but have poor generalization ability on the test set. This phenomenon is called robust overfitting, and it can be observed when adversarially training neural nets on common datasets, including SVHN, CIFAR-10, CIFAR-100, and ImageNet. In this paper, we study the robust overfitting issue of adversarial training by using tools from uniform stability. One major challenge is that the outer function (as a maximization of the inner function) is nonsmooth, so the standard technique (e.g., Hardt et al., 2016) cannot be applied. Our approach is to consider $\eta$-approximate smoothness: we show that the outer function satisfies this modified smoothness assumption with $\eta$ being a constant related to the adversarial perturbation $\epsilon$. Based on this, we derive stability-based generalization bounds for stochastic gradient descent (SGD) on the general class of $\eta$-approximate smooth functions, which covers the adversarial loss. Our results suggest that robust test accuracy decreases in $\epsilon$ when $T$ is large, with a speed between $\Omega(\epsilon\sqrt{T})$ and $\mathcal{O}(\epsilon T)$. This phenomenon is also observed in practice. Additionally, we show that a few popular techniques for adversarial training (\emph{e.g.,} early stopping, cyclic learning rate, and stochastic weight averaging) are stability-promoting in theory.

Ever since \citet{reddi2019convergence} pointed out the divergence issue of Adam, many new variants have been designed to obtain convergence. However, vanilla Adam remains exceptionally popular and it works well in practice. Why is there a gap between theory and practice? We point out there is a mismatch between the settings of theory and practice: \citet{reddi2019convergence} pick the problem after picking the hyperparameters of Adam, i.e., $(\beta_1,\beta_2)$; while practical applications often fix the problem first and then tune $(\beta_1,\beta_2)$. Due to this observation, we conjecture that the empirical convergence can be theoretically justified, only if we change the order of picking the problem and hyperparameter. In this work, we confirm this conjecture. We prove that, when the 2nd-order momentum parameter $\beta_2$ is large and 1st-order momentum parameter $\beta_1 < \sqrt{\beta_2}<1$, Adam converges to the neighborhood of critical points. The size of the neighborhood is propositional to the variance of stochastic gradients. Under an extra condition (strong growth condition), Adam converges to critical points. It is worth mentioning that our results cover a wide range of hyperparameters: as $\beta_2$ increases, our convergence result can cover any $\beta_1 \in [0,1)$ including $\beta_1=0.9$, which is the default setting in deep learning libraries. To our knowledge, this is the first result showing that Adam can converge {\it without any modification} on its update rules. Further, our analysis does not require assumptions of bounded gradients or bounded 2nd-order momentum. When $\beta_2$ is small, we further point out a large region of $(\beta_1,\beta_2)$ combinations where Adam can diverge to infinity. Our divergence result considers the same setting (fixing the optimization problem ahead) as our convergence result, indicating that there is a phase transition from divergence to convergence when increasing $\beta_2$. These positive and negative results provide suggestions on how to tune Adam hyperparameters: for instance, when Adam does not work well, we suggest tuning up $\beta_2$ and trying $\beta_1< \sqrt{\beta_2}$.

Network Function Virtualization is a key technology that enables network operators to provide diverse communication services flexibly over a common infrastructure, resulting in a significantly reduced cost. This paper addresses the problem of optimal network function virtualization for providing multicast services in wireless mesh networks with minimal total cost. This problem is modeled in two different ways: Link-based Model (LBM) and Path-based Model (PBM). In both models, we formulate the problem as an integer linear program to find the best hosts for virtual network functions and to steer traffic across them by considering wireless interference and resource budgets. Furthermore, we propose a heuristic solution based on the decomposition of the problem into two smaller sub-problems that can be solved sequentially in two phases. In the first phase, a multicast tree for forwarding traffic is constructed, while in the second phase, the required network functions are instantiated in appropriately chosen nodes. Simulation results are presented to compare the performance and complexity of the exact solutions of link-based and path-based approaches and the proposed heuristic approach. These results demonstrate the effectiveness of the proposed path-based model and the heuristic algorithm.

Decentralized optimization problems frequently appear in the large scale machine learning problems. However, few works work on the difficult nonconvex nonsmooth case. In this paper, we propose a decentralized primal-dual algorithm to solve this type of problem in a decentralized manner and the proposed algorithm can achieve an $\mathcal{O}(1/\epsilon^2)$ iteration complexity to attain an $\epsilon-$solution, which is the well-known lower iteration complexity bound for nonconvex optimization. To our knowledge, it is the first algorithm achieving this rate under a nonconvex, nonsmooth decentralized setting. Furthermore, to reduce communication overhead, we also modifying our algorithm by compressing the vectors exchanged between agents. The iteration complexity of the algorithm with compression is still $\mathcal{O}(1/\epsilon^2)$. Besides, we apply the proposed algorithm to solve nonconvex linear regression problem and train deep learning model, both of which demonstrate the efficiency and efficacy of the proposed algorithm.

This work pursues an optimal strategy of designing passive beamformer for intelligent reflecting surface (IRS) in order to maximize the overall channel strength. In particular, the choice of phase shift for each reflective element is restricted to$K \geq 2$discrete values. Although the resulting discrete beamforming problem is believed to be NP-hard in some prior works, the paper shows that the global optimum of the binary case with$K=2$can be achieved in linear time. For a general$K$-ary beamforming problem with$K > 2$, the state-of-the-art polynomial time algorithm is to greedily project the relaxed solution to the closest point in the constraint set. However, as shown in the paper, the performance of this greedy method cannot be guaranteed. In contrast, we propose a linear time algorithm that is capable of reaching a near-optimal solution with an approximation ratio of$(1+\cos(\pi/K))/2$, i.e., its performance is at least 75% of the global optimum for$K\geq 3$. Furthermore, inspired by the RFocus method in [1], we develop a statistic implementation of the above approximation algorithm in the absence of channel state information (CSI).

In this paper, we consider the network slicing problem which attempts to map multiple customized virtual network requests (also called services) to a common shared network infrastructure and allocate network resources to meet diverse service requirements, and propose an efficient two-stage algorithm for solving this NP-hard problem. In the first stage, the proposed algorithm uses an iterative linear programming (LP) rounding procedure to place the virtual network functions of all services into cloud nodes while taking traffic routing of all services into consideration; in the second stage, the proposed algorithm uses an iterative LP refinement procedure to obtain a solution for traffic routing of all services with their end-to-end delay constraints being satisfied. Compared with the existing algorithms which either have an exponential complexity or return a low-quality solution, our proposed algorithm achieves a better trade-off between solution quality and computational complexity. In particular, the worst-case complexity of our proposed algorithm is polynomial, which makes it suitable for solving large-scale problems. Numerical results demonstrate the effectiveness and efficiency of our proposed algorithm.

There is a fundamental trade-off between the channel representation resolution of codebooks and the overheads of feedback communications in the fifth generation new radio (5G NR) frequency division duplex (FDD) massive multiple-input and multiple-output (MIMO) systems. In particular, two types of codebooks (namely Type I and Type II codebooks) are introduced with different resolution and overhead. Although the Type I codebook based scheme requires lower feedback overhead, its channel state information (CSI) reconstruction and beamforming performance are not as good as those from the Type II codebook based scheme. However, since the Type I codebook based scheme has been widely used in 4G systems for many years, replacing it by the Type II codebook based scheme overnight is too costly to be an option. Therefore, in this paper, using Type I codebook, we leverage advances in cutting plane method to optimize the CSI reconstruction at the base station (BS), in order to close the gap between these two codebook based beamforming schemes. Numerical results based on channel samples from QUAsi Deterministic RadIo channel GenerAtor (QuaDRiGa) are presented to show the excellent performance of the proposed algorithm in terms of beamforming vector acquisition.

Network slicing to support multi-tenancy plays a key role in improving the performance of 5G networks. In this paper, we propose a novel framework for network slicing with the goal of maximizing the expected utilities of tenants in the backhaul and Radio Access Network (RAN), where we reconfigure slices according to the time-varying user traffic and channel states. Upon the arrival of new statistics from users and channels and considering the expected utility from serving users of a slice and the reconfiguration cost, we formulate a sparse optimization problem to reconfigure resources for network slices with the maximum isolation of reserved resources. The formulated optimization is non-convex and difficult to solve. We use the group LASSO regularization and successive upper-bound minimization techniques to solve this problem by iteratively solving a sequence of convex approximations of the original problem. Simulation results verify that our approach outperforms the existing state of the art method.

Modern neural networks are often quite wide, causing large memory and computation costs. It is thus of great interest to train a narrower network. However, training narrow neural nets remains a challenging task. We ask two theoretical questions: Can narrow networks have as strong expressivity as wide ones? If so, does the loss function exhibit a benign optimization landscape? In this work, we provide partially affirmative answers to both questions for 1-hidden-layer networks with fewer than $n$ (sample size) neurons when the activation is smooth. First, we prove that as long as the width $m \geq 2n/d$ (where $d$ is the input dimension), its expressivity is strong, i.e., there exists at least one global minimizer with zero training loss. Second, we identify a nice local region with no local-min or saddle points. Nevertheless, it is not clear whether gradient descent can stay in this nice region. Third, we consider a constrained optimization formulation where the feasible region is the nice local region, and prove that every KKT point is a nearly global minimizer. It is expected that projected gradient methods converge to KKT points under mild technical conditions, but we leave the rigorous convergence analysis to future work. Thorough numerical results show that projected gradient methods on this constrained formulation significantly outperform SGD for training narrow neural nets.

The optimal k-thresholding (OT) and optimal k-thresholding pursuit (OTP) are newly introduced frameworks of thresholding techniques for compressed sensing and signal approximation. Such frameworks motivate the practical and efficient algorithms called relaxed optimal k-thresholding (ROTω) and relaxed optimal k-thresholding pursuit (ROTPω) which are developed through the tightest convex relaxations of OT and OTP, where ω is a prescribed integer number. The preliminary numerical results demonstrated in Zhao (2020) indicate that these approaches can stably reconstruct signals with a wide range of sparsity levels. However, the guaranteed performance of these algorithms with parameter ω≥2 has not yet established in Zhao (2020). The purpose of this paper is to show the guaranteed performance of OT and OTP in terms of the restricted isometry property (RIP) of nearly optimal order for the sensing matrix governing the k-sparse signal recovery, and to establish the first guaranteed performance result for ROTω and ROTPω with ω≥2. In the meantime, we provide a numerical comparison between ROTPω and several existing thresholding methods.

Network function virtualization is a promising technology to simultaneously support multiple services with diverse characteristics and requirements in the 5G and beyond networks. In particular, each service consists of a predetermined sequence of functions, called service function chain (SFC), running on a cloud environment. To make different service slices work properly in harmony, it is crucial to appropriately select the cloud nodes to deploy the functions in the SFC and flexibly route the flow of the services such that these functions are processed in the order defined in the corresponding SFC, the end-to-end (E2E) latency constraints of all services are guaranteed, and all cloud and communication resource budget constraints are respected. In this paper, we first propose a new mixed binary linear program (MBLP) formulation of the above network slicing problem that optimizes the system energy efficiency while jointly considers the E2E latency requirement, resource budget, flow routing, and functional instantiation. Then, we develop another MBLP formulation and show that the two formulations are equivalent in the sense that they share the same optimal solution. However, since the numbers of variables and constraints in the second problem formulation are significantly smaller than those in the first one, solving the second problem formulation is more computationally efficient especially when the dimension of the corresponding network is large. Numerical results demonstrate the advantage of the proposed formulations compared with the existing ones.

This article studies fast adaptive beamforming optimization for the signal-to-interference-plus-noise ratio balancing problem in a multiuser multiple-input single-output downlink system. Existing deep learning based approaches to predict beamforming rely on the assumption that the training and testing channels follow the same distribution which may not hold in practice. As a result, a trained model may lead to performance deterioration when the testing network environment changes. To deal with this task mismatch issue, we propose two offline adaptive algorithms based on deep transfer learning and meta-learning, which are able to achieve fast adaptation with the limited new labelled data when the testing wireless environment changes. Furthermore, we propose an online algorithm to enhance the adaptation capability of the offline meta algorithm in realistic non-stationary environments. Simulation results demonstrate that the proposed adaptive algorithms achieve much better performance than the direct deep learning algorithm without adaptation in new environments. The meta-learning algorithm outperforms the deep transfer learning algorithm and achieves near optimal performance. In addition, compared to the offline meta-learning algorithm, the proposed online meta-learning algorithm shows superior adaption performance in changing environments.

Beamforming is a common technique used to improve speech intelligibility and listening comfort of hearing aids users in a noisy environment. Traditional hearing aids beamforming algorithms require the a priori knowledge of the auditory of the listener, which may not be available in real applications. Recent advances in electroencephalography (EEG) offer a potential non-invasive solution to this problem. The listener's auditory is derived from the EEG signals through auditory decoding algorithms and can be used as an input to the beamforming algorithms. In [1], a joint auditory decoding and adaptive beamforming algorithm framework by correlating the envelope of beamforming output and the EEG signal was proposed to improve the beamformer's robustness against decoding error. Consistent performance improvement was demonstrated on an EEG database recorded on listeners with fixed . In this study, we present the evaluation results of this joint formulation on a new EEG dataset collected on subjects with dynamic switch. We demonstrate not only the joint framework's performance improvement against decoding errors, but also its ability to capture listener's dynamic switch.

Network Function Virtualization (NFV) is an efficient approach to simplify and accelerate the deployment of diverse network services. A critical challenge lies in mapping Virtual Network Functions (VNFs) to high-volume servers, resource allocation, and traffic routing. In this paper, we study the joint problem of VNF placement on servers and traffic engineering for a network spanning multiple subnetworks. Each subnetwork is owned and controlled by a different administrator. We formulate the joint problem of routing and VNF placement cost minimization subject to flow demands where processing flows in local subnetworks is encouraged. To ensure sensitive information of administrators remains private and to cut the implementation cost, a scalable and decentralized approach based on the proximal Alternating Direction Method of Multipliers (ADMM) is proposed. Extensive numerical evaluations show the efficiency of our approach against existing work.

Motivated by large-scale signal processing and machine learning applications, this paper considers the distributed multi-agent optimization problem for a linearly constrained non-convex problem. Each of the agents owns a local cost function and local variable, but are coupled with each other due to the linear constraint. Most of the existing methods are either applicable for convex problems only or are developed under the non-convex setting subject to a specific type of linear constraint. There still lacks a distributed method for solving the linear constrained problem under the general and non-convex setting. In this paper, we propose such a method, called the proximal dual consensus (PDC) method, that combines a proximal technique and the dual consensus method. Theoretical analysis shows that the proposed PDC method can yield a Karush-Kuhn-Tucker solution of the linearly constrained non-convex problem and it has an O(1/ε) iteration complexity, where ε is a solution accuracy. The practical behavior of the proposed method is examined by numerical results.

Nonconvex-concave min-max problem arises in many machine learning applications including minimizing a pointwise maximum of a set of nonconvex functions and robust adversarial training of neural networks. A popular approach to solve this problem is the gradient descent-ascent (GDA) algorithm which unfortunately can exhibit oscillation in case of nonconvexity. In this paper, we introduce a ``smoothing" scheme which can be combined with GDA to stabilize the oscillation and ensure convergence to a stationary solution. We prove that the stabilized GDA algorithm can achieve an $O(1/\epsilon^2)$ iteration complexity for minimizing the pointwise maximum of a finite collection of nonconvex functions. Moreover, the smoothed GDA algorithm achieves an $O(1/\epsilon^4)$ iteration complexity for general nonconvex-concave problems. Extensions of this stabilized GDA algorithm to multi-block cases are presented. To the best of our knowledge, this is the first algorithm to achieve $O(1/\epsilon^2)$ for a class of nonconvex-concave problem. We illustrate the practical efficiency of the stabilized GDA algorithm on robust training.

Variance reduction is a simple and effective technique that accelerates convex (or non-convex) stochastic optimization. Among existing variance reduction methods, SVRG and SAGA adopt unbiased gradient estimators and are the most popular variance reduction methods in recent years. Although various accelerated variants of SVRG (e.g., Katyusha and Acc-Prox-SVRG) have been proposed, the direct acceleration of SAGA still remains unknown. In this paper, we propose a directly accelerated variant of SAGA using a novel Sampled Negative Momentum (SSNM), which achieves the best known oracle complexity for strongly convex problems (with known strong convexity parameter). Consequently, our work fills the void of directly accelerated SAGA.

The worst-case robust adaptive beamforming problem for generalrank signal model is considered. This is a nonconvex problem, and an approximate version of it (by introducing a matrix decomposition on the presumed covariance matrix of the desired signal) has been studied in the literature. Herein the original robust adaptive beamforming problem is tackled. Resorting to the strong duality of a linear conic program, the robust beamforming problem is reformulated into a quadratic matrix inequality (QMI) problem. There is no general method for solving a QMI problem in the literature. Here- in, employing a linear matrix inequality (LMI) relaxation technique, the QMI problem is turned into a convex semidefinite programming problem. Due to the fact that there often is a positive gap between the QMI problem and its LMI relaxation, a deterministic approximate algorithm is proposed to solve the robust adaptive beamforming in the QMI form. Last but not the least, a sufficient optimality condition for the existence of an optimal solution for the QMI problem is derived. To validate our theoretical results, simulation examples are presented, which also demonstrate the improved performance of the new robust beamformer in terms of the output signal-to-interference- plus-noise ratio.

Traditional adaptive binaural beamforming algorithms for hearing devices often assume that the target talker is known or can be derived from the listener's look direction. When this assumption is violated, the traditional beamforming algorithms often produce distorted target speech and less than optimal noise and interference suppression. Recent advances in electroencephalography (EEG) and its applications to auditory attention decoding have offered a potential solution for tracking the listeners auditory attention in a multi-talker environment [2]-[5]. In this paper, we propose a unified model for joint auditory attention decoding and adaptive binaural beamforming, and solve the problem using an iterative optimization approach. The proposed algorithm has two advantages over the existing algorithms. First, the optimization objective aims to balance auditory attention alignment, target speech distortion, noise and interference suppression. Secondly, there is no need to estimate the speech envelope of each talker from the noisy and reverberant mixture which is a very challenging problem in practice. The proposed algorithm was evaluated using a newly recorded EEG database for a multi-talker, noisy and reverberant environment [6]. The evaluation results confirm the benefits of the proposed algorithm.

Gaussian process (GP) for machine learning has been well studied over the past two decades and is now widely used in many sectors. However, the design of low-complexity GP models still remains a challenging research problem. In this paper, we propose a novel scalable GP regression model for processing big datasets, using a large number of parallel computation units. In contrast to the existing methods, we solve the classic maximum likelihood based hyper-parameter optimization problem by a carefully designed distributed alternating direction method of multipliers (ADMM). The proposed method is parallelizable over a large number of computation units. Simulation results confirm the benefits of the proposed scalable GP model over the state-of-the-art distributed methods.

Waveform optimization is a crucial step in the design of a multiple-input multiple-output system. This letter considers the joint optimization of constant modulus waveforms and mismatched (or matched) receive filters to suppress the auto- and cross correlations using the minimax ( $\ell _{\infty }$ -norm) design criterion. For practical waveform length and system size, the waveform design problem becomes quite challenging due to the large problem size (more than $10^5$ unimodular complex variables and $10^7$ nonlinear constraints). In addition to the large size, this problem is nonconvex, nonsmooth, and as such, cannot be handled effectively by the existing waveform design algorithms or off-the-shelve optimization tools. This letter develops an efficient primal–dual type algorithm with low per-iteration complexity to solve this problem. Numerical comparison shows that the waveforms based on the minimax design outperform those obtained from the existing $\ell _2$ -norm design by 4–5 dBs in terms of peak sidelobe levels.

In this paper, we consider the joint base station (BS) association, power control, and beamforming problem for an uplink SISO/SIMO cellular network under the max-min fairness criterion. We first prove a strange discrepancy: a normalized fixed point (NFP) iterative algorithm has geometric convergence to global optima, but it only has pseudo-polynomial time complexity and thus whether the problem is NP-hard or not is an open question. In this paper, we resolve this discrepancy by proving that this problem is indeed polynomial-time solvable. Our proof is based on converting this mixed integer programming (MIP) problem to a series of auxiliary convex problems. Our results fill in a gap in the understanding of the computational complexity of BS association problem. Another implication of our result is that the uplink SIMO problem is easy, but either changing uplink to downlink or changing SIMO to MIMO will make the problem NP-hard. Empirically, the polynomial time algorithm converges much slower than the NFP algorithm, leaving open the question of whether a polynomial time algorithm that converges fast in practice exists for this problem.

We propose a modified spectral mixture (SM) kernel that serves as a universal stationary kernel for temporal Gaussian process regression (GPR). The kernel is named grid spectral mixture (GSM) kernel as we fix the frequency and variance parameters in the original SM kernel to a set of pre-selected grid points. The hyper-parameters are the non-negative weights of all sub-kernel functions and the resulting optimization task falls under the difference-of-convex programming. Due to the nice structure of the optimization problem, the hyper-parameters are solved by an efficient majorization-minimization method instead of the gradient descent methods. It turns out that the solution is sparse, which provides us with a principled guideline to identify the important frequency components of the data. Experimental results based on various classic time series data sets corroborate that the proposed GPR with GSM kernel significantly outperforms the GPR with SM kernel in terms of both the mean-squared-error (MSE) and the stability of the optimization algorithm.

Beamforming is a common technique used to improve speech intelligibility and listening comfort of hearing aids users in a noisy environment. Traditional beamforming algorithms such as linearly constrained minimum variance (LCMV) beamformer cannot effectively suppress multiple interferences when the degree of freedom (DoF) of the array is less than the number of sources in the environment. In [1], a penalized inequality-constrained minimum variance (P-ICMV) beamformer was proposed to address this challenge. In this study, we evaluate the P-ICMV beamformer and compare its performance with other beamformers including the LCMV in a multiple-interference environment. In an objective evaluation, objective metrics related to speech intelligibility and sound quality are used to compare the algorithm performance. In a subjective evaluation, the speech intelligibility of the beamformer processed stimuli are evaluated using normal-hearing listeners. Both the objective and subjective evaluation results show that the P-ICMV beamformer can suppress the interferences more effectively than the existing beamformers when the array DoF is limited.

To support multiple on-demand services over several fixed communication networks, the network operators must allow flexible customization and fast provision of their network resources. One effective approach is network virtualization, whereby each service is mapped to a virtual subnetwork providing dedicated on-demand support. In practice, each service consists of a pre specified sequence of functions, called a service function chain (SFC). Moreover, each function in a SFC can only be provided by some given network nodes. Thus, to support a given service, we must select network function nodes according to the SFC, and determine the routing strategy through the function nodes in the specified order. A crucial problem that needs to be addressed is how to optimally allocate the network resources while satisfying multiple service requirements specified by the service function chains, subject to link and node capacity constraints. In this paper, we formulate the problem as a mixed binary linear program and establish its NP-hardness. Furthermore, we propose an efficient penalty successive upper bound minimization algorithm to solve the problem. We also present simulation results to demonstrate the effectiveness of the proposed algorithm.

The heavy-tailed distributions of corrupted outliers and singular values of all channels in low-level vision have proven effective priors for many applications such as background modeling, photometric stereo and image alignment. And they can be well modeled by a hyper-Laplacian. However, the use of such distributions generally leads to challenging non-convex, non-smooth and non-Lipschitz problems, and makes existing algorithms very slow for large-scale applications. Together with the analytic solutions to $\ell _{p}$ -norm minimization with two specific values of $p$ , i.e., $p=1/2$ and $p=2/3$ , we propose two novel bilinear factor matrix norm minimization models for robust principal component analysis. We first define the double nuclear norm and Frobenius/nuclear hybrid norm penalties, and then prove that they are in essence the Schatten- $1/2$ and $2/3$ quasi-norms, respectively, which lead to much more tractable and scalable Lipschitz optimization problems. Our experimental analysis shows that both our methods yield more accurate solutions than original Schatten quasi-norm minimization, even when the number of observations is very limited. Finally, we apply our penalties to various low-level vision problems, e.g., text removal, moving object detection, image alignment and inpainting, and show that our methods usually outperform the state-of-the-art methods.

Beamforming algorithms in binaural hearing aids are crucial to improve speech understanding in background noise for hearing impaired persons. In this study, we compare and evaluate the performance of two recently proposed minimum variance (MV) beamforming approaches for binaural hearing aids. The binaural linearly constrained MV (BLCMV) beamformer applies linear constraints to maintain the target source and mitigate the interfering sources, taking into account the reverberant nature of sound propagation. The inequality constrained MV (ICMV) beamformer applies inequality constraints to maintain the target source and mitigate the interfering sources, utilizing estimates of the direction of arrivals (DOAs) of the target and interfering sources. The similarities and differences between these two approaches is discussed and the performance of both algorithms is evaluated using simulated data and using real-world recordings, particularly focusing on the robustness to estimation errors of the relative transfer functions (RTFs) and DOAs. The BLCMV achieves a good performance if the RTFs are accurately estimated while the ICMV shows a good robustness to DOA estimation errors.

An important step in multi-sensor data fusion is sensor registration, namely, to estimate sensors' range and azimuth biases from their asynchronous measurements. Assuming the target moves in a straight line with an unknown constant velocity, we propose a two-stage nonlinear least square (LS) approach to this problem. More specifically, in stage I, each sensor first estimates its own range bias individually, and then in stage II, all sensors jointly estimate their azimuth biases. We show that both of the nonconvex LS problems can be solved to global optimality under mild conditions. Simulation results show that the root mean square error (RMSE) of the proposed approach is quite close to the Cramér-Rao lower bound (CRLB) when the level of the measurement noise is small.

Traffic engineering (TE) problem is a central component of the next generation cloud-based wireless networks. In this paper, we study a new resource allocation scheme for effective traffic engineering under practical constraints such as the finite buffer size at each node. To reduce the computational effort required in the existing single-slot TE approaches and to deal with practical hardware limitations on link flows and buffers, we propose a two time-scale, low-complexity TE algorithm which incorporates a novel link scheduling component. The algorithm can be distributedly implemented. Simulation results demonstrate the effectiveness of the proposed algorithm.

To support multiple on-demand services over fixed communication networks, network operators must allow flexible customization and fast provision of their network resources. One effective approach to this end is network virtualization, whereby each service is mapped to a virtual subnetwork providing dedicated on-demand support to network users. In practice, each service consists of a prespecified sequence of functions, called a service function chain (SFC), while each service function in a SFC can only be provided by some given network nodes. Thus, to support a given service, we must select network function nodes according to the SFC and determine the routing strategy through the function nodes in a specified order. A crucial network slicing problem that needs to be addressed is how to optimally localize the service functions in a physical network as specified by the SFCs, subject to link and node capacity constraints. In this paper, we formulate the network slicing problem as a mixed binary linear program and establish its strong NP-hardness. Furthermore, we propose efficient penalty successive upper bound minimization (PSUM) and PSUM-R(ounding) algorithms, and two heuristic algorithms to solve the problem. Simulation results are shown to demonstrate the effectiveness of the proposed algorithms.

Consider a multi-tone multi-user communication system with K interfering users and N available tones. An effective approach to mitigate interference is through power control at transmitters. In this paper, we consider optimal power allocation to maximize a system utility function, and show that for the two tone cases (N=2) with min-rate, harmonic mean, and geometric mean utility functions, the corresponding optimal power allocation problem is NP-hard. This result fills an important gap in the existing literature, which settled the complexity status of different cases involving various utility functions and values of N. Our proof is through a reduction from the partitioning problem for the min-rate utility function, and from the independent set problem for the harmonic mean and geometric mean utility functions.

Vectoring is a well-known technique to mitigate multi- user interference in the downlink Digital Subscriber Line (DSL) transmission. While effective in canceling interference, vectoring does incur major computational overhead, resulting in significant energy consumption when the number of lines is large. To facilitate energy efficient transmission, a mechanism called discontinuous operation (DO) has been recently proposed. In this paper, we consider the key resource allocation problems in DSL: given the transmission opportunities, determine the optimal DO transmission scheme, and optimally adjust an existing DO transmission scheme for energy saving consideration. We formulate these problems and propose efficient real- time algorithms to solve them to global optimality. Simulation results are shown to demonstrate the efficiency and the effectiveness of the proposed algorithms.

Matrix factorization is a popular approach for large-scale matrix completion. The optimization formulation based on matrix factorization, even with huge size, can be solved very efficiently through the standard optimization algorithms in practice. However, due to the non-convexity caused by the factorization model, there is a limited theoretical understanding of whether these algorithms will generate a good solution. In this paper, we establish a theoretical guarantee for the factorization-based formulation to correctly recover the underlying low-rank matrix. In particular, we show that under similar conditions to those in previous works, many standard optimization algorithms converge to the global optima of a factorization-based formulation and recover the true low-rank matrix. We study the local geometry of a properly regularized objective and prove that any stationary point in a certain local region is globally optimal. A major difference of this paper from the existing results is that we do not need resampling (i.e., using independent samples at each iteration) in either the algorithm or its analysis.

Matrix factorization is a popular approach for large-scale matrix completion. In this approach, the unknown low-rank matrix is expressed as the product of two much smaller matrices so that the low-rank property is automatically fulfilled. The resulting optimization problem, even with huge size, can be solved (to stationary points) very efficiently through standard optimization algorithms such as alternating minimization and stochastic gradient descent (SGD). However, due to the non-convexity caused by the factorization model, there is a limited theoretical understanding of whether these algorithms will generate a good solution. In this paper, we establish a theoretical guarantee for the factorization based formulation to correctly recover the underlying low-rank matrix. In particular, we show that under similar conditions to those in previous works, many standard optimization algorithms converge to the global optima of the factorization based formulation, and recover the true low-rank matrix. A major difference of our work from the existing results is that we do not need resampling (i.e., Using independent samples at each iteration) in either the algorithm or its analysis. To the best of our knowledge, our result is the first one that provides exact recovery guarantee for many standard algorithms such as gradient descent, SGD and block coordinate gradient descent.

In this paper, we analyze the behavior of the alternating direction method of multipliers (ADMM), for solving a family of nonconvex problems. Our focus is given to the well-known consensus and sharing problems, both of which have wide applications in signal processing. We show that in the presence of nonconvex objective function, classical ADMM is able to reach the set of stationary solutions for these problems, if the stepsize is chosen large enough. An interesting consequence of our analysis is that the ADMM is convergent for a family of sharing problems, regardless of the number of blocks or the convexity of the objective function. Our analysis is broadly applicable to many ADMM variants involving proximal update rules and various flexible block selection rules.

We consider the distributed network routing problem in a large-scale hierarchical network whereby the nodes are partitioned into subnetworks, each managed by a network controller (NC), and there is a central NC to coordinate the operation of the distributed NCs. We propose a semi-asynchronous routing algorithm for such a network, whereby the computation is distributed across the NCs and is parallel within each NC. A key feature of the algorithm is its ability to handle a certain degree of asynchronism: the distributed NCs can perform their local computation asynchronously at different processing speed. The efficiency of the proposed algorithm is validated through numerical experiments.

In this paper, we propose a beamforming algorithm for binaural hearing aids with enhanced noise suppression capability. The enhancement is based on incorporating a priori spatial information into the conventional multichannel Wiener filtering (MWF) approach for noise suppression. We develop a low complexity algorithm for the resulting quadratically constrained beamforming problem. Through numerical experiments, we demonstrate that the new algorithm can achieve better noise suppression performance than the existing beamforming algorithms under fairly realistic conditions. In addition, we propose two techniques to further reduce the algorithm's computational complexity and the communication overhead between two hearing aids without sacrificing the noise suppression performance.

In this work, we consider enhancing a target speech from a single-channel noisy observation corrupted by non-stationary noises at low signal-to-noise ratios (SNRs). We take a classification-based approach, where the objective is to estimate an Ideal Binary Mask (IBM) that classifies each time-frequency (T-F) unit of the noisy observation into one of the two categories: speech-dominant unit or noise-dominant unit. The estimated mask is used to binary weight the noisy mixture to obtain the enhanced speech. In the proposed system, the sparse non-negative matrix factorization (NMF) is used to extract features from the noisy observation, followed by a Deep Neural Network (DNN) for classification. Compared with several existing classification-based systems, the proposed system uses minimal speech-specific domain knowledge, but is able to achieve better performance in certain low SNR regions. Moreover, the proposed system outperforms the traditional statistical method, especially in terms of improving the intelligibility.

In a heterogeneous network (HetNet) with a large number of low power base stations (BSs), proper user-BS association and power control is crucial to achieving desirable system performance. In this paper, we systematically study the joint BS association and power allocation problem for a downlink cellular network under the max-min fairness criterion. First, we show that this problem is NP-hard. Second, we show that the upper bound of the optimal value can be easily computed, and propose a two-stage algorithm to find a high-quality suboptimal solution. Simulation results show that the proposed algorithm is near-optimal in the high-SNR regime. Third, we show that the problem under some additional mild assumptions can be solved to global optima in polynomial time by a semi-distributed algorithm. This result is based on a transformation of the original problem to an assignment problem with gains log(gij), where {gij} are the channel gains.

Vector space interference alignment (IA) is known to achieve high degrees of freedom (DoFs) with infiniteindependent channel extensions, but its performance is largely unknown for a finite number of possibly dependent channel extensions. In this paper, we consider a K-user Mt x Mr MIMO interference channel (IC) with an arbitrary number of channel extensions T and arbitrary channel diversity order L (i.e., each channel matrix is a generic linear combination of L fixed basis matrices). We study the maximum DoF achievable via vector space IA in the single beam case (i.e., each user sends one data stream). We prove that the total number of users K that can communicate interference free using linear transceivers is upper bounded by NL + N2/4, where N = min{MtT, MrT}. An immediate consequence of this upper bound is that for a Single-Input Single-Output (SISO) IC the DoF in the single beam case is no more than min { √5/4K, L + 1/4T}. When the channel extensions are independent, i.e., L achieves the maximum MrMtT, we show that this maximum DoF lies in [Mr+ Mt- 1, Mr+ Mt] regardless of T. Unlike the well-studied constant MIMO IC case, the main difficulty is how to deal with a hybrid system of equation (zero-forcing condition) and inequalities (full rank condition). Our approach combines algebraic tools that deal with equations with an induction analysis that indirectly considers the inequalities.

In this paper, we consider a nonsmooth convex problem with linear coupling constraints. Problems of this form arise in many modern large-scale signal processing applications including the provision of smart grid networks. In this work, we propose a new class of algorithms called the block coordinate descent method of multipliers (BCDMM) to solve this family of problems. The BCDMM is a primal-dual type of algorithm. It optimizes an (approximate) augmented Lagrangian of the original problem one block variable per iteration, followed by a gradient update for the dual variable. We show that under certain regularity conditions, and when the order for which the block variables are either updated in a deterministic or a random fashion, the BCDMM converges to the set of optimal solutions. The effectiveness of the algorithm is illustrated using large-scale basis pursuit and smart grid problems.

We consider a heterogenous network (HetNet) consisting of a number of base stations (BSs) and network routers connected via a backhaul network. The optimal provision of such networks requires proper resource allocation across the radio access links in conjunction with appropriate traffic engineering within the backhaul network. In this paper we propose an efficient distributed algorithm for the joint resource allocation across the wireless links and the flow control within the backhaul network. The proposed algorithm, which maximizes the minimum rate among all the users and/or flows, is based on a decomposition approach that leverages both the Alternating Direction Method of Multipliers (ADMM) and the WMMSE algorithm, and is shown to be globally convergent to a stationary solution of the joint flow control and resource allocation problem. Moreover, this algorithm is easily parallelizable and can be extended to the multi-antenna scenario.

In this paper we consider the dictionary learning problem for sparse representation. We first show that this problem is NP-hard and then propose an efficient dictionary learning scheme to solve several practical formulations of this problem. Unlike many existing algorithms in the literature, such as K-SVD, our proposed dictionary learning scheme is theoretically guaranteed to converge to the set of stationary points under certain mild assumptions. For the image denoising application, the performance and the efficiency of the proposed dictionary learning scheme are comparable to that of K-SVD algorithm in simulation.

In a heterogeneous network (HetNet) with a large number of low power base stations (BSs), proper user-BS association and power control is crucial to achieving desirable system performance. In this paper, we consider the joint BS association and power allocation problem for an uplink cellular network under the max-min fairness criterion. We first present a binary search method whereby a QoS (Quality of Service) constrained subproblem is solved at each step. Then, we propose a normalized fixed point iterative algorithm to directly solve the original problem and prove its geometric convergence to the global optimal solution, which implies the pseudo-polynomial time solvability of the considered problem. Simulation results show that the proposed normalized fixed point iterative algorithm converges much faster than the binary search method.

In this work, we consider the joint day-ahead power bidding and load scheduling problem for the smart grid system, in the presence of uncertain energy demand and renewable energy generation. We formulate the problem as a convex stochastic program in which the renewable energy generation and energy demand are modeled as random variables. The objective is to minimize the cost in the day-ahead market as well as the cost due to real-time power imbalance, by simultaneously selecting: 1) the amount of power to buy in the day-ahead market and 2) the schedule for the controllable load. We propose a stochastic alternating direction method of multipliers (S AD-MM) to solve the resulting convex stochastic optimization problem and analyze its convergence. The effectiveness of the proposed approach is demonstrated via numerical experiments using real solar power data.

We consider a cloud-based heterogeneous network of base stations (BSs) connected via a backhaul network of routers and wired/wireless links with limited capacity. The optimal provision of such networks requires proper resource allocation across the radio access links in conjunction with appropriate traffic engineering within the backhaul network. In this paper, we propose an efficient algorithm for joint resource allocation across the wireless links and flow control over the entire network. The proposed algorithm, which maximizes the min-rate among all the transmitted commodities, is based on a decomposition approach that leverages both the alternating direction method of multipliers (ADMM) and the weighted-MMSE (WMMSE) algorithm. We show that this algorithm is easily parallelizable and converges globally to a stationary solution of the joint optimization problem. The proposed algorithm can also be extended to networks with multi-antenna nodes and other utility functions.

Loudness restoration approaches to hearing aid fitting prescribe gain and compression so as to restore the loudness perceived by a hearing-impaired listener to that perceived by a listener with normal-hearing. Restoring the loudness perception to normal is complicated by the spread of excitation at high stimulus levels that causes intense stimuli at low frequencies to be “heard” and to contribute to the perceived loudness at high frequencies, producing excess loudness growth and poor sound quality. We apply derivative-free optimization algorithms to find a configuration of hearing aid gain and compression parameters that restores specific loudness perception of a hearing impaired listener to that of a normal hearing listener, while simultaneously minimizing the across-frequency spreading of excitation, and ensuring the feasibility of the resulting hearing aid parameters.

This paper considers transmit covariance optimization for a multi-input multi-output (MIMO) Gaussian wiretap channel. Specifically, we aim to maximize the MIMO secrecy capacity by judiciously designing the transmit covariance under the sum power and per-antenna power constraints. The MIMO secrecy capacity maximization (SCM) problem is nonconvex, and so far there is no tractable solution available. We propose an alternating optimization (AO) approach to handle the SCM problem. In particular, our development consists of two steps: First, we show that the SCM problem can be reexpressed to a form that can be conveniently processed by AO. Second, we develop a custom-designed fast algorithm for each AO iteration. Interestingly, with this fast implementation, the overall AO algorithm can be viewed as performing iterative reweighting and water-filling. Finally, the convergence of the proposed algorithm to a stationary solution of SCM is shown, and numerical results are provided to demonstrate its efficacy.

In a densely deployed Heterogeneous network (HetNet), the number of pico/micro base stations (BS) can be comparable or more than the number of the users. To reduce the operational overhead of the HetNet, selection of serving BSs becomes an important design issue. In this work, we propose to jointly optimize the transceiver and active BSs to trade off the overall spectrum efficiency with the operational overhead. We formulate this problem as a regularized sum rate maximization problem and solve it using sparse optimization techniques. The proposed algorithm is guaranteed to converge to a local optimal solution. The efficiency and the efficacy of the algorithm are demonstrated via realistic numerical simulations.

In this paper, a novel algorithm named Sparsity-based Wiener plus Dictionary Learning (SWDL) is proposed for single channel speech enhancement. SWDL combines both Wiener filter and dictionary learning technique. The Wiener filter is used to ensure the enhanced speech is statistically optimal, while the dictionary learning technique is used to improve the enhanced speech quality and intelligibility by utilizing speech-specific information. Such information is incorporated in the pre-trained speech dictionary that can sparsely represent the clean speech spectra. When applied to the TIM-IT database, SWDL outperforms the Log Mean Square-Error Short-Time Spectra Amplitude estimator (LSTSA) according to four different objective metrics measuring speech quality and intelligibility. Subjective tests also show that SWDL produces better speech quality and intelligibility than LSTSA.

In this paper, we consider the single-channel speech enhancement problem, in which a clean speech signal needs to be estimated from a noisy observation. To capture the characteristics of both the noise and speech signals, we combine the well-known Short-Time-Spectrum-Amplitude (STSA) estimator with a machine learning based technique called Multi-frame Sparse Dictionary Learning (MSDL). The former utilizes statistical information for denoising, while the latter helps better preserve speech, especially its temporal structure. The proposed algorithm, named STSA-MSDL, outperforms standard statistical algorithms such as the Wiener filter, STSA estimator, as well as dictionary based algorithms when applied to the TIMIT database, using four different objective metrics that measure speech intelligibility, speech distortion, background noise reduction, and the overall quality.

Motivated by various applications in machine learning, the problem of minimizing a convex smooth loss function with trace norm regularization has received much attention lately. Currently, a popular method for solving such problem is the proximal gradient method (PGM), which is known to have a sublinear rate of convergence. In this paper, we show that for a large class of loss functions, the convergence rate of the PGM is in fact linear. Our result is established without any strong convexity assumption on the loss function. A key ingredient in our proof is a new Lipschitzian error bound for the aforementioned trace norm-regularized problem, which may be of independent interest.

We consider the interference management problem in a multicell MIMO heterogeneous network. Within each cell there is a large number of distributed micro/pico base stations (BSs) that can be potentially coordinated for joint transmission. To reduce coordination overhead, we consider user-centric BS clustering so that each user is served by only a small number of (potentially overlapping) BSs. Thus, given the channel state information, our objective is to jointly design the BS clustering and the linear beamformers for all BSs in the network. In this paper, we formulate this problem from a {sparse optimization} perspective, and propose an efficient algorithm that is based on iteratively solving a sequence of group LASSO problems. A novel feature of the proposed algorithm is that it performs BS clustering and beamformer design jointly rather than separately as is done in the existing approaches for partial coordinated transmission. Moreover, the cluster size can be controlled by adjusting a single penalty parameter in the nonsmooth regularized utility function. The convergence of the proposed algorithm (to a stationary solution) is guaranteed, and its effectiveness is demonstrated via extensive simulation.

In a wireless system with a large number of distributed nodes, the quality of communication can be greatly improved by pooling the nodes to perform joint transmission/reception. In this paper, we consider the problem of optimally selecting a subset of nodes from potentially a large number of candidates to form a virtual multi-antenna system, while at the same time designing their joint linear transmission strategies. We focus on two specific application scenarios: 1) multiple single antenna transmitters cooperatively transmit to a receiver; 2) a single transmitter transmits to a receiver with the help of a number of cooperative relays. We formulate the joint node selection and beamforming problems as cardinality constrained optimization problems with both discrete variables (used for selecting cooperative nodes) and continuous variables (used for designing beamformers). For each application scenario, we first characterize the computational complexity of the joint optimization problem, and then propose novel semi-definite relaxation (SDR) techniques to obtain approximate solutions. We show that the new SDR algorithms have a guaranteed approximation performance in terms of the gap to global optimality, regardless of channel realizations. The effectiveness of the proposed algorithms is demonstrated via numerical experiments.

This paper considers transmit optimization in multi-input multi-output (MIMO) wiretap channels, wherein we aim at maximizing the secrecy capacity or rate of an MIMO channel overheard by one or multiple eavesdroppers. Such optimization problems are nonconvex, and appear to be difficult especially in the multi-eavesdropper scenario. In this paper, we propose an alternating optimization (AO) approach to tackle these secrecy optimization problems. We first consider the secrecy capacity maximization (SCM) problem in the single eavesdropper scenario. An AO algorithm is derived through a judicious SCM reformulation. The algorithm conducts some kind of reweighting and water-filling in an alternating fashion, and thus is computationally efficient to implement. We also prove that the AO algorithm is guaranteed to converge to a Karush-Kuhn-Tucker (KKT) point of the SCM problem. Then, we turn our attention to the multiple eavesdropper scenario, where the artificial noise (AN)-aided secrecy rate maximization (SRM) problem is considered. Although the AN-aided SRM problem has a more complex problem structure than the previous SCM, we show that AO can be extended to deal with the former, wherein the problem is handled by solving convex problems in an alternating fashion. Again, the resulting AO method is proven to have KKT point convergence guarantee. For fast implementation, a custom-designed AO algorithm based on smoothing and projected gradient is also derived. The secrecy rate performance and computational efficiency of the proposed algorithms are demonstrated by simulations.

We consider a distributed optimization problem whereby a network of n nodes, Sℓ, ℓ ∈ {1, ..., n}, wishes to minimize a common strongly convex function f(x), x=[x1,...,xn]T, under the constraint that nodeSℓcontrols variablexℓonly. The nodes locally update their respective variables and periodically exchange their values with their neighbors over a set of predefined communication channels. Previous studies of this problem have focused mainly on the convergence issue and the analysis of convergence rate. In this study, we consider noisy communication channels and study the impact of communication energy on convergence. In particular, we study the minimum amount of communication energy required for nodes to obtain an ε-minimizer off(x) in the mean square sense. For linear analog communication schemes, we prove that the communication energy to obtain an ε-minimizer off(x) must grow at least at the rate of Ω(1/ε), and this bound is tight whenfis convex quadratic. Furthermore, we show that the same energy requirement can be reduced toO(log21/ε) if a suitable digital communication scheme is used.

We consider the problem of weighted sum rate optimization in a MIMO interfering multiple access channel (IMAC). We propose to jointly optimize the users' linear procoders as well as their base station (BS) associations. This approach enables the users to avoid congested BSs and can improve system performance as well as user fairness. We formulate the problem into a noncooperative game, and develop an algorithm that allows the players to distributedly reach the Nash Equilibrium (NE) of the game. We show that every NE of the game is a stationary solution of the weighted sum rate optimization problem, and propose an algorithm to compute the NE of the game. Simulation results show that the proposed algorithm performs well in the presence of BS congestion.

In an interference network, joint power and admission control aims to support a maximum number of links at their specified signal to interference plus noise ratio (SINR) targets while using a minimum total transmission power. Since this problem is NP-hard, convex approximation heuristics have been considered in the literature. In this work, we first reformulate the problem as a sparse ℓ0-minimization problem and then relax it to a linear program (LP). Then, we derive an easily-checkable necessary condition for all links in the network to be simultaneously supported at their target SINR levels, and use it to iteratively remove strong interfering links (deflation). Numerical simulations show the proposed heuristic compares favorably with the existing approaches in terms of both the number of supported links and speed.

We consider the problem of unknown maneuvering emitter tracking by a wireless sensor network using the interacting multiple models (IMM) with the TDOA and FDOA measurements. Essential to this tracking framework is the Markov transition probability matrix (TPM) governing the jumps between multiple dynamic motion models for the maneuvering target. In practice, the TPM is unknown and has to be estimated. In this paper, we consider the maximum likelihood (ML) estimation of the TPM and propose a recursive algorithm to update the ML TPM estimate using the analytical center cutting plane method (ACCPM). Compared to the general batch ML method, the resulting recursive ML estimation method has a much lower per sample complexity. Simulation results show the efficacy of the proposed method with improved tracking performance.

Consider a MIMO heterogeneous network with multiple transmitters (including macro, pico and femto base stations) and many receivers (mobile users). The users are to be assigned to the base stations which then optimize their linear transmit beamformers accordingly. In this work, we consider the problem of joint base station assignment and linear beamformer design to maximize a system wide utility. We first establish the NP-hardness of the resulting optimization problem for a large family of α-fairness utility functions. Then, we propose an efficient algorithm to approximately solve this problem for the special case of sum rate maximization. The simulation results show that the algorithm improves the sum rate.

Consider a multiple input-multiple output (MIMO) interference channel where each transmitter and receiver are equipped with multiple antennas. An effective approach to practically achieving high system throughput is to deploy linear transceivers (or beamformers) that can optimally exploit the spatial characteristics of the channel. The recent work of Cadambe and Jafar (IEEE Trans. Inf. Theory, vol. 54, no. 8) suggests that optimal beamformers should maximize the total degrees of freedom and achieve interference alignment in the high signal-to-noise ratio (SNR) regime. In this paper we first consider the interference alignment problem without channel extension and prove that the problem of maximizing the total achieved degrees of freedom for a given MIMO interference channel is NP-hard. Furthermore, we show that even checking the achievability of a given tuple of degrees of freedom for all receivers is NP-hard when each receiver is equipped with at least three antennas. Interestingly, the same problem becomes polynomial time solvable when each transmit/receive node is equipped with no more than two antennas. We also propose a distributed algorithm for transmit covariance matrix design that does not require the DoF tuple preassignment, under the assumption that each receiver uses a linear minimum mean square error (MMSE) beamformer. The simulation results show that the proposed algorithm outperforms the existing interference alignment algorithms in terms of system throughput.

This paper presents an efficient implementation of a robust adaptive beamforming algorithm based on convex optimization for applications in the processing-constrained environment of a digital hearing aid. Several modifications of the standard interior point barrier method are introduced for use where the array data covariance matrix is changing rapidly relative to the algorithm's convergence rate. These efficiency improvements significantly simplify the computation without affecting the algorithm's fast convergence, and are useful for real-time adaptive beamforming regardless of the rate of array correlation change. Simulation results show that this implementation is numerically stable and succeeds where many minimum-variance distortionless response (MVDR) solutions fail.

Consider the MIMO interfering broadcast channel whereby multiple base stations in a cellular network simultaneously transmit signals to a group of users in their own cells while causing interference to the users in other cells. The basic problem is to design linear beamformers that can maximize the system throughput. In this paper we propose a linear transceiver design algorithm for weighted sum-rate maximization that is based on iterative minimization of weighted mean squared error (MSE). The proposed algorithm only needs local channel knowledge and converges to a stationary point of the weighted sum-rate maximization problem. Furthermore, we extend the algorithm to a general class of utility functions and establish its convergence. The resulting algorithm can be implemented in a distributed asynchronous manner. The effectiveness of the proposed algorithm is validated by numerical experiments.

We consider the robust beamforming problem under imperfect channel state information (CSI) subject to SINR constraints in a downlink multiuser MISO system. One popular approach to solve this nonconvex optimization problem is via semidefinite relaxation (SDR). In this paper, we prove that the SDR method is tight when the channel uncertainty bound is small or when the base station is equipped with two antennas.

Direction of arrival (DOA) estimation using sensor array super-resolution techniques are known to suffer from array modeling errors including array element displacements, mutual coupling, and array gain/phase perturbations. In this paper, we consider maximum likelihood (ML) DOA estimation for multiple sources in the presence of unknown mutual coupling, and propose convex semidefinite relaxation approaches to this nonlinear and non-convex problem for uniform linear arrays (ULA's) and uniform circular arrays (UCA's), respectively. Simulation results show that the proposed method are effective to practical applications.

In this paper, we consider the problem of geolocating an unknown emitter by a satellite cluster. We formulate the problem as the maximum likelihood location estimation by using TDOA and FDOA measurements and provide efficient convex relaxations for this non-convex optimization problem. We also propose a formulation for robust geolocation in the presence of satellite orbit perturbations. Simulation results confirm the efficiency and superior performance of the convex relaxation approach as compared to the existing least squares based approach when large measurement noise and orbit perturbations are present.

Consider the max-min fairness linear transceiver design for a multi-user MIMO interference channel. Assuming perfect channel knowledge, this problem can be formulated as the maximization of minimum SINR utility, subject to individual power constraints at each transmitter. In this paper, it is shown that when the number of antennas at each transmitter (receiver) is at least two and at each receiver (transmitter) is at least three, the problem of checking whether the given target SINR is feasible is strongly NP-hard. A cyclic coordinate ascent algorithm is also proposed for this design problem. Monotonicity and global convergence to KKT solution of the proposed algorithm are proved.

Iterative clipping and filtering (ICF) is a widely used technique to reduce the peak-to-average power ratio (PAPR) of orthogonal frequency division multiplexing (OFDM) signals. However, the ICF technique, when implemented with a fixed rectangular window in the frequency-domain, requires many iterations to approach specified PAPR threshold in the complementary cumulative distribution function (CCDF). In this paper, we develop an optimized ICF method which determines an optimal frequency response filter for each ICF iteration using convex optimization techniques. The design of optimal filter is to minimize signal distortion such that the OFDM symbol's PAPR is below a specified value. Simulation results show that our proposed method can achieve a sharp drop of CCDF curve and reduce PAPR to an acceptable level after only 1 or 2 iterations, whereas the classical ICF method would require 8 to 16 iterations to achieve a similar PAPR reduction. Moreover, the clipped OFDM symbols obtained by our optimized ICF method have less distortion and lower out-of-band radiation than the existing method.

In a cellular wireless system, users located at cell edges often suffer significant out-of-cell interference. In this paper we consider a coordinated beamforming approach whereby multiple base stations jointly optimize their downlink beamforming vectors in order to simultaneously improve the data rates of a given group of cell edge users. Assuming perfect channel knowledge, we formulate this problem as the maximization of a system utility function (which balances user fairness and average user rates), subject to individual power constraints at each base station. We show that, for the single carrier case and when the number of antennas at each base station is at least two, the optimal coordinated beamforming problem is strongly NP-hard for both the harmonic mean utility function and the proportional fairness utility function. For the min-rate utility function, we show that the problem is solvable in polynomial time.

Hearing aids suffer from the presence of a positive feedback loop between the output transducer and microphone. This feedback reduces both the stable gain achievable in the forward path as well as the sound quality of the output. Existing solutions to this problem perform feedback cancellation using adaptive filtering. The most common methods of adaptive filtering use the Least Mean Square (LMS) or Recursive Least Squares (RLS) algorithms, with the LMS being the most common choice for hearing aid applications. However, these approaches suffer from various drawbacks due to the unique challenges inherent in hearing aids. A new approach employing the Interior Point Least Squares (IPLS) algorithm demonstrates some distinct advantages over these other algorithms for use in the hearing aid schematic. Specifically, it is capable of achieving slightly faster convergence and, more significantly, maintains desired performance trade-offs with fixed parameter values despite changes in input signal power.

In this paper, we consider a cognitive radio system with one primary (licensed) user and multiple secondary (unlicensed) users. Considering the interference temperature constraints, the secondary users compete for the available spectrum so as to satisfy their need for communication. Borrowing the concept of price from market theory, we develop a decentralized Stackelberg game formulation for power allocation. In this scheme, primary user (leader) announces prices for the available tones such that a system utility is maximized. Using the announced prices, secondary users (followers) compete for the available bandwidth to maximize their own utilities. We show that this Stackelberg game is polynomial time solvable under certain channel conditions. The proposed method is decomposable across the tones and is more power efficient than the Iterative Water-Filling Algorithm.

Consider a scenario in which K users and a jammer have a limited power budget and share a common spectrum of N orthogonal tones. The goal of each user is to allocate its power across the N tones in such a way that maximizes the total sum rate that he/she can achieve, while treating the interference of other users and the jammer's signal as additive Gaussian noise. The jammer, on the other hand, wishes to allocate its power in such a way that minimizes the utility of the whole system; that being the total sum of the rates communicated over the network. For this non-cooperative game, we propose a generalized version of the existing iterative water-filling algorithm whereby the users and the jammer update their power allocations in a greedy manner. We study conditions under which the generalized iterative water-filling algorithm converges to a Nash equilibrium of the game. The conditions that we derive in this paper depend only on the system parameters, and hence can be checked a priori.

In this paper we consider a Digital Subscriber Line (DSL) system with N orthogonal narrowband tones. Each user has a limited power budget, and our goal is to determine the power allocation of each user that enables the ‘user capacity’ of the system to be approached. In this paper, we use ‘user capacity’ to denote the maximum number of users that can be supported by the system, provided that each user is guaranteed to have a data rate that lies within a prescribed range. Finding a power allocation that enables this capacity to be approached directly can be quite cumbersome because it involves solving a (non-convex) integer-program. In order to circumvent this difficulty, in this paper we propose an alternate approach that is based on exploiting the fairness and per-tone convexity of the harmonic mean-rate objective. Using these features, we devise a computationally-efficient power allocation technique that enables the user capacity of the DSL system to be approached more closely than power allocation techniques that are more computationally demanding.

Finding the power allocations that maximize the sum-rate of a K-user N-tone Digital Subscriber Line (DSL) system is known to be NP-hard. In this paper we devise a polynomial-time algorithm to approximate the maximum sum rate of the system. The development of this algorithm is guided by the fact that, to approach the sumrate maximum, the users should operate in an FDMA-mode over frequency tones where the crosstalk coefficients exceed a certain threshold, and should share the tones for which the crosstalk coefficients are sufficiently small. Drawing on this insight, the algorithm partitions the N tones into three sections and imposes an appropriate signalling structure on each section. The first section contains those tones for which the crosstalk coefficients are small and uses an iterative water-filling technique to determine the power allocations. The second section contains the tones with intermediate crosstalk coefficients and uses a primal-dual algorithm, and the third section contains the tones with large crosstalk coefficients and uses a dual FDMA algorithm. To decouple the overall optimization of power allocation across the three sections, we use tools from Lagrangian duality and sensitivity analysis to devise an iterative scheme that can optimally allocate each user's power budget to the three sections. Our numerical simulations, show that the sum-rate of the proposed algorithm is very close to that of the ‘optimal’ spectrum balancing algorithm, but requires considerably less computational effort.

We consider a distributed optimization problem where n nodes, Sl, l isin {1,..., n}, wish to minimize a common strongly convex function f(x), x = [x1,..., xn]T, and suppose that node Slonly has control of variable xl. The nodes locally update their respective variables and periodically exchange their values over noisy channels. Previous studies of this problem have mainly focused on the convergence issue and the analysis of convergence rate. In this work, we focus on the communication energy and study its impact on convergence. In particular, we study the minimum amount of communication energy required for nodes to obtain an isin-minimizer of f(x) in the mean square sense. In an earlier work, we considered analog communication schemes and proved that the communication energy must grow at the rate of Omega(isin-1) to obtain an isin-minimizer of a convex quadratic function. In this paper, we consider digital communication schemes and propose a distributed algorithm which only requires communication energy of O ((log isin-1)3) to obtain an isin-minimizer of f(x). Furthermore, the algorithm provided herein converges linearly. Thus, distributed optimization with digital communication schemes is significantly more energy efficient than with analog communication schemes.

In many imaging applications, the continuous phase information of the measured signal is wrapped to a single period of 2pi, resulting in phase ambiguity. In this paper we consider the two-dimensional phase unwrapping problem and propose a maximum a posteriori (MAP) framework for estimating the true phase values based on the wrapped phase data. In particular, assuming a joint Gaussian prior on the original phase image, we show that the MAP formulation leads to a binary quadratic minimization problem. The latter can be efficiently solved by semidefinite relaxation (SDR). We compare the performances of our proposed method with the existing L1/L2-norm minimization approaches. The numerical results demonstrate that the SDR approach significantly outperforms the existing phase unwrapping methods.

Consider a multiuser communication system in a frequency selective environment whereby users share a common spectrum and can interfere with each other. Assuming Gaussian signaling and no interference cancelation, we study optimal spectrum sharing strategies for the maximization of sum-rate under separate power constraints for individual users. Since the sum-rate function is nonconcave in terms of the users' power allocations, there can be multiple local maxima for the sum-rate maximization problem in general. In this paper, we show that, if the normalized crosstalk coefficients are larger than a given threshold (roughly equal to1/2), then the optimal spectrum sharing strategy is frequency division multiple access (FDMA). In case of arbitrary positive crosstalk coefficients, if each user's power budget exceeds a given threshold, then FDMA is again sum-rate optimal, at least in a local sense. In addition, we show that the problem of finding the optimal FDMA spectrum allocation is NP-hard, implying that the general problem of maximizing sum-rate is also NP-hard, even in the case of two users. We also propose several simple distributed spectrum allocation algorithms that can approximately maximize sum-rates. Numerical results indicate that these algorithms are efficient and can achieve substantially larger sum-rates than the existing Iterative Waterfilling solutions, either in an interference-rich environment or when the users' power budgets are sufficiently high.

In this paper, we develop a new class of parameter estimation techniques for the Gaussian Continuous-Density Hidden Markov Model (CDHMM), where the discriminative margin among a set of HMMs is used as the objective function for optimization. In addition to optimizing the mean parameters of the large-margin CDHMM, which was attempted in the past, our new technique is able to optimize the variance parameters as well. We show that the joint mean and variance estimation problem is a difficult optimization problem but can be approximated by a convex relaxation method. We provide some simulation results using synthetic data which possess key properties of speech signals to validate the effectiveness of the new method. In particular, we show that with joint optimization of the mean and variance parameters, the CDHMMs under model mismatch are much more discriminative than with only the mean parameters.

The problem of distributed beamforming is considered for a network which consists of a transmitter, a receiver, and r relay nodes. Assuming that the second order statistics of the channel coefficients are available, we design a distributed beamforming technique via maximization of the receiver signal-to-noise ratio (SNR) subject to individual relay power constraints. We show that using semi-definite relaxation, this SNR maximization can be turned into a convex feasibility semi-definite programming problem, and therefore, it can be efficiently solved using interior point methods. We also obtain a performance bound for the semi-definite relaxation and show that the semi-definite relaxation approach provides a c-approximation to the (nonconvex) SNR maximization problem, where c = O((log r)-1) and r is the number of relays.

We develop a computationally efficient and memory efficient approach to (near) maximum a posteriori probability demodulation for MIMO systems with QPSK signalling, based on semidefinite relaxation. Existing approaches to this problem require either storage of a large list of candidate bit-vectors, or the solution of multiple binary quadratic problems. In contrast, the proposed demodulator does not require the storage of a candidate list, and involves the solution of a single (efficiently solvable) semidefinite program per channel use. Our simulation results show that the resulting computational and memory efficiencies are obtained without incurring a significant degradation in performance.

We present an efficient optimization scheme for gate sizing in the presence of process variations. Our method is a worst case design scheme; however, it reduces the pessimism involved in traditional worst case methods by incorporating the effect of spatial correlations in the optimization procedure. The pessimism reduction is achieved by employing a bounded model for the parameter variations in the form of anuncertaintyellipsoid, which captures the spatial correlation information between the physical parameters. The use of the uncertainty ellipsoid, along with the assumption that the random variables corresponding to the varying parameters follow a multivariate Gaussian distribution, enables us to size the circuits for a specified timing yield. Using a posynomial delay model, the delay constraints are modified to incorporate uncertainty in the transistor widths and effective channel lengths due to the process variations. The resulting optimization problem is relaxed to a geometric program and is efficiently solved using convex optimization tools. The effectiveness of our robust gate sizing scheme is demonstrated by applying the optimization on the ISCAS'85 benchmark circuits and testing the optimized circuits by performing Monte Carlo simulations to model the process variations. Experimental results show that the timing yield of the robustly optimized circuits improves manifold over the traditional deterministically sized circuits. For the same transistor area, the circuits sized by our robust optimization approach have, on average, 12% fewer timing violations as compared to the gate sizing solutions that are obtained via the traditional deterministically based guard-banding method.

Multiuser downlink beamforming under quality of service (QoS) constraints has attracted considerable interest in years, because it is particularly appealing from a network operator's perspective (e.g., UMTS, 802.16e). When there are many co-channel users and/or the service constraints are stringent, the problem becomes infeasible and some form of admission control is necessary. We advocate a cross-layer approach to joint multiuser transmit beamforming and admission control, aiming to maximize the number of users that can be served at their desired QoS. It is shown that the core problem is NP-hard, yet amenable to convex approximation tools. Two computationally efficient convex approximation algorithms are proposed: one is based on semidefinite relaxation of an equivalent problem reformulation; the other takes a penalized second-order cone approach. Their performance is assessed in a range of experiments, using both simulated and measured channel data. In all experiments considered, the proposed algorithms work remarkably well in terms of the attained performance-complexity trade-off, consistently exhibiting close to optimal performance at an affordable computational complexity.

The goal of the sensor network localization problem is to determine positions of all sensor nodes in a network given certain pairwise noisy distance measurements and some anchor node positions. This paper describes a distributed localization algorithm based on second-order cone programming relaxation. We show that the sensor nodes can estimate their positions based on local information. Unlike previous approaches, we also consider the effect of inaccurate anchor positions. In the presence of anchor position errors, the localization is performed in three steps. First, the sensor nodes estimate their positions using information from their neighbors. In the second step, the anchors refine their positions using relative distance information exchanged with their neighbors and finally, the sensors refine their position estimates. We demonstrate the convergence of the algorithm numerically. Simulation study, for both uniform and irregular network topologies, illustrates the robustness of the algorithm to anchor position and distance estimation errors, and the performance gains achievable in terms of localization accuracy, problem size reduction and computational efficiency.

Consider a multiuser communication system in a frequency selective environment whereby users share a common spectrum and can interfere with each other. Assuming Gaussian signaling and treating interference as noise, we study optimal spectrum sharing strategies for the maximization of weighted sum-rate. In this work, we show that, if the normalized crosstalk gains are larger than a given threshold (roughly equal to 1/2), then the optimal spectrum sharing strategy is frequency division multiple access (FDMA). We also propose several simple distributed spectrum allocation algorithms that can approximately maximize weighted sum-rates. Numerical simulation of DSL applications shows that these algorithms are efficient and can achieve substantially larger weighted sumrates than those obtained by the existing iterative waterfilling algorithm.

Existing approaches to the maximum-likelihood (ML) detection problem in digital communications either suffer from exponential complexity (e.g. sphere decoder and its variants) or exhibit significant bit-error-rate (BER) degradation (e.g. LMMSE detector). In this paper we present an efficient implementation of a semi-definite relaxation-based detector (SDR Detector) which can achieve near-optimal BER performance with worst-case polynomial complexity. This implementation (available online) can be 100 times faster than an off-the-shelf SeDuMi-based implementation, outperforms sphere decoder in low signal-to-noise ratio (SNR) or high dimension regimes, and matches the speed of sphere decoder in the high SNR regime. The core of the detector is an optimized dual-scaling interior-point method (implemented in C) for the relaxed semi-definite program. SNR-sensitive improvements are achieved by a dimension reduction strategy and a warm start technique based on a truncated version of the sphere decoding algorithm. Extensive numerical simulations show that the BER performance and the running time of SDR detector compare favorably to that of other near-optimal detection strategies.

Multiuser downlink beamforming under quality of service (QoS) constraints has attracted considerable interest in recent years, because it is particularly appealing from a network operator's perspective (e.g., UMTS, 802.16e). When there are many co-channel users and/or the service constraints are stringent, the problem becomes infeasible and some form of admission control is necessary. We advocate a cross-layer approach to joint multiuser transmit beamforming and admission control, aiming to maximize the number of users that can be served at their desired QoS. The core problem is NP-hard, yet amenable to convex approximation tools. We propose a computationally efficient semidefinite relaxation algorithm which works remarkably well in a range of experiments, using both simulated and measured channel data.

We consider a distributed optimization problem whereby two nodes Si, S2 wish to jointly minimize a common convex quadratic cost function f(x1,x2), subject to separate local constraints on x1and x2, respectively. Suppose that node S1has control of variable x1only and node S2has control of variable x2only. The two nodes locally update their respective variables and periodically exchange their values over a noisy channel. Previous studies of this problem have mainly focused on the convergence issue and the analysis of convergence rate. In this work, we focus on the communication energy and study its impact on convergence. In particular, we consider a class of distributed stochastic gradient type algorithms implemented using certain linear analog messaging schemes. We study the minimum amount of communication energy required for the two nodes to compute an ∈-minimizer of f(x1,x2) in the mean square sense. Our analysis shows that the communication energy must grow at least at the rate of Ω(∈-1). We also derive specific designs which attain this minimum energy bound, and provide simulation results that confirm our theoretical analysis. Extension to the multiple node case is described.

The goal of the sensor network localization problem is to determine positions of all the sensor nodes in a network given certain pairwise noisy distance measurements and inaccurate anchor node positions. A two-step distributed localization approach based on second-order cone programming (SOCP) relaxation is presented. In the first step, the sensor nodes determine their positions based on local information and in the second step, the anchor nodes refine their positions using information from the neighboring nodes. Our numerical study shows that the sensor and anchor positions cannot be estimated in a single step; the sensors must be estimated first for the results to converge. The second step enables anchors which are in the convex hull of their neighbors to refine their positions. Extensive simulation results with inaccurate anchor positions and noisy distance measurements are presented. These illustrate the robustness of the algorithm and the performance gains achievable in terms of problem size reduction, computational efficiency and localization accuracy.

We introduce a novel approach to multi-hop routing in wireless networks. Instead of the usual graph description we characterize the network by the packet delivery ratio matrix whose entries represent the probability that a given node decodes the packet transmitted by any other node. The model lends itself naturally to the formulation of stochastic routing protocols in which packets are randomly routed to neighboring nodes; and routing algorithms search for a matrix of routing probabilities according to properly defined optimality criteria. The goal of the paper is to show that this novel framework offers a useful model to aid in the design of optimal routing algorithms. In particular, it is established that: (i) performance is improved with respect to graph descriptions; and (ii) optimal routes can be obtained as the solution of optimization problems, many of which turn out to be convex and can thus be solved in polynomial time using interior point methods.

We consider decentralized estimation of a noise-corrupted deterministic parameter using a bandwidth-constrained sensor network with a fusion center (FC). Each sensor's noise is additive, zero mean, and independent across sensors. A decentralized estimator is said to be universal if the local sensor quantization rules and the final fusion rule at the FC are independent of sensor noise pdf. Assuming that information rate from each sensor to the FC is constrained to one bit per sample, we derive a Crameacuter-Rao lower bound (CRLB) on the mean-squared error (MSE) performance of a class of rate-constrained universal decentralized estimators. Our results show that if sensor observation noise has finite range in [-U,U], then the minimum MSE performance of any one-bit rate-constrained universal decentralized estimator is at least U2/(4K), where K is the total number sensors. This bound implies that the recently proposed universal decentralized estimators are optimal up to a constant factor of 4

We consider the problem of multiterminal source-channel communication where a number of distributed and possibly correlated sources are transmitted through an orthogonal multiple access channel to a common destination. We provide a characterization of the optimal tradeoff between the transmission cost Gamma and the distortion vectorDas measured against individual sources. Our approach consists of two steps: 1) a multiple-letter characterization of the rate-distortion region of the multiterminal source coding and 2) a source-channel separation theorem ensuring that all achievable pairs of (Gamma,D) can be obtained by combining the rate-distortion region and the orthogonal multiple access channel capacity region. As a corollary, we determine the optimal power and distortion tradeoff in a quadratic Gaussian sensor network under orthogonal multiple access, and show that separate source and channel coding strictly outperforms the uncoded (amplify-forward) transmission, and is in fact optimal in this case. This result is in sharp contrast to the case of nonorthogonal multiple access for which separate source and channel coding is not only suboptimal but also strictly inferior to uncoded transmission.

We consider the distributed estimation of an unknown vector signal in a bandwidth constrained sensor network with a fusion center (FC). Due to power and bandwidth limitations, each sensor compresses its data in order to minimize the amount of information that needs to be communicated to the FC. In this context, we design a linear decentralized estimation scheme (DES), where each sensor linearly encodes its observations before the transmission to the FC, which performs a minimum mean squared error (MMSE) estimation for the unknown vector signal based on the received messages. When the channels between sensors and the FC are orthogonal, it has been shown previously that the complexity of designing the optimal encoding matrices is NP-hard in general. In this paper, we study the optimal design of linear DES for the case of non- orthogonal multiple access channel (MAC) under both bandwidth and power constraints. We show that when the MAC between sensors and the FC is noiseless, the resulting problem has a closed-form solution, while in the noisy MAC case, the problem can be efficiently solved by semi-definite programming (SDP).

We consider the linear coding of a discrete memoryless Gaussian source transmitted through a discrete memoryless fading channel with additive white Gaussian noise (AWGN). The goal is to minimize the mean squared error (MSE) of the source reconstruction at the destination subject to an average power constraint imposed on the channel input symbols. We show that among all single-letter (or symbol-by-symbol) codes, linear coding achieves the smallest MSE, and is thus optimal. But when block length increases, the linear coding still shares the same performance with the single-letter coding, and thus can not approach the Shannon's bound. In spite of the suboptimality, the performance loss of linear coding compared to the optimal coding can be quantitively bounded in terms of the variance of the fading gain and the average transmit power. We also show that for linear coding, when there is no transmitter channel state information (CSI), uniform power allocation is optimal, and in the presence of transmitter CSI, the optimal power allocation can be analytically solved in terms of the channel fading gains and the average power budget.

We propose an efficient algorithm that computes the maximum achievable rate of a decode-and-forward multi-relay cooperative system with orthogonal transmissions under total power constraint. In [1] we have argued that in a system with Q relays the optimum rate can be found by solving Q convex problem despite the fact that the optimization problem is not convex and it belongs to a class of problems with variational inequality constraints. In this paper we show that the number of computations can be reduced from solving Q convex problem to solving only[log(Q)] + 1 convex problems. The proposed algorithm facilitates comparisons with competing alternatives in cooperative systems such as the amplify-and-forward or the compress-and-forward strategies.

We consider the problem of transmit beamforming to multiple co-channel multicast groups. Since the direct minimization of transmit power while guaranteeing a prescribed minimum signal to interference plus noise ratio (SINR) at each receiver is nonconvex and NP-hard, we present convex SDP relaxations of this problem and study when such relaxations are tight. Our results show that when the steering vectors for all receivers are of Vandermonde type (such as in the case of a uniform linear array and line-of-sight propagation), a globally optimum solution to the corresponding transmit beamforming problem can be obtained via an equivalent SDP reformulation. We also present various robust formulations for the problem of single-group multicasting, when the steering vectors are only approximately known. Simulation results are presented to illustrate the effectiveness of our SDP relaxations and reformulations.

We derive linear estimators of stationary random signals based on reduced-dimensionality observations collected at distributed sensors and communicated over wireless fading links to a fusion center, where additive noise is also present. Dimensionality reduction compresses sensor data to meet low-power and bandwidth constraints, while linearity in compression and estimation are well motivated by the limited computing capabilities wireless sensor networks are envisioned to operate with. For uncorrelated sensor data, we develop mean-square error (MSE) optimal estimators in closed-form; while for correlated sensor data, we derive sub-optimal iterative estimators which guarantee convergence at least to a stationary point. Performance analysis and corroborating simulations demonstrate the merits of the novel distributed estimators relative to existing alternatives.

We investigate distributed estimation based on measurements from multiple wireless sensors. For the same target, different sensors have different observations, which are modeled by additive observation noises of different variances. The observations are transmitted using (analog) amplify-and-forward transmissions from the sensors over non-ideal wireless channels to a fusion center, where they are combined to generate an estimate of the observed target. Our goal is to minimize total end-to-end distortion under certain power constraints, assuming the Best Linear Unbiased Estimator (BLUE) is used. We analyze the system outage performance, and show an achievable diversity gain of order K, which is the number of sensors. We also show that by turning off bad sensors, i.e., sensors with bad channels, we achieve adaptive power gain without losing diversity gain, where the adaptive power gain is similar to the array gain achieved in Multiple Input Single Output (MISO) systems when channel conditions are known to the transmitter.

We investigate the rate maximizing power allocation strategy for a system where the source and the decode-and-forward (DF) relays cooperate by utilizing a distributed space-time block coding strategy. Under the assumption that all transmitters have perfect knowledge of the link gains, we analyze two limit cases - the case of no-collaboration among relays and the case of ideal collaboration among relays - and we provide a polynomial-time algorithm that computes the maximum achievable rate for the distributed space-time coding system despite the fact that the optimization problem is not convex and it belongs to a class of problems with variational inequality constraints. Due to the orthogonal structure of the space-time block code designs, the proposed algorithm can also be used, with minor modifications, in the computation of the optimum power allocation for the case of DF relays with orthogonal transmissions

The multiple antenna multicast channel is considered, in which the transmitter, equipped with an antenna array, sends a common message to multiple receivers, each of which are assumed to have only a single antenna. The information theoretic capacity of this channel is studied, along with the rates achievable using lower complexity transmission schemes. The primary focus of the paper is on the scaling of the capacity and achievable rates as the number of antennas and/or users is taken to infinity

Convex optimization methods are widely used in the design and analysis of communication systems and signal processing algorithms. This tutorial surveys some of recent progress in this area. The tutorial contains two parts. The first part gives a survey of basic concepts and main techniques in convex optimization. Special emphasis is placed on a class of conic optimization problems, including second-order cone programming and semidefinite programming. The second half of the survey gives several examples of the application of conic programming to communication problems. We give an interpretation of Lagrangian duality in a multiuser multi-antenna communication problem; we illustrate the role of semidefinite relaxation in multiuser detection problems; we review methods to formulate robust optimization problems via second-order cone programming techniques.

Multicarrier multiple access with channel knowledge and prescribed power at the transmitters is shown to maximize the sum-rate for circulant intersymbol-interference (ISI) channels. A low-complexity iterative algorithm is derived for optimal subcarrier allocation to multiple users, while power is loaded per user by specializing an existing iterative algorithm to circulant ISI channels. It is analytically shown that each subcarrier should be allocated to the user having relatively better subcarrier gain and that different users may share certain subcarriers.

Given a combination of unprotected and dedicated edge-disjoint path (1+1) protected connection requests and a finite set of fiber types, we consider the problem of allocating fibers on the links of a WDM network at minimum cost, such that all connection requests can be simultaneously realized. Each fiber type, is characterized by its capacity and its cost per unit length, where costs reflect an economy of scale. It is known that a solution induced by "simply" routing each unprotected (respectively 1+1 protected) connection along the shortest path (respectively shortest pair of edge-disjoint paths) minimizes the total wavelength mileage, but may not minimize the total fiber cost. In this paper, we quantify the increase in fiber cost due to shortest path routing. In particular, we prove that the total cost of a shortest path based solution is guaranteed to lie within a certain factor of the minimum possible cost. This leads also to the fact that shortest path routing is asymptotically cost-optimal for a large total number of connection requests. Furthermore, for sparse topologies, e.g., the ring, the ShuffleNet and the mesh(-torus), we show that shortest path routing is asymptotically cost-optimal in large-scale networks supporting all-to-all communication. En route, we prove that by shortest path routing we obtain a provably optimal solution to the linear programming (LP-) relaxation of the problem. We have thus presented a provably good upper bound and a lower bound on the total fiber cost, that can be computed in polynomial-time. These bounds can be used as benchmarks against which heuristic approaches are compared.

A new and conceptually simple semidefinite relaxation approach is proposed for MIMO detection in communication systems employing high-order QAM constellations. The new approach affords improved detection performance compared to existing solutions of comparable worst-case complexity order, which is nearly cubic in the dimension of the transmitted symbol vector and independent of the constellation order for uniform QAM, or affine in the constellation order for nonuniform QAM

We present an efficient optimization scheme for gate sizing in the presence of process variations. Using a posynomial delay model, the delay constraints are modified to incorporate uncertainty in the transistor widths and effective channel lengths due to the process variations. An uncertainty ellipsoid method is used to model the random parameter variations. Spatial correlations of intra-die width and channel length variations are incorporated in the optimization procedure. The resulting optimization problem is relaxed to be a Geometric Program and is efficiently solved using convex optimization tools. The effectiveness of our robust gate sizing scheme is demonstrated by applying the optimization on the ISCAS ’85 benchmark circuits and testing the optimized circuits by performing Monte Carlo simulations to model the process variations. By varying the size of the uncertainty ellipsoids, a trade-off between area and robustness is explored. Experimental results show that the timing yield of the robustly optimized circuits improves manifold over the traditional deterministically sized circuits. As compared to the worst-case design, the robust gate sizing solution having the same area, has fewer timing violations.

Sensor networks in which energy is a limited resource so that energy consumption must be minimized for the intended application are considered. In this context, an energy-efficient method for the joint estimation of an unknown analog source under a given distortion constraint is proposed. The approach is purely analog, in which each sensor simply amplifies and forwards the noise-corrupted analog observation to the fusion center for joint estimation. The total transmission power across all the sensor nodes is minimized while satisfying a distortion requirement on the joint estimate. The energy efficiency of this analog approach is compared with previously proposed digital approaches with and without coding. It is shown in our simulation that the analog approach is more energy-efficient than the digital system without coding, and in some cases outperforms the digital system with optimal coding.

In this paper, we present new approaches to blind channel estimation and equalization based on second order statistics (SOS). We first consider the case of minimum phase channels where the equalizer is designed based on the criterion of autocorrelation matching. We cast the problem as a convex optimization program that can be efficiently solved using interior point methods. Then we consider the equalization of single-input multiple-output (SIMO) channels. Due to oversampling, the equivalent channel matrix possesses a particular structure which enables us to estimate the channel based only on the information contained in the covariance matrix at zero delay. Simulation examples are provided to demonstrate the performance advantage of the proposed algorithms compared to existing techniques.

Despite its optimal bit-error-rate (BER) performance, maximum-likelihood (ML) detection is known to be NP-hard and suffers from high computational complexity. The currently popular suboptimal detectors either achieve a polynomial time complexity at the expense of BER performance degradation (e.g., MMSE detector), or offer a near ML performance with a complexity that is exponential in the worst case. The paper considers a highly efficient (polynomial worst case complexity) quasi-ML detection method based on semi-definite (SDP) relaxation. It is shown that, for a standard vector Rayleigh fading channel, this SDP-based quasi-ML detector achieves, in the high signal-to-noise ratio (SNR) region, a BER which is identical to that of the exact ML detector. In the low SNR region, we use the random matrix theory to show that the SDP-based detector serves as a constant factor approximation to the ML detector for large systems.

We consider the problem of a single parameter estimation by a sensor network with a fusion center (FC). Sensor observations are corrupted by additive noise which can have arbitrary spatial correlation. Due to a bandwidth constraint each sensor is only able to transmit a finite number of bits. The fusion center combines messages from the sensors to produce a parameter estimator, which is required to have mean square error (MSE) within a constant factor of that of the best linear unbiased estimator (BLUE). We show that total sensor transmitted power can be minimized while meeting target MSE requirement if quantization levels are determined jointly by the fusion center using the knowledge of the noise covariance matrix. By numerical examples we show that energy saving up to 70% can be achieved when compared to a uniform quantization strategy when each sensor generates the same number of bits.

We consider universal decentralized estimation of a noise-corrupted signal by a bandwidth constrained sensor network with a fusion center (FC). We show that in a homogeneous sensing environment and under a bandwidth constraint of 1-bit per sample per node, there exist universal decentralized estimation schemes (DES) with a mean squared error (MSE) decreasing at the rate 1/K, where K is the total number of sensors. We extend such 1-bit decentralized estimators to the case of a inhomogeneous sensing environment, and propose quantization and transmission power control strategies for local sensors in order to minimize the total consumed sensor energy while ensuring a given MSE performance. We also design a DES for the joint estimation of a vector source based on its noisy and linearly distorted observations, and show that to achieve a MSE within a factor of 2 away from the best linear unbiased estimator (BLUE), the local message length has a nice form of being the channel capacity of "a virtual AWGN channel" from "nature" to each local sensor.

Consider a bandwidth constrained sensor network in which a set of distributed sensors and a fusion center (FC) collaborate to estimate an unknown vector. Due to power and cost limitations, each sensor must compress its data in order to minimize the amount of information that need to be communicated to the FC. In this paper, we consider the design of a linear decentralized estimation scheme (DES) whereby each sensor transmits over a noisy channel to the FC a fixed number of real-valued messages which are linear functions of its observations, while the FC linearly combines the received messages to estimate the unknown parameter vector. Assuming each sensor collects data according to a local linear model, we propose to design optimal linear message functions and linear fusion function according to the minimum mean squared error (MMSE) criterion. We show that the resulting design problem is nonconvex and NP-hard in general, and identify two special cases for which the optimal linear DES design problem can be efficiently solved either in closed form or by semi-definite programming (SDP).

Consider a decentralized estimation problem whereby an ad hoc network of K distributed sensors wish to cooperate to estimate an unknown parameter over a bounded interval [-U,U]. Each sensor collects one noise-corrupted sample, performs a local data quantization according to a fixed (but possibly probabilistic) rule, and transmits the resulting discrete message to its neighbors. These discrete messages are then percolated in the network and used by each sensor to form its own minimum mean squared error (MMSE) estimate of the unknown parameter according to a fixed fusion rule. In this paper, we propose a simple probabilistic local quantization rule: each sensor quantizes its observation to the first most significant bit (MSB) with probability 1/2, the second MSB with probability 1/4, and so on. Assuming the noises are uncorrelated and identically distributed across sensors and are bounded to [-U,U], we show that this local quantization strategy together with a fusion rule can guarantee a MSE of 4U/sup 2//K, and that the average length of local messages is bounded (no more than 2.5 bits). Compared with the worst case Cramer-Rao lower bound of U/sup 2//K (even for the centralized counterpart), this is within a factor of at most 4 to the minimum achievable MSE. Moreover, the proposed scheme is isotropic and universal in the sense that the local quantization rules and the final fusion rules are independent of sensor index, noise distribution, network size, or topology. In fact, the proposed scheme allows sensors in the network to operate identically and autonomously even when the network undergoes changes in size or topology.

Radar emitter classification is a special application of data clustering for classifying unknown radar emitters from received radar pulse samples. The main challenges of this task are the high dimensionality of radar pulse samples, small sample group size, and closely located radar pulse clusters. In this paper, two new online clustering algorithms are developed for radar emitter classification: One is model-based using the Minimum Description Length (MDL) criterion and the other is based on competitive learning. Computational complexity is analyzed for each algorithm and then compared. Simulation results show the superior performance of the model-based algorithm over competitive learning in terms of better classification accuracy, flexibility, and stability.

A novel split soft-decision equalizer (SSE) with near-optimum performance is proposed for wireless multipath channels with large delay spread. The concept of SSE is significantly different from the traditional notions of the Viterbi algorithm and decision-feedback equalizer. Instead of dealing with received sequence as a combined sequence, it splits the received sequence into its constituent paths. Using an iterative soft-decision algorithm, reliability of the soft decisions on each decomposed element is improved iteratively. The major advantage of SSE is the independence of computation complexity on channel time dispersion. Joint design of SSE with a soft-decision decoder is also considered in this paper. Performance analysis and simulation results show that performance of the proposed algorithm comes very close to that of the logarithmic maximum a posteriori decoder.

Consider a situation where a set of distributed sensors and a fusion center wish to cooperate to estimate an unknown parameter over a bounded interval [-U,U]. Each sensor collects one noise-corrupted sample, performs a local estimation, and transmits a message to the fusion center, while the latter combines the received messages to produce a final estimate. This correspondence investigates optimal local estimation and final fusion schemes under the constraint that the communication from each sensor to the fusion center must be a one-bit message. Such a binary message constraint is well motivated by the bandwidth limitation of the communication links, fusion center, and by the limited power budget of local sensors. In the absence of bandwidth constraint and assuming the noises are bounded to the interval [-U,U], additive, independent, but otherwise unknown, the classical estimation theory suggests that a total of O(U2/epsi2) sensors are necessary and sufficient in order for the sensors and the fusion center to jointly estimate the unknown parameter within epsi root mean squared error (MSE). It is shown in this correspondence that the same remains true even with the binary message constraint. Furthermore, the optimal decentralized estimation scheme suggests allocating 1/2 of the sensors to estimate the first bit of the unknown parameter, 1/4 of the sensors to estimate the second bit, and so on

We consider decentralized estimation of a noise-corrupted deterministic parameter by a bandwidth-constrained sensor network with a fusion center. The sensor noises are assumed to be additive, zero mean, spatially uncorrelated, but otherwise unknown and possibly different across sensors due to varying sensor quality and inhomogeneous sensing environment. The classical best linear unbiased estimator (BLUE) linearly combines the real-valued sensor observations to minimize the mean square error (MSE). Unfortunately, such a scheme cannot be implemented in a practical bandwidth-constrained sensor network due to its requirement to transmit real-valued messages. In this paper, we construct a decentralized estimation scheme (DES) where each sensor compresses its observation to a small number of bits with length proportional to the logarithm of its local signal-to-noise ratio (SNR). The resulting compressed bits from different sensors are then collected and combined by the fusion center to estimate the unknown parameter. The proposed DES is universal in the sense that each sensor compression scheme requires only the knowledge of local SNR, rather than the noise probability distribution functions (pdf), while the final fusion step is also independent of the local noise pdfs. We show that the MSE of the proposed DES is within a constant factor of 25/8 of that achieved by the classical centralized BLUE estimator.

Blind signal detection in multiuser code division multiple access (CDMA) system is particularly attractive when only the desired user signature is known to a given receiver. A problem common to several existing blind multiuser CDMA detectors is that the detection performance is very sensitive to the signature waveform mismatch (SWM) which may be caused by channel distortion. In this paper, we consider the design of a blind multiuser CDMA detector that is robust to the SWM. We present a convex formulation for this problem by using the second-order cone (SOC) programming. The resulting SOC problem can be solved efficiently using the recently developed interior point methods. Computer simulations indicate that the performance of our new robust blind multiuser detector is superior to those of many existing methods.

We address the problem of allocating fibers (each supporting only a limited set of wavelengths) on the links of a WDM network at minimum cost, such that a set of edge-disjoint path protected connection requests can be realized. The cost of a link is assumed to be linear in the number of fibers rather than being linear in the number of wavelengths used on this link, reflecting modular capacity considerations. Therefore, a solution induced by routing each connection "simply" along the minimum-cost (shortest) pair of edge-disjoint lightpaths may not minimize the total fiber cost. In this paper we quantify the increase in the total fiber cost due to this simple routing strategy. In particular, we prove that the cost of a solution induced by routing along shortest path pairs is guaranteed to lie within a certain factor of the minimum possible cost. This leads also to the fact that the cost of this solution is asymptotically minimum in heavily loaded networks, and in networks that are large, sparse and supporting all-to-all communications. En route, we prove that the optimal objective function value of the linear programming (LP) relaxation actually corresponds to routing along shortest path pairs. We have thus presented a provably good upper bound and a lower bound on the total fiber cost, that can be computed in polynomial-time, and can be used as benchmarks against which exact and heuristic approaches are compared.

Consider the problem of decentralized detection with a distributed sensor network where the communication channels between sensors and the fusion center are bandlimited. Previous approaches to this problem typically rely on quantization of either the sensor observations, or the local likelihood ratios, with quantization levels optimally designed using the knowledge of noise distribution. We assume that each sensor is restricted to send a 1-bit message to the fusion center, and that sensor noise is additive, zero mean, spatially independent, but otherwise unknown and with possibly different distributions across sensors. We construct a universal decentralized detector using a recently proposed isotropic decentralized estimation scheme (Z.-Q. Luo, 2003) which requires only the knowledge of either the noise range or its second order moment. We show that the error probability of this detector decays exponentially at a rate which is optimal for bounded range noise, and, for noise with unbounded range, is lower bounded in terms of the signal-to-noise ratio.

We propose a new blind multiuser receiver which is robust against the effects of erroneously presumed desired user signature and short data length. Our approach is based on the explicit modeling of possible mismatches in the mean-square error cost function and worst-case performance optimization. We show that this approach leads to a multiuser receiver which uses the data covariance matrix with an adaptive diagonal loading. Simulation results show performance improvements achieved by our approach relative to existing techniques.

We consider the decentralized estimation of a noise-corrupted deterministic parameter by a bandwidth constrained sensor network with a fusion center. We construct a decentralized estimation scheme (DES) where each sensor compresses its observation to a small number of bits with length proportional to the logarithm of its local Signal to Noise Ratio (SNR). The resulting compressed bits from different sensors are then collected and combined by the fusion center to estimate the unknown parameter. The proposed DES is universal in the sense that the local sensor compression schemes and final fusion function are independent of noise pdf. We show that its mean squared error is within a constant factor to that achieved by the classical centralized best linear unbiased estimator (BLUE).

We consider the problem of optimal power scheduling for the decentralized estimation of a noise-corrupted signal in an inhomogeneous sensor network. Sensor observations are first quantized into discrete messages, then transmitted to the fusion center where a final estimate is generated. Based on the sensor noise levels and channel gains from sensors to the fusion center, optimal quantization levels and transmit power levels at the local sensors can be chosen to minimize the total transmitting power, while ensuring a given mean squared error (MSE) performance. The proposed optimal power scheduling scheme suggests that the sensors with bad channels or poor observation qualities should decrease their quantization resolutions or simply become inactive in order to conserve power. For the remaining active sensors, their optimal quantization and transmit power levels are determined jointly by individual channel gains, local observation noise variance, and the targeted MSE performance. Numerical examples show that up to 60% energy savings is possible when compared with the uniform quantization strategy.

This paper addresses the problem of routing and wavelength assignment (RWA) in multifiber WDM networks with limited resources. Given a traffic matrix, the number of fibers per link, and the number of wavelengths a fiber can support, we seek to maximize the carried traffic of connections. We formulate the problem as an integer linear program (ILP), and show that the lightpaths selected by this formulation can indeed be established by properly configuring the optical switches. An upper bound on the carried traffic can be computed by solving the linear programming (LP)-relaxation of the ILP formulation. It is shown that this bound can be also computed exactly, and in polynomial-time, by solving a significantly simplified LP which considers only one wavelength. The bound can, thus, easily scale to an arbitrarily large number of wavelengths. Furthermore, we demonstrate that any instance of the RWA problem is also an instance of the more general maximum coverage problem. This allows us to take a greedy algorithm for maximum coverage and obtain an algorithm which provides solutions for the RWA problem that are guaranteed to be within a factor of (1-(1/e)) of the optimal solution. Each iteration of the greedy algorithm selects a set of lightpaths that realizes, using one wavelength, the maximum number of connection requests not previously realized. Computational results confirm the high efficiency of our proposed algorithm.

Adaptive beamforming methods degrade in the presence of both signal steering vector errors and interference nonstationarity. We develop a new approach to adaptive beamforming that is jointly robust against these two phenomena. Our beamformer is based on the optimization of the worst case performance. A computationally efficient convex optimization-based algorithm is proposed to compute the beamformer weights. Computer simulations demonstrate that our beamformer has an improved robustness as compared to other popular robust beamforming algorithms.

We consider the problem of determining an optimal transmission scheme for broadcasting a common message over vector channels, given (perfect) channel knowledge at both the receive and transmit ends. We provide an efficient method for jointly designing a linear transmitter and and a set of linear receivers so as to minimize a weighted mean square error (WMSE) of the data estimates. The computational efficiency follows from the convex formulations that we develop. These formulations enable utilization of highly efficient interior point methods. For diagonal channel matrices, which appear in multicarrier systems that employ cyclic prefixing, we show that the optimal transmitter is obtained by subcarrier allocation and power loading. The set of minimum MSE transceivers for a vector broadcast system is parametrized by a unitary matrix degree of freedom. For the case of diagonal systems, we show how this unitary matrix can be chosen so that the symbol error rate is minimized (over the given set). This optimal unitary matrix ensures that, for each receiver, the subcarrier signal-to-noise ratios (SNRs) are all the same. Simulations indicate that our designs can provide significantly improved performance over standard designs.

In this paper we consider the design of lowpass infinite impulse response (IIR) magnitude filters which are robust against the implementation error. It is shown that the design problem can be cast as a quasiconvex problem with a set of linear matrix inequality (LMI) constraints and the autocorrelation sequences of the filter coefficients as the design variables. The relation between the norm error of autocorrelation sequences and that of filter coefficients is derived, and the issue of filter stability is addressed by deriving a lower bound on the distance from the pole to the unit circle. Simulation results show that our designed filter is immune from the errors caused by finite precision implementation. The method can also be used in similar highpass and bandpass IIR filter design.

We propose a new approach to solving the problem of blind separation of BPSK signals. Using the constant modulus property of the signal, we formulate this problem as a constrained minimization problem that can be solved efficiently using an extended Newton's method on the Stiefel manifold. Compared with the existing separation methods, the proposed method is quite robust to additive noise, achieves a low bit error rate, and enjoys a quadratic convergence rate and a low computational complexity. Simulation results show that our method is a competitive blind separation method.

Since exact maximum likelihood (ML) detection is computationally intractable in general, approximate ML approaches are needed to reduce the computation time while maintaining low bit error rate (BER). In this work, we develop an efficient approximate ML decoder for constant modulus signals based on a simple nonlinear programming relaxation. Unlike the existing sphere decoder whose expected complexity is cubic in problem size and whose performance deteriorates with increasing problem size and noise level, our proposed new decoder enjoys a worst case quadratic complexity and scales gracefully with problem dimension and noise level. Our initial testing and analysis suggests that this new decoder is capable of delivering ML like BER performance for PSK signals while requiring substantially lower computational complexity. In this sense, our new decoder is similar to the sphere decoder which is an effective method for QAM signals.

The performance of adaptive beamforming methods may degrade in the presence of even slight mismatches between the actual and presumed array responses to the desired signal. This paper addresses the problem of robust adaptive beamforming in the presence of unknown arbitrary (yet norm-bounded) mismatches of such type as well as interference-plus-noise covariance matrix mismatch. Our approach is developed for the case of an arbitrary dimension of the signal subspace and, therefore, it can be applied to both rank-one and higher-rank signal models. The proposed beamformer is based on the optimization of the worst-case signal-to-interference-plus-noise ratio (SINR). The obtained closed-form solution combines two different types of diagonal loading (DL) applied to the signal and data covariance matrices. An efficient on-line implementation of our beamformer is developed. Simulations validate substantial performance improvements relative to other popular adaptive beamforming techniques.

Adaptive beamforming methods are known to degrade in the presence of both signal steering vector errors and interference nonstationarity. In this paper, we develop a new approach to adaptive beamforming which is jointly robust against these two phenomena. Our approach is based on the optimization of the worst-case beamforming performance. A computationally efficient convex optimization based algorithm is proposed to compute the beamformer weights. Computer simulations compare the performance of our algorithm with other robust adaptive beamforming techniques.

In a WDM based network, lightpaths are established between router pairs to form a virtual topology residing on top of the underlying physical topology. The ability to reconfigure its virtual topology upon dynamically changing traffic patterns has been identified as one of the most important features of WDM based networks. Compared to previously reported reconfiguration studies, we provide contributions along two different directions. First, we address the problem of finding the new virtual topology that maximizes the number of successfully established lightpaths, while guaranteeing absolutely no service disruptions. Second, based on a Lagrangean decomposition approach, we demonstrate that optimal and near-optimal virtual topologies can be obtained by considering only one wavelength in the formulation, leading to a reconfiguration algorithm that scales to an arbitrarily large number of wavelengths. Computational results confirm the high efficiency of the proposed algorithm.

The paper addresses soft maximum-likelihood (ML) detection for multiple-antenna wireless channels. We propose a soft quasi-ML detector, which maximizes the log-likelihood function by developing a semi-definite relaxation (SDR). Given perfect channel state information at the receiver, the quasi-ML detector achieves the performance of the optimal ML detector in both coded and uncoded multiple-input multiple-output (MIMO) channels with quadrature phase-shift keying modulation and frequency-flat Rayleigh fading. The complexity of the quasi-ML SDR detector is much less than that of the optimal ML detector, and, thus, the quasi-ML detector offers more favorable performance/complexity trade-off. Compared to the existing sphere decoder the quasi-ML detector enjoys low polynomial worst-case complexity, as well as guaranteed near capacity performance.

A new approach to adaptive beamforming with sidelobe control is developed. The proposed beamformer represents a modification of the popular minimum variance distortionless response (MVDR) beamformer. It minimizes the array output power while maintaining the distortionless response in the direction of the desired signal and a sidelobe level that is strictly guaranteed to be lower than some given (prescribed) threshold value. The resulting modified MVDR problem is shown to be convex, and its second-order cone (SOC) formulation is obtained that facilitates a computationally efficient way to implement our beamformer using the interior point method.

This paper addresses the problem of routing and wavelength assignment (RWA) in multifiber WDM networks assuming neither a special topology nor wavelength converters. Given a set of connection requests, the number of fibers deployed on each link, and the number of wavelengths a fiber can support, we seek to maximize the number of lightpaths that can be established. We formulate the problem as an integer linear program (ILP), whose validity is proven by showing that the selected lightpaths can indeed be realized by properly configuring the optical switches. Furthermore, using a Lagrangean decomposition approach, the problem formulation is significantly simplified. The main advantage of our approach is that, independent of the number of wavelengths, provably optimal solutions to the problem can be obtained by considering only one wavelength in the formulation, leading to highly efficient and scalable algorithms. Although our formulation is path-flow based rather than link-flow based, we prove that, even if all, possibly exponentially many, paths are considered, its linear programming (LP) relaxation can always be solved in polynomial time. We use the branch-and-bound algorithm in the CPLEX optimization package to solve the resulting ILP formulation. Computational results confirm the high efficiency of the Lagrangean decomposition approach.

In this paper we derive an analytic expression for the linear precoder which minimizes the bit error rate (BER) for block transmission systems with zero-forcing equalization and threshold detection. The design is developed for the two standard schemes for eliminating inter-block interference; viz, zero padding (ZP) and cyclic prefix (CP). The CP minimum BER precoder has a structure similar to that of the conventional water-filling discrete multitone (DMT) modulation scheme, but the diagonal water-filling power loading matrix is replaced by a full matrix consisting of a diagonal minimum mean square error (MMSE) power loading matrix post-multiplied by a Discrete Fourier Transform (DFT) matrix. The ZP minimum BER precoder has a corresponding structure. Performance evaluations indicate that the signal-to-noise ratio (SNR) gain of the ZP and CP minimum BER precoders over conventional water-filling DMT, MMSE, and orthogonal frequency division multiplexing (OFDM) schemes can be as much as several decibels.

If the desired signal is present in training snapshots, the adaptive array performance is known to be quite sensitive even to slight mismatches between the presumed and actual signal steering vectors. Such mismatches can occur as a result of environmental nonstationarities, look direction errors, imperfect array calibration or distorted antenna shape, as well as distortions caused by medium inhomogeneities, near-far mismatch, source spreading, and local scattering. The similar type of performance degradation can occur when the signal steering vector is known exactly but the training sample size is small. In this paper, we develop a new approach to robust adaptive beamforming in the presence of an arbitrary unknown signal steering vector mismatch. Our approach is based on the optimization of worst-case performance using Second-Order Cone (SOC) programming. The adaptive beamformer proposed is shown to have a substantially improved robustness as compared to existing algorithms and enjoy simple implementation.

Previous studies unveiled that huge channel capacity can be achieved by employing multi-element antenna arrays at both transmitter and receiver. Foschini et.al. proposed a vertical Bell Laboratories layered space-time (V-BLAST) system with a detection algorithm based on decision feedback. This system is computationally efficient and yet supporting a high data rate. However, the detection algorithm shows unsatisfactory performance when an equal number of antennas are employed at both ends. In this paper, a parallel detection algorithm is proposed to improve the performance in such scenarios. The detector consists of many low complexity sub-detectors, all of them operating in parallel on a sub-channel matrix. By selecting the submatrix appropriately the overall performance can be improved substantially.

We establish that practical multiple access based on finite size information blocks transmitted with prescribed power and with loaded multicarrier modulation, is optimal with respect to maximizing the sum-rate of circulant intersymbol interference (ISI) channels, that are assumed available at the transmitter. Circulant ISI channels are ensured either with cyclic prefixed block transmissions and an overlap-save reception, or, with zero-padded block transmissions and an overlap-add reception. Analysis asserts that sum-rate optimal multicarrier users could share one or more subcarriers depending on the underlying channels. Optimal loading is performed by specializing an existing iterative low-complexity algorithm to circulant ISI channels.

We study Friedlander's (1993) array interpolation technique, whose main shortcoming in multisource scenarios is that it does not provide sufficient robustness against sources arriving outside specified interpolation sectors. In this letter, we develop a new robust interpolation approach by minimizing the interpolation error inside the sectors of interest while setting multiple "stopband" constraints outside these sectors to prevent performance degradation effects caused by out-of-sector sources. Computationally efficient convex formulations of the robust interpolation matrix design problem using second-order cone programming are derived.

A common problem with the existing blind multiuser CDMA detectors is that their performance is very sensitive to the signature waveform mismatch (SWM) caused by channel distortion. We consider the problem of designing a blind multiuser CDMA detector which is robust to the SWM. We present a convex formulation for this problem by using the second order cone (SOC) programming. We also propose the use of recently developed interior point methods to efficiently solve the resulting SOC problem. Computer simulations indicate that the performance of our new robust blind multiuser detector is superior.

The design of a finite impulse response filter often involves a spectral 'mask' which the magnitude spectrum must satisfy. This constraint can be awkward because it yields an infinite number of inequality constraints (two for each frequency point). In current practice, spectral masks are often approximated by discretization, but we show that piecewise constant masks can be precisely enforced in a finite and convex manner via linear matrix inequalities. This facilitates the formulation of a diverse class of filter and beamformer design problems as semidefinite programmes. These optimization problems can be efficiently solved using recently developed interior point methods. Our results can be considered as extensions to the well-known positive-real and bounded-real lemmas from the systems and control literature.

We formulate the blind equalization of constant modulus (CM) signals as a convex optimization problem. This is done by performing an algebraic transformation on the direct formulation of the equalization problem and then restricting the set of design variables to a subset of the original feasible set. In particular, we express the blind equalization problem as a linear objective function subject to some linear and semidefiniteness constraints. Such semidefinite programs (SDP) can be efficiently solved using interior point methods. Simulations indicate that our method performs better than the standard methods, whilst requiring significantly fewer data samples.

In multiuser detection, maximum-likelihood detection (MLD) is optimum in the sense of minimum error probability. Unfortunately, MLD involves a computationally difficult optimization problem for which there is no known polynomial-time solution (with respect to the number of users). In this paper, we develop an approximate maximum-likelihood (ML) detector using semi-definite (SD) relaxation for the case of anti-podal data transmission, SD relaxation is an accurate and efficient approximation algorithm for certain difficult optimization problems. In MLD, SD relaxation is efficient in that its complexity is O(K/sup 3.5/), where K stands for the number of users. Simulation results indicate that the SD relaxation ML detector has its bit error performance close to the true ML detector, even when the cross-correlations between users are strong or the near-far effect is significant.

We consider the problem of identity fusion for a multisensor target tracking system whereby the sensors generate reports on the target identities. Since sensor reports are typically fuzzy, incomplete, or inconsistent, the fusion of such sensor reports becomes a major challenge. In this paper, we introduce a new identity fusion method based on the minimization of inconsistencies among the sensor reports by using a convex quadratic programming formulation. In contrast to Dempster-Shafer's evidential reasoning approach which suffers from exponentially growing complexity, our approach is highly efficient (polynomial time solvable). Moreover, our approach can fuse sensor reports of the form more general than that allowed by the evidential reasoning theory. Simulation results show that our method generates reasonable fusion results which are similar to that obtained via the evidential reasoning theory.

In many communication systems training sequences are used to help the receiver identify and/or equalize the channel. The amount of training data required depends on the convergence properties of the adaptive filtering algorithms used for equalization. In this paper we propose the use of a new adaptive filtering method, interior point least squares (IPLS), for adaptive equalization. One of the main features of the algorithm is its fast transient convergence: it thus requires fewer training bits than for example RLS. We apply the IPLS algorithm to update the weight vector for a minimum-mean-square-error decision-feedback equalizer (MMSE-DFE)in a CDMA downlink scenario. Numerical simulations show that when training sequences are short IPLS consistently outperforms RLS in terms of system bit-error-rate. As the training sequence gets longer IPLS matches the performance of the RLS algorithm.

Redundant multirate filter bank transceivers have been proposed for block-based transmission over channels whose characteristics are known at both the receiver and the transmitter. We propose a criterion for the design of such transceivers for applications in which the channel is not known at the transmitter. The design objective is the minimization of the average mean square error of the data estimates produced by a zero-forcing equalizer over a statistically modelled class of channels. Two solution methods are proposed, one of which appears to be amenable to modification for the solution of certain other robust performance problems. It is shown that the optimal transmitter provides substantially improved performance over a scheme based on multicarrier modulation.

A fast implementation of a special non-MSE cost function for blind equalization is presented here. This baud-rate equalization algorithm is based on a convex cost function coupled with a simple linear constraint on the equalizer parameters. For a generic class of channels with persistently exciting quadrature amplitude modulation input signals, this new algorithm allows the convergence of equalizer parameters to a unique global minimum achieving intersymbol interference suppression and carrier phase recovery.

Interior point optimization techniques have emerged as a new tool for developing parameter estimation algorithms. These algorithms aim to take advantage of the fast convergence properties of interior point methods, to yield, in particular, fast transient performance. We develop a simple analytic center based algorithm, which updates estimates with a constant number of computation (independent of number of samples). The convergence analysis shows that the asymptotic performance of this algorithm matches that of the well-known least squares filter (provided some mild conditions are satisfied). Some numerical simulations are provided to demonstrate the fast transient performance of the interior point algorithm.

In digital communications, orthogonal pulse shapes are often used to represent message symbols for transmission through a channel. The design of such pulse shapes is formulated as a convex semidefinite programming problem, from which a globally optimal pulse shape can be efficiently found using interior point methods. The formulation is used to design filters which achieve the minimal bandwidth for a given filter length, and the minimal filter length for a given bandwidth. The effectiveness of the method is demonstrated by the design of waveforms with substantially improved performance over the 'chip' waveforms specified in the standards for digital mobile telecommunications.

The wavelet shrinkage denoising approach is able to maintain local regularity of a signal while suppressing noise. However, the conventional wavelet shrinkage based methods are not time-scale adaptive to track the local time-scale variation. In this paper, a new time-scale adaptive denoising method for deterministic signal estimation is presented, based on the wavelet shrinkage. A class of smooth shrinkage functions and the local SURE (Stein's unbiased risk estimate) risk are employed to achieve time-scale adaptive denoising. The system structure and the learning algorithm are developed. The numerical results of our system are presented and compared with the conventional wavelet shrinkage techniques as well as their optimal solutions. Results indicate that the new time-scale adaptive method is superior to the conventional methods. It is also shown that the new method sometimes even achieves better performance than the optimal solution of the conventional wavelet shrinkage techniques.

When a message signal is transmitted through a linear dispersive system, the system output may contain severe intersymbol interference (ISI). The removal of the ISI without the aid of training signals is referred to as blind equalization. We present a new algorithm that achieves blind equalization of possibly nonminimum phase channels, based only on the second-order statistics of the source symbols. Source symbols may have an arbitrary distribution; specifically, they do not have to be independently identically distributed (i.i.d.). This is an extension to previous work done by Tong, Xu and Kailath (1994). Simulations show that the new algorithm compares favorably to the algorithm given by Tong, Xu and Kailath.

Derives a new set of basis functions which have high energy concentration in both time and frequency. The approach is based on transforming a signal energy maximization problem into an equivalent eigenvalue problem for a certain integral operator, and then showing that the eigenvectors of this integral operator form a complete orthonormal basis. This basis set is in some sense optimal since each basis function has the highest energy concentration within a certain subspace of /spl Lscr//sup 2/. Furthermore, this basis can be employed to analyze and design communication signals for which the energy concentration within the essential duration and essential bandwidth is important and some other optimum characteristics would also be required.>

Two sensors obtain data vectors x and y, respectively, and transmit real vectors m/spl I.oarr//sub 1/(x) and m/spl I.oarr//sub 2/(y), respectively, to a fusion center. The authors obtain tight lower bounds on the number of messages (the sum of the dimensions of m/spl I.oarr//sub 1/ and m/spl I.oarr//sub 2/) that have to be transmitted for the fusion center to be able to evaluate a given function f/spl I.oarr/(x,y). When the function f/spl I.oarr/ is linear, they show that these bounds are effectively computable. Certain decentralized estimation problems can be cast in the framework and are discussed in some detail. In particular, the authors consider the case where x and y are random variables representing noisy measurements and f/spl I.oarr/(x,y)=E[z|x,y], where z is a random variable to be estimated. Furthermore, it is established that a standard method for combining decentralized estimates of Gaussian random variables has nearly optimal communication requirements.>

We consider a situation where two processors F'l and Pz are to evaluate a collection of functions f], . . . .f, of two-vector variables x, v, under the assumption that processor P] (respectively, Pz ) has access only to the value of the variable x (respectively, y) and the functional form of ~1,. . . .f,.We provide some new bounds on the communication complexity (the amount of information that has to be exchanged between the processors) for this problem.An almost optimal bound is derived for the case of one-way communication when the functions ~1, . . . .~, are polynomials.We also derive some new lower bounds for the case of two-way communication that improve on earlier bounds by Abelson [2].As an application, we consider the case where x and y are n X t~matrices and f(x, y) is a particular entry of the inverse of .r+ y.Under a certain restriction on the class of allowed communication protocols, we obtain an fl(n2) lower bound, in contrast to the Q(n) lower bound obtained by applying Abelson's results.Our results are based on certain tools from classical algebraic geomet~and field extension theory.

We consider the problem of training a linear feedforward neural network by using a gradient descent-like LMS learning algorithm. The objective is to find a weight matrix for the network, by repeatedly presenting to it a finite set of examples, so that the sum of the squares of the errors is minimized. Kohonen showed that with a small but fixed learning rate (or stepsize) some subsequences of the weight matrices generated by the algorithm will converge to certain matrices close to the optimal weight matrix. In this paper, we show that, by dynamically decreasing the learning rate during each training cycle, the sequence of matrices generated by the algorithm will converge to the optimal weight matrix. We also show that for any given ∊ > 0 the LMS algorithm, with decreasing learning rates, will generate an ∊-optimal weight matrix (i.e., a matrix of distance at most ∊ away from the optimal matrix) after O(1/∊) training cycles. This is in contrast to Ω(1/∊log 1/∊) training cycles needed to generate an ∊-optimal weight matrix when the learning rate is kept fixed. We also give a general condition for the learning rates under which the LMS learning algorithm is guaranteed to converge to the optimal weight matrix.

This paper considers the problem of evaluating a function $f(x,y)(x \in \Re ^m ,y \in \Re ^n )$ using two processors $P_1 $ and $P_2 $, assuming that processor $P_1 $ (respectively, $P_2 $) has access to input x (respectively, y) and the functional form of f. A new general lower bound is established on the communication complexity (i.e., the minimum number of real-valued messages that have to be exchanged). The result is then applied to the case where $f(x,y)$ is defined as a root z of a polynomial equation $\sum _{i = 0}^{n - 1} (x_i + y_i )z^i = 0$ and a lower bound of n is obtained. This is in contrast to the $\Omega (1)$ lower bound obtained by applying earlier results of Abelson.

The authors consider a situation in which two processors P/sub 1/ and P/sub 2/ are to evaluate one or more functions f/sub 1/, . . ., f/sub s/ of two vector variables x and y, under the assumption that processor P/sub 1/ (respectively, P/sub 2/) has access only to the value of x (respectively, y) and the functional form of f/sub 1/, . . ., f/sub s/. They consider a continuous model of communication whereby real-valued messages are transmitted, and they study the minimum number of messages required for the desired computation. Tight lower bounds are established for the following three problems: (1) each f/sub i/ is a rational function and only one-way communication is allowed. (2) The variables x and y are matrices and the processors wish to solve the linear system (x+y)z=b for the unknown z. (3) The processors wish to evaluate a particular root of the polynomial equation Sigma (x/sub i/+y/sub i/)z/sup i/=0, where the sum is from i=0 to n-1.>