Search

Many recent applications in machine learning and data fitting call for the algorithmic solution of structured smooth convex optimization problems. Although the gradient descent method is a natural choice for this task, it requires exact gradient computations and hence can be inefficient when the problem size is large or the gradient is difficult to evaluate. Therefore, there has been much interest in inexact gradient methods (IGMs), in which an efficiently computable approximate gradient is used to perform the update in each iteration. Currently, non-asymptotic linear convergence results for IGMs are typically established under the assumption that the objective function is strongly convex, which is not satisfied in many applications of interest; while linear convergence results that do not require the strong convexity assumption are usually asymptotic in nature. In this paper, we combine the best of these two types of results and establish---under the standard assumption that the gradient approximation errors decrease linearly to zero---the non-asymptotic linear convergence of IGMs when applied to a class of structured convex optimization problems. Such a class covers settings where the objective function is not necessarily strongly convex and includes the least squares and logistic regression problems. We believe that our techniques will find further applications in the non-asymptotic convergence analysis of other first-order methods.

Consider transceiver designs in a multiuser multi-input single-output (MISO) downlink channel, where the users are to receive the same data stream simultaneously. This problem, known as physical-layer multicasting, has drawn much interest. Presently, a popularized approach is transmit beamforming, in which the beamforming optimization is handled by a rank-one approximation method called semidefinite relaxation (SDR). SDR-based beamforming has been shown to be promising for a small or moderate number of users. This paper describes two new transceiver strategies for physical-layer multicasting. The first strategy, called stochastic beamforming (SBF), randomizes the beamformer in a per-symbol time-varying manner, so that the rank-one approximation in SDR can be bypassed. We propose several efficiently realizable SBF schemes, and prove that their multicast achievable rate gaps with respect to the MISO multicast capacity must be no worse than 0.8314 bits/s/Hz, irrespective of any other factors such as the number of users. The use of channel coding and the assumption of sufficiently long code lengths play a crucial role in achieving the above result. The second strategy combines transmit beamforming and the Alamouti space-time code. The result is a rank-two generalization of SDR-based beamforming. We show by analysis that this SDR-based beamformed Alamouti scheme has a better worst-case effective signal-to-noise ratio (SNR) scaling, and hence a better multicast rate scaling, than SDR-based beamforming. We further the work by combining SBF and the beamformed Alamouti scheme, wherein an improved constant rate gap of 0.39 bits/s/Hz is proven. Simulation results show that under a channel-coded, many-user setting, the proposed multicast transceiver schemes yield significant SNR gains over SDR-based beamforming at the same bit error rate level., Comment: To appear in IEEE Transactions on Signal Processing

This is a companion technical report of the main manuscript "Physical-Layer Multicasting by Stochastic Transmit Beamforming and Alamouti Space-Time Coding". The report serves to give detailed derivations of the achievable rate functions encountered in the main manuscript, which are too long to be included in the latter. In addition, more simulation results are presented to verify the viability of the multicast schemes developed in the main manuscript., Comment: Technical Report, Department of Electronic Engineering, the Chinese University of Hong Kong, 13 pages, 6 figures

In this paper, we establish hardness and approximation results for various $L_p$-ball constrained homogeneous polynomial optimization problems, where $p \in [2,\infty]$. Specifically, we prove that for any given $d \ge 3$ and $p \in [2,\infty]$, both the problem of optimizing a degree-$d$ homogeneous polynomial over the $L_p$-ball and the problem of optimizing a degree-$d$ multilinear form (regardless of its super-symmetry) over $L_p$-balls are NP-hard. On the other hand, we show that these problems can be approximated to within a factor of $\Omega((\log n)^{(d-2)/p} \big/ n^{d/2-1})$ in deterministic polynomial time, where $n$ is the number of variables. We further show that with the help of randomization, the approximation guarantee can be improved to $\Omega((\log n/n)^{d/2-1})$, which is independent of $p$ and is currently the best for the aforementioned problems. Our results unify and generalize those in the literature, which focus either on the quadratic case or the case where $p \in {2,\infty}$. We believe that the wide array of tools used in this paper will have further applications in the study of polynomial optimization problems., Comment: 37 pages

In this paper, we establish the following perturbation result concerning the singular values of a matrix: Let $A,B \in \mathbb{R}^{m\times n}$ be given matrices, and let $f:\mathbb{R}_+\rightarrow\mathbb{R}_+$ be a concave function satisfying $f(0)=0$. Then, we have $$ \sum_{i=1}^{\min\{m,n\}} \big| f(\sigma_i(A)) - f(\sigma_i(B)) \big| \le \sum_{i=1}^{\min\{m,n\}} f(\sigma_i(A-B)), $$ where $\sigma_i(\cdot)$ denotes the $i$--th largest singular value of a matrix. This answers an open question that is of interest to both the compressive sensing and linear algebra communities. In particular, by taking $f(\cdot)=(\cdot)^p$ for any $p \in (0,1]$, we obtain a perturbation inequality for the so--called Schatten $p$--quasi--norm, which allows us to confirm the validity of a number of previously conjectured conditions for the recovery of low--rank matrices via the popular Schatten $p$--quasi--norm heuristic. We believe that our result will find further applications, especially in the study of low--rank matrix recovery.

In this paper we consider a probabilistic signal-to-interference and-noise ratio (SINR) constrained problem for transmit beamforming design in the presence of imperfect channel state information (CSI), under a multiuser multiple-input single-output (MISO) downlink scenario. In particular, we deal with outage-based quality-of-service constraints, where the probability of each user's SINR not satisfying a service requirement must not fall below a given outage probability specification. The study of solution approaches to the probabilistic SINR constrained problem is important because CSI errors are often present in practical systems and they may cause substantial SINR outages if not handled properly. However, a major technical challenge is how to process the probabilistic SINR constraints. To tackle this, we propose a novel relaxation- restriction (RAR) approach, which consists of two key ingredients-semidefinite relaxation (SDR), and analytic tools for conservatively approximating probabilistic constraints. The underlying goal is to establish approximate probabilistic SINR constrained formulations in the form of convex conic optimization problems, so that they can be readily implemented by available solvers. Using either an intuitive worst-case argument or specialized probabilistic results, we develop various conservative approximation schemes for processing probabilistic constraints with quadratic uncertainties. Consequently, we obtain several RAR alternatives for handling the probabilistic SINR constrained problem. Our techniques apply to both complex Gaussian CSI errors and i.i.d. bounded CSI errors with unknown distribution. Moreover, results obtained from our extensive simulations show that the proposed RAR methods significantly improve upon existing ones, both in terms of solution quality and computational complexity.

Recently, robust transmit beamforming has drawn considerable attention because it can provide guaranteed receiver performance in the presence of channel state information (CSI) errors. Assuming complex Gaussian distributed CSI errors, this paper investigates the robust beamforming design problem that minimizes the transmission power subject to probabilistic signal-to-interference-plus-noise ratio (SINR) constraints. The probabilistic SINR constraints in general have no closed-form expression and are difficult to handle. Based on a Bernstein-type inequality of complex Gaussian random variables, we propose a conservative formulation to the robust beamforming design problem. The semidefinite relaxation technique can be applied to efficiently handle the proposed conservative formulation. Simulation results show that, in comparison with the existing methods, the proposed method is more power efficient and is able to support higher target SINR values for receivers., Comment: This paper has been withdrawn by the authors

In this paper, we study the optimal secondary-link beamforming pattern that balances between the SU's throughput and the interference it causes to PUs in MIMO cognitive radio networks. In particular, we aim to maximize the throughput of the SU, while keeping the interference temperature at the primary receivers below a certain threshold. Unlike traditional MIMO systems, SUs may not have the luxury of knowing the channel state information (CSI) on the links to PUs. This presents a key challenge for a secondary transmitter to steer interference away from primary receivers. In this paper, we consider three scenarios, namely when the secondary transmitter has complete, partial, or no knowledge about the channels to the primary receivers. In particular, when complete CSI is not available, the interference-temperature constraints are to be satisfied with high probability, thus resulting in chance constraints that are typically hard to deal with. Our contribution is fourfold. First, by analyzing the distributional characteristics of MIMO channels, we propose a unified homogeneous QCQP formulation that can be applied to all three scenarios. The homogeneous QCQP formulation, though non-convex, is amenable to semidefinite programming (SDP) relaxation methods. Secondly, we show that the SDP relaxation admits no gap when the number of primary links is no larger than two. Thirdly, we propose a randomized polynomial-time algorithm for constructing a near-optimal solution to the QCQP problem when there are more than two primary links. Finally, we show that when the secondary transmitter has no CSI on the links to primary receivers, the optimal solution to the QCQP problem can be found by a simple matrix eigenvalue-eigenvector computation, which can be done much more efficiently than solving the QCQP directly., Comment: 12 pages 6 Figures

Adaptive OFDMA has recently been recognized as a promising technique for providing high spectral efficiency in future broadband wireless systems. The research over the last decade on adaptive OFDMA systems has focused on adapting the allocation of radio resources, such as subcarriers and power, to the instantaneous channel conditions of all users. However, such "fast" adaptation requires high computational complexity and excessive signaling overhead. This hinders the deployment of adaptive OFDMA systems worldwide. This paper proposes a slow adaptive OFDMA scheme, in which the subcarrier allocation is updated on a much slower timescale than that of the fluctuation of instantaneous channel conditions. Meanwhile, the data rate requirements of individual users are accommodated on the fast timescale with high probability, thereby meeting the requirements except occasional outage. Such an objective has a natural chance constrained programming formulation, which is known to be intractable. To circumvent this difficulty, we formulate safe tractable constraints for the problem based on recent advances in chance constrained programming. We then develop a polynomial-time algorithm for computing an optimal solution to the reformulated problem. Our results show that the proposed slow adaptation scheme drastically reduces both computational cost and control signaling overhead when compared with the conventional fast adaptive OFDMA. Our work can be viewed as an initial attempt to apply the chance constrained programming methodology to wireless system designs. Given that most wireless systems can tolerate an occasional dip in the quality of service, we hope that the proposed methodology will find further applications in wireless communications.

Motivated by the philosophy and phenomenal success of compressed sensing, the problem of reconstructing a matrix from a sampling of its entries has attracted much attention recently. Such a problem can be viewed as an information-theoretic variant of the well-studied matrix completion problem, and the main objective is to design an efficient algorithm that can reconstruct a matrix by inspecting only a small number of its entries. Although this is an impossible task in general, Cand\`es and co-authors have recently shown that under a so-called incoherence assumption, a rank $r$ $n\times n$ matrix can be reconstructed using semidefinite programming (SDP) after one inspects $O(nr\log^6n)$ of its entries. In this paper we propose an alternative approach that is much more efficient and can reconstruct a larger class of matrices by inspecting a significantly smaller number of the entries. Specifically, we first introduce a class of so-called stable matrices and show that it includes all those that satisfy the incoherence assumption. Then, we propose a randomized basis pursuit (RBP) algorithm and show that it can reconstruct a stable rank $r$ $n\times n$ matrix after inspecting $O(nr\log n)$ of its entries. Our sampling bound is only a logarithmic factor away from the information-theoretic limit and is essentially optimal. Moreover, the runtime of the RBP algorithm is bounded by $O(nr^2\log n+n^2r)$, which compares very favorably with the $\Omega(n^4r^2\log^{12}n)$ runtime of the SDP-based algorithm. Perhaps more importantly, our algorithm will provide an exact reconstruction of the input matrix in polynomial time. By contrast, the SDP-based algorithm can only provide an approximate one in polynomial time., Comment: 23 pages. New section (Section 3.3) added