In high-dimensional data analysis, such as financial index tracking or biomedical applications, it is crucial to select the few relevant variables while maintaining control over the false discovery rate (FDR). In these applications, strong dependencies often exist among the variables (e.g., stock returns), which can undermine the FDR control property of existing methods like the model-X knockoff method or the T-Rex selector. To address this issue, we have expanded the T-Rex framework to accommodate overlapping groups of highly correlated variables. This is achieved by integrating a nearest neighbors penalization mechanism into the framework, which provably controls the FDR at the user-defined target level. A real-world example of sparse index tracking demonstrates the proposed method’s ability to accurately track the S&P 500 index over the past 20 years based on a small number of stocks. An open-source implementation is provided within the R package TRexSelector on CRAN.

We propose the Terminating-Random Experiments (T-Rex) selector, a fast variable selection method for high-dimensional data. The T-Rex selector controls a user-defined target false discovery rate (FDR) while maximizing the number of selected variables. This is achieved by fusing the solutions of multiple early terminated random experiments. The experiments are conducted on a combination of the original predictors and multiple sets of randomly generated dummy predictors. A finite sample proof based on martingale theory for the FDR control property is provided. Numerical simulations confirm that the FDR is controlled at the target level while allowing for high power. We prove that the dummies can be sampled from any univariate probability distribution with finite expectation and variance. The computational complexity of the proposed method is linear in the number of variables. The T-Rex selector outperforms state-of-the-art methods for FDR control in numerical experiments and on a simulated genome-wide association study (GWAS), while its sequential computation time is more than two orders of magnitude lower than that of the strongest benchmark methods. The open source R package TRexSelector containing the implementation of the T-Rex selector is available on CRAN.

Algorithms that ensure reproducible findings from large-scale, high-dimensional data are pivotal in numerous signal processing applications . In recent years, multivariate false discovery rate (FDR) controlling methods have emerged, providing guarantees even in high-dimensional settings where the number of variables surpasses the number of samples. However, these methods often fail to reliably control the FDR in the presence of highly dependent variable groups, a common characteristic in fields such as genomics and finance. To tackle this critical issue, we introduce a novel framework that accounts for general dependency structures. Our proposed dependency-aware T-Rex selector integrates hierarchical graphical models within the T-Rex framework to effectively harness the dependency structure among variables. Leveraging martingale theory, we prove that our variable penalization mechanism ensures FDR control. We further generalize the FDR-controlling framework by stating and proving a clear condition necessary for designing both graphical and non-graphical models that capture dependencies. Numerical experiments and a breast cancer survival analysis use-case demonstrate that the proposed method is the only one among the state-of-the-art benchmark methods that controls the FDR and reliably detects genes that have been previously identified to be related to breast cancer. An open-source implementation is available within the R package TRexSelector on CRAN.

Learning a graph from data is the key to taking advantage of graph signal processing tools. Most of the conventional algorithms for graph learning require complete data statistics, which might not be available in some scenarios. In this work, we aim to learn a graph from incomplete time-series observations. From another viewpoint, we consider the problem of semi-blind recovery of time-varying graph signals where the underlying graph model is unknown. We propose an algorithm based on the method of block successive upperbound minimization (BSUM), for simultaneous inference of the signal and the graph from incomplete data. Simulation results on synthetic and real time-series demonstrate the performance of the proposed method for graph learning and signal recovery.

Sparse principal component analysis (PCA) aims at mapping large dimensional data to a linear subspace of lower dimension. By imposing loading vectors to be sparse, it performs the double duty of dimension reduction and variable selection. Sparse PCA algorithms are usually expressed as a trade-off between explained variance and sparsity of the loading vectors (i.e., number of selected variables). As a high explained variance is not necessarily synonymous with relevant information, these methods are prone to select irrelevant variables. To overcome this issue, we propose an alternative formulation of sparse PCA driven by the false discovery rate (FDR). We then leverage the Terminating-Random Experiments (T-Rex) selector to automatically determine an FDR-controlled support of the loading vectors. A major advantage of the resulting T-Rex PCA is that no sparsity parameter tuning is required. Numerical experiments and a stock market data example demonstrate a significant performance improvement.

The Passive-Aggressive (PA) method is widely used in online regression problems for handling large-scale streaming data, typically updating model parameters in a passive-aggressive manner based on whether the error exceeds a predefined threshold. However, this approach struggles with determining optimal thresholds and adapting to complex scenarios with side information, where tracking accuracy is not the sole metric in the regression model. To address these challenges, we introduce a novel adaptive framework that allows finer adjustments to the weight vector in PA using side information. This framework adaptively selects the threshold parameter in PA, theoretically ensuring convergence to the optimal setting. Additionally, we present an efficient implementation of our algorithm that significantly reduces computational complexity. Numerical experiments show that our model achieves outstanding performance associated with the side information while maintaining low tracking error, demonstrating marked improvements over traditional PA methods across various scenarios.

Gaussian Markov random fields, a class of graphical models, play an increasingly important role in real-world problems, where they are often applied to uncover conditional correlations between pairs of entities in a network. Motivated by recent applications of graphs in financial markets, we investigate the problem of learning undirected, weighted, normalized, graphical models. More precisely, we design an optimization algorithm to learn precision matrices that are modeled as normalized graph Laplacians. The proposed algorithm takes advantages of frameworks such as the alternating direction method of multipliers and projected gradient descent, which allows us to decompose the original problem into subproblems that can be solved efficiently. We demonstrate the empirical performance of the proposed algorithm, in comparison to state-of-the-art benchmark models, in a number of datasets involving financial time-series.

We consider the problem of estimating (diagonally dominant) M-matrices as precision matrices in Gaussian graphical models. Such models have shown interesting properties, e.g., the maximum likelihood estimator exists with as little as two observations in the case of M-matrices, and exists even with one observation in the case of diagonally dominant M-matrices. We propose an adaptive multiple-stage estimation method, which refines the estimate by solving a weighted $\ell_1$-regularized problem in each stage. We further design a unified framework based on gradient projection method to solve the regularized problem, equipped with different projections to handle the constraints of M-matrices and diagonally dominant M-matrices. Theoretical analysis of the estimation error is established. The proposed method outperforms state-of-the-art methods in estimating precision matrices and identifying graph edges, as evidenced by synthetic and financial time-series data sets.

We study the problem of estimating precision matrices in Gaussian distributions that are multivariate totally positive of order two ($\mathrm{MTP}_2$). The precision matrix in such a distribution is an M-matrix. This problem can be formulated as a sign-constrained log-determinant program. Current algorithms are designed using the block coordinate descent method or the proximal point algorithm, which becomes computationally challenging in high-dimensional cases due to the requirement to solve numerous nonnegative quadratic programs or large-scale linear systems. To address this issue, we propose a novel algorithm based on the two-metric projection method, incorporating a carefully designed search direction and variable partitioning scheme. Our algorithm substantially reduces computational complexity, and its theoretical convergence is established. Experimental results on synthetic and real-world datasets demonstrate that our proposed algorithm provides a significant improvement in computational efficiency compared to the state-of-the-art methods.

This paper studies the problem of learning the large-scale Gaussian graphical models that are multivariate totally positive of order two ($\text{MTP}_2$). By introducing the concept of bridge, which commonly exists in large-scale sparse graphs, we show that the entire problem can be equivalently optimized through (1) several smaller-scaled sub-problems induced by a \emph{bridge-block decomposition} on the thresholded sample covariance graph and (2) a set of explicit solutions on entries corresponding to \emph{bridges}. From practical aspect, this simple and provable discipline can be applied to break down a large problem into small tractable ones, leading to enormous reduction on the computational complexity and substantial improvements for all existing algorithms. The synthetic and real-world experiments demonstrate that our proposed method presents a significant speed-up compared to the state-of-the-art benchmarks.

We propose estimating the scale parameter (mean of the eigenvalues) of the scatter matrix of an unspecified elliptically symmetric distribution using weights obtained by solving Tyler's M-estimator of the scatter matrix. The proposed Tyler's weights-based estimate (TWE) of scale is then used to construct an affine equivariant Tyler's M-estimator as a weighted sample covariance matrix using normalized Tyler's weights. We then develop a unified framework for estimating the unknown tail parameter of the elliptical distribution (such as the degrees of freedom (d.o.f.)$\nu$of the multivariate$t$(MVT) distribution). Using the proposed TWE of scale, a new robust estimate of the d.o.f. parameter of MVT distribution is proposed with excellent performance in heavy-tailed scenarios, outperforming other competing methods. R-package is available that implements the proposed method.

Monotonicity is often a fundamental assumption involved in the modeling of a number of real-world applications. From an optimization perspective, monotonicity is formulated as partial order constraints among the optimization variables, commonly known as isotone optimization. In this paper, we develop an efficient, provable convergent algorithm for solving isotone optimization problems. The proposed algorithm is general in the sense that it can handle any arbitrary isotonic constraints and a wide range of objective functions. We evaluate our algorithm and state-of-the-art methods with experiments involving both synthetic and real-world data. The experimental results demonstrate that our algorithm is more efficient by one to four orders of magnitude than the state-of-the-art methods.

We investigate the problem of learning an undirected, weighted bipartite graph under the Gaussian Markov random field model, for which we present an optimization formulation along with an efficient algorithm based on the projected gradient descent. Motivated by practical applications, where outliers or heavy-tailed events are present, we extend the proposed learning scheme to the case in which the data follow a multivariate Student-$t$ distribution. As a result, the optimization program is no longer convex, but a verifiably convergent iterative algorithm is proposed based on the majorization-minimization framework. Finally, we propose an efficient and provably convergent algorithm for learning $k$-component bipartite graphs that leverages rank constraints of the underlying graph Laplacian matrix. The proposed estimators outperform state-of-the-art methods for bipartite graph learning, as evidenced by real-world experiments using financial time series data.

This paper considers the problem of high-dimensional sparse precision matrix estimation under Laplacian constraints. We prove that the Laplacian constraints bring favorable properties for estimation: the Gaussian maximum likelihood estimator exists and is unique almost surely on the basis of one observation, irrespective of the dimension. We establish the optimal rate of convergence under Frobenius norm by the derivation of the minimax lower and upper bounds. The minimax lower bound is obtained by applying Le Cam-Assouad’s method with a novel construction of a subparameter space of multivariate normal distributions. The minimax upper bound is established by designing an adaptive $\ell_1$-norm regularized maximum likelihood estimation method and quantifying the rate of convergence. We prove that the proposed estimator attains the optimal rate of convergence with an overwhelming probability. Numerical experiments demonstrate the effectiveness of the proposed estimator.

The vector autoregressive (VAR) models provide a significant tool for multivariate time series analysis. Most existing works on VAR modeling are based on the multivariate Gaussian distribution. However, heavy-tailed distributions are suggested more reasonable for capturing the real-world phenomena, like the presence of outliers and a stronger possibility of extreme values. Furthermore, missing values in observed data is a real problem, which typically happens during the data observation or recording process. In this paper, we propose an algorithmic framework to estimate the parameters of a VAR model with heavy-tailed Student’s t distributed innovations from incomplete data based on the stochastic approximation expectation maximization (SAEM) algorithm coupled with a Markov Chain Monte Carlo (MCMC) procedure. Extensive experiments with synthetic data corroborate our claims.

Heavy-tailed statistical distributions have long been considered a more realistic statistical model for the data generating process in financial markets in comparison to their Gaussian counterpart. Nonetheless, mathematical nuisances, including nonconvexities, involved in estimating graphs in heavy-tailed settings pose a significant challenge to the practical design of algorithms for graph learning. In this work, we present graph learning estimators based on the Markov random field framework that assume a Student-$t$ data generating process. We design scalable numerical algorithms, via the alternating direction method of multipliers, to learn both connected and $k$-component graphs along with their theoretical convergence guarantees. The proposed methods outperform state-of-the-art benchmarks in an extensive series of practical experiments with publicly available data from the S\&P500 index, foreign exchanges, and cryptocurrencies.

A popular regularized (shrinkage) covariance estimator is the shrinkage sample covariance matrix (SCM) which shares the same set of eigenvectors as the SCM but shrinks its eigenvalues toward its grand mean. In this paper, a more general approach is considered in which the SCM is replaced by an M-estimator of scatter matrix and a fully automatic data adaptive method to compute the optimal shrinkage parameter with minimum mean squared error is proposed. Our approach permits the use of any weight function such as Gaussian, Huber's, or t weight functions, all of which are commonly used in M-estimation framework. Our simulation examples illustrate that shrinkage M-estimators based on the proposed optimal tuning combined with robust weight function do not loose in performance to shrinkage SCM estimator when the data is Gaussian, but provide significantly improved performance when the data is sampled from a heavy-tailed distribution.

The heuristic 1/N (equally weighted) portfolio and long-only quintile portfolio are both popular simple strategies in financial investment. In the 1/N portfolio, a fraction of 1/N of wealth is allocated to each of the N available assets. In the long-only quintile portfolio, first the assets are sorted according to some factors, e.g., expected returns, and then the strategy equally longs the top 20% (i.e., top quintile). Although they have been criticized for naiveness when proposed by practitioners, they have shown great advantage over some sophisticated portfolios. They are becoming more and more popular in practical investment due to their stable performance and easy deployment. In this paper, we formulate a mathematically meaningful robust maximum return portfolio design and show that it reduces to the two heuristic portfolios under different level of estimation error in the mean returns. A variance-adjusted uncertainty set is also proposed to derive an inverse-volatility portfolio, which shows consistent advantage over the heuristic portfolios in backtesting with real market data.

In this paper, we consider the problem of learning a sparse graph from the Laplacian constrained Gaussian graphical model. This problem can be formulated as a penalized maximum likelihood estimation of the precision matrix under Laplacian structural constraints. Like in the classical graphical lasso problem, recent works made use of the $\ell_1$-norm with the goal of promoting sparsity in the Laplacian constrained precision matrix estimation. However, through empirical evidence, we observe that the $\ell_1$-norm is not effective in imposing a sparse solution in this problem. From a theoretical perspective, we prove that a large regularization parameter will surprisingly lead to a solution representing a fully connected graph instead of a sparse graph. To address this issue, we propose a nonconvex penalized maximum likelihood estimation method, and establish the order of the statistical error. Numerical experiments involving synthetic and real-world data sets demonstrate the effectiveness of the proposed method.

Graph learning from data is a canonical problem that has received substantial attention in the literature. Learning a structured graph is essential for interpretability and identification of the relationships among data. In general, learning a graph with a specific structure is an NP-hard combinatorial problem and thus designing a general tractable algorithm is challenging. Some useful structured graphs include connected, sparse, multi-component, bipartite, and regular graphs. In this paper, we introduce a unified framework for structured graph learning that combines Gaussian graphical model and spectral graph theory. We propose to convert combinatorial structural constraints into spectral constraints on graph matrices and develop an optimization framework based on block majorization-minimization to solve structured graph learning problem. The proposed algorithms are provably convergent and practically amenable for a number of graph based applications such as data clustering. Extensive numerical experiments with both synthetic and real data sets illustrate the effectiveness of the proposed algorithms. An open source R package containing the code for all the experiments is available at https://CRAN.R-project.org/package=spectralGraphTopology.

Minimax multiple-input multiple-output (MIMO) transmit beampattern matching is a fundamental and important problem in many MIMO systems. The problem is formulated to minimize the maximum beampattern matching error as well as suppress the cross-correlation beampatterns while taking different practical waveform constraints into consideration. Due to the high nonconvexity of the problem, the traditional way for problem solving is a two-stage approach, where a waveform covariance matrix is firstly designed and then the waveforms are synthesized from the covariance matrix under a specific constraint. This approach is usually very time consuming and only results in suboptimal solutions. In this paper, a novel and unified one-stage approach is proposed to solve the minimax beampattern matching problem which is capable of considering multiple waveform constraints. Superior performance of the proposed approach over the classical approach is verified through numerical simulations.

Learning a graph with a specific structure is essential for interpretability and identification of the relationships among data. But structured graph learning from observed samples is an NP-hard combinatorial problem. In this paper, we first show, for a set of important graph families it is possible to convert the combinatorial constraints of structure into eigenvalue constraints of the graph Laplacian matrix. Then we introduce a unified graph learning framework lying at the integration of the spectral properties of the Laplacian matrix with Gaussian graphical modeling, which is capable of learning structures of a large class of graph families. The proposed algorithms are provably convergent and practically amenable for big-data specific tasks. Extensive numerical experiments with both synthetic and real datasets demonstrate the effectiveness of the proposed methods. An R package containing codes for all the experimental results is submitted as a supplementary file.

Interference management is a fundamental issue in device-to-device (D2D) communications whenever the transmitter-and-receiver pairs are located in close proximity and frequencies are fully reused, so active links may severely interfere with each other. This paper devises an optimization strategy named FPLinQ to coordinate the link scheduling decisions among the interfering links, along with power control and beamforming. The key enabler is a novel optimization method called matrix fractional programming (FP) that generalizes previous scalar and vector forms of FP in allowing multiple data streams per link. From a theoretical perspective, this paper provides a deeper understanding of FP by showing a connection to the minorization-maximization (MM) algorithm. From an application perspective, this paper shows that as compared to the existing methods for coordinating scheduling in the D2D network, such as FlashLinQ, ITLinQ, and ITLinQ+, the proposed FPLinQ approach is more general in allowing multiple antennas at both the transmitters and the receivers, and further in allowing arbitrary and multiple possible associations between the devices via matching. Numerical results show that FPLinQ significantly outperforms the previous state-of-the-art in a typical D2D communication environment.

This paper proposes a novel and structured framework for parameter estimation from incomplete time series data under heavy-tailed random walk model. Traditionally, maximum likelihood estimation (MLE) for Gaussian random walk model from incomplete data has been considered. However, it is not applicable in many practical applications that follow some heavy-tailed random walk model. We first model a random walk model with Student-t residuals. Then we develop an MLE-based stochastic expectation maximization (EM) algorithm. The algorithm provides tractable E and M steps, which are easy to implement with simple updates and fast convergence. The simulation results illustrate the improved performance over the benchmarks.

In this paper, the multiple-input multiple-output (MIMO) transmit beampattern matching problem is considered. The problem is formulated to approximate a desired transmit beampattern (i.e., an energy distribution in space and frequency) and to minimize the cross-correlation of signals reflected back to the array by considering different practical waveform constraints at the same time. Due to the nonconvexity of the objective function and the waveform constraints, the optimization problem is highly nonconvex. An efficient one-step method is proposed to solve this problem based on the majorization-minimization (MM) method. The performance of the proposed algorithms compared to the state-of-art algorithms is shown through numerical simulations.

The problem of estimating sparse eigenvectors of a symmetric matrix attracts a lot of attention in many applications, especially those with high dimensional data set. While classical eigenvectors can be obtained as the solution of a maximization problem, existing approaches formulated this problem by adding a penalty term into the objective function that encourages a sparse solution. Nevertheless, the resulting methods achieve sparsity at a sacrifice of the orthogonality property. In this paper, we develop a new method to estimate dominant sparse eigenvectors without trading off their orthogonality. The problem is highly non-convex and too hard to handle. We apply the minorization-maximization (MM) framework where we iteratively maximize a tight lower bound (surrogate function) of the objective function over the Stiefel manifold. The inner maximization problem turns out to be the rectangular Procrustes problem, which has a closed-form solution. Numerical experiments show that the propose method matches or outperforms existing algorithms in terms of recovery probability and explained variance.

After the 2008 financial crisis, risk management has become more important than performance management and an alternative portfolio design, referred to as risk parity portfolio, has been receiving significant attention from both theoretical and practical fields due to its advantage in diversification of (ex-ante) risk contributions among assets. Usually, this approach results in a portfolio with nonzero weights in all the assets. Investors, however, could not lay out the capital among all the assets listed on the markets, which results in unrealistically high transaction costs, and therefore, reduction of the return of the designed portfolio. To overcome this drawback, in this paper, we propose a method to jointly select only some of the assets and distribute the capital among the selected assets such that the risk is diversified enough.

Sequences with low aperiodic autocorrelation sidelobes are well-known to have extensive applications in active sensing and communication systems. In this paper, we consider the sequence design problem of minimizing the ℓp-norm of the autocorrelation side-lobes, which can then be used to minimize the peak sidelobe level (PSL) criterion. An algorithm based on the general majorization-minimization method is developed to tackle the problem. The proposed algorithm can be implemented by means of fast Fourier transform (FFT) operations and thus is computationally efficient in practice. Numerical experiments show that the proposed algorithm can produce very long sequences with impulse-like autocorrelation and with much smaller PSL compared with some well-known analytical sequences.

Unimodular sequences have been widely used in communications and radars, for which some numerical algorithms have been proposed recently to obtain good autocorrelation properties [1,2]. Design of such "good" sequences, however, does not take into account any prior information of the channel to be estimated. Although shaping the autocorrelation of a training sequence may imply a good performance, it may be advantageous to directly optimize the performance measure of interest. In this paper, we consider the problem of optimal constant-modulus training sequence design for MMSE estimation of the channel impulse response and conditional mutual information maximization. Efficient iterative algorithms based on the majorization-minorization framework are proposed for each formulation. Numerical examples show that our proposed training sequences achieve better performances than that of low sidelobes or random phases.

In this paper, we present an approach to solve the nonconvex optimization problem that arises when designing the transmit covariance matrices in multiuser multiple-input multiple-output (MIMO) broadcast networks implementing simultaneous wireless information and power transfer (SWIPT). The MIMO SWIPT design is formulated as a nonconvex optimization problem in which system sum rate is optimized considering per-user harvesting constraints. Two different approaches are proposed. The first approach is based on a classical gradient-based method for constrained optimization. The second approach is based on difference of convex (DC) programming. The idea behind this approach is to obtain a convex function that approximates the nonconvex objective and, then, solve a series of convex subproblems that, eventually, will provide a (locally) optimum solution of the general nonconvex problem. The solution obtained from the proposed approach is compared to the classical block-diagonalization (BD) strategy, typically used to solve the nonconvex multiuser MIMO network by forcing no inter-user interference. Simulation results show that the proposed approach improves both the system sum rate and the power harvested by users simultaneously. In terms of computational time, the proposed DC programming outperforms the classical gradient methods.

This paper considers a network of energy harvesting wireless nodes transmitting simultaneously in a Gaussian interference channel and investigates a distributed power allocation algorithm that maximizes the sum-rate. The power consumption model is based on a series of step functions that allow to model, among others, radio frequency circuits being on/off and the startup power consumption of the transmitter. After showing that the sum-rate maximization problem is nonsmooth, nonconvex, and NP-hard, the Iterative Smooth and Convex approximation Algorithm (ISCA) is proposed, which successively approximates the step functions by proper smooth functions to obtain a sequence of smooth nonconvex problems that can be solved by means of the successive convex approximation method. It is demonstrated that the ISCA distributedly converges to a stationary solution of the sum-rate maximization problem. For the particular case of point to point communications, the numerical results show that the ISCA is able to avoid bad stationary solutions, performing close to the globally optimal solution. The performance of the ISCA is also evaluated in the interference channel and with real solar energy harvesting data.

In this paper, we start with the standard support vector machine (SVM) formulation and extend it by proposing a general SVM that allows many different variations captured by normalizations in the formulation with very diverse numerical performance. The proposed formulation can not only capture the existing work, i.e., standard soft-margin SVM, ℓ1-SVM, as special cases, but also enable us to propose more SVMs that outperform the existing ones under some scenarios.

Unimodular sequences with low autocorrelations are desired in many applications, especially in the area of radar and code-division multiple access (CDMA). In this paper, we propose a new algorithm to design unimodular sequences with low integrated sidelobe level (ISL), which is a widely used measure of the goodness of a sequence's correlation property. The algorithm falls into the general framework of majorization-minimization (MM) algorithms and thus shares the monotonic property of such algorithms. In addition, the algorithm can be implemented via fast Fourier transform (FFT) operations and thus is computationally efficient. Numerical experiments show that the proposed algorithm outperforms the state-of-the-art algorithm in terms of both the quality of designed sequences and the computational complexity.

In this paper, we consider the robust covariance estimation problem in the non-Gaussian set-up. In particular, Tyler's M-estimator is adopted for samples drawn from a heavy-tailed elliptical distribution. For some applications, the covariance matrix naturally possesses certain structure. Therefore, incorporating the prior structure information in the estimation procedure is beneficial to improving estimation accuracy. The problem is formulated as a constrained minimization of the Tyler's cost function, where the structure is characterized by the constraint set. A numerical algorithm based on majorization-minimization is derived for general structures that can be characterized as a convex set, where a sequence of convex programming is solved. For the set of matrices that can be decomposed as the sum of rank one positive semidefinite matrices, which has a wide range of applications, the algorithm is modified with much lower complexity. Simulation results demonstrate that the proposed structure-constrained Tyler's estimator achieves smaller estimation error than the unconstrained case.

In this work, we focus on separable convex optimization problems with linear and box constraints and compute the solution in closed-form as a function of some Lagrange multipliers that can be easily computed in a finite number of iterations. This allows us to bridge the gap between a wide family of power allocation problems of practical interest in signal processing and communications and their efficient implementation in practice.

Noncooperative game-theoretic tools have been increasingly used to study many important resource allocation problems in communications, networking, smart grids, and portfolio optimization. In this paper, we consider a general class of convex Nash equilibrium problems (NEPs), where each player aims at solving an arbitrary smooth convex optimization problem. Differently from most of current works, we do not assume any specific structure for the players' problems, and we allow the optimization variables of the players to be matrices in the complex domain. Our main contribution is the design of a novel class of distributed (asynchronous) best-response-algorithms suitable for solving the proposed NEPs, even in the presence of multiple solutions. The new methods, whose convergence analysis is based on variational inequality (VI) techniques, can select, among all the equilibria of a game, those that optimize a given performance criterion, at the cost of limited signaling among the players. This is a major departure from existing best-response algorithms, whose convergence conditions imply the uniqueness of the NE. Some of our results hinge on the use of VI problems directly in the complex domain; the study of these new kind of VIs also represents a noteworthy innovative contribution. We then apply the developed methods to solve some new generalizations of Single Input Single Output (SISO) and Multiple Input Multiple Output (MIMO) games in cognitive radio systems, showing a considerable performance improvement over classical pure noncooperative schemes.

The envisioned smart grid aims to improve the interaction between the supply- and the demand-side of the electricity network, resulting in a great optimization potential. In this paper, we propose a holistic-based, distributed day-ahead demand-side management method that is suitable for energy markets subject to an external regulation. Here, active subscribers solve the nonconvex problem of deriving the bidding strategies that minimize their overall expected monetary expense and simultaneously optimize eventual dispatchable energy generation and storage strategies. We show that, when such users collaborate, they achieve greater saving with respect to the corresponding user-oriented, selfish optimization. In this setting, we propose a cooperative, distributed, and iterative algorithm providing the optimal bidding, production, and storage strategies of the users, along with its convergence properties.

We propose a decomposition framework for the distributed optimization of general nonconvex sum-utility functions arising in the design of wireless multi-user interfering systems. Our main contributions are: the development of the first provably convergent Jacobi best-response algorithm, where all users simultaneously solve a suitably convexified version of the original sum-utility optimization problem; the derivation of a general dynamic pricing mechanism that provides a unified view of existing pricing schemes that are based, instead, on heuristics; and a framework that can be easily particularized to well-known applications, giving rise to practical algorithms that outperform all existing ad-hoc methods proposed for very specific problems. Our framework contains as special cases well-known gradient algorithms for nonconvex sum-utility problems, and many block-coordinate descents schemes for convex functions.

In cognitive radio (CR) systems, the primary users (PU) are protected by temperature interference constraints imposed on secondary users (SU). However, such limitations may be easily violated by SUs if perfect SU-to-PU channel state information (CSI) is not available at the secondary transmitters. In this paper, we propose a novel and distributed design of MIMO CR networks that is robust against imperfect SU-to-PU CSI. Specifically, we formulate the system design as a noncooperative game and robust global interference constraints are enforced via pricing; the prices are thus additional variables to be optimized. Building on the advanced and new theory of finite-dimensional variational inequalities (VI) in the complex domain, we analyze the proposed NE problem and devise alternative distributed algorithms along with their convergence properties.

Minimum variance beamformers are widely used for array signal processing. It is known that the diagonal loading method can improve the robustness against mismatches caused by the imprecise steering vector (or the channel vector) and the noise covariance matrix. Instead of concentrating on one aspect of the mismatches and assuming perfect knowledge of the other, we handle both estimation error in the steering vector and the noise covariance matrix caused by the finite sample size simultaneously. We employ high-dimensional asymptotics to reflect the finite sample size, and estimate the optimal loading factor based on random matrix theory. In an asymptotic setting where the number of samples is comparable to the array dimension, we obtain a beamformer that is as good as the beamformer with optimal diagonal loading. Monte Carlo simulations show the advantage of our beamformer in the finite sample size regime.

Cognitive Radio (CR) systems are built on the coexistence of primary users (PUs) and secondary users (SUs), the latter being allowed to share spectral resources with the PUs but under strict interference limitations. However, such limitations may easily be violated by SUs if perfect SU-to-PU channel state information (CSI) is not available at the secondary transmitters, which always happens in practice. In this paper, we propose a distributed design of MIMO CR networks under global interference temperature constraints that is robust (in the worst-case sense) against SU-to-PU channel uncertainties. More specifically, we consider two alternative formulations that are complementary to each other in terms of signaling and system performance, namely: a game-theoretical design and a social-oriented optimization. To study and solve the proposed formulations we hinge on the new theory of finite-dimensional variational inequalities (VI) in the complex domain and a novel parallel decomposition technique for nonconvex sum-utility problems with coupling constraints, respectively. A major contribution of this paper is to devise a new class of distributed best-response algorithms with provable convergence. The algorithms differ in computational complexity, convergence speed, communication overhead, and achievable performance; they are thus applicable to a variety of CR scenarios, either cooperative or non-cooperative, which allow the SUs to explore the trade-off between signaling and performance.

Semidefinite relaxation (SDR) provides a computationally efficient polynomial-time approximation of the maximum likelihood detector. However, most of the existing works mainly focus on particular signal constellations. In this paper, we propose a universal binary semidefinite relaxation scheme that can handle arbitrary signal constellations in polynomial time. The proposed scheme first binarizes the original signal space to a linearly constrained binary space, and then solves the detection problem through SDR.colorblack{{} A specialized dual barrier method is provided to solve the SDR more efficiently. In addition, we propose to apply on-the-fly decision feedback to further reduce the computational complexity and improve the detection performance. The} proposed binary SDR, together with on-the-fly decision feedback scheme, can provide comparable or better solutions compared to existing SDR methods specialized to specific constellations such as 16-QAM and 8-PSK in terms of computational complexity and symbol error rate. Furthermore, the proposed scheme is universal and can solve any other constellations such as 12-QAM, 32-QAM, or M-PSK.

The scalar additive Gaussian noise channel has the “single crossing point” property between the minimum mean square error (MMSE) in the estimation of the input given the channel output, assuming a Gaussian input to the channel, and the MMSE assuming an arbitrary input. This paper extends the result to the parallel vector additive Gaussian channel in three phases. 1) The channel matrix is the identity matrix, and we limit the Gaussian input to a vector of Gaussian i.i.d. elements. The “single crossing point” property is with respect to the signal-to-noise ratio (as in the scalar case). 2) The channel matrix is arbitrary, and the Gaussian input is limited to an independent Gaussian input. A “single crossing point” property is derived for each diagonal element of the MMSE matrix. 3) The Gaussian input is allowed to be an arbitrary Gaussian random vector. A “single crossing point” property is derived for each eigenvalue of the difference matrix between the two MMSE matrices. These three extensions are then translated to new information theoretic properties on the mutual information, using the I-MMSE relationship, a fundamental relationship between estimation theory and information theory revealed by Guo and coworkers. The results of the last phase are also translated to a new property of Fisher information. Finally, the applicability of all three extensions on information theoretic problems is demonstrated through a proof of a special case of Shannon's vector entropy power inequality, a converse proof of the capacity region of the parallel degraded broadcast channel (BC) under an input per-antenna power constraint and under an input covariance constraint, and a converse proof of the capacity region of the compound parallel degraded BC under an input covariance constraint.

Energy efficiency is a major design issue in the context of Wireless Sensor Networks (WSN). If data is to be sent to a far-away base station, collaborative beamforming by the sensors may help to distribute the load among the nodes and reduce fast battery depletion. However, collaborative beamforming techniques are far from optimality and in many cases may be wasting more power than required. In this contribution we consider the issue of energy efficiency in beamforming applications. Using a convex optimization framework, we propose the design of a virtual beamformer that maximizes the network's lifetime while satisfying a pre-specified Quality of Service (QoS) requirement. A distributed consensus-based algorithm for the computation of the optimal beamformer is also provided.

Consider a unicast downlink beamforming optimization problem with robust signal-to-interference-plus-noise ratio constraints to account for non-perfect channel state information at the base station. The convexity of the robust beamforming problem remains unknown. A slightly conservative version of the robust beamforming problem is thus studied herein as a compromise. It is in the form of a semi-infinite second-order cone program (SOCP), and more importantly, it possesses an equivalent and explicit convex reformulation, due to an linear matrix inequality description of the cone of Lorentz-positive maps. Hence the robust beamforming problem can be efficiently solved by an optimization solver. The simulation results show that the conservativeness of the robust form of semi-infinite SOCP is appropriate in terms of problem feasibility rate and the average transmission power.

We consider a worst-case robust precoding design for multi-input multi-output (MIMO) communication systems with imperfect channel state information at the transmitter (CSIT). Instead of a particular choice, we consider a general imperfect CSIT model that only assumes the channel errors to be within a convex set, which includes most common imperfect CSIT models as special cases. The robust precoding design is formulated as a maximin problem, aiming at maximizing the worst-case received signal-to-noise ratio or minimizing the worst-case error probability. It is shown that the robust precoder can be easily obtained by solving a convex problem. We further provide an equivalent but more practical form of the convex problem that can be efficiently handled with common optimization methods and software packages.

When the observation dimension is of the same order of magnitude as the number of samples, the conventional estimators of covariance matrix and its inverse perform poorly. In order to obtain well-behaved estimators in high-dimensional settings, we consider a general class of estimators of covariance matrices and precision matrices (i.e. the inverse covariance matrix) based on weighted sampling and linear shrinkage. The estimation error is measured in terms of the matrix quadratic loss, and the latter is used to calibrate the set of parameters defining our proposed estimator. In an asymptotic setting where the observation dimension is of the same order of magnitude as the number of samples, we provide an estimator of the precision matrix that is as good as the oracle estimator. Our research is based on recent contributions in the field of random matrix theory and Monte-Carlo simulations show the advantage of our precision matrix estimator in finite sample size settings.

Following the seminal work by Zheng and Tse on the diversity and multiplexing tradeoff (DMT) of multiple-input multiple-output (MIMO) channels, in this paper, we introduce the array gain to investigate the fundamental relation between transmission rate and reliability in MIMO systems. The array gain gives information on the power offset that results from exploiting channel state information at the transmitter or as a consequence of the channel model. Hence, the diversity, multiplexing, and array gain (DMA) analysis is able to cope with the limitations of the original DMT and provide an operational meaning in the sense that the DMA gains of a particular system can be directly translated into a parameterized characterization of its associated outage probability performance. In this paper, we derive the best DMA gains achievable by any scheme employing isotropic signaling in uncorrelated Rayleigh, semicorrelated Rayleigh, and uncorrelated Rician block-fading MIMO channels. We use these results to analyze the effect of important channel parameters on the outage performance at different points of the DMT curve.

Following the seminal work of Zheng and Tse on the diversity and multiplexing tradeoff (DMT) of MIMO channels, in this paper we introduce the array gain to investigate the fundamental relation between transmission rate and reliability in MIMO systems. The array gain gives information on the power offset that results from exploiting channel state information at the transmitter or as a consequence of the channel model. Hence, the diversity, multiplexing, and array gain (DMA) analysis can be directly translated into a parameterized characterization of its associated outage probability performance. In this paper we derive the fundamental DMA tradeoff achievable by any scheme in uncorrelated Rayleigh, semicorrelated Rayleigh, and uncorrelated Rician block-fading MIMO channels. We use these results to analyze the effect of important channel parameters in the outage performance at different points of the DMT curve.

This work considers the independent component analysis (ICA) of quaternion random vectors. In particular, we focus on the Gaussian case, and therefore the ICA problem is solved by exclusively exploiting the second-order statistics (SOS) of the observations. In the quaternion case, the SOS of a random vector are given by the covariance matrix and three complementary covariance matrices. Thus, quaternion ICA amounts to jointly diagonalizing these four matrices. Following a maximum likelihood (ML) approach, we show that the ML-ICA problem reduces to the minimization of a cost function, which can be interpreted as a measure of the entropy loss due to the correlation among the estimated sources. In order to solve the non-convex ML-ICA problem, we propose a practical quasi-Newton algorithm based on quadratic local approximations of the cost function. Finally, the practical performance and potential application of the proposed technique is illustrated by means of numerical examples.

Consider the downlink beamforming optimization problem with signal-to-interference-plus-noise ratio constraints, null-shaping interference constraints and multiple groups of individual shaping constraints. We propose an efficient algorithm for the problem, which consists of firstly solving the dual of the semidefinite programm (SDP) relaxation, secondly formulating a linear program (LP) and solving it to find a rank-one solution of the SDP relaxation. In contrast to the existing algorithms, the analysis of the proposed algorithm includes neither the rank reduction steps (purification process) nor the Perron-Frobenius theorem.

The concept of cognitive radio has recently received great attention from the research community as a promising paradigm to achieve efficient use of the frequency resource by allowing the coexistence of primary and secondary users in the same bandwidth. In this paper, we propose a novel Nash equilibrium (NE) problem to model concurrent communications of cognitive secondary users who compete with each other to maximize their information rate, subject to constraints on the transmit power (and possibly spectral masks) as well as on per-carrier and total aggregate interference tolerable at the primary users' receivers. The coupling among the strategies of the players due to the interference constraints presents a new challenge for the analysis of this class of Nash games that cannot be addressed using the game theoretical models proposed in the literature. For this purpose, we need the framework given by the more advanced theory of finite-dimensional Variational Inequalities. This provides us with all the mathematical tools necessary to analyze the proposed NE problem (e.g., existence and uniqueness of the solution) and to devise alternative distributed algorithms along with their convergence properties.

This paper extends the “single crossing point” property of the scalar MMSE function, derived by Guo, Shamai and Verdú (first presented in ISIT 2008), to the parallel degraded MIMO scenario. It is shown that the matrix Q(t), which is the difference between the MMSE assuming a Gaussian input and the MMSE assuming an arbitrary input, has, at most, a single crossing point for each of its eigenvalues. Together with the I-MMSE relationship, a fundamental connection between Information Theory and Estimation Theory, this new property is employed to derive results in Information Theory. As a simple application of this property we provide an alternative converse proof for the broadcast channel (BC) capacity region under covariance constraint in this specific setting.

Following the seminal work of Zheng and Tse on the diversity and multiplexing tradeoff (DMT) of MIMO channels, in this paper we introduce the array gain to further investigate the fundamental relation between transmission rate and reliability in MIMO systems. The array gain gives information on the power offset that results from exploiting channel state information at the transmitter or, simply, because of the channel model. Hence, the diversity, multiplexing, and array gain (DMA) tradeoff is able to cope with the limitations of the original DMT and provide with operational meaning in the sense that the DMA tradeoff of a particular system can be directly translated into a parameterized characterization of its associated outage probability performance. As a first step towards this objective, we present in this paper the fundamental DMA tradeoff achievable by any scheme in uncorrelated Rayleigh block-fading MIMO channels.

Using imperfect channel state information (CSI) may cause severe violations of the interference restriction in cognitive radio (CR). We consider designing a robust CR system, over either SISO frequency-selective or MIMO channels, with multiple primary users (PUs) and multiple noncooperative secondary users (SUs), who form an ad-hoc network that is naturally modeled as a noncooperative game. The imperfectness of PU CSI is taken into account through the worst-case robustness philosophy. We study the existence and uniqueness properties of the Nash equilibria (NE) of the robust games, and devise distributed algorithms with their convergency properties to achieve the competitive optimality for the SU network. As special cases, our framework also provides, through convex optimization, the robust power allocation and precoding for each SU.

The computation of the channel capacity of discrete memoryless channels is a convex problem that can be efficiently solved using the Arimoto-Blahut (AB) iterative algorithm. However, the extension of this algorithm to the computation of capacity regions of multiterminal networks is not straightforward since it gives rise to non-convex problems. In this context, the AB algorithm has only been successfully extended to the calculation of the sum-capacity of the discrete memoryless multiple-access channel (DMAC). Thus, the computation of the whole capacity region still requires the use of computationally demanding search methods. In this paper, we first give an alternative reformulation of the capacity region of the DMAC which condenses all the non-convexities of the problem into a single rank-one constraint. Then, we propose efficient methods to compute outer and inner bounds on the capacity region of the two-user DMAC by solving a relaxed version of the problem and projecting its solution onto the original feasible set. Targeting numerical results, we first take a randomization approach. Focusing on analytical results, we study projection via minimum divergence, which amounts to the marginalization of the relaxed solution. In this case we derive sufficient conditions and necessary and sufficient conditions for the bounds to be tight. Furthermore, we are able to show that the class of channels for which the marginalization bounds match exactly the capacity region includes all the two-user binary-input deterministic DMACs as well as other non-deterministic channels. In general, however, both methods are able to compute very tight bounds as shown for various examples.

This paper considers robust transmit strategies, against the imperfectness of CSIT, for MIMO communication systems. Following a deterministic model that assumes the actual channel inside an ellipsoid centered at a nominal channel, we maximize the worst-case received SNR. It is shown that, for a general class of power constraints, the resulting maximin problem can be equivalently transformed into a convex problem, or even further into a semidefinite program. The most important result is that the optimal transmit directions are just the right singular vectors of the nominal channel under some mild conditions. This result reduces the complicated matrix-valued problems to scalar power allocation problems, for which the closed-form solutions are provided.

Consider a downlink communication system where multi-antenna base stations transmit independent data streams to decentralized single-antenna users over a common frequency band. The goal of the base stations is to jointly adjust the beamforming vectors so as to minimize the transmission powers while ensuring the signal-to-interference-noise ratio (SINR) requirement of individual users within the system, and keeping lower interference level to other systems which operate in the same frequency band and in the same region. This optimal beamforming problem is a separable homogeneous quadratically constrained quadratical programming (QCQP), and it is difficult to solve in general. In this paper, we give conditions under which strong duality holds, and propose an efficient algorithm for the optimal beamforming problem. First, we study rank-constrained solutions of a general separable semidefinite programming (SDP), and propose a rank reduction procedure to achieve a lower rank solution. Then we show that the SDP relaxation of a class of the optimal beamforming problem has a rank-one solution, which can be obtained by invoking the rank reduction procedure.

The design of the precoder the maximizes the mutual information in linear vector Gaussian channels with an arbitrary input distribution is studied. Precisely, the precoder optimal left singular vectors and singular values are derived. The characterization of the right singular vectors is left, in general, as an open problem whose computational complexity is then studied in three cases: Gaussian signaling, low SNR, and high SNR. For the Gaussian signaling case and the low SNR regime, the dependence of the mutual information on the right singular vectors vanishes, making the optimal precoder design problem easy to solve. In the high SNR regime, however, the dependence on the right singular vectors cannot be avoided and we show the difficulty of computing the optimal precoder through an NP-hardness analysis.

This paper considers the joint design of bit loading, precoding and receive filters for a multiple-input multiple-output (MIMO) digital communication system employing decision feedback (DF) detection at the receiver. Both the transmitter as well as the receiver are assumed to know the channel matrix perfectly. It is well known that, for linear MIMO transceivers, a diagonal transmission (i.e., orthogonalization of the matrix channel) is optimal for some criteria. Surprisingly, it was shown five years ago that for the family of Schur-convex functions an additional rotation of the symbols is necessary. However, if the bit loading is optimized jointly with the linear transceiver, then the rotation is unnecessary. Similarly, for DF MIMO transceivers, a rotation of the symbols is sometimes needed. The main result of this paper shows that for a DF MIMO transceiver where the bit loading is jointly optimized with the transceiver filters, the rotation of the symbols becomes unnecessary and, consequently, also the DF part of the receiver is not required.

Within the framework of linear vector Gaussian channels with arbitrary signaling, the Jacobian of the minimum mean square error and Fisher information matrices with respect to arbitrary parameters of the system are calculated in this paper. Capitalizing on prior research where the minimum mean square error and Fisher information matrices were linked to information-theoretic quantities through differentiation, the Hessian of the mutual information and the entropy are derived. These expressions are then used to assess the concavity properties of mutual information and entropy under different channel conditions and also to derive a multivariate version of an entropy power inequality due to Costa.

In this paper we focus on the maximization of the information rates subject to transmit power constraints for noncooperative multiple-input multiple-output (MIMO) systems, using the same physical resources, i.e., time, bandwidth and space. To derive decentralized solutions that do not require any cooperation among the systems, the optimization problem is formulated as a static noncooperative game. The analysis of the game for arbitrary MIMO interference channels is quite involved, since it requires the study of a set of nonlinear nondifferentiable matrix-valued equations, based on the MIMO waterfilling solution. To overcome this difficulty, we provide a new interpretation of the waterfilling operator, for the general MIMO multiuser case, as a matrix projection. This key result allows us to simplify the study of the game and to obtain sufficient conditions for both uniqueness of the Nash equilibrium (NE) and convergence of the proposed totally asynchronous distributed algorithms. The proposed approach provides a general framework that encompasses all previous works, mostly concerned with the particular case of SISO Gaussian frequency-selective interference channel.

In this paper we present a general formulation that unifies the probabilistic characterisation of Hermitian random matrices with a specific structure. Based on a unified expression for the joint pdf, we obtain (i) the joint cdf, (ii) the marginal cdf's, and (iii) the marginal pdf's of the ordered eigenvalues, where (ii) and (iii) follow as simple particularizations of (i). Our formulation is shown to include the distribution of some common MIMO channel models such as the uncorrelated and semicorrelated Rayleigh, and the uncorrelated Rician fading MIMO channel, although it is not restricted only to these. Hence, we provide a solid framework for the simultaneous analytical performance analysis of MIMO systems under different channel models. As an example of application, we obtain the exact outage probability of a spatial multiplexing MIMO system transmitting through the strongest channel eigenmodes.

Images encoded at low-bit rate may suffer from blocking artifacts, which can dramatically degrade the visual quality. In this paper, a novel approach to image deblocking is presented. Based on the analysis of image coding process and the property of natural images, an objective function and a set of constraint functions are proposed, and image deblocking is formulated as a convex optimization problem which can be easily solved using numerical methods. The feasibility of the convex optimization problem is utilized to detect the true object edges and avoid blurring. Experimental results demonstrates the effectiveness of the proposed approach.

While the capacity region of the discrete memoryless broadcast channel is in general unknown, it admits a computable single-letter characterization when it is degraded. In this case, we pose its computation as an optimization problem and analyze its structure. We show that the computation of the capacity region of the two-user discrete memoryless degraded broadcast channel can be characterized as a difference of convex optimization problem, a non-convex problem in general. For this problem, which cannot be solved optimally in polynomial time, we obtain necessary conditions for optimality which substantially reduce the set of potential capacity-achieving candidate distributions. As an application of this result, the capacity region of the BEC-BSC degraded broadcast channel is derived by maximizing the achievable rates over this set of reduced dimensionality.

A simple multivariate version of Costapsilas entropy power inequality is proved. In particular, it is shown that if independent white Gaussian noise is added to an arbitrary multivariate signal, the entropy power of the resulting random variable is a multidimensional concave function of the individual variances of the components of the signal. As a side result, we also give an expression for the Hessian matrix of the entropy and entropy power functions with respect to the variances of the signal components, which is an interesting result in its own right.

The 26 papers in this special issue focus on game theory in communication systems. The papers are grouped in four clusters according to their topics: (1) Physical layer models in wireless communications, (2) higher layer and cross-layer issues in wireless communications, (3) wire-line communication networks, and (4) specific topics including peer-to-peer networking, network coding, and network security.

This paper considers the noncooperative maximization of mutual information in the Gaussian interference channel in a fully distributed fashion via game theory. This problem has been studied in a number of papers during the past decade for the case of frequency-selective channels. A variety of conditions guaranteeing the uniqueness of the Nash Equilibrium (NE) and convergence of many different distributed algorithms have been derived. In this paper we provide a unified view of the state-of- the-art results, showing that most of the techniques proposed in the literature to study the game, even though apparently different, can be unified using our recent interpretation of the waterfilling operator as a projection onto a proper polyhedral set. Based on this interpretation, we then provide a mathematical framework, useful to derive a unified set of sufficient conditions guaranteeing the uniqueness of the NE and the global convergence of waterfilling based asynchronous distributed algorithms. The proposed mathematical framework is also instrumental to study the extension of the game to the more general MIMO case, for which only few results are available in the current literature. The resulting algorithm is, similarly to the frequency-selective case, an iterative asynchronous MIMO waterfilling algorithm. The proof of convergence hinges again on the interpretation of the MIMO waterfilling as a matrix projection, which is the natural generalization of our results obtained for the waterfilling mapping in the frequency-selective case.

A popular way to measure the degree of dependence between two random objects is by their mutual information, defined as the divergence between the joint and product-of-marginal distributions. We investigate an alternative measure of dependence: the lautum information defined as the divergence between the product-of-marginal and joint distributions, i.e., swapping the arguments in the definition of mutual information. Some operational characterizations and properties are provided for this alternative measure of information.

This paper considers the maximization of information rates for the Gaussian frequency-selective interference channel, subject to power and spectral mask constraints on each link. To derive decentralized solutions that do not require any cooperation among the users, the optimization problem is formulated as a static noncooperative game of complete information. To achieve the so-called Nash equilibria of the game, we propose a new distributed algorithm called asynchronous iterative water-filling algorithm. In this algorithm, the users update their power spectral density (PSD) in a completely distributed and asynchronous way: some users may update their power allocation more frequently than others and they may even use outdated measurements of the received interference. The proposed algorithm represents a unified framework that encompasses and generalizes all known iterative water-filling algorithms, e.g., sequential and simultaneous versions. The main result of the paper consists of a unified set of conditions that guarantee the global converge of the proposed algorithm to the (unique) Nash equilibrium of the game.

A systematic theory is introduced for finding the derivatives of complex-valued matrix functions with respect to a complex-valued matrix variable and the complex conjugate of this variable. In the framework introduced, the differential of the complex-valued matrix function is used to identify the derivatives of this function. Matrix differentiation results are developed for use in signal processing and communications applications. Several other examples are given.

Linear MIMO transceivers (composed of a linear precoder at the transmitter and a linear equalizer at the receiver) are a low-complexity approach to optimize the spectral efficiency and/or the reliability of the communication, when perfect channel state information is available at both sides of the link. The design of linear transceivers has been extensively studied in the literature with a variety of cost functions. In this paper we focus on the minimum BER design, and show that the common practice of fixing a priori the number of transmitted data symbols per channel use inherently limits the diversity gain of the system. Finally, we propose a minimum BER linear precoding scheme that achieves the full diversity of the MIMO channel.

This paper considers the competitive maximization of information rates in the Gaussian frequency-selective interference channel, subject to global power and spectral mask constraints. We focus on the practical case in which the transmission by the different users contains time and frequency synchronization offsets. We propose a unified framework based on a distributed algorithm called asynchronous iterative waterfilling algorithm. In this algorithm, the users update their power spectral density in a completely distributed and asynchronous way: some users may update their power allocation more frequently than others and they may even use outdated measurements of the received interference. Moreover the users are not required to know time and frequency offsets. Our main contribution is to provide a unified set of convergence conditions for the whole class of algorithms obtained from the asynchronous iterative waterfilling algorithm.

A systematic approach to solve seemingly nonconvex resource allocation problems in wireless cellular networks is studied in this paper. By revealing and exploiting the hidden convexity in the problem formulations, we obtain solutions that can tackle a variety of objective functions, provide robustness to resource allocations such as power, and be obtained often through distributed algorithms. The advantages of such flexibility and robustness are demonstrated through comparisons with the state-of-the-art in recent research literature. First we show how to distributively solve a variety of resource allocation problems in CDMA and interference limited CDMA channels with quality of service constraints, such as meeting minimum queueing delay or energy per bit requirement. Then, for uplink transmission in a CDMA cellular network, we propose an optimal power control scheme with congestion-aware active link protection. In particular, the tradeoff between power expenditure and the protection margin of the SIR-balancing power algorithm is optimized.

The computation of the channel capacity of discrete memoryless channels is a convex problem that can be efficiently solved using the Arimoto-Blahut (AB) iterative algorithm. However, the extension of this algorithm to the computation of capacity regions of multiterminal networks is not straightforward since its computation gives rise to non-convex problems. In this context, the AB algorithm has been only successfully extended to the calculation of the sum-capacity of the discrete memoryless multiple-access channel. However, the computation of the capacity region still requires the use of computationally demanding random search algorithms or brute force (full search) methods. In this paper, we first give an alternative reformulation of the problem that identifies the non-convexity as a rank-one constraint. We then propose an efficient algorithm to compute outer and inner bounds on the capacity region by relaxing the original problem and then by projecting the relaxed solution onto the original space variable via a minimum divergence criterion. There exists a class of channels for which the proposed algorithm can be shown to compute exactly the capacity region. As an illustration, we analyze two particular channels, the binary adder MAC and the binary switching MAC, in detail. In the general case, the algorithm is able to compute very tight bounds as shown by simulation.

A relationship between information theory and estimation theory was recently shown for the Gaussian channel, relating the derivative of mutual information with the minimum mean-square error. This paper generalizes the link between information theory and estimation theory to arbitrary channels, giving representations of the derivative of mutual information as a function of the conditional marginal input distributions given the outputs. We illustrate the use of this representation in the efficient numerical computation of the mutual information achieved by inputs such as specific codes or natural language

In wireless cellular or ad hoc networks where Quality of Service (QoS) is interference-limited, a variety of power control problems can be formulated as nonlinear optimization with a system-wide objective, e.g., maximizing the total system throughput or the worst user throughput, subject to QoS constraints from individual users, e.g., on data rate, delay, and outage probability. We show that in the high Signal-to- interference Ratios (SIR) regime, these nonlinear and apparently difficult, nonconvex optimization problems can be transformed into convex optimization problems in the form of geometric programming; hence they can be very efficiently solved for global optimality even with a large number of users. In the medium to low SIR regime, some of these constrained nonlinear optimization of power control cannot be turned into tractable convex formulations, but a heuristic can be used to compute in most cases the optimal solution by solving a series of geometric programs through the approach of successive convex approximation. While efficient and robust algorithms have been extensively studied for centralized solutions of geometric programs, distributed algorithms have not been explored before. We present a systematic method of distributed algorithms for power control that is geometric-programming-based. These techniques for power control, together with their implications to admission control and pricing in wireless networks, are illustrated through several numerical examples.

In this paper we propose a unified framework, based on the emergent potential games to deal with a variety of network resource allocation problems. We generalize the existing results on potential games to the cases where there exists coupling among the (possibly vector) strategies of all players. We derive sufficient conditions for the existence and uniqueness of the Nash equilibrium, and provide different distributed algorithms along their convergence properties. Using this new framework, we then show that many power control problems (standard and non-standard) with coupled constraints among the users, can be naturally formulated as potential games and, hence, efficiently solved. Finally, we point out an interesting interplay existing between potential games, classical optimization theory, and Lyapunov stability theory

In Network Utility Maximization (NUM) problems, it is generally assumed that user utilities are uncoupled, i.e., each utility depends only on local variables. Then the coupling in constraint functions among users sharing common resources can be decoupled by standard methods such as dual decomposition. However, in problems where cooperation or competition is modeled through the objective function, such as rate allocation in clustered system and power control in interference limited system, each utility may depend not only on its local variables but also on the local variables of other utilities. Applications of this coupled utility model include wireless power control and DSL spectrum management, where the utilities are functions of the Signal-to-Interference Ratios (SIR) that depend on the transmit powers of other users. We present a systematic approach of consistency pricing to decouple NUM problems with coupled utilities, obtaining distributed algorithms that efficiently handle couplings in utilities with two alternative timescales, as well as a method to reduce message passing overhead in the case of interference-based coupling.

This paper considers the robust design of a linear transceiver with imperfect channel state information (CSI) at the transmitter of a MIMO link. The framework embraces the design problem when CSI at the transmitter consists of the channel mean and covariance matrix or, equivalently, the channel estimate and the estimation error covariance matrix. The design of the linear MIMO transceiver is based on a general cost function covering several well known performance criteria. In particular, two families are considered in detail: Schur-convex and Schur-concave functions. Approximations are used in the low SNR and high SNR regimes separately to obtain simple optimization problems that can be readily solved. Numerical examples show gains compared to other suboptimal methods.

Abstract — Network utility maximization (NUM) problems provide an important approach to conduct network resource management such as end-to-end rate allocation. In the existing literature, distributed implementations are typically achieved by the means of the so-called dual decomposition technique. However, the span of decomposition possibilities includes many other elements which thus far have not been fully exploited such as the use of the primal decomposition technique, the versatile introduction of auxiliary variables, and the potential of multilevel decompositions. This paper presents a systematic framework to exploit the potential of the alternative decomposition structures as a way to obtain different distributed algorithms, each with a different tradeoff among convergence speed, message passing amount and asymmetry, and distributed computation architecture. Many specific applications are considered to illustrate the proposed framework, including resource-constrained and directcontrol rate allocation, and rate allocation among QoS classes and with multipath routing. For each of these applications, the associated generalized NUM formulation is first presented, followed by the development of novel alternative decompositions and numerical experiments on the resulting new distributed algorithms.

The sequential iterative water-filling algorithm (IWFA) proposed by Yu et al. is by now a popular low-complexity algorithm to compute the Nash equilibrium point of the power allocation game in a Gaussian frequency-selective multiuser interference channel. The algorithm is based on a distributed sequential updating where, at each iteration, the users choose their power allocation, one after the other. However, this sequential updating strategy may slow down its convergence time excessively when the number of users is high. In this paper, we propose an alternative distributed algorithm, called simultaneous iterative water-filling algorithm (SIWFA), where at each iteration, all the users update their power allocations simultaneously, rather than sequentially. This reduces the convergence time considerably, specially when the number of users is large. Our main contribution is to provide a unified set of sufficient conditions for the convergence of both IWFA and SIWFA, that are less stringent than those known in the literature for IWFA. These conditions guarantee the convergence of both algorithms also in the presence of spectral mask constraints imposed on the power allocations of the users

A popular way to measure the degree of dependence between two random variables is with mutual information, defined as the divergence between the joint and product-of- marginal distributions. We introduce an alternative measure of dependence we refer to as lautum information: the divergence between the product-of-marginal and joint distributions. Some operational characterizations and properties are provided for this alternative measure of information.

A systematic understanding of the decomposability structures in network utility maximization is key to both resource allocation and functionality allocation. It helps us obtain the most appropriate distributed algorithm for a given network resource allocation problem, and quantifies the comparison across architectural alternatives of modularized network design. Decomposition theory naturally provides the mathematical language to build an analytic foundation for the design of modularized and distributed control of networks. In this tutorial paper, we first review the basics of convexity, Lagrange duality, distributed subgradient method, Jacobi and Gauss-Seidel iterations, and implication of different time scales of variable updates. Then, we introduce primal, dual, indirect, partial, and hierarchical decompositions, focusing on network utility maximization problem formulations and the meanings of primal and dual decompositions in terms of network architectures. Finally, we present recent examples on: systematic search for alternative decompositions; decoupling techniques for coupled objective functions; and decoupling techniques for coupled constraint sets that are not readily decomposable.

This paper considers a general linear vector Gaussian channel with arbitrary signaling and pursues two closely related goals: i) closed-form expressions for the gradient of the mutual information with respect to arbitrary parameters of the system, and ii) fundamental connections between information theory and estimation theory. Generalizing the fundamental relationship recently unveiled by Guo, Shamai, and Verdu/spl acute/, we show that the gradient of the mutual information with respect to the channel matrix is equal to the product of the channel matrix and the error covariance matrix of the best estimate of the input given the output. Gradients and derivatives with respect to other parameters are then found via the differentiation chain rule.

Network utility maximization problems provide an important approach to conduct network resource management such as power and rate allocation. In the existing literature, distributed implementations are typically achieved by the means of the so-called dual decomposition technique. However, the span of decomposition possibilities includes many other elements which thus far have not been fully exploited, such as the use of the primal decomposition technique, the versatile introduction of auxiliary variables, and the potential of multilevel decompositions. This paper presents in a systematic way how to apply these decomposition techniques to network utility maximization problems. The presentation is based on a general network optimization model that unifies existing works, and then is particularized to two concrete examples of recent interest: generalized water-filling algorithms and wireless cellular downlink power control. We can thus obtain a variety of distributed algorithms with different characteristics to suit the needs of specific applications. Both primal and dual decomposition techniques are considered at many different hierarchy levels, leading to a range of choices of hybrid, multi-level, primal/dual decomposition schemes. Each particular combination provides a different distributed algorithm for resource allocation. The choice of decomposition method and distributed algorithm for a particular problem depends on factors such as the amount of signalling required for proper coordination, asymmetry of computational load, and speed of convergence.

In wireless cellular networks that are interference-limited, a variety of power control problems can be formulated as nonlinear optimization with a system-wide objective subject to many QoS constraints from individual users. Previous work have been done in the high SIR regime by solving these problems with nonlinear objectives and constraints as geometric programs. However, in the medium to low SIR regime, these problems cannot be transformed into tractable convex optimization problems. This paper makes two contributions: (1) In the low SIR regime, we propose a method with centralized computation to obtain the globally optimal solution by solving a series of geometric programs. (2) While efficient and robust algorithms have been extensively studied for centralized solutions of geometric programs, distributed algorithms have not been investigated before this paper. We present a systematic method of distributed algorithms for power control based on geometric programs in high SIR regime. These two contributions can be readily combined to distributively solve nonlinear power control problems in general SIR regime

This paper considers a general linear vector Gaussian channel with arbitrary signaling and pursues two closely related goals: i) closed-form expressions for the gradient of the mutual information with respect to arbitrary parameters of the system, and ii) fundamental connections between information theory and estimation theory. Generalizing the fundamental relationship recently unveiled by Guo, Shamai, and Verdu, we show that the gradient of the mutual information with respect to the channel matrix is equal to the product of the channel matrix and the error covariance matrix of the estimate of the input given the output

Network Utility Maximization (NUM) has significantly extended the classical network flow problem and provided an emerging framework to design resource allocation algorithms such as TCP congestion control and to understand layering as optimization decomposition. We present a summary of very recent results in the theory and applications of NUM. We show new distributed algorithms that converge to the globally optimal rate allocation for NUM problems with nonconcave utility functions representing inelastic flows, with coupled utility functions representing interference effects or hybrid social-selfish utilities, and with rate-reliability tradeoff through adaptive channel coding in the physical layer. We conclude by discussing how do different decompositions of a generalized NUM problem correspond to different layering architectures.

This paper addresses the joint design of transmit and receive beamvectors for a multicarrier MIMO channel within the general and powerful framework of convex optimization theory. From this perspective, a great span of design criteria can be easily accommodated and efficiently solved even though closed-form expressions may not be available. Among other criteria, we consider the minimization of the average bit error rate (BER) and also of the maximum BER among all carriers for a given signal constellation. We show how to include additional constraints to control the peak-to-average ratio (PAR) in the system design.

Multi-input multi-output (MIMO) channels have been shown in the literature to present a significant capacity increase over single-input single-output ones in some situations. To achieve this theoretical capacity, the constituent parallel subchannels arising from the MIMO channel have to be properly used. Many practical schemes are being currently developed to achieve this goal. We first show that, from an information-theoretic point of view, beamforming becomes asymptotically optimal as the spatial correlation of the channel fading increases. In light of this result, wideband beamvectors are jointly derived for both transmission and reception. We allow a controlled partial response and design zero-forcing and minimum mean-squared error transmit-receive filters. Conceptually, the beamforming scheme is shown to decompose into two stages: the first one corresponds to a spatial flattening of the MIMO channel, i.e., choosing the subchannel with the highest gain at each frequency; the second stage depends on the particular design criterion and performs a power distribution at the transmitter and defines the equalizer at the receiver. These methods are further extended to the general case of multiple beamforming, i.e., when more than one subchannel are used. An exact and practical implementation of a modified "waterfilling" solution required for the filter design is proposed. All derived methods are assessed and compared in terms of capacity and bit-error rate.

When transmitting over multiple-input-multiple-output (MIMO) channels, there are additional degrees of freedom with respect to single-input-single-output (SISO) channels: the distribution of the available power over the transmit dimensions. If channel state information (CSI) is available, the optimum solution is well known and is based on diagonalizing the channel matrix and then distributing the power over the channel eigenmodes in a "water-filling" fashion. When CSI is not available at the transmitter, but the channel statistics are a priori known, an optimal fixed power allocation can be precomputed. This paper considers the case in which not even the channel statistics are available, obtaining a robust solution under channel uncertainty by formulating the problem within a game-theoretic framework. The payoff function of the game is the mutual information and the players are the transmitter and a malicious nature. The problem turns out to be the characterization of the capacity of a compound channel which is mathematically formulated as a maximin problem. The uniform power allocation is obtained as a robust solution (under a mild isotropy condition). The loss incurred by the uniform distribution is assessed using the duality gap concept from convex optimization theory. Interestingly, the robustness of the uniform power allocation also holds for the more general case of the multiple-access channel.

Multi-input multi-output (MIMO) channels arising from the use of multi-element antenna (MEA) systems both in transmission and reception have been shown to support a considerable amount of bit rate. The information-theoretic capacity of such channels is severely affected by the spatial correlation. In this paper, we evaluate the ergodic and outage capacity of typical MIMO channels appearing in UMTS indoor scenarios. The frequency-selectivity and the spatial correlation of the MIMO channel are taken into account using realistic models obtained from field measurements performed within the IST project METRA (http://www.ist-metra.org). For capacity assessment, we use the transmission schemes considered by the 3GPP for UMTS. In particular, we analyze the cases of having and not having channel state information (CSI) at the transmitter, and also the case in which beamforming is used for transmission.

A self-reference beamforming algorithm, based on the inherent temporal redundancy structure presented by the spreading codes of direct sequence code division multiple access (DS-CDMA) systems, is proposed. It is derived from a novel perspective of chip level cross-correlation properties. The algorithm is shown to give the optimal solution in the sense of maximum signal to interference plus noise ratio (SINR). Block and adaptive approaches to solve the problem are given. The method is tested against the well-known temporal reference beamformer (TRB) combined with a decision-directed approach, showing a performance similar to it, despite no side information is being used.