Search

Rate splitting multiple access (RSMA) is a promising non-orthogonal transmission strategy for next-generation wireless networks. It has been shown to outperform existing multiple access schemes in terms of spectral and energy efficiency when suboptimal beamforming schemes are employed. In this work, we fill the gap between suboptimal and truly optimal beamforming schemes and conclusively establish the superior spectral and energy efficiency of RSMA. To this end, we propose a successive incumbent transcending (SIT) branch and bound (BB) algorithm to find globally optimal beamforming solutions that maximize the weighted sum rate or energy efficiency of RSMA in Gaussian multiple-input single-output (MISO) broadcast channels. Numerical results show that RSMA exhibits an explicit globally optimal spectral and energy efficiency gain over conventional multi-user linear precoding (MU-LP) and power-domain non-orthogonal multiple access (NOMA). Compared to existing globally optimal beamforming algorithms for MU-LP, the proposed SIT BB not only improves the numerical stability but also achieves faster convergence. Moreover, for the first time, we show that the spectral/energy efficiency of RSMA achieved by suboptimal beamforming schemes (including weighted minimum mean squared error (WMMSE) and successive convex approximation) almost coincides with the corresponding globally optimal performance, making it a valid choice for performance comparisons. The globally optimal results provided in this work are imperative to the ongoing research on RSMA as they serve as benchmarks for existing suboptimal beamforming strategies and those to be developed in multi-antenna broadcast channels.

We consider the problem of maximizing the $\ell_1$ norm of a linear map over the sphere, which arises in various machine learning applications such as orthogonal dictionary learning (ODL) and robust subspace recovery (RSR). The problem is numerically challenging due to its nonsmooth objective and nonconvex constraint, and its algorithmic aspects have not been well explored. In this paper, we show how the manifold structure of the sphere can be exploited to design fast algorithms for tackling this problem. Specifically, our contribution is threefold. First, we present a manifold proximal point algorithm (ManPPA) for the problem and show that it converges at a sublinear rate. Furthermore, we show that ManPPA can achieve a quadratic convergence rate when applied to the ODL and RSR problems. Second, we propose a stochastic variant of ManPPA called StManPPA, which is well suited for large-scale computation, and establish its sublinear convergence rate. Both ManPPA and StManPPA have provably faster convergence rates than existing subgradient-type methods. Third, using ManPPA as a building block, we propose a new approach to solving a matrix analog of the problem, in which the sphere is replaced by the Stiefel manifold. The results from our extensive numerical experiments on the ODL and RSR problems demonstrate the efficiency and efficacy of our proposed methods., Comment: Accepted in IEEE Transactions on Signal Processing

We consider stochastic optimization of a smooth non-convex loss function with a convex non-smooth regularizer. In the online setting, where a single sample of the stochastic gradient of the loss is available at every iteration, the problem can be solved using the proximal stochastic gradient descent (SGD) algorithm and its variants. However in many problems, especially those arising in communications and signal processing, information beyond the stochastic gradient may be available thanks to the structure of the loss function. Such extra-gradient information is not used by SGD, but has been shown to be useful, for instance in the context of stochastic expectation-maximization, stochastic majorization-minimization, and stochastic successive convex approximation (SCA) approaches. By constructing a stochastic strongly convex surrogates of the loss function at every iteration, the stochastic SCA algorithms can exploit the structural properties of the loss function and achieve superior empirical performance as compared to the SGD. In this work, we take a closer look at the stochastic SCA algorithm and develop its asynchronous variant which can be used for resource allocation in wireless networks. While the stochastic SCA algorithm is known to converge asymptotically, its iteration complexity has not been well-studied, and is the focus of the current work. The insights obtained from the non-asymptotic analysis allow us to develop a more practical asynchronous variant of the stochastic SCA algorithm which allows the use of surrogates calculated in earlier iterations. We characterize precise bound on the maximum delay the algorithm can tolerate, while still achieving the same convergence rate. We apply the algorithm to the problem of linear precoding in wireless sensor networks, where it can be implemented at low complexity but is shown to perform well in practice.

In this paper, we study decentralized online stochastic non-convex optimization over a network of nodes. Integrating a technique called gradient tracking in decentralized stochastic gradient descent, we show that the resulting algorithm, GT-DSGD , enjoys certain desirable characteristics towards minimizing a sum of smooth non-convex functions. In particular, for general smooth non-convex functions, we establish non-asymptotic characterizations of GT-DSGD and derive the conditions under which it achieves network-independent performances that match the centralized minibatch SGD . In contrast, the existing results suggest that GT-DSGD is always network-dependent and is therefore strictly worse than the centralized minibatch SGD . When the global non-convex function additionally satisfies the Polyak-Łojasiewics (PL) condition, we establish the linear convergence of GT-DSGD up to a steady-state error with appropriate constant step-sizes. Moreover, under stochastic approximation step-sizes, we establish, for the first time, the optimal global sublinear convergence rate on almost every sample path, in addition to the asymptotically optimal sublinear rate in expectation. Since strongly convex functions are a special case of the functions satisfying the PL condition, our results are not only immediately applicable but also improve the currently known best convergence rates and their dependence on problem parameters.

The dictionary learning problem concerns the task of representing data as sparse linear sums drawn from a smaller collection of basic building blocks. In application domains where such techniques are deployed, we frequently encounter datasets where some form of symmetry or invariance is present. Motivated by this observation, we develop a framework for learning dictionaries for data under the constraint that the collection of basic building blocks remains invariant under such symmetries. Our procedure for learning such dictionaries relies on representing the symmetry as the action of a matrix group acting on the data, and subsequently introducing a convex penalty function so as to induce sparsity with respect to the collection of matrix group elements. Our framework specializes to the convolutional dictionary learning problem when we consider integer shifts. Using properties of positive semidefinite Hermitian Toeplitz matrices, we develop an extension that learns dictionaries that are invariant under continuous shifts. Our numerical experiments on synthetic data and ECG data show that the incorporation of such symmetries as priors are most valuable when the dataset has few data-points, or when the full range of symmetries is inadequately expressed in the dataset., Comment: 30 pages, 23 figures

While globally optimal solutions to many convex programs can be computed efficiently in polynomial time, this is, in general, not possible for nonconvex optimization problems. Therefore, locally optimal approaches or other efficient suboptimal heuristics are usually applied for practical implementations. However, there is also a strong interest in computing globally optimal solutions of nonconvex problems in offline simulations in order to benchmark the faster suboptimal algorithms. Global solutions often rely on monotonicity properties. A common approach is to reformulate problems into a canonical monotonic optimization problem where the monotonicity becomes evident, but this often comes at the cost of nested optimizations, increased numbers of variables, and/or slow convergence. The framework of mixed monotonic programming (MMP) proposed in this paper avoids such performance-deteriorating reformulations by revealing hidden monotonicity properties directly in the original problem formulation. By means of a wide range of application examples from the area of signal processing for communications (including energy efficiency for green communications, resource allocation in interference networks, scheduling for fairness and quality of service, as well as beamformer design in multiantenna systems), we demonstrate that the novel MMP approach leads to tremendous complexity reductions compared to state-of-the-art methods for global optimization. However, the framework is not limited to optimizing communication systems, and we expect that similar speed-ups can be obtained for optimization problems from other areas of research as well., Comment: submitted to IEEE Transactions on Signal Processing; Source code available at https://github.com/bmatthiesen/mixed-monotonic

We address the problem of linear precoder (beamformer) design in a multiple-input multiple-output interference channel (MIMO-IC). The aim is to design the transmit covariance matrices in order to achieve max-min utility fairness for all users. The corresponding optimization problem is non-convex and NP-hard in general. We devise an efficient algorithm based on the minorization-maximization (MM) technique to obtain quality solutions to this problem. The proposed method solves a second-order cone convex program (SOCP) at each iteration. We prove that the devised method converges to stationary points of the problem. We also extend our algorithm to the case where there are uncertainties in the noise covariance matrices or channel state information (CSI). Simulation results show the effectiveness of the proposed method compared with its main competitor.

The autoregressive (AR) model is a widely used model to understand time series data. Traditionally, the innovation noise of the AR is modeled as Gaussian. However, many time series applications, for example, financial time series data, are non-Gaussian, therefore, the AR model with more general heavy-tailed innovations is preferred. Another issue that frequently occurs in time series is missing values, due to system data record failure or unexpected data loss. Although there are numerous works about Gaussian AR time series with missing values, as far as we know, there does not exist any work addressing the issue of missing data for the heavy-tailed AR model. In this paper, we consider this issue for the first time, and propose an efficient framework for parameter estimation from incomplete heavy-tailed time series based on a stochastic approximation expectation maximization (SAEM) coupled with a Markov Chain Monte Carlo (MCMC) procedure. The proposed algorithm is computationally cheap and easy to implement. The convergence of the proposed algorithm to a stationary point of the observed data likelihood is rigorously proved. Extensive simulations and real datasets analyses demonstrate the efficacy of the proposed framework., Comment: This is a companion document to a paper that is accepted to IEEE Transaction on Signal Processing 2019, complemented with the supplementary material

We consider the problem of approximating optimal in the Minimum Mean Squared Error (MMSE) sense nonlinear filters in a discrete time setting, exploiting properties of stochastically convergent state process approximations. More specifically, we consider a class of nonlinear, partially observable stochastic systems, comprised by a (possibly nonstationary) hidden stochastic process (the state), observed through another conditionally Gaussian stochastic process (the observations). Under general assumptions, we show that, given an approximating process which, for each time step, is stochastically convergent to the state process, an approximate filtering operator can be defined, which converges to the true optimal nonlinear filter of the state in a strong and well defined sense. In particular, the convergence is compact in time and uniform in a completely characterized measurable set of probability measure almost unity, also providing a purely quantitative justification of Egoroff's Theorem for the problem at hand. The results presented in this paper can form a common basis for the analysis and characterization of a number of heuristic approaches for approximating optimal nonlinear filters, such as approximate grid based techniques, known to perform well in a variety of applications., EXTENDED version of an original paper published in the IEEE Transactions on Signal Processing; 37 pages

We propose a distributed algorithm for solving the optimization problem Basis Pursuit (BP). BP finds the least L1-norm solution of the underdetermined linear system Ax = b and is used, for example, in compressed sensing for reconstruction. Our algorithm solves BP on a distributed platform such as a sensor network, and is designed to minimize the communication between nodes. The algorithm only requires the network to be connected, has no notion of a central processing node, and no node has access to the entire matrix A at any time. We consider two scenarios in which either the columns or the rows of A are distributed among the compute nodes. Our algorithm, named D-ADMM, is a decentralized implementation of the alternating direction method of multipliers. We show through numerical simulation that our algorithm requires considerably less communications between the nodes than the state-of-the-art algorithms., Preprint of the journal version of the paper; IEEE Transactions on Signal Processing, Vol. 60, Issue 4, April, 2012

Compressed sensing aims at reconstructing sparse signals from significantly reduced number of samples, and a popular reconstruction approach is $\ell_1$-norm minimization. In this correspondence, a method called orthonormal expansion is presented to reformulate the basis pursuit problem for noiseless compressed sensing. Two algorithms are proposed based on convex optimization: one exactly solves the problem and the other is a relaxed version of the first one. The latter can be considered as a modified iterative soft thresholding algorithm and is easy to implement. Numerical simulation shows that, in dealing with noise-free measurements of sparse signals, the relaxed version is accurate, fast and competitive to the recent state-of-the-art algorithms. Its practical application is demonstrated in a more general case where signals of interest are approximately sparse and measurements are contaminated with noise., 7 pages, 2 figures, 1 table

Coping with outliers contaminating dynamical processes is of major importance in various applications because mismatches from nominal models are not uncommon in practice. In this context, the present paper develops novel fixed-lag and fixed-interval smoothing algorithms that are robust to outliers simultaneously present in the measurements {\it and} in the state dynamics. Outliers are handled through auxiliary unknown variables that are jointly estimated along with the state based on the least-squares criterion that is regularized with the $\ell_1$-norm of the outliers in order to effect sparsity control. The resultant iterative estimators rely on coordinate descent and the alternating direction method of multipliers, are expressed in closed form per iteration, and are provably convergent. Additional attractive features of the novel doubly robust smoother include: i) ability to handle both types of outliers; ii) universality to unknown nominal noise and outlier distributions; iii) flexibility to encompass maximum a posteriori optimal estimators with reliable performance under nominal conditions; and iv) improved performance relative to competing alternatives at comparable complexity, as corroborated via simulated tests., Comment: Submitted to IEEE Trans. on Signal Processing

Takens' Embedding Theorem remarkably established that concatenating M previous outputs of a dynamical system into a vector (called a delay coordinate map) can be a one-to-one mapping of a low-dimensional attractor from the system state space. However, Takens' theorem is fragile in the sense that even small imperfections can induce arbitrarily large errors in this attractor representation. We extend Takens' result to establish deterministic, explicit and non-asymptotic sufficient conditions for a delay coordinate map to form a stable embedding in the restricted case of linear dynamical systems and observation functions. Our work is inspired by the field of Compressive Sensing (CS), where results guarantee that low-dimensional signal families can be robustly reconstructed if they are stably embedded by a measurement operator. However, in contrast to typical CS results, i) our sufficient conditions are independent of the size of the ambient state space, and ii) some system and measurement pairs have fundamental limits on the conditioning of the embedding (i.e., how close it is to an isometry), meaning that further measurements beyond some point add no further significant value. We use several simple simulations to explore the conditions of the main results, including the tightness of the bounds and the convergence speed of the stable embedding. We also present an example task of estimating the attractor dimension from time-series data to highlight the value of stable embeddings over traditional Takens' embeddings.

This paper considers the weighted sum rate (WSR) maximized resource allocation (RA) constrained by a system sum power in an orthogonal frequency division multiple access (OFDMA) downlink transmission system assisted by multiple decode-and-forward (DF) relays. In particular, multiple relays may cooperate with the source for every relay-aided transmission. A two-step algorithm is proposed to find the globally optimum RA. In the first step, the optimum source/relay power and assisting relays that maximize the rate is found for every combination of subcarrier and destination, assuming a sum power is allocated to the transmission at that subcarrier to that destination in the relay-aided transmission mode and the direct mode, respectively. In the second step, a convex-optimization based algorithm is designed to find the globally optimum assignment of destination, transmission mode, and sum power for each subcarrier to maximize the WSR. Combining the RAs found in the two steps, the globally optimum RA can be found. In addition, we show that the optimum RA in the second step can readily be derived when the system sum power is very high. The effectiveness of the proposed algorithm is illustrated by numerical experiments., 13 pages and 14 figures, to appear in IEEE Transactions Signal Processing

We show that the sensor self-localization problem can be cast as a static parameter estimation problem for Hidden Markov Models and we implement fully decentralized versions of the Recursive Maximum Likelihood and on-line Expectation-Maximization algorithms to localize the sensor network simultaneously with target tracking. For linear Gaussian models, our algorithms can be implemented exactly using a distributed version of the Kalman filter and a novel message passing algorithm. The latter allows each node to compute the local derivatives of the likelihood or the sufficient statistics needed for Expectation-Maximization. In the non-linear case, a solution based on local linearization in the spirit of the Extended Kalman Filter is proposed. In numerical examples we demonstrate that the developed algorithms are able to learn the localization parameters., Comment: shorter version is about to appear in IEEE Transactions of Signal Processing; 22 pages, 15 figures