This paper gives an overview of the majorization-minimization (MM) algorithmic framework, which can provide guidance in deriving problem-driven algorithms with low computational cost. A general ...introduction of MM is presented, including a description of the basic principle and its convergence results. The extensions, acceleration schemes, and connection to other algorithmic frameworks are also covered. To bridge the gap between theory and practice, upperbounds for a large number of basic functions, derived based on the Taylor expansion, convexity, and special inequalities, are provided as ingredients for constructing surrogate functions. With the pre-requisites established, the way of applying MM to solving specific problems is elaborated by a wide range of applications in signal processing, communications, and machine learning.
Sequences with low aperiodic autocorrelation sidelobes are well known to have extensive applications in active sensing and communication systems. In this paper, we first consider the problem of ...minimizing the weighted integrated sidelobe level (WISL), which can be used to design sequences with impulse-like autocorrelation and a zero (or low) correlation zone. Two algorithms based on the general majorization-minimization method are developed to tackle the WISL minimization problem with guaranteed convergence to a stationary point. The proposed methods are then extended to optimize the lp-norm of the autocorrelation sidelobes, which leads to a way to minimize the peak sidelobe level (PSL) criterion. All the proposed algorithms can be implemented via the fast Fourier transform (FFT) and thus are computationally efficient. An acceleration scheme is considered to further accelerate the algorithms. Numerical experiments show that the proposed algorithms can efficiently generate sequences with virtually zero autocorrelation sidelobes in a specified lag interval and can also produce very long sequences with much smaller PSL compared with some well known analytical sequences.
Real and Complex Monotone Communication Games Scutari, Gesualdo; Facchinei, Francisco; Pang, Jong-Shi ...
IEEE transactions on information theory,
07/2014, Letnik:
60, Številka:
7
Journal Article, Conference Proceeding
Recenzirano
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.
Network utility maximization (NUM) problem formulations provide an important approach to conduct network resource allocation and to view layering as optimization decomposition. In the existing ...literature, distributed implementations are typically achieved by means of the so-called dual decomposition technique. However, the span of decomposition possibilities includes many other elements that, 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 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. Several specific applications are considered to illustrate the proposed framework, including resource-constrained and direct-control rate allocation, and rate allocation among QoS classes 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. A systematic enumeration and comparison of alternative vertical decompositions in the future will help complete a mathematical theory of network architectures.
A highly popular regularized (shrinkage) covariance matrix estimator is the shrinkage sample covariance matrix (SCM) which shares the same set of eigenvectors as the SCM but shrinks its eigenvalues ...toward the grand mean of the eigenvalues of the SCM. 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, Tyler's, or <inline-formula><tex-math notation="LaTeX">t</tex-math></inline-formula> 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 an unspecified heavy-tailed elliptically symmetric distribution. Also, real-world and synthetic stock market data validate the performance of the proposed method in practical applications.
Consider a downlink communication system where multiantenna 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 to minimize the transmission powers while ensuring the signal-to-interference-noise ratio requirement of each user within the system. At the same time, it may be necessary to keep the interference generated on other coexisting systems under a certain tolerable level. In addition, one may want to include general individual shaping constraints on the beamforming vectors. This beamforming problem is a separable homogeneous quadratically constrained quadratic program, and it is difficult to solve in general. In this paper, we give conditions under which strong duality holds and propose efficient algorithms for the optimal beamforming problem. First, we study rank-constrained solutions of general separable semidefinite programs (SDPs) and propose rank reduction procedures to achieve a lower rank solution. Then we show that the SDP relaxation of three classes of optimal beamforming problem always has a rank-one solution, which can be obtained by invoking the rank reduction procedures.
Sets of sequences with good correlation properties are desired in many active sensing and communication systems, e.g., multiple-input-multiple-output (MIMO) radar systems and code-division ...multiple-access (CDMA) cellular systems. In this paper, we consider the problems of designing complementary sets of sequences (CSS) and also sequence sets with both good auto- and cross-correlation properties. Algorithms based on the general majorization-minimization method are developed to tackle the optimization problems arising from the sequence set design problems. All the proposed algorithms can be implemented by means of the fast Fourier transform (FFT) and thus are computationally efficient and capable of designing sets of very long sequences. A number of numerical examples are provided to demonstrate the performance of the proposed algorithms.
This paper proposes a framework for optimizing cost functions of orthonormal basis learning problems, such as principal component analysis (PCA), subspace recovery, orthogonal dictionary learning, ...etc. The optimization algorithm is derived using the majorization-minimization framework in conjunction with orthogonal projection reformulations to deal with the orthonormality constraint in a systematic manner. In this scope, we derive surrogate functions for various standard objectives that can then be used as building blocks, with examples for robust learning costs and sparsity enforcing penalties. To illustrate this point, we propose a new set of algorithms for sparse PCA driven by this methodology, whose objective function is composed of an <inline-formula><tex-math notation="LaTeX">M</tex-math></inline-formula>-estimation type subspace fitting term plus a regularizer that promotes sparsity. Simulations and experiments on real data illustrate the interest of the proposed approach, both in terms of performance and computational complexity.
The treatment of channel state information (CSI) is critical in the design of MIMO systems. Accurate CSI at the transmitter is often not possible or may require high feedback rates. Herein, we ...consider the robust design of linear MIMO transceivers with perfect CSI either at the transmitter or at both sides of the link. The framework considers the design problem where the imperfect CSI consists of the channel mean and covariance matrix or, equivalently, the channel estimate and the estimation error covariance matrix. The robust transceiver design is based on a general cost function of the average MSEs as well as a design with individual MSE based constraints. In particular, a lower bound of the average MSE matrix is explored for the design when only the CSI at the transmitter is imperfect. Under different CSI conditions, the proposed robust transceivers exhibit a similar structure to the transceiver designs for perfect CSI, but with a different equivalent channel and/or noise covariance matrix.
The first moment and second central moments of the portfolio return, a.k.a. mean and variance, have been widely employed to assess the expected profit and risk of the portfolio. Investors pursue ...higher mean and lower variance when designing the portfolios. The two moments can well describe the distribution of the portfolio return when it follows the Gaussian distribution. However, the real world distribution of assets return is usually asymmetric and heavy-tailed, which is far from being a Gaussian distribution. The asymmetry and the heavy-tailedness are characterized by the third and fourth central moments, i.e., skewness and kurtosis, respectively. Higher skewness and lower kurtosis are preferred to reduce the probability of extreme losses. However, incorporating high-order moments in the portfolio design is very difficult due to their non-convexity and rapidly increasing computational cost with the dimension. In this paper, we propose a very efficient and convergence-provable algorithm framework based on the successive convex approximation (SCA) algorithm to solve high-order portfolios. The efficiency of the proposed algorithm framework is demonstrated by the numerical experiments.
PDF
