This paper deals with the generalization of the theorems of alternatives in semidefinite programming proposed by Balakrishnan and Vandenberghe. In their original form, the theorems assume that the domain of the linear...
详细信息
ISBN:
(纸本)9781424415304
This paper deals with the generalization of the theorems of alternatives in semidefinite programming proposed by Balakrishnan and Vandenberghe. In their original form, the theorems assume that the domain of the linear mapping be a finite-dimensional Hilbert space. We show that the validity of the basic theorems does not rely on the finite-dimensional assumption, and the derived theorems can also be appropriately generalized. The Moore-Penrose inverse plays a crucial role in the generalization.
In this paper, we design downlink (DL) beamforming vectors for a multiuser multicell network when only imperfect knowledge of the channel covariance is available at base stations. Specifically, we consider two differe...
详细信息
ISBN:
(纸本)9781424492688
In this paper, we design downlink (DL) beamforming vectors for a multiuser multicell network when only imperfect knowledge of the channel covariance is available at base stations. Specifically, we consider two different models for covariance errors: a) deterministic error bounded in a spherical region and b) stochastic error with known probability distribution. Our objective is to minimize the total DL transmit power subject to quality of service (QoS) constraint of every user. It is shown that for both uncertainty models, the optimization can be formulated as a convex semidefinite programming (SDP) problem using the standard rank relaxation approach. Interestingly, numerical results show that the obtained solutions fulfill the rank constraint and are therefore exact.
We study the problem of approximating the joint spectral radius (JSR) of a finite set of matrices. Our approach is based on the analysis of the underlying switched linear system via inequalities imposed between multip...
详细信息
ISBN:
(纸本)9781450306294
We study the problem of approximating the joint spectral radius (JSR) of a finite set of matrices. Our approach is based on the analysis of the underlying switched linear system via inequalities imposed between multiple Lyapunov functions associated to a labeled directed graph. Inspired by concepts in automata theory and symbolic dynamics, we define a class of graphs called path-complete graphs, and show that any such graph gives rise to a method for proving stability of the switched system. This enables us to derive several asymptotically tight hierarchies of semidefinite programming relaxations that unify and generalize many existing techniques such as common quadratic, common sum of squares, maximum/minimum-of-quadratics Lyapunov functions. We characterize all path-complete graphs consisting of two nodes on an alphabet of two matrices and compare their performance. For the general case of any set of n x n matrices we propose semidefinite programs of modest size that approximate the JSR within a multiplicative factor of 1/4 root n of the true value. We establish a notion of duality among path-complete graphs and a constructive converse Lyapunov theorem for maximum/minimum-of-quadratics Lyapunov functions.
In this paper analytical solution of fastest mixing Markov chain problem over a sensor network with K-partite topology is provided. The solution procedure consists of Stratification of sensor network's connectivit...
详细信息
ISBN:
(纸本)9781424495375
In this paper analytical solution of fastest mixing Markov chain problem over a sensor network with K-partite topology is provided. The solution procedure consists of Stratification of sensor network's connectivity graph and semidefinite programming. The studied topologies are evaluated in terms of asymptotic and per step convergence rates. The obtained optimal transition probabilities have been compared with those obtained from Metropolis-Hasting method by comparing mixing time improvements numerically.
The success of many machine learning and pattern recognition methods relies heavily upon the identification of an appropriate distance metric on the input data. It is often beneficial to learn such a metric from the i...
详细信息
The success of many machine learning and pattern recognition methods relies heavily upon the identification of an appropriate distance metric on the input data. It is often beneficial to learn such a metric from the input training data, instead of using a default one such as the Euclidean distance. In this work, we propose a boosting-based technique, termed BOOSTMETRIC, for learning a quadratic Mahalanobis distance metric. Learning a valid Mahalanobis distance metric requires enforcing the constraint that the matrix parameter to the metric remains positive semidefinite. semidefinite programming is often used to enforce this constraint, but does not scale well and is not easy to implement. BOOSTMETRIC is instead based on the observation that any positive semidefinite matrix can be decomposed into a linear combination of trace-one rank-one matrices. BOOSTMETRIC thus uses rank-one positive semidefinite matrices as weak learners within an efficient and scalable boosting-based learning process. The resulting methods are easy to implement, efficient, and can accommodate various types of constraints. We extend traditional boosting algorithms in that its weak learner is a positive semidefinite matrix with trace and rank being one rather than a classifier or regressor. Experiments on various data sets demonstrate that the proposed algorithms compare favorably to those state-of-the-art methods in terms of classification accuracy and running time.
The last decade witnessed the burgeoning development in the reconstruction of signals by exploiting their low-dimensional structures, particularly, the sparsity, the block-sparsity, the low-rankness, and the low-dimen...
详细信息
The last decade witnessed the burgeoning development in the reconstruction of signals by exploiting their low-dimensional structures, particularly, the sparsity, the block-sparsity, the low-rankness, and the low-dimensional manifold structures of general nonlinear data sets. The reconstruction performance of these signals relies heavily on the structure of the sensing matrix/operator. In many applications, there is a flexibility to select the optimal sensing matrix among a class of them. A prerequisite for optimal sensing matrix design is the computability of the performance for different recovery algorithms. I present a computational framework for analyzing the recovery performance of signals with low-dimensional structures. I define a family of goodness measures for arbitrary sensing matrices as the optimal values of a set of optimization problems. As one of the primary contributions of this work, I associate the goodness measures with the fixed points of functions defined by a series of linear programs, second-order cone programs, or semidefinite programs, depending on the specific problem. This relation with the fixed-point theory, together with a bisection search implementation, yields efficient algorithms to compute the goodness measures with global convergence guarantees. As a by-product, we implement efficient algorithms to verify sufficient conditions for exact signal recovery in the noise-free case. The implementations perform orders-of-magnitude faster than the state-of-the-art techniques. The utility of these goodness measures lies in their relation with the reconstruction performance. I derive bounds on the recovery errors of convex relaxation algorithms in terms of these goodness measures. Using tools from empirical processes and generic chaining, I analytically demonstrate that as long as the number of measurements are relatively large, these goodness measures are bounded away from zeros for a large class of random sensing matrices, a result parallel
Balakrishnan and Vandenberghe have given an elegant proof of the KYP lemma based on their theorems of alternatives in semidefinite programming. Based also on these theorems, this paper gives a proof of a generalized v...
详细信息
ISBN:
(纸本)9787811240559
Balakrishnan and Vandenberghe have given an elegant proof of the KYP lemma based on their theorems of alternatives in semidefinite programming. Based also on these theorems, this paper gives a proof of a generalized version of the discrete-time KYP lemma. In addition, we point out that in the nonstrict case of Balakrishnan and Vandenberghe's (continuous-time) KYP formulation the hypothesis that M-22 be positive semidefinite can be dropped.
We consider the problems of finding a caterpillar tree in a graph. We first prove that, unless P=NP, there is no approximation algorithms for finding a minimum spanning caterpillar in a graph within a factor of f(n); ...
详细信息
ISBN:
(纸本)9781920682989
We consider the problems of finding a caterpillar tree in a graph. We first prove that, unless P=NP, there is no approximation algorithms for finding a minimum spanning caterpillar in a graph within a factor of f(n); where f(n) is any polynomial time computable function of n, the order of the graph. Then we present a quadratic integer programming formulation for the problem that can be a base for a branch and cut algorithm. We also show that by using Gomory cuts iteratively, one can obtain a solution for the problem that is close to the optimal value by a factor of 1/ε, for 0 < ε < 1. Finally, we show that our formulation is equivalent to a semidefinite programming formulation, which introduces another approach for solving the problem.
Based on the semidefinite programming relaxation model of the code division multiple access maximum likelihood multiuser detection problem,a detection strategy by successive linear programming method is *** proposed m...
详细信息
Based on the semidefinite programming relaxation model of the code division multiple access maximum likelihood multiuser detection problem,a detection strategy by successive linear programming method is *** proposed method converts the semidefinite programming relaxation to a nonlinear programming problem by the semidefinite matrix factorization.A successive linear programming method is used to solve the nonlinear *** with randomized method,a suboptimal solution is obtained for the multiuser detection *** results show that the bit error rate performances of a detection strategy based on the successive linear programming method is almost similar to that of the detection strategy based on the semidefinite programming ***,average CPU time of the successive linear programming method is lower than that of the semidefinite programming relaxation method.
We provide a general framework of utilizing the no-signaling principle in derivation of the guessing probability in the minimum-error quantum state discrimination. We show that, remarkably, the guessing probability ca...
详细信息
We provide a general framework of utilizing the no-signaling principle in derivation of the guessing probability in the minimum-error quantum state discrimination. We show that, remarkably, the guessing probability can be determined by the no-signaling principle. This is shown by proving that, in the semidefinite programing for the discrimination, the optimality condition corresponds to the constraint that quantum theory cannot be used for a superluminal communication. Finally, a general bound to the guessing probability is presented in a closed form.
暂无评论