Nonnegative matrix factorization (NMF) under the separability assumption can provably be solved efficiently, even in the presence of noise, and has been shown to be a powerful technique in document classification and ...
详细信息
Nonnegative matrix factorization (NMF) under the separability assumption can provably be solved efficiently, even in the presence of noise, and has been shown to be a powerful technique in document classification and hyperspectral unmixing. This problem is referred to as near-separable NMF and requires that there exists a cone spanned by a small subset of the columns of the input nonnegative matrix approximately containing all columns. In this paper, we propose a preconditioning based on the minimum volume ellipsoid and semidefinite programming making the input matrix well-conditioned. This in turn can improve significantly the performance of near-separable NMF algorithms which is illustrated on the popular successive projection algorithm (SPA). The new preconditioned SPA is provably more robust to noise, and outperforms SPA on several synthetic data sets. We also show how an active-set method allows us to apply the preconditioning on large-scale real-world hyperspectral images.
For nonnegative integers n, d, and w, let A(n, d, w) be the maximum size of a code C subset of F-n 2 with a constant weight w and minimum distance at least d(2). We consider two semidefinite programs based on quadrupl...
详细信息
For nonnegative integers n, d, and w, let A(n, d, w) be the maximum size of a code C subset of F-n 2 with a constant weight w and minimum distance at least d(2). We consider two semidefinite programs based on quadruples of code words that yield several new upper bounds on A(n, d, w). The new upper bounds imply that A(22, 8, 10) = 616 and A(22, 8, 11) = 672. Lower bounds on A(22, 8, 10) and A(22, 8, 11) are obtained from the (n, d) = (22, 7) shortened Golay code of size 2048. It can be concluded that the shortened Golay code is a union of constant-weight w codes of sizes A(22, 8, w).
Several important problems in control theory can be reformulated as semidefinite programming problems, i.e., minimization of a linear objective subject to linear matrix inequality (LMI) constraints. From convex optimi...
详细信息
Several important problems in control theory can be reformulated as semidefinite programming problems, i.e., minimization of a linear objective subject to linear matrix inequality (LMI) constraints. From convex optimization duality theory, conditions for infeasibility of the LMIs, as well as dual optimization problems, can be formulated. These can in turn be reinterpreted in control or system theoretic terms, often yielding new results or new proofs for existing results from control theory. We explore such connections for a few problems associated with linear time-invariant systems.
semidefinite programs have recently turned out to be a powerful tool for approximating integer problems. To survey the development in this area over the last few years, the following topics are addressed in some detai...
详细信息
semidefinite programs have recently turned out to be a powerful tool for approximating integer problems. To survey the development in this area over the last few years, the following topics are addressed in some detail. First, we investigate ways to derive semidefinite programs from discrete optimization problems. The duality theory for semidefinite programs is the key to understand algorithms to solve them. The relevant duality results are therefore summarized. The second part of the paper deals with the approximation of integer problems both in a theoretical setting, and from a computational point of view. (C) 1999 Elsevier Science B.V. and IMACS, All rights reserved.
An SDP relaxation based method is developed to solve the localization problem in sensor networks using incomplete and inaccurate distance information. The problem is set up to find a set of sensor positions such that ...
详细信息
An SDP relaxation based method is developed to solve the localization problem in sensor networks using incomplete and inaccurate distance information. The problem is set up to find a set of sensor positions such that given distance constraints are satisfied. The nonconvex constraints in the formulation are then relaxed in order to yield a semidefinite program that can be solved efficiently. The basic model is extended in order to account for noisy distance information. In particular, a maximum likelihood based formulation and an interval based formulation are discussed. The SDP solution can then also be used as a starting point for steepest descent based local optimization techniques that can further refine the SDP solution. We also describe the extension of the basic method to develop an iterative distributed SDP method for solving very large scale semidefinite programs that arise out of localization problems for large dense networks and are intractable using centralized methods. The performance evaluation of the technique with regard to estimation accuracy and computation time is also presented by the means of extensive simulations. Our SDP scheme also seems to be applicable to solving other Euclidean geometry problems where points are locally connected.
We derive several efficiently computable converse bounds for quantum communication over quantum channels in both the one-shot and asymptotic regime. First, we derive one-shot semidefinite programming (SDP) converse bo...
详细信息
We derive several efficiently computable converse bounds for quantum communication over quantum channels in both the one-shot and asymptotic regime. First, we derive one-shot semidefinite programming (SDP) converse bounds on the amount of quantum information that can be transmitted over a single use of a quantum channel, which improve the previous bound from [Tomamichel/Berta/Renes, Nat. Commun. 7, 2016]. As applications, we study quantum communication over depolarizing channels and amplitude damping channels with finite resources. Second, we find an SDP-strong converse bound for the quantum capacity of an arbitrary quantum channel, which means the fidelity of any sequence of codes with a rate exceeding this bound will vanish exponentially fast as the number of channel uses increases. Furthermore, we prove that the SDP-strong converse bound improves the partial transposition bound introduced by Holevo and Werner. Third, we prove that this SDP strong converse bound is equal to the so-called max-Rains information, which is an analog to the Rains information introduced in [Tomamichel/Wilde/Winter, IEEE Trans. Inf. Theory 63:715, 2017]. Our SDP strong converse bound is weaker than the Rains information, but it is efficiently computable for general quantum channels.
A common technique for passive source localization is to utilize the range-difference (RD) measurements between the source and several spatially separated sensors. The RD information defines a set of hyperbolic equati...
详细信息
A common technique for passive source localization is to utilize the range-difference (RD) measurements between the source and several spatially separated sensors. The RD information defines a set of hyperbolic equations from which the source position can be calculated with the knowledge of the sensor positions. Under the standard assumption of Gaussian distributed RD measurement errors, it is well known that the maximum-likelihood (ML) position estimation is achieved by minimizing a multimodal cost function which corresponds to a difficult task. In this correspondence, we propose to approximate the nonconvex ML optimization by relaxing it to a convex optimization problem using semidefinite programming. A semidefinite relaxation RD-based positioning algorithm, which makes use of the admissible source position information, is proposed and its estimation performance is contrasted with the two-step weighted least squares method and nonlinear least squares estimator as well as Cramer-Rao lower bound.
作者：
Parrilo, PAETH
Swiss Fed Inst Technol Automat Control Lab CH-8092 Zurich Switzerland CALTECH
Control & Dynam Syst Dept Pasadena CA 91125 USA
A hierarchy of convex relaxations for semialgebraic problems is introduced. For questions reducible to a finite number of polynomial equalities and inequalities, it is shown how to construct a complete family of polyn...
详细信息
A hierarchy of convex relaxations for semialgebraic problems is introduced. For questions reducible to a finite number of polynomial equalities and inequalities, it is shown how to construct a complete family of polynomially sized semidefinite programming conditions that prove infeasibility. The main tools employed are a semidefinite programming formulation of the sum of squares decomposition for multivariate polynomials, and some results from real algebraic geometry. The techniques provide a constructive approach for finding bounded degree solutions to the Positivstellensatz, and are illustrated with examples from diverse application fields.
In this paper we analyze a known relaxation for the Sparsest Cut problem based on positive semidefinite constraints, and we present a branch and bound algorithm and heuristics based on this relaxation. The relaxed for...
详细信息
In this paper we analyze a known relaxation for the Sparsest Cut problem based on positive semidefinite constraints, and we present a branch and bound algorithm and heuristics based on this relaxation. The relaxed formulation and the algorithms were tested on small and moderate sized instances. It leads to values very close to the optimum solution values. The exact algorithm could obtain solutions for small and moderate sized instances, and the best heuristics obtained optimum or near optimum solutions for all tested instances. The semidefinite relaxation gives a lower bound C/W and each heuristic produces a cut S with a ratio c(S)/omega(S) where either cs is at most a factor of C or omega(S) is at least a factor of W. We solved the semidefinite relaxation using a semi-infinite cut generation with a commercial linear programming package adapted to the sparsest cut problem. We showed that the proposed strategy leads to a better performance compared to the use of a. known semidefinite programming solver.
In this paper, we investigate semidefinite programming (SDP) lower bounds for the Quadratic Minimum Spanning Tree Problem (QMSTP). Two SDP lower bounding approaches are introduced here. Both apply Lagrangian Relaxatio...
详细信息
In this paper, we investigate semidefinite programming (SDP) lower bounds for the Quadratic Minimum Spanning Tree Problem (QMSTP). Two SDP lower bounding approaches are introduced here. Both apply Lagrangian Relaxation to an SDP relaxation for the problem. The first one explicitly dualizes the semidefiniteness constraint, attaching to it a positive semidefinite matrix of Lagrangian multipliers. The second relies on a semi-infinite reformulation for the cone of positive semidefinite matrices and dualizes a dynamically updated finite set of inequalities that approximate the cone. These lower bounding procedures are the core ingredient of two QMSTP Branch-and-bound algorithms. Our computational experiments indicate that the SDP bounds computed here are very strong, being able to close at least 70% of the gaps of the most competitive formulation in the literature. As a result, their accompanying Branch-and-bound algorithms are competitive with the best previously available QMSTP exact algorithm in the literature. In fact, one of these new Branch-and-bound algorithms stands out as the new best exact solution approach for the problem. (C) 2019 Elsevier B.V. All rights reserved.
暂无评论