We investigate optimal encoding and retrieval of digital data, when the storage/communication medium is described by quantum mechanics. We assume an m-ary alphabet with arbitrary prior distribution, and an n-dimension...
详细信息
We investigate optimal encoding and retrieval of digital data, when the storage/communication medium is described by quantum mechanics. We assume an m-ary alphabet with arbitrary prior distribution, and an n-dimensional quantum system. Under these constraints, we seek an encoding-retrieval setup, comprised of code-states and a quantum measurement, which maximizes the probability of correct detection. In our development, we consider two cases. In the first, the measurement is predefined and we seek the optimal code-states. In the second, optimization is performed on both the code-states and the measurement. We show that one cannot outperform "pseudo-classical transmission," in which we transmit n symbols with orthogonal code-states, and discard the remaining symbols. However, such pseudo-classical transmission is not the only optimum. We fully characterize the collection of optimal setups, and briefly discuss the links between our findings and applications such as quantum key distribution and quantum computing.
A class of important problems in structural mechanics leads to optimization problems with linear objective functions and constraints consisting in (a) linear equalities and (b) inequalities imposed by the material str...
详细信息
A class of important problems in structural mechanics leads to optimization problems with linear objective functions and constraints consisting in (a) linear equalities and (b) inequalities imposed by the material strength, the so-called failure criteria. It is shown that a wide variety of failure criteria can be represented as systems of either second-order cone or semidefinite constraints, giving rise to respective optimization problems.
We propose a Positivstellensatz for trigonometric polynomials that is simpler than its correspondent for polynomials of real variable. Using it, we give a stability test for multidimensional systems, consisting of che...
详细信息
We propose a Positivstellensatz for trigonometric polynomials that is simpler than its correspondent for polynomials of real variable. Using it, we give a stability test for multidimensional systems, consisting of checking the feasibility of a linear matrix inequality. The same result is used for a robust stability test for systems whose coefficients depend polynomially on some bounded parameters. The new tests are either more accurate or faster than previous ones.
We consider the problem of computing the outer-radii of point sets. In this problem, we are given integers n, d, and k, where k 0 when d - k is a fixed constant [M. Badoiu, S. Har-Peled, and P. Indyk, in Proceedings ...
详细信息
We consider the problem of computing the outer-radii of point sets. In this problem, we are given integers n, d, and k, where k <= d, and a set P of n points in R-d. The goal is to compute the outer k-radius of P, denoted by R-k(P), which is the minimum over all (d - k)-dimensional flats F of max(p epsilon P) d(p, F), where d(p, F) is the Euclidean distance between the point p and flat F. Computing the radii of point sets is a fundamental problem in computational convexity with many significant applications. The problem admits a polynomial time algorithm when the dimension d is constant [U. Faigle, W. Kern, and M. Streng, Math. Program., 73 (1996), pp. 1-5]. Here we are interested in the general case in which the dimension d is not fixed and can be as large as n, where the problem becomes NP-hard even for k = 1. It is known that R-k(P) can be approximated in polynomial time by a factor of (1 + epsilon) for any epsilon > 0 when d - k is a fixed constant [M. Badoiu, S. Har-Peled, and P. Indyk, in Proceedings of the ACM Symposium on the Theory of Computing, 2002;S. Har-Peled and K. Varadarajan, in Proceedings of the ACM Symposium on Computing Geometry, 2002]. A polynomial time algorithm that guarantees a factor of O(root log n) approximation for R-1(P), the width of the point set P, is implied by the results of Nemirovski, Roos, and Terlaky [Math. Program., 86 (1999), pp. 463-473] and Nesterov [Handbook of semidefinite programming Theory, Algorithms, Kluwer Academic Publishers, Norwell, MA, 2000]. In this paper, we show that R-k(P) can be approximated by a ratio of O(root log n) for any 1 <= k <= d, thus matching the previously best known ratio for approximating the special case R-1(P), the width of point set P. Our algorithm is based on semidefinite programming relaxation with a new mixed deterministic and randomized rounding procedure. We also prove an inapproximability result that gives evidence that our approximation algorithm is doing well for a large range of k.
The binary quadratic knapsack problem maximizes a quadratic objective function subject to a linear capacity constraint. Due to its simple structure and challenging difficulty it has been studied intensively during the...
详细信息
The binary quadratic knapsack problem maximizes a quadratic objective function subject to a linear capacity constraint. Due to its simple structure and challenging difficulty it has been studied intensively during the last two decades. The present paper gives a survey of upper bounds presented in the literature, and show the relative tightness of several of the bounds. Techniques for deriving the bounds include relaxation from upper planes, linearization, reformulation, Lagrangian relaxation, Lagrangian decomposition, and semidefinite programming. A short overview of heuristics, reduction techniques, branch-and-bound algorithms and approximation results is given, followed by an overview of valid inequalities for the quadratic knapsack polytope. The paper is concluded by an experimental study where the upper bounds presented are compared with respect to strength and computational effort. (c) 2006 Elsevier B.V. All rights reserved.
We consider the problem of estimating a vector x in the linear model Ax approximate to y, where A is a block circulant ( BC) matrix with N blocks and x is assumed to have a weighted norm bound. In the case where both ...
详细信息
We consider the problem of estimating a vector x in the linear model Ax approximate to y, where A is a block circulant ( BC) matrix with N blocks and x is assumed to have a weighted norm bound. In the case where both A and y are subjected to noise, we propose a minimax mean-squared error (MSE) approach in which we seek the linear estimator that minimizes the worst-case MSE over a BC structured uncertainty region. For an arbitrary choice of weighting, we show that the minimax MSE estimator can be formulated as a solution to a semidefinite programming problem ( SDP), which can be solved efficiently. For a Euclidean norm bound on x, the SDP is reduced to a simple convex program with N + 1 unknowns. Finally, we demonstrate through an image deblurring example the potential of the minimax MSE approach in comparison with other conventional methods.
We consider the problem of partitioning the vertices of a weighted graph into two sets of sizes that differ at most by a given threshold B, so as to maximize the weight of the crossing edges. For B equal to 0 this pro...
详细信息
We consider the problem of partitioning the vertices of a weighted graph into two sets of sizes that differ at most by a given threshold B, so as to maximize the weight of the crossing edges. For B equal to 0 this problem is known as Max Bisection, whereas for B equal to the number n of nodes it is the maximum cut problem. We present polynomial time randomized approximation algorithms with non trivial performance guarantees for its solution. The approximation results are obtained by extending the methodology used by Y. Ye for Max Bisection and by combining this technique with another one that uses the algorithm of Goemans and Williamson for the maximum cut problem. When B is equal to zero the approximation ratio achieved coincides with the one obtained by Y. Ye;otherwise it is always above this value and tends to the value obtained by Goemans and Williamson as B approaches the number n of nodes. (c) 2007 Elsevier B.V. All rights reserved.
Embedding algorithms search for a low dimensional continuous representation of data, but most algorithms only handle objects of a single type for which pairwise distances are specified. This paper describes a method f...
详细信息
Embedding algorithms search for a low dimensional continuous representation of data, but most algorithms only handle objects of a single type for which pairwise distances are specified. This paper describes a method for embedding objects of different types, such as images and text, into a single common Euclidean space, based on their co-occurrence statistics. The joint distributions are modeled as exponentials of Euclidean distances in the low-dimensional embedding space, which links the problem to convex optimization over positive semidefinite matrices. The local structure of the embedding corresponds to the statistical correlations via random walks in the Euclidean space. We quantify the performance of our method on two text data sets, and show that it consistently and significantly outperforms standard methods of statistical correspondence modeling, such as multidimensional scaling, IsoMap and correspondence analysis.
Lovasz and Schrijver (SIAM J. Optim. 1:166-190, 1991) have constructed semidefinite relaxations for the stable set polytope of a graph G = (V,E) by a sequence of lift-and-project operations;their procedure finds the s...
详细信息
Lovasz and Schrijver (SIAM J. Optim. 1:166-190, 1991) have constructed semidefinite relaxations for the stable set polytope of a graph G = (V,E) by a sequence of lift-and-project operations;their procedure finds the stable set polytope in at most alpha(G) steps, where alpha(G) is the stability number of G. Two other hierarchies of semidefinite bounds for the stability number have been proposed by Lasserre (SIAM J. Optim. 11:796-817, 2001;Lecture Notes in Computer Science, Springer, Berlin Heidelberg New York, pp 293-303, 2001) and by de Klerk and Pasechnik (SIAM J. Optim. 12:875-892), which are based on relaxing nonnegativity of a polynomial by requiring the existence of a sum of squares decomposition. The hierarchy of Lasserre is known to converge in alpha(G) steps as it refines the hierarchy of Lovasz and Schrijver, and de Klerk and Pasechnik conjecture that their hierarchy also finds the stability number after alpha(G) steps. We prove this conjecture for graphs with stability number at most 8 and we show that the hierarchy of Lasserre refines the hierarchy of de Klerk and Pasechnik.
We show that every real polynomial f nonnegative on [-1, 1](n) can be approximated in the l(1)-norm of coefficients, by a sequence of polynomials {fer} that are sums of squares (s.o.s). This complements the existence ...
详细信息
We show that every real polynomial f nonnegative on [-1, 1](n) can be approximated in the l(1)-norm of coefficients, by a sequence of polynomials {fer} that are sums of squares (s.o.s). This complements the existence of s.o.s. approximations in the denseness result of Berg, Christensen and Ressel, as we provide a very simple and explicit approximation sequence. Then we show that if the moment problem holds for a basic closed semi-algebraic set K-S subset of R-n with nonempty interior, then every polynomial nonnegative on KS can be approximated in a similar fashion by elements from the corresponding preordering. Finally, we show that the degree of the perturbation in the approximating sequence depends on epsilon as well as the degree and the size of coefficients of the nonnegative polynomial f, but not on the specific values of its coefficients.
暂无评论